최근 포토로그


Parallel Programming, OpenMP 그리고 Win32 - 3 복잡한컴퓨터이야기

지금 올리고 있는 글이 OpenMP와 관련된 내용이기는 하지만 사실 OpenMP를 이용하여 Parallel Programming을 하면 80점 이상 주기 어렵습니다. 당연한 이야기겠지만 OpenMP는 Parallel Programming을 하기 위한 하나의 방법이고, 다양한 Platform으로 이식이 가능한 형태로 작성되었기 때문에 Platform 전용의 API를 사용하는 것만큼 최적의 성능을 낼 수는 없습니다. 또 다른 이유는 OpenMP가 Compiler Directive에 크게 의존하고 있기 때문에 표현력이 많이 떨어집니다. Computing Language나 API는 다양한 기능을 지원하는 것과 동시에 표현력이 상당히 중요한데, 그런 점에서 OpenMP는 그 뿌리가 Fortran으로부터 왔기 때문에 태생적 한계를 많이 가지고 있습니다. “뭐 이거 그래서 하지 말라는 이야기냐?” 라고 물으신다면 그것 아니고요 Parallel Programming에서 이미 상당한 입지를 가지고 있는 API를 가볍게 하지만 조금은 깊이 있게 알아봄으로써, MPI와 같은 다른 구현이나 Microsoft의 PPL, TPL 그리고 AXUM 등을 이해하는 밑거름이 될 수 있다고 믿기 때문입니다. 한가지 더 덧붙이자면 WIN32 API를 이용한 Concurrent Programming에 대한 추가적인 이해를 도모할 수 있다고 생각하기 때문이지요.

오늘은 #pragma omp parallel for와 같이 제대로 쓸만한 기능을 좀 알아보려고 합니다. 다음 예제를 살펴보시죠.

double pi = 0.0;
const int iterationCount = 200000000;

clock_t startTime = clock();

for (int i = 0 ; i < iterationCount ; i++)
{
pi += 4* (i % 2 ? -1 : 1) / ( 2.0 * i + 1.0);
}

_tprintf(_T("Elpase Time : %d\n"), clock() - startTime);
_tprintf(_T("pi = %.8f\n"), pi);

아주 간단한 PI 계산 프로그램입니다. PI는 다양한 방법으로 계산할 수 있지만, 위 프로그램에서 적용한 공식은 다음과 같습니다.


clip_image001


제 컴퓨터에서는 다음과 같은 결과가 나왔네요

clip_image003

대략 1.5초가 걸렸습니다.

이 프로그램에 Parallel version의 코드를 추가하여 수행 결과를 비교해 보았습니다.

double pi = 0.0;
const int iterationCount = 200000000;

clock_t startTime = clock();

for (int i = 0 ; i < iterationCount ; i++)
{
pi += 4* (i % 2 ? -1 : 1) / ( 2.0 * i + 1.0);
}

_tprintf(_T("Elpase Time : %d\n"), clock() - startTime);
_tprintf(_T("pi = %.8f\n"), pi);

pi = 0.0;
startTime = clock();

#pragma omp parallel
{
#pragma omp for reduction(+:pi)
for (int i = 0 ; i < iterationCount ; i++)
{
pi += 4* (i % 2 ? -1 : 1) / ( 2.0 * i + 1.0);
}
}

_tprintf(_T("Elpase Time : %d\n"), clock() - startTime);
_tprintf(_T("pi = %.8f\n"), pi);



clip_image005


#pragma omp parallel은 이제 익숙하실 것으로 생각이 듭니다. 바로 parallel region을 지정하기 위한 directive이죠. parallel region이 시작되면 시스템의 상황에 맞게 Thread를 추가로 생성한다는 것은 말씀 드렸죠. “#pragma omp for” directive는 “이하에 나오는 for loop은 반복횟수를 적절히 분배하여 병렬적으로 수행하라”라는 의미입니다. 위 같은 경우 반복 횟수가 200000000 회 정도 되는데, 예를 들어 Thread가 추가로 3개(총 4개)가 생성되었다면, 대강 200000000 / 4회 정도로 나누어 수행하면 가장 공평하겠지요. 즉 Thread 별로 0 ~ 50000000, 50000000 ~ 100000000, 100000000 ~ 150000000, 150000000 ~ 200000000 이렇게 나누어 수행하는 것이죠. 정말 그렇게 되는지 debugging을 해보겠습니다. (제 machine의 Quad Core CPU임을 이미 말씀 드렸었죠?)


