최근 포토로그


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

이번 글에서는 OpenMP의 Loop scheduling에 대해서 조금 알아보려고 합니다. OpenMP의 Loop scheduling이 운영체제의 scheduling을 제어하는 것은 아닙니다. 단지 OpenMP가 관장하는 Thread들이 좀 더 효과적으로 작업을 처리할 수 있도록 scheduling 방법을 제어하는 정도의 수준입니다. 다음 코드를 보시고 기본 scheduling으로는 뭔가 부족한 부분이 있다는 것을 파악하실 수 있다면 좋겠군요.

#include <omp.h>
int _tmain(int argc, _TCHAR* argv[])
{
omp_set_num_threads(4);

clock_t startTime = clock();
#pragma omp parallel
{
int threadCount = omp_get_num_threads();
#pragma omp for schedule(static)
for (int i = 0 ; i < threadCount * 5 ; i++)
{
Sleep(i * 100);
_tprintf(_T("Thread Num: %d, counter = %i\n"), omp_get_thread_num(), i);
}
_tprintf(_T("Thread Num: %d, Finished\n"), omp_get_thread_num());
}
_tprintf(_T("Elpase Time: %d\n"), clock() - startTime);
}


일단 조금 낯선 header file이 하나 있습니다. omp.h 파일인데요. 앞서 수 차례 OpenMP가 compiler directive, library function, environment variable의 집합이라고 말씀 드린 바 있는데요. 오늘 예제에서 드디어 library function을 처음으로 사용하게 되네요. 내용은 간단합니다. OpenMP도 나름의 library들을 가지고 있고 이를 사용하기 위해서는 omp.h header file을 include 해야 하는 것입니다. 제공되는 함수는 omp.h header 파일 내부를 들여다 보면 알 수 있는데, 그 개수가 2.0을 기준으로 22개 밖에 되지 않고, 함수의 이름만을 살펴보아도 대략적인 의미를 파악하실 수가 있을 정도입니다. 위 예제에서는 3개의 함수를 사용해 보았습니다.



omp_set_num_threads() 뒤따르는 parallel region에서 사용할 thread의 개수를 지정함
omp_get_num_threads() 현재 parallel region에서 사용 중인 thread의 개수를 가져옴
omp_get_thread_num() 현재 이 함수를 호출한 thread의 고유 번호



omp_set_num_threads같은 경우는 #pragma omp parallel num_threads() 를 이용해서도 설정할 수 있었죠. 위 예제에서는 4로 설정하여 총 4개의 thread를 운용하겠다는 의미가 됩니다. omp_get_num_threads()는 앞서 thread의 갯수를 4로 설정하였기 때문에 당연히 4가 반환될 것입니다. omp_get_thread_num() 함수의 호출도 보일텐데요, 이 함수를 호출하면 해당 함수를 호출한 thread의 고유 번호가 반환됩니다. windows의 경우 thread handle(process 단위)혹은 thread id(system 단위)라는 값으로 각각의 thread들을 구분할 수가 있는데요, 여기서 반환되는 값은 process단위의 unique identifier이긴 하지만 thread handle 값과 그 값이 일치하지는 않고, 단지 0, 1, 2 와 같이 linear한 값이 반환됩니다.



코드를 살펴보면 loop 반복횟수는 thread 갯수 x 5 를 했으니, 각각의 thread 별로 반복횟수를 공정하게 scheduling 된다고 가정하면 총 5회씩 반복을 수행하게 되겠지요. Loop 내에서 하는 일이라고는 loop 변수 값인 i * 100만큼의 시간만큼 기다린 후, Thread 번호와, i 값을 출력 하는 것이 전부입니다.



 image



