A Matching Based Escape Routing Algorithm with Variable Design Rules and Constraints
DescriptionWe present a high-performance escape routing algorithm to handle the problems with variable design rules and manual constraints, including variable line widths/spaces and the neck mode of wires. Modeling routing channels with grids, we construct bipartite graphs and propose a hierarchical sequencing algorithm based on the maximum matching formulation. Finally, we order the routing channels for each pin/diffusion using DFS and BFS alternatively to obtain a detailed routing solution according to the constraints. Experimental results show that our algorithm can achieve 100% routability without any design rule violation for all given industrial PCB instances.
Event Type
Research Manuscript
TimeTuesday, July 11th3:40pm - 3:55pm PDT
Location3008, 3rd Floor
Physical Design and Verification