현재 호주 퍼스의 University of Western Australia에서 교환학생 생활을 하고 있다. 이곳에서 High Performance Computing이라는 수업을 듣고 있는데, 이 수업에서 다루는 openMP에 대해 정리해본다.

c/c++에서 #pragma란?

c/c++에서 #define에 의해 전처리기에 의해 처리되는 메크로와 달리 #pragma 지시자는 컴파일 과정에서 최적화 전인 IR 단계에서 기본적인 문법에 더불어 추가적인 문법을 기계어로 변환할 수 있도록 돕는다.

이를 통해 openMP의 병렬화를 손쉽게 구현할 수 있다.

omp parallel

#pragma omp parallel
{
  // 병렬 코드
} 

parallel 지시어는 바로 아래 스코프의 코드들이 모든 스레드에서 병렬로 실행하는 지시어이다. 모든 스레드는 스코프의 종료 후 스코프의 마지막 부분에서 동기화된다.

race condition

int sum = 0;
#pragma omp parallel
{
  sum++; // race condition
}

어떤 병렬처리에서든 공통적인 주의사항으로 race condition이 발생할 수 있다. 예를 들어 위 코드는 sum 변수의 상태를 모든 스레드에서 공유하기 때문에, 실제로 존재하는 스레드의 수보다 작은 값이 sum에 최종적으로 할당될 가능성이 있다.

전역 & 지역 스코프 변수

int global = 0;  // shared
void func() {
  int local = 0;  // shared
  static int stat = 0;  // shared
  #pragma omp parallel
  {
    int priv = 0;  // private
    global++;  
    local++;   
    stat++;    
    priv++;
  }
}

전역 & 지역 변수의 개념도 존재하는데, omp parallel 내부에서 선언된 변수는 다른 스레드와 독립적인 변수가 되고, 그 이외의 변수들은 모든 스레드들에서 공유된다. 따라서 스코프 내에서 생성된 변수의 경우에는 race condition이 발생하지 않는다.

스코프 내에서 스레드 id 활용

#pragma omp parallel
{
  int id = omp_get_thread_num();
  int total = omp_get_num_threads();
  printf("스레드 %d/%d 실행 중\n", id, total);
  
  if (id == 0) {
    // 마스터 스레드만 실행
  }
}

omp_get_thread_num()으로 현재 스레드의 id를, omp_get_num_threads()로 전체 스레드의 개수를 알 수 있다. 이를 활용해 특정 스레드마다 다른 작업을 처리하도록 코드를 작성할 수 있다.

False Sharing

하지만 단순히 parallel를 사용할 경우 False Sharing이 발생할 수 있다.

False sharing이란 cpu의 캐시가 특정 단위(ex, 64B)의 블록을 기준으로 동일한 캐시라인에 캐싱하기 때문에 배열과 같이 물리적 주소가 연속적인 자료구조에 빈번히 값이 변경될 경우 캐시 miss가 자주 발생하는 문제이다.

이런 오버헤드로 인해 병렬처리로 인한 이점보다 낭비되는 자원이 많아질 수 있다.

아래 배열의 합을 구하는 코드를 예시로 보자.

double array[SIZE]

for (int i = 0; i < SIZE; i++) {
	array[i] = rand() / (float)(RAND_MAX + 1.0);
}

double sums[2] = {0, 0};
double sum;

// 스레드를 2개만 사용한다고 가정
#pragma omp parallel 
{
	if(omp_get_thread_num() == 0) {
    	for(int i = 0; i < SIZE / 2; ++i) {
        	sums[0] += arr[i];
		}
    } else {
    	for(int i = SIZE / 2; i < SIZE; ++i) {
        	sums[1] += arr[i];
        }
    }
}

sum = sums[0] + sums[1];

위의 경우에 0번 스레드와 1번 스레드는 각각 sums[0], sums[1]에 접근하고 있지만 동일한 캐시라인에 값이 캐싱되기 때문에 false sharing이 발생한다.

false sharing을 방지하기 위해서는 배열에 블록 사이즈와 동일한 크기의 버퍼를 사용하거나 이후 등장할 for reduction을 사용할 수 있다.

omp parallel for

#pragma omp parallel for
for (int i = 0; i < n; i++) {
  // 루프 반복을 스레드 간에 분배
}

for 반복문을 사용할 때, 가용 가능한 스레드들에게 작업을 자동으로 분배해준다.

for reduction

int sum = 0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < n; i++) {
  sum += array[i];
}

각 스레드가 지역 변수를 통해 계산한 다음, 최종적으로 결합해 race condition, false sharing과 같은 문제를 해결할 수 있게 해준다.

위의 예시에서는 i == 0에서부터 i == n-1까지의 값을 각각의 스레드가 균등하게 분배받아 sum의 값을 구할 수 있게 된다.

for schedule

int a[100][100] = {0};

#pragma omp parallel for schedule(dynamic)
for (int i = 0; i < 100; i++) {
  for (int j = i; j < 100; j++) {
    a[i][j] = i * j;
  }
}

각각의 스레드가 반복문 내부에서 얼마나 작업을 실행할지 정의해준다. 앞서 간단한 덧셈 예시의 경우에는 모든 회차의 연산 비용이 동일하지만, 위의 예시는 매 회차마다의 연산 비용이 다르기 때문에 균등한 작업량 분배를 위해 for schedule이 필요하다.

단순히 최상단의 i를 기준으로 작업을 분배할 경우, i가 작은 경우의 작업을 할당받은 스레드의 작업량이 다른 스레드보다 많이지기 때문에 최적의 효율을 달성하지 못한다.

스케줄링 방식은 크게 static, dynamic, guided으로 나눌 수 있다.

• static: 컴파일 타임에 작업을 스레드마다 균등하게 분할
• dynamic: 런타임에 작업을 동적으로 분할
• guided: 청크 크기를 감소시키며 동적으로 분할
  

이러한 특성 때문에 일반적으로 작업의 크기가 동일할 경우 static을, 작업의 크기가 변할 경우 dynamic을 선택해야 효율적으로 작업을 처리할 수 있다.

for collapse

#pragma omp parallel for collapse(2)
for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    // do something
  }
}

중첩 반복문을 하나로 합쳐서 스레드에게 분배하는 방식이다.

for ordered

#pragma omp parallel for ordered
for (int i = 0; i < n; i++) {
  // do something

  #pragma omp ordered
  {
    // 순차적으로 실행할 코드
  }
}

반복문 내의 병렬 실행 코드를 기존 루프의 순서대로 실행시킬 수 있다. 성능 저하가 발생하기 때문에 순서가 꼭 지켜져야 하는 경우에만 사용해야 한다. #pragma omp ordered가 붙은 스코프에서만 순서가 지켜지며 한 반복문 내에서 한 번만 사용할 수 있다.