References
- An Introduction to Parallel Programming
Contents
- Odd-even transposition sort
- MPI Safety, MPI_Ssend
- MPI_Sendrecv
- 성능 측정 및 비교
분산 메모리 환경에서 병렬 정렬 알고리즘은 무엇을 의미할까요 ? 무엇이 '입력'이 되고, 무엇이 '출력'이 될까요?
이는 정렬하고자하는 키(key)에 달려 있습니다. 프로세스 간에 분산된 키를 가지고 시작하거나 하나의 프로세스에 할당된 키로 시작할 수도 있습니다. 이번 포스팅에서는 프로세스 간 분산된 키를 사용하는 정렬 알고리즘을 살펴보겠습니다.
만약 n개의 키가 있고, 프로세스 p = comm_sz개가 있다면, 각 프로세스에 \(\frac{n}{p}\)개의 키를 할당하여 알고리즘을 수행합니다. 이때 보통 n은 p로 나누어떨어진다고 가정합니다. 시작할 때는 어떤 키가 어떤 프로세스에 할당되는지 상관없지만, 알고리즘이 종료되었을 때에는 각 프로세스의 할당된 키가 오름차순으로 정렬되어야 하고, \(q < r\)이면
프로세스 q에 할당된 각 키는 프로세스 r에 할당된 모든 키에 대해 작거나 같아야 합니다. 사용되는 키의 자료형은 int로 가정하겠습니다.
간단한 시리얼 정렬 알고리즘
우선 간단한 시리얼 정렬 알고리즘에 대해서 살펴보겠습니다. 아마 잘 알고 있으리라 생각되는 정렬은 버블 정렬(bubble sort)일 것입니다. 버블 정렬은 아래와 같이 구현할 수 있고, 이 정렬 알고리즘은 배열의 요소들을 한 쌍식 비교하며 동작합니다.
void Bubble_sort(
int a[] /* in/out */,
int n /* int */)
{
int temp;
for (int list_length = n; list_length >= 2; list_length--) {
for (int i = 0; i < list_length - 1; i++) {
if (a[i] > a[i+1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
}
}즉, a[0]은 a[1]과 비교하고 a[1]은 a[2]와 비교하는 식입니다. 만약 비교하는 쌍의 크기가 오름차순이 아니라면 두 요소의 위치를 서로 바꿉니다. 따라서 첫 번째 루프 list_length가 n일 때 배열에서 가장 큰 숫자는 첫 번째 루프가 끝날 때 a[n-1]로 이동하게 됩니다. 두 번째 루프에서 두 번째로 큰 요소가 a[n-2]의 위치로 이동합니다. 이렇게 list_length가 감소할 수록 정렬된 요소들이 리스트의 마지막 위치에 들어가게 됩니다.
우리가 이번에 병렬화하고자 하는 알고리즘이 이 버블 정렬 알고리즘은 아닙니다.
\(a[i-1] = 9, a[i] = 5, a[i+1] = 7\)이 있다고 가정해봅시다. 알고리즘의 처음에는 9와 5를 비교하여 둘의 위치를 서로 바꿉니다. 그리고 9와 7을 비교하여 이 두 값도 위치를 바꿉니다. 결국 5,7,9라는 순서를 얻게 됩니다. 만약 순서를 반대로하여 5와 7을 먼저 비교하고, 그 다음에는 9와 5를 비교하게 됩니다. 그러면 순서는 5, 9 ,7이 됩니다. 그러므로 '비교(compare)-교환(swap)'이 발생하는 순서는 알고리즘의 정확성에 중요한 요소라는 것을 알 수 있습니다.
다른 정렬을 알아볼텐데, 바로 버블 정렬에서 파생된 odd-even transposition sort 입니다. 이 정렬 알고리즘이 병렬화하기가 조금 더 용이한데, 이 알고리즘에 키 아이디어는 바로 위에서 언급한 '비교-교환'을 decouple하는 것입니다. 알고리즘은 두 종류의 phase(단계)의 연속으로 이루어집니다.
even(짝수) phase에는 다음의 쌍들이 비교-교환되고,
\[(a[0], a[1]), (a[2],a[3]), (a[4], a[5]), \cdots,\]
odd(홀수) phase에는 다음의 쌍들이 비교-교환됩니다.
\[(a[1], a[2]), (a[3], a[4]), (a[5], a[6]), \cdots, \]
간단한 예를 들어보겠습니다.
Start : (5, 9, 4, 3)
(1)Even Phase : (5,9)와 (4,3)을 비교-교환 -> (5, 9, 3, 4)
(2)Odd Phase : (9,3) 비교-교환 -> (5, 3, 9, 4)
(3)Even Phase : (5,3), (9,4) 비교-교환 -> (3, 5, 4, 9)
(4)Odd Phase : (5,4) 비교-교환 -> (3, 4, 5, 9)
이 예제는 4개의 요소를 갖는 배열 정렬하기 위해서 4단계가 필요합니다. 일반적으로 더 적은 단계로 가능하지만 이론적으로 n개의 요소를 갖는 배열을 정렬하는데 최대 n단계로 정렬할 수 있다는 것을 보장합니다.
다음은 odd-even 정렬 알고리즘을 시리얼로 구현한 것입니다.
void Odd_even_sort(
int list[] /* in/out */,
int n /* in */)
{
int tmp;
for (int phase = 0; phase < n; phase++) {
if (phase % 2 == 0) {
/* even phase */
for (int i = 1; i < n; i += 2) {
if (list[i-1] > list[i]) {
tmp = list[i];
list[i] = list[i-1];
list[i-1] = tmp;
}
}
}
else {
/* odd phase */
for (int i = 1; i < n-1; i += 2) {
if (list[i] > list[i+1]) {
tmp = list[i];
list[i] = list[i+1];
list[i+1] = tmp;
}
}
}
}
}
Odd-even 정렬의 벙렬화
이 정렬 알고리즘은 버블 정렬보다 병렬화하기가 수월합니다. 이는 모든 '비교-교환' 과정이 동시에 일어날 수 있기 때문입니다.
정렬 알고리즘이 시작될 때 각 프로세스에는 \(\frac{n}{p}\)개의 키가 할당되어 있습니다. n=p일 때, 위 그림은 알고리즘이 어떻게 동작하는지 보여주고 있는데, 단계에 따라서 프로세스 i는 현재 값 a[i]를 프로세스 i-1이나 프로세스 i+1에 전송합니다. 동시에 프로세스 i-1이나 프로세스 i+1로부터 정렬된 값을 받습니다. 그리고 나서 어떤 값이 다음 단계에서 a[i]의 값으로 저장될지를 결정합니다.
하지만, 실제 프로그램은 n=p가 아니라 일반적으로 n은 프로세스의 수보다 훨씬 많은 경우가 많습니다. 만약 프로세스가 수천 혹은 수만개의 프로세스가 액세스한다고 하더라도, 메세지를 주고받는 비용은 프로그램을 느리게 만들어서 프로그램 자체를 사용하기 어렵게 합니다.
만약 프로세스보다 키가 더 많은 상황에서는 \(\frac{n}{p} > 1\)개의 요소들을 어떻게 저장할까요? 아래의 표처럼 p = 4이고, n = 16이라고 가정해봅시다.
처음에 빠른 시리얼 정렬 알고리즘으로 각 프로세스의 요소들을 각자 정렬할 수 있습니다. 예를 들어, 각 프로세스에서 C 라이브러리의 qsort를 사용할 수 있습니다. 그리고 프로세스 0과 1은 서로의 요소들을 교환하고, 프로세스 2와 3도 서로의 요소들을 교환합니다. 그러고 나면 프로세스 0은 프로세스 0과 1의 요소들 중에서 가장 작은 4개의 요소들을 갖게 되고, 반대로 프로세스 1은 가장 큰 4개의 요소들을 갖게됩니다. 프로세스 2와 3도 동일하게 프로세스 2에서는 작은 요소들을, 프로세스 3에서는 큰 요소들을 갖게 됩니다. 이 과정의 결과가 위 표의 3번째 After Phase 0의 경우입니다.
다음 단계로 넘어가면 이번에는 Odd phase로 프로세스 1과 2가 서로의 요소들을 교환합니다. 이때, 0과 3은 idle 상태가 되어서 해당 프로세스에서는 교환이 일어나지 않습니다. 이런 과정을 반복하면 두 단계가 더 진행한 후에 정렬된 배열을 얻게 됩니다. 각 프로세스의 키는 오름차순으로 정렬되고, q < r이면 프로세스 q에 할당된 모든 키는 프로세스 r에 할당된 모든 키보다 작거나 같습니다.
(사실 이 예제는 worst case 성능을 보여주고 있긴 합니다.)
병렬 알고리즘은 의사코드로 다음과 같이 명확하게 나타낼 수 있습니다.
다만, 이 알고리즘을 MPI 프로그램으로 변환하기 전에 확실하게 정리해야할 것이 있습니다.
첫 번째는 서로 교환을 할 파트너 rank를 어떻게 계산할 지에 관한 것이고, 두 번째는 프로세스가 idle 상태일 때의 파트너 rank는 무엇인가에 대해서 입니다. 만약 even phase라면 홀수 my_rank의 파트너는 my_rank-1과 교환하고, 짝수 my_rank는 my_rank+1과 교환합니다. odd phase에서는 반대가 됩니다.
하지만, my_rank = 0 이거나 my_rank = comm_sz-1 이라면, 파트너 rank가 -1 또는 comm_sz가 될 수 있습니다. 따라서parter = -1 또는 comm_sz라면 해당 프로세스는 idle 상태가 되어야 합니다.
이 idle 상태를 위하여 MPI_PROC_NULL이라는 상수를 사용할 수 있습니다. 이는 MPI에서 제공되는 상수이며, 점대점 통신에서 source나 dest로 이 값이 사용될 때, 통신은 발생하지 않으며 통신에 대한 호출은 단순 리턴됩니다.
if (my_rank % 2 != 0) { /* even phase */
even_partner = my_rank - 1;
odd_partner = my_rank + 1;
if (odd_partner == comm_sz)
odd_partner = MPI_PROC_NULL;
}
else { /* odd phase */
even_partner = my_rank + 1;
if (even_partner == comm_sz)
even_partner = MPI_PROC_NULL;
odd_partner = my_rank - 1;
}
MPI 프로그램에서의 Safety와 MPI_Sendrecv
만약 프로세스가 idle 상태가 아닐 때, MPI_Send와 MPI_Recv을 사용하여 통신을 다음과 같이 수행할 수 있습니다.
MPI_Send(my_keys, n/comm_sz, MPI_INT, partner, 0, comm);
MPI_Recv(temp_keys, n/comm_sz, MPI_INT, partner, 0, comm, MPI_STATUS_IGNORE);하지만 이는 프로그램이 hang되거나 crash될 수 있습니다. MPI_Send는 두 가지 방법으로 동작하는데, MPI_Send가 호출되면 메세지를 MPI에서 관리하는 버퍼에 저장하고 리턴하거나, 이와 매칭되는 MPI_Recv가 호출될 때까지 block이 됩니다. MPI에서는 버퍼링의 한계를 설정하고 있기 때문에, 상대적으로 작은 메세지는 MPI_Send에 의해 버퍼링되지만, 큰 메시지의 경우에는 block될 수 있습니다. 따라서 각 프로세스에서 MPI_Send가 실행된다면, 어떠한 프로세스도 MPI_Recv를 호출할 수 없는 상황이 발생할 수 있습니다. 결국 프로그램은 hang되거나 데드락(deadlock)에 걸리며 각 프로세스는 일어나지 않을 이벤트를 무한정 기다리게 됩니다.
이처럼 MPI에서 제공하는 버퍼링에 의존적인 프로그램은 unsafe하다고 할 수 있습니다. 그러한 프로그램은 다양한 입력에 따라서 문제가 없이 실행될 수 있지만, 그러나 다른 종류의 입력에서는 hang되거나 crash될 수 있습니다. 따라서 이 방법처럼 MPI_Send와 MPI_Recv를 사용한다면, 이 프로그램은 unsafe하다고 할 수 있고, 작은 n에서는 문제없이 동작하지만 큰 n에 대해서는 문제가 발생할 수 있습니다.
그렇다면, (1)일반적으로 프로그램이 세이프(safe)하다는 것을 어떻게 말할 수 있으며, (2)이 odd-even 정렬 알고리즘에서 프로그램이 세이프하려면 통신을 어떻게 구현해야 할까요?
첫 번째 질문의 답은 MPI 표준에서 정의한 MPI_Send의 다른 버전인 MPI_Ssend를 사용하면 됩니다. 'S'가 추가로 붙은 것은 synchronous를 의미하고 MPI_Ssend에 매칭되는 수신이 시작할 때까지 blocking되는 것을 보장합니다. MPI_Ssend는 MPI_Send와 동일한 인수를 사용합니다.
(하지만, 이 경우 프로그램이 hang되는 것을 막지는 못합니다.)
저의 경우 n을 5000으로만 설정해도 프로그램이 멈추어서 진행이 되지 않았습니다.
프로그램은 아래의 코드를 컴파일하여 실행하였습니다.
GitHub - junstar92/parallel_programming_study
Contribute to junstar92/parallel_programming_study development by creating an account on GitHub.
github.com
두 번째 질문의 답은 통신이 재구성되어야 합니다. unsafe한 프로그램의 가장 공통적인 원인은 동시에 서로에서 메세지를 전송하고 수신한다는 점입니다. 바로 odd-even 정렬 알고리즘에서 파트너끼리의 교환의 경우가 이에 속합니다. 다른 예시로는 ring pass가 있는데, 프로세스 q가 프로세스 q+1에게 전송하고, 마지막 프로세스는 프로세스 0에 전송하는 것입니다.
따라서, 프로그램이 hang되는 것을 막기 위해서 다음과 같이 통신을 재구성할 수 있습니다.
또한, MPI는 통신을 스스로 스케쥴링하기 위한 MPI_Sendrecv 함수를 제공합니다.
int MPI_Sendrecv(
void* send_buf_p /* in */,
int send_buf_size /* in */,
MPI_Datatype send_buf_type /* in */,
int dest /* in */,
int send_tag /* in */,
void* recv_buf_p /* out */,
int recv_buf_size /* in */,
MPI_Datatype recv_buf_type /* in */,
int source /* in */,
int recv_tag /* in */,
MPI_Comm comm /* in */,
MPI_Status* status_p /* in */);이 함수는 하나의 함수 호출에서 send와 receive를 blocking 합니다. dest와 source는 같거나 다를 수 있습니다. 이 함수의 특별한 점은 MPI 자체에서 프로그램이 hand 또는 crash되지 않도록 통신을 스케쥴링 한다는 것입니다. 위에서 hang을 피하기 위해 rank가 짝수인지 홀수인지 체크하고 MPI_Send, MPI_Recv의 순서를 바꿔서 구현하는 코드가 아닌 이 함수 하나로 대체하여 사용할 수 있습니다.
(전송할 버퍼와 수신할 버퍼가 동일하다면, MPI_Sendrecv_replace 함수를 제공합니다. 따로 살펴보지는 않겠습니다.)
마지막으로 각 프로세스에서 서로 주고받은 키들을 오름차순으로 정렬하여 각 프로세스에 할당하는 것이 남았습니다. 만약 프로세스 0과 1이 서로의 키들을 교환했다면, 프로세스 0에는 0과 1에 존재하는 \(\frac{2n}{p}\)개의 키들 중에서 가장 작은 \(\frac{n}{p}\)개의 키를 갖도록 하고 프로세스 1에는 가장 큰 \(\frac{n}{p}\)개의 키를 갖도록 해야합니다. 가장 확실한 방법은 \(\frac{2n}{p}\)개의 요소를 갖는 배열을 정렬하는 것입니다. 하지만, 정렬은 상대적으로 코스트가 많이드는 연산이기 때문에 우리는 이미 \(\frac{n}{p}\)개의 요소를 갖는 이미 정렬된 배열을 하나의 배열로 머지하는 것이 좋습니다. 사실 완전히 머지할 필요도 없습니다. 각 프로세스는 가장 작은 키들 혹은 가장 큰 키들을 다 찾기만한다면 바로 중단해도 상관없기 때문입니다.
가장 작은 \(\frac{n}{p}\)개의 키를 찾는 함수는 다음과 같습니다.
void Merge_low(int local_list[], int recv_list[], int temp_list[], int local_n)
{
int local_i = 0, recv_i = 0, temp_i = 0;
while (temp_i < local_n) {
if (local_list[local_i] <= recv_list[recv_i]) {
temp_list[temp_i] = local_list[local_i];
local_i++; temp_i++;
}
else {
temp_list[temp_i] = recv_list[recv_i];
recv_i++; temp_i++;
}
}
memcpy(local_list, temp_list, local_n * sizeof(int));
}
가장 큰 \(\frac{n}{p}\)개의 키를 찾으려면 위에서 합친 배열의 순서를 거꾸로 하면 됩니다.
이를 모두 적용하여 odd-even 정렬은 다음과 같이 구현할 수 있습니다.
void Sort(int local_list[], int local_n, int my_rank, int comm_sz, MPI_Comm comm)
{
int* recv_list, *temp_list;
int even_partner, odd_partner;
recv_list = (int*)malloc(local_n * sizeof(int));
temp_list = (int*)malloc(local_n * sizeof(int));
if (my_rank % 2 != 0) {
even_partner = my_rank - 1;
odd_partner = my_rank + 1;
if (odd_partner == comm_sz)
odd_partner = MPI_PROC_NULL;
}
else {
even_partner = my_rank + 1;
if (even_partner == comm_sz)
even_partner = MPI_PROC_NULL;
odd_partner = my_rank - 1;
}
/* Sort local list using built-in quick sort */
qsort(local_list, local_n, sizeof(int), Compare);
for (int phase = 0; phase < comm_sz; phase++)
Odd_even_iter(local_list, recv_list, temp_list, local_n, phase,
even_partner, odd_partner, my_rank, comm_sz, comm);
free(recv_list);
free(temp_list);
}
void Odd_even_iter(int local_list[], int recv_list[], int temp_list[],
int local_n, int phase, int even_partner, int odd_partner,
int my_rank, int comm_sz, MPI_Comm comm)
{
MPI_Status status;
if (phase % 2 == 0) {
/* even phase */
if (even_partner >= 0) {
MPI_Sendrecv(local_list, local_n, MPI_INT, even_partner, 0,
recv_list, local_n, MPI_INT, even_partner, 0, comm, &status);
if (my_rank % 2 != 0)
Merge_high(local_list, recv_list, temp_list, local_n);
else
Merge_low(local_list, recv_list, temp_list, local_n);
}
}
else {
/* odd phase */
if (odd_partner >= 0) {
MPI_Sendrecv(local_list, local_n, MPI_INT, odd_partner, 0,
recv_list, local_n, MPI_INT, odd_partner, 0, comm, &status);
if (my_rank % 2 != 0)
Merge_low(local_list, recv_list, temp_list, local_n);
else
Merge_high(local_list, recv_list, temp_list, local_n);
}
}
}Sort 함수가 먼저 호출되고, 각 프로세스의 요소들을 우선 퀵소트로 정렬한 후에 파트너 rank와 서로의 키를 교환하고, 머지하여 두 프로세스 간의 오름차순이 되도록 알고리즘을 수행합니다.
전체 코드는 아래를 참조하시기 바랍니다 !
https://github.com/junstar92/parallel_programming_study/blob/master/mpi/13_mpi_odd_even_sort_safe.c
GitHub - junstar92/parallel_programming_study
Contribute to junstar92/parallel_programming_study development by creating an account on GitHub.
github.com
아래는 프로세스와 배열의 수에 따른 실행시간입니다.
그리고 C++의 <algorithm>에서 제공되는 sort 함수로 동일한 크기의 배열의 정렬하는데 걸린 시간을 측정해보았습니다.
8코어 프로세스를 모두 사용할 때보다 약 3배의 성능 차이를 보여주고 있습니다.
'프로그래밍 > 병렬프로그래밍' 카테고리의 다른 글
| [pthread] 행렬 - 벡터 곱 연산 (+ 캐시 일관성, 거짓 공유) (0) | 2021.11.16 |
|---|---|
| [pthread] Hello, Pthreads (0) | 2021.11.15 |
| [MPI] MPI Derived Datatypes (파생 데이터타입) (0) | 2021.11.13 |
| [MPI] 행렬 - 벡터 곱 연산 + 성능 평가 (0) | 2021.11.12 |
| [MPI] 데이터 분산 (벡터합 병렬화) (0) | 2021.11.11 |
댓글