RETIMING - Timing - page 236

Generating the linear program. Using the alternative description of the
maximal FF sharing in Section 10.5.1, the objective function coefficients are
obtained by inspection of the circuit, without explicitly adding the mirror ver-
tices. The circuit and the mirror constraints in are obtained from direct
inspection of the circuit graph using relation (10.23). Because the bounds on
the mirror vertices can also be obtained directly from the bounds on the gate
vertices, we do not need to explicitly add the mirror vertices to the circuit
graph. Since every multi-fanout gate has a mirror vertex, this gives us impor-
tant savings in terms of the space and time requirements. We now describe
how to obtain the period constraints in
We take advantage of the bounds obtained in Section 10.5.2 to modify the
method from [SR94] to run faster, generating only the reduced constraint set

As noted earlier, due to the monotonicity of edge weights, if we ensure at
least one FF on any sub-path, we are assured of having at least one FF on all
paths that contain this sub-path. Therefore, if the bounds on the variables
guarantee us at least one FF on any sub-path, we need not process any path
containing this sub-path. We use this observation in addition to relation (10.19)
to reduce the number of period constraints.
At the end of the ASTRA run for obtaining the lower bounds, all FF's are in
their ALAP locations. If the delay of all the gates is not the same, it is possible
that retimed circuit obtained by ASTRA with FF's in the ALAP locations may
have some purely combinational paths with delays that are greater than the
target clock period P. However, in practice, most of the other paths satisfy
the target clock period. We will use this observation to further speed up the
constraint generation process.
Consider a fixed gate in the circuit at the end of the ALAP run. If none of
the combinational paths starting at this gate violate the clock period, we have
if

Since we

have or Since gate is fixed
we obtain which is guaranteed to be true, and hence,
all constraints starting from fixed gate are redundant, and we do not need
to generate them. Thus, we must generate period constraints only from those
fixed gates which have at least one purely combinational path starting from it
with delay more than the clock period. Let us call this set
The method from [SR94] presented in Section 10.11 is modified to take ad-
vantage of the bounds on the variables to generate the reduced constraint set
efficiently. The pseudocode is presented below with the modifications shown
in boldface.