[논문]멀티 스레딩 기반 병렬 프로그램의 효과적인 디버깅을 위한 추상적 시각화

김영주

doi:10.6109/jkiice.2016.20.3.549

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

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.20 no.3, 2016년, pp.549 - 557

김영주 (Embedded SW Research Department, Electronics and Telecommunications Research Institute)

초록
AI-Helper

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

Abstract ▼ AI-Helper

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.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 내포병렬성과 임계구역을 가지는 OpenMP 병렬 프로그램을 대상으로 하여 탐지된 최초 경합 정보와 프로그램 런타임 수행정보를 효과적으로 시각화하기 위해서, 스레드간의 병행성 관계를 표현하는 Partial Order Execution Graph (POEG)[16, 17]을 효과적으로 시각화하는 추상화 도구를 제안한다. 이 도구에서는 프로그램 수행 중에 최초경합에 참여하는 접근 사건들만을 병목현상이 없이 탐지하여 프로그램 수행정보와 함께 보고하는 수행중 경합탐지(on-the-fly race detection) 기법[4-7, 16]에서 보고되는 정보의 공간적 복잡성을 줄이기 위해서 최초경합과 관련된 정보만을 선택하는 수행중 추적선택 (on-the-fly trace filtering) 기법과 선택된 정보를 이용하여 시각적 복잡성을 줄이기 위한 그래프 추상화(graph abstraction) 기법인 내포병렬성 추상화와 임계구역 추상화 기법 등을 적용한다.
본 논문에서는 내포병렬성과 임계구역을 가지는 OpenMP 프로그램을 대상으로 최초경합 탐지정보와 프로그램 수행정보를 효과적으로 시각화하기 위해서, 스레드간의 병행성 관계를 표현하는 POEG을 추상적으로 시각화하는 도구를 제안하였다. 이 도구에서는 프로그램 수행 중에 경합에 참여하는 접근사건들만을 병목현상이 없이 선택하여 최초경합을 탐지하여 프로그램 수행정보와 함께 저장하고, 추적되는 정보의 공간적 복잡성을 줄이기 위해서 최초경합과 관련된 시각화 정보만을 선택하며, 선택된 정보를 이용하여 시각적 복잡성을 줄이기 위해서 내포병렬성 추상화와 임계구역 추상화를 위한 그래프 추상화를 적용한다.
본 절에서는 내포병렬성과 임계구역을 가지는 OpenMP 프로그램을 대상으로 최초경합 탐지정보와 프로그램 수행정보를 추상적으로 시각화하는 도구를 제안한다. 이 도구에 전체적인 구조는 그림 3과 같다.

제안 방법

추상화는 대상이 되는 부분그래프를 추상적 노드로 대체함으로써 가능하고, 추상화된 노드들을 다시 추상화하거나 원래의 그래프로 복원할 수도 있어서 그래프 추상의 확대 및 축소가 모두 가능하다. 그리고 시각화된 각 노드들을 세 가지 수행상태 집합(past, present, future)으로 관리하여 일보 전후진과 같은 순차 디버거 기능에 대응되는 기능을 제공한다. 그러나 이 도구는 임계구역, 최초경합 등과 관련된 추상적 시각화를 모두 제공하지 못하며, 여전히 공간적 복잡성이 크다는 단점이 있다.
이 도구에 전체적인 구조는 그림 3과 같다. 본 도구는 프로그램 수행중에 발생하는 수행정보를 기반으로 최초경합에 참여하는 접근사건들만을 병목현상없이 선택하고 선택된 접근사건들을 기반으로 최초경합을 탐지하는 수행중 경합 탐지기 (Race Detector)와 보고되는 정보의 공간적 복잡성을 줄이기 위해서 최초 경합과 관련된 시각화 정보만을 선택하여 시각화하는 추상적 시각화기 (Abstract Visualizer)로 구성된다. 시각적 복잡성을 줄이기 위해서 그래프 추상화(graph abstraction) 기법인 내포병렬성 추상화와 임계구역 추상화 기법을 제안한다.
본 절에서는 대상 프로그램 모델인 OpenMP 프로그램과 프로그램의 수행구조를 표현하는 그래프[16, 17]를 이용하여 경합과 최초경합에 대한 개념을 설명하고, 이러한 공유메모리 병렬프로그램의 수행시각화를 위한 기존의 대표적인 도구들[12, 15, 18]을 소개하고 문제점을 분석한다.
본 도구는 프로그램 수행중에 발생하는 수행정보를 기반으로 최초경합에 참여하는 접근사건들만을 병목현상없이 선택하고 선택된 접근사건들을 기반으로 최초경합을 탐지하는 수행중 경합 탐지기 (Race Detector)와 보고되는 정보의 공간적 복잡성을 줄이기 위해서 최초 경합과 관련된 시각화 정보만을 선택하여 시각화하는 추상적 시각화기 (Abstract Visualizer)로 구성된다. 시각적 복잡성을 줄이기 위해서 그래프 추상화(graph abstraction) 기법인 내포병렬성 추상화와 임계구역 추상화 기법을 제안한다.

