Static Detection Of Unspecified Behaviors And Deadlocks In OpenMP Programs

Because of good flexibility and portability, OpenMP has become the industry standard for shared memory programming. However, it is so difficult to develop correct parallel programs that OpenMP programs are apt to malfunction. Unspecified behaviors and the deadlocks related to barriers are two potential factors that cause OpenMP programs to err at runtime. Static analysis is used to detect these hazards in OpenMP programs without running these programs.To begin with, the above two hazards in OpenMP programs are investigated and summarized. Unspecified behaviors are classified into four categories,.and the deadlocks related to barriers are classified into two categories. Then, three key techniques for static analysis of OpenMP programs are introduced. Firstly, traditional control flow graph is extended. Parallel basic blocks are introduced to represent OpenMP API, and structure edges are added to determine the scope of directives and control structures. Secondly, indeterminate program behaviors caused by control structures are analyzed conservatively. Thirdly, meaningful interpretations are reported for each detected hazard, which make it convenient for users to not only confirm the found hazards, but also give priority to the hazards that are more likely to occur. Searching is used to record the paths in control flow graph that lead to the detected hazards, and static branch prediction is employed to estimate the execution probability of a path.Next, the procedures to detect the above two hazards are presented. To detect unspecified behaviors, a structured region is divided into different levels according to the nesting relations of the control structures in it and analyzed with level as a unit, while an unstructured region is checked through the identification of live private variables. Existence rule and nonuniformity rule are adopted to detect the first and the second category of the deadlocks related to barriers respectively. The identification of reaching definitions to lock variables is used to detect the first category of deadlocks in the mutual exclusion regions determined by lock variables. Nestable locks introduced by OpenMP can also be analyzed. Furthermore, the identification of reaching definitions to virtual variable is used to detect the second category of deadlocks. Moreover, the searching techniques to record the paths leading to these hazards are discussed.At last, a static correctness checking tool for OpenMP programs, called C-Checker, is described. C-Checker is tested using several customized OpenMP programs and SPEComp2001 benchmark suite. Experiments show that, C-Checker can effectively detect unspecified behaviors and the deadlocks related to barriers in actual OpenMP programs, and help programmers eliminate these hazards.