A Matching-Based Escape Routing Algorithm With Variable Design Rules and Multiple Constraints

doi:10.1109/TCAD.2025.3569773

A Matching-Based Escape Routing Algorithm With Variable Design Rules and Multiple Constraints

2025-05-13

0

PRE

AI

DOI：10.1109/TCAD.2025.3569773

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Differential pairs

escape routing

manual constraints

maximum matching

printed circuit board

A Matching-Based Escape Routing Algorithm With Variable Design Rules and Multiple Constraints

Abstract

Journal

Organization