SHPC 13 - OpenMP

OpenMP

• C, C++, Fortran에서 사용되는 shared-memory parallelism API
  • Shared memory를 사용하는 쓰레드들의 parallelism과 synchronization을 원활하게 함
• Fortran의 cray directive를 본따 만들어짐
  • Directive : 컴파일러에게 지시하는 지시문을 코드 중간에 넣는 형식
  • OpenMP도 directive를 통해 컴파일러 및 런타임이 자동으로 쓰레드를 생성해준다
• 프로그래밍이 간단하지만 성능이 낮아서 practical하지 않다

Threading in OpenMP

• Thread
  • Stack과 thread-private memory를 가진 실행주체
  • OpenMP에서는 OpenMP runtime이 관리 → 신경쓸 필요가 없음
• Thread-safe routine
  • 여러 쓰레드에 의해 concurrent하게 실행해도 정확하게 동작하는 루틴
• 프로그래밍 과정에서 shared, private 변수를 명시적으로 표기해주지 않거나, critical section을 명시적으로 보호하지 않으면 data race가 생길 수 있음

OpenMP Execution Model

• Fork-join parallelism 모델 사용
  • Fork : 마스터 쓰레드가 쓰레드들을 spawn
  • Join : 쓰레드들이 parallel section에서 일을 완료하면 마스터 쓰레드만 남기고 종료
• 실제로 아래처럼 매번 새로 쓰레드를 만들지는 않는다
  • 미리 만들어두고 일을 주는 식, 최적화를 위해

Pragmas

• #pragma omp 이후 옵션들을 넣는 형식
  • 컴파일러가 openmp를 지원하면 보고 알아서 처리 (안하면 무시)
• 컴파일러에게 OpenMP를 사용할지 알리는 방법
  • 헤더파일을 포함하는 방법
    • #include <omp.h>
    • 컴파일러가 openmp를 지원하지 않으면 컴파일 에러가 발생
  • Conditional compilation
    • #ifdef _OPENMP ← OPENMP 가 정의되어있는지 확인
    • #endif
• gcc -fopenmp 옵션 사용하면 openmp로 컴파일 가능

Query Functions

• 쓰레드 관련 정보를 조회하는 함수들
• int omp_get_num_threads(void)
  • 현재 코드영역을 실행중인 쓰레드 팀에 속한 쓰레드의 갯수를 리턴
  • 쓰레드 팀: OpenMP에서 병렬 코드영역을 실행하는 쓰레드의 그룹
    • 마스터 쓰레드와 워커 쓰레드로 나뉨
• int omp_get_thread_num(void)
  • 쓰레드 번호를 리턴 (쓰레드 팀 내에서 부여받음)
  • 쓰레드 팀의 마스터는 0, 나머지는 … N-1까지 붙어있을 것

Parallel Region Construct

#pragma omp parallel [...]
{
	structured block
}

• 이 시점부터 쓰레드 팀을 생성
• SPMD를 달성하는 방법
• Default로 모든 variable은 shared variable이다
• 쓰레드 팀이 또 다른 parallel directive를 만나면, 새로운 팀을 또 만든다

Shared Variables vs Private Variables

• 모든 쓰레드는 자기자신의 execution context를 갖는다
  • Execution context : 접근 가능한 변수들…
• Shared variable : 모든 쓰레드의 접근 주소 동일
• Private variable : 자기만 접근 가능, 접근 주소 서로 다름

Hello world in OpenMP

• #pragma omp parallel num_threads(cnt_threads) : 쓰레드 갯수를 pragma로 시작과 동시에 정할 수 있다.

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

void hello(void);

void main(int argc, char* argv[]) {  
	int cnt_threads = strtol(arg[1], NULL, 10);

	#pragma omp parallel num_threads(cnt_threads) 
	// 쓰레드 개수 정하기
	hello();

	return 0; 
}

void hello(void) {  
	int my_id = omp_get_thread_num();  
	int num_threads = omp_get_num_threads();

	printf(“Hello world! %d %d\n”, my_id, num_threads); 
}

• #pragma omp parallel private(tid): 변수를 private으로 변경 가능하다

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

