A Matching Based Escape Routing Algorithm with Variable Design Rules and Constraints

Abstract

Escape routing is a critical problem in PCB routing, and its quality greatly affects the PCB design cost. Unlike the traditional escape routing that works mainly for the BGA package with unique line width and space, this paper presents a high-performance escape routing algorithm to handle problems with variable design rules and manual constraints, including variable line widths/spaces, the neck mode of wires, and the pad entry for differential pairs. We first propose a novel obstacle-avoiding method to project pins to the boundary and construct a channel projection graph. 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 initialization and rip-up and reroute path optimization. Finally, we complete detailed routing in every face, ensuring the wire angle and pad entry constraints. Experimental results show that our algorithm can achieve 100% routability without any design rule violation for all given industrial PCB instances, while two state-of-the-art routers cannot complete routing.