深維科技-北京大學(xué)合作團(tuán)隊(duì)在FPGA'24布線加速競賽中奪得佳績！

獲 獎 情 況

美國西部時(shí)間2024年3月4日，我司與北大合作團(tuán)隊(duì)在FPGA'24布線加速競賽中獲得優(yōu)異的成績。此次比賽由AMD公司組織并在美國加州舉辦，共歷時(shí)3個(gè)月，來自北京大學(xué)、香港中文大學(xué)、中國科學(xué)技術(shù)大學(xué)、加拿大奎爾夫大學(xué)等40支隊(duì)伍、遍布15個(gè)國家和地區(qū)、超過150名選手報(bào)名參賽。

賽事現(xiàn)場

經(jīng)過激烈的角逐，最終有十支隊(duì)伍成功入圍決賽。決賽通過15個(gè)隱藏用例的評比，計(jì)算出各個(gè)隊(duì)伍的平均分?jǐn)?shù)，并根據(jù)最終得分進(jìn)行排名。AceRoute以優(yōu)異的成績獲得了該次比賽的第三名。

AceRoute介紹

AceRoute基于PathFinder協(xié)商布線算法，采用迭代方法消除擁塞并優(yōu)化其關(guān)鍵路徑，參考RWRoute的擁塞代價(jià)管理策略，實(shí)現(xiàn)高效的C++布線引擎。同時(shí)提出自定義的擴(kuò)展連接邊界框的方法，以更好的管理連接并優(yōu)化布線結(jié)果。這些方法的綜合應(yīng)用有助于提高電路性能和可靠性。

Aceroute采用遞歸網(wǎng)表分割，將網(wǎng)表分割成3到n個(gè)平衡子集。根據(jù)源和匯位置設(shè)計(jì)切割線，每次迭代地劃分子集，利用任務(wù)流確保執(zhí)行順序并避免沖突。后期迭代中，動態(tài)重新分區(qū)以保持負(fù)載平衡。

Aceroute在處理內(nèi)部連接問題時(shí)，采用了雙向A*算法。這種算法同時(shí)從源節(jié)點(diǎn)（正向）和匯節(jié)點(diǎn)（反向）開始搜索，以尋找最佳路徑。這種雙向搜索方法在內(nèi)部連接問題中非常有效，因?yàn)樗軌驕p少搜索過程中訪問的節(jié)點(diǎn)數(shù)量，并且能夠保證找到的路徑是最優(yōu)的，從而提高了內(nèi)部連接問題的解決效率。

在競賽基準(zhǔn)測試中，對比AMD/Xilinx研究實(shí)驗(yàn)室和比利時(shí)根特大學(xué)聯(lián)合研發(fā)的高質(zhì)量布線器RWRoute平均速度提升了2.5倍，而且實(shí)現(xiàn)了相同的布線質(zhì)量。AceRoute同時(shí)也成功超越了商業(yè)工具Vivado布線器的性能。

審核編輯：劉清