[MPI] 사다리꼴 공식 (trapezoidal rule) 병렬화 - 2

References

• An Introduction to Parallel Programming

Contents

• Collective Communication (집합 통신)
• MPI_Reduce, MPI_Allreduce, MPI_Bcast

---

이전 글에서 MPI로 사다리꼴 공식을 병렬화하여 코드를 작성해봤습니다.

2021.11.09 - [프로그래밍/병렬프로그래밍] - [MPI] 사다리꼴 공식 (trapezoidal rule) - 1

하지만 작성한 코드에서 각 프로세스들은 연산을 수행하고 그 연산 결과를 합하기 위하여 프로세스 0에게 결과를 전달하고, 프로세스 0에서 모든 결과를 더하는 작업을 수행합니다. 이전 글 마지막에 언급했듯이 이러한 작업이 최선이 아니고, 성능을 향상시킬 수 있는 여지가 남아있습니다.

 

트리 구조 통신

2021.11.07 - [프로그래밍/병렬프로그래밍] - 병렬 프로그래밍

병렬 프로그래밍

위 글에서 언급했듯이 아래의 이진 트리 구조를 사용할 수 있습니다.

이 다이어그램에서 프로세스 1,3,5,7은 자신의 값을 프로세스 0,2,4,6에게 각각 전송합니다. 그리고 0,2,4,6은 수신한 값에 자신이 갖고 있는 값을 더합니다. 이 과정을 반복하면 최종 합을 구할 수 있습니다. 

이러한 솔루션은 이상적으로 보이지는 않습니다. 그 이유는 프로세스의 절반(1,3,5,7)은 기존의 방식 그대로 작업하기 때문입니다. 그러나 이 문제를 조금만 생각해보면 이전에는 프로세스 0에서 comm_sz - 1 = 7개의 수신과 7개의 덧셈이 필요했습니다. 그에 비해 위의 새로운 방법은 프로세스 0에서 3번의 수신과 덧셈을 하고 다른 프로세스들이 나머지 수신과 덧셈을 했습니다. 즉, 다른 프로세스에 의해서 많은 일을 병행하여 처리할 수 있게 되었습니다.

예를 들어, 첫 번째 과정에서 프로세스 0, 2, 4, 6의 수신과 덧셈은 동시에 일어날 수 있습니다. 프로세스가 거의 같은 시간에 시작하면 global sum을 구하는데 걸리는 전체 시간은 프로세스 0이 3번의 수신과 3번의 덧셈을 하는데 필요한 시간과 같습니다.

 

즉, 전체 시간을 약 50% 감소시켰고, 만약 더 많은 프로세스를 사용한다면 더 좋은 성능을 얻을 수 있을 것입니다. 

만약 somm_sz = 1024라면 기존의 방법은 프로세스 0에서 1023번의 수신과 덧셈을 해야하는 반면에 이 방법은 프로세스 0이 단지 10번의 수신과 덧셈만을 하면 됩니다. 이는 기존의 방법에서 약 100배의 성능 향상을 발생하였습니다.

 

아마도 괜찮은 것이라고 생각되겠지만, 트리 구조 global sum을 코딩하는 것은 생각보다 해야할 것들이 많아보일 수 있습니다. 사실 문제는 더 어려운데, 예를 들어, 다른 프로세스-쌍을 사용하여 트리 구조 global sum을 구현하는 것은 완벽하게 가능합니다. 아래 그림처럼 첫 번째 단계에서 0과 4를 한 쌍으로, 1과 5를 한 쌍으로, 2와 6을, 3와 7을 한 쌍으로 만들 수 있습니다. 그리고 나서 두 번째 단계에서 0과 2, 그리고 1과 3을 묶을 수 있으며 마지막으로 0과 1을 묶을 수 있습니다.

