中圖分類號：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
