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

author:

Lin, D. (Lin, D..) [1] | Chen, C. (Chen, C..) [2] | Wei, R. (Wei, R..) [3] | Liu, Q. (Liu, Q..) [4] | He, H. (He, H..) [5] | Zhu, Z. (Zhu, Z..) [6] | Lin, Z. (Lin, Z..) [7] | Chen, J. (Chen, J..) [8]

Indexed by:

Scopus

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:

Heuristic algorithm Linear programming Min-cost multi-commodity flow Ordered escape routing

Community:

  • [ 1 ] [Lin D.]College of Computer and Data Science, Fuzhou University, Fuzhou, 350108, China
  • [ 2 ] [Chen C.]School of Microelectronics, Fuzhou University, Fuzhou, 350108, China
  • [ 3 ] [Wei R.]School of Microelectronics, Fuzhou University, Fuzhou, 350108, China
  • [ 4 ] [Liu Q.]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 H.]Hangzhou Huawei Enterprises Telecommunication Technologies Co., Ltd, Hangzhou, 310000, China
  • [ 6 ] [Zhu Z.]National ASIC System Engineering Center, Southeast University, Nanjing, 210096, China
  • [ 7 ] [Lin Z.]Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou, 350108, China
  • [ 8 ] [Chen J.]School of Microelectronics, Fudan University, Shanghai, 200433, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

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: 2

Affiliated Colleges:

Online/Total:101/9652520
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