Retiming

Leiserson and Saxe

- moving registers to minimize area, time (clock period), or both (given one is constrained)
- it is done under several (untrivial) assumptions

- D matrix - path delay matrix
- W matrix - path matrix for min #register for any pair of vertices.

Floyd-Warshall

Bellman-Ford
- n - 1 iterations
- an extra iteration to check negative weigh cycle
- d(v) < d(u) + w(u,v) <== relaxation

clock skew vs. retiming

Peripherial retiming
- use retiming to augment the circuit
- and perform optimization on the combinational parts

The initial value problem
- decreasing the number of registers, then there are less initial values
- if initial values determine the behavior for the circuit, then retiming may not preserve the original circuit