BonnTools: Mathematical Innovation for Layout and Timing Closure of Systems on a Chip
Authors:
- Bernhard KorteBKBernhard Korte
- Dieter RautenbachDRDieter Rautenbach
- Jens VygenJVJens Vygen
- 30 April 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 95 (3) , 555-572
Abstract
The BonnTools provide innovative solutions for layout and timing closure that are used for many of the most complex integrated circuits. During 20 years of cooperation between the University of Bonn and IBM, new mathematical foundations and algorithms have been developed for the need of new technologies and leading-edge designs. In this paper we present the main ideas for placement, routing, timing optimization, and clock tree synthesis, which are the foundation of a continuing success storyKeywords
This publication has 35 references indexed in Scilit:
- Legalizing a Placement with Minimum Total MovementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004
- Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chipDiscrete Applied Mathematics, 2002
- Worst‐case ratios of networks in the rectilinear planeNetworks, 2001
- Global routing by new approximation algorithms for multicommodity flowIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001
- Fast and exact simultaneous gate and wire sizing by Lagrangian relaxationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999
- Multiterminal global routing: A deterministic approximation schemeAlgorithmica, 1991
- GORDIAN: VLSI placement by quadratic programming and slicing optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- The maximum concurrent flow problemJournal of the ACM, 1990
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978