초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

경합은 공유메모리 병렬프로그램의 비결정적인 수행결과를 초래하므로, 디버깅을 위해서 경합탐지는 중요하다. 임계구역을 가진 병렬프로그램을 위한 수행중 경합 탐지 기법은 공유 자료구조를 사용하므로, 매 접근 사건 시에 병목현상을 유발한다. 본 연구에서는 동기화가 있는 병렬프로그램에서 매 반복을 수행할 때마다 공유 자료구조의 접근 횟수를 기껏해야 임계구역의 수에 비례하도록 매 접근사건을 검사한다. 그러므로 이 기법은 수행중 경합탐지의 확장성과 효율성을 제공한다.

경합은 공유메모리 병렬프로그램의 비결정적인 수행결과를 초래하므로, 디버깅을 위해서 경합탐지는 중요하다. 임계구역을 가진 병렬프로그램을 위한 수행중 경합 탐지 기법은 공유 자료구조를 사용하므로, 매 접근 사건 시에 병목현상을 유발한다. 본 연구에서는 동기화가 있는 병렬프로그램에서 매 반복을 수행할 때마다 공유 자료구조의 접근 횟수를 기껏해야 임계구역의 수에 비례하도록 매 접근사건을 검사한다. 그러므로 이 기법은 수행중 경합탐지의 확장성과 효율성을 제공한다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 프로토콜은 매 접근사건의 발생 시마다 접근 역사에 순서적으로 접근해야 하므로 병목현상을 초래한다. 본 논문에서는 매 접근 사건이 최초 경합의 구성 대상인 경우에만 접근 역사를 섭 근 하는 프로토골을 세안한다. 이는 기존의 프로토콜로서 최초 경합을 구성하는 사건을 검사하면, 적어도 하나의 경합 탐지는 보장되기 때문이다.
• 본 논문에서는 탐지 기법 자체를 개선하여 임계구역을 가진 프로二 L 램의 수행 중 경합 탐지 효율성을 높인다. 개선된 탐시 기법의 효율성을 평가하기 위해서, OpenMP 커널 프로二t램을 이용하여 개선된 刃법을 구현하고 二L 효과를 살험하였다.
• 본 절에서는 병목현상을 개선하는 수행 중 탐지를 위해서, 매 접는 사건을 검사하여 각 농기화 블록마다 최대 2개의 접근 사건만 접근 역사에 접근할 수 있도록 하는 선택 사건 알고리즘을 소개한다. 먼저 이를 위해 선택되는 사건인 선댁사건(fihered event)를 소개하고, 선택 사건 알고리즘을 설명한다.
• 수행 중 탐지 기법은 병렬 프로그램 수행 중에 접건■사건의 발생 시마다 공유 자료구조인 접근 익사를 유지하며 논리적인 병행성을 체크하여 경합을 보고한다. 레이블링(labeling)은 수행 중인 각 스레三에 병행성을 식별 가능한 고유한 정보를 할당하는 기법으로서, 접근 역사에 기록될 수 있다.

제안 방법

• 二丄리고 선택 사건 알고리즘은 C언어로 구현하었다. BD 레이블링과 선택사건 알고리즘은 라이브러화하였고, 실험 대상인 OpenMP Fortran 프로二램에 라이브러리 호출코느-를 추가하였다. 대상 프로그램은 커널 프로그램으로 작성하 이 평가하였다.
• 본 논문에서는 탐지 기법 자체를 개선하여 임계구역을 가진 프로二 L 램의 수행 중 경합 탐지 효율성을 높인다. 개선된 탐시 기법의 효율성을 평가하기 위해서, OpenMP 커널 프로二t램을 이용하여 개선된 刃법을 구현하고 二L 효과를 살험하였다. 2장에 서는- 병렬프로二t램의 수행에 관계되는 사항을 설명하고, 기존의 수행 중 경합 탐지 기법이 가진 문제점을 소개한다, 3상에서는 개선된 탐지기법과 알고리즘을 설명하고, 4장에서는 본 논문에서 제안하는 기법의 평가를 위한 실험과 끄결과를 분석 중!■고, 마지막으로 5장에서는 결론을 내린다.
• BD 레이블링과 선택사건 알고리즘은 라이브러화하였고, 실험 대상인 OpenMP Fortran 프로二램에 라이브러리 호출코느-를 추가하였다. 대상 프로그램은 커널 프로그램으로 작성하 이 평가하였다.
• 수행 중 경합 탐지 기법은 모든 접근 사건 발생 시에 병목현상이 유발되기 때문어】, 모든 접근 사건들이 순서적으로 검사되어야 하는 문제점이 있다. 본 연구에서는 OpenMP 병렬 프로그램에서 적용되는 경합 탐지 방법을 제시하였고, 병목현상을 유발하는 접근사건 중에서 경합에 필요한 사건들만 선택함으로써 효율성을 향상시키는 사건 선택 알고리즘과 그 실험적 결과를 보였匸+. 본 기법은 내포되지 않는 임계구역 모델에 제한된 것이므로, 향후 연구과제로는 내포 가능한 임계구역 모델을 위해서 본 기법을 확장할 필요가 있다.

