11月4日，在電子設計自動化（EDA）領域的國際會議計算機輔助設計國際會議（ICCAD2021）上，華中科技大學計算機學院呂志鵬教授團隊獲得了CAD Contest布局布線（Routing with Cell Movement Advanced）算法競賽的第一名。團隊成員還包括博士生蘇宙行、研究生羅燦輝、梁鏡湖和謝振軒。

呂志鵬教授團隊合

ICCAD會議始于1980年，是電子設計自動化領域歷史最悠久的頂級學術會議之一，其中CAD Contest算法競賽作為會議的標志性事件，長期以來受到國際學術界與工業(yè)界的廣泛關注。每屆競賽的賽題均來自Cadence、Synopsys、Mentor Graphics、Nvidia、IBM等全球著名EDA或半導體公司的真實業(yè)務場景，涵蓋集成電路設計、制造與測試等環(huán)節(jié)中的核心算法難題，如邏輯綜合、布局布線、等價驗證、時序分析等。本屆CAD Contest算法競賽共有來自12個國家/地區(qū)的137支隊伍參與，包括眾多國內(nèi)外知名高校與研究機構(gòu)，如加州大學伯克利分校、東京大學、臺灣大學、香港中文大學、復旦大學等。

競賽獲獎證書：布局布線算法競賽第一名

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

三維芯片設計布局布線示意圖

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

芯片設計的復雜度

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