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

author:

Lin, Disi (Lin, Disi.) [1] | Chen, Chuandong (Chen, Chuandong.) [2] | Wei, Rongshan (Wei, Rongshan.) [3] | Liu, Qinghai (Liu, Qinghai.) [4] | He, Huan (He, Huan.) [5] | Zhu, Ziran (Zhu, Ziran.) [6] | Lin, Zhifeng (Lin, Zhifeng.) [7] | Chen, Jianli (Chen, Jianli.) [8]

Indexed by:

EI

Abstract:

The Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical to PCB design. Primary methods based on integer linear programming (ILP) work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, traditional ILP strategies frequently cause time violations as the number of variables increases due to time-consuming preprocessing. In addition, heuristic algorithms have a time advantage when dealing with specific problems. In this paper, We propose an efficient two-stage escape routing method that employs LP for global routing and uses a heuristic algorithm to deal with the path intersection problem to minimize wiring length and runtime for large-scale PCBs. We first model the OER problem as a min-cost multi-commodity flow problem and use ILP to solve it. Then, we relax the non-crossing constraints and transform the ILP model into an LP model to reduce the runtime. we also construct a crossing graph according to the intersection of routing paths and propose a heuristic algorithm to locate congestion quickly. Finally, we reduce the local area capacity and allow global automatic congestion optimization. Compared with the state-of-the-art work, experimental results show that our method can reduce the routing time by 60% and handle larger-scale PCB escape routing problems. © 2024

Keyword:

Computational cost Global optimization Heuristic algorithms Integer linear programming Integer programming Linear programming Mixed-integer linear programming NP-hard Routing algorithms Traffic congestion

Community:

  • [ 1 ] [Lin, Disi]College of Computer and Data Science, Fuzhou University, Fuzhou; 350108, China
  • [ 2 ] [Chen, Chuandong]School of Microelectronics, Fuzhou University, Fuzhou; 350108, China
  • [ 3 ] [Wei, Rongshan]School of Microelectronics, Fuzhou University, Fuzhou; 350108, China
  • [ 4 ] [Liu, Qinghai]Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, the Center for Applied Mathematics of Fujian Province, and the Center for Discrete Mathematics, Fuzhou University, Fuzhou; 350108, China
  • [ 5 ] [He, Huan]Hangzhou Huawei Enterprises Telecommunication Technologies Co., Ltd, Hangzhou; 310000, China
  • [ 6 ] [Zhu, Ziran]National ASIC System Engineering Center, Southeast University, Nanjing; 210096, China
  • [ 7 ] [Lin, Zhifeng]Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou; 350108, China
  • [ 8 ] [Chen, Jianli]School of Microelectronics, Fudan University, Shanghai; 200433, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Integration

ISSN: 0167-9260

Year: 2025

Volume: 100

2 . 2 0 0

JCR@2023

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:225/9653214
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