MINIMAL BUFFER INSERTION IN CLOCK TREES WITH SKEW AND SLEW RATE CONSTRAINTS

In this paper, we investigate the problem of computing a lower bound o n the number of buffers required when given a maximum clock slew rate (or rise time) constraint and a predefined clock tree, Using generaliz ed properties of published CMOS timing models, we formulate a novel no nlinear buffer insertion problem, Next, we derive an algorithm that bo unds the capacitance for each buffer stage without sacrificing the gen erality of the timing models, With this capacitance bound we formulate a second linear buffer insertion problem, which we solve optimally in O(n) time, The basic formulation and algorithm are extended to includ e a skew upper bound constraint, Using these algorithms we propose fur ther algorithmic extensions that allow area and phase delay tradeoffs, Our results are verified using SPICE3e2 simulations with MCNC MOSIS 2 .0 mu models and parameters, Experiments with these test cases show th at the buffer insertion algorithms proposed herein can be used effecti vely for designs with high clock speeds and small skews.