[Parallel Computing] (11) OpenMP

OpenMP는 Sharedf-memory parallelism을 수행하기 위한 API로, C, C++ 그리고 Fortan 프로그램에서 수행가능하다. 병렬 프로그래머를 위한 컴파일러 지시자, 환경 변수 등을 제공한다. 컴파일러는 스레드 프로그램과 동기화를 생성하는데, 이를 자동으로 수행하지는 않는다.
OpenMP에서의 스레드는 실행 단위로 스레드마다 Stack, thread-private memory로 불리는 associated static memoy를 가진다. Thread-safe routine은 앞 글에서도 언급했었지만, 특정 함수를 여러 스레드가 동시에 수행해도 정확하게 수행되는 것을 말한다. OpenMP 실행 모델은 Fork-join parallelism 형태로 수행된다. Fort는 Master 스레드가 존재하고, 이 Master 스레드는 스레드들로 구성된 팀을 만든다. Join은 한 팀의 스레드들이 서로의 Task를 병렬적으로 수행하고, 해당 지점에서 동기화를 위해 멈추고, Master 스레드만 남는다. Parallel region은 모든 스레드가 동시에 실행되는 코드 영역을 말한다. Master를 제외한 나머지 Worker 스레드는 다음 fork가 나타날 때까지 기다린다.
Pragmas는 특별한 사전처리를 위한 Instruction이다. 기본적인 C Spec. 에 없는 동작을 허용하며, 컴파일러는 해당 Pragmas를 지원하지 않으면 해당 부분은 무시할 수 있다.
#pragma omp directive_name [ clause [ clause]...] new-line
형태로 사용된다.
현재 병렬로 수행 중인 영역에서 현재 팀에 포함된 스레드의 개수를 반환하는 함수(omp_get_num_threads)가 존재하며,  팀 내부에서 스레드 숫자를 반환하는 함수(omp_get_thread_num) 존재하다. 기본적으로 Master 스레드의 숫자는 0이다.
OpenMP 프로그램은 하나의 프로세스, Master 스레드로 시작하며, 병렬로 수행할 수 있는 영역을 만다면, 스레드 팀이 모집되고 수행된다. 각 스레드는 동일한 코드에서 수행되는 SPMD이며, 병렬로 수행되는 영역에서의 스레드 숫자는 각자 고유한 형태로 고정되어 있다. 기본적으로 모든 변수는 공유하는 형태이며, 병렬로 수행하는 영역의 끝은 암시적인 Barrier로 되어 있다. 병렬로 수행할 수 영역에서 또 다른 병렬 지시자를 만나면 새로운 스레드 팀을 구성한다.
  모든 스레드는 각자가 가진 execution context가 존재하며, 모든 변수가 포함된 addressing space를 접근할 수 있다. 공유 변수는 모든 스레드의 execution context 내에서 동일한 주소를 가지며, 모든 스레드가 접근 가능하다. Private 변수는 모든 스레드의 execution context 내에서 서로 다른 주소를 가진다.
