臺灣博碩士論文加值系統

這篇論文展示了一個針對ARM處理器可以獲得確切最差執行時間的工具。 這個工具是一個介於ARM的GCC編譯器和SWEET最差執行時間分析器之間的介面。 SWEET是一個開放原碼的靜態分析器，可獲得程式確切的最差執行時間上限。
在即時系統中，程式的最差執行時間是一個重要的計量，因為工作排程器必須決定分配多少時間給各個程序。 真實的最差執行時間值是有用的，但不幸的是它難以取得。因此靜態程式分析已經成為取得最差執行時間上限的方法，它是透過完整程式中各個獨立片段的保守執行時間近似值來取得最差執行時間上限的方法。 SWEET是靜態分析器的其中一個。
我們的工具工作在ARM-GCC的內部，取出所有SWEET需要的程式特性資訊。 然後這個工具包裝這些資訊成為SWEET的ALF格式。 這個工具已經被測試過且對任何我們已經測試的輸入來源可以正確的運作(包含所有從WCET BENCHMARK SUITE[1] 得到的34個標準檢查程式)

This thesis presents a tool for obtaining worst-case execution time (WCET) guarantees for ARM processors. This tool is an interface between ARM’s GCC compiler and the SWEET WCET analyzer. SWEET is an open-source static analyzer that derives a guaranteed upper bound on the WCET of a program.
The WCET of a program is an important metric in real-time systems. The task scheduler must decide how much time to allot for each process; if the allotted time exceeds the WCET, the process can be guaranteed to always finish in time. Although the WCET value is therefore useful, it is difficult to find. But, for the purpose of guaranteeing that a process finishes on time, an upper bound on the WCET suffices. Static program analysis has been proposed as a method to derive such an upper-bound on the WCET, by means of conservatively approximating the runtime of the individual parts of a complete program. SWEET is one such static analyzer.
Our tool works inside of ARM-GCC, extracting all of the information that SWEET needs about the program’s behavior. Our tool then packages the information into the SWEET’s ALF format. The tool has been tested and works correctly for every input source that we have tested (including all 34 benchmarks from the WCET BENCHMARK SUITE[1]).


This work was funded by Taiwan’s National Science Council, grant NSC 97-2218-E-110-003

摘要…...………….………………………………………………….. i
Abstract.............................................................................................. ii
Index.................................................................................................. iii
SECTION 1 INTRODUCTION………..................................................... 1

SECTION 2 RELATED WORK…........................................................... 6
2.1 STATIC ANALYSIS.................................................................... 6
2.1.1 THE FLOW ANALYSIS PHASE……………........................... 7
2.1.2 THE ARCHITECTURAL MODELING PHASE....................... 10
2.1.3 THE WCET CALCULATION PHASE................................... 12
2.1.4 THE CHOICES MADE BY THE SWEET ANALYZER’S PHASES.............................................................................................. 13
2.2 RELATED WORK IN INTERMEDIATE REPRESENTATIONS......... 15

SECTION 3 IMPLEMENTATION OF OUR CONVERTER............................ 19
3.1 The situation where GIMPLE has all the information needed for the ALF file.................................................................... 20
3.1.1 EXAMPLE............................................................................ 20
3.2 The situation where ALF requires more information than exists in GIMPLE............................................................................ 21
3.3 GCC modifications to produce the missing information that the ALF format requires.......................................................... 26
3.4 Problems that occur in special situations.......................... 28
3.5 Implementation of the GandALF converter...................... 32

SECTION 4 RESULTS.......................................................................... 34
References......................................................................................... 35
APPENDIX.......................................................................................... 38

