멀티코어컴퓨팅 - 10. OpenMP

OpenMP

multi-processing을 위한 framework이다. c/c++을 지원한다.

pthread에서 사용했던 thread 라이브러리보다는 더 사용이 쉬운 high level api이다.

openMP는 thread를 생성해서 작업을 할당한다. 작업들은 반드시 독립적인 작업이어야 한다.

병렬 처리 할 부분을 compiler directives로 나타낸다.

master thread가 소스를 실행하다 parallel region을 마주치면 thread들이 동시에 그 구역의 작업을 처리한다.

region 끝에서 쓰레드들이 대기하게 되고 모든 쓰레드가 도착하면 master thread는 다음 코드를 실행한다.

 

#pragma = open MP directives라고 한다.

컴파일러에게 아래 블럭이 parallel block이라고 알려준다.(쓰레드 만들고 각각 실행해라!)

preprocessor directive : 컴파일러가 제일 먼저 알아야 할 것을 알려줌

 

초기 설정된 코어수에 따라 greeting! 문구가 화면에 출력된다.

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

void main()
{	
	omp_set_num_threads(7);
#pragma omp parallel
	{
		printf("Hello World! Thread#: %d , Total Thread#:%d, numprocs:%d\n", omp_get_thread_num(),omp_get_num_threads(), omp_get_num_procs());
	}
}

함수를 통해 실행 thread 수를 정할 수도 있고

directive를 통해 활성화할 쓰레드 수를 명시할 수 있다.

실행되고 있는 쓰레드 index, 개수 등을 제공하는 함수도 있다.

 

Parallel Loops

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

#define NUM_THREADS 4
#define NUM_END 8

int main ()
{ 
	int i;
	omp_set_num_threads(NUM_THREADS);
	printf("program starts!\n");


//#pragma omp parallel
//	{
//		#pragma omp for

#pragma omp parallel for
		for (i = 0; i < NUM_END; i++) printf("i=%d (%d/%d)\n",i,omp_get_thread_num(),omp_get_num_threads());
//	}

	printf("program ends!\n");

	return 1;
}

#pragma omp parallel for 는 #pragma omp parallel { #pragma omp for }의 축약형이다.

for loop 안 8번의 반복 작업을 4개의 쓰레드가 사이좋게 나누어 수행한다.

 

Shared and Private Variables

parallel block 밖에 선언된 변수는 여러 쓰레드에 의해 공유된다.

하지만 Loop안에서 사용하는 Index는 private하다.

parallel block 안에서 선언된 변수는 private하다.

x, y, n은 밖에서 선언되었기 때문에 shared 변수이고 i는 private 변수이다.

이런식으로 확실하게 명시할 수도 있다.

행렬 곱셈을 수행하는 코드이다. 3개 중첩 루프로 쌓인 작업을 여러 쓰레드가 나누어 처리한다.

 

Critical Sections and Reduction Variables

이 코드를 병렬처리해보자.

이렇게 코드를 짜면 sum에 대해 race condition이 발생한다. 동시에 서로 다른 쓰레드가 sum의 값을 꺼내고 수정하여 결과가 실행때마다 다르게 나올 수 있다.

따라서 저 변수를 thread safe하게 해주어야 한다.

한가지 방법은 sum을 update하는 line을 critical section으로 만들어서 한번에 한 쓰레드만 들어올 수 있도록 한다.

또 다른 방법으로는 reduction 변수를 사용하는 것이다.

각 쓰레드마다 sum을 구하고 맨 마지막에 최종 sum을 구한다.

*, &&, || 등의 연산자도 사용가능하다.

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

long num_steps = 10000000; 
double step;

void main ()
{ 
	long i; double x, pi, sum = 0.0;
	step = 1.0/(double) num_steps;

#pragma omp parallel for reduction(+:sum) private(x)
// #pragma omp parallel for reduction(+:sum) 
	for (i=0;i< num_steps; i++){
		x = (i+0.5)*step;
		sum = sum + 4.0/(1.0+x*x);
	}
	pi = step * sum;
	printf("pi=%.8lf\n",pi);
}

구분구적법으로 pi를 구하는 코드이다. x를 shared variable로 사용하면 결과가 이상하게 나온다. private 변수로 만들어줘야 3.141592가 제대로 나온다.

 

schedule

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

#define NUM_THREADS 4
#define END_NUM 20

