華中大團(tuán)隊斬獲算法競賽冠軍：團(tuán)隊獲得CAD Contest布局布線算法競賽第一名！

11月4日結(jié)束的EDA(電子設(shè)計自動化)領(lǐng)域國際會議ICCAD 2021(計算機(jī)輔助設(shè)計國際會議)傳來好消息，華中科技大學(xué)計算機(jī)學(xué)院呂志鵬教授團(tuán)隊獲得了CAD Contest布局布線算法競賽的第一名。這是團(tuán)隊首次參賽，成員還包括蘇宙行博士、研究生羅燦輝、梁鏡湖和謝振軒，平均年齡才24歲。

ICCAD會議始于1980年，是EDA領(lǐng)域歷史最悠久的頂級學(xué)術(shù)會議之一，其中CAD Contest算法競賽作為會議的標(biāo)志性事件，長期以來受到國際學(xué)術(shù)界與工業(yè)界的廣泛關(guān)注，此次共有來自12個國家和地區(qū)的137支隊伍參賽，包括眾多知名高校與研究機(jī)構(gòu)，如加州大學(xué)伯克利分校、東京大學(xué)、臺灣大學(xué)、香港中文大學(xué)、復(fù)旦大學(xué)等。

EDA是電子設(shè)計的基石產(chǎn)業(yè)，也被譽(yù)為“芯片之母”。本屆競賽的布局布線問題作為EDA芯片后端物理設(shè)計中最重要的環(huán)節(jié)，直接影響芯片的功耗、面積、時延等各項性能指標(biāo)。其中，布局過程需將一系列電路單元放置于給定的長方體空間中;而布線過程則需將屬于同一個網(wǎng)的單元引腳用導(dǎo)線連接起來。參賽算法需要在考慮空間容量、電壓區(qū)、最小布線層、金屬層布線方向等眾多真實約束的情況下，確定每個單元在芯片內(nèi)的位置，并同時為每個網(wǎng)規(guī)劃無短路、無斷路的信號傳輸路徑，使得導(dǎo)線的加權(quán)總長度最短。

Electronic Design Automation，電子設(shè)計自動化的意思。最早是為了解決集成電路布局布線問題而出現(xiàn)的，后來學(xué)術(shù)界和工業(yè)界的一些人覺得用計算機(jī)手段幫助設(shè)計電路挺有意思，就搞了個會議叫Design Automation Conference (DAC)。開始討論一些利用計算機(jī)輔助手段解決集成電路設(shè)計的問題。同時期UC Berkeley開發(fā)了一個求解電路的數(shù)值軟件，也就是后來的SPICE(Simulation Program with IC Emphasis)這兩個事件也許算是EDA產(chǎn)業(yè)的伏筆。

EDA真正開始是上世紀(jì)80年代的某一次DAC上，有人覺得可以利用計算機(jī)輔助軟件賺取設(shè)計廠商的錢，于是大家紛紛發(fā)現(xiàn)了商機(jī)，EDA產(chǎn)業(yè)就這么雨后春筍般的起來了。后來隨著集成電路規(guī)模越來越大，EDA的應(yīng)用不僅僅限于布線和數(shù)值仿真，高層次的數(shù)字設(shè)計又催生了硬件描述語言Verilog和VHDL。一直到今天，個人感覺EDA里最大塊的三部分就是高層次設(shè)計相關(guān)的部分，驗證/綜合/布局相關(guān)的部分，和偏底層的SPICE仿真。當(dāng)然現(xiàn)在隨著集成電路尺寸到了20納米下，各種其他問題也越來越受到關(guān)注，比如良率，信號完整性，甚至封裝，EDA充斥在IC產(chǎn)業(yè)的方方面面。

