A Matching Based Escape Routing Algorithm With Variable Design Rules and Multiple Constraints
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Start Page
1-1
ISSN
0278-0070
1937-4151
Date Issued
2025
Author(s)
Abstract
Escape routing is a critical problem in printed circuit board (PCB) routing, and its quality dramatically affects the cost of the PCB design. Unlike the traditional escape routing that works mainly for the ball grid array with unique line width and space, this article presents a high-performance escape routing algorithm to handle problems with variable design rules and multiple constraints. We first propose a novel obstacle-avoiding method to project pins to the boundary and construct a channel projection graph combined with a channel merging technique to handle complex irregular packages. We then construct a bi-projection graph and propose a matching-based hierarchical sequencing algorithm to consider manual constraints. We perform global routing for each pin/differential pair by congestion-avoiding path initializing and rip-up and reroute path optimizing. Finally, a length-aware detail routing algorithm is developed to optimize the line length while ensuring the differential pair constraints. The experimental results on industrial PCB instances show that our algorithm can achieve 100% routability without violating the design rules and constraints, while two state-of-the-art PCB routers, FreeRouting and Allegro, cannot complete escape routing.
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Type
journal article