Civil Engineering Reference
In-Depth Information
where
This problem is then solved using Lagrangian relaxation. In each step‚ this
iteratively sizes the gates in the circuit for the value of from the previous
iteration‚ exploiting the properties of the Elmore delay function to speed up the
procedure. The initial values of the are chosen to be uniform‚ and these
values are adapted from step to step based on a subgradient optimization.
8.5.3 Sizing based on accurate nonconvex delay functions
The use of Elmore delay metrics has the disadavantage of low accuracy‚ while
providing substantial advantages in terms of the convexity of the delay function.
An alternative approach might use high accuracy delay evaluators that can
guarantee that the solution can indeed achieve the performance promised by
the optimizer. The drawback of such an approach‚ however‚ is the loss of the
convexity properties of the Elmore metric. As a result‚ the result may fall in a
local minimum rather than being guaranteed of a globally optimal solution.
The approach in VC99] uses a fast and accurate simulator based
on SPECS [VR91‚ VW93]‚ which guarantees correctness of the delay compu-
tation. However‚ the simulator cannot guarantee the convexity of the delay
metric‚ and therefore any such optimization comes at the cost of a potential
loss in global optimality. To overcome this‚ the method uses a theoretically
rigorous and computationally efficient optimization engine that is empirically
seen to be likely to yield a good solution to the optimization problem.
The problem statement is similar to that in Equation (8.3)‚ except that
SPECS is used for delay computation to ensure better accuracy than an Elmore-
based method. The use of SPECS removes the restriction that the optimization
formulation must maintain convexity‚ and frees up the optimizer to incorporate
several other constraints such as
Upper and lower bounds on the signal transition times at each gate output
Timing constraints related to dynamic logic
Noise constraints may be incorporated: for example‚ sizing a gate very asym-
metrically results in poor noise margins‚ and this may be stated as a con-
straint.
The LANCELOT optimization engine [CGT92] is used to perform the opti-
mization‚ and an industrial strength implementation of the method is widely
used in IBM. The engine requires evaluations of the objective and constraint
functions and their gradients. The objective function‚ as in other methods‚ is
