페이지

▼

2014년 12월 29일 월요일

OpenMP를 이용한 멀티 쓰레드 프로그래밍 HOWTO #1


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


목차
0. 시작하기에 앞서
1. OpenMP란?
2. OpenMP의 시작
3. OpenMP를 이용한 work-sharing 모델
4. Loop construct
  4.a Loop consturct 기본 형태
  4.b 병렬 처리시 주의점
  4.c 스케줄링
* 연습문제 (멀티 쓰레딩과 reentrant 함수의 관계에 대한 문제)
5. Section construct
* 연습문제 (섹션별로 task를 할당하는 방법)
6. Single Construct
7. Master Construct
8. Barrier
  8.a Implicit barrier
  8.b Explicit barrier
9. critical & atomic construct
  9.1 critical construct
  9.2 atomic construct
10. OpenMP API
11. OpenMP에서 제공하는 환경변수 및 전처리기
12. OpenMP vs pthread (POSIX thread)
13. 마치면서 

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

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

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

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

* 이 글은 intel Korea의 도움으로 작성된 글이며, 대부분의 자료는 intel Multi-Core CPU제품과 intel compiler에서 테스트 되었다. 



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 construct4.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의 크기는 다음 공식을 따른다. 























시간:




















댓글 없음:
















댓글 쓰기