int main ()
{ 
	int i;
	double start_time, end_time;
	omp_set_num_threads(NUM_THREADS);
	start_time = omp_get_wtime( );

	#pragma omp parallel for schedule(static)
    //#pragma omp parallel for schedule(static, 5)
	//#pragma omp parallel for schedule(dynamic, 2)
	//#pragma omp parallel for schedule(guided, 2)
	for (i = 1; i <= END_NUM; i++) {
		printf("%3d -- (%d/%d)\n",i, omp_get_thread_num(),omp_get_num_threads());
	}

	end_time = omp_get_wtime( );
	printf("time elapsed: %lfs\n",end_time-start_time);

	return 0;
}

스케쥴링도 할 수 있다. 이런 스케쥴링의 목적은 효율적인 Load balancing을 위해서이다.

 

#pragma omp parallel for schedule(static, n)

static scheduling이다 iteration 횟수를 n, chunk 크기로 나누어서 4개의 쓰레드에게 돌아가면서 할당해준다.

n을 생략하면 알아서 공평하게 작업량을 나눈다. #pragma omp parallel for schedule(static)

 

#pragma omp parallel for schedule(dynamic, n)

n, chunk 수만큼 interation을 나누어서 cyclic하게 쓰레드들에게 할당해준다. 대신 avaliable한 쓰레드에게 작업을 우선 할당한다.

#pragma omp parallel for schedule(guided, 2)

dynamic과 비슷하다 차이로는 chunk를 크게 잡고 점점 줄여나간다.

 

SECTIONS

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

int main()
{
	omp_set_num_threads(4);
	printf("before omp sections\n");
#pragma omp parallel sections
//#pragma omp parallel 
//	#pragma omp sections
	{
		#pragma omp section
		{
			printf("section 1: %d/%d\n",omp_get_thread_num(),omp_get_num_threads());
		}

		#pragma omp section
		{
			printf("section 2: %d/%d\n",omp_get_thread_num(),omp_get_num_threads());
		}
	}
	printf("after omp sections\n");
	return 0;
}

block 안에 section block을 또 선언하면 쓰레드들에게 block을 분배해준다.

위의 예시의 경우 총 4개의 쓰레드가 있지만 실제로는 두 쓰레드가 두 block을 실행하고 끝났다.

parallel region 안에서 쓰레드가 서로 다른 구역을 실행하도록 하고 싶을 때 유용하다.

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

#define SWAP(a,b) {int temp = a; a = b; b = temp;}

#define SIZE 1048576

void setUp(int a[], int size);
void tearDown(double start, double end, int a[], int size);
void merge(int a[], int size, int temp[]);
void mergesort_serial(int a[], int size, int temp[]);
void mergesort_parallel_omp
(int a[], int size, int temp[], int threads);

int main() {
	int a[SIZE];
	int temp[SIZE];
	double startTime, endTime;
	int num_threads;

	#pragma omp parallel
	{
		#pragma omp master
		{
			num_threads = omp_get_num_threads();
		}
	}

	setUp(a, SIZE);

	startTime = omp_get_wtime();
	mergesort_parallel_omp(a, SIZE, temp, num_threads);
	endTime = omp_get_wtime();

	tearDown(startTime, endTime, a, SIZE);
}

void mergesort_serial(int a[], int size, int temp[]) {
	int i;

	if (size == 2) { 
		if (a[0] <= a[1])
			return;
		else {
			SWAP(a[0], a[1]);
			return;
		}
	}

	mergesort_serial(a, size/2, temp);
	mergesort_serial(a + size/2, size - size/2, temp);
	merge(a, size, temp);
}

void mergesort_parallel_omp(int a[], int size, int temp[], int threads) {
    if ( threads == 1) {
        mergesort_serial(a, size, temp);
    }
    else if (threads > 1) {
        #pragma omp parallel sections
        {
            #pragma omp section
            mergesort_parallel_omp(a, size/2, temp, threads/2);
            #pragma omp section
            mergesort_parallel_omp(a + size/2, size-size/2,
                temp + size/2, threads-threads/2);
        }

        merge(a, size, temp);
        } // threads > 1
}

mergesort를 section으로 구현하였다. divide한 작업을 각 쓰레드가 수행하고 마지막에 merge는 master thread가 수행한다.

이 경우 쓰레드 수를 아무리 늘려도 결국 실행되는 쓰레드 수는 정해져있다. 

mege() 부분이 sequential한 작업이기 때문에 쓰레드 수를 마냥 늘린다고 성능이 증가하지는 않는다.