Content area
As computational scientists continue to demand higher performance, the use of parallelism is becoming more pervasive. Workstations with multiple CPU's are no longer unusual. With higher performance networks, clusters of workstations or PCs networked together have become a cost-effective parallel machine for high performance computing. A variety of parallel programming languages and sophisticated compiler technology has been developed for gaining efficient use of the available parallelism.
Programmers often have to be concerned with ensuring that communication and synchronization between processes are correctly achieved in addition to programming computational components. For efficiency, most parallel programming paradigms allow for nondeterministic execution, in which processes do not synchronize after every statement. Instead processes execute at different speeds such that different sequences of statements are executed during different runs of the program with the same input data. Parallel programmers find software tools for performance analysis and debugging very valuable, but otherwise there is a lack of software tools for parallel programmers. In particular, little to no support for testing parallel programs exists.
Many structural testing methodologies and algorithms for generating test data automatically have been developed and successfully used for testing sequential programs. Some progress has been made in the analysis, testing, and debugging of Ada-like concurrent programs. Also, there has been considerable work in analyzing parallel programs for the detection of deadlock and race conditions, debugging, and optimizing analysis and transformation. The current testing methodologies target concurrent programs with rendezvous communication, hence, do not support the testing of programs using more general synchronization and communication features. Without further consideration, structural testing methodologies used for testing sequential programs cannot be applied to parallel programs.
The main objective of this research has been to demonstrate that program-based methodologies can be used to generate test cases automatically for shared memory parallel programs. That is, even when a formal specification is lacking, software testing of shared memory parallel programs can still be performed in a systematic fashion with the aid of software testing tools.
The contributions of this research include the following. The framework for testing sequential programs is extended to support parallel program testing, taking into account the nondeterministic nature of parallel programs. A novel algorithm is presented to generate a du-path coverage with respect to a define and use pair, i.e., du-pair, for shared memory parallel programs. Modifications to this algorithm in order to test parallel programs with message passing and rendezvous communication are described. With the goal of exposing synchronization errors, a temporal testing method is presented with the capability of automatically generating temporal test suites. Because the total number of possible temporal test cases is exponential, several approaches to reducing the size of a temporal test suite are presented. The methodologies developed in this dissertation have been implemented and incorporated into a software testing tool, called della pasta, which provides a practical and user-friendly interface for visualizing a du-pair and a path coverage in a shared memory parallel program. (Abstract shortened by UMI.)