Analysis of Synchronization in a Parallel Programming Environment

This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/16485Parallel programming is an intellectually demanding task. One of the most difficult challenges in the development of parallel programs for asynchronous shared memory systems is avoiding errors caused by inadvertent data sharing, often referred to as data races. Static prediction of data races requires data dependence analysis, as well as analysis of parallelism and synchronization. This thesis addresses synchronization analysis of parallel programs. Synchronization analysis enables accurate prediction of data races in a parallel program. The results of synchronization analysis can also be used in a variety of other ways to enhance the power and flexibility of a parallel programming environment. We introduce the notion of schedule-correctness of a parallel program and relate it to data dependences and execution orders in the program. We develop a framework for reasoning about execution orders and prove that static determination of execution orders in parallel programs with synchronization is NP-hard, even for a simple language. We present two different algorithms for synchronization analysis that determine whether the cumulative effect of synchronization is sufficient to ensure the execution ordering required by data dependence. The first algorithm iteratively computes and propagates ordering information between neighbors in the program flow graph, analogous to data flow analysis algorithms. The second algorithm computes the necessary path information in the program graph and uses it to transform the problem into an integer programming problem, which also is NP-hard. We present a heuristic approach to solving the integer programming problem obtained and argue that it is efficient for the problem cases that we expect to encounter in our analysis. We discuss the merits, shortcomings and suitability of the two algorithms presented. We have developed a prototype implementation of synchronization analysis. We discuss the implementation and practical issues relating to the effectiveness and usefulness of our analysis