Global critical path: a tool for system-level timing analysis

ABSTRACT

An effective method for focusing optimization effort on the most important parts of a design is to examine those elements on the critical path. Traditionally, the critical path is defined at the RTL level, as the longest path in the combinational logic between clocked registers. In this paper, we present a system-level timing analysis technique to define the concept of a Global Critical Path (GCP), for predicting system-level performance. We show how the GCP can be used as a theoretical and practical tool for understanding, summarizing and optimizing the behavior of highly concurrent self-timed circuits. We formally define the GCP and show how it can be constructed using a discrete event model and hardware profiling techniques. The GCP provides valuable insight into the control-path behavior of circuits and in finding system-level bottlenecks. We have incorporated the GCP construction and analysis framework into a high-level synthesis and simulation toolchain, thus enabling complete automation in modeling, analysis and optimization.

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: Brian Fields , Shai Rubin , Rastislav Bodík, Focusing processor policies via critical-path prediction, ACM SIGARCH Computer Architecture News, v.29 n.2, p.74-85, May 2001
• 5: 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]
• 6: H. Hulgaard and T. Amon. Symbolic timing analysis of asynchronous systems. IEEE Transactions on Computer Aided Design of Int. Circuits and Systems, 19(10): 1093--1104, October 2000.
• 7: 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
• 8: Scott McFarling, Reality-based optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 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: 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]
• 11: I. E. Sutherland, Micropipelines, Communications of the ACM, v.32 n.6, p.720-738, June 1989 [doi>10.1145/63526.63532]
• 12: G. Venkataramani, T. Chelcea, et al. Modeling the global critical path in concurrent systems. Technical Report CMU-CS-06-144, Carnegie Mellon University, Aug. 2006.
• 13: 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]
• 14: 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

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:
global critical path, hardware profiling, system modeling