Title :
Algorithms and data structures for fast and good VLSI routing
Author :
Gester, Michael ; Müller, Dirk ; Nieberg, Tim ; Panten, Christian ; Schulte, Christian ; Vygen, Jens
Author_Institution :
Res. Inst. for Discrete Math., Univ. of Bonn, Bonn, Germany
Abstract :
We present advanced data structures and algorithms for fast and high-quality global and detailed routing in modern technologies. Global routing is based on a combinatorial approximation scheme for min-max resource sharing. Detailed routing uses exact shortest path algorithms, based on a shape-based data structure for pin access and a two-level track-based data structure for long-distance connections. All algorithms are very fast. We demonstrate their superiority over traditional approaches by a comparison to an industrial router (on 32 nm and 22 nm chips). Our router is over two times faster, has 5% less netlength, 20% less vias, and reduces detours by more than 90%.
Keywords :
VLSI; approximation theory; data structures; network routing; resource allocation; VLSI routing; algorithms structures; combinatorial approximation scheme; industrial router; long-distance connections; min-max resource sharing; pin access; shape-based data structure; two- level track-based data structure; Approximation algorithms; Data structures; Pins; Routing; Shape; Wires; Wiring; Detailed Routing; Global Routing; Routing Optimization; VLSI Design;
Conference_Titel :
Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
978-1-4503-1199-1