메시지전달 프로그램의 영향받지 않은 경합조건 탐지를 위한 경합상태 전이기법 = Race State Transition for Detecting Unaffected Race Conditions in Message-Passing Programs

국문 초록 (Abstract)

메시지전달 프로그램에서 발생하는 임의의 메시지경합은 다른 경합의 발생에 영향을 줄 수 있으므로, 효과적인 디버깅을 위해서 영향받지 않은 경합을 탐지하는 것이 중요하다. 이러한 경합을 효율적으로 탐지하기 위한 기존의 기법은 각 프로세스에서 가장 먼저 발생하는 경합의 수신사건에서 수행을 중단하여 경합하는 메시지들을 탐지한다. 그러나 프로세스의 수행 중단은 경합들간에 존재하는 영향관계의 단절을 초래하므로, 탐지된 모든 경합이 영향받지 않은 경합임을 보장하지 못한다. 본 논문은 탐지된 경합의 상태를 프로그램의 수행 종료까지 수신하는 메시지들의 영향 여부에 따라 전이하는 새로운 기법을 제안한다. 본 기법은 경합을 탐지하고 그들간의 영향관계를 프로그램 종료까지 유지하므로, 영향받지 않은 경합만을 효율적으로 탐지한다.

다국어 초록 (Multilingual Abstract)

Detecting unaffected race conditions is important to debugging message-passing programs effectively, because such a message race can affect other races to occur or not. The previous technique to detect efficiently unaffected races detects racing messages by halting at the receive event of the first race to occur in each process. However this technique does not guarantee that all of the detected races are unaffected, because halting such processes does disconnect some chain of affects-relations among those races. In this paper, we present a novel technique that manages the state of the detected race by examining if every received message is affected until the execution terminates. Our technique therefore guarantees to detect efficiently the unaffected races, because it maintains affects-relations of the races all along the execution of program.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 연구 배경
• 3. 영향받지 않은 경합의 탐지
• 4. 실험
• 5. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 Mattern, F, "Virtual Time and Global States of Distributed Systems" Parallel and Distributed Algorithms 215-226, 1989

2 Gropp, W, "User's Guide for Mpich, A Portable Implementation of MPI" (6) : 1996

3 Lamport, L, "Time, Clocks, and the Ordering of Events in a Distributed System" 21 (21): 558-565, 1978

4 Cypher, R, "The Semantics of Blocking and Nonblocking Send and Receive Primitives" 729-735, 1994

5 Damodaran-Kamal, "Testing Races in Parallel Programs with an OtOt Strategy" Int'l Symp. on Software Testing and Analysis 216-227, 1994

6 Gropp, W, "Reproducible Measurements of MPI Performance Characteristics" 11-18, 1999

7 Tai, K. C, "Reachability Testing of Asynchronous Message-Passing Programs" Int'l. Symp. on Software Engineering for Parallel and Distributed Systems 50-61, 1997

8 Tai, K. C, "Race Analysis of Traces of Asynchronous Message-Passing Programs" Distributed Computing Systems 261-268, 1997

9 Geist, A, "PVM: Parallel Virtual Machine," A Users' Guide and Tutorial for Networked Parallel Computing" MIT Press 1994

10 Netzer, R. H. B, "Optimal Tracing and Replay for Debugging Message- Passing Parallel Programs" Supercomputing 502-511, 1992

11 Kranzlmüller, D, "Notes on Nondeterminism in Message Passing Programs" 357-367, 2002

12 Damodaran-Kamal, S. K, "Nondeterminacy: Testing and Debugging in Message Passing Parallel Programs" 28 (28): 118-128, 1993

13 Claudio, A.P, "Monitoring and Debugging Message Passing Applications with MPVisualizer," 376-382, 2000

14 Snir, M, "MPI: The Complete Reference" MIT Press

15 Krammer, B, "MPI Application Development Using the Analysis Tool MARMOT" 464-471, 2004

16 Kranzlmüller, D, "Event Graph Analysis for Debugging Massively Parallel Programs" Kepler University Linz 2000

17 Cypher, R, "Efficient Race Detection for Message-Passing Programs with Nonblocking Sends and Receives" 534-541, 1995

18 Netzer, R. H. B, "Debugging Race Conditions in Message- Passing Programs" 1996

19 Kranzlmüller, D, "Brief Overview of the MAD Debugging Activities" 2000

20 Kilgore, R, ""Re-execution of Distributed Programs to Detect Bugs Hidden by Racing Messages" 423-432, 1997

21 Fidge, C. J, ""Partial Orders for Parallel Debugging" 183-194, 1998