물론 다른 경우의 수도 많이 존재합니다. 어떤 것이 가장 최선인지를 어떻게 결정할 수 있을까요 ? 작업에 따라서 적합한 구조가 다를 수 있고, 최악의 경우에는 각 시스템마다 잘 동작하는 구조가 따로 있을 수 있습니다.

 

---

Collective Communication 집합 통신

이러한 상황에서 MPI 개발자들이 최적화된 global-sum 함수를 구현한다고 기대한다는 것은 힘듭니다. 그래서 MPI는 특별히 개발자들이 MPI 구현에 필요한 끝없는 최적화에 빠지지 않도록 보호하는데, 이는 어플리케이션 개발자가 아닌 MPI 개발자들이 해야하는 몫입니다.

 

global-sum 함수는 통신이 필요합니다. 그러나 MPI_Send와 MPI_Recv의 쌍과는 달리 global-sum 함수는 두 개 이상의 프로세스를 포함합니다. 사실 사다리꼴 공식 프로그램에서 MPI_COMM_WORLD의 모든 프로세스를 포함하긴 했습니다. MPI에서는 커뮤니케이터에 있는 모든 프로세스를 포함하는 통신 함수를 Collective Communication(집합 통신)이라고 합니다. 이 집합 통신과 MPI_Send/MPI_Recv와 같은 함수를 구분하기 위해서 MPI_Send와 MPI_Recv를 Point-to-Point Communication(점대점 통신)이라고 합니다.

 

사실 global sum은 집합 통신 중에서 하나의 케이스입니다. 예를 들어, comm_sz 집합의 수들의 합을 찾는 대신 이 수들에서 최댓값, 최솟값 등의 다른 케이스를 찾을 수도 있습니다. MPI에서는 global sum 함수를 일반화하여 여러 기능 중의 하나를 하나의 함수로 구현했습니다.

MPI_Reduce

int MPI_Reduce(
	void*          input_data_p  /* in  */,
    void*          output_data_p /* out */,
    int            count         /* in  */,
    MPI_Datatype   datatype      /* in  */,
    MPI_Op         operator      /* in  */,
    int            dest_process  /* in  */,
    MPI_Comm       comm          /* in  */);

일반화하는 중요한 키는 바로 5번째 인수, operator 입니다. 이 인수는 MPI_Op 타입이고, 이는 MPI_Datatype이나 MPI_Comm처럼 MPI에 정의된 타입입니다. 여러 개의 정의된 MPI_Op 타입이 있으며, 새로운 operator 타입을 정의하는 것도 가능합니다.

global sum에서 사용하는 것은 MPI_SUM 입니다. operator 인수로 이 값을 사용하면 02_mpi_trap1.c에서 main함수의 line 41-51은 아래처럼 하나의 함수 호출로 변경할 수 있습니다.

