병렬계산 2. OpenMP1

OpenMP는 Open Multi-Processing이라는 API로, 공유 메모리 환경에서 multi-processing을 할 수 있게 해주는 것이다. 주요 기능은 multi-threading이고, 포트란/C/C++에서 지원된다고 한다.

스레드는 스케줄러에 의해서 통제되는 여러 명령들의 가장 작은 단위이다. 즉, 스케줄러에 의해서 컨트롤되는 task를 의미한다. OpenMP에서는 여러 스레드가 하나의 프로세스에 존재할 수 있고, 스레드는 프로세스의 자원을 공유하고, 스레드는 동시에 실행될 수 있고, 스레드는 자기 자신의 private variables을 가질 수 있다. 몇몇 CPU는 하이퍼스레딩을 지원한다. 병렬계산을 할 때, master 스레드가 여러 개의 slave 스레드를 생성하는 과정을 fork라고 하고 slave 스레드가 다시 master로 합쳐지는 과정을 join이라고 한다.

OpenMP의 구성 요소는 컴파일러 디렉티브와 런타임 라이브러리 루틴, 그리고 환경변수이다. 디렉티브는 컴파일러가 OpenMP 모드일 때만 의미가 있고, 그렇지 않으면 무시되는 명령어를 말하고 C++에서는 pragma form으로 사용된다. 예를 들어서 다음과 같이 사용하면 된다.

#pragma omp parallel for
for (int i = 0; i < N; i++){
        a[i] = a[i] * x[i];
}

OpenMP에서 자주 사용되는 키워드는 parallel, do/for, private, shared, reduction 등등이 있다. 그리고 라이브러리 루틴은 코드에서 사용되는 함수를 의미한다. 자주 사용되는 것들은 다음과 같음.

omp_set_num_threads
omp_get_num_threads
omp_get_thread_num
omp_get_num_procs
omp_get_max_threads

환경변수는 코드가 아닌 OS에서 사용되는 것들. 예를 들면 bash에서 다음과 같음.

export OMP_NUM_THREADS=8

자주 사용되는 환경변수는 다음과 같음.

OMP_NUM_THREADS
OMP_SCHEDULE

OpenMP가 사용된 코드를 컴파일할 때는 컴파일 명령어에다가 OpenMP 관련 flag를 추가하면 됨. 컴파일러마다 플래그가 다른데 나는 gcc 계열 C++ 컴파일러인 g++를 쓰니까 다음과 같이 하면 됨.

g++ -fopenmp …

간단한 예시 코드

#include <iostream>
#include <omp.h>

int main(){
           int id, N;
           float fraction;
           N = 4;

           std::cout << N << " threads set by me\n";

           omp_set_num_threads(N);

           std::cout << omp_get_num_procs() << " procs\n";
           std::cout << omp_get_max_threads() << " max. threads\n";
           std::cout << omp_get_num_threads() << " threads now\n";

           std::cout << "Fork!\n";

           #pragma omp parallel private(id, fraction) shared(N)
           {
           id = omp_get_thread_num();
           fraction = float(id)/float(N);
           
                     #pragma omp critical(printing)
                     {
                     std::cout << "Hello, I'm thread " << id << '\n';
                     std::cout << id << "/" << N << "= " << fraction << '\n';
                     }
           }
           std::cout << "Join!\n";
           return 0;
}

 

#pragma omp parallel [clauses] {}안에 있는 내용이 병렬로 실행되는 것인데, 이 블록이 시작할 때 fork가 발생하고 끝날 때 join이 발생한다. 그리고 마지막에서 동기화를 하기 때문에, 내가 배리어를 사용하지 않아도 자동적으로 implicit barrier가 사용된다. 그리고 위 코드에서 private/shared을 볼 수 있는데, private 변수는 모든 스레드가 같은 이름을 갖는 개별 변수를 갖는 것이다. 변수의 이름만 같고 실제로 저장되는 메모리의 위치는 다르다. 반면 shared는 모든 스레드가 같은 메모리에 위치한 같은 변수를 갖는 것이다. shared 디렉티브는 보통 쓰지 않아도 자동으로 된다. 그리고 shared 변수가 많으면 cache coherence, synchronization 등의 작업이 발생하기 때문에 속도는 느려진다. shared 변수에서 race condition이라는 것이 발생할 수 있다.

race condition은 여러 스레드가 동시에 같은 shared 변수를 읽고 쓸 때 실행 순서에 따라서 결과가 달라지는 현상을 말한다. 예시는 다음과 같다.

#pragma omp parallel private(i) shared(a,b)
{
           i = omp_get_thread_num()
           b = b + a[i]*a[i]
}

여기서 스레드마다 b에 다른 값이 저장되기 때문에 문제가 되는 건데, b=0이고 a=[3,4]인 예시를 보자. 이 경우에 원하는 답은 9+16=25이다. 0번 스레드에서는 b=0의 값을 불러오고 a[0]*a[0]을 계산해서 레지스터에 0+9라는 값을 저장해놨다가 b의 메모리에 9를 쓰려고 한다. 그런데 동시에 1번 스레드에서 초기에 b=9를 불러와서 올바르게 값을 구할 수도 있지만, b=0을 불러온다면 0+16을 레지스터에 저장해놨다가 b의 메모리에 16을 쓸 수도 있다. 그러면 답이 9 또는 16이 될 수도 있는 것이다. 이러한 race condition은 변수를 추가하거나 synchronization을 위한 디렉티브를 쓰거나, reduction clause를 통해 해결할 수 있다.

