Dynamic slicing of parallel message-passing programs

Dynamic Slicing of Parallel Message-Passing Programs Mariam Kamkar, Patrik Krajina, Peter Fritzson Department of Computer and Information Science Linkoping University, S-58 1 83 Linkoping, Sweden Email: marka@i d a h .se, p a w ida.liu .se, p e t m ida.liu.se Fax: +46 13 282666 Phone: +46 13 281000

This is useful for understanding dependences within programs. A static program slice [ 151 is computed through static data and control flow analysis and is valid for all possible executions of the program. Static slices are often imprecise, i.e., they contain unnecessarily large parts of the program. In contrast, dynamic program slicing [9] considers only a particular execution of a program. The main application of dynamic program slicing is hence in program debugging. This is due to the fact that program debugging is used to analyze a particular execution of a program, the one that shows the existence of a bug in the program. Given an incorrect value of a variable of interest, dynamic program slicing can present a dynamic slice to the debugger (human or system) for further investigation. As an example consider the program in Figure 1(I) which computes sum of the integers 1to n. Figure l(I1) shows a static slice of this program with respect to the value of variable sum that is computed at statement p r i n t f ( If %\n" , sum). This slice consists of all statements in the program that are needed to compute the final value of sum in any execution, in this example the static slice is equal to the original program. Figure l(II1) shows a dynamic slice of the program in Figure 1(I) with respect to the final value of sum for the specific test case n=O. The concept of dynamic slicing has been introduced originally for sequentialprograms (for a survey of program slicing techniques see [7,14]). Distributed programs introduce several problems which do not exist in sequential programs (e.g., non-reproduciblebehaviors, non-deterministic selection of communication events, etc.). Several methods for dynamic slicing of distributed programs have been proposed [lo, 3,2]. Previously we have developed an interproceduraldynamic slicing algorithm, which works at the procedure abstraction level [ll], and which here has been generalized to handle communicating, messagepassing parallel programs. In this paper we present an algorithm for dynamic slicing

Abstract As software applications grow larger and more complex, program maintenance activities such as adding new functionality, debugging, and testing consume an increasing amount of available resources for software development. This is especially true for distributed systems communicating via message-passing, In order to cope with this increased complexity, programmers need effective computer-supported methods for decomposition and dependence analysis of programs, to understand dependencies between differentparts of software systems and to Jind the sources of errors. Program slicing is one method for such decomposition and dependence analysis. A program slice with respect to a specijied variable at some program point consists of those parts of the program which may directly or indirectly affect the value of that variable at the particular program point. In this paper we present an algorithmfor dynamic slicing of distributedparallel programs and some results from an implementationfor a parallel MIMD computer.

1

Introduction

As software applications grow larger and more complex, program maintenance activities such as adding new functionality, debugging, and testing consume an increasing amount of available resources for software development.In order to cope with this increased complexity,programmers need effective computer-supportedmethods for decomposition and dependence analysis of programs [6,5, 13,8]. Program slicing is one method for such decomposition and dependence analysis. A program slice with respect to a specified variable at some program point consists of those parts of the program which may directly or indirectly affect the value of that variable at the particular program point.

1066-6192196 $5.00 0 1996 IEEE Proceedings of PDP '96

170

~~

main ( ) {

(I)

int N, i, sum; iread ( 0 , &N) ; sum

=

i

1;

=

0;

while (i