Shared variable/Private variable은 아래와 같이 선언할 수 있다.
# pragam omp parallel for private/shared(j) // j라는 Private/Shared variable을 선언
작업 공유 구조(Work Sharing Constructs)는 Construct로 둘러싸인 코드의 실행을 팀 내의 스레드 간에 나눈다. 작업 공유가 이루어지려면 구조가 병렬 영역의 동적 범위 내에 포함되어야 합니다. 팀 내부에 한 개의 스레드만 있을 경우 병렬로 수행되지 않는다. Work sharing regison에는 베리어가 존재하지 않는다.
Loop Construct는 병렬 동작을 수행하는 하나 이상의 관련 Loop들을 구성할 수 있다.  Loop를 여러 스레드가 나눠서 병렬 동작을 수행한다. 병렬 동작을 수행하는 동안 Loop Index는 각 스레드마다 독립적으로 동작해야 하므로 private variable이다.  
#pragma omp parallel
{
  #pragma omp for nowait -> For Loop를 병렬로 수행하는 데, 스레드 별로 끝나는 대로 바로 다음 라인을 수행하도록 지시.
  for (i=1; i <n; i++)
        %%%%%%
  # pragma omp for nowait
  for(i=0; i <m; i++)
       %%%%%%%
}
스레드마다 Loop의 iteration을  분배하는 방법에는 static/dynamic/guided/auto 방식이 있다.
static은 interation을 round-robin 방식대로 스레드 번호의 순서에 따라 팀 내의 스레드에 분할하여 할당한다. 크기가 지정되지 않는 경우 총작업량을 스레드 수로 나누어 분할한다.
dynamic 방식은 작업을 수행할 준비가 완료된 대기 상태의 스레드로부터 작업 할당 요청을 한다. 스케줄을 분배한 상태로 작업을 진행하는 것이 아니라 작업을 할 수 있는 스레드가 있으면 그때그때 배분하는 방식이다. 각각의 스레드는 할당된 작업을 완료할 때까지 작업을 수행하고, 더는 진행할 작업이 없는 경우 다시 대기 상태로 들어가 작업 할당 요청을 한다. 분배하는 모든 작업량은 지정된 크기만큼 반복적으로 분해되고 마지막에는 나머지 크기만큼 할당한다. 크기를 지정하지 않았을 경우, 기본값은 1이다. 예를 들어 for-loop이 수행될 때, iteration이 진행함에 따라 작업의 크기가 커지는 경우, static을 사용하면 스레드 별로 공평하게 배분되지 않을 수 있다. dynamic 방식을 사용하면 작업량만큼 할당하므로 모든 스레드가 일정 작업량을 배분받을 수 있다.
guided는 dynamic 방식에서 배정하는 작업량을 점차 줄여나가는 방식이다. static과 dynamic 방식을 어느 정도 합한 것과 비슷하다. 작업량의 크기는 아직 배분되지 않는 Iteration를 팀 내의 스레드의 수로 나눈 것에 비례한다. 작업량은 점차 줄어들고, 마지막으로 줄어든 작업량은 설정한 크기만큼 이 된다.
auto는 컴파일러나 runtime system에 의해서 방식이 결정된다.
Sections Constuct는 loop가 아닌 동작을 병렬로 수행하기 위해서 사용되며, 각 스레드가 수행될 section들을 기술한다.
for-loop이 data parallelism을 이용한 것이라면, section은 task paralleism을 활용한다.
하나의 for-loop 구문을 한 개의 스레드에 할당하려면 아래와 같이 section을 사용하고, Loop iterator를 스레드 별로 독립적으로 수행할 수 있도록 private로 선언해야 한다.
#pragma omp parallel shared(n, a, b, c, d) private(i)
{
    #pragma omp setions nowait
    {
          #pragma omp section
          for (i = 0; i < n ; i++)
                 %%%%%%%%%
          #pragma omp section
          for (i=0; i <n-1; i++)
                 %%%%%%%%%
    }
}
Single Construct는 팀 내의 오직 한 개의 스레드만 수행되도록 지시한다. 꼭 Master일 필요는 없고, 하나의 스레드만 수행하면 된다.
앞서 parallel과 for/section 지시자를 사용하였는데, 아래와 같이 이를 합쳐서 기술해도 된다.
#pragma omp parallel for
#pragma omp parallel sections
만약 아래와 같이 두 번째 Loop의 iterator를 private로 지정하면 첫 번째 Loop만 병렬로 수행된다.
#pragma omp parallel for private (j)
for(i=0; i <M; i++)  --> 병렬로 수행.
    for(j=0;j <N;j++)  --> 병렬로 수행되지 않음.
          %%%%%%%%%%%%%%%
