臺灣博碩士論文加值系統

物件導向(object-oriented, OO)程式設計已成為軟體發展的主流方式。比起傳統的程序導向方法，其設計出的程式較具擴充性、易管理及高再利用性，但卻面臨執行效率不彰與程式動態行為複雜，不易了解動態執行程序等困境。為改善或減輕此困境，進而提供更準確效能測量及提昇程式執行效能，程式分析扮演重要的角色。目前程式分析方法如靜態及動態分析不足以了解程式執行時的行為樣式，同時也未有將行為樣式量化的文獻或報告。對程式語言而言，程式碼樣式(code patterns)是靜態重複的結構，可在軟體設計時加入以解決特定的問題。相對於程式碼樣式，控制樣式(control pattern)是在程式執行時動態產生的重複結構，可應用於設計測量程式(benchmark)及了解程式執行的行為(runtime behavior)，並對執行程式最佳化有幫助。
在論文中，我們分析Java程式多種度量方式(metric)與物件方法呼叫序列(method invocation sequence)，我們提出以控制樣式為基礎的動態分析工具(profiler)，控制樣式包含一個有向圖(directed graph)及兩個函數，限制輸出函數(constraint output function)，限制布林函數(constraint Boolean function)，可將程式執行的軌跡(run-time trace)以有向圖(directed graph)表示，限制輸出函數及限制布林函數來說明程式執行真正的路徑。藉由此分析，希望能更了解Java程式執行時的行為。首先，我們修改了昇陽公司的模擬Java虛擬機器軟體(Java virtual machine)，藉此得到Java程式動態執行時的資訊。然後設計與實作一個控制樣式探索工具(control pattern mining tool)來分析所得到的動態執行資訊。同時，我們收集了18個Java程式做為控制樣式分析實驗程式。
物件導向程式的執行是藉由訊息呼叫(message invocation)而導致物件的產生與消滅(lifetime)，控制樣式敘述了物件之間控制權的轉移。本論文藉由實驗結果說明了控制樣式的存在及提供量化分析，控制樣式包括複雜的控制樣式(complex control pattern)、複合式的控制樣式(compound control pattern)和簡單的控制樣式(simple control pattern)在實驗程式中佔有不同的比例，且並非所有的程式都擁有這三類控制樣式，但大部分的程式也都含有高比例不尋常的控制樣式(nontrivial control pattern)。在此研究中，我們特別說明控制樣式可應用於物件導向測量程式建構，建議一個以控制樣式為基礎的物件導向測量程式建構方法，另一方面，控制樣式也可以提供給程式設計師設計較有效率的物件導向程式，同時，為了更容易了解，論文中使用許多範例來解釋控制樣式的應用方法。

Object-Oriented (OO) programming has played a major role in program design and implementation due to the fact that it is more extensible, maintainable, and reusable in the software system construction. Experiences of using Object-Oriented programming have indicated that there exist disadvantages with respect to its execution inefficiency and complicated runtime behaviors. Program analysis is essential for performance measurement and improvement. Current static and dynamic analysis using OO programming cannot characterize runtime behavior well and are also hard to quantify the measured results. In this dissertation, research work was performed to analyze several Java program metrics and method invocation sequence. The results not only provide us a better understanding of the runtime behavior but also present more information for different application domains.
Code-patterns are statically recurring structure specifically related to a programming language. It can be used in parallel to help designing software systems for solving particular problems. In opposition to code-patterns’ role in assisting compilation, control-patterns are dynamically recurring structures invoked during program execution time. It can be used to understand the run-time behaviors of OO-programs for the underlying architecture such as Java-VM. We have proposed a run-time profiler based on control patterns to show that all run-time trace can be represented by a directed graph, a constrained output function, and a constraint Boolean function.
It is known that the progress of program is the lifetime of objects by message invocation. Control pattern describes the model of control transfer among objects in OO program execution. In this research, several control patterns are proposed and discussed. Particularly, we have analyzed and collected several control patterns over several Java program corpora. The experimental results show that control pattern does exist and provide quantitative analysis. Simple pattern, compound pattern and complex pattern have different ratio respectively, according to a variety of different source programs. Not all benchmark programs contain all three kinds of patterns. There are high percentages of programs with nontrivial behaviors. Application of control patterns are addressed in this study specifically since control patterns can be used to design an OO benchmark for understanding the execution behaviors of OO systems. An OO benchmark design methodology is proposed for implementing such application. Also, control pattern can be used to provide guidelines for OO programmers to write more effective OO program. To make it clear, examples are also used to illustrate the applicability of these control patterns.

