請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61045
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 廖世偉 | |
dc.contributor.author | Tzu-Hsiang Chien | en |
dc.contributor.author | 簡子翔 | zh_TW |
dc.date.accessioned | 2021-06-16T10:43:15Z | - |
dc.date.available | 2013-08-16 | |
dc.date.copyright | 2013-08-16 | |
dc.date.issued | 2013 | |
dc.date.submitted | 2013-08-13 | |
dc.identifier.citation | Bibliography
[1] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006. [2] B. Alpern, C. R. Attanasio, J. Barton, M. G. Burke, P. Cheng, J.-D. Choi, A. Cocchi, S. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. Shepherd, S. E. Smith, V. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeno virtual machine. IBM Systems Journal, 39(1):211–238, 2000. [3] C. S. Ananian and M. Rinard. Static single information form. Technical report, Master’s thesis, Massachussets Institute of Technology, 1999. [4] V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: a transparent dynamic optimization system. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, PLDI ’00, pages 1–12, New York, NY, USA, 2000. ACM. [5] R. Bodik. Gupta, and V. Sarkar. ABCD: Eliminating array bounds checks on demand. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, PLDI ’00, pages 321–333, New York, NY, USA, 2000. ACM. [6] D. Bornstein. Dalvik VM internals, 2008. https://sites.google.com/site/io/dalvik-vm-internals/. [7] B. Cheng and B. Buzbee. A JIT compiler for Android’s Dalvik VM, 2010. http://www.google.com/events/io/2010/sessions/jit-compiler-androids-dalvik-vm.html. [8] D. D. I. F. Committee et al. DWARF debugging information format version 4, 2010. [9] comScore/the Kelsey group. April 2013 u.s. smartphone subscriber market share. Press Release, June 2013. http://www.comscore.com/Insights/Press_Releases/2013/6/comScore_Reports_April_2013_U.S._Smartphone_Subscriber_Market_Share. [10] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991. [11] A. Gal, C. W. Probst, and M. Franz. HotpathVM: an effective JIT compiler for resource-constrained devices. In Proceedings of the 2nd international conference on Virtual execution environments, VEE ’06, pages 144–153, New York, NY, USA, 2006. ACM. [12] J. Gosling, B. Joy, G. Steele, and G. Bracha. Java Language Specification, Second Edition: The Java Series. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 2000. [13] C. Haubl and H. Mossenbock. Trace-based compilation for the Java HotSpot virtual machine. In Proceedings of the 9th International Conference on Principles and Practice of Programming in Java, PPPJ ’11, pages 129–138, New York, NY, USA, 2011. ACM. [14] J. L. Hennessy and D. A. Patterson. Computer Architecture, Fourth Edition: A Quantitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2006. [15] H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani. A trace-based java JIT compiler retrofitted from a method-based compiler. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO’11, pages 246–256, Washington, DC, USA, 2011. IEEE Computer Society. [16] K. Ishizaki, M. Kawahito, T. Yasue, M. Takeuchi, T. Ogasawara, T. Suganuma, T. Onodera, H. Komatsu, and T. Nakatani. Design, implementation, and evaluation of optimizations in a just-in-time compiler. In Proceedings of the ACM 1999 conference on Java Grande, JAVA ’99, pages 119–128, New York, NY, USA, 1999. ACM. [17] M. Kawahito, H. Komatsu, and T. Nakatani. Effective null pointer check elimination utilizing hardware trap. SIGPLAN Not., 35(11):139–149, Nov. 2000. [18] T. Kotzmann, C. Wimmer, H. Mossenbock, T. Rodriguez, K. Russell, and D. Cox. Design of the Java HotSpotTM client compiler for Java 6. ACM Trans. Archit. Code Optim., 5(1):7:1–7:32, May 2008. [19] T. Lindholm and F. Yellin. Java Virtual Machine Specification. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 1999. [20] H.-S. Oh, B.-J. Kim, H.-K. Choi, and S.-M. Moon. Evaluation of Android Dalvik virtual machine. In Proceedings of the 10th International Workshop on Java Technologies for Real-time and Embedded Systems, JTRES ’12, pages 115–124, New York, NY, USA, 2012. ACM. [21] I. Rogers, J. Zhao, and I. Watson. Boot image layout for Jikes RVM. 2008. [22] Y. Shi, K. Casey, M. A. Ertl, and D. Gregg. Virtual machine showdown: Stack versus registers. ACM Trans. Archit. Code Optim., 4(4):2:1–2:36, Jan. 2008. [23] R. Sol, C. Guillon, F. M. Q. a. Pereira, and M. A. S. Bigonha. Dynamic elimination of overflow tests in a trace compiler. In Proceedings of the 20th international conference on Compiler construction: part of the joint European conferences on theory and practice of software, CC’11/ETAPS’11, pages 2–21, Berlin, Heidelberg, 2011. Springer-Verlag. [24] D. Spinellis and G. Gousios. Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design. O’Reilly Media, Inc., 1st edition, 2009. [25] 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 Syst. J., 39(1):175–193, Jan. 2000. [26] T. Wurthinger, C. Wimmer, and H. Mossenbock. Array bounds check elimination for the Java HotSpotTM client compiler. In Proceedings of the 5th international symposium on Principles and practice of programming in Java, PPPJ ’07, pages 125–133, New York, NY, USA, 2007. ACM. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61045 | - |
dc.description.abstract | 本論文將會探討 Dalvik Tracing JIT 的特性,解釋為何現有的最佳化無法消除一些冗餘的 Null Pointer 檢查。
為解決此問題,本文提出一個以 SSA Renaming 為基礎的程式分析,用以消去這些冗餘檢查。對於「部分冗餘檢查 (Partial Redundant Check)」,本文亦善用 Tracing JIT 的特性,將迴圈內的檢查投機地移到迴圈外,以減少程式的執行時間。 除此之外,對於非冗餘的 Null Pointer 檢查,本文亦引入硬體中斷機制,利用「記憶體分頁存取保護」降低 Null Pointer 檢查在正常情況的執行成本。 根據實驗結果,本文提出之最佳化分別可以讓 LinPack 加快 20.08% 與 SciMark 2.0 加快 2.74%。至於最佳化的額外負擔,對於不常操作 Java 物件或陣列的 Benchmarks 沒有顯著的影響。 | zh_TW |
dc.description.abstract | This thesis discusses several properties of Dalvik Tracing JIT and explains the reason why does the existing optimization or algorithm can't eliminate some redundant null pointer check.
To solve this problem, this thesis proposed a new algorithm based on SSA renaming to eliminate these redundant checks. For the partial redundant checks, we can even take advantage of the Tracing JIT, and speculatively move the checks to the loop header so that we can reduce the number of instructions per iteration. For the non-redundant checks, this thesis utilize the hardware trap and page protection mechanism to reduce the run-time cost of the normal execution of the program. Our experimental results shows that our approach can speed up LinPack by 20.08% and SciMark 2.0 by 2.74%. For the benchmarks that seldom access Java objects or arrays, the overhead of our approach are negligible. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T10:43:15Z (GMT). No. of bitstreams: 1 ntu-102-R01922063-1.pdf: 1430412 bytes, checksum: 3a8608c19bda866be07e55b4017900fe (MD5) Previous issue date: 2013 | en |
dc.description.tableofcontents | Contents
口試委員會審定書 i 誌謝 ii Acknowledgements iii 摘要 iv Abstract v 1 Introduction 1 1.1 Context 1 1.2 Goal 3 1.3 Structure of the Thesis 4 2 Background 5 2.1 Java Programming Language 5 2.2 Java Virtual Machine 6 2.2.1 Instruction Set 6 2.2.2 Method JIT 6 2.2.3 Tracing JIT 7 2.3 Dalvik Virtual Machine 8 2.3.1 Instruction Set 8 2.3.2 Dex File and Zygote 8 2.3.3 Tracing JIT 9 3 Redundant Check Elimination 10 3.1 Motivation 10 3.2 SSA Renaming 12 3.3 Speculative Null Pointer Check Motion 15 3.4 Complete Algorithm 17 4 Hardware Trap 20 4.1 Motivation 20 4.2 Hardware Trap 20 4.3 Complete Algorithm 22 5 Evaluation 24 5.1 Environment 24 5.2 Microbenchmark 25 5.2.1 Integer Array Microbenchmark 25 5.2.2 Object Array Microbenchmark 26 5.2.3 Linear Trace Microbenchmark 27 5.3 Java Benchmark 30 6 Related Works 31 6.1 Null Pointer Checks Elimination 31 6.2 Array Bound Checks Elimination 33 7 Conclusion 35 7.1 Conclusion 35 7.2 Future Works 36 Bibliography 37 | |
dc.language.iso | en | |
dc.title | Dalvik Tracing JIT 最佳化 -- 去除冗餘例外檢查與低成本例外檢查實作 | zh_TW |
dc.title | Dalvik Tracing JIT Optimization -- Redundant Check Elimination and Low-cost Check Implementation | en |
dc.type | Thesis | |
dc.date.schoolyear | 101-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 徐慰中,黃維中,陳呈瑋,陳官辰 | |
dc.subject.keyword | 編譯器,冗餘檢查,例外處理, | zh_TW |
dc.subject.keyword | Tracing JIT,Null Pointer Check,Exception Handling, | en |
dc.relation.page | 40 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2013-08-13 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 1.4 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。