void main() {  
	int num_threads, tid;  
	num_threads = omp_get_num_threads();

	printf("Sequential section: # of threads = %d\n", num_threads);

	#pragma omp parallel private(tid) // 변수를 private 으로 설정
	{
		tid = omp_get_thread_num();  
		printf("Parallel section: Hello world from thread 
		%d\n", tid);
		if (tid == 0) {  
			num_threads = omp_get_num_threads(); 
			printf("Parallel section: # of threads = %d\n",
		}
	}
}

• omp_set_num_threads(n); : 쓰레드 갯수를 함수로 시작 전에 세팅 가능하다

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

void main() {  
	int num_threads, tid; 
	omp_set_num_threads(2);  
	num_threads = omp_get_num_threads();

	printf("Sequential section: # of threads = %d\n",num_threads);

	#pragma omp parallel private(tid)
	{  
		tid = omp_get_thread_num();  
		printf("Parallel section: Hello world from thread %d\n",
		tid);

		if (tid == 0) {  
			num_threads = omp_get_num_threads(); 
			printf("Parallel section: # of threads = %d\n",
			num_threads);
		} 
	}
}

if/private/shared clauses

• if(scalar_expression)
  • scalar_expression이 참일 때만 병렬처리
  • 거짓이면 시퀀셜 처리
• shared(list)
  • 팀의 모든 쓰레드에 의해 접근 가능
• private(list)
  • 초기화 값을 무시함
  • entry, exit 시점에 list의 값은 undefined임
• firstprivate(list)
  • 초기화 값을 카피해서 들어감
• lastprivate(list)
  • parallel region 이 끝나면 해당 값으로 변수를 업데이트함.
  • 쓰레드 순서에 따라 결과가 달라질 수 있음

Work sharing constructs

Loop construct

#pragma omp parallel
#pragma omp for [...]
for(i=0; i<N; i++) ...

• 쓰레드에게 iteration을 하나씩 가져가서 병렬처리하라고 지시
  • 이게 없으면 for문 전체를 N번 실행할 것
• Loop index는 private variable
• 아래 코드는 barrier가 없어도 되는 예시 (퍼포먼스 고려해 nowait 사용)
  • 만약 두번째 루프에서 b[i]를 읽는 경우 배리어가 필요
  • 두번째 루프가 첫번째 루프에 대해 데이터 의존성이 있기 때문

#include <math.h>  
void nowait_example(int n, int m, float *a, float *b, float *y, float *z)
{  
	int i;
	#pragma omp parallel 
	{
		#pragma omp for nowait 
		for (i=1; i<n; i++)
			b[i] = (a[i] + a[i-1]) / 2.0;
		
		#pragma omp for nowait 
		for (i=0; i<m; i++)
			y[i] = sqrt(z[i]);
	} 
}

pragma omp for ← loop를 병렬처리해라 nowait - 일반적으로 쓰레드가 for loop의 끝에서 barrier를 부르는데, nowait의 경우 퍼포먼스를 고려해 barrier를 넣지 않는 것. 아래 경우 배리어 없어도 상관없는데, 아래 루프에서 b[i]를 읽는 경우 배리어가 필요하니 쓰면 안됨

Thread Scheduling Clause

• 워크로드 밸런싱을 어떻게 할 것인지를 정의하는 clause
• iteration을 청크단위로 묶어서 나눠주는 게 기본
• Static schedule(static [, chunk_size])
  • 청크 사이즈를 고정해서 round robin으로 순서대로(in-order!) 분배
    • 순서대로 분배하는게 특히 다른 방법들과 다른 점임
    • 예를 들어 20개를 4개 쓰레드에 분배하는데 청크사이즈가 3인 경우
      • 0번: 0, 1, 2
      • 1번: 3, 4, 5
      • 2번: 6, 7, 8
      • 3번: 9, 10, 11
      • 0번: 12, 13, 14
      • 1번: 15, 16, 17
      • 2번: 18, 19
    • 청크 사이즈 디폴트는 1
    • 워크로드 사이즈를 판단 가능한 경우 직접 파라미터로 설정해 줄 수도 있음
      • +) $2^n$ 사이즈로 나눠주는 것이 하나의 cache 라인을 가지고 서로 기다리는걸 막기 때문에 좋음
  • (한번에 다 나눠줌)
• Dynamic schedule(dynamic [, chunk_size])
  • 하나의 쓰레드가 실행이 끝나면 그 쓰레드에게 다시 청크 사이즈를 나눠줌
    • iteration마다 계산의 양이 다른 경우 유리함
    • 그러나 분배에 오버헤드가 있음
  • (빨리 끝나는 쓰레드에게 추가로 나눠줌)
• Guided
  • Dynamic 방식의 오버헤드를 줄일 수 있음
    • 왜인가 하고 찾아봤는데, 청크를 분배하는 오버헤드는 생기긴 하지만 애초에 전체 청크 수, 즉 분배 횟수가 조금 더 적어진다고 함
  • 청크 사이즈를 줄여가면서 다이나믹하게 분배
    • 청크 사이즈 == 분배되지 않은 iteration의 수 / 전체 쓰레드 수
    • 예를 들어 20개 반복을 4개 쓰레드가 처리하는 경우,
      • 0번: 20 / 4 = 5개 할당, 15개 미할당
      • 1번: 15 / 4 = 4개 할당, 11개 미할당
      • 2번: 11 / 4 = 3개 할당, 8개 미할당
      • 3번: 8 / 4 = 2개 할당, 6개 미할당
      • 빨리 끝난 다음 쓰레드: 6 / 4 = 2개 할당, 4개 미할당 …
  • 청크 사이즈의 최소값을 설정할 수도 있음
    • 위 예제에서 3으로 설정한 경우, 3번에게 3개 청크가 할당될 것
    • 마지막 청크는 더 작아질 수 있음
• auto
  • 런타임 시스템 혹은 컴파일러에게 스케쥴링을 맡기는 것

Section Construct

• Non-iterative work sharing construct
• 각 블록은 쓰레드 팀의 하나에 의해서만 실행됨
• 쓰레드 개수가 섹션 수보다 적으면 차례대로 처리하고, 많으면 남는 섹션은 논다
• 단점 : Task parallelism이라 비효율적이어서 잘 사용하지 않음

#pragma omp sections [...] {
	[#pragma omp section
		...
	]
	[#pragma omp section
		...
	]
}

