Civil Engineering Reference
In-Depth Information
Algorithm CP
This algorithm computes the clock period
for a synchronous
circuit
{
1. Let be the subgraph of G that contains precisely those
edges such that the register count
2. Perform a topological sort on totally ordering
its vertices so that if there is an edge from vertex
to vertex in then precedes in the total order.
3. Go through the vertices in the order defined by the
topological sort.
On visiting each vertex
compute
as follows:
a. If there is no incoming edge to
b. Otherwise,
and
4. The clock period
is
}
The advantage of this method is that it does not require the explicit calcula-
tion of the
W
and
D
matrices, thereby reducing the memory overhead. Step 2
of
FEAS
can be shown to be equivalent to applying the Bellman-Ford algorithm
on the graph
G.
The application of either of these retiming procedures may be used to as-
sign the labels to each vertex in the graph corresponding to the correlator
circuit shown in Figure 10.4(a). For the unretimed circuit, the clock period
is 24 units, which corresponds to the sum of the propagation delays along the
longest register-free path, The graph obtained on ap-
plying minimum period retiming to Figure 10.4(b) is shown in Figure 10.5.
The labels describe the manner in which flip-flops are added or removed
from the original graph. For instance, the edge has one more regis-
ter since (see relation (10.1)). Since retiming preserves the
input-output latency of the circuit, the original and the retimed circuits corre-
