{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:16:27Z","timestamp":1672290987296},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2005,4]]},"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.<\/jats:p>","DOI":"10.1145\/1059876.1059877","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"187-204","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling and optimal register placement for synchronous circuits derived using software pipelining techniques"],"prefix":"10.1145","volume":"10","author":[{"given":"Noureddine","family":"Chabini","sequence":"first","affiliation":[{"name":"Royal Military College of Canada, Canada"}]},{"given":"El Mostapha","family":"Aboulhamid","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al, Canada"}]},{"given":"Isma\u00efl","family":"Chabini","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, MA, USA"}]},{"given":"Yvon","family":"Savaria","sequence":"additional","affiliation":[{"name":"\u00e9cole Polytechnique de Montr\u00e9al, QC, Canada"}]}],"member":"320","published-online":{"date-parts":[[2005,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"-B","author":"Ahuja R.-K.","year":"1993","unstructured":"Ahuja , R.-K. , Magnanti , T.-L. , and Orlin , J . -B . 1993 . Network Flows : Theory, Algorithms, and Applications, Prentice Hall , Englewood Cliffs, NJ. Ahuja, R.-K., Magnanti, T.-L., and Orlin, J.-B. 1993. Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/212094.212131"},{"key":"e_1_2_1_3_1","unstructured":"Bennour I.-E. 1996. Estimation de la performance et m\u00e9thodes d'allocation dans la synth\u00e8se de syst\u00e8mes num\u00e9riques. Th\u00e8se de doctorat. DIRO Universit\u00e9 de Montr\u00e9al. Bennour I.-E. 1996. Estimation de la performance et m\u00e9thodes d'allocation dans la synth\u00e8se de syst\u00e8mes num\u00e9riques. Th\u00e8se de doctorat. DIRO Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502175.502180"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of European Conference on Circuit Theory and Design (Aug.)","author":"Boyer F.-R.","unstructured":"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. 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."},{"key":"e_1_2_1_7_1","volume-title":"The 7th IEEE International Conference on Electronics, Circuits and Systems. Lebanon.","author":"Boyer F.-R.","unstructured":"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. 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."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of IEEE Computer Society Workshop on VLSI (April)","author":"Chabini N.","unstructured":"Chabini , N. , Aboulhamid , E.-M. , and Savaria , Y . 2001. Reducing register and phase requirements for synchronous circuits derived using software pipelining techniques . In Proceedings of IEEE Computer Society Workshop on VLSI (April) . Orlando, FL. Chabini, N., Aboulhamid, E.-M., and Savaria, Y. 2001. Reducing register and phase requirements for synchronous circuits derived using software pipelining techniques. In Proceedings of IEEE Computer Society Workshop on VLSI (April). Orlando, FL."},{"key":"e_1_2_1_9_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. McGraw Hill New York NY. Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. McGraw Hill New York NY."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.728912"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference, 304--309","author":"Deokar R. B.","unstructured":"Deokar , R. B. and Sapatnekar , S. S . 1995. A fresh look at retiming via clock skew optimization . In Proceedings of the ACM\/IEEE Design Automation Conference, 304--309 . 10.1145\/217474.217547 Deokar, R. B. and Sapatnekar, S. S. 1995. A fresh look at retiming via clock skew optimization. In Proceedings of the ACM\/IEEE Design Automation Conference, 304--309. 10.1145\/217474.217547"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.55696"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of Design Automation and Test in Europe, 643--649","author":"Friedman E. G.","unstructured":"Friedman , E. G. , Liu , X. , and Papaefthymiou , M. C . 1999. Minimizing sensitivity to delay variations in high-performance synchronous circuits . Proceedings of Design Automation and Test in Europe, 643--649 . 10.1145\/307418.307581 Friedman, E. G., Liu, X., and Papaefthymiou, M. C. 1999. Minimizing sensitivity to delay variations in high-performance synchronous circuits. Proceedings of Design Automation and Test in Europe, 643--649. 10.1145\/307418.307581"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"A polynomial-time algorithm for the computation of the iteration-period bound in recursive data-flow graphs","volume":"39","author":"Gerez S.-H.","year":"1992","unstructured":"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 . 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.","journal-title":"IEEE Trans. Circuits and Syst."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing (May)","author":"Goldberg A.-V.","unstructured":"Goldberg , A.-V. and Tarjan , R . -E. 1987. Solving minimum-cost flow problems by successive approximation . Proceedings of the 19th Annual ACM Symposium on Theory of Computing (May) . New York, NY. 10.1145\/28395.28397 Goldberg, A.-V. and Tarjan, R.-E. 1987. Solving minimum-cost flow problems by successive approximation. Proceedings of the 19th Annual ACM Symposium on Theory of Computing (May). New York, NY. 10.1145\/28395.28397"},{"key":"e_1_2_1_16_1","volume-title":"Department of Computer Science","author":"S'","unstructured":"ISCA S' 89 Benchmark suite. 1996. Department of Computer Science . North Carolina State University . Available at http:\/\/www.cbl.ncsu.edu\/benchmarks\/. ISCAS'89 Benchmark suite. 1996. Department of Computer Science. North Carolina State University. Available at http:\/\/www.cbl.ncsu.edu\/benchmarks\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256301"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Karmakar N. 1984. A new polynomial-time algorithm for linear programming. Combinatorica 4. 10.1007\/BF02579150 Karmakar N. 1984. A new polynomial-time algorithm for linear programming. Combinatorica 4. 10.1007\/BF02579150","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_19_1","unstructured":"Khachian L.-G. 1979. A polynomial algorithm in linear programming. Soviet Math. Doklady 20. Khachian L.-G. 1979. A polynomial algorithm in linear programming. Soviet Math. Doklady 20."},{"key":"e_1_2_1_20_1","unstructured":"Kung S. Y. Whitehouse H. J. and Kailath T. 1985. LSI and Modern Signal Processing Prentice-Hall Inc. Englewood Cliffs NJ. 259--60. Kung S. Y. Whitehouse H. J. and Kailath T. 1985. LSI and Modern Signal Processing Prentice-Hall Inc. Englewood Cliffs NJ. 259--60."},{"key":"e_1_2_1_21_1","volume-title":"Advanced Research in VLSI: Proceedings of the 1995 Chapel Hill Conference (March).","author":"Lalgudi K. N.","unstructured":"Lalgudi , K. N. and Papaefthymiou , M. C . 1995. Efficient retiming under a general delay model . Advanced Research in VLSI: Proceedings of the 1995 Chapel Hill Conference (March). Lalgudi, K. N. and Papaefthymiou, M. C. 1995. Efficient retiming under a general delay model. Advanced Research in VLSI: Proceedings of the 1995 Chapel Hill Conference (March)."},{"key":"e_1_2_1_22_1","volume-title":"Combinatorial Optimization: Networks and Matroids, Holt, Reinhart, and Winston","author":"Lawler E.-L.","year":"1976","unstructured":"Lawler , E.-L. 1976 . Combinatorial Optimization: Networks and Matroids, Holt, Reinhart, and Winston , New York, NY . Lawler, E.-L. 1976. Combinatorial Optimization: Networks and Matroids, Holt, Reinhart, and Winston, New York, NY."},{"key":"e_1_2_1_23_1","volume-title":"IEEE\/ACM International Workshop on Logic Synthesis (IWLS'97)","author":"Legl C.","unstructured":"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) . 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)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01759032","article-title":"Retiming synchronous circuitry","volume":"6","author":"Leiserson C. E.","year":"1991","unstructured":"Leiserson , C. E. and Saxe , J. B. 1991 . Retiming synchronous circuitry . Algorithmica 6 , 5 -- 35 . Leiserson, C. E. and Saxe, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 5--35.","journal-title":"Algorithmica"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Computer-Aided Design.","author":"Li Y. -M.","unstructured":"Li , Y. -M. and Jabori , M . -A. 1992. A zero-skew clock routing scheme for VLSI circuits . In Proceedings of the International Conference on Computer-Aided Design. Li, Y. -M. and Jabori, M.-A. 1992. A zero-skew clock routing scheme for VLSI circuits. In Proceedings of the International Conference on Computer-Aided Design."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.980258"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1109\/43.310899","article-title":"Optimal retiming of level-clocked circuits using symmetric clock schedules","volume":"13","author":"Lockyear B.","year":"1994","unstructured":"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 . 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.","journal-title":"IEEE Trans. Comput.-Aided Design of Integr. Circuits Syst."},{"key":"e_1_2_1_28_1","unstructured":"The LP_Solve Tool. Available at ftp:\/\/ftp.ics.ele.tue.nl\/pub\/lp_solve\/. The LP_Solve Tool. Available at ftp:\/\/ftp.ics.ele.tue.nl\/pub\/lp_solve\/."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference, 2--6. 10","author":"Maheshwari N.","unstructured":"Maheshwari , N. and Sapatnekar , S. S . 1997. An improved algorithm for minimum area retiming . In Proceedings of the ACM\/IEEE Design Automation Conference, 2--6. 10 .1145\/266021.266025 Maheshwari, N. and Sapatnekar, S. S. 1997. An improved algorithm for minimum area retiming. In Proceedings of the ACM\/IEEE Design Automation Conference, 2--6. 10.1145\/266021.266025"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.784118"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.541443"},{"key":"e_1_2_1_32_1","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design","author":"Shenoy N.","unstructured":"Shenoy , N. and Rudell , R . 1994. Efficient implementation of retiming . IEEE\/ACM International Conference on Computer-Aided Design , San Jose, CA. Shenoy, N. and Rudell, R. 1994. Efficient implementation of retiming. IEEE\/ACM International Conference on Computer-Aided Design, San Jose, CA."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems (May.), 1748--1751","author":"Soyata T.","unstructured":"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 . 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."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design (Nov.), 234--241","author":"Soyata T.","unstructured":"Soyata , T. and Friedman , E. G . 1994. Retiming with non-zero clock skew, variable register, and interconnect delay . Proceedings of the IEEE International Conference on Computer-Aided Design (Nov.), 234--241 . Soyata, T. and Friedman, E. G. 1994. Retiming with non-zero clock skew, variable register, and interconnect delay. Proceedings of the IEEE International Conference on Computer-Aided Design (Nov.), 234--241."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1109\/43.205004","article-title":"An exact zero-skew clock routing algorithm","volume":"12","author":"Tsay R.-S.","year":"1993","unstructured":"Tsay , R.-S. 1993 . An exact zero-skew clock routing algorithm . IEEE Trans. Comput.- Aided Design 12 ( Feb. ), 242 -- 249 . Tsay, R.-S. 1993. An exact zero-skew clock routing algorithm. IEEE Trans. Comput.- Aided Design 12 (Feb.), 242--249.","journal-title":"IEEE Trans. Comput.- Aided Design"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1059876.1059877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:05:35Z","timestamp":1672229135000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1059876.1059877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,4]]}},"alternative-id":["10.1145\/1059876.1059877"],"URL":"http:\/\/dx.doi.org\/10.1145\/1059876.1059877","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":["Electrical and Electronic Engineering","Computer Graphics and Computer-Aided Design","Computer Science Applications"],"published":{"date-parts":[[2005,4]]},"assertion":[{"value":"2005-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}