摘 要
Abstract
Table of Contents
List of Figures
List of Tables
1.Introduction
1.1 Introduction
1.2 Motivation
1.3 Organization of this dissertation
2. Related Work
2.1 Static program analysis
2.1.1 Static statistics
2.1.2 Intraprocedural control flow analysis
2.1.3 Data flow analysis
2.1.4 Interprocedural control flow analysis
2.2 Dynamic program analysis
2.3 Data mining
2.4 Mining process models from workflow logs
3. Run-Time Profiling of Java Program Execution
3.1 JVM instruction set overview
3.1.1 Supported data types
3.1.2 Instruction set
3.2 Java class file format
3.3 JVM software implementation internals
3.4 Modified implementation
3.5 Profile files
4. Control Patterns
4.1 Catalogs of control patterns
4.1.1 Simple control patterns
4.1.2 Compound control pattern
4.1.3 Complex control pattern
4.2 Control pattern
4.2.1 A formal definition of control patterns
4.2.2 Control pattern mining
4.3 Mining execution log patterns
4.4 Other object-oriented program behaviors
5. Benchmark Programs and Assessment
5.1 Benchmark programs
5.2 Runtime statistics
5.2.1 Method size
5.2.2 Native method
5.2.3 Method invocation localities
5.2.4 Receiver class versus method class
5.3 Control pattern
5.3.1 Statistics - Control pattern (Animation)
5.3.2 Statistics - Control pattern(LinpackJava)
5.3.3 Statistics - Control pattern (BackgroundThread &
DitherTest)
5.3.4 Statistics - Control pattern (TuringMachine)
5.4 Comparison
6. Applications
6.1 Benchmark design
6.2 Redesign program to improve performance
7. Conclusion and Future Work
7.1 Conclusion
7.2 Future work
References
Appendix
VITA
Publications

