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.
- Cocchini, P. 2002. Concurrent flip-flop and repeater insertion for high performance integrated circuits. In Proceedings of the International Conference on Computer-Aided Design. 268--273. Google ScholarDigital Library
- 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.Google Scholar
- Cong, J., Coudert, O., and Sarrafzadeh, M. 2000. Incremental CAD. In Proceedings of the International Conference on Computer-Aided Design. Google ScholarDigital Library
- Dasdan, A., Irani, S. S., and K. Gupta, R. 1999. Efficient algorithms for optimum cycle mean and optimum cost to time ratio. In Proceedings of the Design Automation Conference. Google ScholarDigital Library
- Dijkstra, E. W. 1975. Guarded commands, nondeterminacy, and the formal derivation of programs. Comm. ACM 8, 453--457. Google ScholarDigital Library
- Dijkstra, E. W. 1976. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
- Even, G., Spillinger, I. Y., and Stok, L. 1996. Retiming Revisited and Reversed. IEEE Trans. Comput.-Aid. Desi. Integr. Circ. 15, 3, 348--357. Google ScholarDigital Library
- Floyd, R. W. 1967. Assigning meanings to program. In Proceedings of the American Mathematics Society Symposia in Applied Mathematics. vol. 19, 19--31.Google ScholarCross Ref
- Ford, J. R. and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press.Google Scholar
- Goldberg, A. V. and Tarjan, R. E. 1988. A new approach to the maximum flow problem. J. ACM 35, 921--940. Google ScholarDigital Library
- Gries, D. and Schneider, F. B. 1993. A Logical Approach to Discrete Math. Springer-Verlag, Berlin, Germany. Google ScholarDigital Library
- Hassoun, S. and Alpert, C. J. 2002. Optimal path routing in single and multiple clock domain systems. In Proceedings of the International Conference on Computer-Aided Design. 247--253. Google ScholarDigital Library
- Hoare, C. A. R. 1969. An axiomatic basis for computing programming. Commun. ACM 12, 10, 576--580. Google ScholarDigital Library
- Ishii, A. T., Leiserson, C. E., and Papaefthymiou, M. C. 1997. Optimizing two-phase, level-clocked circuitry. J. ACM 44, 1, 148--199. Google ScholarDigital Library
- Leiserson, C. E. and Saxe, J. B. 1983. Optimizing Synchronous Systems. J. VLSI Comput. Syst. 1, 1, 41--67.Google Scholar
- Leiserson, C. E. and Saxe, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 1, 5--35.Google ScholarDigital Library
- Lockyear, B. and Ebeling, C. 1994. Optimal retiming of level-clocked circuits using symmetric clock schedules. IEEE Trans. Comput.-Aid. Des. 13, 1097--1109.Google ScholarDigital Library
- Maheshwari, N. and Sapatnekar, S. S. 1999. Optimizing large multi-phase level-clocked circuits. IEEE Trans. Comput.-Aid. Des. 18, 9, 1249--1264. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Papaefthymiou, M. C. and Randall, K. H. 1993. Tim: A timing package for two-phase, level-clocked circuitry. In Proceedings of the Design Automation Conference (Dallas, TX). 497--502. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Shenoy, N. and Rudell, R. 1994. Efficient implementation of retiming. In Proceedings of the International Conference on Computer-Aided Design. 226--233. Google ScholarDigital Library
- Singhal, V., Pixley, C., Rudell, R. L., and Brayton, R. K. 1995. The validity of retiming sequential circuits. In Proceedings of the Design Automation Conference (San Francisco, CA). 316--321. Google ScholarDigital Library
- Zhou, H. and Lin, C. 2004. Retiming for wire pipelining in system-on-chip. IEEE Trans. Comput. Aid. Des. 23, 9, 1338--1345. Google ScholarDigital Library
Index Terms
- A new efficient retiming algorithm derived by formal manipulation
Recommendations
An efficient incremental algorithm for min-area retiming
DAC '08: Proceedings of the 45th annual Design Automation ConferenceAs one of the most effective sequential optimization techniques, retiming is a structural transformation that relocates flip-flops in a circuit without changing its functionality. The min-area retiming problem seeks a solution with the minimum flip-flop ...
Deriving a new efficient algorithm for min-period retiming
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation ConferenceA 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 ...
Retiming synchronous circuitry
AbstractThis paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming ...
Comments