[OpenMP] for 루프 병렬화 (+ default, private, shared clause)

References

• An Introduction to Parallel Programming

Contents

• 데이터 의존성
• private clause
• default, share clause

---

2021.11.21 - [프로그래밍/병렬프로그래밍] - [OpenMP] 사다리꼴 공식 (trapezoidal rule)

[OpenMP] 사다리꼴 공식 (trapezoidal rule)

이전 포스팅에서 사다리꼴 공식을 사용하여 특정 구간의 임의의 함수 그래프와 x축 사이의 넓이를 구하는 알고리즘을 병렬화해보았습니다. 그 방법 중의 하나로 parallel for을 사용하여 알고리즘을 병렬화하였습니다. 그리고 for 루프를 병렬화하는 조건을 마지막에 언급했는데, 다음의 조건을 하나라도 만족하지 못하면 컴파일러는 해당 코드를 컴파일할 때 에러를 발생시킵니다.

예를 들어, 다음의 선형 탐색 함수를 컴파일한다고 가정해봅시다. 동작이 아닌 컴파일이 되는지 확인하는 용도라 그냥 단순히 아래 코드를 복사해서 컴파일하시면 됩니다.

#include <stdio.h>
#include <omp.h>

int thread_count;

int Linear_search(int key, int A[], int n)
{
#pragma omp parallel for num_threads(thread_count)
    for (int i = 0; i < n; i++) {
        if (A[i] == key)
            return i;
    }
    return -1;
}

int main(int argc, char* argv[])
{
    /* do something */

    return 0;
}

위의 코드를 다음의 명령어로 컴파일하면,

컴파일 에러가 발생합니다. 이는 바로 for문의 반복 횟수가 정해져 있지 않기 때문입니다.

---

데이터 의존성

루프에서 발생할 수 있는 더 큰 문제점은 반복문의 결과가 이전 또는 그 이전의 반복문 결과에 의존할 때 발생합니다. 예를 들어, 피보나치 수열을 계산하는 코드가 이에 해당됩니다.

fibo[0] = fibo[1] = 1;
for (int i = 2; i < n; i++)
	fibo[i] = fibo[i-1] + fibo[i-2];

피보나치 수열을 구하기 위한 for 루프에 parallel for 디렉티브를 사용하여 병렬화해보겠습니다. 위 코드를 병렬화한 부분이 바로 line 15-17입니다. 전체 코드는 아래 링크를 참조바랍니다.

https://github.com/junstar92/parallel_programming_study/blob/master/OpenMP/06_omp_fibo.c

GitHub - junstar92/parallel_programming_study

int main(int argc, char* argv[])
{
    int thread_count, n;
    long long* fibo;

    if (argc != 3)
        Usage(argv[0]);
    
    thread_count = strtol(argv[1], NULL, 10);
    n = strtol(argv[2], NULL, 10);

    fibo = (long long*)malloc(n * sizeof(long long));
    fibo[0] = fibo[1] = 1;

#pragma omp parallel for num_threads(thread_count)
    for (int i = 2; i < n; i++)
        fibo[i] = fibo[i-1] + fibo[i-2];
    
    printf("The first n Fibonacci numbers:\n");
    for (int i = 0; i < n; i++)
        printf("%d\t%lld\n", i, fibo[i]);
    
    free(fibo);

    return 0;
}

그리고 컴파일 후, 10번째 피보나치 수열을 2개의 스레드로 계산하게 되면,

위의 리스트를 얻을 수 있습니다.

하지만, (저의 경우에 2개 스레드로는 항상 정상적인 결과가 나왔으나) 2개의 스레드로 잘못된 결과가 나올 수도 있습니다. 3개 이상의 스레드로 돌려보면 확실하게 결과가 잘못나옵니다.

 

2개의 스레드를 사용했다고 가정하면, 런타임 시스템에서 fibo[2], fibo[3], fibo[4], fibo[5]에 대한 계산을 하나의 스레드에 할당하고, fibo[6], fibo[7], fibo[8], fibo[9]를 또 다른 스레드에 할당할 것입니다. 프로그램이 실행될 때, 다른 스레드가 시작하기 전에 fibo[2], fibo[3], fibo[4], fibo[5]의 연산이 끝나면 문제가 발생하지 않습니다. 하지만 fibo[6]의 연산 중에 첫 번째 스레드에서 fibo[4]와 fibo[5]의 연산이 끝났다고 확신할 수가 없습니다. (스레드에 할당되는 크기가 매우 작기 때문에 대부분 두 번째 스레드가 시작되기 전에 첫 번째 스레드가 끝날 것이긴 합니다.)

 

