A time-predictable execution mode for superscalar pipelines with instruction prescheduling

ABSTRACT

The time predictability of the components of a real-time system is required whenever it must be guaranteed that deadlines will be met. Research on techniques to evaluate the Worst-Case Execution Time (WCET) of programs has received much attention these last years but current high-performance processors prove to be hard to model both safely and tightly. We acknowledge the difficulty of taking into account more and more dynamic mechanisms within static analysis and this motivates our approach that consists in making the processor fit WCET estimation techniques. We focus on out-of-order superscalar pipelines and we propose to regulate the instruction flow so that subsequent basic blocks execute independently one of each other. This would allow any WCET estimation tool to limit the measurement to individual basic blocks.

REFERENCES

• 1: Martin Alt , Christian Ferdinand , Florian Martin , Reinhard Wilhelm, Cache Behavior Prediction by Abstract Interpretation, Proceedings of the Third International Symposium on Static Analysis, p.52-66, September 24-26, 1996
• 2: Aravindh Anantaraman , Kiran Seth , Kaustubh Patil , Eric Rotenberg , Frank Mueller, Virtual simple architecture (VISA): exceeding the complexity limit in safe real-time systems, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 3: Oren Avissar , Rajeev Barua , Dave Stewart, Heterogeneous memory management for embedded systems, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502223]
• 4: M. Berkelaar, "lp_solve: (Mixed Integer) Linear Programming Problem Solver", 2003. (ftp://ftp.es.ele.tue.nl/pub/lp_solve)
• 5: Ramon Canal , Antonio González, A low-complexity issue logic, Proceedings of the 14th international conference on Supercomputing, p.327-335, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335263]
• 6: Antoine Colin , Isabelle Puaut, Worst Case Execution Time Analysis for a Processor withBranch Prediction, Real-Time Systems, v.18 n.2-3, p.249-274, May 2000 [doi>10.1023/A:1008149332687]
• 7: M. Delvai, W. Huber, P. Puschner, A. Steininger, "Processor Support for Temporal Predictability -- The SPEAR Design Example", 15th Euromicro Conference on Real-Time Systems, 2003.
• 8: J. Engblom, A. Ermedahl, M. Sjödin, J. Gustafsson, H. Hansson, "Towards Industry-Strength Worst-Case Execution Time Analysis", Technical Report ASTEC 99/02, 1999.
• 9: J. Engblom, "Processor Pipelines and Static Worst-Case Execution Time Analysis", PhD thesis, University of Uppsala, 2002.
• 10: Jakob Engblom, Analysis of the Execution Time Unpredictability caused by Dynamic Branch Prediction, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.152, May 27-30, 2003
• 11: M. Harmon, T. Baker, D. Whalley, "A Retargetable Technique for Predicting Execution Time", Real Time Systems Symposium, 1992.
• 12: R. Heckmann, M. Langenbach, S. Thesing, R. Wilhelm "The Influence of Processor Architecture on the Design and the Results of WCET tools", Proceedings of the IEEE, vol.9, n®7, 2003.
• 13: Sung-Kwan Kim , Sang Lyul Min , Rhan Ha, Efficient worst case timing analysis of data caching, Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96), p.230, June 10-12, 1996
• 14: S.-S. Lim, Y. Bae, G. Jang, B.-D. Rhee, S. Min, C. Park, H. Shin, C. Kim, "An Accurate Worst Case Timing Analysis for RISC Processors", Real-Time Systems Symposium, 1994.
• 15: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, ACM SIGPLAN Notices, v.30 n.11, p.88-98, Nov. 1995
• 16: S.-S. Lim, S. Min, M. Lee, C. Park, H. Shin, C. S. Kim, "An Accurate Instruction Cache Analysis Technique for Real-Time Systems", Workshop on Architectures for Real-Time Applications, 1994.
• 17: Xianfeng Li , Abhik Roychoudhury , Tulika Mitra, Modeling Out-of-Order Processors for Software Timing Analysis, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.92-103, December 05-08, 2004 [doi>10.1109/REAL.2004.33]
• 18: Thomas Lundqvist , Per Stenström, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999 [doi>10.1023/A:1008138407139]
• 19: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 20: Marti-Campoy, A. Ivars, J. Busquets-Martaix, "Static Use of Locking Caches in Multitask Preemptive Real-Time Systems", Real-Time Embedded Systems Workshop, 2001.
• 21: Srilatha Manne , Artur Klauser , Dirk Grunwald, Pipeline gating: speculation control for energy reduction, Proceedings of the 25th annual international symposium on Computer architecture, p.132-141, June 27-July 02, 1998, Barcelona, Spain
• 22: T. Mitra, A. Roychoudhury, "A Framework to Model Branch Prediction for WCET Analysis", 2nd Workshop on WCET Analysis, 2002.
• 23: Frank Mueller, Timing Analysis for Instruction Caches, Real-Time Systems, v.18 n.2-3, p.217-247, May 2000 [doi>10.1023/A:1008145215849]
• 24: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 25: P. Puschner , Ch. Koza, Calculating the maximum, execution time of real-time programs, Real-Time Systems, v.1 n.2, p.159-176, Sep. 1989 [doi>10.1007/BF00571421]
• 26: C.Rochange, P. Sainrat, "Dissecting Execution Traces to Understand Long Timing Effects", Technical Report IRIT?2005-6-R, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Measurement, Performance

Keywords:
WCET, pipeline, processor architecture, real-time