Level-clocked circuits are often used in high-performance designs because they allow delays to be shared across latches, something that is no possible with edge-triggered registers. However, retiming becomes much more difficult because of the many interacting timing constraints that must be satisfied in latch-based circuits. This research defined a new and efficient algorithm for retiming level-clocked circuits.

Project Overview

Retiming is a process of rearranging the storage elements in a synchronous circuit -- without altering the combinational logic -- in order to optimize the circuit's performance. In effect, the technique reschedules circuit computations based on their duration and when clock signals are expected to arrive at synchronizers. Two synchronization methods commonly exist: edge-clocked, in which data values are passed through synchronizers once at a fixed point during each clock period; and level-clocked, in which values are passed continuously over a range of the period. Of these two, the increased flexibility in scheduling allowed by level-clocked designs can be used to implement faster, less expensive, and more robust circuits. Taking advantage of this flexibility is difficult, however, because of a corresponding increase in number and complexity of timing constraints. Through its ability to optimally schedule computations, retiming can be an important tool for gaining the greatest possible benefit from level-clocked timing.

This research defines timing constraints which are both necessary and sufficient to ensure a broad class of multi-phase, level-clocked circuits are correctly timed. The constraints are then used to extend the retiming techniques developed for edge-clocked circuits by [Leiserson et al.] to this class of level-clocked circuits. An efficient algorithm is presented which extracts a circuit's timing constraints for a particular clock period and identifies a retiming which satisfies them or reports that none exist. Additional techniques are provided to model expected clock skew, to retime in the presence of that skew, and to identify robust retimings which are least likely to fail due to variations from the expected skews.

All of the algorithms developed in this reserach have been implemented in a retiming tool, sskew. This tool and its usage are described along with experimental results providing a measure of the effectiveness of the algorithms and the advantages gained through the use of level-clocked timing. When pipelining a set of 75 MCNC combinational logic benchmark circuits, level-clocking is shown to reduce the clock period by an average of 10% over minimum possible with edge-triggered timing. When the same set of pipelined circuits are retimed at the minimum edge-triggered clock period (where edge-clocking provides zero skew tolerance) level-clocking provides an average skew tolerance equal to 15% of the clock period.

Researchers

Brian Lockyear and Prof. Carl Ebeling

Select References

Brian E. Lockyear and Carl Ebeling.
"Optimal Retiming of Multi-Phase, Level-Clocked Circuits", Advanced Research in VLSI and Parallel Systems: Proc. of the Brown/MIT Conference, 1992, pp. 265-280.

Brian E. Lockyear and Carl Ebeling.
"The Practical Application of Retiming to the Design of High-Performance Systems", IEEE/ACM International Conference on CAD, 1993.

Brian Lockyear and Carl Ebeling.
"Minimizing the Effect of Clock Skew Via Circuit Retiming", In Proceedings of TAU'93: 1993 ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems. September 1993.

Brian E. Lockyear.
"Algorithms for Retiming Level-Clocked Circuits and their use in Increasing Circuit Robustness", Ph.D. Thesis. University of Washington, Seattle, Washington, 1994.

Brian Lockyear and Carl Ebeling.
"Optimal Retiming of Level-Clocked Circuits Using Symmetric Clock Schedules", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 13, No. 9, pp. 1097-1109, September 1994.

Carl Ebeling and Brian Lockyear.
"On the Performance of Level-Clocked Circuits", Proceedings of the North Carolina Conference on Advanced Research in VLSI, Chapel Hill, pp. 342-356, March 1995.