BonnRoute: Algorithms and data structures for fast and good VLSI routing

We present the core elements of BonnRoute: advanced data structures and algorithms for fast and high-quality 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...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on design automation of electronic systems 2013-03, Vol.18 (2), p.1-24
Main Authors: Gester, Michael, Müller, Dirk, Nieberg, Tim, Panten, Christian, Schulte, Christian, Vygen, Jens
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present the core elements of BonnRoute: advanced data structures and algorithms for fast and high-quality 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. Compared to an industrial router (on 32 nm and 22 nm chips), BonnRoute is over two times faster, has 5 % less netlength, 20 % less vias, and reduces detours by more than 90 %.
ISSN:1084-4309
1557-7309
DOI:10.1145/2442087.2442103