Reduction clause는 각 스레드가 private에서 독립적으로 계산한 뒤, 병렬 구간이 끝날 때 하나의 연산으로 안전하게 합산하는 기능을 말한다. reduction clause는 연산자와 변수를 함께 설정하면 된다. 다음과 같다.

#pragma omp parallel reduction(+:b) private(i) shared(a)
{
           i = omp_get_thread_num()
           b = b + a[i]*a[i]
}

연산이 +이면 b의 값은 각 스레드에서 자동으로 0(합의 항등원)으로 초기화되고 연산이 *이면 1(곱의 항등원)으로 초기화된다.

합을 안전하게 하는 또다른 방법은 critical directive를 쓰는 것이다. 위의 hello 예제에서도 critical을 썼는데, critical은 한 번에 하나의 스레드만 특정 코드 블록에 진입할 수 있도록 하는 것이다. 위의 hello 예제에서 critical이 없으면 Hello I’m thread Hello I’m thread Hello I’m thread Hello I’m thread 0/4=1 1/4=0.25와 같은 형태로 출력될 수 있다. critical을 쓰면 코드 블럭 안에 한 번에 하나의 스레드만 들어갈 수 있게 돼서 사실상 serial로 실행하는 것이 되고 전체 수행 시간이 늘어난다. 따라서 꼭 필요한 경우에만 써야 한다. critical 블럭의 이름은 아무거나 써도 되는데, critical 블록을 여러 개 쓸 거면 각각 이름을 써줘야 한다. 이름을 구분하지 않으면 critical 블록을 구분하지 않게 돼서, 각 critical 블록에 들어가야 하는 스레드가 들어가야 하는 블록에 못들어간다. critical을 통해 합을 안전하게 구현하면 다음과 같다.

#pragma omp parallel private(i) shared(a, b) num_threads(2)
{
    i = omp_get_thread_num();
    #pragma omp critical
    {
        b = b + a[i] * a[i];
    }
}

atomic 디렉티브도 critical이랑 같은 역할을 하는데, atomic operation에만 쓸 수 있다. atomic은 블록 구조가 아니다. 제약이 많긴 한데 빨라서 atomic을 쓸 수 있으면 atomic을 쓰는 게 좋다. atomic으로 합을 구하면 다음과 같다.

#pragma omp parallel private(i) shared(a, b) num_threads(2)
{
    i = omp_get_thread_num();
    #pragma omp atomic
    b += a[i] * a[i];
}

reduction, critical, atomic 세 가지를 쉽게 정리하면, reduction은 각 스레드에서 계산한 값을 각 스레드에 있는 임시 private인 b에 저장해놨다가 마지막에 합치는 거고, atomic에서는 b 자체는 shared인데 a[i]*a[i]를 계산하는 건 병렬로 동시에 하긴 하지만 b에 접근하는 순간만 한 번에 한 스레드가 할 수 있도록 하는 거고 critical은 a[i]*a[i]부터 b에 합치는 것까지 모두 다 serial로 하는 거다.

이 외에 다른 synchronization 디렉티브로는 barrier와 master가 있다. barrier는 모든 스레드가 해당 지점에 도달할 때까지 기다리는 동기화 디렉티브이다. 병렬 블록 안에 여러 단계가 있을 때, 단계 간 동기화를 위해서 사용한다. master는 master 스레드인 0번 스레드만 실행하고, 다른 스레드는 대기 없이 통과하도록 하는 디렉티브이다. 초기화나 출력과 같이 한 번만 할 작업에 대해서 사용한다. master와 barrier는 보통 같이 사용한다. master만 쓰면 다른 스레드가 준비되기 전에 다음 단계로 넘어갈 수 있기 때문이다. barrier과 master를 사용해서 병렬 블록 안에서 합을 확인하기 위해 시도한 최종 코드는 다음과 같다. 먼저 reduction의 경우에는,

#include <iostream>
#include <omp.h>
#include <vector>

int main(){
	std::vector<int> a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	int b = 0;
	int i;
#pragma omp parallel private(i) shared(a) reduction(+:b)
	{
		i = omp_get_thread_num();
		b = b + a[i] * a[i];
#pragma omp barrier
#pragma omp master
		{
			std::cout << "Sum is " << b << '\n';
		}

	}
	std::cout << "Sum is " << b << '\n';
	return 0;
}

이걸 컴파일해서 실행하면

Sum is 1

Sum is 2870

이 나온다. reduction은 병렬 블록이 끝나면서 join을 통해 값이 합산되기 때문에 barrier와 master로도 병렬 블록 안에서는 최종 값 확인이 불가능하다. 다만 atomic은 join하면서 값이 합쳐지는 게 아니라 각 스레드가 b에 접근하는 즉시 값이 합쳐지기 때문에 다음과 같은 코드로 병렬 블록 안에서 합을 볼 수 있다.

#include <iostream>
#include <omp.h>
#include <vector>

int main(){
	std::vector<int> a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	int b = 0;
	int i;
#pragma omp parallel private(i) shared(a, b)
	{
		i = omp_get_thread_num();
#pragma omp atomic
		b = b+ a[i] * a[i];
#pragma omp barrier
#pragma omp master
		{
			std::cout << "Sum is " << b <<'\n';
		}

	}
	std::cout << "Sum is " << b << '\n';
	return 0;
}