Civil Engineering Reference
In-Depth Information
the left-hand side of the inequality is the sum of
which is convex in the
new
variables‚ and
which is linear (hence convex)
4
‚ in the variables
and
All of the above statements are valid for general sequential circuits‚ and not
just acyclic pipelines. Therefore‚ it can be concluded that for general sequential
circuits‚ the problem of adjusting both clock skews and transistor sizes to meet
long path constraints‚ while minimizing total gate area‚ corresponds to a convex
optimization program.
Based on these observations‚ the following approach was proposed to solve
this problem in two steps:
Neglect the short path constraints (which may be nonconvex [Fis90]) and
solve the combined sizing and skew optimization under long path constraints
only. This is equivalent to a convex optimization problem and is therefore
a unimodal problem‚ i.e.‚ any local minimum is also a global minimum‚ and
is solved using an adaptation of the TILOS algorithm [FD85].
1.
Resolve any short path constraints that are violated at the end of Step 1 by
changing the topology of the circuit and adding buffers in an optimal manner
using variation of techniques such as [SBS93]‚ described in Section 8.9.
2.
9.4.3 A procedure that incorporates the cost of the clock tree
Both the linear programming and convex programming technique described
here control the cost of the clocking network only by placing bounds on the
clock skews. An alternative procedure in [XD97] optimizes the cost of the
clock tree directly‚ but uses more approximate models for gate sizing. The
optimization problem is set up as
where
C(T‚ X)
is a cost function that is dependent on the routing topology
T
of
the clock tree and on the vector of gate sizes
x
. The functions
L(T)
and
represent the total wire length of the clock tree‚ and the power dissipation
of the sized gates‚ respectively‚ and are appropriately chosen weighting
parameters. The cost function is optimized using simulated annealing [KGV83].
The algorithm first derives bounds on the relative skew at various sinks. If
a pair of latches and is connected by combinational logic‚ then it is possible
to derive upper and lower bounds on the value of the difference in skew
using expression (9.9); these are referred to as the positive skew bound‚
and the negative skew bound‚ For nonadjacent sinks‚ no such bound
exists. Note that since the expression (9.9) is dependent on the delays‚ the
bounds are derived over all circuit delays that correspond to allowable gate
1
sizes.
The clock tree construction method is based on the DME procedure [KR95]‚
outlined in Section 9.6. Briefly‚ this is related to the fact that unlike the case