clip_image007


우측의 i 값을 보세요. 첫 번째 Thread가 계산식에 최초로 진입했을 때 i 값이 0 임을 알 수 있습니다.


이번에는 두 번째 Thread입니다.


clip_image009


세 번째, 네 번째 Thread도 알아볼까요?


clip_image011


clip_image013


이러한 수행 예를 그림을 도식화 해 보면 아마 다음과 같이 될 것 같군요.


image


그런데 여기서 잠깐! 몇 가지 더 살펴볼 것이 있습니다.


처음으로 살펴보아야 할 것은 바로 i 라는 변수 값입니다. 위 그림과 같이 4개의 Thread들은 제 각각 반복해야 할 범위가 서로 다릅니다. 그리고 매 iteration마다 i 값을 1씩 증가시켜 나가야 하죠. 각각의 Thread가 사용하는 i 라는 변수가 만일 하나의 단일 변수라면 동기화 문제가 발생하게 될 겁니다. 그런데 위 결과를 보면 pi가 정상적으로 계산이 되고 있음을 알 수 있습니다. OpenMP에서는 for loop에서 사용하는 iterator, 즉 i 변수는 Thread별로 서로 다른 공간을 사용하게 됩니다. 각각의 Thread는 자신만의 Stack을 가지게 되는데, 이 stack에 i 변수를 유지하게 되죠. 이것도 확인해 봅시다. 첫 번째 Thread와 두 번째 Thread에 대해서만 살펴보죠.


clip_image017


위 그림은 첫 번째 Thread의 수행 예이죠. &i 값이 0x0041f948임을 알 수 있습니다.


clip_image019


&i 값이 0x21af830로 바뀌었습니다. 그리고 esp register의 값을 보면 0x21af824임을 알 수 있는데, 이로써 i 변수가 stack에 존재함을 알 수 있습니다. 사실 이처럼 Thread별로 서로 독립적인 값을 유지하고 싶을 경우에는 다음과 같은 구문을 사용해야 합니다.


#pragma omp for private(variable_name)


위와 같이 private 을 사용하게 되면 뒤따라 오는 변수를 Thread별로 독립적으로 사용하게 됩니다. OpenMP는 for loop의 iterator로 사용하는 변수를 기본적으로 private으로 간주합니다. (당연히 그렇게 해야 하겠지요.)


private를 사용한 예를 하나 알아보기로 하죠. 동기화 문제를 유발하기 위해서 Sleep()을 중간에 포함시켰습니다.

int _tmain(int argc, _TCHAR* argv[])
{
int temp = 0;
int ar[10] = {0,1,2,3,4,5,6,7,8,9};

#pragma omp parallel
{
#pragma omp for
for
(int i = 0 ; i < 10 ; i ++)
{
temp = ar[i];
Sleep(10);
ar[i] = do_something(temp);
_tprintf(_T("%d\n"), ar[i]);
}
}
}
image 
결과가 엉망이죠. #pragma omp for 를 다음과 같이 변경한 후 수행해 보았습니다.
#pragma omp for private(temp)
for (int i = 0 ; i < 10 ; i ++)




clip_image023


순서는 뒤바뀌어 있으나 정확하게 0~9까지가 출력되었음을 알 수 있습니다. 한가지 더 test를 해보겠습니다. 다음과 같은 코드를 test 해 봅시다.


int base = 10;

#pragma omp parallel
{
#pragma omp for private(base)
for (int i = 0 ; i < 10 ; i ++)
{
_tprintf(_T("%d\n"), base);
}
}


base를 10으로 초기화 하고 그 값을 출력했으니, 10이 10번 출력되는 것이 맞을 것 같습니다. 하지만 실제 수행 결과는 다음과 같습니다.



clip_image025


왜 이런 이상한 값이 나왔을 까요? private으로 설정된 변수는, Thread별로 stack에 그 공간이 독립적으로 구성된다고 앞서 이야기 한 바 있습니다. 그런데 공간을 새로 할당하기는 하지만, 기존의 값을 복사하지는 않습니다. 따라서 위의 결과와 같이 의미 없는 값들이 출력되게 됩니다. 이를 수정하려면 다음과 같이 코드를 변경하면 됩니다.

#pragma omp parallel 
{
#pragma omp for firstprivate(base)
for (int i = 0 ; i < 10 ; i ++)
{
_tprintf(_T("%d\n"), base);
}
}


