Criticality: static profiling for real-time programs
Tóm tắt
With the increasing performance demand in real-time systems it becomes more and more important to provide feedback to programmers and software development tools on the performance-relevant code parts of a real-time program. So far, this information was limited to an estimation of the worst-case execution time (WCET) and its associated worst-case execution path (WCEP) only. However, both, the WCET and the WCEP, only provide partial information. Only code parts that are on one of the WCEPs are indicated to the programmer. No information is provided for all other code parts. To give a comprehensive view covering the entire code base, tools in the spirit of program profiling are required. This work proposes an efficient approach to compute worst-case timing information for all code parts of a program using a complementary metric, called criticality. Every statement of a program is assigned a criticality value, expressing how critical the code is with respect to the global WCET. This gives valuable information how close the worst execution path passing through a specific program part is to the global WCEP. We formally define the criticality metric and investigate some of its properties with respect to dominance in control-flow graphs. Exploiting some of those properties, we propose an algorithm that reduces the overhead of computing the metric to cover complete programs. We also investigate ways to efficiently find only those code parts whose criticality is above a given threshold. Experiments using well-established real-time benchmark programs show an interesting distribution of the criticality values, revealing considerable amounts of highly critical as well as uncritical code. The metric thus provides ideal information to programmers and software development tools to optimize the worst-case execution time of these programs.
Tài liệu tham khảo
Agrawal H (1994) Dominators, super blocks, and program coverage. In: Proc. of the symposium on principles of programming languages. ACM, New York, pp 25–34
Aho AV, Lam MS, Sethi R, Ullman JD (2006) Compilers: principles, techniques, and tools, 2nd edn. Addison-Wesley, Reading
Ball T, Eick SG (1996) Software visualization in the large. Computer 29:33–43
Ball T, Larus JR (1994) Optimally profiling and tracing programs. ACM Trans Program Lang Syst 16(4):1319–1360
Brandner F, Hepp S, Jordan A (2012) Static profiling of the worst-case in real-time programs. In: Proceedings of the international conference on real-time and network systems, RTNS ’12. ACM, New York, pp 101–110
Colombet Q, Brandner F, Darte A (2011) Studying optimal spilling in the light of ssa. In: Proceedings of the international conference on compilers, architectures and synthesis for embedded systems, CASES ’11. ACM, New York, pp 25–34
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press, Cambridge
Dvorak DL (2009) NASA study on flight software complexity. Technical excellence initiative. NASA Office of Chief Engineer
Georgiadis L, Tarjan RE (2004) Finding dominators revisited: extended abstract. In: Proceedings of the symposium on discrete algorithms, SODA ’04. Society for Industrial and Applied Mathematics, Philadelphia, pp 869–878
Graham SL, Kessler PB, Mckusick MK (1982) Gprof: a call graph execution profiler. In: Proc. of the symposium on compiler construction, CC ’82. ACM, New York, pp 120–126
Gustafsson J, Betts A, Ermedahl A, Lisper B (2010) The Mälardalen WCET benchmarks—past, present and future. In: Proc. of the workshop on worst-case execution time analysis, OCG, pp 137–147
Holsti N, Långbacka T, Saarinen S (2000) Using a worst-case execution-time tool for real-time verification of the DEBIE software. In: Proc. of the Data Systems in Aerospace Conference, ESA, p 307
Lemieux F, Salois M (2006) Visualization techniques for program comprehension a literature review. In: Proc. of the conference on new trends in software methodologies, tools and techniques (SoMeT ’06). IOS Press, Amsterdam, pp 22–47
Lengauer T, Tarjan RE (1979) A fast algorithm for finding dominators in a flowgraph. ACM Trans Program Lang Syst 1(1):121–141
Li YTS, Malik S (1995) Performance analysis of embedded software using implicit path enumeration. In: Proc. of the design automation conference, DAC ’95. ACM, New York, pp 456–461
Lokuciejewski P, Gedikli F, Marwedel P (2009) Accelerating WCET-driven optimizations by the invariant path paradigm—a case study of loop unswitching. In: Proc. of the workshop on software & compilers for embedded systems (SCOPES ’09), pp 11–20
Lupo C, Wilken KD (2006) Post register allocation spill code optimization. In: Proceedings of the international symposium on code generation and optimization, CGO ’06. IEEE, New York, pp 245–255
Nemer F, Cassé H, Sainrat P, Bahsoun JP, Michiel MD (2006) Papabench: A free real-time benchmark. In: Proc. of the Workshop on Worst-Case Execution Time Analysis, OCG, pp 63–68
Puschner PP, Schedl AV (1997) Computing maximum task execution times—a graph-based approach. Real-Time Syst 13(1):67–91
Samples AD (1991) Profile-driven compilation. PhD thesis, University of California at Berkeley
Stappert F, Ermedahl A, Engblom J (2001) Efficient longest executable path search for programs with complex flows and pipeline effects. In: Proc. of the conference on compilers, architecture, and synthesis for embedded systems. ACM, New York, pp 132–140
Tarjan RE (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146–160
Theiling H, Ferdinand C, Wilhelm R (2000) Fast and precise WCET prediction by separated cache and path analyses. Real-Time Syst 18(2/3):157–179
Wimmer C, Mössenböck H (2005) Optimized interval splitting in a linear scan register allocator. In: Proceedings of the international conference on virtual execution environments, VEE ’05. ACM, New York, pp 132–141