| With the rapid progress in the areas of parallel algorithms and parallel architectures, it is realized that effective, systematic methodologies for parallel software construction and validation must be developed to fully utilize the potential offered by parallel processing. Motivated by the fact that program testing has been the most commonly used approach to sequential software validation but little previous research has focused on parallel program testing, this thesis addresses the issues of testing parallel programs with emphasis on synchronous parallel programs for SIMD machines.; We first introduce a Pascal based, general purpose parallel language for SIMD machine programming. Algorithms for interconnection and shared memory machines are implemented in this language and used as examples. This provides us with an environment to study the characteristics of parallel programming.; An essential element of a theory for parallel program testing is a classification of parallel programming errors. Based on the prominent features of parallel programs, we classify parallel programming errors into processor activation errors, interprocessor communication errors, and computation errors. This classification scheme refines the widely accepted dichotomy of domain and computation errors for sequential programs but is free of its problems.; We then develop several approaches to designing testing coverage criteria for parallel programs. Various testing metrics, including ones adapted from sequential program testing criteria and genuine parallel program testing criteria are defined accordingly; they include control flow metrics, data flow metrics, and metrics based on input-driven structures. The properties of these criteria are discussed, and their relationships in terms of relative strengths are derived. Several relevant feasibility problems are proved to be undecidable. Finally, a testing strategy based on grouping processors into clusters is presented and analyzed.; We also design and present a complete methodology for testing parallel programs which incorporates specific coverage metrics and sequential program testing methods. Program testing procedures and tools based on our methods can be readily implemented and integrated into parallel programming environments. The implementation of a sample testing system is discussed. |