Single Construct

• 팀의 하나의 쓰레드만 실행하면 되는 코드 영역
• 다른 쓰레드는 놀고있다
• section이랑 다른 점은 section은 무조건 병렬화해서 처리하지만 single은 하나의 스레드가 여러 single을 실행할 수도 있다는 점 같음
  • section은 무조건 놀고있는 쓰레드가 태스크를 take해야 함
  • single은 하나의 쓰레드만 실행하라는 조건만 만족하면 됨. 놀고있는 쓰레드가 있어도 싱글을 take하지 않아도 됨. 한명한테 몰아줄 수 있음

Combined work sharing constructs

• for, section을 omp parallel에 붙여 쓸 수 있게 함
  • parallel for / parallel section
• 아래 예시에서 j는 shared로 설정되므로 명시적으로 private 처리를 해줘야 한다.

Reduction

• #pragma omp parallel for reduction (op:list) 과 같은 형태
• 실행시 list의 로컬 카피를 가져가 지정된 연산을 수행하고, 마지막에 마스터가 op연산으로 이 list의 로컬카피들을 글로벌 변수 list 하나로 합치게 됨
• 아래 예시에서는
  • 1. 쓰레드 내에서 sum의 로컬카피 생성
  • 2. A값의 합을 sum에 넣고 기다림
  • 3. 모든 쓰레드가 배리어에 도착하면 마스터가 모든 쓰레드의 sum을 op(+) 연산으로 합침

double sum = 0.0, A[MAX];
int i;

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

ave = sum/MAX;

Master Construct

• 마스터만 실행하는 construct
• #pragma omp master

Critical const

• #pragma omp critical (section_name)
• Structured block에 single thread만 들어갈 수 있도록 제한
  • 크리티컬 섹션의 이름을 지정하여 동일한 이름을 실행중인 스레드는 하나만 존재하도록 함
• 상호배제 달성하는 코드
• lock, unlock으로 감싸져 있다고 생각할 수 있음

Barrier Construct

• 모든 쓰레드가 도착할 때까지 대기
• #pragma omp barrier
• 컴파일러가 이후 barrier 함수호출로 교체해 준다

Atomic

• #pragma omp atomic [read | write | update | capture]
  • [] 안의 연산을 아토믹하게 실행
• #pragma omp atomic capture \n structured-block
  • block을 아토믹하게 실행
  • capture는 v = x++, v = x— 같이 값을 바꾸면서 캡쳐하는 것
• 중괄호가 불가능하다
• 아래 예시에서는 x의 업데이트를 원자적으로 수행 성능때매 마니 안쓴다. 근데 이거 consistency랑 관련 있나? SC처럼 동작한다는 건가? 요 코드 좀 더 분석 필요

OpenMP Memory Consistency

• Language 레벨에서 정의
• 하위 아키텍처로의 매핑은 컴파일러가 해줌
• Weak ordering 사용
• 각 쓰레드가 자기만의 view가 존재, sync 시점이 오면 글로벌 뷰에 업데이트
• sync 시점은?
  • flush operation

Flush operation

• #pragma omp flush [(list)]
• list가 비어있는 경우, 전체 변수가 flush됨
• flush를 하면 모든 쓰레드의 private view가 업데이트된다. 쓰기 아니더라도 list 없으면 전체 변수가 전부 flush됨 flush 하면 순서가 어떻게 반영될지? → 찾아봐라

참고자료 https://stackoverflow.com/questions/42970700/openmp-dynamic-vs-guided-scheduling