|
병렬 계산의 분야에서는
"병렬 계산은 장래적으로는 각광을 받는다. 언제가 되어도 장래적으로" 등이라고 말 해지기도 합니다. 이것은 최근 수십 년에
있어 진실했습니다. 같은 일은 컴퓨터 아키텍쳐의 업계에도
있어 프로세서 클락의 고속화는 곧바로 한계에 이른다고 언제나 말해지고 있습니다만 실제로는 지금도
고속화가 계속 되고 있습니다. 멀티 코어 혁명은 이러한 병렬처리 분야에서의 낙관과 아키텍쳐 분야에서의 비관의 충돌이라고 말할 수 있습니다.
주요한 CPU 벤더는 클락 속도의 증가로부터 멀티 코어 프로세서에
의한 on-chip로의 병렬처리 지원의 제공으로 방향성을 바꾸고 있습니다. 생각은 단순하고 하나의 칩에 복수의 CPU 코어를 탑재하자고
하는 것입니다. 이것에 의해 하나개의 프로세서에 2개의
코어를 탑재하고, 시스템을 듀얼 프로세서 컴퓨터와
같이 동작시킬 수 있습니다. 게다가 하나의 프로세서에 4개의
코어를 탑재하면 시스템은 네 번째 프로세서와 같이 동작합니다. 이 방법에 의해 CPU 벤더는 고속화를 진행시키는 가운데의 기술적인 벽을 피하면서도 보다 퍼포먼스의 높은 프로세서를 제공할 수 있습니다.
여기까지는 훌륭한 일인 것 같이 들립니다만 어플리케이션이 멀티 코어를 활용하지 않으면 동작은 완전히 빨라지지
않습니다. 여기서 OpenMP의
등장입니다. OpenMP에 의해 C++ 개발자는 multi-thread 어플리케이션을 보다 재빠르게
작성할 수 있습니다.
OpenMP는 대규모이고 기능 풍부한 API 이기 때문에 이것에 대해 하나의 기사로 말하는 것은 매우 곤란합니다.
이 때문에 이 기사에서는 도입으로서OpenMP 의 여러 가지 기능을 사용해 multi-thread 어플리케이션을
재빠르게 작성하는 방법을 소개합니다. 상세한 것에 대하여는 OpenMP Web site (영어)에서 읽기 쉬운 사양이 입수 가능합니다.
Visual C++에서의
OpenMP의 유효화
OpenMP 표준은 1997년에
포터블한 multi-thread 어플리케이션을 작성하기
위한 API로서 정해졌습니다. 처음은 Fortran 베이스의 표준이었지만 뒤에 C 및 C++를 포함하도록 확장되었습니다. 현재의 버전은 OpenMP
2.0 입니다. Visual C++ 2005는 이 표준을 완전하게 지원 합니다. OpenMP는 또 Xbox
360 플랫폼에서도 지원 됩니다.
코드의 상세한 설명에 들어가기 전에 컴파일러로의 OpenMP 기능의 유효화에 대해 설명합니다. Visual
C++ 2005에서는 컴파일러가 OpenMP 지시문을 해석할 수 있도록 하는 /openmp
컴파일러 스윗치가 새롭게 제공되고 있습니다.(또, 프로젝트의 프롭퍼티 페이지에서도 OpenMP
지시문을 유효하게 할 수 있습니다. [구성
프롭퍼티], [C/C++], [
언어] 라는 것을 클릭하여 [OpenMP 서포트] 프롭퍼티를 변경합니다.) /openmp 스윗치가 호출 된 경우 컴파일러는 심볼 _OPENMP 를 정의합니다. 이것은 #ifndef _OPENMP를 사용해 OpenMP가 유효하게 되고 있는 것을 검출하는데 사용됩니다.
OpenMP는 임포트
라이브러리 vcomp.lib에 의해서 어플리케이션에
링크됩니다. 대응의 런타임 라이브러리는 vcomp.dll 입니다. 이 임포트 라이브러리 및 런타임 라이브러리의 디버그 버전(각각 vcompd.lib 과 vcompd.dll)에는 특정의 부정한 조작 때에 발생하는 추가의 에러 메세지가 있습니다. Visual C++은 OpenMP 런타임의 정적 링크는 지원 하고 있지 않는 것에
주의해 주세요. 다만 Xbox 360에서는 정적 링크가
지원 됩니다.
OpenMP로의 병렬처리
OpenMP 어플리케이션은 우선 하나의 스레드 즉 마스터 스레드로부터 작성합니다. 프로그램을 실행하면 어플리케이션은 마스터 스레드가 스레드 팀(마스터 스레드도
포함한다) 를 작성하는 병렬 영역에 들어갑니다. 병렬 영역이 끝나면 스렛드
팀은 정지 하고 마스터 스레드가 실행을 계속합니다. 하나의
병렬 영역에는 네이스트 된 복수의 병렬 영역이 존재할 수 있습니다. 네이스트 된 병렬 영역에서는 원래의 병렬 영역의 각 스레드가 스레드 팀의 마스터가 됩니다. 네이스트 된 병렬처리는 한층 더 다른 병렬 영역을 네이스트 할 수 있습니다.
그림
1 OpenMP 의 병렬 섹션
그림 1 에 OpenMP의 병렬처리의 동작을 나타냅니다. 가장 왼쪽의 황색 선이 마스터 스레드입니다. 이 스레드는 1의
포인트로 최초의 병렬 영역이 시작될 때까지는 싱글 스레드
어플리케이션으로서 실행됩니다. 병렬 영역에 들어가면 마스터 스레드가
스레드 팀(황색 및 오렌지색의 선으로 구성된다)을 작성합니다. 이러한 스레드는
모두 동시에 병렬 영역에서 실행됩니다.
2의 포인트에서는 병렬 영역에서 실행되고 있는 4개의 스레드 중 3개의 스레드가
새로운 스레드 팀(핑크색, 녹색, 청색)을 네이스트 된 병렬 영역에 작성합니다. 팀을 작성한 황색 및 오렌지의
스레드는 각각 자신의 팀의 마스터입니다. 각 스레드는 새로운 팀을 각각 다른 시점에서 작성할 수 있는 것에 주의해 주세요. 이것을 할 수 없으면 병렬 영역이 네이스트 될 것은 없습니다.
3 의 포인트에서 병렬 영역은 종료합니다. 네이스트 된 병렬 영역은 각각 그 영역 내의 스레드를 동기
합니다만 다른 영역과는 동기 되지 않는 것에 주의해 주세요. 4의 포인트에서는 최초의 병렬 영역이
종료하고 5의 포인트에서는 또 새로운 병렬 영역이 개시하고 있습니다. 5의 포인트가 새로운 병렬 영역에서는 각 스레드의 스레드 로컬 데이터는 앞의 병렬 영역으로부터 지속하고 있습니다.
이것으로 실행 모델의 기본적 이해를 얻을 수 있었다고 생각합니다. 여기에서
실제로 병렬 어플리케이션의 작성에 관한 설명에 들어갑니다.
OpenMP 의 구성
OpenMP는 사용하기 쉽고 단 2개의
기본적인 구성체, 프라그마 및 런타임 루틴으로 구성됩니다. OpenMP 프라그마는
통상 코드의 섹션을 병렬화하도록 컴파일러에 지시합니다. 모든 OpenMP 프라그마는 #pragma omp로
시작됩니다. 어느 프라그마의 경우에서도 이러한 지시문은 그 기능 여기에서는 OpenMP를
지원 하고 있지 않는 컴파일러에서는 무시됩니다.
OpenMP 런타임 루틴은 주로 환경에 관한 정보를 설정 및
취득하기 위해서 사용됩니다. 또 동기의 특정의 타입용의 API도
있습니다. OpenMP 런타임의 함수를 사용하려면
프로그램에서 OpenMP 헤더 파일 omp.h를 인클루드
할 필요가 있습니다. 어플리케이션이 프라그마만을 사용하는
경우는 omp.h를 생략 할 수 있습니다.
OpenMP 에 의해서 어플리케이션에 병렬처리를 추가하는 것은
간단하고 프라그마를 추가하고 필요한 경우에는 OpenMP 런타임으로부터 OpenMP 함수를 호출할 뿐입니다. 이러한 프라그마에는 다음의 형식이 사용됩니다.
#pragma omp <directive> [clause[
[,] clause]...]
지시문에는
parallel, for, parallel for, section, sections, single, master, critical,
flush, ordered 및 atomic이 들어갑니다. 이러한
지시문은 워크 쉐어링 또는 동기의 구성체의 어느 쪽인가를 지정합니다. 이 기사에서는 이러한
지시문의 대부분에 임해서 설명합니다.
구는 지시문의
옵션의 수식자로 지시문의 동작에 영향을 줍니다. 지시문에는 다양한 구를 조합해 사용할 수 있습니다. 또 5개의 지시문(master,
critical, flush, ordered 및
atomic) 은 구를 사용하지 않습니다.
병렬처리의 지정
많은 지시문이
있습니다만 조금씩 시작합시다. 가장 자주 사용되고 한편 중요한 지시문은 parallel 입니다. 이 지시문은 디렉티브의
뒤에 계속 되는 구조화 블록의 동적 범위를 나타내는 병렬 영역을 작성합니다. 예를 들어 다음과 같이
됩니다.
#pragma omp parallel [clause[ [, ]clause] ...]
structured-block
이 지시문은, 구조화 블록이 복수의 스레드로 병렬에 처리되는 것을 컴파일러에게
전합니다. 각 스레드는 같은 명령 스트림을 실행합니다만 명령의 같은 세트일 필요는 없습니다. 이것은 if-else 등의 제어 플로우 스테이트먼트에 의해서 정해집니다.
여기서 친숙한 "Hello World" 프로그램의
샘플을 나타냅니다.
#pragma omp parallel
{
printf("Hello
World\n");
}
2개의 프로세서의 경우 다음과 같은 출력이 되는 것을 기대하겠지요.
Hello World
Hello World
그러나 다음과 같이 될 가능성도 있습니다.
HellHell oo WorWlodrl
d
2번째의 출력은 2개의
스레드가 병렬로 실행되어 그 양쪽 모두가 동시에 출력하려고 한 결과입니다. 복수의 스레드가 하나의 공유 자원(이 경우의 공유 자원은 콘솔 윈도우) 를 읽어 들이거나 변경하거나 하는 경우 경합 상태가 발생할 가능성이 있습니다. 이것은 어플리케이션 중에서는 비결정적인 버그가 되어 찾아내는 것이 곤란하게 되는 경우도 있습니다. 프로그래머는 이러한 버그가 발생하지 않게 할 필요가 있습니다. 통상은
락을 사용하던지 또는 가능한 한 공유 자원을 피합니다.
다음으로 좀 더 도움이 되는 샘플을 소개합니다. 하나의 배열에
포함된 2개의 값의 평균을 계산해 그 값을 다른 배열에 세트 합니다. 여기에서는 새로운 OpenMP의
구성체 #pragma omp
for를 사용합니다. 이것은 워크 쉐어링
지시문입니다. 워크 쉐어링 지시문은 병렬처리를 작성하는 것이 아니라 스레드 팀을 논리적으로 분배해 뒤에서 계속 되는 제어 플로우의
구성체를 구현합니다. #pragma omp for 워크 쉐어링 지시문은 이하의 코드에 나타내는 for 루프가 병렬 영역으로부터
불려 갔을 경우 반복을 스레드 팀에서 분할하는 것을 OpenMP에게 전합니다.
#pragma omp parallel
{
#pragma omp for
for(int i = 1; i < size; ++i)
x[i]
= (y[i-1] + y[i+1])/2;
}
이 케이스로 size의
값을 100으로 하고 4 개의 프로세서를 탑재하는 컴퓨터로
실행하면 루프의 반복은 프로세서 1에 반복의 1 ~ 25, 프로세서 2에 반복의 26 ~ 50, 프로세서 3에 반복의 51 ~ 75, 그리고 프로세서 4에 반복의 76 ~ 99이 각각 할당할 수 있습니다. 이것은 스케줄링 폴리시가
static 스케줄링인 것을 전제로 합니다. 스케줄링 폴리시에 대해서는 이 기사의 다음에 상세하게 설명합니다.
이 프로그램에서는 명시적이 아닙니다만 병렬 영역의 마지막에는 바리어
동기가 있습니다. 모든 스레드는 마지막 스레드가 완료할 때까지 여기서 블록 됩니다.
이하와 같이 앞에 나타낸 코드의 #pragma
omp for를 사용하지 않으면 스레드가
각각 for 루프 전체를 실행하므로 각 스레드의 처리는
장황하게 됩니다.
#pragma
omp parallel //
아마 의도적인 것은 아니다
{
for(int i = 1; i
< size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
병렬 루프는 가장 자주 사용되는 병렬화 가능한 워크 쉐어링의 구성체이므로 OpenMP에는 #pragma omp
parallel의 뒤에 #pragma omp for를 기술하는 생략 형식이 제공되고 있습니다. 다음과
같이 됩니다.
#pragma omp parallel for
for(int i = 1; i < size; ++i)
x[i]
= (y[i-1] + y[i+1])/2;
여기서 루프 반송 의존이 없는 것에 주의해 주세요. 즉, 루프 1개의
반복이 그 루프의 다른 반복에 의존하고 있지 않습니다. 예를 들어 다음의 2개의 루프에는 루프 반송 의존의 특성이 2개 있습니다.
for(int i = 1; i <= n; ++i)
//
루프 (1)
a[i]
= a[i-1] + b[i];
for(int i = 0; i < n; ++i)
//
루프 (2)
x[i]
= x[i+1] + b[i];
루프 1을 병렬처리 하는 데는 문제가 있습니다. 루프 i 의 반복을 실행하기 위해서 i-1의 결과를 취득할 필요가 있기 때문에입니다. i의 반복은 i-1의 반복 해에 의존합니다. 루프 2를 병렬처리 하는 것도 문제입니다. 정확히 이유는 다릅니다. 이 루프에서는 x[i-1]의 값을 계산하기 전에 x[i]
를 계산할 수 있습니다. 그러나 x[i] 를
계산하면 x[i-1]의 값이 바뀌어 버립니다. i-1의
반복은 i의 반복 해에 의존합니다.
루프를 병렬처리 하는 경우는 루프의 반복에 의존관계(dependencies)가
존재하지 않게 합니다. 루프의 반복에 의존이 없는 경우 컴파일러는 그 루프를 어떠한 순서에서도 즉
병렬에 실행할 수 있습니다. 이것은 컴파일러에서는 체크되지 않는 중요한 요건입니다. 사실상 개발자가 병렬처리 되는 루프에는 루프 반송 의존이 포함되지 않는 것을 컴파일러에 단언할 수 밖에
없습니다. 루프가 의존관계(dependencies)를
가지는 경우에 컴파일러에 병렬처리를 하도록 설정하면 컴파일러는 설정된 대로 실행해 최종적으로 잘못된 결과가 되어 버립니다.
이외에도 OpenMP에서는 #pragma omp for 또는 #pragma omp parallel for의 블록 내에서 가능한 for 루프의
형식에 제한이 있습니다. 루프는 다음의 형식일 필요가 있습니다.
for([integer type] i
= loop invariant value;
i
{<,>,=,<=,>=} loop invariant value;
i
{+,-}= loop invariant value)
이것은 OpenMP가 루프의 최초에서 루프가 실행하는 반복의 회수를 판단하기 위해서 필수입니다.
OpenMP 와 Win32 스레드의 비교
앞에 나타낸 #pragma omp parallel for의
샘플과Windows API를 사용해 스레드화 하기
위해 필요한 일을 비교해 보고 알 수 있는 것이 몇 개인가 있습니다. 그림 2 로부터 같은 결과를 얻기 위해서보다 많은 코드가 필요하다라고 하는
것을 압니다. 또, 여기에는 수면 아래에서 행해지는 트릭과
같은 것도 존재합니다. 예를 들어 ThreadData의 constructor는 스레드
호출할 것에 개시와 종료를 계산합니다. OpenMP는
이러한 상세를 자동적으로 처리합니다. 게다가 프로그래머가 병렬 영역 및 코드의 구성을 조정하는 것도
가능하게 합니다.
공유 데이터와 프라이빗 데이터
병렬 프로그램을 작성할 때는 퍼포먼스의 향상을 위해서 뿐만이 아니고 정상적인 처리를 하듯이 하기 위해서 어느 데이터가 공유되어 어느
데이터가 프라이빗이 되는지를 이해해 두는 것이 매우 중요합니다.
OpenMP는 이 구별을 프로그래머에게는 확실하게 나타내 보입니다. 또 수동으로 조작할 수도 있습니다.
공유 변수는 스레드 팀의 모든 스레드로 공유됩니다. 즉 1개의
스레드로 공유 변수로 변경을 더하면, 그 변경은 그
병렬 영역 내의 다른 스레드로부터 인식됩니다. 한편
프라이빗 변수는 스렛트 팀의 스레드 마다 프라이빗으로 작성됩니다. 이 때문에 1개의 스레드로
변경을 더해도 그 변경은 다른 스레드의 프라이빗
변수에서는 인식되지 않습니다.
기정에서 병렬 영역 내의 모든 변수는 공유입니다. 다만 예외가 3개 있습니다. 첫번째는 parallel for 루프에 있어서의 루프의 인덱스로 이것은 프라이빗입니다. 그림 3의 샘플로 i 변수는 프라이빗입니다. j 변수는 기정에서는 프라이빗이 아닙니다만 firstprivate 구를 사용해 명시적으로 프라이빗으로 되고 있습니다.
2번째로서 병렬 영역의 블록에 로컬인 변수는 프라이빗이 됩니다. 그림 3의 변수 doubleI은
병렬 영역에서 선언되고 있기 때문에 프라이빗입니다. myMatrix::GetElement으로 선언된
비정적 변수 및 비 멤버 변수는 모두 프라이빗이 됩니다.
3번째의 예외는 private, firstprivate,
lastprivate 또는 reduction 구에
리스트 된 변수로 이것들은 모두 프라이빗이 됩니다. 그림 3 의 변수 I, j 및 sum은 스레드 팀의 각 스레드로 프라이빗이 됩니다. 이것은 이러한 변수의 카피를 스레드 마다 따로 따로 작성하는 것으로써 실현됩니다.
4개의 구는 모두 변수의 리스트를 받습니다만 그러한 시멘틱스는
모두 다릅니다. private 구는 리스트내의 각 변수의 사적인 카피가 스레드 마다 작성되는 것을 지정합니다. 이 프라이빗 카피는 기정치로 초기화됩니다(적절한 경우에는 기정의 constructor가 사용됩니다) . 예를 들어 int 형태의 변수의 기정치는 0 입니다.
firstprivate 구는 시멘틱스는 private 와)과
거의 같습니다만, 병렬 영역이 각 스레드에 들어가기
전에 프라이빗 변수의 값을 카피합니다. 적절한 경우에는
카피 constructor가 사용됩니다.
lastprivate 구는 시멘틱스는 private와 거의 같습니다만 마지막 반복해 또는
워크 쉐어링의 구성체의 마지막 섹션으로 lastprivate 구에 리스트 된 변수의 값이 마스터 스레드의 변수에 할당할 수 있습니다. 적절한 경우에는 오브젝트를
카피하는데 카피 할당 연산자가 사용됩니다.
reduction 구는 private의 시멘틱스를 닮아 있습니다. 다만 변수와 연산자의 양쪽 모두를
받습니다. 연산자의 편성은 그림 4 에 일람 한 연산자에 한정됩니다. reduction 변수는 스칼라 변수(예를 들어 float, int 또는
long 등 이며, std::vector,
int [] 등에서는 없는 변수) 일
필요가 있습니다. reduction 변수는 스레드
마다 겉(표)에 일람 한 값에 초기화됩니다. 코드 블록의 최후로 reduction 연산자가, 변수의 각 프라이빗 카피에 적용되어 한층 더 변수의 원래의
값에도 적용됩니다.
그림 3의 샘플에서는 sum의
값은 각 스레드로 암묵적으로 0.0f으로 초기화됩니다. (겉(표)의 정규화
값은 0인 것에 주의해 주세요. 이것은 sum의 형태가 float 이기 위해서 0.0f 이 됩니다.) #pragma omp for 블록이 완료한 후 스레드는 + 연산자를 모든 프라이빗
sum의 값, 및 원래의 값(sum의 원래의
값, 이 샘플에서는 10.0f)에 적용합니다. 결과는 원의 공유 sum 변수에 할당할 수 있습니다.
루프 이외의 병렬처리
OpenMP는 루프 레벨로의 병렬처리에 자주 사용됩니다만 함수 레벨로의
병렬처리도 지원하고 있습니다. 이 메커니즘은 OpenMP sections으로 불려 갑니다.
sections의 구조는 간단하고 많은 경우에 유용합니다.
컴퓨터 과학에 있어 가장 중요한 알고리즘인 퀵 소트에 대해서
생각해 봅시다. 여기서 채택하는 예는 일련의 정수를 대상으로 하는 단순한 재귀적 퀵 소트 알고리즘입니다. 단순하게 하기 위해 일반인 형식의 버전은
사용하지 않고 OpenMP의 생각을 채용합니다. 그림 5의 코드는 sections을 사용하는 퀵 소트의 메인이 되는 함수입니다(여기에서는 간단하게 하기 위해서 Partition 함수에 대해서는
생략 합니다) .
이 샘플에서는 최초의 #pragma에서
섹션의 병렬 영역을 작성합니다. 지시문 #pragma omp
section의 뒤로 각 섹션이 지정됩니다. 병렬 영역의 섹션이 각각 스레드 팀 내의 1개의 스레드로
지정되므로 모든 섹션을 동시에 처리할 수 있습니다. 각 병렬 섹션이 각각 QuickSort를 재귀적으로 호출합니다.
#pragma omp
parallel for 구성체의 경우와 같이 섹션이 병렬로 처리되기 위해서는 각 섹션이 다른 섹션에 Ǿ |