Cycle time and slack optimization for VLSI-chips
Christoph Albrecht, Bernhard Körte, Jürgen Schietke, Jens Vygen · 1999
We consider the problem of finding an optimal clock schedule, i.e. optimal arrival times for clock signals at latches of a VLSI chip. We describe a general model which includes all previously considered models. Then we show how to optimize the cycle time and optimally balance slacks on data paths and on clocktree paths. The problem of finding a clock schedule with the optimum cycle time was solved before, either by linear programming or by binary search, using a test for negative circuits in a digraph as a subroutine. We show that the parametric shortest path algorithm of Young, Tarjan and Orlin solves this problem optimally. Incidentally, this yields a new efficient method for timing analysis with transparent latches. Then we extend this algorithm to the slack balancing problem: To make the chip less sensitive to routing detours, process variations and manufacturing skew it is desirable to have as few critical paths as possible. We show how to find the clock schedule wit...