臺灣博碩士論文加值系統

在這篇論文中，我們介紹了兩個在堆疊快取（Stack Cache）大小固定的爪哇處理器（Java Processor）上針對堆疊框架（Stack Frame）配置的 Bytecode 最佳化技術。我們實驗平台的硬體架構基本上是一顆堆疊快取大小固定的爪哇處理器，而且這顆處理器必須直接在堆疊快取上實作 JVM 的堆疊框架配置機制，以及提供堆疊搬進（Fill）與搬出（Spill）的機制。爪哇處理器具有快速運算的堆疊指令機制來加快程式執行速度，然而因為成本與處理器面積的關係，硬體的堆疊快取都有大小的限制。在執行爪哇程式的時候，會在記憶體中配置一個共用區塊來作為壘堆（Heap），此壘堆區塊在執行爪哇程式時是所有執行程式一起共用的，而且主要用來儲存爪哇程式中的實體物件（Instance Object）及矩陣（Array）。而當程式執行到某一個函式（Method）的時候，處理器會在硬體堆疊快取上配置適當連續的空間來給該函式使用，在堆疊上的這段連續空間我們稱之為堆疊框架（Stack Frame）。堆疊框架包含該函式的參數（Argument）與區域變數（Local Variable）、框架狀態（Frame State）以及運算用堆疊區域（Operand Stack）。而當函式所需求的堆疊框架如果大於處理器可以在堆疊快取上配置的大小時，則爪哇處理器將另外付出效能損失（Performance Penalty）來解決這個問題。
首先，我們提出反轉成物件（Reverse Object-unfolding）技術來解決在爪哇處理器中單一行程（Intra-procedural）呼叫的堆疊框架配置問題。針對單一行程呼叫的配置問題，我們的解決方案注重在堆疊框架中區域變數的配置。將原本配置在堆疊框架中的區域變數轉變成配置在壘堆記憶體中的物件變數，減少區域變數的個數，相對地減少堆疊框架的大小，使得處理器可以在堆疊快取上配置出適當的空間。接著，我們延伸這種堆疊配置架構來處理跨行程（Inter-procedural）呼叫的堆疊框架配置問題，並且提出一個演算法（Heuristic Algorithm）來解決跨行程呼叫的堆疊配置問題。我們的解決方式注重在減少記憶體存取以及堆疊般進（Fill）與搬出（Spill）的次數。最後，我們利用工研院（ITRI）的爪哇處理器與 Kaffe VM 模擬器（Simulator）來進行實驗，並且提出有關單一行程呼叫與跨行程呼叫的實驗數據。由實驗數據可以看出，我們所提出的兩種方案可以有效地解決在爪哇處理器上的堆疊框架配置問題。

In this thesis, we describe two techniques to optimize hardware stack machine performances on Java environments. Our hardware model basically is a Java processor with a fixed-size stack cache, which directly implements the method frame activation allocations of a software Java virtual machine (JVM). In the first category, we present a technique to solve the problem about the stack allocations for intra-procedural methods in the Java processor. We put emphasis on the issue with the local variable allocation of the method frame. A structure or object unfolding technique can be used to transform heap accesses into stack accesses. The composite object in Java is accessed via heap in memory, while object unfolding transforms heap access to scalar and stack references. For Java processors with a fixed-size stack cache, unlimited employment of structure unfolding techniques however will result in the size of local variables excelling the size of the stack cache. Thus it will reduce the performance gains. For example, ITRI-made Java processor experiences performance penalty in this scenario. To solve this problem, we propose a mechanism, reverse object-unfolding, to report an allocation scheme for a given size of the stack allocation according to our cost model. In the second category of this problem, we also extend our framework for stack allocations to deal with inter-procedural cases. We model this problem into equations and propose a heuristic algorithm based on the domain decomposition of the call graphs of a program to solve the stack allocation problems for inter-procedural cases. Our solution deals with the reduction of both memory references and stack flushes.
Our experiment is performed on the ITRI-made Java processor architecture and Kaffe VM simulator. The ITRI-made Java processor is with a fixed-size stack cache and directly allocates the method frames on the stack cache. We report experimental results and profiling data for both intra-procedural and inter-procedural cases. The experiments indicate our proposed methods are promising in speedup Java programs on the Java processor with a fixed-size stack cache.

