TIMING ANALYSIS FOR SEQUENTIAL CIRCUITS - Timing - page 143

An alternative approach to this method utilizes the concept of back-edges
[LTW94]. For a directed acyclic graph processed in topological order, the
Bellman-Ford procedure (or the algorithm TIMING_VERIFY above) concludes
in one iteration. It can be shown that if the graph has back edges, it-
erations are necessary. While the problem of identifying a minimal number
of back-edges (i.e., the minimum feedback vertex set problem) is NP-hard, in
real circuits, it is found that the number of back edges is small enough that
almost any set is good enough to provide a good improvement over a naive
implementation of the relaxation procedure above.

7.4 CLOCK SCHEDULE OPTIMIZATION FOR LEVEL-CLOCKED
CIRCUITS
The clock schedule optimization problem is the problem of finding the minimum
clock period, and the corresponding locations of the rising and falling edges of
each phase so that the clocking scheme meets all timing constraints. Due to the
freedom allowed in the arrival times for level-clocked circuits, this optimization
can make a substantial difference to the behavior of the circuit.
The minTc algorithm [SMO90] formulates the clock schedule optimization
problem as a linear program. The problem is stated as follows:

After relaxing all max operators in relations (7.17) through (7.19) by replacing
them by inequalities, the problem maps on to a linear program whose
minimum objective function value can be proven to be the same as that of the
original problem.
The work in [Szy92] developed techniques to reduce the number of long path
constraints in the linear program. A principal idea was the concept of relevant
paths. Before defining this concept, we observe that if denotes the number
of latches on a path and is the delay along the path (with
allowances for setup times), then it must be true that

A path, is said to be relevant for period P if for any other path, with

the same endpoints as if
and if It was shown that in order to check the
feasibility of a clock schedule, it suffices to check if the constraints on the set
of relevant paths are satisfied; the intuition behind this is that satisfying the
relevant constraint will ensure that other constraints that were not relevant will
be forced to satisfy Relation (7.24).
The work in [Szy92] uses this pruning to reduce the constraint set before
feeding the resulting optimization problem to an LP solver. Subsequently,