Efficient longest executable path search for programs with complex flows and pipeline effects

ABSTRACT

Current development tools for embedded real-time systems do not efficiently support the timing aspect. The most important timing parameter for scheduling and system analysis is the Worst-Case Execution Time (WCET) of a program.This paper presents a fast and effective WCET calculation method that takes account of low-level machine aspects like pipelining and caches, and high-level program flow like loops and infeasible paths. The method is more efficient than previous path-based approaches, and can easily handle complex programs. By separating the low-level from the high-level analysis, the method is easy to retarget.Experiments confirm that speed does not sacrifice precision, and that programs with extreme numbers of potential execution paths can be analyzed quickly.

REFERENCES

• 1: L. Casparsson,A.Rajnak,K.Tindell,and P.Malmberg.Volcano -A Revolution in On-Board Communications.Volvo Technology Report ,1:9 -19, 1998.
• 2: R.Chapman.Program Timing Analysis.Dependable Computing System Centre,University of York, England,May 1994.
• 3: R.Chapman,A.Burns,and A.Wellings.Integrated Program Proof and Worst-Case Timing Analysis of SPARK Ada.In Proc.ACM SIGPLAN Workshop on Languages,Compilers and Tools for Real-Time Systems (LCT-RTS '94),1994.
• 4: 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]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: NEC Corporation.V850E/MS1 32/16-bit Single Chip Microcontroller:Architecture ,3rd edition,January 1999.Document no.U12197EJ3V0UM00.
• 7: Jakob Engblom , Andreas Ermedahl, Pipeline Timing Analysis Using a Trace-Driven Simulator, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.88, December 13-15, 1999
• 8: J.Engblom and A.Ermedahl.Modeling Complex Flow for Worst-Case Execution Time Analysis.In Proc.21th IEEE Real-Time Systems Symposium (RTSS '00),November 2000.
• 9: J.Engblom,A.Ermedahl,M.Sjodin,J.Gustafsson, and H.Hansson.Worst-Case Execution-Time Analysis for Embedded Real-Time Systems.Software Tools for Technology Transfer ,2001.Accepted for publication.
• 10: Andreas Ermedahl , Jan Gustafsson, Deriving Annotations for Tight Calculation of Execution Time, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.1298-1307, August 26-29, 1997
• 11: C.Ferdinand,F.Martin,and R.Wilhelm.Applying Compiler Techniques to Cache Behavior Prediction.In Proc.ACM SIGPLAN Workshop on Languages, Compilers and Tools for Real-Time Systems (LCT-RTS '97),1997.
• 12: J.Ganssle.Really Real-Time Systems.In Proceedings of the Embedded Systems Conference San Fransisco (ESC SF)2001 ,April 2001.
• 13: T.R.Halfhill.Embedded Market Break New Ground.Microprocessor Report,January 17 ,2000.
• 14: Christopher A. Healy , Robert D. Arnold , Frank Mueller , Marion G. Harmon , David B. Walley, Bounding Pipeline and Instruction Cache Performance, IEEE Transactions on Computers, v.48 n.1, p.53-70, January 1999 [doi>10.1109/12.743411]
• 15: Christopher Healy , David Whalley, Tighter Timing Predictions by Automatic Detection and Exploitation of Value-Dependent Constraints, Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium, p.79, June 02-04, 1999
• 16: IAR Systems WWW homepage.URL: http://www.iar.com
• 17: 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
• 18: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.456-461, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217570]
• 19: Sung-Soo Lim , Young Hyun Bae , Gyu Tae Jang , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Heonshik Shin , Kunsoo Park , Soo-Mook Moon , Chong Sang Kim, An Accurate Worst Case Timing Analysis for RISC Processors, IEEE Transactions on Software Engineering, v.21 n.7, p.593-604, July 1995 [doi>10.1109/32.392980]
• 20: S.-S. Lim , J. H. Han , J. Kim , S. L. Min, A Worst Case Timing Analysis Technique for Multiple-Issue Machines, Proceedings of the IEEE Real-Time Systems Symposium, p.334, December 02-04, 1998
• 21: Thomas Lundqvist , Per Stenström, Integrating Path and Timing Analysis Using Instruction-Level Simulation Techniques, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.1-15, June 01, 1998
• 22: E.Martins and J.Santos.A New Shortest Paths Ranking Algorithm.Investigacao Operational , 20(1):47 -62,2000.
• 23: F.M~ller.Timing Predictions for Multi-Level Caches. In Proc.ACM SIGPLAN Workshop on Languages, Compilers and Tools for Real-Time Systems (LCT-RTS '97),pages 29 -36,Jun 1997.
• 24: G.Ottosson and M.Sj~din.Worst-Case Execution Time Analysis for Modern Hardware Architectures.In Proc.ACM SIGPLAN Workshop on Languages, Compilers and Tools for Real-Time Systems (LCT-RTS '97),June 1997.
• 25: Chang Yun Park, Predicting program execution times by analyzing static and dynamic program paths, Real-Time Systems, v.5 n.1, p.31-62, March 1993 [doi>10.1007/BF01088696]
• 26: Stefan M. Petters , Georg Färber, Making Worst Case Execution Time Analysis for Hard Real-Time Tasks on State of the Art Processors Feasible, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.442, December 13-15, 1999
• 27: 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]
• 28: P.Puschner and A.Schedl.Computing Maximum TaskExecution Times with Linear Programming Techniques.Technical report,Technische Universit~t, Institut fur Technische Informatik,Wien,April 1995.
• 29: Jörn Schneider , Christian Ferdinand, Pipeline behavior prediction for superscalar processors by abstract interpretation, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.35-44, May 05-05, 1999, Atlanta, Georgia, United States
• 30: Friedhelm Stappert , Peter Altenbernd, Complete worst-case execution time analysis of straight-line hard real-time programs, Journal of Systems Architecture: the EUROMICRO Journal, v.46 n.4, p.339-355, Feb. 2000 [doi>10.1016/S1383-7621(99)00010-7]
• 31: F.Stappert,A.Ermedahl,and J.Engblom.E .cient Longest Executable Path Search for Programs with Complex Flows and Pipeline E .ects.Technical Report 2001-012,Dept.of Information Technology,Uppsala University,2001.
• 32: IAR Systems.V850 C/EC++Compiler Programming Guide ,1st edition,January 1999.
• 33: Randall T. White , Christopher A. Healy , David B. Whalley , Frank Mueller , Marion G. Harmon, Timing Analysis for Data Caches and Set-Associative Caches, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.192, June 09-11, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance

Keywords:
WCET, embedded systems, hard real-time, path search, pipeline timing, program flow