Acknowledgements i
Abstract ii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Approaches . . . . . . . . . . . . . . . . . . . . . . . 3
2 Machine Architectures 6
3 Reverse Object-unfolding 10
3.1 Weight Assignments to Local Objects . . . . . . . . . . 11
3.1.1 The Kinds of Operations Performed . . . . . . . . . . 12
3.1.2 Frequency and Weight Cost . . . . . . . . . . . . . . 13
3.1.3 Reorder Local Variables . . . . . . . . . . . . . . . 14
3.2 Transformation Techniques . . . . . . . . . . . . . . . 15
4 Inter-procedural Stack Cache Optimization 19
4.1 Cost Model for an Individual Procedure . . . . . . . . . 19
4.2 Optimal Solutions for Inter-procedural Environments . . 20
4.3 Heuristic Algorithms for Inter-procedural Environments . 22
5 Experiments and Discussions 25
5.1 The Modification of Kaffe VM . . . . . . . . . . . . . . 26
5.2 Experimental Results . . . . . . . . . . . . . . . . . . 27
5.2.1 Intra-procedural Case . . . . . . . . . . . . . . . . 28
5.2.2 Inter-procedural Case . . . . . . . . . . . . . . . . 30
6 Related Work and Conclusion 39
Bibliography 41

[1] Ana Azevedo, Alex Nicolau, and Joe Hummel, "Java Annotation-Aware Just-In-Time (AJIT) Compilation System", ACM Java Grande Conference, June 12-14, 1999.
[2] Andreas Krall, Anton Ertl, and Michael Gschwind, "Java VM Implementation: Compilers versus Hardware", ACAC ''98, pp. 101-110.
[3] Andrew W. Appel, Modern Compiler Implementation in Java, Cambridge University Press, 1998.
[4] Alfred V. Aho, Ravi Sethi, Jerey D. Ullman, Compilers Principles, Techniques, and Tools, Addison-Wesley, 1985.
[5] Art J.C. Bik and Dennis B. Gannon, "A prototype bytecode parallelization tool", to appear in Concurrency, Practice and Experience.
[6] Bill Venners, Inside the Java Virtual Machine, Second Edition, McGraw-Hill, 1999.
[7] Cheng-Hsueh A. Hsieh, John C. Gyllenhaal, and Wen-mei W. Hwu, "Java bytecode to native code translation: the caffeine prototype and preliminary results", Proceedings of the 29th annual IEEE/ACM international symposium on Microarchitecture, December 2-4, 1996, pp. 90-99.
[8] D. Viswanathan and S. Liang, "Java Virtual Machine Profiler Interface", IBM System Journal, 39(1), 2000, pp. 82-95.
[9] J. L. Bruno and T. Lassagne, "The Generation of Optimal Code for Stack Machines", Journal of the ACM 22:3, 1975, pp. 382-396.
[10] J. M. Bull, L. A. Smith, M. D. Westhead, D. S. Henty and R. A. Davey, "A methodology for Benchmarking Java Grande Applications", ACM Java Grande Conference, June 12-14, 1999.
[11] Jack J. Dongarra, Linpack Benchmark - Java Version, this package is made available at http://www.netlib.org/benchmark/linpackjava/.
[12] James Gosling, Bill Joy, and Guy Steele, The Java Language Specification, Addison-Wesley, 1996.
[13] JOIE: The Java Object Instrumentation Environment, this package is made available at http://www.cs.duke.edu/ari/joie/.
[14] Jon Meyer and Troy Downing, Java Virtual Machine, O''Reilly, 1997.
[15] Jonathan C. Hardwick and Jay Sipelstein, "Java as an Intermediate Language", Technical Report CMU-CS-96-161, School of Computer Science, Carnegie Mellon University, 1996.
[16] Julian Dolby and Andrew A. Chien, "An Evaluation of Object Inline Allocation Techniques", in the 13th Annual Conference on Object-Oriented Systems, Languages and Applications (OOPSLA), 1998.
[17] Kazuaki Ishizaki, Motohiro Kawahito, Toshiaki Yasue, Mikio Takeuchi, Takeshi Ogasawara, Toshio Suganuma, Tamiya Onodera, Hideaki Komatsu, and Toshio Nakatani, "Design, Implementation, and Evaluation of Optimizations in a Just-in-Time Compiler", ACM Java Grande Conference, June 12-14, 1999.
[18] Ken kennedy and Z. Budimlic, "Optimizing Java: Theory and Practice", Concurrency, Practice and Experience, 9(6), 1997, pp. 445-463.
[19] Kemal Ebcioglu, Erik Altman, and Erdem Hokenek, "A Java ILP Machine Based on Fast Dynamic Compilation", IEEE Mascots International Workshop on Security and Efficiency Aspects of Java, IEEE Computer Society Press, January 9-10, 1997.
[20] Markus Dahm, "Byte Code Engineering with the JavaClass API", Technical Report B-17-98, Freie University Berlin, Institute for Information, 1999.
[21] Markus Dahm, JavaClass API, this package is made available at http://www.inf.fu-berlin.de/ dahm/JavaClass/index.html.
[22] Han Bok Lee and Benjamin G. Zorn, BIT: Bytecode Instrumenting Tool, this package is made available at http://www.cs.colorado.edu/ hanlee/BIT/index.html.
[23] Michal Cierniak and Wei Li, "Optimizing Java bytecodes", Concurrency, Practice and Experience, 9(6), 1997, pp. 427-444.
[24] Michal Cierniak and Wei Li, "Just-in-time optimizations for high-performance Java programs", to appear in Concurrency: Practice and Experience.
[25] Michael G. Burke, Jong-Deok Choi, Stephen Fink, David Grove, Michael Hind, Vivek Sarkar, Mauricio J. Serrano, V. C. Sreedhar, Harini Srinivasan and John Whaley, "The Jalapeno Dynamic Optimizing Compiler for Java", ACM Java Grande Conference, June 12-14, 1999.
[26] Nathaniel Nystrom, BLOAT: The Bytecode-Level Optimizer and Analysis Tool, this package is made available at http://www.cs.purdue.edu/homes/whitlock/bloat/.
[27] "picoJava-II Programmer''s Reference Manual", Sun Microsystems Inc., March 1999.
[28] Rong-Guey Chang, Cheng-Wei Chen, Tyng-Ruey Chuang, and Jenq Kuen Lee, "Towards automatic supports of parallel sparse computation in Java with continuous compilation", Concurrency: Practice and Experience, 9(11):1101{1111, November 1997.
[29] Steven S. Muchnick, Advanced Compiler Design Implementation, Morgan Kaufmann Publishers, 1997.
[30] Sun Microsystems Inc., Java HotSpot Server VM, this package is made available at http://www.javasoft.com/products/hotspot/index.html.
[31] T. Suganuma, T. Ogasawara, M. Takeuchi, T. Yasue, M. Kawahito, K. Ishizaki, H. Komatsu, and T.Nakatani, "Overview of the IBM Java Just-in-Time Compiler", IBM System Journal, 39(1), 2000, pp. 175-193.
[32] Tim Lindholm and Frank Yellin, The Java Virtual Machine Specification, Addison-Wesley, 1997.
[33] Tim Lindholm and Frank Yellin, The Java Virtual Machine Specification, Second Edition, Addison-Wesley, 1999.
[34] Transvirtual Technologies, Inc., Kaffe Open VM Desktop Edition, this package is made available at http://www.kaffe.org.
[35] Trishul M. Chilimbi, B. Davidson, J. Larus, "Cache-conscious structure definition", PLDI ''99, May 1-4, 1999.
[36] "User Manuals for Java CPU", Technical Report, CCL, Industrial Technology and Research Institute, Taiwan, 1999.