{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T13:09:36Z","timestamp":1675343376363},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2004,10]]},"abstract":"Optimum cycle ratio (OCR) algorithms are fundamental to the performance analysis of (digital or manufacturing) systems with cycles. Some applications in the computer-aided design field include cycle time and slack optimization for circuits, retiming, timing separation analysis, and rate analysis. There are many OCR algorithms, and since a superior time complexity in theory does not mean a superior time complexity in practice, or vice-versa, it is important to know how these algorithms perform in practice on real circuit benchmarks. A recent published study experimentally evaluated almost all the known OCR algorithms, and determined the fastest one among them. This article improves on that study in the following ways: (1) it focuses on the fastest OCR algorithms only; (2) it provides a unified theoretical framework and a few new results; (3) it runs these algorithms on the largest circuit benchmarks available; (4) it compares the algorithms in terms of many properties in addition to running times such as operation counts, convergence behavior, space requirements, generality, simplicity, and robustness; (5) it analyzes the experimental results using statistical techniques and provides asymptotic time complexity of each algorithm in practice; and (6) it provides clear guidance to the use and implementation of these algorithms together with our algorithmic improvements.<\/jats:p>","DOI":"10.1145\/1027084.1027085","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"385-418","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":106,"title":["Experimental analysis of the fastest optimum cycle ratio and mean algorithms"],"prefix":"10.1145","volume":"9","author":[{"given":"Ali","family":"Dasdan","sequence":"first","affiliation":[{"name":"Synopsys, Inc., Mountain View, CA"}]}],"member":"320","published-online":{"date-parts":[[2004,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/S0377-2217(96)00269-X","article-title":"Computational investigations of maximum flow algorithms","volume":"97","author":"Ahuja R. K.","year":"1997","unstructured":"Ahuja , R. K. , Kodialam , M. , Mishra , A. K. , and Orlin , J. B. 1997 . Computational investigations of maximum flow algorithms . Europ. J. Oper. Res. 97 , 509 -- 542 . Ahuja, R. K., Kodialam, M., Mishra, A. K., and Orlin, J. B. 1997. Computational investigations of maximum flow algorithms. Europ. J. Oper. Res. 97, 509--542.","journal-title":"Europ. J. Oper. Res."},{"key":"e_1_2_1_2_1","unstructured":"Ahuja R. K. Magnanti T. L. and Orlin J. B. 1993. Network Flows. Prentice Hall Upper Saddle River N.J. Ahuja R. K. Magnanti T. L. and Orlin J. B. 1993. Network Flows. Prentice Hall Upper Saddle River N.J."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, Calif., 232--238","author":"Albrecht C.","unstructured":"Albrecht , C. , Korte , B. , Schietke , J. , and Vygen , J . 1999. Cycle time and slack optimization for VLSI chips . In Proceedings of the International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, Calif., 232--238 . Albrecht, C., Korte, B., Schietke, J., and Vygen, J. 1999. Cycle time and slack optimization for VLSI chips. In Proceedings of the International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, Calif., 232--238."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Symposium on Physical Design. ACM\/IEEE","author":"Alpert C. J.","year":"1998","unstructured":"Alpert , C. J. 1998 . The ISPD98 circuit benchmark suite . In Proceedings of the International Symposium on Physical Design. ACM\/IEEE , New York, 588--593. 10.1145\/274535.274546 Alpert, C. J. 1998. The ISPD98 circuit benchmark suite. In Proceedings of the International Symposium on Physical Design. ACM\/IEEE, New York, 588--593. 10.1145\/274535.274546"},{"key":"e_1_2_1_5_1","volume-title":"-P","author":"Bacelli F.","year":"1992","unstructured":"Bacelli , F. , Cohen , G. , Olsder , G. J. , and Quadrat , J . -P . 1992 . Synchronization and Linearity. Wiley , New York. Bacelli, F., Cohen, G., Olsder, G. J., and Quadrat, J.-P. 1992. Synchronization and Linearity. Wiley, New York."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 37th Design Automation Conference","author":"Carloni L. P.","unstructured":"Carloni , L. P. and Sangiovanni-Vincentelli , A. L. 2000. Performance analysis and optimization of latency insensitive systems . In Proceedings of the 37th Design Automation Conference . IEEE Computer Society Press , Los Alamitos , Calif., 361--367. 10.1145\/337292.337441 Carloni, L. P. and Sangiovanni-Vincentelli, A. L. 2000. Performance analysis and optimization of latency insensitive systems. In Proceedings of the 37th Design Automation Conference. IEEE Computer Society Press, Los Alamitos, Calif., 361--367. 10.1145\/337292.337441"},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. UMIACS-TR-99-59","author":"Chandrachoodan N.","year":"1999","unstructured":"Chandrachoodan , N. , Bhattacharyya , S. S. , and Liu , K. R . 1999 . Negative cycle detection in dynamic graphs. Tech. Rep. UMIACS-TR-99-59 , Institute for Advanced Computer Studies, Univ. of Maryland at College Park, College Park , Md., Sept. Chandrachoodan, N., Bhattacharyya, S. S., and Liu, K. R. 1999. Negative cycle detection in dynamic graphs. Tech. Rep. UMIACS-TR-99-59, Institute for Advanced Computer Studies, Univ. of Maryland at College Park, College Park, Md., Sept."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 4th European Symposium on Algorithms. 349--363","author":"Cherkassky B. V.","unstructured":"Cherkassky , B. V. and Goldberg , A. V . 1996. Negative-cycle detection algorithms . In Proceedings of the 4th European Symposium on Algorithms. 349--363 . Cherkassky, B. V. and Goldberg, A. V. 1996. Negative-cycle detection algorithms. In Proceedings of the 4th European Symposium on Algorithms. 349--363."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IFAC Conference on System Structure and Control.","author":"Cochet-Terrasson J.","unstructured":"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. 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."},{"key":"e_1_2_1_11_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1991. Introduction to Algorithms. MIT Press Cambridge Mass. Cormen T. H. Leiserson C. E. and Rivest R. L. 1991. Introduction to Algorithms. MIT Press Cambridge Mass."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF02662016","article-title":"Maximum cycle-means of weighted digraphs","volume":"11","author":"Cuninghame-Green R. A.","year":"1996","unstructured":"Cuninghame-Green , R. A. and Yixun , L. 1996 . Maximum cycle-means of weighted digraphs . Applied Math.-JCU 11 , 225 -- 234 . Cuninghame-Green, R. A. and Yixun, L. 1996. Maximum cycle-means of weighted digraphs. Applied Math.-JCU 11, 225--234.","journal-title":"Applied Math.-JCU"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Dantzig B. Blattner W. and Rao M. R. 1967. Finding a cycle in a graph with minimum cost to times ratio with applications to a ship routing problem. In Theory of Graphs P. Rosenstiehl Ed. Dunod Paris and Gordon and Breach New York 77--84. Dantzig B. Blattner W. and Rao M. R. 1967. Finding a cycle in a graph with minimum cost to times ratio with applications to a ship routing problem. In Theory of Graphs P. Rosenstiehl Ed. Dunod Paris and Gordon and Breach New York 77--84.","DOI":"10.21236\/AD0646553"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 10th International Symposium on HW\/SW Codesign (CODES). 127--132","author":"Dasdan A.","year":"2002","unstructured":"Dasdan , A. 2002 . A strongly polynomial algorithm for over-constraint resolution . In Proceedings of the 10th International Symposium on HW\/SW Codesign (CODES). 127--132 . 10.1145\/774789.774816 Dasdan, A. 2002. A strongly polynomial algorithm for over-constraint resolution. In Proceedings of the 10th International Symposium on HW\/SW Codesign (CODES). 127--132. 10.1145\/774789.774816"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.728912"},{"key":"e_1_2_1_16_1","unstructured":"Dasdan A. Irani S. and Gupta R. K. 1998. An experimental study of minimum mean cycle algorithms. Tech. Rep. #98-32 University of California Irvine Calif. July. Dasdan A. Irani S. and Gupta R. K. 1998. An experimental study of minimum mean cycle algorithms. Tech. Rep. #98-32 University of California Irvine Calif. July."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 36th Design Automation Conference. 10","author":"Dasdan A.","unstructured":"Dasdan , A. , Irani , S. , and Gupta , R. K . 1999. Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems . In Proceedings of the 36th Design Automation Conference. 10 .1145\/309847.309862 Dasdan, A., Irani, S., and Gupta, R. K. 1999. Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In Proceedings of the 36th Design Automation Conference. 10.1145\/309847.309862"},{"key":"e_1_2_1_18_1","unstructured":"Goldberg A. V. 2001. A practical shortest path algorithm with linear expected time. Submitted to SIAM J. Comput. http:\/\/www.avglab.com\/andrew\/. Goldberg A. V. 2001. A practical shortest path algorithm with linear expected time. Submitted to SIAM J. Comput. http:\/\/www.avglab.com\/andrew\/."},{"key":"e_1_2_1_19_1","unstructured":"Gondran M. and Minoux M. 1984. Graphs and Algorithms. Wiley New York. Gondran M. and Minoux M. 1984. Graphs and Algorithms. Wiley New York."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1002\/net.3230230607","article-title":"Finding minimum cost to time ratio cycles with small integral transit times","volume":"23","author":"Hartmann M.","year":"1993","unstructured":"Hartmann , M. and Orlin , J. B. 1993 . Finding minimum cost to time ratio cycles with small integral transit times . Networks 23 , 567 -- 574 . Hartmann, M. and Orlin, J. B. 1993. Finding minimum cost to time ratio cycles with small integral transit times. Networks 23, 567--574.","journal-title":"Networks"},{"key":"e_1_2_1_21_1","volume-title":"Dynamic Programming and Markov Processes","author":"Howard R. A.","unstructured":"Howard , R. A. 1960. Dynamic Programming and Markov Processes . The M.I.T. Press , Cambridge, Mass . Howard, R. A. 1960. Dynamic Programming and Markov Processes. The M.I.T. Press, Cambridge, Mass."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.475126"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02107055"},{"key":"e_1_2_1_24_1","volume-title":"The Art of Computer Systems Peformance Analysis","author":"Jain R.","unstructured":"Jain , R. 1991. The Art of Computer Systems Peformance Analysis . Wiley-Interscience , New York . Jain, R. 1991. The Art of Computer Systems Peformance Analysis. Wiley-Interscience, New York."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Johnson D. S.","unstructured":"Johnson , D. S. , McGeoch , L. A. , and Rothberg , E. E . 1996. Asymptotic experimental analysis for the held-karp traveling salesman bound . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 341--350. Johnson, D. S., McGeoch, L. A., and Rothberg, E. E. 1996. Asymptotic experimental analysis for the held-karp traveling salesman bound. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 341--350."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","article-title":"A characterization of the minimum cycle mean in a digraph","volume":"23","author":"Karp R. M.","year":"1978","unstructured":"Karp , R. M. 1978 . A characterization of the minimum cycle mean in a digraph . Disc. Math. 23 , 309 -- 311 . Karp, R. M. 1978. A characterization of the minimum cycle mean in a digraph. Disc. Math. 23, 309--311.","journal-title":"Disc. Math."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","article-title":"Parametric shortest path algorithms with an application to cyclic staffing","volume":"3","author":"Karp R. M.","year":"1981","unstructured":"Karp , R. M. and Orlin , J. B. 1981 . Parametric shortest path algorithms with an application to cyclic staffing . Disc. Appl. Math. 3 , 37 -- 45 . Karp, R. M. and Orlin, J. B. 1981. Parametric shortest path algorithms with an application to cyclic staffing. Disc. Appl. Math. 3, 37--45.","journal-title":"Disc. Appl. Math."},{"key":"e_1_2_1_28_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 . Lawler, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/293625.293631"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"e_1_2_1_32_1","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn K.","year":"2000","unstructured":"Mehlhorn , K. and Naher , S . 2000 . LEDA: A Platform for Combinatorial and Geometric Computing . The Cambridge University Press , New York . Mehlhorn, K. and Naher, S. 2000. LEDA: A Platform for Combinatorial and Geometric Computing. The Cambridge University Press, New York."},{"key":"e_1_2_1_33_1","unstructured":"Mendenhall W. and Beaver R. J. 1994. Introduction to Probability and Statistics. Duxbury Press Belmont Calif. Mendenhall W. and Beaver R. J. 1994. Introduction to Probability and Statistics. Duxbury Press Belmont Calif."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 31st Design Automation Conference. IEEE, Computer Society Press, Los Alamitos, Calif., 70--76","author":"Nielsen C. D.","year":"1962","unstructured":"Nielsen , C. D. and Kishinevsky , M . 1994. Peformance analysis based on timing simulation . In Proceedings of the 31st Design Automation Conference. IEEE, Computer Society Press, Los Alamitos, Calif., 70--76 . 10.1145\/ 1962 44.196281 Nielsen, C. D. and Kishinevsky, M. 1994. Peformance analysis based on timing simulation. In Proceedings of the 31st Design Automation Conference. IEEE, Computer Society Press, Los Alamitos, Calif., 70--76. 10.1145\/196244.196281"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586040"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/BF01240734","article-title":"Tight bounds on the number of minimum-mean cycle cancellations and related results","volume":"11","author":"Radzik T.","year":"1994","unstructured":"Radzik , T. and Goldberg , A. V. 1994 . Tight bounds on the number of minimum-mean cycle cancellations and related results . Algorithmica 11 , 226 -- 242 . Radzik, T. and Goldberg, A. V. 1994. Tight bounds on the number of minimum-mean cycle cancellations and related results. Algorithmica 11, 226--242.","journal-title":"Algorithmica"},{"key":"e_1_2_1_37_1","first-page":"5","article-title":"Performance evaluation of asynchronous concurrent systems using petri nets","volume":"6","author":"Ramamoorthy C. V.","year":"1980","unstructured":"Ramamoorthy , C. V. and Ho , G. S. 1980 . Performance evaluation of asynchronous concurrent systems using petri nets . IEEE Trans. Software Eng. 6 , 5 (Sept.), 440--9. Ramamoorthy, C. V. and Ho, G. S. 1980. Performance evaluation of asynchronous concurrent systems using petri nets. IEEE Trans. Software Eng. 6, 5 (Sept.), 440--9.","journal-title":"IEEE Trans. Software Eng."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 31st Design Automation Conference. IEEE, Computer Society Press, Los Alamitos, Calif., 226--33","author":"Shenoy N.","unstructured":"Shenoy , N. and Rudell , R . 1994. Efficient implementation of retiming . In Proceedings of the 31st Design Automation Conference. IEEE, Computer Society Press, Los Alamitos, Calif., 226--33 . Shenoy, N. and Rudell, R. 1994. Efficient implementation of retiming. In Proceedings of the 31st Design Automation Conference. IEEE, Computer Society Press, Los Alamitos, Calif., 226--33."},{"key":"e_1_2_1_39_1","unstructured":"Skorobohatyj G. 1993. Code for finding a minimum mean cycle in a directed graph. WWW document Konrad-Zuse-Zentrum fur Informationstechnik Berlin (http:\/\/elib.zib.de\/pub\/Packages\/mathprog\/netopt\/mmc\/). Skorobohatyj G. 1993. Code for finding a minimum mean cycle in a directed graph. WWW document Konrad-Zuse-Zentrum fur Informationstechnik Berlin (http:\/\/elib.zib.de\/pub\/Packages\/mathprog\/netopt\/mmc\/)."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 29th Design Automation Conference. ACM","author":"Szymanski T. G.","year":"1992","unstructured":"Szymanski , T. G. 1992 . Computing optimal clock schedules . In Proceedings of the 29th Design Automation Conference. ACM , New York, 399--404. Szymanski, T. G. 1992. Computing optimal clock schedules. In Proceedings of the 29th Design Automation Conference. ACM, New York, 399--404."},{"key":"e_1_2_1_41_1","article-title":"Shortest paths","author":"Tarjan R. E.","year":"1981","unstructured":"Tarjan , R. E. 1981 . Shortest paths . Tech. Rep., AT&T Bell Laboratories, Murray Hill, N.J. Tarjan, R. E. 1981. Shortest paths. Tech. Rep., AT&T Bell Laboratories, Murray Hill, N.J.","journal-title":"Tech. Rep., AT&T Bell Laboratories, Murray Hill, N.J."},{"key":"e_1_2_1_42_1","volume-title":"Data Structures and Network Algorithms","author":"Tarjan R. E.","unstructured":"Tarjan , R. E. 1983. Data Structures and Network Algorithms . Society for Industrial and Applied Math., Philadelphia, Pa . Tarjan, R. E. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Math., Philadelphia, Pa."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.631210"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/net.3230210206","article-title":"Faster parametric shortest path and minimum-balance algorithms","volume":"21","author":"Young N. E.","year":"1991","unstructured":"Young , N. E. , Tarjan , R. E. , and Orlin , J. B. 1991 . Faster parametric shortest path and minimum-balance algorithms . Networks 21 , 205 -- 221 . Young, N. E., Tarjan, R. E., and Orlin, J. B. 1991. Faster parametric shortest path and minimum-balance algorithms. Networks 21, 205--221.","journal-title":"Networks"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1027084.1027085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:38:36Z","timestamp":1672241916000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1027084.1027085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1145\/1027084.1027085"],"URL":"http:\/\/dx.doi.org\/10.1145\/1027084.1027085","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":[[2004,10]]},"assertion":[{"value":"2004-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}