A new efficient retiming algorithm derived by formal manipulation

ABSTRACT

A new efficient algorithm is derived for the minimal period retiming by formal manipulation. Contrary to all previous algorithms, which used fixed period feasibility checking to binary-search a candidate range, the derived algorithm checks the optimality of a feasible period directly. It is much simpler and more efficient than previous algorithms. Experimental results showed that it is even faster than ASTRA, an efficient heuristic algorithm. Since the derived algorithm is incremental by nature, it also opens the opportunity to be combined with other optimization techniques.

REFERENCES

• 1: Pasquale Cocchini, Concurrent flip-flop and repeater insertion for high performance integrated circuits, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.268-273, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774612]
• 2: Cochet-Terrasson, J., Cohen, G., Gaubert, S., McGettrick, M., and Quadrat, J.-P. 1998. Numerical computation of spectral elements in max-plus algebra. In Proceedings of the IFAC Conference on System Structure and Control.
• 3: Olivier Coudert , Jason Cong , Sharad Malik , Majid Sarrafzadeh, Incremental CAD, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 4: Ali Dasdan , Sandy S. Irani , Rajesh K. Gupta, Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.37-42, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309862]
• 5: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 6: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 7: Even, G., Spillinger, I. Y., and Stok, L. 1996. Retiming Revisited and Reversed. IEEE Trans. Comput.-Aid. Desi. Integr. Circ. 15, 3, 348--357.
• 8: Floyd, R. W. 1967. Assigning meanings to program. In Proceedings of the American Mathematics Society Symposia in Applied Mathematics. vol. 19, 19--31.
• 9: Ford, J. R. and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press.
• 10: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 11: David Gries , Fred B. Schneider, A logical approach to discrete math, Springer-Verlag New York, Inc., New York, NY, 1993
• 12: Soha Hassoun , Charles J. Alpert , Meera Thiagarajan, Optimal buffered routing path constructions for single and multiple clock domain systems, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.247-253, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774609]
• 13: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 14: Alexander T. Ishii , Charles E. Leiserson , Marios C. Papaefthymiou, Optimizing two-phase, level-clocked circuitry, Journal of the ACM (JACM), v.44 n.1, p.148-199, Jan. 1997 [doi>10.1145/256292.256301]
• 15: Leiserson, C. E. and Saxe, J. B. 1983. Optimizing Synchronous Systems. J. VLSI Comput. Syst. 1, 1, 41--67.
• 16: Leiserson, C. E. and Saxe, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 1, 5--35.
• 17: Lockyear, B. and Ebeling, C. 1994. Optimal retiming of level-clocked circuits using symmetric clock schedules. IEEE Trans. Comput.-Aid. Des. 13, 1097--1109.
• 18: Maheshwari, N. and Sapatnekar, S. S. 1999. Optimizing large multi-phase level-clocked circuits. IEEE Trans. Comput.-Aid. Des. 18, 9, 1249--1264.
• 19: Malik, S., Singh, K. J., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1993. Performance optimization of piplelined circuits using peripheral retiming and resynthesis. IEEE Trans. Comput.-Aid. Des. 12, 5, 568--578.
• 20: Pan, P., Karandikar, A. K., and Liu, C. L. 1998. Optimal clock period clustering for sequential circuits with retiming. IEEE Trans. Comput.-Aid. Desi. 17, 6, 489--498.
• 21: Marios C. Papaefthymiou , Keith H. Randall, TIM: a timing package for two-phase, level-clocked circuitry, Proceedings of the 30th international conference on Design automation, p.497-502, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164998]
• 22: Sapatnekar, S. S. and Deokar, R. B. 1996. Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE Trans. Comput.-Aid. Desi. 15, 10, 1237--1248.
• 23: Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
• 24: Vigyan Singhal , Carl Pixley , Richard L. Rudell , Robert K. Brayton, The validity of retiming sequential circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.316-321, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217548]
• 25: Zhou, H. and Lin, C. 2004. Retiming for wire pipelining in system-on-chip. IEEE Trans. Comput. Aid. Des. 23, 9, 1338--1345.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
Clockperiod minimization, algorithm derivation, retiming