Experimental analysis of the fastest optimum cycle ratio and mean algorithms
- 1 October 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 9 (4), 385-418
- https://doi.org/10.1145/1027084.1027085
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.Keywords
This publication has 19 references indexed in Scilit:
- Rate analysis for embedded systemsACM Transactions on Design Automation of Electronic Systems, 1998
- Faster maximum and minimum mean cycle algorithms for system-performance analysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Performance analysis and optimization of mixed asynchronous synchronous systemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- Computational investigations of maximum flow algorithmsEuropean Journal of Operational Research, 1997
- An algorithm for exact bounds on the time separation of events in concurrent systemsIEEE Transactions on Computers, 1995
- Tight bounds on the number of minimum-mean cycle cancellations and related resultsAlgorithmica, 1994
- Finding minimum cost to time ratio cycles with small integral transit timesNetworks, 1993
- Faster parametric shortest path and minimum‐balance algorithmsNetworks, 1991
- Parametric shortest path algorithms with an application to cyclic staffingDiscrete Applied Mathematics, 1981
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978