Project Title: PROGRAM SLICING FOR OPENMP SHARED MEMORY PARALLEL PROGRAMS

Project Overview:
-----------------

This project will take our current program slicing implementation for OpenMP shared memory parallel programs to a level that will make it usable by a parallel programmer who knows little about the underlying infrastructure. Static interprocedural slicing for sequential codes is well understood and used in a variety of applications. A static program slice is defined as follows: Let P be a program, p be a point in P, and v be a variable that is defined or used at point p. Then a static slice relative to the slicing critierion (p,v) is the set of all statements in the program P that might affect the value of v defined or used at point p. Slicing is used for software development and maintenance activities such as program understanding, software testing, and debugging. By extending and modifying an interprocedural slicing algorithm for sequential programs, and an intraprocedural slicing algorithm for parallel programs, we have developed a technique for static interprocedural slicing of shared memory parallel programs, written using OpenMP explicitly parallel constructs. OpenMP is the standard for explicitly parallel shared memory programming.

This project consists of designing and implementing a user-friendly slicing tool for OpenMP based on our slicing algorithm. An initial prototype of our algorithm exists, but it is not in a state to be used by a novice.

This project has several parts:
--------------------------------

1. literature review of papers on program slicing, OpenMP parallel programming, and our Odyssey/SUIF compiler infrastructure; learning about the capabilities/use of a program slicer and expected input and output of the current slicing algorithm for OpenMP.

2. design of a user-friendly GUI for a slicing tool, after examination of existing slicing tool(s) for sequential programs.

3. building the user-friendly slicing tool, reusing and extending the code for the slicing itself and adding a GUI.

4. writing web-based documentation and tutorial for the slicing tool

5. running experiments to learn about the interactions of variables in slices of parallel programs.

6. giving an oral presentation and demo on the tool to the local researchers.

Tasks involved:
---------------

1. In order to gain background in program slicing and its applications, initial background reading will be required. This first step is to read the following papers, asking questions and discussing the papers as needed during initial meetings.

The following is a list of some relevant background material:

- Program Slicing for Sequential Programs:

1. M. Weiser. Program slicing. IEEE Transactions on Software Engineering, vol. 10, pp. 352-357, 1984.

2. F. Tip. A survey of program slicing techiques. Journal of Programming Languages, vol 3., no. 3, pp 121-189, September 1995.

3. S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs, ACM TOPLAS, January 1990.

4. J. Krinke. Static slicing of threaded programs. In Proc. Of ACM SIGPLAN Workshop on Program Analysis for Software Tools & Engineering, Montreal, CA, June 1998.

5. P. Livadas and S. Croll. A new algorithm for the calculation of transitive dependences, Journal of Software Maintenance, vol 6, , pp. 100-127, 1994.

- Slicing OpenMP Programs: - 1. Matt Bridge's honor's thesis

2. Dixie Hisley, Matt Bridges, and Lori Pollock, ``Static Interprocedural Sli cing of Shared Memory Parallel Programs, {\bf International Conference on Parallel and Distributed Processing Techniques and Applications }, (PDPTA'02), pp. 658-664, June 2002.

2. The next step is to familiarize yourself with the interface to the current slicer for OpenMP, and the OpenMP compiler infrastructure to the extent needed for this project. This entails learning how to run the slicer on different programs and slicing criteria, looking at the input and output formats, and how to invoke the slicer with different parameters.

3. The next step is to examine some existing tools that perform program slicing for sequential programs. Codesurfer is an example that we have locally here. There are probably others that could be found on the web and used. The goal is the investigate the user interface for usefulness, user-friendliness, and information that is given by and to the user. Look at what you believe is good and what you believe is bad in design and user-friendliness and its application to parallel programs. Give demos and report back at a meeting on your opinions etc.

4. Create a design for the GUI for the program slicer. Discuss the justification for the design at a meeting, finalizing its design.

5. Choose a method for implementing the GUI design: language, tool, libraries,...and discuss choice.

6. Implement an initial GUI and interface with the current slicer. Do a demo in a meeting to show its progress, good points and issues.

7. Revise the design, debug, and test the slicer tool. Have someone try it out and give feedback on your design, and revise.

8. Design, and set up some slicing tests to provide experimental data on program slicing of parallel programs. What metrics should be used? How can they be measured? What slicing criteria should be tested? What programs should be tested?

9. Perform experiments and gather data.

10. Analyze and discuss experimental results.

11. Write web-base documentation and tutorial for the slicing tool.

12. Create and deliver an oral presentation on your research experience to the local research group.

13. Outline and begin writing a paper on the slicing tool and experiments.

Requirements:
-------------

- C++ programming experience - Data structures - Background in parallel programming, if possible.