여기서 OpenMP에서 두 가지 특징이 발견됩니다.

• OpenMP 컴파일러는 parallel for 디렉티브를 사용하여 병렬화할 루프의 반복문에 있는 의존성을 검사하지 않습니다. 이 문제를 파악하는 것은 개발자에게 달려있습니다.
• 다른 반복의 결과에 의해 의존적으로 설계된 반복문은 일반적으로 OpenMP를 사용하여 정상적으로 병렬화할 수 없습니다.

이처럼 fibo[6]의 연산에서 fibo[5]의 연산에 대한 의존성을 데이터 의존성(data dependence)라고 합니다. fibo[5]의 값이 반복문에 의해 계산되고 그 결과는 다음에 실행되는 반복문에 사용되기 때문에 이러한 의존성은 루프에 의한 의존성(loop-carried dependeces)라고도 합니다.

 

다음의 예제 코드를 살펴봅시다.

for (int i = 0; i < n; i++) {
	x[i] = a + i*h;
    y[i] = exp(x[i]);
}

line2와 line3 사이에는 데이터 의존성이 존재합니다. 하지만 병렬화에는 문제가 없습니다. x[i]의 연산과 그 결과는 항상 같은 스레드에서 사용됩니다.

 

이처럼 parallel for 디렉티브를 사용하려고 할 때에는 루프에 의한 의존성에 대해 고려해야하고, 이를 찾기 위해서는 루프 내부에서 업데이트되는 변수들을 체크해봐야 합니다.

---

pi 값 계산

다음의 공식으로 pi의 근사값을 계산해보도록 하겠습니다.

위의 수식을 시리얼 코드로 구현하면 다음과 같습니다.

double factor = 1.0;
double sum = 0.0;
for (int k = 0; i < n; k++) {
	sum += factor/(2*k + 1);
    factor = -factor;
}
double pi_approx = 4.0 * sum;

 

OpenMP로 위의 코드를 어떻게 병렬화할 수 있을까요?

단순하게 parallel for을 사용하면 어떨까요?

double factor = 1.0;
double sum = 0.0;
#pragma omp parallel for num_threads(thread_count) \
	reduction(+: sum)
for (int k = 0; k < n; k++) {
	sum += factor/(2*k + 1);
    factor = -factor;
}
double pi_approx = 4.0*sum;

위 코드에서 k번 반복하는 동안 line 7에서 factor를 업데이트하고 k+1번째 반복에서 line 6에서 사용되므로 루프에 의한 의존성을 가지고 있습니다. 따라서 스레드가 2개 이상인 경우에는 line 6의 factor값이 올바르다고 보장될 수 없습니다.

이 경우에는 다음과 같이 사용되는 공식을 수정할 수 있습니다.

k번에서 반복되는 factor는 \((-1)^k\)이 되고, 이 값은 k가 짝수이면 +1, k가 홀수이면 -1이 됩니다.

코드를 다음과 같이 변경해보겠습니다.

double factor;
double sum = 0.0;
#pragma omp parallel for num_threads(thread_count) \
	reduction(+: sum)
for (int k = 0; i < n; k++) {
	factor = (k % 2 == 0) ? 1.0 : 1.0;
	sum += factor/(2*k + 1);
}
double pi_approx = 4.0 * sum;

이와 같이 수정함으로써 루프에 의한 의존성을 제거할 수 있습니다.

하지만, 위 코드는 아직 문제가 있습니다. 저의 경우에는 10개의 스레드를 사용하여 n = 1000으로 설정한 후에 실행하면, 항상 결과가 틀리게 나옵니다. (첫 번째가 위 코드 수행 결과값, 두 번째는 math library를 사용한 결과값)

하지만, 하나의 스레드로만 실행했을 땐

항상 동일한 결과를 얻습니다.

 

무엇이 잘못되었을까요?

parallel for 디렉티브에서 병렬화된 블록을 생각해보면 됩니다. 기본적으로 루프 전에 선언된 변수들은 스레드들 사이에서 공유(shared)됩니다. 따라서 factor 변수는 공유되고 스레드 0은 factor 변수에 1을 할당하지만 이 값으로 sum이 업데이트되기 전에 스레드 1에서 factor 변수에 -1을 할당할 수 있습니다. 그러므로 factor 계산에 있는 루프에 의한 의존성이 제거되었다고 하더라도 각 스레드가 자신만의 factor를 사용할 수 있도록 해야합니다. 즉, 위의 코드가 올바르게 실행되려면 factor는 private 범위를 가져야 합니다. 