이론/모형

본 논문에서는 내포병렬성과 임계구역을 가지는 OpenMP 병렬 프로그램을 대상으로 하여 탐지된 최초 경합 정보와 프로그램 런타임 수행정보를 효과적으로 시각화하기 위해서, 스레드간의 병행성 관계를 표현하는 Partial Order Execution Graph (POEG)[16, 17]을 효과적으로 시각화하는 추상화 도구를 제안한다. 이 도구에서는 프로그램 수행 중에 최초경합에 참여하는 접근 사건들만을 병목현상이 없이 탐지하여 프로그램 수행정보와 함께 보고하는 수행중 경합탐지(on-the-fly race detection) 기법[4-7, 16]에서 보고되는 정보의 공간적 복잡성을 줄이기 위해서 최초경합과 관련된 정보만을 선택하는 수행중 추적선택 (on-the-fly trace filtering) 기법과 선택된 정보를 이용하여 시각적 복잡성을 줄이기 위한 그래프 추상화(graph abstraction) 기법인 내포병렬성 추상화와 임계구역 추상화 기법 등을 적용한다.
하지만, 프로그램 코드로 스레드간의 병렬성과 내포병렬성 여부들을 직관적으로 파악하기 쉽지 않다. 이러한 문제를 해결하기 위한 방법 중의 하나가 방향성이 있는 비순환 그래프인 Partial Order Execution Graph (POEG)[16, 17]를 이용하는 것이다. 이 그래프를 이용하면 병렬 프로그램의 경합과 병렬루프 내에 다른 병렬루프를 가질 수 있는 내포병렬성을 표현할 수 있으므로 직관적으로 프로그램의 수행 양상을 볼 수 있다.

성능/효과

따라서, 논문에서 제시한 경합 시각화 도구는 수행중 경합탐지기와 추상적 시각화기를 통해서 사용자가 보다 효과적으로 병렬프로그램에 대한 구조적 파악할 수 있는 시각화 정보를 제공할 수 있다.

후속연구

향후과제로는, 보다 효과적인 추상적 시각화를 위해서 병행 수행되는 스레드들의 수에 대한 제약 없이 시각화 할 수 있도록 스레드를 선택할 수 있는 기법을 추가하고, 사용자의 편리를 위해 소스 프로그램과 시각화 내용을 연동하는 사용자 인터페이스를 개발하는 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	OpenMP란 무엇인가?	OpenMP[1]는 공유메모리 병렬프로그램을 위한 산업표준 프로그램 모델이다. 하지만 OpenMP 병렬프로그램에서 발생하는 오류를 수정하는 것은 어렵다.
	추상적 시각화기의 구성은?	추상적 시각화기는 추적선택기, 그래프 추상화기, 그리고 그래프 생성기로 구성되어 있다. 프로그램의 수행을 시각적으로 표현하기 위해서는 정보의 수집이 필수적이다.
	OpenMP 병렬프로그램에서 발생하는 오류를 수정하는 것이 어려운 이유는?	하지만 OpenMP 병렬프로그램에서 발생하는 오류를 수정하는 것은 어렵다. 왜냐하면 OpenMP 프로그램은 동일한 입력에 대하여 프로그램의 매 수행 시에 의도되지 않은 결과를 나타내는 비결정적인 수행을 초래할 수 있기 때문이다. 이러한 비결정적인 수행의 주된 원인이 되는 경합(race)[2-4]은 병행 수행되는 스레드들간에 동기화 없이 적어도 하나의 쓰기 사건으로 동일한 공유변수에 접근할 때 발생하는 것으로, OpenMP 프로그램의 디버깅을 위해서 반드시 탐지되어야 한다.

참고문헌 (22)

