Efficient performance analysis of asynchronous systems based on periodicity

ABSTRACT

This paper presents an efficient method for the performance analysis and optimization of asynchronous systems. An asynchronous system is modeled as a marked graph with probabilistic delay distributions. We show that these systems exhibit inherent periodic behaviors. Based on this property, we derive an algorithm to construct the state space of the system through composition and capture the time evolution of the states into a periodic Markov chain. The system is solved for important performance metrics such as the distribution of input arrival time at a component, which is useful for subsequent system optimization, as well as relative component utilization, system latency and throughput. We also present a tool to demonstrate the feasibility of this method. Initial experimental results are promising, showing over three orders of magnitude improvement in runtime and nearly two orders of magnitude decrease in the size of the state space over previously published results. While the focus of this paper is on asynchronous digital systems, our technique can be applied to other concurrent systems that exhibit global asynchronous behavior, such as GALS and embedded systems.

REFERENCES

• 1: Martin Bene_ , Steven M. Nowick , Andrew Wolfe, A Fast Asynchronous Huffman Decoder for Compressed-Code Embedded Processors, Proceedings of the 4th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.0043, March 30-April 02, 1998
• 2: David S. Bormann, Asynchronous Wrapper for Heterogeneous Systems, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.307, October 12-15, 1997
• 3: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 4: Rohan Angrish, Probabilistic Timing Analysis of Asynchronous Systems with Moments of Delays, Proceedings of the 8th International Symposium on Asynchronus Circuits and Systems, p.99, April 08-11, 2002
• 5: Daniel Marcos Chapiro, Globally-asynchronous locally-synchronous systems (performance, reliability, digital), 1985
• 6: E. Cinlar. Introduction to Stochastic Processes. Prentice-Hall, Inc., 1973.
• 7: F. Commoner, A. Holt, S. Even, and A. Pnueli. Marked directed graphs. Journal of Computer and System Sciences, 5:511--523, 1971.
• 8: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 9: W. Feller. An Introduction to Probability Theory and Its Application, Vol. 1. John Wiley and Sons, Inc., 1968.
• 10: M. Greenstreet and K. Steiglitz. Bubbles can make self-timed pipelines fast. Journal of VLSI Signal Processing, 2:139--148, 1990.
• 11: Steven M. Burns , Henrik Hulgaard , Tod Amon , Gaetano Borriello, An Algorithm for Exact Bounds on the Time Separation of Events in Concurrent Systems, IEEE Transactions on Computers, v.44 n.11, p.1306-1317, November 1995 [doi>10.1109/12.475126]
• 12: Anoop Iyer , Diana Marculescu, Power and performance evaluation of globally asynchronous locally synchronous processors, Proceedings of the 29th annual international symposium on Computer architecture, p.158, May 25-29, 2002, Anchorage, Alaska
• 13: G. Kahn. The semantics of a simple language for parallel programming. In Information Processing 74: Proceedings of IFIP Congress 74, pages 471--475, Stockholm, Sweden, Aug. 1974. North-Holland.
• 14: Prabhakar Kudva , Ganesh Gopalakrishnan , Erik Brunvand , Venkatesh Akella, Performance Analysis and Optimization of Asynchronous Circuits, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.221-224, October 10-12, 1994
• 15: E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235--1245, Sept. 1987.
• 16: Robert Mullins , George Taylor , Peter Robinson , Simon Moore, Point to Point GALS Interconnect, Proceedings of the 8th International Symposium on Asynchronus Circuits and Systems, p.69, April 08-11, 2002
• 17: P. B. K. Pang , M. R. Greenstreet, Self-Timed Meshes Are Faster Than Synchronous, Proceedings of the 3rd International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.30, April 07-10, 1997
• 18: Gill A. Pratt , John Nguyen, Distributed Synchronous Clocking, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.314-328, March 1995 [doi>10.1109/71.372779]
• 19: Shai Rotem , Ken Stevens , Charles Dike , Marly Roncken , Boris Agapiev , Ran Ginosar , Rakefet Kol , Peter Beerel , Chris Myers , Kenneth Yun, RAPPID: An Asynchronous Instruction Length Decoder, Proceedings of the 5th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.60, April 19-21, 1999
• 20: I. E. Sutherland, Micropipelines, Communications of the ACM, v.32 n.6, p.720-738, June 1989 [doi>10.1145/63526.63532]
• 21: Sunan Tugsinavisut , Youpyo Hong , Daewook Kim , Kyeounsoo Kim , Peter A. Beerel, Efficient asynchronous bundled-data pipelines for DCT matrix-vector multiplication, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.4, p.448-461, April 2005 [doi>10.1109/TVLSI.2004.842908]
• 22: Elizabeth Anne Walkup, Optimization of linear max-plus systems with application to timing analysis, University of Washington, Seattle, WA, 1996
• 23: Aiguo Xie , Peter A. Beerel, Symbolic Techniques for Performance Analysis of Timed Systems Based on Average Time Separation of Events, Proceedings of the 3rd International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.64, April 07-10, 1997
• 24: Aiguo Xie , Sangyun Kim , Peter A. Beerel, Bounding Average Time Separations of Events in Stochastic Timed Petri Nets with Choice, Proceedings of the 5th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.94, April 19-21, 1999
• 25: Kenneth Y. Yun , Ayoob E. Dooply , Julio Arceo , Peter A. Beerel , Vida Vakilotojar, The Design and Verification of A High-Performance Low-Control-Overhead Asynchronous Differential Equation Solver, Proceedings of the 3rd International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.140, April 07-10, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Performance

Keywords:
asynchronous, marked graphs, performance, periodic, petrinets