Civil Engineering Reference
In-Depth Information
where
is a path from to a fanin of
Thus, if the period constraint
is added, the fanouts of
need not be relaxed. The pseudocode for constraint
generation is as follows:
Algorithm CONSTRAINT_GENERATION
{
P = target clock period;
= the
heap;
{
s = current vertex;
and
= current register weight;
do
{
if
add a period edge
with weight
else {
{
if
heap-insert
}
}
} while
}
}
The work in published a few months before [SR94], used the same
idea and referred to it as “clock-period limited labeling.” It was demonstrated
that the use of this method caused a significant speedup in constraint gen-
eration. A second method presented in the work was termed “relevant path
labeling.” Starting from a source node this technique labels each vertex
with the maximum value of the label The
rationale behind this approach is that for every path originating at it must
be true that and therefore, the largest value of
must be nonpositive. However, unlike the method of clock-period limited la-
beling, this must traverse all vertices, and while it generates a smaller number
of constraints, the amount of time required to generate these constraints was
reported to be extremely large.
10.5.2 The Minaret algorithm
Although the techniques of the previous section make minimum area retiming
efficient, they cannot handle large circuits with tens of thousands of gates. In
[MS97a, MS98b], an amalgamation of the Leiserson-Saxe approach and the
