VLSI Digital Signal Processing Systems: Design and Implementation

5.4    CRITICAL PATH, UNFOLDING, AND RETIMING

This section relates the critical path of the original DFG, G, to that of the J-unfolded DFG, G_J. The relationship between the critical path of the J-unfolded version of a retimed DFG, (G_r)j, and the retimed version of the J-unfolded DFG, (G_J)_r, is also explored [8]− [10].

Property 5.4.1  Consider a path with w delays in the original DFG. J-unfolding of this path leads to (J − w) paths with no delays and w paths with 1 delay each, when w < J.

Corollary 5.4.1  Any path in the original DFG containing J or more delays leads to J paths with 1 or more delays in each path. Therefore, a path in the original DFG with J or more delays cannot create a critical path in the J-unfolded DFG.

Using Property 5.4.1, we can retime the original DFG such that the J-unfolded version of the retimed DFG will meet a specified critical path computation time, c. The critical path of the unfolded DFG can be c if there exists a path in the original DFG with computation time c and less than J delay elements. This leads to the critical path constraint for retiming for critical path reduction in the unfolded version of the retimed DFG. If D(U, V) ≥ c, then W_r(U, V) = W(U, V) + r(V) − r(U) ≥ J, or r(U) − r(V) ≤ W(U, V) − J. The usual feasibility constraint, w(e) + r(V) − r(U) ≤ 0, should be used with this critical path constraint.

Lemma 5.4.1    Any feasible clock cycle period that can be obtained by retiming the J-unfolded DFG, G_J , can be achieved by retiming the ...