Understanding retiming through maximum average-weight cycles

Publisher Website
Google Scholar
Abstract
A synchronous circuit built of functional elements and registers is a simple implementation of the semisystolic model of computation that can be used to design parallel algorithms. Retiming is a wellknown technique that can transform a given circuit into a faster circuit by relocating its registers. We give novel and tight bounds on the minimum clock period that can be achieved by retiming a synchronous circuit. These bounds are expressed in terms of the maximum delay-to-register ratio of the cycles in the circuit graph, and the maximum propagation delay D of the circuit components. Our bounds are of theoretical as well as practical interest. They are the first bounds presented that do not depend on the size of the circuit, and they characterize exactly the minimum clock period that can be achieved by retiming a unit-delay circuit. They also lead to more efficient algorithms for several important problems related to retiming. In particular, we give an 0( V112Elg(VW)) algorithm for minimum clock period retiming of unitdelay circuitry, where W is the maximum number of registers on any wire in the circuit. We also give

This publication has 0 references indexed in Scilit: