VLSI Digital Signal Processing Systems: Design and Implementation

4.4    RETIMING TECHNIQUES

This section considers some techniques used for retiming. First, two special cases of retiming, namely, cutset retiming and pipelining, are considered. Two algorithms are then considered for retiming to minimize the clock period and retiming to minimize the number of registers that are required to implement the circuit.

4.4.1    Cutset Retiming and Pipelining

Cutset retiming is a useful technique that is a special case of retiming. A cutset is a set of edges that can be removed from the graph to create 2 disconnected subgraphs. Cutset retiming only affects the weights of the edges in the cutset. If the 2 disconnected subgraphs are labeled G₁ and G₂, then cutset retiming consists of adding k delays to each edge from G₁ to G₂ and removing k delays from each edge from G₂ to G₁. For example, a cutset is shown with a dashed line in Fig. 4.4(a). The 3 edges in the cutset are 2 → 1, 3 → 2, and 1 → 4. The 2 subgraphs G₁ and G₂ found by removing the 3 edges in the cutset are shown in Fig. 4.4(b). For k = 1, the result of cutset retiming is shown in Fig. 4.4(c). The edges from G₁ to G₂ are 3 → 2 and 1→ 4, and one delay is added to each of these edges. The edge from G₂ to G₁ is 2 → 1, and one delay is subtracted from this edge.

Fig. 4.4    (a) The unretimed DFG with a cutset shown as a dashed line. (b) The 2 graphs G₁ and G₂ formed by removing the edges in the cutset. ...