TESTING, DEBUGGING, AND MEASURING PARALLEL SOFTWARE

Mohamad  I. LADAN

Testing and debugging sequential software is a fairly complex  process, and it is even more complex when it is applied to parallel software. Different techniques are available for testing and debugging sequential programs, however, these tech­niques cannot be applied effectively to test and debug parallel programs. This is because of the complexity of the synchronization/communication structure and the non‑deterministic execution of parallel programs. The objective of this thesis is to in­vestigate how to effectively test and debug parallel programs. We develop static anal­ysis approaches for detecting race conditions and deadlocks in both shared‑memory and message‑passing parallel programs. Furthermore, we develop a novel set of met­rics that assess the quality of parallel software.

Race condition detection is a crucial aspect of developing and debugging shared-­memory parallel programs. Explicit synchronization is usually added to such pro­grams to coordinate access to shared data, and race conditions result when this syn­chronization does not force concurrent processes to access data in the expected order. In this thesis, we develop an efficient static concurrency analysis approach for detect­ing race conditions in shared‑memory parallel programs with explicit synchronization. This approach is based on a graph model, the Concurrency Synchronization Graph (CSG), that represents the execution state space of a parallel program. This model is constructed from a set of Compact Control Flow Graphs(CCFG) generated from a slic­ing mechanism based on the synchronization structure of the program. Our approach is more efficient and accurate than previous static analysis approaches. Comparison results using several program examples and a general complexity analysis are pre­sented.

Most of the static analysis techniques have not addressed detection of race condi­tions in parallel loops. In this thesis, we extend our static concurrency analysis ap­proach to detect race conditions in parallel loops. We used existing data dependence analysis techniques to identify loop iterations that could exhibit race conditions. The CSG‑based approach is extended to represent the concurrent execution state space of these iterations, and to check whether or not the synchronization structure used in the loop has preserved the data dependence constraints, and thus prevented race conditions from occurring. The approach is illustrated using several parallel loop ex­amples, and is compared with related techniques.

Deadlock in message‑passing parallel programs is an important anomaly that must be addressed. Previous static concurrency analysis techniques are based on a graph model with exponential state space complexity, and have focused on detecting dead­locks in Concurrent Ada programs. In this thesis, we extend our race condition detection approach to detect deadlocks in message‑passing parallel programs. The resulted approach has a polynomial state space complexity. Complexity analysis and experimental results that show the efficiency and accuracy of our approach compared with related existing approaches are presented.

Software metrics have been developed for sequential software as a quantitative means of.assessing the software development process as well as the quality of soft­ware products. However, few metrics have been developed for parallel software. In this thesis, we develop a concurrency metric that we refer to as the Program Con­currency Measure (PCM). PCM characterizes the synchronization and concurrency complexity in parallel programs. This metric is used for assessing the quality of a parallel program design and can be used for performance prediction. PCM is based on a static concurrency analysis approach that considers all possible concurrency and synchronization relations among events in parallel programs while previous concur­rency metrics are based on a logical time analysis approach that considers only part of the concurrency relations. Furthermore, we have presented experimental results that validate and illustrate the use of this metric.