Data-Race Detection and Lock-Mechanism Validation for OpenMP Programs on GCC

由於多核心處理器已成為目前IT界之主流設計，所以當今多執行緒程式已經成為目前程式開發之主流模式。除了使用p-thread相關之API來開發多執行緒程式之外，使用較簡單且較快速的API來開發的多執行緒程式也已經成為當前之主流，如OpenMP。因此，許多主流編譯器廠商也支援OpenMP，包括GCC。雖然使用OpenMP指示詞較為簡單，但是對於純粹使用OpenMP指示詞來開發的程式而言，我們觀察到其中還是會有一些異常現象存在。基於這樣的觀察，針對OpenMP指示詞和資料環境的獨特性，我們在GCC上發展出一個靜態時間的分析工具來偵測OpenMP程式的潛在data races，並且回報給程式開發人員關於lock規範的誤用以及那些未遵守OpenMP規範的誤用案例。Multi-threaded programs become the main programming fashion as the processors with multi-cores have turned into the state-of-the-art design in IT market nowadays. In addition to traditional p-thread-API oriented technologies to implement multi-threaded programs, simpler and quicker technology like using OpenMP directives to develop programs which intentionally require threads to partake certain amounts of computational tasks, is also a popular way. Hence, various dominant vendors of compilers support OpenMP, including the GCC compiler. Although it is rather simpler to use OpenMP directives, there still exist some programming anomalies specific to programs applying OpenMP directives. Observed this, we developed a static-time analysis tool embedded in GCC to detect potential data races under the unique scenarios of OpenMP directives and data environments, report programmers on the improper uses of OpenMP lock-discipline, and other misuses which are not conformable to the OpenMP specifications.誌謝 i文摘要 iibstract iii錄 iv目錄 vii目錄 viiihapter 1 Introduction 1hapter 2 Related Works 4hapter 3 Analysis System Overview 10.1 Introduction 10.2 System Overview 11.3 Internal Processing and Implementations for OpenMP in GCC 12.4 Implementation Issues and Compromises 13.4.1 Control-Flow Issues 13.4.2 Improperly-Placed OMP Barriers 13.4.3 OMP-Kernel Functions 14.4.4 Force Inlining Callee Functions of Kernels 15.4.5 Preserving IRs of the Functions 17.4.6 Retrieve Inlined Statements 17hapter 4 Data-Race Detection Introduction 19.1 Introduction 19.2 The May-Happen-in-Parallel Relationship for OpenMP Semantics 19.2.1 Background 20.2.2 The MHP Relationship 23.2.3 Basic Components in MHP Graph 24.3 The Organization of MHP Graph 30.4 MHP Relationship Calculation for Interested-Statements 31.5 Data-Race Detection Based on MHP Relations 32.5.1 Introduction 32.6 Classifying Data-Race Types 33.7 Inferring Accessed Variables 33.8 Filter Out Variable References Which Never Induce Data Races 36hapter 5 Protecting Lock Analysis and Lock-Discipline Misuse Detection Introduction 37.1 Introduction 37.2 The OpenMP Lock-Routine Functions 38.3 The Algorithm Overview 39.4 Lock-Discipline Misuses Detection 41.5 Additional Lock-Discipline Misuses 45.6 Calculate True Data-Race Sets 47hapter 6 Non-Conforming Misuses Detection Introduction 49.1 Introduction 49.2 Non-Conforming Cases 50.3 Implementation 51hapter 7 Experiments 53.1 Introduction 53.2 Environments 54.3 Refinements 54.4 Methodology 55.5 Experiment Results 56hapter 8 Conclusions and Future Works 68eferences 6