Reduction은 sum += A [i]와 같이 행렬의 합을 구하는 과정을 병렬로 수행하기 위한 지시자이다.
아래와 같이 어떤 operation을 수행하며, 결괏값이 저장되는 변수 이름을 적어준다.
#pragma omp parallel for reduction (+: sum)
    for (i=0;i <MAX;i++){
           sum += A[i];
    }
이를 수행하면 각 스레드는 각자의 계산 결과를 Local에 가지고 있다가 orignal global 변수로 합쳐진다.
Master Construct는 팀 내의 master가 수행하는 영역임을 지시한다.
Critical Construct는 한 번에 한 개의 스레드만이 수행되도록 한다.
Single과 Critical Construct의 차이는 무엇일까? 아래 코드 예제가 그 차이를 잘 보여준다.  아래를 보면 4개의 스레드를 팀으로 하여 수행하였고, a++은 single, b++은 critical로 설정하였다. print로 각 연산 결과를 출력해 보면, a는 1로 한 번만 수행되었고, b는 4로 4번 수행되었다. 즉, 4개의 스레드가 동시에 수행하는 병렬 영역에서 single은 하나의 스레드만 수행하는 것이고, critical은 모든 스레드가 수행하되 한 번에 한 개의 스레드만 수행되도록 하는 것이다.  

SIngle vs Critical [1]

Barrier point를 지정하거나(Barrier Contruct) 현재 Task 중의 Child task의 완료를 기다리게 하는 Taskwait Construct이 있다.
Atomic Consturct는 여러 개의 동시 쓰기 스레드의 가능성에 노출하지 않고 특정 메모리 위치가 원자성으로 업데이트되도록 한다.

OpenMP Memory Consistency model
모든 OpenMP 스레드들은 메모리에서 변수 값을 읽거나 쓸 수 있다. 추가적으로 각 스레드는 각자의 메모리를 가지는 것처럼 행동하는 것을 허용한다. OpenMP에서 지원하는 Flush 동작은 실제 Memory와 스레드가 가지는 Memory와의  Memory Consistency를 맞출 수 있도록 한다. 이때, Memory Consistency는 여러 스레드가 공유 변수를 접근하는 순서에 따라 결과 값이 달라질 수 있는 데, 이를 일정하게 정해둔 것을 의미한다. 각 스레드에서 보고 있는 변수의 값과 실제 메모리에 저장되어 있는 값이 서로 다를 수 있다. 항상 같지는 않지만 읽거나 쓰는 동작을 수행할 때는 같도록 해주는 것이 Relaxed consistency이다.
멀티 스레드 환경에서 글로벌 메모리에 있는 변숫값을 참조할 때 일시적인 오류가 발생할 수 있다. 예를 들어 하나의 스레드가 글로벌 변수를 읽고, 동시에 다른 스레드가 같은 변수를 쓴다면, 프로그램이 어떻게 동작할지 예상할 수 없다. 이처럼 하나의 메모리 변수를 가지고 여러 개의 스레드가 경합을 벌이게 될 때, 그 정합성을 유지시켜주는 지시어가 flush이다. 스레드가 글로벌 메모리에 값을 읽을 때 임시적인 뷰를 가지게 된다. 그 이후 다른 스레드가 같은 변수에 대해서 값을 변경하면 먼저 읽어간 스레드는 이전의 값을 가지고 연산을 수행하게 된다. 이때 값을 변경한 스레드에서 flush 지시어를 사용하면, 다른 스레드에서 읽어간 뷰가 갱신되면서 데이터의 정합성을 유지하게 된다.
# pragma omp flush(변수명)
'변수명'으로 지정되는 메모리의 값을 스레드 팀 전체에 전달하여, 그 데이터 정합성을 유지하도록 한다. flush 하는 변수를 콤마로 구분하여 여러 개로 지정할 수 있다. 변수명을 지정하지 않은 flush는 코드에 있는 글로벌 변수값을 전달(flush)한다.




[1] : https://stackoverflow.com/questions/33441767/difference-between-omp-critical-and-omp-single

difference between omp critical and omp single