RETIMING EDGE-TRIGGERED CIRCUITS UNDER GENERAL DELAY MODELS

The retiming transformation can be used to optimize synchronous circui ts for maximum speed of operation by relocating their storage elements . For relatively simple delay models, an optimal retiming of a given c ircuit can be computed in polynomial time. Under more comprehensive de lay models, however, the retiming problem is solved by resorting to br anch-and-bound techniques. In this paper, we investigate retiming unde r delay models that encompass load-dependent gate delays, register del ays, interconnect delays, and clock skew. For the most general of our delay models, we express the retiming problem as a set of integer line ar programming (ILP) constraints that can be solved using ILP techniqu es. For less general delay models, which encompass circuits with monot onic clock skews and load-dependent gate delays, we give an integer mo notonic programming formulation for the retiming problem and an asympt otically efficient retiming algorithm. Our algorithm re-times any give n edge-triggered circuit to achieve a specified clock period in O((VF) -F-3) steps, where V is the number of combinational logic gates in the circuit and F is a constant no greater than the circuit's register co unt. We have implemented our algorithms in DELAY, a software tool for optimizing synchronous circuits, and have evaluated their performance on benchmark circuits.