MPI_Reduce(&local_int, &total_int, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

전체 코드는 아래 github을 참조바랍니다.

https://github.com/junstar92/parallel_programming_study/blob/master/mpi/04_mpi_trap2.c

GitHub - junstar92/parallel_programming_study

한 가지 포인트는 count 인수는 1 이상이라는 것입니다. MPI_Reduce는 스칼라 대신 배열을 사용하는데, 만약 하나의 프로세스당 N차원 벡터의 합을 구하려면 다음과 같이 호출할 수 있습니다.

---

Collective Communication vs. Point-to-Point Communication

집합 통신과 점대점 통신은 여러가지 면에서 다릅니다.

1. 커뮤니케이터 안에 있는 모든 프로세스는 같은 집합 통신 함수를 호출해야 합니다. 예를 들어, MPI_Reduce에 대한 호출은 다른 프로세스에서 MPI_Recv에대한 호출과 매칭시키려는 시도는 에러를 발생시킬 수 있으며, 프로그램이 hang되거나 crash됩니다.
2. 각 프로세스에서 MPI Collective 통신으로 전달된 인수들은 호환되어야 합니다. 예를 들어, dest_process에 0을 전달하고 다른 프로세스에는 1을 전달하면 MPI_Reduce의 호출에 대한 결과는 에러를 발생시킵니다. 이 경우에도 프로그램이 hang되거나 crash됩니다.
3. output_data_p 인수는 dest_process에서만 사용되어야 합니다. 그러나 모든 프로세스에서 output_data_p에 대응되는 실제 인수를 넘길 필요가 있는데, 이는 NULL을 사용해도 됩니다.
4. 점대점 통신은 tag와 커뮤니케이터를 기반으로 매칭됩니다. 집합 통신은 tag를 사용하지 않으며 커뮤니케이터와 호출된 순서를 기반으로 매칭됩니다. 예를 들어, 아래의 MPI_Reduce에 대한 호출을 보여주는 표를 보도록 하겠습니다. 각 프로세스가 MPI_SUM operator를 갖고 MPI_Reduce를 호출하고 도착 프로세스는 0이라고 가정하도록 하겠습니다. 표를 봤을 때, MPI_Reduce는 2번 호출되었다고 할 수 있습니다. 따라서, 호출은 Time 1에서 a를 b에 더하는 호출 2번, c를 d에 더하는 호출 1번, 그리고 Time 2에서 a를 b에 더하는 호출 1번, c를 d에 더하는 호출 2번, 각 프로세스에서 2번씩 호출이 되었습니다. 그러나 메모리 위치의 이름은 매칭이나 MPI_Reduce의 호출과는 상관이 없습니다. 호출 순서가 매칭을 결정하고, 따라서 밑의 표의 경우에 b에 저장된 값은 1+2+1=4이며, d에 저장된 값은 2+1+2=5 입니다.

 

4번이 조금 헷갈려서 실제로 테스트를 해봤습니다. 아래 코드는 짝수번 프로세스에서와 홀수번 프로세스의 MPI_Reduce의 호출 인수가 반대입니다.

#include <stdio.h>
#include <mpi.h>

int main(void)
{
    int a = 1, b = 0, c = 2, d = 0;
    int comm_sz, my_rank;

    MPI_Init(NULL, NULL);
    MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

    if(my_rank % 2 == 0) {
        MPI_Reduce(&a, &b, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
        MPI_Reduce(&c, &d, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
    }
    else {
        MPI_Reduce(&c, &d, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
        MPI_Reduce(&a, &b, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
    }

    if(my_rank == 0) {
        printf("b = %d\n", b);
        printf("d = %d\n", d);
    }

    MPI_Finalize();

    return 0;
}

위 코드를 컴파일하고, 3개의 프로세스만 활성화하여 실행하면,

위의 결과를 얻을 수 있습니다. 실제 MPI_Reduce 호출과는 상관이 없고, 호출 순서가 매칭을 결정합니다.

그렇다면, 어떤 프로세스의 호출 순서로 매칭을 결정하는가를 살펴봤습니다. MPI_Reduce의 dest_process를 1로 변경하고, 22 line의 if(my_rank == 0)을 if(my_rank == 1)로 변경하여 다시 컴파일하고 실행해봤습니다.

이번엔 반대의 결과가 나왔습니다. b는 2+1+2=5가 되었고, d는 1+2+1=4가 되었습니다.

 

결과를 봐선 목적지 프로세스의 MPI_Reduce 호출 순서에 따라서 매칭이 결정되는 것 같습니다.

 

 

MPI_Reduce를 사용할 때 주의사항으로는 입력과 출력을 같은 버퍼를 사용하여 MPI_Reduce를 호출하려고 할 수 있습니다. 예를 들어, 각 프로세스에서 x의 합계를 구해서 프로세스 0의 x에 결과를 저장하려고 한다면 다음과 같이 호출할 수 있습니다.

MPI_Reduce(&x, &x, 1, MPI_DOUBLE, MPI_SUM, 0, comm);

그러나 이 호출은 맞지 않는 코드이고, 그 결과는 예측할 수 없습니다. 잘못된 결과를 출력하기도 하고, 프로그램이 crash될 수도 있습니다. 심지어 올바른 결과가 나올 수도 있습니다. 이는 output 인수의 aliasing을 포함하기 때문입니다. 만약 같은 메모리 블록을 참조한다면 두 인수는 앨리어스되고, MPI는 그 인수들 중 하나가 input/output 인수라면 인수의 앨리어스를 금지하고 있습니다.

 

---

MPI_Allreduce

사다리꼴 공식 프로그램에서 단순히 결과를 출력했지만, 모든 프로세스에서 이 결과(global sum)이 필요한 상황이 있을 수도 있습니다. 이러한 경우 global sum에서 직면했던 문제들을 다시 만나게 됩니다. 예를 들어, global sum를 위해서 트리를 사용한 경우, global sum을 다시 각 프로세스에 분산하기 위해서 트리를 역으로 구성할 수 있습니다.

위 방법 대신, 우리는 단방향 통신을 사용하지 않고 각 프로세스들이 부분적인 결과를 바꾸는 방법을 사용할 수 있습니다. 이러한 패턴을 butterfly라고 부릅니다.

어떤 구조를 사용할지나 어떻게 최적의 성능을 갖도록 코딩할지를 결정할 필요는 없습니다. 다행히, MPI에서는 커뮤니케이터의 모든 프로세스에 결과를 저장하는 MPI_Allreduce를 제공합니다.

int MPI_Allreduce(
	void*        input_data_p  /* in  */,
    void*        output_data_p /* out */,
    int          count         /* in  */,
    MPI_Datatype datatype      /* in  */,
    MPI_Op       operator      /* in  */,
    MPI_Comm     comm          /* in  */);

이 함수에 사용되는 함수는 dest_process가 없다는 것을 제외하고는 MPI_Reduce의 인수와 동일합니다. (모든 프로세스가 동일한 결과를 갖게 되기 때문)

 

---

MPI_Bcast

지금까지 프로세스 0에서 수신하는 트리 구조를 수정하여 성능을 향상시켰다면, 입력 데이터의 분산을 유사한 방식으로 성능을 향상시킬 수 있습니다.

아까 위에서 봤던 트리 구조의 역으로 통신한다면 아래의 같은 트리 구조를 얻을 수 있습니다.

그리고 이 구조를 입력 데이터를 분산시키는 구조로 사용할 수 있습니다. 하나의 프로세스에 속해있는 데이터가 커뮤니케이터에 존재하는 모든 프로세스에게 전송되는 집합 통신(Collective Communication)을 broadcast라고 합니다. 그리고 이 통신을 위해 MPI는 MPI_Bcast 함수를 제공합니다.

int MPI_Bcast(
	void*        data_p      /* in/out */,
    int          count       /* in     */,
    MPI_Datatype datatype    /* in     */,
    int          source_proc /* in     */,
    MPI_Comm     comm        /* in     */);

source_proc 프로세스는 커뮤니케이터 comm에 있는 모든 프로세스에게 data_p에 의해 참조되는 메모리의 내용을 송신합니다. 04_mpi_trap2.c의 코드에서 MPI_Bcast를 Get_input 함수에서 사용하여, 입력받은 입력 데이터들을 모든 프로세스에 전송할 수 있습니다.

(전체 코드: https://github.com/junstar92/parallel_programming_study/blob/master/mpi/05_mpi_trap3.c)

void Get_input(int my_rank, int comm_sz, double* p_a, double* p_b, int* p_n)
{
    if (my_rank == 0) {
        printf("Enter a, b, and n\n");
        scanf("%lf %lf %d", p_a, p_b, p_n);
    }

    MPI_Bcast(p_a, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Bcast(p_b, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Bcast(p_n, 1, MPI_INT, 0, MPI_COMM_WORLD);
}

이 함수에서 더이상 MPI_Send와 MPI_Recv를 사용하지 않고, 대신 MPI_Bcast를 사용합니다.