UNDERSTANDING RETIMING THROUGH MAXIMUM AVERAGE-DELAY CYCLES

A synchronous circuit built of functional elements and registers is a simple implementation of the semisystolic model of computation that ca n be used to design parallel algorithms. Retiming is a well-known tech nique that transforms a given circuit into a faster circuit by relocat ing its registers. We give tight bounds on the minimum clock period th at can be achieved by retiming a synchronous circuit. These bounds are expressed in terms of the maximum delay-to-register ratio of the cycl es in the circuit graph and the maximum propagation delay d(max) of th e circuit components. Our bounds do not depend on the size of the circ uit, and they are of theoretical as well as practical interest. They c haracterize exactly the minimum clock period that can be achieved by r etiming a unit-delay circuit, and they lead to more efficient algorith ms for several important problems related to retiming. Specifically, w e give an O(V1/2E 1g V) algorithm for minimum clock-period retiming of unit-delay circuitry. For non-unit-delay circuitry, we describe an O( VE 1g d(max)) algorithm for minimum clock-period retiming. We also des cribe an O(V1/2E 1g2(Vd(max))) algorithm for retiming with clock perio d that does not exceed the minimum by more than d(max) - 1. Finally, w e give an O(E 1g d(max)) algorithm for minimum clock-period pipelining of combinational circuitry.