《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 电子元件 > 设计应用 > 一种基于线性规划的全局逃逸布线算法
一种基于线性规划的全局逃逸布线算法
2023年电子技术应用第1期
陈虹1，陈传东1，2，魏榕山1
1.福州大学 物理与信息工程学院，福建 福州 350108；2.福建省光电信息科学与技术实验室，福建 福州 350108
摘要： 有序逃逸布线问题作为PCB设计中的关键一环，属于一类特殊的NP-困难问题，近年来得到广泛研究。传统方法中，基于整数线性规划或者是拆线重布类的启发式算法只适用于引脚数目较少的PCB引脚阵列，否则容易出现时间违规而导致布线失败。针对传统方法中大规模全局自动布线难的问题，基于线性规划的全局自动布线算法提出采用线性规划解决逃逸布线问题，并提出降低线网容量化解拥塞的新方法。与最新的逃逸布线算法相比，在处理大规模问题时，该算法不仅可以实现全部引脚的有序逃逸，并且布线时间提升50%，节省31%线长。
中圖分類號(hào)：TN47；TP391
文獻(xiàn)標(biāo)志碼：A
DOI: 10.16157/j.issn.0258-7998.222554
中文引用格式： 陳虹，陳傳東，魏榕山. 一種基于線性規(guī)劃的全局逃逸布線算法[J]. 電子技術(shù)應(yīng)用，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)有的電子設(shè)計(jì)自動(dòng)化（Electronic Design Automation，EDA）工具已無法滿足高密度引腳布線要求，一般與人工布線相結(jié)合，布線工作變得耗時(shí)且復(fù)雜[2]。因此，為了得到更高效的布線結(jié)果，EDA自動(dòng)布線算法成為近幾年的研究熱點(diǎn)。

    傳統(tǒng)意義上，PCB布線分為逃逸布線（Escape Routing）和區(qū)域布線（Area Routing）[3]。逃逸布線是指將引腳按要求逃逸到組件邊界，其作為PCB布線的關(guān)鍵一環(huán)，對(duì)電路性能好壞和后期的區(qū)域布線起著決定性作用。區(qū)域布線是指將不同組件中對(duì)應(yīng)功能的引腳實(shí)現(xiàn)互連，合法化的逃逸布線結(jié)果為區(qū)域布線階段節(jié)省布線空間，并大大提升PCB整體布通率。為實(shí)現(xiàn)更高的空間利用率，逃逸布線又可精細(xì)化分為有序逃逸布線（Ordered Escape Routing，OER）和無序逃逸布線[4]。




本文詳細(xì)內(nèi)容請(qǐng)下載：http://m.ihrv.cn/resource/share/2000005084。




作者信息：

陳虹1，陳傳東1，2，魏榕山1

（1.福州大學(xué) 物理與信息工程學(xué)院，福建 福州 350108；2.福建省光電信息科學(xué)與技術(shù)實(shí)驗(yàn)室，福建 福州 350108）




wd.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。

相關(guān)內(nèi)容