[1]Shih-Kun Huang, Optimizing Run-Time Behaviors in Object-Oriented Programming Systems, Ph.D. Dissertation of Institute of Computer Science and Information Engineering, National Chiao-Tung University, HsinChu, Taiwan, 1996.
[2]H.J. Curnow, and B.A.Wichmann , “A synthetic benchmark”, Computer Journal, Vol. 19, No. 1, Feb. 1976, pp. 43-49.
[3]R.P. Weicker and R. Dhrystone, “A synthetic systems programming benchmark”, Comm. ACM, Vol. 27, No. 10, October 1984, pp. 1013-1030.
[4]James Rumbaugh, Micheal Blaha, William Premerlani, Frederick Eddy, and William Lorensen, Object-Oriented Modeling and Design, Prentice-Hall Inc., 1991.
[5]Tim Lindholm and Frank Yellin, The Java Virtual Machine Specification, Addison-Wesley Pub. Co., 1997.
[6]Sun Microsystems, Inc., Java Platform Performance Strategies and Tactics, http://java.sun.com/docs/books/performance, 2002.
[7]Sun Microsystems, Inc., Heap Analysis Tool,
http://developer.java.sun.com/developer/onlineTraining/Programming/JDCBook/perf3.html#os, 2002.
[8]VMGEAR, Optimzeit, http://www.vmgear.com/products/index.html, 2002.
[9]KL group, Jprobe Suite, http://www.klgroup.com/software/jprobe/jprobesuite.html, 2002.
[10]Rakesh Agrawal and Ramakrishnan Srikant, “Mining Sequential Patterns”, Research Report RJ 9910, IBM Almaden Research Center, San Jose, California, October, 1994.
[11]Rakesh Agrawal and Ramakrishnan Srikant, “Fast Algorithms for Mining Association Rules”, Research Report RJ 9839, IBM Almaden Research Center, San Jose, California, October, 1994.
[12]Johannes Klein, “Advanced Rule Driven Transaction Management”, IEEE COMPON, 1991, pp. 562-567.
[13]Reinhold and P. Weicker, “An Overview of Common Benchmarks”, IEEE Computer, Vol. 23, No. 12, 1990, pp. 65-75.
[14]Hans Zima and Barbara Chapman, Supercompilers for Parallel and Vector Computers, Addison-Wesley Pub. Co., 1990.
[15]Aho A.V., Sethi R., and Ullmjan J.D., Compilers. Principled, Techniques and Tools, Addison-Wesley Pub. Co., 1986.
[16]Jaffrey Dean, Greg DeFouw, David Grove, Vassily Litvinov, and Graig Chambers, “Vortex: An Optimizing Compiler for Object-Oriented Languages”, OOPSLA’96, San Jose, Californi, October 1996, pp. 83-100.
[17]David Grove, Greg DeFouw, Jeffrey Dean, and Craig Chambers, “Call Graph Construction in Object-Oriented Languages”, OOPSLA’97, Atlantas, GA, USA, October 1997, pp. 108-124.
[18]Ming-Syan Chen, Jiawei Han, and Philip S. Yu, “Data Mining: An Overview from a Database Perspective”, IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 6, December 1996, pp. 866-883.
[19]R. Srikant and R. Agrawal. “Mining Generalized Association Rules”, ResearchReport RJ 9963, IBM Almaden Research Center, San Jose, California, June 1999.
[20]R. Agrawal, T. Imielinski, and A. Swami, “Mining association rules between sets of items in large databases”, In Proc. of the ACM SIGMOD Conference on Management of Data, Washington, D.C., May 1993, pp. 207-216.
[21]U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI Press/MIT Press, 1996.
[22]W. J. Frawley, G. Piatetsky-Shapiro, and C.J. Matheus, Knowledge Discovery in Databases, AAAI Press, 1993.
[23]Rakesh Agrawal, Dimitrios Gumopulos, and Frank Leymann, “Mining Process Models from Workflow Logs”, Research Report RJ 10100, IBM Almaden Research Center, San Jose, California, December, 1997.
[24]Bill Venners, Inside the Java Virtual Machine, McGraw-Hill, 1998.
[25]Sun Microelectronics, JavaChips,
http://www.sun.com/smi/Press/sunflash/9704/sunflash.970402.9999.html, 2002.
[26]Han-Min Tseng, Instruction Folding Analysis in Java Processor, Master Thesis of Institute of Computer Science and Information Engineering, National Chiao-Tung University, HsinChu Taiwan, 1997.
[27]Sun Microelectronics, The VIS instruction Set,
http://www.sun.com/products/processors/vis/index.html, 2002.
[28]Sun Microelectronics, picoJava Microprocessor Core Architecture,
http://www.sun.com/microelectronics/picoJava/overview.html, 2002.
[29]Sun Microsystems, Inc., Java JIT Compiler,
http://wwws.sun.com/software/solaris/jit/, 2002.
[30]Microsoft Corporation, Visual J++,
http://msdn.microsoft.com/visualj/prodinfo/previous/v11/faq.asp, 2002.
[31]HP, HP-UX,
http://www.hp.com/products1/unix/java/infolibrary/prog_guide/java1/tools.html, 2002.
[32]Jon Meyer, Troy Downing, Java Virtual Machine, O’Reilly & Associates, 1997.
[33]Jan Vitek, R. Nigel Horspool and Andreas Krall, “Efficient Type Inclusion Tests”, OOPSLA’97, Atlantas, GA, USA, October 1997, pp. 142-157.
[34]Andreas Krall, Jan Vitek and Nigel Horspool, “Near Optimal Hierarchical Encoding of Types”, ECOOP’97, Jyvaskyla, Finland, June 1997, pp. 128-145.
[35]Jeffrey Dean, David Grove, and Craig Cambers, “Optimization of Object-Oriented Programs using Static Class Hierarchy Analysis”, ECOOP’95, Aarhus, Denmark, August 1995, pp. 77-101.
[36]Matt T. Yourst, Inside Java Class Files, Dr. Dobb’s Journal, 1998.
[37]The Unicode Standard: Worldwide Character Encoding, http://unicode.org, 2002.
[38]UCS Transformation Format 8 (UTF-8),
http:// www.stonehand.com/unicode/standard/wg2n1036.html, 1999.
[39]P. Michaud, “Clustering techniques”, Future Generation Computer Systems, 1997, pp.135-147.
[40]M. R. Anderberg, Cluster Analysis for Applications, Academic Press, New York, 1973.
[41]C.C. Hwang, S.K. Huang, M.S. Lin, and D.J. Chen, “Dynamic Java Programming Corpus Analysis Part2: The Control Pattern Analysis”, Journal of Object-Oriented Programming, June/July 2001, pp. 17-23.
[42]C.C. Hwang, S.K. Huang, D.J. Chen, and David T.K. Chen,” Object-Oriented Program Behavior Analysis Based on Control Patterns”, APAQS 2001, Proceedings of the Second Asia-Pacific Conference on Quality Software, Hong Kong, December 2001, pp. 81-87.
[43]U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Pub. Co., 1989.
[44]Ralphp. Grimadldi, Discrete and Combinatorial Mathematics an Applied Introduction, Addison-Wesley Pub. Co., 1989.
[45]C.C. Hwang, S.K. Huang, D.J. Chen, and M.S. Lin, “Dynamic Java Program Corpus Analysis Part1: The Analyzer”, Journal of Object-Oriented Programming, MAY 2001, pp. 26-29.
[46]Jack Dongarra, Reed Wade, and Paul McMahan, LinpackJava, http://www.netlib.org/benchmark/linpackjava/, 2002.
[47]Pascal Andre and Jean-Claude Royer, “Optimizing Method Search with Lookup Caches and Incremental Coloring”, OOPSLA’92, pp. 110-120.
[48]Henry Lieberman, “Using Prototypical Objects to Implement Shared Behavior in Object Oriented Systems”, OOPSLA’86 Proceedings September 1986, pp. 214-223.
[49]Lewis J. Pinson and Richard S. Wiener, An Introduction to Object-Oriented Programming and Smalltalk, Addison-Wesley Pub. Co., 1998.
[50]William Pugh and Grant Weddell, “Two-directional record layout for multiple inheritance”, Proceedings of the ACM SIGPLAN’90 Conference on Programming Language Design and Implementation, White Plains, New York, June 1990, pp. 85-91.
[51]Craig Chambers, David Ungar, and Elgin Lee, “An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes”, OOPSLA’89 Proceedings, October 1989, pp. 49-70.
[52]David Ungar and Randall B. Smith, Craig Chambers, and Urs Holzle, “Object, Message, and Performance: How They Coexist in Self”, IEEE Computer, October 1992, pp.53-64.
[53]David Ungar, Randall B. Smith, “Self: The Power of Simplicity”, OOPSLA’87 Proceedings, 1987, pp. 227-241.