An Effective Cost-Skew Tradeoff Heuristic for VLSI Global Routing

Andrew Kahng1, Shreyas Thumathy2, Mingyu Woo3
1UCSD CSE and ECE Departments, 2Canyon Crest Academy, 3UCSD ECE Department


In global routing of relatively large nets, particularly clock subnets, obtaining a good cost-skew tradeoff has remained beyond the reach of efficient heuristics. This is in contrast to obtaining a good cost-radius tradeoff, which has been well addressed by a series of methods. We propose a simple heuristic for optimizing the cost-skew tradeoff, based on a "multi-sourceā€ variation of the well-known Prim-Dijkstra (PD) construction. Our experiments demonstrate effectiveness of the multi-source PD heuristic compared to existing alternatives including H-tree, bounded-skew DME, and original Prim-Dijkstra constructions. We additionally develop characterization data for PD with respect to instance parameters to aid future research.