clip_image027 

여기서 first의 의미는 Thread 별로 stack에 독립공간을 구성하는 시점을 의미하게 되겠지요. lastprivate 이라는 clause도 있습니다. 이는 Thread가 수행을 마친 후, 변수의 값을 update하도록 합니다. 그런데 firstprivate과는 다르게 lastprivate을 사용할 때는 다시 한번 생각할 것이 있습니다. firstprivate의 경우 하나의 변수가 다수의 Thread별 변수로 복사됩니다. 하지만 lastprivate의 경우 역으로 Thread별 변수들이 하나의 변수로 복사되게 됩니다. 그렇다면 과연 변수 값은 어느 쓰레드의 변수 값이 복사되는 걸까요? 답은 가장 마지막에 종료되는 Thread의 값으로 overwrite된다 입니다. 하지만 이것이 for 루프의 마지막 iteration을 말하는 것은 아니라는 점에 주의하시기 바랍니다.

int base = 10;

#pragma omp parallel
{
#pragma omp for lastprivate(base)
for (int i = 0 ; i < 10 ; i ++)
{
base = 100;
}
}
_tprintf(_T("%d\n"), base);



이제 오늘 알아볼 마지막 clause인 reduction을 알아볼까 합니다. 이 녀석이 아주 재미납니다. 우리가 첫 번째로 다루었던 pi 계산 예제를 보면 누적 값을 계산하는 pi에 대하여 reduction(+:pi) 라고 설정한 부분이 있음을 알 수 있습니다. 이 예제를 살펴보면 pi 값은 private으로 선언하지 않았기 때문에 모든 Thread들이 동일한 변수 공간에 접근하여 값을 갱신하려고 시도 합니다. 이런 경우 전형적인 동기화 문제가 발생하게 됩니다. 일반적으로 이러한 문제를 해결하기 위해서는 pi 값을 갱신하는 부분을 다수의 Thread가 동시에 수행하지 못하도록 해야 하며, 이를 위해서critical 이라는 construct를 사용하면 됩니다.(이에 대해서는 나중에 좀 더 알아보겠습니다.) 하지만 이처럼 Thread의 접근을 선형화 해버리면 아무래도 성능에 손해를 보게 됩니다. 그래서 생긴 것이 reduction 입니다. reduction으로 변수를 선언하게 되면, 해당 변수는 Thread별로 독립공간을 유지한 채로 수행이 됩니다. 그리고 Thread가 종료되면, Thread별로 계산한 변수 값들을 모두 모아서 한번에 재계산을 합니다. 이렇게 하면 interation과정에서의 동기화 문제가 해결될 수 있는 것이지요. 그런데 reduction의 사용 예를 보면 이 변수를 어떻게 사용할지를 나타내는 연산자를 지정하게 되어 있습니다. 이 연산자의 용도는 크게 2가지 인데 첫째로 reduction으로 선언된 변수의 초기값을 설정하는데 사용합니다. + 나 - 연산의 경우 초기 값을 0으로 설정하면 될 것이지만, *의 경우 1을 초기 값으로 합니다. 아래에 표로 정리해 보았습니다.


연산자 / 초기값
+        0
-        0
*        1
&        ~0
|        0
^        0
&&      1
||       0





그냥 “critical로 해도 별 문제는 없겠구만”이라고 생각하시는 분이 있다면 다음 source와 결과를 살펴보시기 바랍니다.

double pi = 0.0;
const int iterationCount = 200000000;

clock_t startTime = clock();

#pragma omp parallel reduction(+:pi)
{
#pragma omp for
for
(int i = 0 ; i < iterationCount ; i++)
{
pi += 4* (i % 2 ? -1 : 1) / ( 2.0 * i + 1.0);
}
}
_tprintf(_T("Elpase Time : %d\n"), clock() - startTime);
_tprintf(_T("pi = %.8f\n"), pi);


pi = 0.0;
startTime = clock();

#pragma omp parallel
{
#pragma omp for
for
(int i = 0 ; i < iterationCount ; i++)
{
#pragma omp critical
{
pi += 4* (i % 2 ? -1 : 1) / ( 2.0 * i + 1.0);
}
}
}

_tprintf(_T("Elpase Time : %d\n"), clock() - startTime);
_tprintf(_T("pi = %.8f\n"), pi);
clip_image029


reduction이 별것 아닌 줄 알았더니 엄청난 성능차이를 보이죠?




