一種基于線性規(guī)劃的全局逃逸布線算法
2023年電子技術應用第1期
陳虹1，陳傳東1，2，魏榕山1
1.福州大學 物理與信息工程學院，福建 福州 350108；2.福建省光電信息科學與技術實驗室，福建 福州 350108
摘要： 有序逃逸布線問題作為PCB設計中的關鍵一環(huán)，屬于一類特殊的NP-困難問題，近年來得到廣泛研究。傳統(tǒng)方法中，基于整數(shù)線性規(guī)劃或者是拆線重布類的啟發(fā)式算法只適用于引腳數(shù)目較少的PCB引腳陣列，否則容易出現(xiàn)時間違規(guī)而導致布線失敗。針對傳統(tǒng)方法中大規(guī)模全局自動布線難的問題，基于線性規(guī)劃的全局自動布線算法提出采用線性規(guī)劃解決逃逸布線問題，并提出降低線網容量化解擁塞的新方法。與最新的逃逸布線算法相比，在處理大規(guī)模問題時，該算法不僅可以實現(xiàn)全部引腳的有序逃逸，并且布線時間提升50%，節(jié)省31%線長。
中圖分類號：TN47；TP391
文獻標志碼：A
DOI: 10.16157/j.issn.0258-7998.222554
中文引用格式： 陳虹，陳傳東，魏榕山. 一種基于線性規(guī)劃的全局逃逸布線算法[J]. 電子技術應用，2023，49(1)：97-101.
英文引用格式： Chen Hong，Chen Chuandong，Wei Rongshan. Algorithm of global escape routing problem based on linear programming[J]. Application of Electronic Technique，2023，49(1)：97-101.
文獻標志碼：A
DOI: 10.16157/j.issn.0258-7998.222554
中文引用格式： 陳虹，陳傳東，魏榕山. 一種基于線性規(guī)劃的全局逃逸布線算法[J]. 電子技術應用，2023，49(1)：97-101.
英文引用格式： Chen Hong，Chen Chuandong，Wei Rongshan. Algorithm of global escape routing problem based on linear programming[J]. Application of Electronic Technique，2023，49(1)：97-101.
Algorithm of global escape routing problem based on linear programming
Chen Hong1，Chen Chuandong1，2，Wei Rongshan1
1.School of College and Information Engineering， Fuzhou University， Fuzhou 350108， China； 2.Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China， Fuzhou 350108， China
Abstract： As a key part of PCB design, the ordered escape routing problem is a special NP-hard problem, which has been studied extensively in recent years. In the traditional method, both ILP method and the heuristic algorithms based on ripping-up and rerouting are only applicable to small-scaled pin arrays with fewer pins, which easily lead to time violation. Aiming at the difficulty of large-scale global routing in traditional methods, the iteration-driven method is proposed to solve the global escaping routing problem by linear programming (LP), and to optimize area congestion by reducing capacity. Compared with the latest work, this algorithm can not only escape all pins but also achieve up to 50% times speed up and save 31% wire length.
Key words : PCB design；ordered escape routing；LP；congestion-driven
0 引言
印制電路板（Printed Circuit Board，PCB）是集成電路（Integrated Circuit，IC）的載體[1]。隨著大規(guī)模集成電路和超大規(guī)模集成電路的發(fā)展，PCB的集成度要求越來越高，現(xiàn)有的電子設計自動化（Electronic Design Automation，EDA）工具已無法滿足高密度引腳布線要求，一般與人工布線相結合，布線工作變得耗時且復雜[2]。因此，為了得到更高效的布線結果，EDA自動布線算法成為近幾年的研究熱點。
傳統(tǒng)意義上，PCB布線分為逃逸布線（Escape Routing）和區(qū)域布線（Area Routing）[3]。逃逸布線是指將引腳按要求逃逸到組件邊界，其作為PCB布線的關鍵一環(huán)，對電路性能好壞和后期的區(qū)域布線起著決定性作用。區(qū)域布線是指將不同組件中對應功能的引腳實現(xiàn)互連，合法化的逃逸布線結果為區(qū)域布線階段節(jié)省布線空間，并大大提升PCB整體布通率。為實現(xiàn)更高的空間利用率，逃逸布線又可精細化分為有序逃逸布線（Ordered Escape Routing，OER）和無序逃逸布線[4]。
本文詳細內容請下載：http://m.jysgc.com/resource/share/2000005084。
作者信息：
陳虹1，陳傳東1，2，魏榕山1
（1.福州大學 物理與信息工程學院，福建 福州 350108；2.福建省光電信息科學與技術實驗室，福建 福州 350108）
此內容為AET網站原創(chuàng)，未經授權禁止轉載。