臺灣博碩士論文加值系統

程式切片(Program slicing) 為一個被廣泛運用在程式的除錯以及程式的測試與了解的技術。它保留了程式當中純粹影響使用者有興趣的變數值的程式碼給使用者作參考以及除錯。在近幾年來多核心系統架構帶動了平行化程式的撰寫風氣以達到高效能運算的目的，在程式切片的技術中，針對平行化程式的分析也開始被提起；在現有針對平行化程式的切片技術當中，大部分的研究為針對此程式產生特定的單一程式切片，或是產生自行定義的平行化圖形並標示出抓取到了哪些元素給使用者參考，雖然這些方法可以產生比較精準的程式切片，但在程式除錯以及程式分析的應用層面上來說，比較難讓使用者針對這些結果來了解平行化程式導致執行錯誤的執行行為為何。在本論文裡，我們提出了一個針對OpenMP parallel for construct的靜態程式切片方法，它將已經先做好的循序程式(sequential program）切片加以分析其平行化部份，並用排列組合的方法表示其平行化程式可能的執行順序為何。我們同時透過觀察到的結果來減少可能產生相同結果的組合順序，並減少了49% 以上的組合結果。最後我們針對所提出的方法實作了一個網頁介面的程式切片工具來方便使用者可以很容易地使用我們的工具。

Program slicing is a program-reduction technique extract statements influence other statements. This well-known technique is widely leveraged to help program analyses and debugging. In recent years, with the growth of multi-core systems, parallel programming is getting more and more important. Unfortunately, the precise and efficient slicing algorithms known for sequential programs cannot be applied to parallel programs. The existing program slicing techniques for parallel programs generate specific program slices or represent the slices with some special graphs which are hard to understand the parallel program execution behaviors. In this thesis, we proposed a static slicing algorithm extending a traditional sequential slicing algorithm for OpenMP parallel for construct with a combination representation to help programmers understand the execution behaviors of parallel programs. Our algorithm exposed the detailed execution orders of shared variables in a parallel region among threads. We also proposed the reduction approaches that reduced the number of combination results by 49 percent. Finally, based our algorithm, a Web-based static slicer was developed for user to operate the slicer in a friendly manner.

Chapter 1 Introduction
1.1 Thesis Contribution
1.2 Thesis Organization
Chapter 2 Background
2.1 Program Slicing
2.2 CodeSurfer
2.3 OpenMP
Chapter 3 Algorithm
3.1 Sequential Slicing
3.1.1 Slicing Algorithm
3.1.2 Backward Slice
3.2 Analysis and Combination Algorithm
3.2.1 Analyzing Interference Variables
3.2.2 Work List Construction
3.2.3 Distributing Loop Iterations Over Threads
3.2.4 Combination Algorithm
3.3 Reduction of Combination
3.3.1 The Original Combination List Counting
3.3.2 Reduction Method 1
3.3.3 Reduction Method 2
3.3.4 Evaluation
3.4 Overall Algorithm
Chapter 4 Static Slicer for OpenMP Parallel For Construct
4.1 Design
4.4.1 System Framework
4.2 Implementation
4.2.1 Sequential Slicing Using CodeSurfer
4.2.2 Dependence Checking by SUIF1
4.2.3 Combination
4.3 Case Study
4.3.1 Case 1
4.3.2 Case 2
4.3.4 Case 3
4.4 Discussion
4.4.1 Extension of the Original Algorithm
4.4.2 Hierarchical Combination Checking
Chapter 5 Related Work
Chapter 6 Conclusion and Future Work
6.1 Conclusion
6.2 Future Work
Reference

[1]“CodeSurfer: A code browse that understands pointers, indirect function calls, and whole-program effects,” online available at http://www.grammatech.com/products/codesurfer/overview.html.
[2]D. Giffhorn, C. Hammer, “An Evaluation of Static Slicing Algorithms for Concurrent Programs,” Seventh IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM’07).
[3]D. M. Hisley, M. J. Bridges, L. L. Pollock, “Static Interprocedural Slicing of Shared Memory Parallel Programs,” International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), June 2002.
[4]F. Tip, “A Survey of Program Slicing Techniques,” Journal of Programming Languages, 3(3):121-189, September 1995.
[5]“HTML: Hypertext Markup Language,” online available at http://www.w3.org/html/default.asp.
[6]“ICC: Intel C++ Compiler,” online available at http://software.intel.com/en-us/intel-compilers/.
[7]J. Cheng, “Dependence Analysis of Parallel and Distributed Programs and Its Applications,” International Conference on Advances in Parallel & Distributed Computing, 1997.
[8]J. Ferrante, K. J. Ottenstein, J. D. warren, “The Program Dependence Graph and Its Use in Optimization,” ACM Transactions on Programming Languages and Systems, 1987.
[9]J. Krinke, “Static Slicing of Threaded Programs,” Proceedings of ACM SIGPLAN Workshop on Program Analysis for software Tools & Engineering, Montreal, CA, June 1998.
[10]J. Krinke, “Context-sensitive Slicing of Concurrent Programs,” ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003.
[11]“JavaScript,” online available at http://www.jacascript.com/.
[12]K. J. Ottenstein and L. M. Ottenstein, “The Program Dependence Graph in a Software Development Environment,” Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, ACM SIGPLAN Notices 19,5, May 1984.
[13]B. Korel, J. Laski, “Dynamic Program Slicing,” Information Processing Letters, 29(3):155-163, 1988
[14]M. G. Nanda and S. Ramesh, “Interprocedural Slicing of Multithreaded Programs With Applications to Java,” ACM Transactions on Programming Languages and Systems (TOPLAS), 28(6):1088–1144, 2006.
[15]M. Weiser, “Program Slicing,” IEEE Transactions on Software Engineering, vol. 10, pp. 352-357, 1984.
[16]N. Uchihira, S. Honiden and T. Seki, “Hypersequential Programming,” IEEE Concurrency, July-September 1997.
[17]“OpenMP: The OpenMP API specification for parallel programming,” online available at http://openmp.org.
[18]P. Anderson, “CodeSurfer/Path Inspector,” Proceeding of the 20th IEEE international Conference on Software Maintenance (ICSM’04).
[19]P. Anderson, T. Teitelbaum, “Software Inspection Using CodeSurfer,” Proceeding of The First Workshop on Inspection in Software Engineering (WISE’01), Paris, July, 2001.
[20]P. Anderson, M. Zarins, “The CodeSurfer Software Understanding Platform,” Proceeding of the 13th International Workshop on Program Comprehension (IWPC’05).
[21]“PHP: Hypertext Preprocessor,” online available at http://php.net/.
[22]S. Horwitz, T. Reps and D. Binkley, “Interprocedural Slicing Using Dependence Graphs,” Proceeding of the SIGPLAN’88 Conference on Programming Language Design and Implementation (PLDI’88) , Atlanta, Georgia, June 22-24, 1988.
[23]“The SUIF 1.x Compiler System,” online available at http://suif.stanford.edu/suif/suif1/.
[24]Unknown Authors, “Dependence Graphs and Program Slicing,” GrammaTech, Inc., White Paper.