Worst-case execution time driven method inlining for embedded Java processors

Abstract

Java Bytecode wird üblicherweise in einer Java Virtual Machine (JVM) auf einem Desktop PC ausgeführt. Meistens wird der Code von der JVM interpretiert oder mittels eines Just-In-Time (JIT) Compilers in Maschinencode übersetzt. Basierend auf Profiling-Informationen werden kritische Stellen zur Laufzeit bei Bedarf optimiert. Java Prozessoren wie der Java Optimized Processor (JOP) können hingegen Java Bytecode direkt ausführen ohne zusätzlich einen Interpreter oder JIT Compiler zu benötigen.<br />Die Worst-Case Execution Time (WCET) ist bei Echtzeitsystemen wichtiger als die Average-Case Execution Time (ACET). Falls die WCET eines Echtzeit-Prozesses zu hoch ist, werden Optimierungen während der Entwicklung benötigt um den Worst-Case Pfad im Programm zu optimieren und damit die WCET zu reduzieren.<br />In dieser Diplomarbeit wird gezeigt, wie eine Worst-Case Analyse (WCA) verwendet werden kann um einen Optimizer zu unterstützen. Des weiteren werden die Auswirkungen des Method Cache auf die Effizienz von Optimierungen betrachtet. Ein bestehendes WCET Analysetool wird verwendet um Optimierungen für JOP zu lenken. Als zentrale Optimierung wird Method Inlining verwendet, wobei versucht wird eine Verschlechterung der WCET durch höhere Cache-Miss Kosten zu vermeiden.<br />Ein Framework wurde erstellt um die Optimierungen und die Worst-Case Analyse auf den selben Daten arbeiten zu lassen, damit die WCA während der Optimierung mit geringen Overhead mehrfach durchgeführt werden kann.<br />Um die Auswirkungen der Optimierungen zu testen wurden mehrere Benchmark-Anwendungen optimiert und analysiert. Die WCET, die ACET und die Codegröße der optimierten Anwendungen wurden mit den nicht optimierten Versionen verglichen.<br />

Java bytecode is commonly executed by a Java virtual machine (JVM) on a desktop computer, which usually either interprets the code or employs a just-in-time (JIT) compiler to translate the code to native machine code. Profile-guided optimizations are used to speedup hotspots at runtime. In contrast to that, Java processors like the Java Optimized Processor (JOP) execute Java bytecode directly without the need for a JIT compiler or an interpreter.<br />For real-time applications the worst-case execution time (WCET) is more important than the average-case execution time (ACET). If the WCET of a real time task is too high, ahead-of-time optimization is required that focuses the worst-case execution path to reduce the WCET.<br />In this thesis, we show how the worst-case analysis (WCA) can be used to guide the optimizer and discuss the impact of a method cache on the performance of the optimizations. An existing WCET analysis tool is used to drive WCET oriented optimizations for the JOP processor.<br />The main optimization is inlining method calls to eliminate the invoke overhead, while trying to avoid increasing the overall WCET due to higher method cache miss penalties. A framework has been implemented which allows the optimizer and the WCA to work on the same data structures in memory so that the WCA can be invoked repeatedly during the optimizations with low overhead.<br />To test the impact of the optimizations, various benchmark applications have been optimized and analyzed, and the WCET, the ACET as well as the code size of the optimized applications are compared to their unoptimized version.