VLSI中X結構多層總體佈線問題：X結構帶來物理設計諸多性能的提高,該結構的引入和多層工藝的普及,使得總體佈線算法更復雜，目前缺乏一種解決非曼哈頓結構下多層總體佈線問題的有效算法。
鑑於總體佈線是VLSI物理設計中極為重要的一部分,學者們提出很多有效的算法。（1）大部分總體佈線算法都是以曼哈頓結構為模型基礎開展相關工作,而基於曼哈頓結構的優化策略在進行互連線線長優化時,由於繞線方向只能為水平和垂直,其優化能力受限。因此,研究人員開始嘗試以非曼哈頓結構為基礎模型進行佈線,實現芯片整體性能的優化。（2）此外,隨著集成電路設計進入納米領域,佈線層數增加,使電路的性能和密度得到了很大的提高,因此多層佈線應運而生,並且引起了諸多研究機構的廣泛關注。
而現有關於非曼哈頓結構總體佈線問題的研究中,僅侷限於單層結構總體佈線問題的研究,尚未開展考慮到非曼哈頓結構、多層結構兩個條件的總體佈線算法研究。因此,本文以X結構作為非曼哈頓結構的代表,基於整數規劃模型(Integer Linear Programming,ILP)和粒子群優化算法(Particle Swarm Optimization,PSO) ,提出了三種有效的加強策略 ,從而構建了一種高性能X結構多層總體佈線器，ML-XGRouter。
（1）ML-XGRouter採用“增加新型走線方式”策略,增加新型走線方式有助於初始階段中放棄連接的線網集在主階段的布通率。
在本文主階段中,設計了新型走線方式,針對水平或垂直關係的線網採用圖1(a)和1(b)的兩種連接方式,而針對450或1350關係的線網(N2)採用圖1(c) 的連接方式,通過新增佈線方式,主階段可合理避開擁擠區域。實驗結果表明通過採用“增加新型走線方式”策略相對未採用該策略的總體佈線結果在總溢出數方面取得了16.63%的減少率，從而表明該策略有助於主階段儘可能多連接線網，從而提高布通率。
圖1 “增加新型走線方式”策略
（2）ML-XGRouter採用“PSO與迷宮算法的結合”策略, 將基於新佈線代價的迷宮佈線策略移至主階段中每次box區域內的PSO佈線後,可有效提高當前box未布通線網集的布通率。
先前工作的迷宮佈線是放在主階段之後,容易堆積非常多的未布通線網,嚴重影響到PSO算法的求解質量.如圖2所示, P1和P2在box0的階段中,由於灰色擁擠區域的存在,P1和P2在採用先前工作的邊接連方式,是不能在box0階段完成佈線.而如果等到box0擴張到整個芯片的階段,P1和P2可能要採用圖2的實線連接,佔用更多的佈線資源,從而導致溢出數的增加.而ML-XGRouter會在box0佈線結束後,立即引入迷宮佈線連接PSO未能佈線的線網,即採用圖2的虛線進行連接,儘可能佔用box0附近的資源 ,可有效減少佈線資源的冗餘佔用,有效提高佈線的完成率。實驗結果表明採用“PSO與迷宮算法的結合”策略相對未採用該策略的總體佈線結果在總溢出數取得了77.01%的大幅度減少率,表明該策略有助於在主階段合理使用線網附近的佈線資源,從而產生更少的溢出。
圖2 “PSO與迷宮算法的結合”策略
（3）ML-XGRouter採用“初始佈線階段的佈線容量縮減”策略, 將初始佈線階段的佈線容量縮減到原容量的一半,使得部分線網留在主階段用PSO算法佈線,從而可有效利用PSO算法的全局優化能力,同時進一步加強上述（1）和（2）兩種策略的優化效果。
如圖3所示,假設初始佈線中線網的佈線順序為N1(包含N11和N12引腳),N2(包含N21和N22引腳),N3(包含N31和N32引腳),佈線邊的最大容量為2.採用先前工作的佈線策略,即將N1和N2優先連接,而在主階段中N3的連接需要佔用非常多的佈線資源,如圖3(a)所示。但如果採用本文的“初始佈線階段的佈線容量縮減”策略,預留一半的佈線資源,初始佈線只連接N1,而N2和N3則留在主階段處理,PSO算法可從全局的角度去衡量N2和N3的佈線方式,從而得到圖3(b)的方案,以更少的佈線資源完成N1,N2和N3的連接。
(a) 未採用“初始佈線階段的佈線容量縮減”策略
(b) 採用“初始佈線階段的佈線容量縮減”策略 圖3 “初始佈線階段的佈線容量縮減” 策略
ML-XGRouter是第一次求解非曼哈頓結構下多層總體佈線問題。實驗結果表明本文提出的三種策略對溢出數和線長總代價優化的有效性。最終的實驗結果表明ML-XGRouter在兩類基準電路上均可取得相對當前總體佈線器而言最佳的溢出數和線長總代價。此外，時延目前也是VLSI芯片設計中一個非常重要的指標，未來的工作中我們將基於Elmore延遲模型進一步研究時延驅動的總體佈線算法。
文章信息：劉耿耿, 莊震, 郭文忠, 陳國龍. VLSI中高性能X結構多層總體佈線器. 自動化學報, 2020, 46(1): 79-93.
