HydraRoute

Routing for dense circuits is a major challenge for VLSI physical design. Most routing approaches rely at least partially on a "rip-up and reroute" scheme, where solution quality and run times can be impacted profoundly by the order in which nets are routed. Other routing tools rely on backtracking methods embedded in integer linear programming solvers. In this paper, we present a novel approach which avoids backtracking, and largely eliminates the routing order considerations, by constructing a large number of routings simultaneously. By keeping "options open," our approach sidesteps conflicts. Our approach is a factor of ten faster than other recent work, reduces via counts by 30% or more, and is competitive on both wire length and completion rates. The approach is simple, scalable, and adaptable to the complex constraints of modern circuit fabrication processes.