대상 데이터

• 커널 프로二I램은 9개로서, (1) 최대병렬성을 10으로 하고, ⑵ 한 스레드 당 블록 수는 201개, (3) 공유변수는 1개, (4) 블록낭 접근 사건 수는 10, 20, 50 등의 3가지 경우로 하고, ⑸ 선택 증단 사건의 위치는 전체 접근 사건들 중의 1%, 50%, 100% 등에 위치하는 것으로 하였다. 그러므로 각 프로그램의 총 접근 사건 수는 각각 20100, 40200, 100500개이다. 이러한 OpenMP Fortran 커널 프로그램들을 이용하여 3가지 수행 시간을 측정하였다’ 측정한 시간은 (1) 원래 커널 프로그램의 수행 시간, (2) 선택 사건 기법을 적용하지 않고 경합을 탐지한 시간,(3) 사건 선택 기법을 적용하여 경합을 탐지한 시간 등이다.
• 본 논문에서는 공유 메모리를 사용하는 병렬프로그래밍 모델로서 산업 표준인 0penMP[6] Fortran 프로그램을 대상으로 하며, 내포 병렬성이 없이 임계구역을 가질 수 있다. 임계구역 (critical secli<m)(_2] 은 명령문들의 수행 시에 상호배제를 제공하므로, 한순간에 한 스레드만이 수행할 수 있는 동기화된 구역이다, 비임 계구역(non-critical section)은 임계구역에 속하치 않은 스레屯 수행 부분을 뜻한다.

데이터처리

• 본 기법의 효율성을 평가하기 위해서 OpenMP Fortran으로 실험했다. 실험을 위해 레이블링 기법으로는 BD 레이블링 [1]을 사용했고, 프로토콜 기법은 Lock Cover 프로토콜[2]을 사용했다.

이론/모형

• 이러한 경합을 탐지하는 기존의 기법들은 정적분식 기법 (static analyis)[5], 사후 추적 분석 기법 (posl-m()「iem analysis)⑸, 수행 중 분석 기법(on-the-fly analysis)⑸ S의 3종류가 있다. 본 料문에서는 이 세 가지 기법 늘 숭에서 가장 현실적인 기법으로 알려진 수행 중 분석 기법을 사용한다.
• 본 기법의 효율성을 평가하기 위해서 OpenMP Fortran으로 실험했다. 실험을 위해 레이블링 기법으로는 BD 레이블링 [1]을 사용했고, 프로토콜 기법은 Lock Cover 프로토콜[2]을 사용했다. BD 레이블링은 동기화를 가진 병렬 프로그램에서 스레드마다 고유번호를 붙이는 레이블링 기법이고, Lock Cover 프로토콜 기법은 임계구역을 가진 병렬 프로그램에서 경합을 탐지하는 프로토콜이다.

성능/효과

• BD 레이블링은 동기화를 가진 병렬 프로그램에서 스레드마다 고유번호를 붙이는 레이블링 기법이고, Lock Cover 프로토콜 기법은 임계구역을 가진 병렬 프로그램에서 경합을 탐지하는 프로토콜이다. 二丄리고 선택 사건 알고리즘은 C언어로 구현하었다. BD 레이블링과 선택사건 알고리즘은 라이브러화하였고, 실험 대상인 OpenMP Fortran 프로二램에 라이브러리 호출코느-를 추가하였다.
• 이는 기존의 프로토콜로서 최초 경합을 구성하는 사건을 검사하면, 적어도 하나의 경합 탐지는 보장되기 때문이다. 그 결과, 매 스레드를 수행할 때마다 접근 역사의 접근 횟수를 최대 임계〒역의 수에 비계하고, 매 접達사 건의 발생 수와는 무관하게 된다. 예로서, (그림1)의 Thread-2 에서 기존의 수행 중 탐지 기법으로 수행을 했다면 최악의 경우 접근 역사에 8번을 접근해야 하지반, 본 연구 기법으로는 4번의 접근으로 탐지된다.
• 그리고 블록당 접군 사건 수가 많아지고, 선택 중단 사건의 위치 값이 클수록 그 효율성은 낮아진다. 마지막으로, 톤 탐지 기법은 동기화 명령의 횟수에 의존적이지만, 선택 사건 알고리즘을 사용하지 하지 않은 경우와 비교해 볼때 (그림4)에서 보인 바와 같은 높은 효율성을 제공한다.

후속연구

• 본 연구에서는 OpenMP 병렬 프로그램에서 적용되는 경합 탐지 방법을 제시하였고, 병목현상을 유발하는 접근사건 중에서 경합에 필요한 사건들만 선택함으로써 효율성을 향상시키는 사건 선택 알고리즘과 그 실험적 결과를 보였匸+. 본 기법은 내포되지 않는 임계구역 모델에 제한된 것이므로, 향후 연구과제로는 내포 가능한 임계구역 모델을 위해서 본 기법을 확장할 필요가 있다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기