Logic optimization with provable performance guarantees
Jürgen Werber ( Universität Bonn )
Thursday 22 November, 2007, 15.00 sharp (s.t), b-it 1.25 (cosec meeting room)
At late stages of VLSI (very-large-scale integration) design, chips often have timing problems which are due to long data paths. The global structure of the combinatorial logic is determined much earlier in the design process, when no exact information about placement, electrical properties and timing behaviour is available. As a consequence, techniques are needed for restructuring the critical parts of the logic later, with timing as primary optimization objective. In this talk, we generalize the classical notion of circuit depth to a new measure, called delay, which takes signal starting times into account and is closer to the standard method of modelling and analysing timing in modern chip design than depth. We present an algorithm for restructuring critical paths and prove that it always constructs a circuit of near-optimal delay. A practical implementation demonstrates that the procedure leads to considerable timing improvements on real-world industrial designs.