메시지 전달 프로그램에서의 수행 중 경합탐지 = On-the-fly Detection of Race Conditions in Message-Passing Programs

국문 초록 (Abstract)

프로그램에서 발생하는 메시지경합은 프로그램의 비결정적 수행결과를 초래하므로 효과적인 디버깅을 위하여 탐지되어야 한다. 특히 각 프로세스에서 가장 먼저 발생하는 최초경합은 동일한 프로세스 내에서 다른 경합의 발생을 초래할 수 있으므로, 효과적인 경합탐지를 위해서 우선적으로 탐지되어야 한다. 이러한 경합을 탐지하기 위한 기존의 기법들은 적어도 프로그램을 두 번 수행하거나, 메시지들의 수에 비례한 크기의 추적 파일의 분석을 요구한다. 본 논문은 추적파일을 생성하지 않으면서 단 한번의 프로그램 수행으로 각 프로세스에서 발생하는 최초경합을 탐지하는 기법을 제시하고, 실험을 통해서 본 기법이 최초경합을 정확히 탐지함을 보인다.

다국어 초록 (Multilingual Abstract)

races should be detected for debugging message-passing parallel programs because they can cause non-deterministic executions. Specially, it is important to detect the first race in each process because the first race can cause the occurrence of the other races in the same process. The previous techniques for detecting the first races require more than two monitored runs of a program or analyze a trace file which size is proportional to the number of messages. In this paper we introduce an on-the-fly technique to detect the first race in each process without generating any trace file. In the experiment we test the accuracy of our technique with some benchmark programs and it shows that our technique detects the first race in each process in all benchmark programs.

참고문헌 (Reference)

1 "and the Ordering of Events in a Distributed System Communications of the ACM" 558-565,

2 "The Semantics of Blocking and Nonblocking Send and Receive Primitives" 729-735,

3 "Testing Races in Parallel Programs with an OtOt Strategy" 216-227, 1994

4 "Reproducible Measurements of MPI Performance Characteristics" Springer-Verlag 1697 : 11-18, 1999.9

5 "Re-execution of Distributed Programs to Detect Bugs Hidden by Racing Messages" 1 : 423-432, 1997.1

6 "Race Analysis of Traces of Asynchronous Message-Passing Programs" 261-268, 1997.5

7 "Partial Orders for Parallel Debugging SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging" 183-194

8 "Optimal Tracing and Replay for Debugging Message- Passing Parallel Programs" (v) : 502-511, 1992

9 "Notes on Nondeterminism in Message Passing Programs" Springer-Verlag 2474 : 357-367, 2002.9

10 "Monitoring and Debugging Message Passing Applications with MPVisualizer" IEEE 376-382, 2000.1

11 "MPI: The Complete Reference" MIT Press 1996

12 "MPI Run Time Error Detection Test Suites" 2006

13 "MPI Application Development Using the Analysis Tool MARMOT" Springer-Verlag 3038 : 464-471, 2004.6

14 "Efficient Race Detection for Message-Passing Programs with Nonblocking Sends and Receives" 534-541, 1995.10

15 "Detecting Unaffected Race Conditions in Message-Passing Programs" Springer-Verlag 3241 : 268-276, 2004.9

16 "Detecting Unaffected Message Races in Parallel Programs" Springer-Verlag, Taichung, Taiwan 3947 : 187-196, 2006.5

17 "Debugging Race Conditions in Message-Passing Programs" 31-40, 1996.5

18 "A Users' Guide and Tutorial for NetworkedParallel Computing" MIT Press 1994

19 "A Brief Overview of the MAD Debugging Activities" 2000.8