這個行業(yè)曾經(jīng)是IC產(chǎn)業(yè)中最暴利的一環(huán)，從業(yè)者也是IC行業(yè)中知識最全面最聰明的一批。不過由于在IC產(chǎn)業(yè)內(nèi)創(chuàng)業(yè)門檻低，越來越多的人加入到競爭中，在幾十年的競爭和吞并后，現(xiàn)在已經(jīng)成了Synopsys和Cadence兩家獨大的局面了，另外受到整個IC行業(yè)下行的影響，油水也大不如前，EDA從業(yè)者的技能也被細(xì)化，是個容易進(jìn)入不容易離開的行業(yè)。

EDA是電子設(shè)計的基石產(chǎn)業(yè)，也被譽(yù)為“芯片之母”。本屆競賽的布局布線問題作為EDA芯片后端物理設(shè)計中最重要的環(huán)節(jié)，直接影響芯片的功耗、面積、時延等各項性能指標(biāo)。其中，布局過程需將一系列電路單元放置于給定的長方體空間中;而布線過程則需將屬于同一個網(wǎng)的單元引腳用導(dǎo)線連接起來。參賽算法需要在考慮空間容量、電壓區(qū)、最小布線層、金屬層布線方向等眾多真實約束的情況下，確定每個單元在芯片內(nèi)的位置，并同時為每個網(wǎng)規(guī)劃無短路、無斷路的信號傳輸路徑，使得導(dǎo)線的加權(quán)總長度最短。呂志鵬教授團(tuán)隊所設(shè)計的啟發(fā)式優(yōu)化算法，在冗余導(dǎo)線檢測、布線環(huán)路消除、并行化鄰域評估加速、布局調(diào)整最優(yōu)移動區(qū)域識別等多項關(guān)鍵技術(shù)上實現(xiàn)了突破。根據(jù)ICCAD 2021會議公布的競賽結(jié)果，該團(tuán)隊所設(shè)計的算法在所有測試算例上均達(dá)到了競賽中的最優(yōu)結(jié)果。據(jù)悉，今年是該團(tuán)隊首次參加ICCAD競賽。

呂志鵬教授團(tuán)隊設(shè)計的啟發(fā)式優(yōu)化算法，在冗余導(dǎo)線檢測、布線環(huán)路消除、并行化鄰域評估加速、布局調(diào)整最優(yōu)移動區(qū)域識別等多項關(guān)鍵技術(shù)上實現(xiàn)了突破。根據(jù)ICCAD 2021會議公布的競賽結(jié)果，該團(tuán)隊設(shè)計的算法在所有測試算例上均達(dá)到了競賽中的最優(yōu)結(jié)果。

此時此刻，離武漢千里之外的成都，2020年扎根的初創(chuàng)型企業(yè)英諾達(dá)也正在深耕EDA領(lǐng)域。這家企業(yè)于今年初搭建了國內(nèi)首個EDA硬件工具云賦能平臺，8月獲得近億元融資，10月獲得中國半導(dǎo)體協(xié)會“創(chuàng)芯中國”總決賽一等獎。

“武漢同行問鼎世界頂尖賽事，給我們帶來極大的振奮，也鼓舞我們加快技術(shù)研發(fā)步伐?！?1月11日，英諾達(dá)市場和業(yè)務(wù)拓展部副總裁馬超在接受紅星新聞記者采訪時透露，除了搭建EDA相關(guān)技術(shù)平臺外，公司已擁有自研的EDA，聚焦于國內(nèi)同行尚未涉足的數(shù)字中端領(lǐng)域，年底會有原型產(chǎn)品面市，希望能助力成都電子信息產(chǎn)業(yè)補(bǔ)齊IC設(shè)計短板。

“實際上，我們的創(chuàng)新突破主要在商業(yè)模式和運營上，通過自主可控的技術(shù)平臺，力爭打破國外“卡脖子”現(xiàn)象，平臺會賦能中小企業(yè)，降低國內(nèi)企業(yè)研發(fā)成本，同時也會幫助芯片設(shè)計行業(yè)加速向云端遷移?！瘪R超說。

