병렬 처리에서 가장 중요한 변수 중 하나인 스케줄링입니다. 스케줄링은 병렬화 한 구문을 어떤 스레드에게 어떻게 분배할지 결정하는 것입니다. 만약 이걸 std::thread와 같은 스레드에 구현해서 쓰려고 하면 아주 골치 아파집니다. 자세히 알고 싶으시면 즐거운 운영체제 강의를 열심들 들어 봅시다~ 유후~(졸업해서 다행이다..) OpenMP는 골치 아픈 스케줄링을 간편하게 구현해 줍니다. 쉽게 3가지 대표적인 스케줄링 기법이 있고, 사용자가 원한다면 만들어 사용할 수 있습니다.
OpenMP의 스케줄링
스케줄링에 들어가기에 앞서 이용되는 변수인 chunk에 대해 알아보죠. OpenMP에서 chunk는 스레드에게 분배하는 task의 최저 크기입니다. 만약 task의 총 개수가 11개 이고, chunk가 1이라면 OpenMP는 task를 1개씩 11개로 분배해서 구동합니다. 동일 환경에서 chunk가 10이라면, OpenMP는 10개와 1개의 task로 분류하여 사용하게 되는 거죠. 아래에 나올 구동 결과를 보시면 쉽게 이해할 수 있습니다.
일단 세 가지 스케줄링 기법을 알아보죠. 아래 설명에서는 4개의 스레드를 사용할 수 있는 환경에서 101개의 태스크를 수행한다고 가정합니다.
- Static : 병렬화 구문의 태스크를 chunk의 크기로 분할하여, 구문의 구동 전 각 스레드에게 미리 분배합니다.
- Dynamic : 태스크를 chunk의 크기로 분할해 둔 뒤, 구동 중 태스크를 끝낸 스레드에게 남은 태스크를 분배합니다.
- Guided : Dynamic과 Static의 장점을 취합한 구조입니다. Dynamic과 동일한 동작 구조이지만 처음엔 다수의 태스크를 분배해 준 뒤, 구동 중 분배해주는 태스크의 숫자를 줄입니다. chunk 크기는 분배해주는 태스크의 최저 개수가 됩니다.
개념적으로 Static은 정적인 스케줄링 기법으로 스레드의 상태나 각 태스크의 작업량 차이에 상관없이 같은 수의 태스크를 미리 분배하는 방식입니다. Dynamic은 동적인 스케줄링 기법으로 태스크를 마치는 스레드에게 남은 태스크를 분배해 주는 방식이죠. Static은 사전에 분배를 마치기 때문에 모든 태스크의 작업량이 같고, 스레드의 성능이 모두 동일한 경우 좋은 성능을 보여 줍니다. Dynamic은 구동 중에도 태스크를 관리하며, 스레드에게 분배해줘야 하는 작업이 추가되기 때문에 리소스를 더 사용합니다. 따라서 태스크의 작업량 차이가 크고 스레드 별 성능 차이가 큰 경우 적합합니다.
스케줄링 방법은 간단합니다. 기존 parallel for 구문의 끝에 schedule(schedule_type, chunk_size)를 지정합니다. schedule_type은 상기 3가지 스케줄링 타입이나 사용자 지정, runtime 중 선택해 주시면 됩니다. chunk_size는 기본값으로 하고 싶은 경우 -1로 지정하고, 원하는 사이즈가 있으면 지정합니다. 아래 예제를 보시면 쉽게 이해하실 수 있을 것입니다.
#pragma omp parallel for schedule(static, 10)
#pragma omp parallel for schedule(dynamic, 1)
#pragma omp parallel for schedule(guided, 1)
글로는 따분하기만 하니 적합한 예제로 설명드리겠습니다. 아래 예제는 101개의 태스크를 openMP가 스케줄러 선정에 따라 어떻게 분배하는지 보여주는 코드입니다. 병렬 처리된 태스크가 너무 간단하면 작업 분배가 제대로 이루어지지 않을 수 있기 때문에 간단한 소수 판별 함수를 이용해서 100,000,007(100,000,000 이상의 가장 작은 소수) 이 소수인지 판별하게 합니다.
#include <iostream>
#include <vector>
#include <thread>
#include <chrono>
#include <omp.h>
using namespace std;
bool isPrime(int src){
for(int i =2 ; src > i ; i++){
if(0 == (src%i)){
return false;
}
}
return true;
}
int main(int argc, char ** argv){
bool isprime;
omp_sched_t scheduleType = static_cast<omp_sched_t>(atoi(argv[1]));
int nChunk = -1;
if(3 == argc){
nChunk = atoi(argv[2]);
}
vector<vector<char>> arr(4, vector<char>(101, ' '));
omp_set_num_threads(4);
omp_set_schedule(scheduleType, nChunk);
#pragma omp parallel for schedule(runtime)
for(int i = 0 ; 101 > i ; i++){
isprime = isPrime(100000007);
arr[omp_get_thread_num()][i] = '*';
}
for(int i = 0 ; 4 > i ; i++){
cout << "thread " << i << " : ";
for(int j = 0 ; 101 > j ; j++){
cout << arr[i][j];
}
cout << endl;
}
return 0;
}
구동후 처음에는 argument로 넘어온 두 가지 변수(schduleType, nChunk)를 파싱 합니다. omp_sched_t는 openMP의 스케줄러 타입을 지정합니다. 1부터 4까지 있으며, 1은 static, 2는 dynamic, 3은 guided, 4는 auto입니다. chunk 사이즈는 미지정시 -1(기본값)로 지정합니다. omp_set_num_threads 함수를 이용해 사용하는 스레드의 숫자를 4개로 줄입니다. 이후 omp_set_schedule 함수로 스케줄러 타입과 chunk의 사이즈를 적용합니다. 병렬 처리 구문은 #pragma omp parallel for schedule(runtime)입니다. 윗줄에 omp_set_schedule이 있으나 그래도 명확히 runtime 형태의 스케줄러를 이용한다고 명시해야 합니다. 그렇지 않으면 기본 스케줄러(static, -1)를 이용합니다.
병렬 처리 구문은 100,000,007이 소수인지 확인한 후, 할당받은 태스크가 어느 스레드에서 구동되었는지 vector에 표기합니다. 구문이 끝나면 결과를 출력하고 종료하죠.
그럼 구동 결과를 보여 드리겠습니다. 먼저 static 스케줄러입니다.
chunk가 기본 값(-1) 인경우 전체 task를 순서대로 각 스레드에 분배됩니다. 지정해 주면 지정된 chunk의 값대로 태스크를 나누어 마스터 스레드부터 순서대로 분배합니다. 두 번째와 세 번째 결과를 보면 마지막 태스크는 다른 태스크와 함께 분배되지 않았죠. chunk가 총 태스크 수에 나누어 떨어지지 않으면, 남는 태스크만 따로 분할됩니다. 만약 chunk 사이즈가 너무 크면(4번째 case) 병렬화가 전혀 되지 않을 수도 있습니다.
다음으로 dynamic 스케줄러의 결과입니다.
Static과 다르게 순서대로 분배되지 않습니다. 4가지 스레드가 각기 할당받은 태스크를 수행한 후 태스크가 종료되면 다음 태스크를 할당받기 때문입니다. 그 외에는 static과 동일하죠.
다음은 guided 스케줄러입니다.
Dynamic과 동일하게 할당된 태스크가 종료되면 다음 태스크를 할당받아 처리합니다. dynamic과 다른 점은 초기엔 분배받은 태스크의 개수가 많지만 구동되면서 점차 줄어듭니다. 단 분배받는 태스크의 개수는 chunk보다 작아지지는 않습니다. (남는 태스크 제외)
마지막으로 auto입니다.
이 예제에서 auto 스케줄러는 guided 스케줄러를 선택했습니다. 그리고 chunk는 무시됩니다. 자동으로 하겠다고 했으니, chunk도 가장 적합한 모델로 선정된 것이죠.
그럼 다음으로 동일 소프트웨어의 구동 시간 분석을 해보겠습니다. 시간 측정을 위해 구동 코드는 아래와 같이 변경됩니다.
#include <iostream>
#include <vector>
#include <thread>
#include <chrono>
#include <omp.h>
using namespace std;
bool isPrime(int src){
for(int i =2 ; src > i ; i++){
if(0 == (src%i)){
return false;
}
}
return true;
}
int main(int argc, char ** argv){
bool isprime;
omp_sched_t scheduleType = static_cast<omp_sched_t>(atoi(argv[1]));
int nChunk = -1;
if(3 == argc){
nChunk = atoi(argv[2]);
}
vector<vector<char>> arr(4, vector<char>(101, ' '));
omp_set_num_threads(4);
omp_set_schedule(scheduleType, nChunk);
chrono::time_point<chrono::high_resolution_clock> sTime;
chrono::time_point<chrono::high_resolution_clock> eTime;
double cTime;
double minTime = 10000000.;
double maxTime = 0.;
double sumTime = 0.;
for(int t = 0 ; 5 > t ; t++){
sTime = chrono::high_resolution_clock::now();
#pragma omp parallel for schedule(runtime)
for(int i = 0 ; 101 > i ; i++){
isprime = isPrime(100000007);
arr[omp_get_thread_num()][i] = '*';
}
eTime = chrono::high_resolution_clock::now();
cTime = static_cast<double>((chrono::duration_cast<chrono::milliseconds>(eTime-sTime)).count())/1000;
minTime = min(minTime, cTime);
maxTime = max(maxTime, cTime);
sumTime += cTime;
}
cout << "min : " << minTime << endl;
cout << "avg : " << sumTime/5 << endl;
cout << "max : " << maxTime << endl;
return 0;
}
스냅숏으로 보기 힘든 결과이니 표로 정리하였습니다. 조건의 위 스냅숏들과 같습니다. 코드 상으로는 min, max도 출력시키지만 표로는 평균 수치만 비교하였습니다.
| -1 | 2 | 4 | 101 | |
| static | 4.425 | 4.497 | 4.821 | 16.345 |
| dynamic | 4.449 | 4.472 | 4.963 | 16.364 |
| guided | 4.375 | 4.396 | 4.522 | 15.950 |
| auto | 4.510 | 4.387 | 4.328 | 4.330 |
표기된 단위는 모두 sec입니다. 위 예제에서 모든 태스크는 동일한 작업을 하니 이론적으로 static이 가장 효과적 이어야 합니다. 하지만 chunk가 -1인 결과에서 모두 4.375초에서 4.510초로 어떤 방식이 더 좋다고 결정하기 어렵습니다. 그 이유는 사용된 컴퓨팅 시스템의 구조 때문입니다.
일반적인 컴퓨팅 시스템은 다목적으로 설계됩니다. 그래서 컴퓨팅 시스템은 운영체제를 구동하고, 운영 체제가 소프트웨어와 하드웨어들을 관리하죠. 부팅 직후에도 구동 중인 소프트웨어의 종류를 보면 수십 가지에서 수백 가지가 구동됩니다. 이러한 환경에서 컴퓨팅 시스템의 하드웨어를 하나의 소프트웨어가 독점하는 일은 발생할 수 없습니다. 만약 그런 일이 발생한다면 대화형 인터페이스는 불가능하고, 사용자는 컴퓨터가 일을 끝낼 때까지 경과도 모르는 상태로 기다려야 하죠.
현대 운영체제가 시분할 시스템을 이용하는 이상 구동 소프트웨어들은 서로 하드웨어를 사용하기 위해 경쟁하고, 운영체제는 각 소프트웨어를 제어합니다. 이런 환경이다 보니 예제의 소프트웨어도 하드웨어를 독점하지 못하고, 다른 소프트웨어와 같이 구동되어, 이론과 같은 결과를 얻지 못한 것입니다.
그래도 아예 의미 없는 결과는 아닙니다. auto를 제외하고 3가지 결과를 보면 chunk가 증가할수록 느려지는 현상(chunk 101 제외)이 발생합니다. 이유는 간단합니다. 태스크의 개수가 101개이니 이론적으로 chunk가 기본값이면, 26, 25, 25, 25로 분배됩니다. 이경우 가장 많은 태스크의 스레드와 가장 적은 태스크의 스레드 차이는 1이죠. 2인 경우에는 26, 26, 25, 24입니다. 차이는 2로 늘지만 그래도 가장 많은 태스크는 동일함으로 구동 시간은 변화가 매우 적습니다. 그런데 4가 되면, 28, 25, 24, 24 가 됩니다. 차이도 4가 되지만 가장 많은 태스크를 받은 스레드는 28개의 태스크를 수행해서 2개 더 수행하게 됩니다. 그로 인해 -1과 2에서 근소하게 증가한 구동 시간이 4에서 크게 증가되는 거죠.
위 결과는 태스크의 작업이 모두 동일할 때의 결과입니다. 이론으로는 static, -1이 최고의 성능을 보여야 합니다. 하지만, 현대 컴퓨팅 시스템은 하나의 소프트웨어에 하드웨어를 독점시키지 않음으로 큰 차이 없는 결과가 나옵니다. (더 많은 태스크로 구동해도 동일함을 확인했습니다.)
그럼 이번에는 태스크의 작업량이 차이가 나는 경우를 보겠습니다. 이번에 이용할 알고리듬은 피보나치수열입니다. 피보나치수열은 아래 수식과 같은 수열입니다.
$$f_0 = 0$$
$$f_1 = 1$$
$$f_n = f_{n-1} + f_{n-2} \quad (n \in \left\{ 2,3,4,\cdots \right\} )$$
이 알고리듬은 메모리제이션을 이용하는 게 좋은 방법이지만, 이 포스팅에서는 스케줄러의 성능을 보는 것이 목적이니, 제기 호출을 이용하는 단순한 알고리듬을 사용합니다. 제작된 예제 코드는 아래와 같습니다.
#include <iostream>
#include <vector>
#include <chrono>
#include <omp.h>
using namespace std;
// 피보나치 수열 계산
int fibonachi(int n){
if(2 > n){
return n;
}
return fibonachi(n-1) + fibonachi(n-2);
}
int main(int argc, char ** argv){
int n = atoi(argv[1]);
vector<int> arr(n,0);
// 구동 시간 행렬
// 1행 ~ 4행 스케줄러 타입
// 0열 : min 1열 : avg 2열 : max
vector<vector<double>> exTime(5, vector<double>(3,0.));
chrono::time_point<chrono::high_resolution_clock> sTime;
chrono::time_point<chrono::high_resolution_clock> eTime;
double cTime;
for(int i = 0 ; 5 > i ; i++){
exTime[i][0] = 100000.;
}
// 스케줄러 타입.
for(int scheduleTime = 1 ; 5 > scheduleTime ; scheduleTime++){
omp_set_schedule(static_cast<omp_sched_t>(scheduleTime), -1);
// 구동 횟수 5회
for(int t = 0 ; 5 > t ; t++){
sTime = chrono::high_resolution_clock::now();
// 병렬화 구역
#pragma omp parallel for schedule(runtime)
for(int i = 0 ; n > i ; i++){
arr[i] = fibonachi(i);
}
eTime = chrono::high_resolution_clock::now();
cTime = static_cast<double>((chrono::duration_cast<chrono::milliseconds>(eTime-sTime)).count())/1000;
// 구동횟수 저장
exTime[scheduleTime][0] = min(exTime[scheduleTime][0], cTime);
exTime[scheduleTime][1] += cTime;
exTime[scheduleTime][2] = max(exTime[scheduleTime][2], cTime);
}
exTime[scheduleTime][1] /= 5;
}
// 피보나치 수열 출력
for(int i = 0 ; n > i ; i++){
cout << i << "\t : " << arr[i] << endl;
}
// 구동 시간 출력
cout << "excute time" << endl;
for(int i = 1 ; 5 > i ; i++){
for(int j = 0 ; 3 > j ; j++){
cout << exTime[i][j] << "\t";
}
cout << endl;
}
return 0;
}
프로그램 구조상 n이 클수록 더 많은 작업이 필요합니다. 따라서 static 보다 dynamic과 guided가 더 효과적인 스케줄러가 됩니다. 결과는 아래 스냅숏입니다. 이경우 인풋 아귀 먼트로 50을 넣었습니다.
먼저 지적해야 할 부분이 있죠. F(47)이 음수가 됩니다. 32비트 변수를 이용할 때 정상적인 결과는 F(46)까지 입니다. 그 이상은 오버 플로우가 발생되어 잘못된 값이 나옵니다. 이 범위를 늘리고 싶으시면 64비트 변수를 이용하세요.
구동 시간을 보면 static에 비해서 dynamic과 guided가 훨씬 빠르게 끝나는 것을 보실 수 있습니다. 병렬화를 하는 코드에 따라 적합한 스케줄러는 다르지만, 개인적으로 추천하는 건 guided입니다. 물론 static에 비해서 잡 스케줄링을 위한 리소스가 추가로 필요하다고 해도, 상기 예제들과 같이 그 효과는 아주 작습니다.
그럼 여기까지 openMP의 스케줄러에 대한 긴 글이었네요. 공유 메모리 환경에서는 openMP를 이용해서 쉽게 병렬화가 가능하고 상기와 같이 효과적인 스케줄러를 사용할 수 있습니다.
긴 글 봐주셔서 감사합니다.
'Computer & Parallel Processing' 카테고리의 다른 글
| OpenMP 병렬 처리 : 공유변수 문제 (레이스 컨디션) 해결 (0) | 2021.03.12 |
|---|---|
| OpenMP 병렬 처리 : 공유변수 문제 (레이스 컨디션) (0) | 2020.10.19 |
| OpenMP를 이용한 병렬처리 (parallel for) (1) | 2020.10.13 |
| 컴퓨터 사용의 목적 (0) | 2020.10.08 |