위 결과를 좀 자세히 살펴보시죠. counter의 최대 값이 19인 것은 thread 갯수(4) x 5 까지 반복했으니 당연한 결과입니다. 0번 Thread의 경우 0,1,2,3,4의 반복을 수행하였고, 3번 Thread의 경우 15, 16, 17, 18, 19의 반복을 수행하였습니다. 그런데 말이죠, 반복 횟수로만 본다면 각 thread별로 5회씩 아주 공정하게 작업이 배분된 것으로 보이지만, 수행 시간으로 본다면 아주 불공정하죠. 왜냐하면 실제로 loop내에서 수행하는 업무가 iterator(i) 값에 비례하기 때문입니다. Sleep 시간으로만 Thread의 수행 시간을 계산해 보면 0번 Thread의 경우 0+1+2+3+4 = 10 이므로 10 x 100의 시간. 즉 1초 만큼만 loop 내부를 수행하면 됩니다. 하지만 3번 thread의 경우 15+16+17+18+19 = 85이므로 85 x 100의 시간 즉 8.5초 만큼의 시간을 소비하게 됩니다. 일찌감치 loop 순회를 마친 0~3분 thread들은 가장 느려터진 3번 thread가 완료될 때까지 아무런 일도 하지 않고 기다리게 됩니다. 결국 3번 thread의 작업이 모두 완료되면 그제서야 “… Finished”를 각각 출력하게 되죠. 총 소요시간은 대략 8.5초가 소요되었네요. 이 값은 thread 3번의 총 수행 시간과 일치하고 있음을 알 수 있습니다. 각 쓰레드들의 능력은 동일한데 주어진 일감을 완료할 때까지 걸리는 시간이 서로 다르기 때문에 이런 문제가 생기는 것이겠죠. 어떻게 하면 이러한 작업을 좀 더 효과적으로 수행할 수 있을까요? 한가지 idea는 0번 thread가 수행하는 loop를 0,1,2,3,4로 하지 말고, 0,4,8,12,16번을 수행하게 하고 1번 thread가 1,5,9,13,17번을 수행하고, 2, 3번 thread도 각각 그런 식으로 일을 가져가면 좀 더 효과적이지 않을까요? 이렇게 하기 위해서는 코드를 약간만 수정하면 됩니다.

#pragma omp for schedule(dynamic)


schedule이라는 새로운 construct가 나왔네요. 이 부분이 바로 바로 앞서 이야기한 바와 같이 OpenMP가 scheduling을 어떻게 수행할지를 결정해주는 부분입니다. 일단 프로그램의 수행 결과부터 살펴보죠.



image



Wow! 단지 schedule(dynamic) 이라는 construct를 하나 추가했을 뿐인데 속도가 무려 3초나 개선되었군요. 이제 schedule construct에 어떤 값을 지정할 수 있는지 세부적으로 살펴보도록 하겠습니다.



#pragma omp parallel for schedule(kind[, chunk size])



