Indexed by:
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:
Reprint 's Address:
Email:
Source :
Integration
ISSN: 0167-9260
Year: 2025
Volume: 100
2 . 2 0 0
JCR@2023
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: