병렬 프로그래밍

References

• An Introduction to Parallel Programming (Peter Pacheco)

Contents

• 병렬 프로그램이 필요한 이유
• 병렬 프로그램을 작성하는 방법
• 공유 메모리(shared-memory)와 분산 메모리(distributed-memory)

---

병렬 프로그래밍이 필요한 이유

싱글 프로세서 성능의 증가는 집적회로(intergraed circuit;IC)의 트랜지스터, 즉 전자회로의 밀집도 증가에 기인합니다. 트랜지스터의 크기가 작아질수록 트랜지스터의 속도는 증가되며, 집적회로의 전체 속도도 증가됩니다. 그러나 트랜지스터 속도의 증가는 전력 소모도 증가시킵니다. 이 전력 대부분은 열로 발산되며, 집적회로가 뜨거워지면 그 회로의 기능에 대한 신뢰성이 떨어집니다.

 

그러므로 직접회로의 속도를 계속 증가시키는 것이 점점 불가능해졌습니다. 그러나 트랜지스터 자체의 집적도는 적어도 당분간은 계속 증가할 수 있고, 현재의 컴퓨팅 능력을 높이기 위해 이러한 노력들은 피할 수 없는 선택입니다. 따라서 만약 집적회로 산업이 계속해서 새롭고 더 나은 제품을 개발하지 못한다면 산업은 점차 소멸할 수 밖에 없을 것입니다.

 

그렇다면 어떻게 트랜지스터의 집적도를 계속 증가시켜 나갈 수가 있을까요? 이 문제의 정답이 바로 병렬화(parallelism)입니다. 더 빠르고 더 복잡한 모놀리식(monolithic) 프로세서를 구축하기보다는, 상대적으로 간단하고 완벽한 프로세서 여러 개를 하나의 칩에 넣기로 결정했습니다. 이러한 집적회로를 멀티코어(multicore) 프로세서라고 하며, 코어(core)는 중앙처리장치(central processing unit), 즉 CPU라고 합니다. 하나의 CPU로 구성된 기존의 프로세서를 싱글코어(single-core) 시스템이라고 합니다.

 

---

대부분의 프로그램은 하나의 코어만을 고려하는 일반적인 방법으로 프로그래밍되고 멀티코어의 존재에 대해 고려하지는 않습니다. 멀티코어 시스템에서 하나의 프로그램에 대한 다중 인스턴스(instance)를 생성하여 실행하기도 하지만, 이것을 정확하게 멀티코어를 고려했다고 말하기는 어렵습니다. 예를 들어, 게임 프로그램을 여러 개의 인스턴스로 생성하여 실행하는 것은 우리가 원하는 것이 아니고, 좀 더 빠르게 실행되고 보다 화려한 그래픽을 보는 것을 원할 수 있습니다. 이러한 일을 하기 위해서 시리얼 프로그램을 병렬 프로그램으로 다시 작성해야 하며, 병렬 프로그램을 작성해야 멀티코어를 사용할 수 있습니다. 혹은 시리얼 프로그램을 병렬 프로그램으로 자동으로 변환해주는 변환 프로그램을 이용하기도 합니다. 다만, C/C++로 작성된 시리얼 프로그램을 병렬 프로그램으로 변환해 주는 프로그램은 제약이 많습니다.

이러한 프로그램은 놀랄만한 것은 아닙니다. 시리얼 프로그램에서 공통 부분을 인식하는 프로그램을 작성하여, 자동으로 이러한 부분을 효율적인 병렬 코드로 변환할 수 있지만, 병렬 코드들의 시퀀스는 상당히 비효율적인 코드가 될 수 있습니다.

 

시리얼 프로그램의 효율적인 병렬 구현은 각 단계별로 효율적으로 병렬화한다고 얻을 수 있는 것이 아닙니다. 오히려 가장 최고의 병렬화는 각 단계를 효율적으로 병렬화하는 것보다 완전히 새로운 알고리즘을 개발하는 것이 더 최선일 수 있습니다.

예를 들어, n개의 값을 계산하고 그 값을 덧셈하는 경우를 가정해보겠습니다. 우선 다음의 시리얼 코드로 원하는 결과를 얻을 수 있습니다.

