在 GCC 與 LLVM 上實作以 OpenMP 程式為主動態與靜態混 合之 Data Race 偵測

Static and Dynamic Data Race Detection for OpenMP Programs on GCC and LLVM

張家榮(Jia-Zon Chang)

指導教授 ： 廖世偉

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.02358

摘要

近年來,多核心的處理器架構已經被廣為採用並成為業界的主流設 計。為了能夠有效的利用多核心處理器所帶來的效能,多執行緒程式 已經成為軟體開發上的必備的技巧。除了使用 POSIX threads (Pthreads) API 外,簡單、易讀且富有可攜性的多執行緒程式開發標準也被廣泛 的使用,而 OpenMP 便是其中的佼佼者。然而在享受多執行緒程式開 發所帶來的效能地同時卻延伸出一些棘手的問題,其中之一便是 data race。在這篇論文中,我們設計了一個應用在 OpenMP 程式上,動態 與靜態偵測 data race 的工具。

首先,我們利用 GCC 分析並編譯 OpenMP 程式,分析的結果可以 用來減少之後在執行期所需的檢測。接著再利用 LLVM 在透過觀察與 分析程式的行為進行更近一步的偵測。

關鍵字

OpenMP ； GCC ； LLVM ； data race ； 多線程 ； 動態分析 ； 靜態分析

並列摘要

Multicore processors have become mainstream. Therefore, to exploit sil- icon resource effectively, multithreaded programming is critical. In addi- tion to the traditional POSIX threads API, other multithreaded APIs such as OpenMP have been proposed. OpenMP provide an interface that is easy to use, highly reliable, and portable. However, the effective exploitation of re- sources by multithreaded programming comes with cost. For instance, data races result in incorrect execution sometimes and are expensive to be elim- inated. We present a novel data race detection tool to address this cost of multithreaded programming.

Specifically, we develop a plugin for GCC compiler to analyze the OpenMP constructs from the source and compile the OpenMP program. The results from the static analysis can be used to reduce the necessary instrumentation later. Next, we utilize the LLVM compiler infrastructure to observe and ana- lyze the runtime behaviors for further data race detection.

並列關鍵字

OpenMP ； GCC ； LLVM ； data race ； multithread ； dynamic analysis ； static analysis

參考文獻

[6] R. Agarwal and S. Stoller. Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. PADTAD ’06: Proceedings of the 2006 workshop on Parallel and distributed systems: testing and debugging, Jul 2006.

[15] J.-D. Choi, A. Loginov, and V. Sarkar. Static Datarace Analysis for Multithreaded Object-Oriented Programs. Jan 2001.

[16] M. Christiaens and K. D. Bosschere. Accordion Clocks: Logical Clocks for Data Race Detection. Euro-Par 2001 Parallel Processing, 2150:494–503, 2001.

[17] J. W. Cooley and J. W. Tukey. An Algorithm for the Machine Calculation of Com- plex Fourier Series. Mathematics of Computation, 19(90):297–301, 1965.

[18] D. L. Detlefs, K. R. M. Leino, G. Nelson, and J. B. Saxe. Extended Static Checking. Dec 1998.