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

呂志鵬教授團(tuán)隊(duì)合

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

競(jìng)賽獲獎(jiǎng)證書：布局布線算法競(jìng)賽第一名

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

三維芯片設(shè)計(jì)布局布線示意圖

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

芯片設(shè)計(jì)的復(fù)雜度

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