Algorithms and data structures for fast and good VLSI routing

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Gester, Michael, Müller, Dirk, Nieberg, Tim, Panten, Christian, Schulte, Christian, Vygen, Jens
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Data structures
Detailed Routing
Global Routing
Hardware > Electronic design automation > Physical design (EDA) > Placement
Hardware > Electronic design automation > Physical design (EDA) > Wire routing
Hardware > Very large scale integration design
Pins
Routing
Routing Optimization
Shape
VLSI Design
Wires
Wiring
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 32nm and 22nm chips). Our router is over two times faster, has 5% less netlength, 20% less vias, and reduces detours by more than 90%.
ISSN:0738-100X
DOI:10.1145/2228360.2228441