Retiming Synchronous Circuitry and Mixed-Integer Optimization.

摘要

In this paper we investigate properties of retiming, a circuit transformation which preserves the behavior of the circuit as a whole. We present an algorithm which transforms a given combinational circuit into a functionally equivalent pipelined circuit with minimum latency and clock-period no greater than a given upper bound c. The algorithm runs in O(E) steps, where E is the number of interconnections in the circuit, and is optimal within a constant factor. We give a novel and concise characterization of the minimum clock-period of a circuit in terms of the maximum delay-to-register ratio cycle in the circuit. We show that this ration does not exceed the minimum feasible clock-period by more than the maximum delay D of the elements in the circuit. This characterization leads to an O(E lg D) algorithm for minimum clock-period pipelining of combinational circuitry with latency no greater than a given upper bound. (kr)