오늘 말씀드릴 새로운 내용은 다 말씀드린 것 같습니다. 이제는 각각에 대해서 좀 더 자세히 알아보겠습니다. “#pragma omp for”가 참 대단한 것 같아도 사실 따져보면 이것저것 한계가 많습니다. 몇 가지 제약사항을 살펴보겠습니다. 일단 iterator로 사용하는 변수는 반드시 부호 있는 정수 이어야 합니다. 그리고 for 구문의 조건문은 반드시 <, <=, >, >= 중 하나이어야 합니다. 더 재미있는 제약은 <나 <=를 사용한 경우 for 구문의 마지막 부분인 증감 연산은 반드시 +(더하기)이어야 합니다. 또한 iterator 변수는 loop내에서 값을 변경해서는 안됩니다. 아래 예제에서 잘못된 부분을 찾아보십시오

#pragma omp parallel 
{
#pragma omp for
for
(unsigned int i = 100 ; 0 < i ; i--)
{
i--;
do_something(i);
}
}



loop 내에서 iterator를 변경하면 안됨, unsigned int는 허용되지 않음. 반복조건이 < 일 경우 반드시 i 값을 증가시켜야 함.
이외에도 상당히 많은 제약사항이 있는데요, 이에 대해서는 spec. 문서를 확인해보세요(www.openmp.org, 이럴때 찾아보는 것이 spec. 이죠) 서두에서도 말씀 드렸지만 OpenMP를 사용하게 되면 C/C++의 유연한 문법 구조를 활용하지 못하는 부분이 많이 있는 건 사실입니다. 표현력이 떨어지는 것이죠. 하지만 아주 못쓸 만큼은 아닙니다. 이와 더불어 do~while loop나 while loop등은 제공되지 않습니다 . for만 지원됩니다.



private에 대해서도 좀 더 살펴보죠, private은 결국 Thread별로 독립된 공간을 할당하여 사용하기 위함인데, 사실 for loop 내에서 변수를 선언해서 사용하면 private 을 사용하지 않고도 동기화 문제를 해결할 수가 있습니다. 따라서 private을 사용하기 전에 과연 이 변수가 loop 외부에서 반드시 선언된 후 사용되어야 하는지에 대해서 다시 한번 생각해 볼 필요가 있습니다. 즉 위 private 예제는 다음과 같이 해도 무방합니다.

int ar[10] = {0,1,2,3,4,5,6,7,8,9};

#pragma omp parallel
{
#pragma omp for
for
(int i = 0 ; i < 10 ; i ++)
{
int temp = ar[i];
Sleep(10);
ar[i] = do_something(temp);
_tprintf(_T("%d\n"), ar[i]);
}
}


firstprivate은 마치 CreateThread나 beginthreadex 함수를 호출할 때 Thread Function에 전달할 LPVOID type의 parameter 같은 느낌입니다. 혹은 Thread별로 공간을 가지는 TLS(Thread Local Storage) 같은 느낌을 줍니다. lastprivate은 GetExitCodeThread() 함수나, GetOverlappedResult()를 이용해서 Thread의 수행 결과를 얻어오는 느낌을 주고 reduction의 경우에도 이렇게 반환된 결과치를 다시 한번 재구성하는 코드를 덧붙인 느낌을 주지요.



OpenMP를 이용한 다음 예를 WIN32를 이용하여 재구성해 보겠습니다.

const int threadCount = 4;

int sum = 0;
int fp = 1;
int lp = 2;
int p = 3;

#pragma omp parallel num_threads(threadCount)
{
#pragma omp for reduction(+:sum), firstprivate(fp), lastprivate(lp), private(p)
for (int i = 0 ; i < 100 ; i ++)
{
p = fp;
lp = p;
sum+= i;
}
}

_tprintf(_T("fp=%d, lp=%d, p=%d, sum = %d\n"), fp, lp, p, sum);

return 0;





결과가 예측이 되시나요?


clip_image031


 struct ThreadArgs
{
    int start;        // loop의 시작
    int chuckSize;    // 반복횟수
    int fp; // firstprivate(fp)
    int lp;            // lastprivate(lp)
};

__declspec(thread) int p;    // TLS를 이용하여 private(p)를 emulation 한다.

DWORD WINAPI ThreadFunc(LPVOID pData)
{
    ThreadArgs *pArgs = (ThreadArgs *)pData;

    int start = pArgs->start;
    int chunkSize = pArgs->chuckSize;
    int fp = pArgs->fp;
   
    // reduction(+:sum)을 emulation 한다.
int sum = 0;
    int lp;

    for (int i = start ; i < start + chunkSize ; i++)
    {
        p = fp;
        lp = p;
        sum+= i;
    }

    pArgs->lp = lp;
   
    return sum;
}



int _tmain(int argc, _TCHAR* argv[])
{
const int threadCount = 4;

HANDLE *pThreads = new HANDLE[threadCount];
ThreadArgs *pArgs = new ThreadArgs[threadCount];

// OpenMP와 동일한 초기화 코드
int sum = 0;
int fp = 1;
int lp = 2;
int p = 3;

// 각 hread 별로 반복횟수를 계산한다. OpenMP의 경우 내부적으로 이 값이 계산 될 것이다.
int chunkSize = 100 / threadCount;

for (int i = 0 ; i < threadCount ; i++)
{
// parameter를 구성한다.
pArgs[i].start = i * chunkSize; // loop의 시작
pArgs[i].chuckSize = chunkSize; // 반복횟수
pArgs[i].fp = fp; // firstprivate(fp)를 emulation 한다.

// Thread를 생성하고, 지체없이 바로 실행한다.
pThreads[i] = CreateThread(NULL, 0, ThreadFunc, (LPVOID)&pArgs[i], 0, NULL);
}

// 모든 Thread의 종료를 기다린다.
WaitForMultipleObjects(threadCount, pThreads, TRUE, INFINITE);

// reduction(+:sum)을 emulation 하여, 최종 결과 값을 도출한다.
// 각 Thread의 반환 값이 Thread별 sum이다.
for (int i = 0 ; i < threadCount ; i++)
{
DWORD tempSum;
GetExitCodeThread(pThreads[i], &tempSum);
sum += tempSum;
lp = pArgs[i].lp; // lastsprivate(lp)를 emulation 한다.
CloseHandle(pThreads[i]);
}

_tprintf(_T("fp=%d, lp=%d, p=%d, sum = %d\n"), fp, lp, p, sum);

delete [] pThreads;
delete [] pArgs;

return 0;
}

사실 위 win32 code가 완벽하게 OpenMP를 이용한 코드와 일치하는 것은 아닙니다. 가장 큰 차이점은 Win32가 Thread를 하나 더 생성한다는 것이고요, lastprivate 값을 획득하는 과정도 앞서의 설명과 조금 상이한 부분이 있습니다. 또한 TLS와 Thread Parameter의 사용 예를 보여주기 위해서 code를 약간 복잡하게 구성한 부분이 없지 않습니다. 하지만 전체적인 맥락에서는 거의 유사한 형태이므로 비교해 보시면 좋을 것 같습니다.



오늘은 많이 길어졌네요. 도움이 되셨길…
*Live Writer로 글을 올리고 있는데 사정없이 깨지내요. egloos말고 다른 곳으로 이사가야할 까봐요. 좋은 곳 있음 알려주세요

Parallel Programming, OpenMP 그리고 Win32 - 1

Parallel Programming, OpenMP 그리고 Win32 - 2

Parallel Programming, OpenMP 그리고 Win32 - 3

Parallel Programming, OpenMP 그리고 Win32 - 4

Parallel Programming, OpenMP 그리고 Win32 - 5

Parallel Programming, OpenMP 그리고 Win32 - 6


덧글

  • esstory 2010/05/17 17:06 # 삭제 답글

    덕분에 openmp 에 대해 조금이라도 이해하게 되었습니다. 정말 감사합니다~
  • 김명신 2010/05/17 17:34 #

    도움이 되셨다니 보람이 있군요. 감사합니다.
  • 나그네 2013/04/27 21:46 # 삭제 답글

    잘 보고 갑니다. 좋은 글 감사합니다.
  • kamchol 2017/04/03 15:59 # 삭제 답글

    블로그 글을 보고 많은 도움을 받았습니다.

    한가지 궁금 한게 있습니다. openmp 사용 중에 생긴 문제점을 위의 블로그에서

    #pragma omp parallel
    {
    #pragma omp for firstprivate(base)

    말씀하신 방법으로 해결하였습니다.

    제가 똑같은 방법으로 TBB로 구현 하려 하는데 TBB 역시 독립적인 공간에 관한 문제가 발생하였는데요

    혹시 TBB에 관한 방법도 알고 계신지 궁금합니다
댓글 입력 영역


facebook 프로필 위젯

트위터 위젯