멀티 스레딩 기반 병렬 프로그램의 효과적인 디버깅을 위한 추상적 시각화 = Abstract Visualization for Effective Debugging of Parallel Programs Based on Multi-threading

국문 초록 (Abstract)

효과적인 시각화는 일반적으로 대용량의 디버깅 정보와 프로그램의 추상적 수행모델을 표현하는 것이 중요하다. 본 논문에서는 스레드들간의 논리적 병행성 관계를 나타내는 부분순서 수행그래프를 이용하여 내포병렬성과 임계구역을 가진 OpenMP 병렬 프로그램의 수행양상과 경합정보의 효과적 디버깅을 위해서 효과적으로 제공하는 추상적 시각화 도구를 제안한다. 본 도구는 수행중 추적선택 기법으로 시각화 정보를 위한 공간적 복잡성을 줄이고, 추적된 시각화 정보에 프로그램의 내포병렬성과 임계구역 동기화를 위한 그래프 추상화를 제공하여 시각적 복잡성을 해결한다. 그래프 추상화를 통한 스레드들간의 부분순서 관계와 경합탐지 정보는 프로그램의 제어흐름과 경합의 위치를 구조적으로 파악할 수 있게 하므로 프로그램 수행의 이해와 경합 탐지 및 수정에 효과적이다.

다국어 초록 (Multilingual Abstract)

It is important for effective visualization to summarize not only a large amount of debugging information but also the mental models of abstract ideas. This paper presents an abstract visualization tool which provides effective visualization of thread structure and race information for OpenMP programs with critical sections and nested parallelism, using a partial order execution graph which captures logical concurrency among threads. This tool is supported by an on-the-fly trace-filtering technique to reduce space complexity of visualization information, and a graph abstraction technique to reduce visual complexity of nested parallelism and critical sections in the filtered trace. The graph abstraction of partial-order relation and race information is effective for understanding program execution and detecting to eliminate races, because the user can examine control flow of program and locations of races in a structural fashion.

참고문헌 (Reference)

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

2 Y. J. Kim, "VORD: A Versatile On-the-fly Race Detection Tool in OpenMP Programs" 42 (42): 900-930, 2014

3 D. Zernik, "Using Visualization Tools to Understand Concurrency" IEEE 9 (9): 87-92, 1992

4 D. P. Helmbold, "TraceViewer:A Graphical Browser for Trace Analysis" UCSC 1990

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

6 E. Kraemer, "The Visualization of Parallel Systems : An Overview" 18 (18): 105-117, 1993

7 J. Garcia, "Scalable Visualization of Parallel Systems" 1994

8 J. Kim, "Scalable On-the-fly Detection of the First Races in Parallel Programs" ACM 345-352, 1998

9 Y. Kim, "Scalable Monitoring Technique for Detecting Races in Parallel Programs with Locking" KISS 11 (11): 44-53, 2000

10 Y. K. Jun, "Scalable Monitoring Technique for Detecting Races in Parallel Programs" IEEE 340-347, 2000

11 D. Citron, "Parallel Activity Roadmaps" Elsevier Science 593-596, 1994

12 B. Kuhn, "OpenMP versus Threading in C/C++" 12 (12): 1165-1176, 2000

13 OpenMP Architecture Review Board, "OpenMP Application Programming Interface, Version 4.5"

14 Y. K. Jun, "On-the-fly Detection of the First Races in Programs with Nested Parallelism" CSREA 1549-1560, 1996

15 Message Passing Interface Forum, "MPI: A Message-Passing Interface Standard, version 3.1"

16 S. Utter-Honig, "Graphical Animation of Parallel Fortran Programs" ACM/IEEE 491-500, 1991

17 K. Ha, "Efficient on-the-fly detection of first races in nested parallel programs" 75-84, 2004

18 IEEE, "Draft Standard for Information Technology: Portable Operating System Interface (POSIX)"

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

20 C. E. McDowell, "Debugging Concurrent Programs" 21 (21): 593-622, 1989

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

22 D. Kim, "An Effective Tool for Debugging Races in Parallel Programs" CSREA 117-126, 1997