在成都的集成電路產(chǎn)業(yè)版圖上，已初步形成了IC設(shè)計、晶圓制造、封裝測試、材料與配套、系統(tǒng)與整機(jī)等相對完整的發(fā)展體系，然而，與IC設(shè)計緊密相關(guān)的EDA技術(shù)領(lǐng)域一直存在短板，本地EDA企業(yè)發(fā)展尚未成勢，一些產(chǎn)業(yè)空白亟待填補(bǔ)。

“我們有自研的EDA，聚焦國內(nèi)目前無人涉足的數(shù)字中端領(lǐng)域，開發(fā)有自主知識產(chǎn)權(quán)的專門型產(chǎn)品和通用型平臺，希望能助力IC設(shè)計產(chǎn)業(yè)早日補(bǔ)齊短板?！瘪R超介紹，公司圍繞EDA硬件工具云賦能平臺，目前正在申請3項專利。

EDA作為我國“卡脖子”關(guān)鍵技術(shù)之一，難點主要在于算法，其核心問題在算法上通常具有極高的計算復(fù)雜度，即為NP難問題。本次競賽的布局布線問題，涉及了圖著色、集合劃分、二次指派、廣義指派、斯坦納樹、斯坦納森林等眾多經(jīng)典的NP難問題，是計算復(fù)雜性理論研究與實際工業(yè)應(yīng)用相結(jié)合的典型場景。

值得注意的是，這支實力雄厚的參賽團(tuán)隊非常年輕，包括蘇宙行博士、研究生羅燦輝、梁鏡湖和謝振軒。其中，謝振軒、梁鏡湖均生于1999年，羅燦輝生于1998年。

此外，導(dǎo)師呂志鵬關(guān)注芯片領(lǐng)域不到三年。在此之前，他主攻算法研究，2018年，他帶領(lǐng)實驗室里一群計算機(jī)專業(yè)出身、毫無任何芯片背景的“熱心群眾”，跳進(jìn)了芯片主戰(zhàn)場。年輕團(tuán)隊首次參賽即奪冠，背后是實驗室團(tuán)隊40余年的積累。

“我們深知，要想把科研成果寫在祖國大地上，絕不能停留在學(xué)術(shù)研究的表面，一定要結(jié)合實際應(yīng)用并落地。我們希望借助研究所數(shù)十年的積累與傳承，一方面賦能中國企業(yè)解決EDA‘卡脖子’問題，另一方面為國家培養(yǎng)更多掌握核心技術(shù)的人才?！?

導(dǎo)師呂志鵬關(guān)注芯片領(lǐng)域不到三年。在此之前，他主攻算法研究，2018年，他帶領(lǐng)實驗室里一群計算機(jī)專業(yè)出身、毫無任何芯片背景的“熱心群眾”，跳進(jìn)了芯片主戰(zhàn)場。年輕團(tuán)隊首次參賽即奪冠，背后是實驗室團(tuán)隊40余年的積累。

據(jù)官網(wǎng)介紹，呂志鵬教授所在實驗室自成立至今的40余年來，一直聚焦于NP難問題的求解算法與工業(yè)應(yīng)用研究，曾多次獲得國際算法競賽全球前三名，如：2021年GECCO“最優(yōu)相機(jī)布局與集合覆蓋”國際算法競賽第一名;2021年ISPD“晶圓級物理建?！鼻蟹植季植季€國際算法競賽第三名;2020年GECCO“最優(yōu)相機(jī)布局與集合覆蓋”國際算法競賽第一名;2018年SAT國際算法競賽第三名;2017年SAT國際算法競賽第一名;2016年ROADEF/EURO“液化氣庫存路由”國際算法挑戰(zhàn)賽第三名;2010年國際護(hù)士排班算法競賽第三名;2008年國際大學(xué)排課表算法競賽第二名等。