Civil Engineering Reference
In-Depth Information
where and is the set of all the mirror vertices,
and additional constraints due to the mirror vertices are called the mirror con-
straints. For simplicity, we can rewrite the above LP as follows
where is the constraint set of the LP in (10.16), and includes
the period constraint set
the circuit constraint set
and the mirror
constraint set
A constraint
in the constraint set
C
is of the form
where
The objective function of the LP in (10.17) now denotes the increase in
the number of FF's assuming maximal sharing of FF's at the output of all
gates. The weights on all paths from gate to its mirror vertex are the
same before retiming, i.e., and
therefore, the weights on all paths from gate to its mirror vertex must
be equal after retiming. Since the mirror vertex is a sink in the graph, the
register count on one of the edges from the fanout nodes to will be zero,
i.e., Thus, the weight on all paths from gate to mirror
vertex after retiming will be since all
of the retimed edge weights As there are paths,
each with width the total cost of all paths will be as desired.
Like the LP in (10.15), the LP in (10.17) is also the dual of a minimum cost
network flow problem.
An alternative view of this model is as follows. The change in cost function
due to adding or removing latencies from the fanout junction of gate is
modeled by two retiming variables: one for the gate, and other for the
mirror vertex, Any change in the cost function due to FF's moving
across the multi-fanout gate itself are modeled by
while any change due
