Slack analysis in the system design loop

ABSTRACT

We present a system-level technique to analyze the impact of design optimizations on system-level timing dependencies. This technique enables us to speed up the design cycle by substituting, in the design the loop, the time-consuming simulation step with a fast timing update routine. As a result, we can significantly reduce the design time from on the order of hours/days to the order of seconds/minutes. The update algorithm is defined on the Transaction Level Model (TLM) and can be used by any design flow that invokes TLM-based optimizations. This algorithm has linear-time complexity in the program size and experimental results indicate that any loss of accuracy due to this technique is negligible (< ±1%); the benefit is a reduction in total design cycle time from several hours to a matter of seconds.

REFERENCES

• 1: 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]
• 2: Mihai Budiu , Girish Venkataramani , Tiberiu Chelcea , Seth Copen Goldstein, Spatial computation, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 3: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 4: Lukai Cai , Daniel Gajski, Transaction level modeling: an overview, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944651]
• 5: Ali Dasdan, Experimental analysis of the fastest optimum cycle ratio and mean algorithms, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.385-418, October 2004 [doi>10.1145/1027084.1027085]
• 6: Brian Fields , Rastislav Bodík , Mark D. Hill, Slack: maximizing performance under technological constraints, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 7: Stephen B. Furber , Paul Day, Four-phase micropipeline latch control circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.2, p.247-253, June 1996 [doi>10.1109/92.502196]
• 8: Kazuhito Ito , Keshab K. Parhi, Determining the minimum iteration period of an algorithm, Journal of VLSI Signal Processing Systems, v.11 n.3, p.229-244, Dec. 1995 [doi>10.1007/BF02107055]
• 9: K. S. Khouri, G. Lakshminarayana, et al. High-level synthesis of low-power control-flow intensive circuits. TCAD, 18(12):1715--1729, 1999.
• 10: Michael Kishinevsky , Jordi Cortadella , Alex Kondratyev, Asynchronous interface specification, analysis and synthesis, Proceedings of the 35th annual conference on Design automation, p.2-7, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277046]
• 11: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: 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]
• 13: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 14: Christian D. Nielsen , Michael Kishinevsky, Performance analysis based on timing simulation, Proceedings of the 31st annual conference on Design automation, p.70-76, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196281]
• 15: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 16: Frank Vahid , Tony Givargis, Platform Tuning for Embedded Systems Design, Computer, v.34 n.3, p.112-114, March 2001 [doi>10.1109/2.901171]
• 17: Girish Venkataramani , Seth Copen Goldstein, System-level timing analysis and optimizations for hardware compilation, Carnegie Mellon University, Pittsburgh, PA, 2007
• 18: Girish Venkataramani , Mihai Budiu , Tiberiu Chelcea , Seth C. Goldstein, Global critical path: a tool for system-level timing analysis, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278675]
• 19: Girish Venkataramani , Tiberiu Chelcea , Seth C. Goldstein, Heterogeneous Latch-Based Asynchronous Pipelines, Proceedings of the 2008 14th IEEE International Symposium on Asynchronous Circuits and Systems, p.83-92, April 07-10, 2008 [doi>10.1109/ASYNC.2008.21]
• 20: 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]
• 21: Girish Venkataramani , Seth C. Goldstein, Operation chaining asynchronous pipelined circuits, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 22: A. Yakovlev , L. Lavagno , A. L. Sangiovanni-Vincentelli, A unified signal transition graph model for asynchronous control circuit synthesis, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.104-111, December 1992, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Measurement, Performance

Keywords:
slack analysis, system design loop, timing update