Performance estimation and slack matching for pipelined asynchronous architectures with choice

ABSTRACT

This paper presents a fast analytical method for estimating the throughput of pipelined asynchronous systems, and then applies that method to develop a fast solution to the problem of pipelining "slack matching." The approach targets systems with hierarchical topologies, which typically result when high-level (block structured) language specifications are compiled into data-driven circuit implementations. A significant contribution is that our approach is the first to efficiently handle architectures with choice (i.e., the presence of conditional computation constructs such if-then-else and conditional loops).

The key idea behind the fast speed of our analysis method is to exploit information about the hierarchy of a given block-structured system, thereby yielding a runtime that is linear in the number of pipeline stages. In contrast, existing approaches typically represent an entire system as a single Petri net or marked graph, and then apply Markov chain analysis or other state enumeration methods with costly runtimes.

Building upon our analysis approach, we introduce a novel solution to the problem of slack matching, i.e., determining optimal insertion of FIFO stages into a pipelined design to improve performance. We present both an optimal solution using an MILP formulation, and a fast heuristic algorithm that yielded optimal results for all of our examples.

REFERENCES

• 1: Narendra Shenoy, Retiming: theory and practice, Integration, the VLSI Journal, v.22 n.1-2, p.1-21, Aug. 1997 [doi>10.1016/S0167-9260(97)00002-3]
• 2: T. E. Williams, M. Horowitz, R. L. Alverson, and T. S. Yang, "A self-timed chip for division," in Advanced Research in VLSI, P. Losleben, Ed. MIT Press, 1987, pp. 75--95.
• 3: M. R. Greenstreet and K. Steiglitz, "Bubbles can make self-timed pipelines fast," Journal of VLSI Signal Processing, vol. 2, no. 3, pp. 139--148, Nov. 1990.
• 4: A. M. Lines, "Pipelined asynchronous circuits," Master's thesis, California Institute of Technology, 1998.
• 5: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 6: E. G. Mercer and C. J. Myers, "Stochastic cycle period analysis in timed circuits," in Proc. Int. Symp. on Circuits and Systems, 2000, pp. 172--175.
• 7: A. Xie and P. A. Beerel, "Performance analysis of asynchronous circuits and systems using stochastic timed Petri nets," in Hardware Design and Petri Nets, A. Yakovlev, L. Gomes, and L. Lavagno, Eds. Kluwer Academic Publishers, Mar. 2000, pp. 239--268.
• 8: 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
• 9: Peggy B. McGee , Steven M. Nowick , E. G. Coffman, Jr., Efficient performance analysis of asynchronous systems based on periodicity, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084892]
• 10: 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
• 11: 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
• 12: 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]
• 13: S. Chakraborty, K. Yun, and D. Dill, "Timing analysis of asynchronous systems using time separation of events," IEEE Trans. on Computer-Aided Design, vol. 18, no. 8, pp. 1061--1076, Aug. 1999.
• 14: Peggy B. McGee , Steven M. Nowick, An efficient algorithm for time separation of events in concurrent systems, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 15: Peter A. Beerel , Nam-Hoon Kim , Andrew Lines , Mike Davies, Slack Matching Asynchronous Designs, Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems, p.184, March 13-15, 2006 [doi>10.1109/ASYNC.2006.26]
• 16: Piyush Prakash , Alain J. Martin, Slack Matching Quasi Delay-Insensitive Circuits, Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems, p.195, March 13-15, 2006 [doi>10.1109/ASYNC.2006.27]
• 17: Girish Venkataramani , Seth C. Goldstein, Leveraging protocol knowledge in slack matching, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233650]
• 18: Ted Eugene Williams, Self-timed rings and their application to division, Stanford University, Stanford, CA, 1992
• 19: Gennette Gill , John Hansen , Montek Singh, Loop pipelining for high-throughput stream computation using self-timed rings, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233559]