Retiming with non-zero clock skew, variable register, and interconnect delay

ABSTRACT

A retiming algorithm is presented which includes the effects of variable register, clock distribution, and interconnect delay. These delay components are incorporated into retiming by assigning Register Electrical Characteristics (RECs) to each edge in the graph representation of the synchronous circuit. A matrix (called the Sequential Adjacency Matrix or SAM) is presented that contains all path delays. Timing constraints for each data path are derived from this matrix. Vertex lags are assigned ranges rather than single values as in standard retiming algorithms. The approach used in the proposed algorithm is to initialize these ranges with unbounded values and continuously tighten these ranges using localized timing constraints until an optimal solution is obtained. The algorithm is demonstrated on modified MCNC benchmark circuits and both increased clock frequencies and elimination of all race conditions are observed.

REFERENCES

• 1: C.E. Leiserson and J. B. Saxe, "Retiming Synchronous Circuitry," Algorfthmica, Vol. 6, pp. 5-35, January 1991.
• 2: A.T. Ishii, C. E. Leiserson, and M. C. Papeefthymion, "Optimizing Two-Phase, Level-Clocked Circuitry," Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, pp. 245-264, March 1992.
• 3: G. De Micheli, "Synchronous Logic Synthesis: Algorithms for Cycle-Time Minimization," IEEE Transactions on Computer-Aided Design, Vol. CAD-10, No. 1, pp. 63--73, January 1991.
• 4: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 5: E.G. Friedman, "The Application of Localized Clock Distribution Design to Improving the Performance of Retimed Sequential Circuits," Proceedings of the IEEE Asia.Pacific Conference on Circuits and Syzt~u, pp. 12-17, December 1992.
• 6: T. Soynte, E. G. Friedman, and J.' H. Mulligan, Jr., "Integration of Clock Skew and Register Delays into a Retiming Algorithm,,' Proceedings of the IEEE International Syml~sium on Circuits and Systems, pp. 1483-1486, May 1993.
• 7: Brian Lockyear , Carl Ebeling, The practical application of retiming to the design of high-performance systems, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.288-295, November 07-11, 1993, Santa Clara, California, United States
• 8: T. Soyata and E. G. Friedman, "Synchronous Pefformmu~ and Reliability Improvement in Pipelined ASICs," Proceedings of the ASIC Conference, September 1994.
• 9: S. Simon, E. Bernard, M. Sauer, and J. A. Nossek, "A New Retiming Algorithm for Circuit Design," Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 4.35-4.38, May/June 1994.
• 10: L. Chao and E. H. Slut, "Retiming and Clock Skew for Synchfoaons Systems," Proceedings of the IEEE Interna~onal Symposium on Circuits and Systems, pp. 1.283-I.286, May/June 1994.
• 11: E.G. Friedman and J. H. Mulligan, "Clock Frequency and Latency in Synchronous Digital Systems," IEEE Transactions on Signal Processing, VoL 39, No. 4, pp. 930-934, April 1991.
• 12: E.G. Friedman, "Clock Distribution Design in VLSI Circtdts -- an Overview," Proceedings of the IEEE International Symposiwn on Circuits and Systems, pp. 1475-1478, May 1993.
• 13: K.A. Sakallah, T. N. Medge, T. M. Bmks, and E. S. Davidsm, "Synchronization of Pipelines," IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, VoL CAD--12, No. 8, pp. I 132-1146, August 1993.
• 14: S. Malik, E. M. Sentovich, R. K. Brayton, and A. Sangiovanni- Vincentelli, "Retiming and Resynttz~is: Optimizing Sequential Networks with Combinatorial Techniques," IEEE Transactions on Computer-Aided Design, VoL CAD-10, No. 1, pp. 74-84, January 1991.
• 15: E.L. Lawler, Combinatorial Optim~on: Networks and Matroide. Holt, Rinehart and Winston, NewYork, 1976.
• 16: R. Lisanke, "Logic Synthesis and Optimization Benchnmrks User Guide:. Version 2.0," Tech. Rep., Microelectronics Center of North Carolina, December 1988.
• 17: S. Yang, "Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0," Tech. Rep., Microelectronics Center of North Carolina, January 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Measurement, Performance, Theory