[1] WCET benchmarks, Website: http://www.mrtc.mdh.se/projects/wcet/benchmarks.html
[2] The SWEdish Execution Time tool. Website: http://www.mrtc.mdh.se/projects/wcet/sweet.html
[3] T. Lundqvist and P. Stenström, “Integrating path and timing analysis using instruction-level simulation techniques”, in Proc. of the ACM SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems (LCTES), Montreal, Canada, June 1998.
[4] A. W. Appel, Modern Compiler Implementation in C. Press Syndicate of the University of Cambridge, ISBN 0-521-58390-X, 1999.
[5] P. Cousot and R. Cousot, “Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints”, in Conference Record of the 4th Annual ACM SIPLAN-SIGACT Symposium on Principles of Programming Languages, pp 238-252, Los Angeles, California, January 1977.
[6] C. Healy, M Sjödin, V. Rustagi, and D. Whalley, “Bounding loop iterations for timing analysis”, in Proc. of the 4th IEEE Real-Time Technology and Applications Symposium. Denver, Colorado, June 1998.
[7] T. Cheatham, G. Holloway, and J. Townley, “Symbolic evaluation and the analysis of programs”, IEEE Transactions on Software Engineering 5(4) pp. 403-417, 1979.
[8] J. Gustafsson, B. Lisper, R. Kirner, and P. Puschner, “Code analysis for temporal predictability”, Real-Time Systems, volume 32, issue 3, p. 253-277 Spring-Verlag March 2006.
[9] H. Theiling and C. Ferdinand, “Combining abstract interpretation and ILP for microarchitecture modeling and program path analysis”, in Proc. of the 19th IEEE Real-Time Systems Symposium. Madrid, Spain, December 1998.
[10] J. Gustafsson and A. Ermedahl, “Automatic derivation of path and loop annotations in object-oriented real-time programs”, Parallel and Distributed Computing Practices. 1(2), June 1998.
[11] B. Lisper, “Fully automatic, parametric worst-case execution time analysis”, in Proc. of the 3rd International Workshop on WCET Analysis (WCET), Porto, Portugal, July 2003.
[12] C. Healy, M. Sjödin, V. Rustagi, and D. Whalley, “Supporting timing analysis by automatic bounding of loop iterations”, Real-Time Systems, volume 18, issue 2, p. 121-148, May 2000.
[13] C. Healy, R. van Engelen, and D. Whalley, “A general approach for tight timing predictions on non-rectangular loops”, in Proc. of the 5th IEEE Real-Time Technology and Applications Symp., Vancouver, Canada, June 1999.
[14] C. Healy and D. Whalley, “Tighter timing predictions by automatic detection and exploitation of value-dependent constraints”, in Proc. of the 5th IEEE Real-Time Technology and Applications Symposium, Vancouver, Canada, June 199.
[15] M. Corti and T. Gross, “Approximation of the worst-case execution time using structural analysis”, in Proc. of the Fourth ACM International Conference on Embedded Software(EMSOFT04), Pisa, Italy, September 2004.
[16] J. Engblom, A. Ermedahl, M. Sjödin, J. Gustafsson, and H. Hansson, “Worst-case execution time analysis for embedded real-time systems”, International Journal on Software Tools for Technology Transfer, volume 4, p 437-455, 2003.
[17] A. Coen-Porisini, G. Denaro, C. Ghezzi, and M. Pezzè, “Using symbolic execution for verifying safety critical systems”, in 8th European Software Engineering Conference, Vienna, Austria, September 2001.
[18] G. Bernat and A. Burns, “An approach to symbolic worst-case execution time analysis”, in Proc. of the 25th IFAC Workshop on Real-Time Programming, Palma, Spain. May 2000.
[19] J. Blieberger, “Data-flow frame works for worst case execution time analysis”, Real-Time Systems, volume 22 p.183-227. 2002.
[20] D. Kebbal and P. Sainrat, “Combining symbolic execution and path enumeration in worst-case execution time analysis”, in Proc. of the 6th International Workshop on WCET Analysis (WCET), Dresden, Germany, July 4, 2006.
[21] G. Bernat, A. Colin, S. M. Petters, “WCET analysis of probabilistic hard real-time system”, in Proc. Of the 23rd Real-Time Systems Symposium(RTSS), Austin, Texas. Dec2002.
[22] S. Petters and G.. Färber, “Making worst case execution time analysis for hard real-time tasks on the art processors feasible”, in Proc. of the 6th Conference on Real-Time Computing Systems and Applications (RTCSA ''99), Hong Kong, December 1999.
[23] I. Wenzel, R. Kirner, B. Rieder, and P. Puschner, “Measurement-based worst-case execution time analysis”, in Proc. of the 3rd workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS), Seattle, Washington, USA, May 2005.
[24] R. Kirner, I. Wenzel, B. Rieder, and P. Puschner, “Using Measurements as a complement to static worst-case execution time analysis”, Intelligent Systems at the Service of Mankind, vol. 2, December 2005.
[25] R Heckmann, M Langenbach, S Thesing, R Wilhelm, “The influence of processor architecture on the design and the results of WCET tools”, Proc. of the IEEE, 91(7):1038-1054. July, 2003.
[26] P. Puschner, “Is worst-case execution-time analysis a non-problem? – towards new software and hardware architectures”, in Proc. of the 2nd Euromicro International Workshop on WCET Analysis, Vienna, Austria. June 2002.
[27] P. Atannassov and P. Puschner, “Impact of DRAM refresh on the execution time of real-time tasks”, in Proc. of the IEEE International Workshop on Application of Reliable Computing and Communication, Seoul, Korea, p. 29-34, December 2001.
[28] R. Emst and W. Ye, “Embedded program timing analysis based on path clustering and architecture classification”, in Proc. of the Int’l Con. on Computer-Aided Design (ICCAD), San Jose, California, November 1997.
[29] M. Lindgren, “Measurements and simulation based techniques for real-time systems analysis”, Licentiate Thesis, Uppsala University of Technology, Uppsala, Sweden, 2000.
[30] C. Park and A. Shaw, “Experiments with a program timing tool based on source-level timing schema”, IEEE Transactions on Computers, vol. 24. pp. 48-57, May 1991.
[31] P. Puschner and C. Koza, “Calculating the maximum execution time of real-time programs”, Real-Time Systems, vol. 1, no. 2, pp 159-176, September 1989.
[32] S. M. Petters, A. Betts, and G. Bernat, “A new timing schema for WCET analysis”, in Proc. of the 4th International Workshop on Worst Case Execution Time Analysis, June 2004.
[33] C. Healy and D. Whalley, “Automatic detection and exploitation of branch constrains for timing analysis”, IEEE Transactions on Software Engineering, pp 28-35, 2002.
[34] F. Stappert, A. Ermedahl, and J. Engblom, “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 System (CASES), Atlanta, Georgia, USA, November 2001.
[35] M.Ji, J. Wang, S. Li, Z. Qu, “Automated WCET analysis based on program moders”, in Proc. of the 2006 international Workshop on Automation of Software Test, Shanghai, China, May 2006.
[36] C. Ferdinand, “Worst case execution time prediction by static program analysis”, in Proc. of the 18th International Parallel and Distributed Processing Symposium (IPDPS), Santa Fe, New Mexico, USA, April 2004.
[37] P. Puschner and V. Schedl, “A tool for the computation of the worst case task execution times”, in Proc. of the Euromicro Workshop on Real-Time Systems, Oulu, Finland, June 1993.
[38] J. Engblom and A. Ermedahl, “Modeling complex flows for worst case execution time analysis”, in Proc. of the 23rd Real-Time Systems Symposium(RTSS), Orlando, Florida, Nov 2000.
[39] Richard M. Stallman and the GCC Developer Community, “GNU Compiler Collection Internals”, GNU Technical Report, p.147-157, 2008.
[40] AndreasErmedahl, JanGustafsson, andBjörn Lisper, “ALF(ARTIST2 Language for Flow Analysis) Specification”, MRTC Internal Report, 2009.
[41] GNU ARM toolchain, Website: http://www.gnuarm.com/
[42] Jobn R. Levine, Tony Mason, and Doug Brown, “lex&yacc, Second edition”, O’REILLY, 2007.