이는 private clause를 추가하면 해결됩니다.

double factor, sum = 0.0;
#pragma omp prallel for num_threads(thread_count) \
	reduction(+: sum) private(factor)
for (int k = 0; k < n; k++) {
	factor = (k % 2 == 0) ? 1.0 : -1.0;
    sum += factor/(2*k + 1);
}
double pi_approx = 4.0*sum;

전체 코드는 아래 링크를 참조바랍니다 !

https://github.com/junstar92/parallel_programming_study/blob/master/OpenMP/07_omp_pi.c

GitHub - junstar92/parallel_programming_study

그 결과,

스레드가 몇 개가 되던, n이 같다면 pi 근사값은 모두 동일하게 계산됩니다.

 

private clause는 괄호 안에 리스트된 변수들이 각 스레드에서 각자의 카피를 갖도록 해줍니다. 위의 예제에서 각 스레드는 변수 factor에 대해서 각자의 카피본을 갖게 되고, 각 스레드에서 업데이트되는 factor는 다른 스레드에 있는 facto의 값에 영향을 미치지 않습니다.

 

---

추가로 private scope를 갖는 변수의 값은 parallel 블록이나 parallel for 블록을 시작할 때 알 수 없습니다. 이 값은 또한 parallel이나 parallel for 블록이 완료된 이후에도 특정할 수 없습니다. 다음의 예제 코드를 살펴보겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main(int argc, char* argv[])
{
    int x = 5;
    int thread_count = strtol(argv[1], NULL, 10);

#pragma omp prallel num_threads(thread_count) \
    private(x)
    {
        int my_rank = omp_get_thread_num();
        printf("Thread %d > before initialization, x = %d\n", my_rank, x);
        x = 2*my_rank + 2;
        printf("Thread %d > after initialization, x = %d\n", my_rank, x);
    }
    printf("After parallel block, x = %d\n", x);

    return 0;
}

위의 코드에서 첫 번째 printf 문장의 결과는 알 수 없습니다. 이는 명시적으로 x를 초기화하기 전에 private 변수 x를 출력하기 때문입니다. 마찬가지로 마지막 printf의 결과도 알 수 없습니다. 이는 parallel 블록이 완료된 후에 변수 x를 출력하기 때문입니다.

위 코드를 컴파일하면,

초기화되지 않은 x를 사용한다고 컴파일 경고가 발생하고,

4개의 스레드로 실행해보면 위의 결과를 확인할 수 있습니다. 처음에 x는 5로 초기화가 되어 있지만, private 변수로 사용되는 x는 5가 아닌 0으로 출력되고, parallel 블록안에서 변경된 x의 값은 parallel 블록이 끝난 후에 사라지고 main문에서 초기화된 값이 그대로 마지막에 출력되고 있는 것을 볼 수 있습니다.

 

이처럼 parallel 블록이나 parallel for 블록을 사용할 때에는 블록 안에서 사용되는 각 변수의 범위에 대해서 생각해볼 필요가 있습니다.

---

default, shared clause

OpenMP에는 각 변수의 범위를 임의로 설정할 수 있는 기능을 제공합니다. 바로 default(none) clause를 사용하면 되는데, 이 디렉티브를 사용하면 블록에서 사용하게 될 변수의 범위를 설정할 수 있도록 해줍니다. 다만, 범위를 설정할 변수들은 블록 외부에서 선언되어 있어야 합니다. (블록 안에서 선언된 변수는 항상 private 범위이기 때문입니다.)

 

예를 들어, default(none) clause를 사용하면 pi값을 계산하는 코드는 다음과 같이 수정됩니다.

double factor, sum = 0.0;
int k;
#pragma omp prallel for num_threads(thread_count) \
	default(none) reduction(+: sum) private(k, factor) shared(n)
for (k = 0; k < n; k++) {
	factor = (k % 2 == 0) ? 1.0 : -1.0;
    sum += factor/(2*k + 1);
}
double pi_approx = 4.0*sum;

위 코드에서는 for 루프 안에 4개의 변수를 사용합니다. default(none)을 사용하게 되면 각 변수의 범위를 직접 설정해주어야합니다. 사실 변수 k는 for문 내부에서 int로 선언하여 private 변수로 사용할 수 있기 때문에 굳이 위 코드처럼 블록 밖에 선언한 후에 private 변수로 설정할 필요는 없습니다. factor는 앞서 살펴보았듯이 블록 내에서 private 변수로 사용되어야 하기 때문에 private 변수로 설정하고, n은 블록 내에서 업데이트되지 않는 변수이므로 shared로 설정되었습니다.