sum = 0;
for (i = 0; i < n; i++)
{
	x = Compute_next_value(...);
    sum += x;
}

 

이제 p개의 코어가 있고, p는 n보다는 훨씬 작다고 가정해보겠습니다. 그렇다면 각 코어는 \(\frac{n}{p}\)의 수만큼 부분합의 형태로 변경할 수 있습니다.

my_sum = 0;
my_first_i = ...;
my_last_i = ...;
for (my_i = my_first_i; my_i < my_last_i; my_i++)
{
	my_x = Compute_next_value(...);
    my_sum += my_x;
}

(여기서 my_라고 하는 접두어는 각 코어에서 자신의 로컬 변수 혹은 프라이빗(private) 변수를 사용하며, 각 코어는 이 코드 블록을 다른 코어와는 상관없이 독립적으로 실행한다는 것을 의미합니다.

 

각 코어가 이 코드의 실행을 완료한 후에 변수 my_sum에는 Compute_next_value를 호출해서 계산한 값의 합이 저장됩니다. 예를 들어, 코어가 8개이고, n = 24이면, 24번의 Compute_next_value를 호출하고, 호출 결과는 다음과 같다고 가정하겠습니다.

그렇다면, 각 코어에서 my_sum에 저장된 값은 다음과 같을 것입니다.

(여기서 각 코어는 0, 1, ..., p-1까지의 범위 중에서 음수가 아니라고 가정하고, p는 코어의 수입니다.)

 

각 코어가 my_sum 값의 계산을 완료하면 그 결과를 '마스터' 코어로 설계된 코어에 해당 결과를 전송해서 전체 합을 계산합니다. 그 부분에 대한 코드를 다음과 같이 구현할 수 있습니다.

if (마스터 코어) {
	sum = my_sum;
    foreach (각 코어에서) {
    	코어들로부터 값 수신(value);
        sum += value;
    }
}
else {
	my_sum을 마스터 코어에 전송;
}

결과를 보면, 마스터 코어를 코어 0이라고 했을 때, 그 값은 8 + 19 + 7 + 15 + 7 + 13 + 12 + 14 = 95가 됩니다.

 

하지만, 이보다 더 좋은 방법이 존재합니다. 특히, 코어 수가 많다면 더욱 그렇습니다. 마스터 코어에서 최종 합계를 구하는 작업 전부를 맡기는 것보다 각 코어들을 쌍으로 묶어서 코어 0은 코어 1과의 합을 계산하고, 코어 2는 코어 3과의 합을 계산하도록 하는 방법입니다. 이러한 작업은 짝수 코어에서 실행하게 됩니다. 반복해서 코어 0은 코어 2와의 합을 계산하고, 코어 4는 코어 6과의 합을 계산하는 식입니다. 

이 과정을 위 그림과 같이 네 번 반복할 수 있습니다.

전역합에서 코어 0에서 최종 합계를 구하는 방법은 마스터 코어(코어 0)가 다른 코어보다 더 많은 일을 하며, 프로그램이 최종합을 구하는데 걸리는 시간은 마스터 코어가 완료하는 시간에 따라 결정됩니다. 그러나 8개의 코어가 있는 경우, 첫 번째 방법(코어 0에서 모든 합을 계산)에서 마스터 코어는 다른 코어로부터 총 7번의 합을 수신받아서 덧셈을 하게 되지만, 두 번째 방법은 단지 세 번만 이 작업을 해주면 됩니다. 따라서 두 번째 방법의 결과는 두 배 이상의 성능이 향상됩니다.

 

이 결과의 차이는 코어의 수가 증가하면 할수록 더 커집니다. 1000개의 코어가 있는 경우 첫 번째 방법은 999번을 수신하고 덧셈하지만, 두 번째 방법은 단지 10번의 수신만 필요하고, 결국 거의 100배의 성능 증가를 얻을 수 있습니다.

 

첫 번째 전역합은 시리얼 형태의 전역합을 일반화시킨 평이한 방법입니다. 코어별로 덧셈 작업을 나누고, 각 코어는 자신의 합을 계산한 후에 마스터 코어는 단순히 기본적인 시리얼 덧셈을 반복합니다. p개의 코어가 있다면 p만큼의 덧셈이 필요하게 됩니다. 반면에, 두 번째 전역합은 처음의 시리얼 덧셈과 많은 차이가 있습니다.

 

여기서 중요한 것은 변환 프로그램으로는 두 번째 전역 합 알고리즘을 만들어 내는 것이 쉽지 않다는 것입니다. 오히려 효율적인 전역합을 미리 정의하고 변환 프로그램을 통해 그 정의된 알고리즘의 형태로 변환하는 것이 일반적입니다. 이는 원래의 시리얼 루프를 인식하고 그 인식된 부분을 미리 코딩되어 있는 효율적이고 병렬화된 전역합의 코드로 변환하는 것입니다.

 

시리얼 코드의 많은 부분이 공통 부분으로 인식되고 효율적으로 병렬화되도록 수정하여 다중 코어를 사용할 수 있도록 하기 위한 소프트웨어를 개발할 수 있지 않을까 기대할 수도 있습니다만, 시리얼 프로그램이 복잡하면 할수록 그 내부를 병렬화 가능 부분으로 인식하기는 너무 어렵습니다. 따라서 이러한 부분을 효율적인 병렬화 코드로 미리 코딩하기는 거의 불가능에 가깝습니다.

 

때문에 시리얼 프로그램을 작성하지 않고 병렬 프로그램을 작성해야 프로그램이 멀티 프로세서의 능력을 제대로 이용할 수 있습니다.

---

병렬 프로그램을 작성하는 방법

이 주제에 대해 몇 가지 답을 제시할 수는 있지만, 이 주제에 대한 해답은 코어에서 동작하는 각각의 작업량을 파티셔닝(partitioning)한다는 기본적인 개념에 따라 몇 가지로 다르게 나타납니다. 크게 보면 태스크 병렬화(task-parallelism)와 데이터 병렬화(data-parallelism)라는 두 가지 방법이 있습니다. 태스크 병렬화는 문제를 해결하기 위해 여러 가지 태스크를 각 코어에 파티셔닝, 즉 할당하는 방법입니다. 데이터 병렬화는 문제를 해결하기 위해 사용할 데이터를 쪼개어 각 코어에 할당하는 방법입니다.

 

예를 들어, P 교수가 강의를 하는데, P 교수의 수업을 듣는 학생 수는 100명, 네 명의 조교 A, B, C, D가 있다고 가정해봅시다. 학기가 끝날 때 P 교수는 다섯 문제로 구성된 기말고사를 보기로 하고, 이 기말고사를 채점하기 위해서 P 교수와 네 명의 조교들은 다음과 같은 두 가지 선택을 고민하게 됩니다. P 교수와 네 명의 조교는 한 문제당 학생 100명의 기말고사를 채점할 수 있습니다. 이는 P 교수는 1번 문제, A 조교는 2번 문제를 맡아서 채점하는 방법입니다. 또 하나의 선택은 한 명당 전체 기말고사 중에 20명 분의 문제지를 채점하는 방법입니다. 

 

위의 두 가지 방법에서 교수와 조교들은 '코어'를 의미합니다. 첫 번째 방법은 태스크 병렬화의 예라고 볼 수 있습니다. 이 방법은 다섯 개의 태스트가 동작하는 방법이며, 각 태스크마다 하나의 문제에 대해 채점하는 방식입니다. 각 채점자마다 채점하는 문제에 대한 정보는 서로 다른데, 따라서, 교수와 네 명의 조교는 서로 다른 채점 기준으로 채점하게 됩니다.

반대로, 두 번째 방법은 데이터 병렬화를 고려한 방법입니다. '데이터'는 학생들이 제출한 답안지이며, 각 답안지를 코어의 수에 맞게 배분하여 각 코어들은 같은 채점 기준으로 채점하게 됩니다.

 

위의 전역합 예제에서 첫 번째 부분(각 코어에서 합을 구하는 것) 데이터 병렬화의 예를 고려한 경우입니다. 데이터는 Compute_next_value로 계산되며 각 코어에서는 할당된 엘리먼트만큼 같은 동작을 수행합니다. 첫 번째 전역합의 두 번째 파트는 태스트 병렬화를 고려한 것인데, 여기서는 중간 합계를 받아서 각 코어의 중간 합계를 더하는 마스터 코어의 태스크와 중간 합계를 계산하고 마스터 코어에 전송하고 마스터 코어 이외의 다른 코어에서 실행되는 태스크로 구성되어 있습니다.

 

코어들이 서로 독립적으로 실행할 때, 병렬 프로그램은 시리얼 프로그램을 작성하는 방법과 거의 같습니다. 코어들이 서로 협력할 필요가 있을 때 프로그램 작성 방법이 점점 더 복잡해지게 됩니다. 위의 두 번째 전역합의 예제에서 다이어그램의 트리 구조는 이해하기에는 쉽지만 실제 코드를 작성하기에는 꽤 어렵습니다. 이는 코어들 간에 협력해야할 것들이 많기 때문입니다.

 

두 개의 전역합 예제에서는 코어들 간의 협력은 서로 간의 통신(communication)을 포함하고 있습니다. 하나 이상의 코어들이 현재의 부분 합을 다른 코어에서 전송합니다. 전역합의 예제는 로드 밸런싱(load balancing)을 통한 협력도 포함하고 있습니다. 명시적인 수식으로 살펴보지는 않았지만, 각 코어들마다 거의 비슷한 양의 계산을 하는 것이 바람직합니다. 예를 들어, 하나의 코어가 대부분의 연산을 하고 나머지 코어들은 상대적으로 연산이 적어 빨리 끝난다면, 전체적인 연산 능력을 낭비하게 됩니다.

 

세 번째는 동기화(synchronization)입니다. 예를 들어, 연산할 값을 추가하는 대신 stdin으로부터 그 값을 읽어들인다고 가정해봅시다.

if (마스터코어)
{
	for (my_i = 0; my_i < n; my_i++)
    	scanf("%lf", &x[my_i]);
}

대부분의 시스템에서 코어는 자동적으로 동기화하지 못합니다. 오히려 각 코어는 다른 코어의 존재에 대한 고려없이 동작합니다. 이 경우에 문제는 다른 코어들이 아직 계산되지도 않은 중간 합계를 사용하려고 한다거나, 마스터 코어가 x를 초기화하고 다른 코어들에게 x를 사용해도 된다고 알리기도 전에 중간 합계를 계산하는 경우입니다.

즉, 이 말은 각 코어는 코드 실행 전에 기다려야 한다는 의미입니다.

 

---

앞으로 병렬 프로그램을 작성하는 방법에 대해서 알아볼텐데, MPI, POSIX threads(Pthreads), OpenMP를 사용하여 프로그래밍하는 기본 개념을 알아볼 예정입니다. 여기서 MPI와 Pthreads는 C 프로그램에서 사용할 수 있도록 구성된 라이브러이며, OpenMP는 라이브러리와 함께 약간의 C 컴파일러의 대산 수정도 필요합니다.

 

병렬 시스템에는 중요한 두 가지 타입이 존재하는데 하나는 공유 메모리(shared-memory) 시스템이고, 다른 하나는 분산 메모리(distributed-memory) 시스템입니다. 공유 메모리 시스템에서는 컴퓨터의 메모리를 공유하며, 특히 각 코어는 각 메모리의 주소에 읽고 쓸 수 있습니다. 공유 메모리 시스템에서는 공유 메모리 주소를 액세스하거나 업데이트하면서 각 코어들 간의 협업을 할 수 있도록 합니다. 반면에 분산 메모리 시스템에서는 자신만의 메모리, 즉 개인(private) 메모리를 갖고 있으며, 코어들간에는 네트워크를 통해 메세지를 전송하는 등의 방법을 통해 명시적으로 통신해야 합니다.

(왼) 공유 메모리 / (오) 분산 메모리

 

Pthreads와 OpenMP는 공유 메모리 시스템에서 사용되도록 설계되었고, 이 두 가지 기술은 공유 메모리 주소를 액세스할 수 있는 메커니즘을 제공합니다. MPI는 분산 메모리 시스템에서 프로그래밍할 수 있도록 설계되었습니다. 따라서 메세지 전송과 관련된 메커니즘을 제공합니다.