Deriving a new efficient algorithm for min-period retiming

ABSTRACT

A new efficient algorithm is derived for the minimal period retiming problem by formal methods. Contrary to all previous algorithms, which used binary search to check feasibilities on a range of candidate periods, the derived algorithm checks the optimality of a current 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: G. De Micheli. Synchronous Logic Synthesis: Algorithms for Cycle-Time Minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 10(1):63--73, January 1991.
• 3: 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]
• 4: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 5: G. Even, I. Y. Spillinger, and L. Stok. Retiming Revisited and Reversed. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 15(3):348--357, March 1996.
• 6: R. W. Floyd. Assigning meanings to program. In Proc. Amer. Math. Soc. Symposia in Applied Mathematics, volume 19, pages 19--31, 1967.
• 7: David Gries , Fred B. Schneider, A logical approach to discrete math, Springer-Verlag New York, Inc., New York, NY, 1993
• 8: 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]
• 9: 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]
• 10: 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]
• 11: C. E. Leiserson and J. B. Saxe. Optimizing Synchronous Systems. Journal of VLSI and Computer Systems, 1(1):41--67, Spring 1983.
• 12: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5--35, 1991.
• 13: S. S. Sapatnekar and R. B Deokar. Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE TCAD, 15(10):1237--1248, October 1996.
• 14: H. Zhou and C. Lin. Retiming for wire pipelining in system-on-chip. IEEE TCAD, 23(9):1338--1345, September 2004.