static loop 반복회수를 thread수로 나눈 chuck 갯수만큼 순차적으로 작업을 수행합니다.(이 schedule 방식이 기본 scheduling 방식입니다. 즉 schedul 이하를 쓰지 않으면, 이 schedule방식을 사용합니다.
dynamic loop반복횟수를 chunk size로 나눈 독립된 작업으로 생각하고, 각 작업을 queueing한 후 thread들이 순차적으로 job을 가져가게 합니다. 만일 chuck size를 지정하지 않으면 기본 값은 1이 됩니다.
guided dynamic과 유사하지만 chuck size를 처음에는 크게 시작하여, 점점 chuck size를 줄여갑니다.
runtime OMP_SCHEDULE 환경 변수에 지정된 값으로 scheduling 합니다. OMP_SCHEDULE로 지정할 수 있는 값을 앞서 알아본 static, dynamic, guided 중 하나입니다.



먼저 chuck size라는 용어부터 정리해 보아야 할 것 같습니다. chuck size는 각 thread에게 할당하는 고정된 iteration 횟수를 의미합니다. 즉 loop가 총 20회 반복되어야 하고, thread의 갯수가 4개라면, chuck size는 5가 됩니다. 위의 첫번째 예와 같이 loop를 수행한다면 i=0~4는 첫 번째 thread가, i=5~9까지는 두 번째 thread가 각각 작업을 수행하게 됩니다. dynamic의 경우는 위의 두 번째 예와 같이 chuck size를 기본 1로 가져가기 때문에, 업무가 loop 반복 횟수로 쪼개지고, 이것을 각각의 thread가 순차적으로 가져가는 형태로 scheduling이 됩니다. 그렇다면 무조건 dynamic이 좋은 걸까요? 그렇지는 않습니다. 각각의 thread에게 작업이 한번에 할당되지 않기 때문에, thread간의 context switching이 빈번하게 일어나게 되므로 performace의 손해를 볼 가능성도 배제할 수 없습니다. static와 dynamic의 장점만을 취하고자 한 scheduling 방식이 guided 인데요, 이 방식은 전체 반복횟수를 처음에는 chuck size를 크게 하여 job을 쪼개고 뒤로 갈수록 chuck size를 줄여가면서 job을 쪼갭니다. scheduling을 설정하는 이유는 parallel region을 수행하는 각각의 thread들이 동시에 작업을 마칠 수 있도록 하기 위함인데 guided 방식을 사용함으로써, thread간 switching회수를 줄이면서도 동시에, 작업 수행에 걸리는 시간을 적절히 thread별로 배분하기 위한 방법이라고 볼 수 있습니다. 각각의 scheduling 방식에 대한 결과를 살펴보기로 하죠.

#pragma omp for schedule(static, 2)


image



chunk size를 2로 설정했기 때문에 0번 thread가 최초에 0, 1 반복을 수행하였고, 1번 thread는 2, 3을 2번 thread는 4,5, 3번 thread는 6,7을 각각 수행했습니다. dynamic은 위에서 살펴보았으니 guided를 알아보죠.

#pragma omp for schedule(guided)


image



2번 thread의 경우 처음에는 0,1,2,3,4로 5번의 iteration을 할당 받았지만, 그 다음에는 14,15로 2번의 iteration을 마지막으로는 19로 1번의 iteration만을 할당 받았습니다. 어떻게 알 수 있냐구요? counter를 0부터 순차적으로 listup 해보면 알 수 있습니다. 아래처럼 말이죠



Thread Num: 2, counter = 0
Thread Num: 2, counter = 1
Thread Num: 2, counter = 2
Thread Num: 2, counter = 3
Thread Num: 2, counter = 4
Thread Num: 0, counter = 5
Thread Num: 0, counter = 6
Thread Num: 0, counter = 7
Thread Num: 0, counter = 8
Thread Num: 1, counter = 9
Thread Num: 1, counter = 10
Thread Num: 1, counter = 11
Thread Num: 3, counter = 12
Thread Num: 3, counter = 13
Thread Num: 2, counter = 14
Thread Num: 2, counter = 15
Thread Num: 3, counter = 16
Thread Num: 0, counter = 17
Thread Num: 1, counter = 18
Thread Num: 2, counter = 19



이해 되시죠?
OpenMP의 기능 중에 일부는 Environment variable의 설정 값에 따라 그 기능의 세부 수행 방식이 변경될 수 있습니다. 위에서 만일 schedule 방식을 runtime으로 변경한 후, OMP_SCHEDULE environment variable 값을 다음과 같이 변경하면, dynamic schedule을 수행하게 됩니다.



set OMP_SCHEDULE=dynamic



오늘 알아볼 마지막 concept은 barrior라는 것입니다. barrior는 말 그대로 해석하면 “장벽”인데요, 각각의 thread가 자신에게 할당된 일을 모두 마무리 했을 때, barrior에서 다른 thread가 작업을 완료할 때까지 기다리도록 하는 역할을 수행합니다. barrior는 명시적으로 설정하지 않더라도 대부분 암시적으로 지정되는데요. 위 코드에서도 암시적인 barrior를 찾으실 수 있을 겁니다.

for (int i = 0 ; i < threadCount * 5 ; i++)
{
Sleep(i * 100);
_tprintf(_T("Thread Num: %d, counter = %i\n"), omp_get_thread_num(), i);
} // 바로 여기가 암시적인 barrior 입니다. 모든 thread들은 작업이 완료되더라도 여기서 기다리게 되죠.
_tprintf(_T("Thread Num: %d, Finished\n"), omp_get_thread_num());


하지만 굳이 이렇게 다른 thread들의 작업 완료를 기다릴 필요가 없다면, nowait를 사용하여 barrior를 없애 버릴 수도 있습니다.

#pragma omp for schedule(static) nowait
for (int i = 0 ; i < threadCount * 5 ; i++)
{
Sleep(i * 100);
_tprintf(_T("Thread Num: %d, counter = %i\n"), omp_get_thread_num(), i);
} // 이제 작업을 완료한 thread는 다른 thread를 여기서 기다리지 않습니다.
_tprintf(_T("Thread Num: %d, Finished\n"), omp_get_thread_num());


결과가 어떻게 바뀔지 예측이 되시나요?



image



Thread의 완료를 나타내는 Finished 출력이 중간 중간에 흩어져 있을 것을 보실 수 있을 겁니다.



사실 OpenMP의 loop scheduling은 Platform에서의 scheduling이라기 보다는 loop의 iteration을 어떻게 각 thread에 적절히 배분할까에 대한 문제에 focusing하고 있음을 알 수 있습니다. 따라서 각각의 작업에 걸리는 시간이 동일함에도 불구하고, 동적으로 우선순위를 높여서 특정 thread가 빨리 작업을 마치게 한다거나 혹은 iteration 중에 동적으로 scheduling 방식을 변경하는 등의 고급 scheduling을 구현할 수는 없습니다.



오늘은 이 정도까지만 살펴볼까 합니다. 감사합니다.

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


덧글

  • 감감이 2015/02/27 15:27 # 삭제 답글

    좋은글 감사합니다~ 많이 배워갑니다 ㅎㅎ
  • sirUM 2017/12/16 17:08 # 삭제 답글

    좋은 설명 감사합니다 ㅠㅠ!
댓글 입력 영역


facebook 프로필 위젯

트위터 위젯