• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Chen, Chuandong (Chen, Chuandong.) [1] (Scholars:陈传东) | Lin, Dishi (Lin, Dishi.) [2] | Wei, Rongshan (Wei, Rongshan.) [3] (Scholars:魏榕山) | Liu, Qinghai (Liu, Qinghai.) [4] | Zhu, Ziran (Zhu, Ziran.) [5] | Chen, Jianli (Chen, Jianli.) [6]

Indexed by:

CPCI-S EI Scopus

Abstract:

Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical in PCB design. Primary methods based on integer linear programming (ILP) or heuristic algorithms work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, the performance of ILP strategies suffers dramatically as the number of variables increases due to time-consuming preprocessing. As for heuristic algorithms, ripping-up and rerouting is adopted to increase resource utilization, which frequently causes time violation. In this paper, we propose an efficient ILP-based routing engine for dense PCB to simultaneously minimize wiring length and runtime, considering the specific routing constraints. By weighting the length, we first model the OER problem as a special network flow problem. Then we separate the non-crossing constraint from typical ILP modeling to reduce the number of integral variables greatly. In addition, considering the congestion of routing resources, the ILP method is proposed to detect congestion. Finally, unlike the traditional schemes that deal with negotiated congestion, our approach works by reducing the local area capacity and then allowing the global automatic optimization of congestion. Compared with the state-of-the-art work, experimental results show that our algorithm can solve cases in larger scale in high routing quality of less length and reduce routing time by 76%.

Keyword:

Community:

  • [ 1 ] [Chen, Chuandong]Fuzhou Univ, Fuzhou, Peoples R China
  • [ 2 ] [Lin, Dishi]Fuzhou Univ, Fuzhou, Peoples R China
  • [ 3 ] [Wei, Rongshan]Fuzhou Univ, Fuzhou, Peoples R China
  • [ 4 ] [Liu, Qinghai]Fuzhou Univ, Fuzhou, Peoples R China
  • [ 5 ] [Zhu, Ziran]Southeast Univ, Nanjing, Peoples R China
  • [ 6 ] [Chen, Jianli]Fudan Univ, Shanghai, Peoples R China

Reprint 's Address:

Show more details

Version:

Related Keywords:

Related Article:

Online/Total:181/9648587
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1