Scheduling and optimal register placement for synchronous circuits derived using software pipelining techniques

ABSTRACT

Data dependency constraints constitute a lower bound P on the minimal clock period of single-phase clocked sequential circuits. In contrast to methods based on basic retiming, clocked sequential circuits with clock period P can always be obtained using software pipelining techniques. Such circuits can be derived by any method that can be framed in the following four-step process: Step 1, determine P; Step 2, compute a valid periodic schedule of the computational elements; Step 3, place registers back to the circuit; Step 4, assign the clock signals to control registers.Methods with polynomial run-time to implement this process are proposed in the literature. They implement these steps sequentially, starting with Step 1. These methods do not know how to optimally place registers which leads to an unnecessary number of registers. In this article, we address the problem of how to simultaneously implement Steps 2 and 3 in order to minimize the total number of registers. We conjecture that the problem is NP-hard in its general form. We formulate the problem for the first time in the literature, and devise a Mixed Integer Linear Program (MILP) to solve it. From this MILP, we derive a linear program to determine approximate solutions to the problem for large general circuits. We show that the proposed approach can handle nonzero clock skew. Experimental results confirm the effectiveness of the approach and show that significant reductions of the number of registers can be obtained although register sharing is not used. When the schedule is given, the proposed approach provides solutions to the problem of how to place the minimal number of registers in Step 3.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 3: Bennour, I.-E. 1996. Estimation de la performance et méthodes d'allocation dans la synthèse de systèmes numériques. Thèse de doctorat. DIRO, Université de Montréal.
• 4: Bennour, I.-E. and Aboulhamid, E.-M. 1995. Les problèmes d'ordonnancement cycliques dans la synthèse de systèmes numeriques. Technical Report 996 (Oct.). DIRO, Université de Montréal. http://www.iro.umontreal.ca/~aboulham/pipeline.pdf.
• 5: François R. Boyer , El Mostapha Aboulhamid , Yvon Savaria , Michel Boyer, Optimal design of synchronous circuits using software pipelining techniques, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.516-532, October 2001 [doi>10.1145/502175.502180]
• 6: Boyer, F.-R., Aboulhamid, E.-M., and Savaria, Y. 2001b. Minimizing sensitivity to clock skew variations using level sensitive latches. In Proceedings of European Conference on Circuit Theory and Design (Aug.). Espoo, Finland.
• 7: Boyer, F.-R., Aboulhamid, E.-M., and Savaria, Y. 2001c. An efficient verification method for a class of multi-phase sequential circuits. The 7th IEEE International Conference on Electronics, Circuits and Systems. Lebanon.
• 8: Noureddine Chabini , El Mostapha Aboulhamid , Yvon Savaria, Reducing Register and Phase Requirements for Synchronous Circuits Derived Using Software Pipelining Techniques, Proceedings of the IEEE Computer Society Workshop on VLSI 2001, p.71, April 19-20, 2001
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: Dasdan, A. and Gupta, R. K. 1998. Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 17, 10 (Oct.).
• 11: Rahul B. Deokar , Sachin S. Sapatnekar, A fresh look at retiming via clock skew optimization, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.310-315, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217547]
• 12: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696 ]
• 13: Xun Liu , Marios C. Papaefthymiou , Eby G. Friedman, Minimizing sensitivity to delay variations in high-performance synchronous circuits, Proceedings of the conference on Design, automation and test in Europe, p.126-es, January 1999, Munich, Germany [doi>10.1145/307418.307581]
• 14: Gerez, S.-H., De Groot, S.-M. -H., and Herrmann, O.-E. 1992. A polynomial-time algorithm for the computation of the iteration-period bound in recursive data-flow graphs. IEEE Trans. Circuits and Syst. 39, 1.
• 15: A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
• 16: ISCAS'89 Benchmark suite. 1996. Department of Computer Science. North Carolina State University. Available at http://www.cbl.ncsu.edu/benchmarks/.
• 17: 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]
• 18: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 19: Khachian, L.-G. 1979. A polynomial algorithm in linear programming. Soviet Math. Doklady 20.
• 20: S. Y. Kung , Thomas Kailath , Harper J. Whitehouse, VLSI and Modern Signal Processing, Prentice Hall Professional Technical Reference, 1984
• 21: K. N. Lalgudi , M. C. Papaefthymiou, Efficient retiming under a general delay model, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.368, March 27-29, 1995
• 22: Lawler, E.-L. 1976. Combinatorial Optimization: Networks and Matroids, Holt, Reinhart, and Winston, New York, NY.
• 23: Legl, C., Vanbekbergen, P., and Wang, A. 1997. Retiming of edge-triggered circuits with multiple clocks and load enables. IEEE/ACM International Workshop on Logic Synthesis (IWLS'97).
• 24: Leiserson, C. E. and Saxe, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 5--35.
• 25: Y.-M. Li , M. A. Jabri, A zero-skew clock routing scheme for VLSI circuits, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.458-463, December 1992, Santa Clara, California, United States
• 26: Liu, X., Papaefthymiou, M. C., and Friedman, E. G. 2002. Retiming and clock scheduling for digital circuit optimization. IEEE Trans. Comput.-Aided Design 21, 2, 184--203.
• 27: Lockyear, B. and Ebeling, C. 1994. Optimal retiming of level-clocked circuits using symmetric clock schedules. IEEE Trans. Comput.-Aided Design of Integr. Circuits Syst. 13 (Sept.), 1097--1109.
• 28: The LP_Solve Tool. Available at ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.
• 29: Naresh Maheshwari , Sachin S. Sapatnekar, An improved algorithm for minimum-area retiming, Proceedings of the 34th annual conference on Design automation, p.2-7, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266025]
• 30: Maheshwari, N. and Sapatnekar, S. S. 1999. Optimizing large multiphase level-clocked circuits. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 18, 9 (Sept.) 1249--1264.
• 31: Sapatnekar, S. S. and Deokar, R. B. 1996. Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE Trans. Comput.-Aided Design 15, 10 (Oct.), 1237--1248.
• 32: 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
• 33: Soyata, T., Friedman, E. G., and Mulligan, J. H. 1995. Monotonicity constraints on path delays for efficient retiming with localized clock skew and variable register delay. Proceedings of the IEEE International Symposium on Circuits and Systems (May.), 1748--1751.
• 34: Tolga Soyata , Eby G. Friedman, Retiming with non-zero clock skew, variable register, and interconnect delay, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.234-241, November 06-10, 1994, San Jose, California, United States
• 35: Tsay, R.-S. 1993. An exact zero-skew clock routing algorithm. IEEE Trans. Comput.- Aided Design 12 (Feb.), 242--249.

INDEX TERMS

Primary Classification:
  B. Hardware

General Terms:
Algorithms, Performance

Keywords:
Retiming, clock, multiphase, sequential circuit, software pipelining