The retiming transformation can be used to optimize synchronous circuits for maximum speed of operation by relocating their storage elements. For relatively simple delay models, an optimal retiming of a given circuit can be computed in polynomial time. Under more comprehensive delay models, however, the retiming problem is solved by resorting to branch-and-bound techniques. In this paper, we investigate retiming under delay models that encompass load-dependent gate delays, register delays, interconnect delays, and clock skew. For the most general of our delay models, we express the retiming problem as a set of integer linear programming (ILP) constraints that can be solved using ILP techniques. For less general delay models, which encompass circuits with monotonic clock skews and load-dependent gate delays, we give an integer monotonic programming formulation for the retiming problem and an asymptotically efficient retiming algorithm. Our algorithm re-times any given edge-triggered circuit to achieve a specified clock period in O(V/sup 3/ F) 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 count. We have implemented our algorithms in DELAY, a software tool for optimizing synchronous circuits, and have evaluated their performance on benchmark circuits.
展开▼