OpenMP Architecture Review Board, "OpenMP Application Programming Interface," Version 4.5, Nov. 2015.
C. E. McDowell, and D. P. Helmbold, "Debugging Concurrent Programs," Computing Surveys, vol. 21, no. 4, pp. 593-622, Dec. 1989.

상세보기
R. H. B. Netzer, and B. P. Miller, "What Are Race Conditions? Some Issues and Formalizations," ACM Letters on Programming Language and Systems, vol. 1, no. 1, pp. 74-88, March 1992.

상세보기
Y. J. Kim, S. J. Song, and Y. K. Jun, "VORD: A Versatile On-the-fly Race Detection Tool in OpenMP Programs," International Journal of Parallel Programming, vol. 42, no. 6, pp. 900-930, Dec. 2014.

상세보기
J. Kim, and Y. K. Jun, "Scalable On-the-fly Detection of the First Races in Parallel Programs," in Proceeding of 12nd Int'l Conf. on Supercomputing, pp. 345-352, ACM, Melbourne, Australia, July 1998.
K. Ha, Y. K. Jun, and K. Yoo, "Efficient on-the-fly detection of first races in nested parallel programs," in Proceeding of Workshop on State-of-the-Art in Scientific Computing, pp. 75-84, 2004.
Y. K. Jun, and C. E. McDowell, "On-the-fly Detection of the First Races in Programs with Nested Parallelism," in Proceeding of 2nd Int'l Conf. on Parallel and Distributed Processing Techniques and Applications, pp. 1549-1560, CSREA, August 1996.
Y. K. Jun, and C. E. McDowell, "Scalable Monitoring Technique for Detecting Races in Parallel Programs," in Proceeding of 5th Int'l Workshop on High-Level Parallel Programming Models and Supportive Environments, pp. 340-347, IEEE, Cancun, Mexico, May 2000.
B. Kuhn, P. Petersen, and E. O'Toole., "OpenMP versus Threading in C/C++," Concurrency and Computation: Practice and Experience, vol. 12, no. 12, pp. 1165-1176, May 2000.

상세보기
D. Citron, D. G. Feitelson, and I. Exman, "Parallel Activity Roadmaps," in Proceeding of Int'l Conf. on Parallel Computing, pp. 593-596, Elsevier Science, 1994.
D. Kim, and Y. Jun, "An Effective Tool for Debugging Races in Parallel Programs," in Proceeding of 3rd Int'l Conf. on Parallel and Distributed Processing Techniques and Applications, pp. 117-126, CSREA, Las Vegas, Nevada, July 1997.
D. Zernik, M. Snir, and D. Malki, "Using Visualization Tools to Understand Concurrency," Software, vol. 9, no. 3, pp. 87-92, IEEE, May 1992.

상세보기
E. Kraemer, and J. T. Stasko, "The Visualization of Parallel Systems: An Overview," Journal of Parallel and Distributed Computing, vol. 18, no. 2, pp. 105-117, June 1993.

상세보기
J. Garcia, and R. Hughey, "Scalable Visualization of Parallel Systems," Technical Report, 1994.
S. Utter-Honig, and C. M. Pancake, "Graphical Animation of Parallel Fortran Programs," in Proceeding of Supercomputing, pp. 491-500, ACM/IEEE, Nov. 1991.
A. Dinning, and E. Schonberg, "Detecting Access Anomalies in Programs with Critical Sections," in Proceeding of 2nd Workshop on Parallel and Distributed Debugging, pp. 85-96, ACM, May 1991.
A. Dinning, and E. Schonberg, "An Empirical Comparison of Monitoring Algorithms for Access Anomaly Detection," in Proceeding of 2nd Symp. on Principles and Practice of Parallel Programming, pp. 1-10, ACM, March 1990.
D. P. Helmbold, C. E. McDowell, and J. Wang, TraceViewer: A Graphical Browser for Trace Analysis, TR-90-59, UCSC, 1990.
IEEE, Draft Standard for Information Technology: Portable Operating System Interface (POSIX), IEEE and The Open Group, 2008.
Message Passing Interface Forum, MPI: A Message-Passing Interface Standard, version 3.1, the University of Tennessee, June 2015.
L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Comm. of the ACM, vol. 21, no. 7, pp. 558-565, ACM, July 1978.

상세보기
Y. Kim, S. Lee, M. Park, S. Kim, S. Park, and Y. Jun, "Scalable Monitoring Technique for Detecting Races in Parallel Programs with Locking," in Proceeding of Parallel Processing Systems, vol. 11, no.2, pp. 44-53, KISS, Sep. 2000.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증