(An) efficient debugging method for message-based parallel programs using static analysis information

Abstract

Since the interactions among processes of a parallel program are intrinsically nondeterministic, parallel programs often yield different results on repeated runs with the same input data. This non-reproducibility makes it extremely difficult to debug parallel programs. In addition, the interactions may be interfered with and even changed by extra codes inserted into the original program for debugging purpose. This phenomena, called probe effects, is another serious obstacle. Guaranteeing reproducibility and minimizing probe effects are major issues in the parallel program debugging. This thesis suggests a new debugging method, named detect and reproduce method, for message-based parallel programs. This proposed method guarantees the reproducible behaviors of a target program. It is also devised to alleviate probe effects by reducing both the number of the probes to be inserted into a program and the amount of information gathered by those probes. Uniqueness of this method arises from the fact that it employs a static analysis technique to detect nondeterminacy. By detecting nondeterminacy before running the program, only a small number of probes are required to assure reproducibility. To analyze message-based programs statically, an MHB model is designed to catch the synchronization structures and a few algorithms have been developed to locate nondeterminacy based on the MHB model. Based on the analysis results, probes are inserted only into the places where nondeterminacy may occur.