내부적 비결정성을 가진 공유 메모리 병렬 프로그램에서 잠재적 경합탐지를 위한 전처리기 = A Preprocessor for Detecting Potential Races in Shared Memory Parallel Programs with Internal Nondeterminism

국문 초록 (Abstract)

OpenMP와 같은 공유 메모리 기반의 병렬 프로그램에서 발생하는 경합은 프로그래머가 의도하지 않은 비결정적인 수행 결과를 초래하므로 반드시 탐지되어야한다. 이러한 경합의 존재를 수행 중에 검증하는 기존의 기법들은 내부적 비결정성이 존재하지 않는 프로그램에 대해서만 가능하다. 하지만 이 조건을 만족하지 못한다면 경합검증을 위해서 각 임계구역마다 적어도 N! 만큼의 프로그램 수행이 필요하다. 여기서 N은 탐지 대상 프로그램이 가진 최대 병렬성을 의미한다. 본 논문에서는 프로그램 슬라이싱을 이용하여 내부적 비결정성을 가진 프로그램에 존재하는 비결정적 접근사건을 정적으로 분석하고, 이 정보를 이용하여 한번의 수행으로 실제 경합뿐만 아니라 잠재적 경합까지 탐지할 수 있는 경합 전처리기를 제안한다. 제안된 도구는 OpenMP 병렬 프로그램에서 발생할 수 있는 비결정적 접근사건들에 대해서 항상 결정적으로 감시할 수 있으므로 임계구역 가진 프로그램 모델에 적용할 수 있는 어떠한 경합탐지 프로토콜을 사용하더라도 경합 검증이 가능하다. 본 도구의 실험적 증명을 위해서 비결정성이 포함된 합성 프로그램, 공인된 벤치마크 프로그램인 OpenMP Microbenchmark, NAS Parallel Benchmark, 그리고 OpenMP 응용 프로그램을 이용하여 제안된 도구의 정확성을 보인다.

다국어 초록 (Multilingual Abstract)

Races that occur in shared-memory parallel programs such as OpenMP programs must be detected for debugging because of causing unintended non-deterministic results. Previous works which verify the existence of these races on-the-fly are limited to the programs without internal non-determinism. But in the programs with internal non-determinism, such works need at least N! execution instances for each critical section to verify the existence of races, where N is the degree of maximum parallelism. This paper presents a preprocessor that statically analyzes the locations of non-deterministic accesses using program slicing and can detect apparent races as well as potential races through single execution using the analyzed information. The suggested tool can deterministically monitor non-deterministic accesses to occur in OpenMP programs so that this tool can verify the existence of races even if it is used any race detection protocol which can apply to programs with critical section. To prove empirically this tool, we have experimented using a set of benchmark programs such as synthetic programs that involve non-deterministic accesses, OpenMP Microbenchmark, NAS Parallel Benchmark, and OpenMP application programs.

참고문헌 (Reference)

1 Netzer, R. H. B, "What Are Race Conditions? Some Issues and Formalizations" 74-88, 1992

2 Ferrante, J, "The Program Dependence Graph and Its Use in Optimization" ACM 319-349, 1987

3 Jin, H, "The OpenMP Implementation of NAS Parallel Benchmarks and its Performance" NASA Ames Research Center 1999

4 SUN Microsystems Inc, "Sun Studio12: Thread Analyzer User's Guide"

5 Yu, Y, "Race Track: Efficient Detection of Data Race Conditions via Adaptive Tracking" ACM 221-234, 2005

6 Dagum, L, "OpenMP: An Industry-Standard API for Shared-Memory Programming" IEEE 5 (5): 46-55, 1998

7 김영주, "OpenMP 디렉티브 프로그램을 위한 자료경합 검증도구" 한국정보과학회 34 (34): 395-406, 2007

8 Petersen, P, "OpenMP Support in the Intel Thread Checker" 1-12, 2003

9 Jun, Y, "On-the-fly Detection of Access Anomalies in Nested Parallel Loops" ACM 28 (28): 107-117, 1993

10 Praun, C, "Object Race Detection" ACM 70-82, 2001

11 Bull,J.M, "Measuring Synchronisation and Scheduling Overheads in OpenMP" 99-105, 1999

12 O'Callahan, R, "Hybrid Dynamic Data Race Detection" ACM 2003

13 Stefan S, "Eraser: a dynamic data race detector for multithreaded programs" ACM 391-411, 1997

14 Kim, Y, "Effcient Race Verfication for Debugging Programs with OpenMP Directives" Springer 4671 : 230-239, 2007

15 Cheng, G. I, "Detecting Data Races in Cilk Programs that Use Locks" ACM 298-309, 1998

16 Dinning, A, "Detecting Access Anomalies in Programs with Critical Sections" 85-96, 1991

17 Terboven,C, "Comparing Intel Thread Checker and Sun Thread Analyzer" 2007

18 Audenaert,K, "Clock Trees: Logical Clocks for Programs with Nested Parallelism" IEEE 23 (23): 646-658, 1997

19 Dinning, A, "An Empirical Comparison of Monitoring Algorithms for Access Anomaly Detection" ACM 1-10, 1990

20 Kim, Y, "An Empirical Analysis of Intel Thread Checker for Detecting Races in OpenMP Programs" IEEE 409-414, 2008

21 Park,S., "A Comparison of Scalable Labeling Schemes for Detecting Races in OpenMP Programs" Springer-Verlag 2104 : 68-80, 2001