Disjoint-Path and Golden-Pin Based Irregular PCB Routing with Complex Constraints
Authors:
- 9 July 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
PCB routing becomes time-consuming as the complexity of PCB design increases. Unlike traditional schemes that treat the two essential PCB routing processes separately, namely, escape and bus routing, we consider the continuity between them and present a golden-pin-based routing scheme to find the desired solution with angle and topology constraints. Further, conventional rip-up and reroute methods are often ineffective and inefficient for congestion alleviation and routability optimization. We construct a component graph by modeling components as vertices and applying the minimum weight vertex covering method to improve the routability. A self-adaptable ordering method is presented for escape routing to arrange the pin order on the component boundary, guaranteeing successful bus routing. In addition, escape routing is performed based on a disjoint path method. We construct a dynamic Hanan grid in bus routing and utilize a novel congestion adjustment technique to improve solution quality. Compared with FreeRouting and Allegro, the experiment results show that our algorithm achieves high routability and a significant 90% runtime reduction.Keywords
Funding Information
- AnaGlobe
- Delta
This publication has 13 references indexed in Scilit:
- A Complete PCB Routing Methodology with Concurrent Hierarchical Routing2021
- A DAG-Based Algorithm for Obstacle-Aware Topology-Matching On-Track Bus RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020
- Ordered Escape Routing with Consideration of Differential Pair and BlockageACM Transactions on Design Automation of Electronic Systems, 2018
- Ordered escape routing using network flow and optimization model2015
- Simultaneous escape routing on multiple components for dense PCBs2013
- A New Strategy for Simultaneous Escape Based on Boundary RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011
- On using SAT to ordered escape problems2009
- Ordered escape routing based on Boolean satisfiability2008
- A Length-Matching Routing Algorithm for High-Performance Printed Circuit BoardsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981