Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs

150 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.Parallel programs are significantly different from sequential programs in the sense that they can exhibit timing-dependent behaviour. The same program with the same input data can produce different results on different executions. This is unacceptable for a large number of programs. The main focus of this thesis is techniques to automatically detect such situations. Since nondeterminacy is intimately related to the ordering between operations executed by the program, the main problem studied is that of computing ordering between operations. The ordering is determined by the synchronization operations used.The computation of ordering can be done either at compile time, or execution time and later. We describe techniques for both. Static analysis is applicable to every input data set, but is approximate due to the incompleteness of information available at compile time. Execution time analysis, on the other hand, has complete information about the execution, but may be applicable only for the input data set used on that execution. The approach advocated is a combination of compile time and execution time analysis.The feasibility of these ideas is demonstrated by the implementation of a tool that detects nondeterminacy in the parallel programs available to us. Detection is practical with a combination of aggressive compile time analysis and execution time checking.As an extension of the work on detecting ordering, a technique is described to perform dataflow analysis of parallel programs in order to effect scalar optimizations such as conditional constant propagation. The new dataflow framework reflects the fact that in parallel programs a number of threads can execute simultaneously.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD