[펌]C언어: OpenMP를 이용한 멀티 쓰레드 프로그래밍 HOWTO

희자매파파 2009. 12. 23. 12:48

2009. 12. 23. 12:48

C언어: OpenMP를 이용한 멀티 쓰레드 프로그래밍 HOWTO #1 http://sunyzero.egloos.com/4227785

0. 시작하기에 앞서
병렬처리 프로그래밍을 위한 기법중 OpenMP를 이용하는 방법에 대해서 보도록 할 것이다.

불과 10여년 전만 하더라도 병렬 처리를 위한 프로그래밍은 사치에 가까웠고 CPU를 여러 개 장착한 PC는 보기 힘들었다. 하지만 최근 CPU의 발달은 Hz 속도를 거의 한계에 다다르게 하였다:현재 한계는 약 3GHz 전후이다. 물론 이론상으로는 5GHz도 가능하지만 엄청난 발열과 전력 소비로 인해서 효과적이지 못하다. 그리하여 CPU 벤더들은 Hz속도의 경쟁보다는 복수개의 코어로 진화할 수 밖에 없게 되었다.

그러나 기존 프로그램은 멀티 코어를 지원하도록 작성된 경우가 거의 없기에 심각한 문제로 대두되기 시작했다. 앞으로의 추세는 병렬 처리를 위한 멀티 쓰레드 프로그래밍이지만 이 분야가 결코 쉽지 않다는 점이 발목을 잡는다. 일반적인 native multi-thread programming은 고급 레벨이 아니고서는 작성하기 힘들어서 해당 분야 전공자가 아닌 응용 프로그래머는 손대기가 힘들었다. 예를 들어 물리나 수학, 화학에서 C, C++, fotran을 이용한 수치계산을 한다고 가정해보자. 연구중인 앨거리즘이나 휴리스틱 기법을 테스트하려고 하는데 더 빠른 계산을 위해서 고급 멀티 쓰레드 프로그래밍을 배우려고 한다면 얼마나 걸릴 것인가? 물론 천재적인 사람이라면 금방 가능하겠지만 일반적으로는 프로그래밍 배우는데 몇개월에서 반 년이상을 투자해야 제대로 할 수 있을 것이다 그러나 이는 배보다 배꼽이 더 큰 문제가 되어버린다.

따라서 간단한 멀티 쓰레드 프로그래밍을 구현하기 위한 좀 더 쉬운 adaptive multi-thread programming 기법으로 OpenMP가 나오게 되었다. OpenMP는 뛰어난 프로그래밍 실력을 아니더라도 단 몇일만 투자해도 쉽게 멀티 쓰레드 프로그래밍을 할 수 있게 도와 준다.

1. OpenMP란?
멀티 쓰레드 프로그래밍을 간단하게 하기 위해서 개발된 기법.
OpenMP는 컴파일러 지시자만으로서 블록을 멀티 쓰레드로 작동하게 할 수 있다.
현재 대부분의 컴파일러(e.g. gcc, Intel Compiler, Microsoft visual studio, Sun studio... 등등)는 OpenMP지시자를 지원한다.

지원언어 : C, C++, Fortran
표준 : http://www.openmp.org (현재 OpenMP 3.0-May, 2008이 나와있지만 이 문서는 2.5 spec을 기준으로 설명한다. 3.0은 나중에 따로 추리도록 하겠다.)

2. OpenMP의 시작

코드에 #pragma omp 로 시작하는 지시어를 삽입한다.

#pragma omp parallel [clause[ [, ]clause] ...] new-line

structured-block

그러면 간단한 Hello world 예제를 OpenMP 멀티 쓰레드 프로그램으로 만들어 보자.
우선 아래의 프로그램은 그냥 일반 single thread 프로그램이다.

# include <stdio.h>

int main() 
{
    printf("Hello world\n");
    return 0;
}

여기에 OpenMP 지시어를 추가하여 멀티 쓰레드 프로그램으로 바꾸면 아래처럼 작성된다.

# include <stdio.h>

int main() 
{
#pragma omp parallel
    {
        printf("Hello world\n");
    }

    return 0;
}

실제로 엄청 간단하지 않은가? 그러면 컴파일 해보자.
단 주의할 점은 OpenMP를 인식할 수 있도록 컴파일러에 옵션을 넣어줘야 한다.

OpenMP 컴파일 옵션 : -fopenmp (GCC인 경우), -openmp (Intel C Compiler인 경우)
윈도우즈용 비주얼 스튜디오는 알아서 컴파일 해준다.

$ gcc -fopenmp -o helloworld_omp helloworld.c

$ ./helloworld_omp

Hello world
Hello world

파일명이 helloworld.c라고 가정할 때 위와 같이 컴파일하면 된다.
make를 쓸줄 안다면 "make CFLAGS=-fopenmp helloworld"라고 해도 된다.

그리고 실행해보면 필자의 플랫폼에서는 2번 출력되었다. 하지만 3번이나 4번 출력되는 사람도 있을것이다.
이는 기본적으로 OpenMP가 물리적 CPU개수만큼 쓰레드를 만들기 때문이다. 즉 필자는 듀얼코어를 쓰고 있다.

그러면 쓰레드의 개수를 임의로 늘릴 수는 없는가? 가능하다. 환경변수나 omp_set_num_threads(int)함수를 이용하면 된다.
그러면 임의로 쓰레드의 개수를 4개로 만들어 보겠다.

# include <stdio.h>

# include <omp.h>

int main() 

{

    omp_set_num_threads(4);

#pragma omp parallel

    {

        printf("Hello world\n");
    }

    return 0;

}

앞의 예제에서 달라진 것은 omp.h 헤더를 포함한 것과 병렬구간을 시작하기 전에 omp_set_num_threads(4)를 실행한 것이다.
혹은 OMP_NUM_THREADS라는 환경변수를 세팅해도 된다. 본쉘이라면 "export OMP_NUM_THREADS=4"으로 명령하면 되겠다.

3. OpenMP를 이용한 work-sharing 모델
이번에는 OpenMP를 이용한 work-sharing 모델 분류를 배우도록 하겠다. 분류는 3가지 정도 된다.(OpenMP 3.0에서는 worksharing라는 지시어가 추가되었는데 fortran전용이며 이 문서는 오래전 2.5때 쓰여진 것이라 여기서는 설명하지 않는다.)

loop construct
section construct
single construct

loop construct는 for 루프문을 병렬처리하는 기법이고, section construct 는 블록단위로 병렬처리를 하도록 하는 방법이다. single은 병렬처리구간에서 한번만 실행되어야 하는 블록을 지정할 때 사용한다.

4. Loop construct

4.a Loop consturct 기본 형태
loop construct는 for 루프문을 병렬처리 한다고 했다. 기초적인 예제를 보자.

예제에서 보면 총 8번의 루프동안 2개의 쓰레드로 병렬처리하는 것을 보여주고 있다. 물론 쓰레드가 4개라면 2개씩 처리할 것이다.
그런데 위에는 병렬처리 구간이 for 루프 구간과 겹치므로 #pragma omp parallel 과 #pragma omp for를 합칠 수 있다.

합치니까 매우 깔끔해 보인다.
그런데 루프문 안에서 printf()의 출력결과는 단지 index만 출력하고 있으므로 어떤 쓰레드가 어떤 결과를 출력하는지
알 수 있는 방법이 없다. 그래서 쓰레드 번호를 찍는 것을 추가해 보도록 하자.

omp_get_thread_num()은 쓰레드 번호를 출력해 주므로 각각의 쓰레드가 어떻게 출력하는지 나타난다.
그러면 수정된 예제를 컴파일 후 실행해보면 결과는 어떻게 나올까? (위의 파일명은 loop_exam1.c라고 하자)

$ gcc -fopenmp -o loop_exam1 loop_exam1.c

$ ./loop_exam1

[1-4] Hello world
[1-5] Hello world
[1-6] Hello world
[1-7] Hello world
[0-0] Hello world
[0-1] Hello world

[0-2] Hello world

[0-3] Hello world

결과를 보면 0번 쓰레드가 0~3까지 처리하고, 1번 쓰레드가 4~7까지 처리하는 것으로 나온다. 위에는 이쁘지 않게 순서가 거꾸로 출력되었지만, 이 순서는 항상 같으리라고 보장할수는 없다. 따라서 출력 순서는 그냥 신경쓰지 말자.

4.b 병렬 처리시 주의점
이번에는 예제를 하나 풀어보면서 Loop construct를 적용할 때 주의점도 보겠다. 간혹 잘못된 멀티 쓰레드 적용은 false-sharing문제나 멀티 쓰레드가 계산한 결과의 reduction처리를 빼먹어서 잘못된 값이 나올 수 있기 때문이다.

풀어볼 예제는 3.141592의 숫자로 알고 있는 파이(pi) 계산을 멀티 쓰레드로 만드는 것이다. pi 계산을 선택한 이유는 쉽게 CPU를 혹사시킬 수 있는 방법이기 때문이다. 우선 Single threaded 버전을 한번 보자.

#include <stdio.h>

#include <stdlib.h>
int num_steps=1000000000; /* 10억번 : 너무 많으면 조금 줄이시길... */



int main()

{

    int i;

    double x, step, sum = 0.0;

    step = 1.0/(double) num_steps;

    for (i=0; i<num_steps; i++) {

        x = (i+0.5) * step;

        sum += 4.0/(1.0 + x*x);

    }

    printf("PI = %.8f (sum = %.8f)\n", step*sum, sum);

    return EXIT_SUCCESS;

}

위의 pi 구하는 소스코드가 어떻게 나왔는지는 그냥 양념으로 알아두자.
(생각없이 그냥 그런가보다 할 수도 있지만 이런 계산법을 알아두는 것도 고등학교때 추억을 떠올리는 즐거움이 있다.)

우선 위의 pi를 구하는 공식은 그레고리 급수를 전개하기 전까지의 방법이다.
그레고리는 계산의 편리함을 위해서 급수로 전개했지만, 컴퓨터가 있으니 그냥 적분값을 무수히 계산시키면 쉽다.

이제 y=1/(1+x^2)의 0~1까지의 정적분에 4를 곱하면 pi의 값이 나온다는 것을 알았다. 이를 컴퓨터를 이용해서 계산할 때는 해당 구간을 무수히 작은 사각형으로 쪼개서 더하는 numerical integration으로 구하면 쉽다. 즉 0~1까지의 x의 값을 n개로 쪼갠 뒤에 y와 곱한 직사각형을 더할 것이다.(이때 x의 좌표값은 중간값을 취하는 Midpoint rule을 적용하므로 0.5씩 더했다.)

하지만 정의역(x)의 범위인 0~1에 대해 y의 범위는 4~2가 나오지만, numerical integration을 위해서
정의역을 n개로 나누면 n이 작을수록 한 개의 직사각형의 크기는 엄청 작아진다.(물론 정밀도가 올라간다.)

하지만 소수점으로 너무 작아지는 x값을 사용하면 계산에도 무리가 있으므로 직사각형의 높이(y)는 그대로 두고
x만 n번을 곱한 수로 치환하면 x는 1이 된다. 그리고 n개의 직사각형을 더한 뒤 n으로 다시 나누면 pi가 나오게 된다.

이제 수학적인 부분을 다 설명했으므로 위의 pi계산 프로그램을 single thread버전으로 돌려보자.(파일명을 pi_numerical_integration.c라고 지정했다.)
예제 파일 : pi_numerical_integration.c

$ make pi_numerical_integration

$ time ./pi_numerical_integration

PI = 3.14159265 (sum = 2513274122.87223005)

real    0m8.994s

user    0m8.993s

sys     0m0.001s

time명령으로 수행 시간을 보니 약 8.994초이며 user/sys영역에서 소비한 CPU타임도 이와 같은 것을 볼때 1개의 CPU만 사용했음을 알 수 있다. 이번에는 OpenMP를 적용하도록 소스코드를 수정하겠다. 중간에 #pragma omp parallel for 구문을 넣어주었다.

#include <stdio.h>

#include <stdlib.h>

int num_steps=1000000000; /* 10억번 : 너무 많으면 조금 줄이시길... */



int main()

{

    int i;

    double x, step, sum = 0.0;

    step = 1.0/(double) num_steps;

#pragma omp parallel for

    for (i=0; i<num_steps; i++) {

        x = (i+0.5) * step;

        sum += 4.0/(1.0 + x*x);

    }

    printf("PI = %.8f (sum = %.8f)\n", step*sum, sum);

    return EXIT_SUCCESS;
}

이제 컴파일 후 실행해야한다. 컴파일은 make에 CFLAGS (Compiler flags) 변수에 openmp기능을 넣고 컴파일한다. (make를 이용하는 것이 쉬워서인데 gcc 명령어를 직접 타이핑하는게 좋다면 gcc -o pi_numerical_integration -fopenmp pi_numerical_integration.c 를 모두 타이핑하면 된다.)

$ make CFLAGS="-fopenmp" pi_numerical_integration

$ time ./pi_numerical_integration

PI = 2.26234349 (sum = 1809874795.18165779)



real    0m50.394s

user    1m38.686s
sys     0m0.013s

멀티 쓰레드를 사용했는데 실제 수행 시간은 50여초나 걸렸고, CPU는 무려 1분 38초 넘게 사용되었다. 어째서 수행 시간이 더 늘어난 것일까? 더군다나 pi값도 틀리게 출력된다.

수행시간의 오버헤드는 True-sharing, False-sharing 때문에 발생한다. True-sharing은 복수개의 CPU가 공유 변수인 x, sum을 접근하려고 할 때 발생시키는 cache miss 오버헤드이며, 이는 정확한 값을 유지하려고 하는 동기화 오버헤드를 가져온다. False-sharing은 예제의 x와 sum은 연속된 공간에 있을 확률이 높기에(64 byte cache line을 사용하는 최근 Intel CPU에서는 x와 sum이 같은 cache line에 있을 가능성이 높다.) x나 sum 둘 중에 하나만 update되어도 cache line단위로 업데이트 되어 다른 CPU의 cache line을 무효(invalid) 시켜버리는 문제를 가져온다. 특히 위의 예제처럼 x, sum이 종종 업데이트 되는 계산구조라면 cache miss가 비약적으로 증가하여 엄청난 페널티가 있으므로 이를 회피하도록 설계를 바꿔야만 한다. - object(minjang.egloos.com)님의 지적

따라서 프로그래머는 True-sharing, False sharing을 피하기 위해 멀티 쓰레드가 사용하는 메모리 공간은 서로 공유하지 않도록 설계하거나, 혹은 lock을 사용하거나, 동일 cache line에 걸칠 가능성이 있는 데이터 구조에는 padding을 넣어 설계하는 방법등이 있다. (자세한 False-sharing 문제는 OS관련 책에 나오니 그 부분을 참고)

위 예제의 경우도 x와 sum을 공유하지 않도록 로컬 변수로 만들어 버리면 해결된다. 마침 OpenMP에서는 private(변수, ...)이란 지시어를 제공하고 있는데, private에 선언된 변수는 병렬처리 구간에서 같은 이름을 가지는 새로운 스택 변수로 선언되어 공유를 피할 수 있게 된다.

그러면 private(x, sum)으로 선언해야 할까? 아니다. x는 private으로 선언하는 것이 맞지만 sum값은 작동 방법이 조금 다르다. sum은 각각의 쓰레드가 작동하여 따로 계산할지라도 끝에서는 각 쓰레드의 값을 합산하여 보정해야 되기 때문이다. 이를 위해서 보정하는 지시어인 reduction(...)이 제공된다. reduction(op:변수...)로 선언하며 op에 해당하는 operand로 reduction시켜준다. 또한 reduction에 선언된 변수는 자동으로 private변수가 되어 공유를 피할 수 있게 해준다. 위 예제는 덧셈이므로 op부분에 +를 넣어주면 되겠다. 플러스 외에 사용가능한 reduction operand는 다음과 같다.

그러면 private()과 reduction()을 적용하여 수정된 예제를 보도록 하자.
예제 파일 : pi_numerical_integration_omp.c

#include <stdio.h>

#include <stdlib.h>

int num_steps=1000000000; /* 10억번 : 너무 많으면 조금 줄이시길... */

int main()

{

    int i;
    double x, step, sum = 0.0;

    step = 1.0/(double) num_steps;

#pragma omp parallel for private(x) reduction(+:sum)

    for (i=0; i<num_steps; i++) {

        x = (i+0.5) * step;

        sum += 4.0/(1.0 + x*x);

    }

    printf("PI = %.8f (sum = %.8f)\n", step*sum, sum);

    return EXIT_SUCCESS;
}

이제 컴파일후 실행해보면 real time이 약 CPU개수만큼 줄어드는 것을 볼 수 있다.
듀얼코어인 필자 시스템에서는 절반으로 줄어들었다.

4.c 스케줄링
앞의 for문을 여러 쓰레드가 나눌때는 정확하게 1/n (n=# of threads)로 나누는 것을 볼 수 있다.
이렇게 스케줄링하는 방법은 편리하긴 하지만 때에 따라서는 언밸런스를 가져올 수 있으므로 OpenMP는 각 반복작업(iteration)을 스케줄링 하는 3가지 방법을 제공한다. 이는 #pragram omp for의 지시어의 뒤에 붙여서 사용한다.

schedule(static [, x])
schedule(dynamic [, x])
schedule(guided [, x])

static 스케줄링은 round-robin 방식으로 각 쓰레드에게 작업을 할당한다.
뒤의 x은 한번에 할당할 chunk의 개수로 생략하면 1로 지정된다.
static 스케줄은 OpenMP의 기본 스케줄 방식이며 기본값일 경우는 x는 전체 iteration을 쓰레드의 개수로 나눈 값이 지정된다.
이 방식은 각 iteration의 완료 시간이 규칙적일때 모든 쓰레드들은 비슷한 시간에 종료하게 된다.
만일 각 iteration의 완료 시간이 불규칙적이라면 static 스케줄링은 좋지 못한 결과를 가져올 수도 있다.

dynamic 스케줄링은 작업을 빨리 마치고 idle상태인 쓰레드에게 chunk개수만큼씩을 할당한다.
마찬가지로 x가 생략되면 chunk의 개수는 1로 지정된다.
dynamic은 각 chunk들의 작업 완료 시간이 불규칙적일 때 매우 유용하다.
왜냐하면 쓰레드 중에 작업을 빨리 끝내는 경우가 있다면 다음 작업을 빨리 할당받아 실행할 가능성이 높기 때문이다.
(단 주의할 점은 너무 적은 chunk의 개수를 할당하면 스케줄링하는 오버헤드가 더 커질 수 있으니 적당한 값을 써야 한다.)

guided는 dynamic과 비슷하여 idle 상태인 쓰레드에게 먼저 chunk를 할당한다.
다만 다른 점은 dynamic은 chunk의 개수가 고정인데 반해, guided는 chunk의 개수를 큰 수에서 점점 작은 수로
줄여나간다는 점이다. guided는 chunk를 지수적으로 감소시키되 지정된 x의 크기 이하로는 감소시키지 않는다.(x는 생략시 1이다)
chunk의 크기는 다음 공식을 따른다.

C언어: OpenMP를 이용한 멀티 쓰레드 프로그래밍 HOWTO #2 http://sunyzero.egloos.com/4227785

* 연습문제 (멀티 쓰레딩과 reentrant 함수의 관계에 대한 문제)

이번에는 pi를 몬테 카를로 시뮬레이션을 이용해서 구해보도록 하겠다.
각변의 길이가 1인 정사각형이 있다. 그리고 정사각형 안에 반지름(r)이 1인 원호를 그리도록 하자.
그러면 중점으로부터 원호까지의 최단 길이는 무조건 1이 된다.

그러면 이제 정사각형 안에 임의의 점(x,y)좌표를 찍어서 중점에서 선분을 연결하고 아랫변까지 선분을 내리면 직각삼각형이 된다.
그리고 이 직각삼각형의 길이는 x, 높이는 y가 된다.
피타고라스의 정리에 의해 (x의 제곱)+(y의 제곱)=(빗변의 제곱)이 되는데, 빗변이 길이가 1보다 작으면
원호 안에 찍힌 점이 되고, 1보다 크면 원호 밖에 정사각형 내부에 찍힌 점이 된다.

원호의 넓이는 반지름 r=1일 때 pi/4이 된다. 따라서 위의 수많은 랜덤 좌표를 찍은 뒤에 (원호 내부의 점의 개수)/(전체 랜덤 수)는 pi/4와 같아질 것이다. 그러면 이제 기본 코딩을 해보자.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#define LOOP_ITERATION 200000000
int hits;

int main()
{ int i;
double x, y, rns;
time_t t_now;

printf("Loop iteration = %ld\n", (long)LOOP_ITERATION);
rns = 1.0/(double)RAND_MAX;
t_now = time(0);
srand((unsigned int)t_now);
for (i=0; i<LOOP_ITERATION; i++) {
x = (double)rand() * rns;
y = (double)rand() * rns;
if (x*x + y*y < 1) {
hits++; } }
printf("pi = %f\n", 4*(double)hits/LOOP_ITERATION);
return 0;
}
이제 컴파일 후 실행을 해 보겠다. 소스코드의 파일명은 pi_monte.c라고 저장했다.

$ gcc -o pi_monte pi_monte.c
$ time ./pi_monte
Loop iteration = 200000000
pi = 3.141588

real 0m8.726s
user 0m8.702s
sys 0m0.023s
CPU를 한 개만 사용했기 때문에 real과 user+sys 시간이 같게 나온다.
이제 여기에 OpenMP를 적용해보도록 하자. 중복되는 코드는 모두 생략하고 중간에 loop부분만 적도록 하겠다.

...생략...
#pragma omp parallel for private(x,y) reduction(+:hits)
for (i=0; i<LOOP_ITERATION; i++) { x = (double)rand() * rns; y = (double)rand() * rns; if (x*x + y*y < 1) { hits++; } }
...생략...
자 이제 수정된 소스코드를 컴파일하고 다시 실행해보겠다.

$ gcc -o pi_monte_omp -fopenmp pi_monte.c
$ time ./pi_monte_omp
Loop iteration = 200000000
pi = 3.141513
real 0m54.909s user 0m54.173s sys 0m53.115s
OpenMP버전의 실행 시간이 엄청나게 증가한 것을 볼 수 있다.
이는 뭔가 문제가 발생한 것이다. profiler가 있으면 cache miss가 많아진 것을 추적할 수 있다. 그러면 왜 cache miss가 많아졌을까?

이는 멀티 쓰레드 안전(thread-safe, MT-safe)한 함수를 사용하지 않았기 때문이다.
단도직입으로 원인은 rand()함수이다. rand()함수는 내부에 static 변수(BSS영역)를 사용하기 때문에 lock 없이 사용하면
오염된 공간을 쓸 수 있다. 그렇다고 lock으로 보호하는 것은 성능상으로 좋지 못하다. 따라서 MT-safe한 랜덤생성 함수로
대체해야 한다. 마침 rand()의 reentrant 버전인 rand_r()이 있으므로 이를 사용하도록 바꾸면 된다.

* reentrant에 대한 이해가 필요하다면...http://sunyzero.egloos.com/4188321 글을 읽도록 한다.

그러면 이제 수정된 버전을 보도록 하겠다.

#define _REENTRANT
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#ifdef LOOP_ITERATION #define LOOP_ITERATION 200000000
#endif
int hits; int main() { unsigned int state;
int i;
double x, y, rns; printf("Loop iteration = %ld\n", (long)LOOP_ITERATION);
rns = 1.0/(double)RAND_MAX;
state = (unsigned int)time(0);
#pragma omp parallel for firstprivate(state) private(x, y) reduction(+:hits)
for (i=0; i<LOOP_ITERATION; i++) {
x = (double)rand_r(&state) * rns;
y = (double)rand_r(&state) * rns;
#if LOOP_ITERATION < 100
printf("THR[%d:%d] x,y/state = %f,%f/%u\n", omp_get_thread_num(), i, x, y, state);
#endif
if (x*x + y*y < 1) { hits++; }
}
printf("pi = %f (hits = %d)\n", (double)hits/LOOP_ITERATION * 4, hits);
return 0;
}
중요한 변화를 확인하기 위해 LOOP_ITERATION이 100 이하인 경우에는 루프를 돌때마다 rand_r()로 얻어진 x, y, state의 값을 출력하도록 디버깅 코드를 심어놨다. 그러면 LOOP_ITERATION을 20으로 줄여서 컴파일&실행으로 디버깅 해보자.

$ gcc -o pi_monte_omp_logging -DLOOP_ITERATION=20 -fopenmp pi_monte.c
$ ./pi_monte_omp_logging
Loop iteration = 20
THR[0:0] x,y/state = 0.739258,0.373189/1534713604 THR[0:1] x,y/state = 0.741886,0.152093/434332526 THR[0:2] x,y/state = 0.399359,0.675170/1402811528 THR[0:3] x,y/state = 0.140991,0.510551/3217124562 THR[0:4] x,y/state = 0.117010,0.018486/2612351692 THR[0:5] x,y/state = 0.151627,0.286311/535820534 THR[0:6] x,y/state = 0.412198,0.450266/361487824 THR[0:7] x,y/state = 0.126866,0.324974/1313573850 THR[0:8] x,y/state = 0.923697,0.862684/1937324436 THR[0:9] x,y/state = 0.828232,0.810037/3167316350 THR[1:10] x,y/state = 0.739258,0.373189/153471360
THR[1:11] x,y/state = 0.741886,0.152093/434332526
THR[1:12] x,y/state = 0.399359,0.675170/1402811528
THR[1:13] x,y/state = 0.140991,0.510551/3217124562
THR[1:14] x,y/state = 0.117010,0.018486/2612351692
THR[1:15] x,y/state = 0.151627,0.286311/535820534
THR[1:16] x,y/state = 0.412198,0.450266/361487824
THR[1:17] x,y/state = 0.126866,0.324974/1313573850
THR[1:18] x,y/state = 0.923697,0.862684/1937324436
THR[1:19] x,y/state = 0.828232,0.810037/3167316350
pi = 3.200000 (hits = 16)
iteration이 20번이므로 pi의 정확도는 일단 포기하자. 지금은 pi의 결과를 보려는 것이 아니라, 각 쓰레드의 x, y값을 확인하기 위함이다. 0번째 쓰레드의 첫번째 데이터와 1번째 쓰레드의 첫번째 데이터를 비교하니 뭔가 이상하다. 이해를 돕기 위해 두개만 따로 떼어서 보도록 하자.

THR[0:0] x,y/state = 0.739258,0.373189/1534713604
THR[1:10] x,y/state = 0.739258,0.373189/1534713604

둘이 놀랍도록 일치하지 않은가? 왜 이런 문제가 발생할까? 이는 rand_r()함수에 사용하는 seed값 변수인 state의 초기값이 모든 쓰레드들에 대해서 같기 때문에 발생하는 문제다. 그렇다면 각 쓰레드가 seed를 다르게 가져가도록 소스코드를 수정해야 한다.

#define _REENTRANT
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#ifdef LOOP_ITERATION
#define LOOP_ITERATION 200000000
#endif
int hits; int main() { unsigned int state1, state2;
int i;
double x, y, rns;
printf("Loop iteration = %ld\n", (long)LOOP_ITERATION);
rns = 1.0/(double)RAND_MAX; state1 = (unsigned int)times(NULL);
#pragma omp parallel private(x, y, state2) reduction(+:hits) shared(state1)
{
#pragma omp critical
state2 = rand_r(&state1);
printf("THR[%d] state1/state2 = %u/%u\n", omp_get_thread_num(), state1, state2);
#pragma omp for
for (i=0; i<LOOP_ITERATION; i++) { x = (double)rand_r(&state2) * rns; y = (double)rand_r(&state2) * rns;
#if LOOP_ITERATION < 100 printf("THR[%d:%d] x,y/state,hits = %f,%f/%u,%d\n", omp_get_thread_num(), i, x, y, state2,hits);
#endif
if (x*x + y*y < 1) { hits++; } } }
printf("hits(%d), pi = %f\n", hits, (double)hits/LOOP_ITERATION * 4);
return 0; }
#pragma omp critical 지시어는 아래의 블럭공간을 락으로 보호해준다. 즉 state1으로부터 state2라는 seed값을 생성하는 코드 부분은 각 쓰레드들이 직렬적으로 실행하게 되므로 각각 다른 seed (=state2)를 가질 수 있게 해준다.

그러면 이제 수정된 버전의 확인을 위해 LOOP_ITERATION을 20번으로 지정하고 컴파일하여 다시 실행해보자.

$ gcc -o pi_monte_omp_logging -DLOOP_ITERATION=20 -fopenmp pi_monte.c
$ ./pi_monte_omp_logging
Loop iteration = 20
THR[0] state1/state2 = 2209777173/920556694 THR[0:0] x,y/state,hits = 0.007502,0.800638/402955376,0 THR[0:1] x,y/state,hits = 0.031584,0.366846/1879397754,1 THR[0:2] x,y/state,hits = 0.084310,0.126795/2318644788,2 THR[0:3] x,y/state,hits = 0.219188,0.054924/839319838,3 THR[0:4] x,y/state,hits = 0.315477,0.640078/2081973432,4 THR[0:5] x,y/state,hits = 0.423693,0.287051/4130577282,5 THR[0:6] x,y/state,hits = 0.738140,0.376765/2380434428,6
THR[0:7] x,y/state,hits = 0.127375,0.723816/3248220326,7
THR[0:8] x,y/state,hits = 0.832496,0.256793/3481063424,8
THR[0:9] x,y/state,hits = 0.939841,0.108509/3174395018,9
THR[1] state1/state2 = 2209777173/754906038
THR[1:10] x,y/state,hits = 0.446803,0.061819/2639594128,0
THR[1:11] x,y/state,hits = 0.919237,0.585474/2439875226,1
THR[1:12] x,y/state,hits = 0.122634,0.254468/2048737876,1
THR[1:13] x,y/state,hits = 0.204702,0.526382/3058641982,2
THR[1:14] x,y/state,hits = 0.642845,0.756832/477247192,3
THR[1:15] x,y/state,hits = 0.550340,0.531024/1736039586,4
THR[1:16] x,y/state,hits = 0.926036,0.217729/4074357788,5
THR[1:17] x,y/state,hits = 0.266219,0.975137/2510577606,6
THR[1:18] x,y/state,hits = 0.663719,0.557898/2880736800,6 THR[1:19] x,y/state,hits = 0.491536,0.580296/2760522154,7
hits(18), pi = 3.600000
실행 결과를 보면 이제 x, y값이 각 쓰레드마다 달라지는 것을 볼 수 있다.

그러면 이제 기능상의 문제는 해결되었으니 원래대로 200,000,000번의 시행 횟수로 실행시간을 비교해보자.

$ gcc -o pi_monte_omp -fopenmp pi_monte.c
$ time ./pi_monte_omp
Loop iteration = 200000000
THR[0] state1/state2 = 319398670/265139008
THR[1] state1/state2 = 319398670/1387545353
hits(157082826), pi = 3.141657
real 0m2.414s
user 0m4.737s
sys 0m0.013s
싱글 쓰레드 버전이 8.6초 걸린 것에 비해 OpenMP로 돌린 버전은 2.4초로 확 줄어들었다. 원래대로라면 듀얼코어니 4.3초정도가 나와야 하겠지만, rand_r()자체가 rand()보다 가볍기 때문에 그로 인해서 속도가 더 빨라졌다. 즉 싱글 쓰레드 버전이라고 해도 rand()보다는 rand_r()을 사용하면 더 빠르다라는 교훈도 덤으로 알려드리는 문제였다.

5. Section construct
section construct는 task level parallelism에 사용하며, 각각의 작업들이 서로 관련이 없는 경우에 사용한다.
(task 레벨의 병렬화이므로 divide and conquer 형태의 문제해결에도 적용가능하다.)

그림에서 볼 수 있듯이 오렌지색의 섹션과 블루색의 섹션이 각각 독립적으로 작동하도록 구성할 수 있다.
단 각각의 섹션은 누가 먼저 종료하든지 #pragram omp sections 블록의 끝에는 implicit barrier가 있으므로 대기하게 된다.

참고로 병렬구간내에 섹션구간만 존재하는 경우라면 #pragma omp parallel sections로 구문을 합칠 수 있다.

그러면 이번에는 앞에서 loop construct때 연습했던 2가지 pi 구하는 방법(numerical integration, monte carlo simulation)을
sections를 이용해서 동시에 작동시키도록 바꿔보자.

* 연습문제 (섹션별로 task를 할당하는 방법)

앞에서 Single threaded 버전으로 만들었던 소스코드들을 연달아 붙여두면 된다.
우선 Numerical Integration 방법의 소스코드를 다시 보자.

#include <stdio.h>
#include <stdlib.h>
int num_steps=1000000000; /* 10억번 : 너무 많으면 조금 줄이시길... */
int main()
{
int i;
double x, step, sum = 0.0;
step = 1.0/(double) num_steps;
for (i=0; i<num_steps; i++) {
x = (i+0.5) * step;
sum += 4.0/(1.0 + x*x);
}
printf("PI = %.8f (sum = %.8f)\n", step*sum, sum);
return EXIT_SUCCESS;
}
이번에는 Monte Carlo simulation방법을 다시 보겠다.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#define LOOP_ITERATION 200000000
int hits;
int main()
{
int i;
double x, y, rns;
time_t t_now;
printf("Loop iteration = %ld\n", (long)LOOP_ITERATION);
rns = 1.0/(double)RAND_MAX;
t_now = time(0);
srand((unsigned int)t_now);
for (i=0; i<LOOP_ITERATION; i++) {
x = (double)rand() * rns;
y = (double)rand() * rns;
if (x*x + y*y < 1) { hits++; }
}
printf("pi = %f\n", 4*(double)hits/LOOP_ITERATION);
return 0;
}
이제 이 2개의 소스코드를 합쳐야 한다. 주의할 점은 두번째 Monte Carlo simulation에서는 rand()함수 대신에 rand_r()을 사용하는 것을 잊지 말아야 한다. 항상 Non-multi-threaded model을 Multi-threaded model로 바꿀때는 MT-safe function이나 reentrant function으로 골라 써야 한다는 점이다.

그리고 false-sharing문제를 피하기 위해서 동일 캐시 라인에 올라갈 수 있는 전역변수나 힙 메모리를 사용하면 안된다는 점이다. 왠만하면 쓰레드 로컬 변수에서 대부분 해결하도록 하자.

그러면 둘을 #pragma omp sections로 합친 코드를 보겠다. 보기 좋게 출력부분의 수정을 했으나 기본 코드는 같다.

#define _XOPEN_SOURCE 600
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <time.h>
#include <sys/times.h>
#include <omp.h>
#ifndef LOOP_ITERATION
#define LOOP_ITERATION 200000000
#endif
double pi[2];
int main()
{
clock_t start_m, end_m;
clock_t sc_clk_tck = sysconf(_SC_CLK_TCK);
start_m = times(NULL);
printf("LOOP ITERATION = %ld\n",(long)LOOP_ITERATION);
#ifdef _OPENMP
omp_set_num_threads(2);
#endif
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
{
int i;
double x, step, hits;
float t_elapsed;
clock_t start, end;
hits = 0.0;
#ifdef _OPENMP
printf("[SECTION] integration method by thread(%d)\n", omp_get_thread_num());
#else
printf("[SECTION] start integration method\n");
#endif
start = times(NULL); /* get clock tick */
step = 1.0/(double) LOOP_ITERATION;
for (i=0; i<LOOP_ITERATION; i++) {
x = (i+0.5) * step;
hits += 1.0/(1.0 + x*x);
}
pi[0] = 4 * hits * step;
end = times(NULL);
t_elapsed = (float) (end - start)/sc_clk_tck;
#ifdef _OPENMP
printf("[SECTION] end integration method by thread(%d):elapsed time(%.02f sec)\n",
omp_get_thread_num(), t_elapsed);
#else
printf("[SECTION] end integration method: elapsed time(%.02f sec)\n",
t_elapsed);
#endif
}
#pragma omp section
{
int i, state, hits;
double x, y, rns;
float t_elapsed;
clock_t start, end;
#ifdef _OPENMP
printf("[SECTION] monte carlo method by thread(%d)\n", omp_get_thread_num());
#else
printf("[SECTION] start monte carlo method\n");
#endif
start = times(NULL); /* get clock tick */
state = time(0);
rns = 1.0/(double)RAND_MAX;
hits = 0;
for (i=0; i<LOOP_ITERATION; i++) {
x = (double)rand_r((unsigned int *)&state) * rns;
y = (double)rand_r((unsigned int *)&state) * rns;
if (x*x + y*y < 1) { hits++; } }
pi[1] = (hits / LOOP_ITERATION) * 4;
end = times(NULL);
t_elapsed = (float) (end - start)/sc_clk_tck;
#ifdef _OPENMP
printf("[SECTION] end monte carlo method by thread(%d): elapsed time(%.02f sec)\n",
omp_get_thread_num(), t_elapsed);
#else
printf("[SECTION] end monte carlo method: elapsed time(%.02f sec)\n",
t_elapsed);
#endif
}
}
}
end_m = times(NULL);
printf("integration PI = %.8f\n", pi[0]);
printf("monte carlo PI = %.8f\n", pi[1]);
printf("* Total elapsed time(%.02f sec)\n", (double)(end_m - start_m)/sc_clk_tck);
return EXIT_SUCCESS;
}
이제 실행을 해보자.

$ gcc -o pi_sections_omp -fopenmp pi_sections.c
$ time ./pi_sections_omp
LOOP ITERATION = 200000000
[SECTION] integration method by thread(0)
[SECTION] monte carlo method by thread(1)
[SECTION] end integration method by thread(0):elapsed time(1.79 sec)
[SECTION] end monte carlo method by thread(1): elapsed time(5.05 sec)
integration PI = 3.14159265
monte carlo PI = 3.14161276
* Total elapsed time(5.05 sec)
real 0m5.052s
user 0m6.858s
sys 0m0.016s
당연히 Numerical Integration이 더 빠르기 때문에 먼저 끝난다. 하지만 implicit barrier가 있기 때문에 대기하게 된다. Monte Carlo simulation은 더 오래 걸리기 때문에 전체 수행 시간은 Monte Carlo simulation이 끝나는 시간에 종료한다.

C언어: OpenMP를 이용한 멀티 쓰레드 프로그래밍 HOWTO #3 http://sunyzero.egloos.com/4234766

[#M_더보기|접기|

6. Single Construct

single construct로 지시된 구간은 단 한번만 실행된다. 실행되는 쓰레드는 여러 쓰레드중에 제일 먼저 진입하는 쓰레드이다.

single construct는 처음으로 진입한 쓰레드가 실행한다.

나머지 쓰레드들은 single construct 끝에 존재하는 implicit barrier에서 대기한다.

single construct가 끝나고 모든 쓰레드들은 implicit barrier에서 동시에 시작한다.

그림에서 보이듯이 parallel 구간에서 쓰레드들 중에 한 개만 single construct를 실행하고 나머지는 뒤에 존재하는 implicit barrier에서 대기하는 것을 볼 수 있다. 그러면 위 소스코드를 컴파일하고 실행해보자. 실행결과는 예상대로 "1. Hello world"는 1번 출력되고, "2. Hello world"는 2번 실행된다.(테스트 호스트는 듀얼 코어이므로)

$ gcc -o omp_single -fopenmp omp_single.c
$ ./omp_single
1. Hello world 2. Hello world 2. Hello world

7. Master Construct

master construct는 single construct와 매우 비슷하다.
하지만 다른 점이 2가지 있다.

master construct 구간은 무조건 master thread (main thread)가 1번 실행한다.

master construct 구간뒤에 implicit barrier가 없다.
즉 모든 쓰레드는 master construct 실행되는 동안에도 계속 실행한다.

실행 결과는 위의 single construct와 같지만 위 그림에서 보듯이 약간의 차이는 있다. master construct는 implicit barrier가 없다는 점이다. 중요한 차이므로 꼭 기억해야 한다.

8. Barrier

배리어란 동기화(synchronization)을 위해서 사용되는 기능이다.

동기화는 시간적 개념이다. 풀어서 설명하기 위해 예를 들자. 스타크래프트 배틀넷은 왠만한 사람이면 다 해봤을 것이다. 최대 8명까지 게임에 참가할 수 있는데, 어떤 유저가 매우 느린 모뎀을 쓰고 있으면 게임 중간에 타임을 세는 화면이 뜨고 기다려주는 것을 볼 수 있다. 이는 빠른 네트워크/컴퓨터를 가진 유저와 느린 네트워크/컴퓨터를 가진 유저의 게임 속도를 맞추기 위해서 배리어가 작동한 것이다. 따라서 결과적으로 배리어는 느린 사람에 맞춰서 앞서 가는 사람이 대기하도록 하는 기능이다.

그러면 프로그래밍에서는 배리어를 어떻게 사용해야 하는가? 작업이 병렬적으로 이뤄진다고 하더라도 전처리, 후처리 작업들이 나눠져 있을 경우에는 전처리 작업들을 병렬처리했을때 어떤 특정 쓰레드가 빨리 처리했다고 후처리 작업을 먼저 출발하면 데이터가 꼬이거나 로직이 망가질 수 있다. 이럴 경우 중간중간에 적절한 배리어를 넣어주면 깔끔하게 해결된다.(하지만 역으로 배리어가 많으면 그 만큼 대기도 많아질 수 있다.)

8.a Implicit barrier

앞에서 implicit barrier(암묵적 배리어)에 대해서 이야기를 많이 했다. OpenMP는 각 작업의 동기화에 대한 편의성을 제공하기 위해서 implicit barrier를 잘 제공한다. 어떤 construct 에 대해서 implicit barrier가 제공되는지 정리하고 넘어가자.

#pragma omp parallel

#pragma omp for

#pragma omp sections

#pragma omp single

위의 4가지의 경우는 블록 끝에 자동적으로 implicit barrier가 들어간다. 하지만 위의 4가지 construct 의 끝에 nowait clause를 지정하면 implicit barrier가 제거되고 대기하지 않고 이후 코드가 즉시 실행된다.

위의 예제에서는 single construct에 nowait를 적용하여 implicit barrier를 제거하는 것을 볼 수 있다.
(그림 아래에 있는 implicit barrier는 parallel construct에 있는 barrier다.)

8.b Explicit barrier

이번에는 사용자가 직접 지정할 수 있는 explicit barrier 기능에 대해서 보겠습니다.

#pragma omp barrier 구문을 지정하면 해당 부분에서 모든 쓰레드가 도착할 때까지 대기하게 된다.

char * get_time0(char *buf, size_t sz_buf);
int main() {
int t_sleep; char buf[16];
#pragma omp parallel private(t_sleep, buf)
{
#pragma omp single nowait
sleep(1);
printf("[%s] phase1:sleep %ld sec.\n", get_time0(buf, sizeof(buf)), t_sleep = times(NULL)%8);
sleep(t_sleep);
#pragma omp barrier
/* explicit barrier */
printf("[%s] phase2. Hello world\n", get_time0(buf, sizeof(buf)));
}
return 0;
}
char * get_time0(char *buf, size_t sz_buf)
{
time_t t0; struct tm tm_now;
if (buf == NULL) return NULL;
if (time(&t0) == ((time_t)-1)) return NULL;
localtime_r(&t0, &tm_now);
if (strftime(buf, sz_buf, "%H:%M:%S", &tm_now) == 0) return NULL;
return buf;
}
이제 실행해보면 배리어 효과때문에 마지막 실행한 19:12:28에서 5초뒤에 phase2가 실행되는 것을 볼 수 있다.

$ ./omp_barrier
[19:12:27] phase1:sleep 1 sec.
[19:12:28] phase1:sleep 5 sec.
[19:12:33] phase2. Hello world
[19:12:33] phase2. Hello world

_M#]

C언어: OpenMP를 이용한 멀티 쓰레드 프로그래밍 HOWTO #4 http://sunyzero.egloos.com/4258873

9. critical & atomic construct

critical construct와 atomic construct는 공유(shared) 영역을 보호하는 lock의 일종이다. 따라서 critical과 atomic을 사용한 영역은 쓰레드 중에 단 하나의 쓰레드만 진입하고 나머지는 대기하게 된다. 즉 직렬실행구간이 된다. 따라서 역으로 말하면 critical과 atomic을 남발하는 프로그래밍을 하면 성능이 확 떨어진다는 소리이다. 그럼에도 불구하고 꼭 lock이 필요한 기능이므로 잘 익혀두어야만 한다.

우선 둘의 차이부터 이해하고 넘어가자. 만일 두 단어만 보고도 감이 오는 사람은 학생 때 운영체제 수업에서 critical section이나 atomic operation을 배운 사람일 것이다.

• critical : 범용적인 lock
• atomic : critical보다 가볍고 빠른 lock (critical의 special한 케이스)

critical은 노멀한 lock이지만 atomic은 매우 가벼운 용도에만 사용한다. 가볍다는 것은 보통 1개의 스칼라 변수를 업데이트 하는 정도를 의미한다. 만일 변수 업데이트를 넘어서 계산이나 캐스팅, 복잡한 데이터 핸들링을 하는 경우라면 critical을 사용하도록 한다.
[참고로 정수형 변수 1개의 값을 변경하는 정도라면 atomic 없이 프로그래밍을 하는 것도 추천한다. atomic을 쓰지 않으면 수치상의 오류가 생기는 경우도 있겠지만 일반적으로는 10ppm(part per million) 이하인 경우이므로 무시할 수 있는 오차 일 수 있다. 왜냐하면 atomic의 가벼운 lock도 멀티 쓰레드에서는 성능을 많이 떨어뜨리기 때문이다.]
[보충 설명: 일반적으로 공유된 데이터에 복수개의 쓰레드가 접근할 경우에는 무조건 lock으로 보호해야만 한다. 모든 교과서나 매뉴얼에는 이렇게 나와있다. 그러나 프로그래머가 어느 정도 멀티 쓰레드에 대한 이해가 깊어지면 교과서나 매뉴얼을 응용할 수 있어야만 한다. 필자가 앞에서 정수형 변수 1개의 값을 업데이트하는 경우에는 lock을 쓰지 않는 것도 좋다고 했는데 이는 감히 교과서에는 쓸 수 없는 내용이다. 하지만 공유된 변수가 약간의 오차가 생겨도 괜찮은 경우, 즉 근접해나 근사치를 계산하는 시뮬레이션이나 휴리스틱 코드라면 atomic을 쓰지 않을 경우 더 빠르게 작동할 수 있다. 그리고 빠른 실행이 가능해졌기 때문에 시행횟수를 더 늘림으로서 오차를 보정할 수 있게된다. 그러므로 오차 보정이 가능한 수치계산이나 오차보다 속도가 더 중요한 문제라면 atomic을 생략하는 것도 고려하라는 뜻이 담겨있는 것이다. 그러나 주의할 점은 꼭 프로그래밍을 할 때 atomic을 선택적으로 적용할 수 있도록 코딩해두고 atomic을 사용한 버전과 사용하지 않은 버전의 차이를 꼭 비교해봐야 한다. 만일 atomic을 사용하지 않은 버전이 메리트가 없다면 반드시 lock을 사용한 버전을 택하는 것이 좋다.

9.1 critical construct

#pragma omp critical [(lock_name)]
critical에서 락 이름(lock_name)을 생략하는 경우는 동일한 lock을 사용하는 것으로 간주되어 critical 지시어가 여러 번 나오더라도 동일하게 보호되는 구간이 된다. 자세한 것은 예제를 보면서 익히도록 하자. 예제로 아래와 같은 pseudo code가 있다.

#pragma omp parallel for
for (i=0; i<MAX_ITERATION; i++) {
process_a();
chk_process();
process_b();
chk_process();
process_c();
chk_summary();
}
위의 예제에서 chk_process() 함수가 lock으로 보호되어야 한다면 critical 지시어를 사용하여 아래와 같이 할 수 있다.

#pragma omp parallel for
for (i=0; i<MAX_ITERATION; i++) {
process_a();
#pragma omp critical
chk_process();
process_b();
#pragma omp critical
chk_process();
process_c();
chk_summary();
}
critical construct을 2군데에서 사용했지만 lock_name을 지정하지 않았기 때문에 같은 lock으로 인식하여 보호된다. [위와 같이 프로그래밍하지 않고 chk_process()함수 내부에 critical을 선언하여도 결과는 같다.]

그렇다면 이번에는 chk_summary()에 critical을 추가해보겠다. 하지만 chk_process()와는 상관없이 다른 락으로 보호하도록 하겠다. 이 경우에는 필수적으로 lock_name을 사용해야 한다.

#pragma omp parallel for
for (i=0; i<MAX_ITERATION; i++) {
process_a();
#pragma omp critical (lock1)
chk_process();
process_b();
#pragma omp critical (lock1)
chk_process();
process_c();
#pragma omp critical (lock2)
chk_summary();
}
이제 critical의 사용방법에 대해서는 어느정도 감이 왔을 것이다. 하지만 거듭 강조하지만 왠만하면 lock은 최소한으로 사용하는 것이 좋다. 멀티 쓰레드 프로그래밍에서 lock을 통한 직렬구간을 많이 만들면 프로그래밍은 쉽지만 성능은 바닥을 치기 때문에 멀티 쓰레드 프로그래밍을하는 의미가 사라지게 된다.

9.2 atomic construct

#pragma omp atomic
atomic은 스칼라 변수 한개를 업데이트 한다고 했다. 너무 간단하기 때문에 간단한 예제 하나로 끝내겠다.

#pragma omp parallel
...생략...;
#pragma omp atomic
n_count++; }
atomic에서 쓸 수 있는 표현식은 ++나 --같은 unary operation이나 "변수=값"정도의 간단한 대입식 정도이다.

10. OpenMP API
앞에서 omp_get_thread_num() 같은 openmp의 함수들을 보았다. 이번에는 주로 사용되는 함수들을 정리해서 보도록 하겠다.

* 쓰레드 풀에 관련된 함수들
void omp_set_num_threads(int num_threads); 병렬 구간에서 생성할 쓰레드 개수를 설정
int omp_get_num_threads(void); 병렬 구간에서 생성할 쓰레드 개수를 리턴
int omp_get_max_threads(void); 쓰레드 최대값 리턴
int omp_get_thread_num(void); 현재 쓰레드 번호 리턴
int omp_get_num_procs(void); 물리적 프로세서의 개수 리턴

int omp_in_parallel(void); 병렬 구간일 경우 true(0이 아닌값), 아니면 false(0)을 리턴

void omp_set_dynamic(int dynamic_threads); 생성할 쓰레드 개수를 동적으로 조정할 지 여부 (dynamic_threads가 1이면 true, 0이면 false)
int omp_get_dynamic(void); 위의 omp_set_dynamic의 설정을 리턴

아래 예제처럼 omp_set_dynamic이 설정되면 사용량에 따라서 쓰레드의 개수가 10개를 넘지 않는 범위에서 적당하게 조정된다.
#include <omp.h>
int main()
{
omp_set_dynamic(1);
#pragma omp parallel num_threads(10)
{
/* do work here */
}
return 0;
}
예제 출처: OpenMP 2.5 Specification

* OpenMP에서 제공하는 lock 기능 API : 정교한 모델을 만들때 유용하므로 꼭 읽어두자.

void omp_set_nested(int nested); nested가 1이면 병렬구간의 중첩을 허용, 0이면 허용하지 않음
int omp_get_nested(void); 위의 nested 설정을 리턴

void omp_init_lock(omp_lock_t *lock); OMP의 lock을 초기화
void omp_init_nest_lock(omp_nest_lock_t *lock); 중첩 lock버전의 위와 같은 기능의 함수 (=재귀잠금이 가능한 lock)

void omp_destroy_lock(omp_lock_t *lock); OMP의 lock을 제거
void omp_destroy_nest_lock(omp_nest_lock_t *lock); nested lock버전의 위와 같은 기능의 함수

void omp_set_lock(omp_lock_t *lock); OMP의 lock을 잠금
void omp_set_nest_lock(omp_nest_lock_t *lock); nested lock버전의 위와 같은 기능의 함수

void omp_unset_lock(omp_lock_t *lock); OMP의 lock을 잠금 해제
void omp_unset_nest_lock(omp_nest_lock_t *lock); nested lock버전의 위와 같은 기능의 함수

int omp_test_lock(omp_lock_t *lock); 잠금 여부를 테스트하여 가능한 상태면 잠그고 다른 쓰레드에 의해 잠긴 상태면 false를 리턴 (=nonblocking 버전의 함수임)
int omp_test_nest_lock(omp_nest_lock_t *lock); nested lock버전의 위와 같은 기능의 함수

double omp_get_wtime(void); 병렬처리 구간에서의 수행 시간(단위: 초)
double omp_get_wtick(void); omp_get_wtime()에서 제공하는 시간 정밀도 (최소 단위 시간)

double start;
double end;
start = omp_get_wtime();
... work to be timed ...
end = omp_get_wtime();
printf("Work took %f seconds\n", end - start);
예제 출처: OpenMP 2.5 Specification

OpenMP 2.5에서 제공하는 모든 API를 다루었다. 특히 lock관련 함수는 중요하기 때문에 잘 알아두면 도움이 된다.

11. OpenMP에서 제공하는 환경변수 및 전처리기

OpenMP에서는 스케줄링, 생성할 쓰레드 개수, 동적 조정 여부, 병렬구간에서 쓰레드의 중첩 허용을 runtime시에 결정할 수 있도록 환경변수를 설정할 수 있다.

• OMP_SCHEDULE : 스케줄링 타입과 chunk 크기를 설정
• OMP_NUM_THREADS : 병렬 구간에서 생성할 쓰레드 개수
• OMP_DYNAMIC : 쓰레드 개수의 동적 조정 여부를 설정
• OMP_NESTED : 쓰레드 중첩의 허용 여부를 설정

사용예 : bash (or POSIX shell)의 명령
export OMP_SCHEDULE="dynamic"
export OMP_SCHEDULE "guided,4"
export OMP_NUM_THREADS 16
export OMP_DYNAMIC true
export OMP_NESTED false

* OMP 조건부 컴파일을 위한 전처리기

#include <stdio.h>
int main()
{
# ifdef _OPENMP
printf("Compiled by an OpenMP-compliant implementation.\n");
# endif
return 0;
}

12. OpenMP vs pthread (POSIX thread)

OpenMP로 작성한 프로그램을 그대로 pthread 버전으로 바꾸면서 둘의 차이를 보도록 하겠다.
예제로 볼 것은 앞에서 numerical integration으로 pi를 계산한 프로그램을 두가지 버전으로 작성해서 비교하도록 하겠다.

우선 HOWTO #1에서 봤던 OpenMP 버전을 다시 보도록 하겠다.
예제 파일 : pi_numerical_integration.c
#include <stdio.h>
#include <stdlib.h>
int num_steps=1000000000; /* 10억번 : 너무 많으면 조금 줄이시길... */
int main()
{
int i;
double x, step, sum = 0.0;
step = 1.0/(double) num_steps;
#pragma omp parallel for private(x) reduction(+:sum)
for (i=0; i<num_steps; i++) {
x = (i+0.5) * step;
sum += 4.0/(1.0 + x*x);
}
printf("PI = %.8f (sum = %.8f)\n", step*sum, sum);
return EXIT_SUCCESS;
}
OpenMP버전은 이미 설명했었기 때문에 이를 바로 Pthread 버전으로 바꾸도록 하겠다.

pthread 버전 예제 파일 : pi_integration_pth.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
static int num_steps=1000000000;
double pi, step;
struct start_arg {
int i_start;
int i_end;
double sum;
} start_arg[2];
void *start_func(void *arg)
{
int i;
double x, sum = 0.0;
struct start_arg *p_arg = (struct start_arg *) arg;
for (i=p_arg->i_start; i<p_arg->i_end; i++) {
x = (i+0.5) * step;
sum += 4.0/(1.0 + x*x);
}
p_arg->sum = sum;
return NULL;
}
int main()
{
int i;
double sum;
pthread_t pt_id[2];
step = 1.0/(double) num_steps;
start_arg[0].i_start = 0;
start_arg[0].i_end = num_steps>>1;
start_arg[1].i_start = start_arg[0].i_end + 1;
start_arg[1].i_end = num_steps;
printf("%d~%d, %d~%d\n",
start_arg[0].i_start, start_arg[0].i_end ,
start_arg[1].i_start, start_arg[1].i_end );
for (i=2; i--; ) /* Create Pthread */ {
if (pthread_create(&pt_id[i], NULL, start_func, &start_arg[i])) {
perror("pthread_create");
return 1;
}
}
for (i=2; i--; ) /* join pthread : explicit barrier */
{ if (pthread_join(pt_id[i], NULL)) {
perror("pthread_join");
return 1;
}
}
sum = start_arg[0].sum + start_arg[1].sum;
printf("PI = %.8f (sum = %.8f)\n", step*sum, sum);
return EXIT_SUCCESS;
}
pthread 버전으로 바꾸면 openmp버전보다 코딩량이 훨씬 늘어난다.

POSIX thread를 사용하면 OpenMP에서 없는 explicit barrier를 넣어주어야 하므로 pthread_join()함수를 사용했으며, OpenMP에서 간단하게 reduction을 했던 것이 POSIX thread에서는 개별적인 start_arg라는 구조체를 통해서 확인했다. 이로 인해서 코딩량과 자료구조까지 신경써야 하는 불편함이 생긴다.

그러나 OpenMP가 POSIX thread보다 우월하다고 말하는 것은 아니다. 문제가 정교함을 요구하는 경우에는 오히려 OpenMP가 적합하지 않은 경우도 많기 때문이다. 실제로 조건변수를 이용한다든지 쓰레드 키를 이용한 라이브러리등을 사용하는 경우라면 POSIX thread외에는 대안이 없는 경우가 많기 때문이다. 이 글은 OpenMP를 소개하는 글이므로 OpenMP에 대해 좋은 말만 늘어놓고 있지만 필자의 말을 비판없이 받아들여서 OpenMP가 최고라는 편협한 사고에 휩싸이지는 않았으면 좋겠다.

잡설이 길었는데 마지막으로 두가지 버전의 실행 결과를 확인해보자. 첫번째 실행한 파일인 pi_integration이 OpenMP버전이고, 두번째의 pi_integration_pth가 Pthread버전이다.

$ time ./pi_integration
PI = 3.14159265 (sum = 3141592653.59036255)
real 0m3.910s
user 0m7.484s
sys 0m0.018s

$ time ./pi_integration_pth
0~500000000, 500000001~1000000000
PI = 3.14159265 (sum = 3141592650.38979244)
real 0m4.071s
user 0m7.399s
sys 0m0.022s
결과를 보면 실행결과나 성능에 큰 차이가 없어 보인다. 하지만 몇몇 컴파일러에서는 특정 버전이 더 느린 경우도 있다.(이는 해당 플랫폼의 특징에서 기인한다. 표준안에는 성능에 대한 제약은 없기 때문에 몇몇 플랫폼은 OpenMP 구현시 덜 최적화 되어있는 경우도 있다.)

13. 마치면서.

처음 시작하면서 멀티 쓰레드 프로그래밍의 필요성에 대해서 언급했었다. CPU의 개별 코어의 주파수(frequency)는 거의 한계치에 와 있기 때문에 개별 코어의 속도는 파이프라인의 증설이나 몇가지 기술로 약간의 진보밖에 이룰 수 없게 되었다. 따라서 멀티코어를 적극적으로 사용하는 기술이 뒷받침되지 않고는 프로그램의 성능을 높일 수 있는 방법은 거의 없다.(일각에서 언급되는 그래픽카드의 코어를 병렬로 이용하는 GPGPU도 같은 맥락이다.) 하지만 멀티 쓰레드 프로그래밍은 다음과 같은 난제가 있다.

멀티 쓰레드 프로그램의 문제점 : 디버깅이 힘들다. (재현성이 나쁘기 때문)

아키텍처와 메모리 모델에 대한 이해가 필요하다. (본인도 부족하다. 그래서 실수를 할 때가 있다.)

첫째로 문제인 디버깅에서 언급되는 재현성은 쓰레드 프로그래밍에서 큰 난제이다. 디버깅을 위해서는 같은 조건하에서 시행하였을때 동일한 문제가 재현되어야만 버그를 찾아낼 수 있다. 그러나 멀티 쓰레드 프로그램은 각각의 쓰레드들이 같은 순서로 실행된다는 보장이 없기 때문에 버그가 발생한 순서조합이 디버깅때도 항상 발생하지 않는다. 즉 문제를 찾아내려고 할때는 오히려 제대로 작동하는 경우도 많다는 것이다.

따라서 멀티 쓰레드 프로그램을 대형 모델에 적용할 때는 투명성을 높여서 각각의 데이터나 태스크의 흐름을 모니터링할 수 있도록 만들어야 한다. 이를 위해서 여러 방법론이 나와있지만 스페셜한 케이스에는 딱 들어맞는 것은 없다. 그러므로 반복적인 프로그래밍 훈련만이 투명성을 높이고 디버깅이 쉬운 개발철학을 만들 수 있게 해준다.

둘째로 우리가 종종 사용하는 x86 인텔 호환 플랫폼은 PC환경에서 가장 많이 쓰이지만 산업체에서는 IA64, Sparc, MIPS, PPC(PowerPC) 등등의 CPU에 여러가지 OS조합의 플랫폼이 사용된다. 그러나 같은 프로그래밍을 짜도 표준안에서 언급한 semantic을 만족하면서 미묘한 차이를 보이는 경우가 많다. 특히 기능은 제대로 작동하는데 성능은 이상하게 차이나는 경우가 발생할 수 있다. 이를 해결하기 위해서는 각각의 플랫폼에 대한 이해와 하드웨어 지식이 필요한데, 한사람의 프로그래머가 모든 플랫폼에 정통할 수는 없기 때문에 적극적으로 다른 플랫폼의 전문가와 소통할 수 있는 채널이 있어야만 한다. (더 중요한 점은 다른 플랫폼의 전문가와 제대로 소통할 수 있도록 질문을 잘 하는 방법을 익히는 것이다. 간혹 질문을 잘 못하고 횡설수설하면 답변을 해주고 싶어도 못한다. 필자도 좀 횡설수설하는 스타일이라 고치려고 하는데 참 어렵다.)

하지만 이런 어려움은 점차 해소될 전망이다. 앞으로 나오는 많은 기술들과 소프트웨어 방법론들은 프로그래머가 복잡한 이론이나 방법론을 몰라도 멀티 쓰레드 프로그래밍을 쉽게 할 수 있도록 돕고 있다. 실제로 10년전과 지금은 하늘과 땅 차이로 멀티 쓰레드 프로그래밍이 쉬워졌다.(그럼에도 불구하고 아직도 멀티 쓰레드 프로그래밍은 어려운 분야이지만...)

비슷한 예를 하나 들자면 15년전쯤에 필자가 프로그래밍을 처음 접하던 시절에는 그래픽 처리를 위해 어셈블리어를 배우는 것이 유행했던 시절이 있었다. 속도와 최적화 문제에서 다른 대안이 없었기 때문이었다. 그러나 지금은 어셈블리어를 몰라도 왠만한 그래픽 최적화를 하는데 무리가 없다.(아주 가끔 어셈블러에 의지해야 하는 스페셜 케이스가 있긴하다.) 이는 시간이 지나면 좀 더 편리한 프로그래밍 환경이 만들어진다는 것을 의미한다.

그렇다면 이쯤에서 독자들은 필자에게 반문할 것이다. "멀티 쓰레드 프로그래밍이 쉬워지기를 기다리라는 말입니까?" 이에 대한 필자의 대답은 "절반은 그렇다"이다. 왜 절반만 Yes를 하는지는 그 쉬워지는 시점 때문이다. 많은 선도자들은 예측하기를 멀티 쓰레드 프로그래밍의 하드웨어적, 소프트웨어적 난제들이 해결되어 많은 부분에서 변화가 생기려면 적어도 5~10년후가 되어야 할 것이라고 한다. 그렇다면 본인이 앞으로 5~10년을 기다릴 수 있는 형편인지 아니면 당장 써야 하는지 결정해야한다. 한창 공부하는 학생이라면 더 기다리다가 공부해도 되겠지만 field에서 일하는 산업역군이라면 당장 공부하라고 말해주겠다.

저작자표시 비영리 변경금지

'1.소프트웨어 이야기 > 09.ETC' 카테고리의 다른 글

XCOPY 사용 방법 (0)	2010.01.14
[펌] Tip of finding Bugs (0)	2009.12.16
switch case 문안에 변수나 클래스를 초기화 하고자 할때.. (0)	2009.11.25

김용유닷컴