Civil Engineering Reference
In-Depth Information
9.3.3
Efficient solution of the skew optimization problem
The constraints of the linear program (9.7) are rewritten as
Note that the skews at the primary inputs and the primary outputs may be
set to zero under the assumption that they cannot be controlled or adjusted.
For a constant value of
P‚
the constraint matrix for this problem reduces to a
system of difference constraints [CLR90]. For such a system‚ it is possible to
construct a constraint graph. The vertices of the constraint graph correspond
to the variables‚ and each constraint corresponds to a directed
edge from node to node with a weight of If
P
is achievable‚ then a set
of skews that satisfies
P
can be found by solving the longest path problem on
this directed graph. The clock period
P
is feasible provided the corresponding
constraint graph contains no positive cycles.
This observation was utilized in [DS94] for efficient solution of the skew
optimization problem. The optimal clock period is obtained by performing
a binary search. At each step in the binary search (for clock period
P
) the
Bellman-Ford algorithm‚ to be described shortly‚ is applied to the corresponding
constraint graph to check for positive cycles. The procedure continues until the
smallest feasible clock period is found. The following skeletal pseudo-code is
used to perform the binary search for the optimal clock period.
Algorithm MINPERIOD
_
WITH
_
OPTIMAL
_
SKEWS
Construct the constraint graph;
...(Lemma 3.3)
...(Lemma 3.4)
while
{
if constraint graph has a positive cycle
else
}
The binary search can be provably justified since it can be shown that any
clock period that is larger than the optimal period is feasible‚ and that any
clock peiod that is smaller is infeasible [DS94‚ SD96].
The bounds on the the clock period‚ and may be computed as
follows. Given a pair of inequalities in Equation (9.9)‚ if we define
Such a quantity can be defined for any pair of flip-flops‚ and
that are
connected by a combinational path. Then a lower bound‚
is given by
