[Parallel Computing] (13) MPI

MPI(Message Passing Interface)는 Cluster의 node 간의 통신을 수행한다.
Symmetric multiprocessing 혹은 SMP(Shared-memory multiprocessing)는 여러 개의 프로세서들을 포함하고 있으며 각 프로세서는 각자의 메모리 가지고 있고, 프로세서들이 모두 사용하는 공유 메모리를 가지고 있고, 모든 프로세서들은 모든 영역에 대해서 접근할 수 있다.
예를 들어 프로세서 'A'의 메모리 영역에 프로세서 'B'가 접근하여 데이터를 가져올 수 있다. 프로세서 'B'는 바로 프로세서 'A'의 메모리 영역에 접근할 수 없고, MPI와 같은 Interface를 통해서 프로세서 'A'에 요청하여 접근할 수 있다.
MPI는 현재 Parallel Computing에서 사실상의 Standard로 사용되고 있으며, 다른 Interface보다 성능 측면에서 좋고, 확장성도 뛰어나다.
초장기 MPI는 여러 PC를 네트워크로 연결하여 통신할 수 있도록 하였고, 현재 MPI는 SMP 간에 통신을 할 수 있도록 한다.
MPI는 Virtually 동작하므로 어떠한 Hardware platform에서도 동작가능하다.
MPI는 각 프로세서가 구분된 주소 공간을 가지고, 프로세서들 간의 통신을 수행한다. 프로세서들간의 통신은 프로세서들 간의 동기화 또는 데이터 이동으로 구성된다. 데이터 이동은 Point-to-Point 통신으로 명시적으로 하나의 프로세스에서 다른 프로세스로 데이터 전송이 수행이 가능하다. 또한 Reduction 동작을 위해  Broad casting처럼 모든 프로세서들이 통신을 수행할 수 있다. 이를  Collectivie Communication이라 한다. MPI_Reduce/MPI_Bcast/MPI_Barrier로 수행가능하다. 또한 Scatter/Gather도 가능하다.
모든 프로세서가 동일한 프로그램을 수행하지만 서로 다른 데이터를 처리하는 SPMD(Single Program Multiple Data) 방식뿐만 아니라 각 프로세스가 다른 프로그램을 가지고 서로 다른 데이터를 처리하는 MPMD(Multiple Program Multiple Data)도 지원한다.
N개의 프로세서들은 0 ~ N-1의 숫자로 표현되며, Communicator를 이용하여 프로세서들 간의 통신이 이뤄진다. 예를 들어 MPI_COMM_WORLD라는 Communicator가 존재하는 데, 해당 Communicator가 포함되어 있는 프로세서들의 Rank(the specific number of a process)를 이용하여 통신을 수행할 수 있다. 같은 프로세서라도 어떤 Communicator에 포함되어 있느냐에 따라 다른 Rank 값을 가질 수 있다.
Message는 유저가 정의한 Tag를 이용하여 전송된다. 보낼 때 사용한 Tag 값을 통해서 받을 때 어떤 데이터인지를 Tag Matching을 통해 알 수 있다.
기본적으로 MPI_Send(), MPI_Recv() 함수를 통해서 메시지를 주고받을 수 있다. 해당 함수의 입력으로 buffer 주소, 데이터사이즈, 데이터 타입, 받는(Send)/보내는(Recv) 프로세스의 rank 값, Tag 값, status를 전달한다. 위 두 함수는 함수 수행에 따른 Response를 받기 전까지 계속 멈춰있는 Blocking 동작이다. MPI_Send()는 실제 받는 프로세스가 데이터를 전달받는 시점이 아니라 데이터가 현재 프로세스의 시스템에서 전송될 때까지 기다리며, MPI_Recv()는 현재 프로세스의 시스템으로부터 데이터를 받을 때까지 기다린다. 어떤 경우에는 MPI_Send()를 수행했지만, 받는 프로세스에서 데이터를 아직 못 받고 있을 수도 있다. 또한 buffering을 통해서 전송한 데이터가 buffer에 저장되어 있다가 전송될 수도 있고, 아닐 수도 있다. Standard mode인 MPI_Send()에서는 작으면 buffering을 수행하고 크면 수행하지 않고 바로 전송한다. Buffered mode인 MPI_Bsend(), No buffering mode인 MPI_Ssend() 등이 있다.
Send/Recv의 순서에 따라 deadlock이 발생할 수 있다. 예를 들어 서로의 프로세서에서 서로 같은 Tags 값을 받기를 기다리는 것이다. 이런 deadlock을 피하기 위해, send와 receive를  Non-blocking으로 구현하고, 완료를 기다리는 형태로 구현한다. MPI_Sendrecv은 send와 receive를 모두 수행하는 Call로 한 번의 호출로 받고 전송하는 걸 동시에 수행가능하다.  MPI_Sendrecv의 내부에 구현된 Send와 Recv는 서로 non-blocking으로 수행되고, 완료를 기다린다. 각 send와 receive도 non-blocking으로 수행하고 나중에 결과를 체크하면 deadlock에 빠질 염려가 없다. 또한 전송도중 다른 일을 수행할 수도 있다.
전송하거나 받는 non-blocking 함수를 MPI_Irecv(), MPI_Isend()라 하고, 결과를 기다리는 함수는 MPI_Wait()이다.
이전에 deadlock이 발생한 예제를 코드로 살펴보자
> rank 0
MPI_Recv(보내는 RANK = 1, TAG = MYTAG) -> deadlock
MPI_Send(받는 RANK = 0, TAG = MYTAG)
> rank 1
MPI_Recv(보내는 RANK = 0, TAG = MYTAG) -> deadlock
MPI_Send(받는 RANK = 1, TAG = MYTAG)
MPI_Recv를 MPI_Irecv(Non-blocking) + MPI_Wait(wait) 방식으로 아래와 같이 변경할 수 있다.
> rank 0
MPI_Irecv(보내는 RANK = 1, TAG = MYTAG)
MPI_Send(받는 RANK = 0, TAG = MYTAG)
MPI_Wait(MPI_Irecv 정보)
> rank 1
MPI_Irecv(보내는 RANK = 0, TAG = MYTAG)
MPI_Send(받는 RANK = 1, TAG = MYTAG)
MPI_Wait(MPI_Irecv 정보)
이럴 경우, MPI_Irecv는 Non-blocking이므로 다음 코드인 MPI_Send가 수행가능하다. 그러므로 deadlock을 피할 수 있다.
일반적으로 많은 MPI 함수가 존재하지만 아래 6개로 모든 구현이 가능하다.
1. MPI_INIT()
2. MPI_FINALIZE()
3. MPI_COMM_SIZE()
4. MPI_COMM_RANK()
5. MPI_SEND()
6. MPI_RECV()

마지막으로 MPI를 이용하여 원주율을 계산하는 코드를 살펴보자.
순서는 다음과 같다.
1. Master 프로세스는 얼마만큼의 간격으로 계산할 것인 지 입력을 받는다.
2. Master는 이 입력된 숫자를 다른 모든 프로세스에게 broadcast를 수행한다.
3. 각 프로세스는 각자에 맞는 영역에 대해서 계산을 수행한다.
4. 계산된 값들을 Reduction을 이용하여 합친다.

아래는 Pseudo Code이다

MPI_INIT()                -> MPI 초기화
MPI_Comm_Size() -> 총 프로세스 수 얻기
MPI_Comm_rank() -> 내 프로세스의 ID 얻기
if(id==0)                     -> Master 일 경우, 입력값을 받음.
  입력받는 코드
MPI_Bcast(입력값을 MPI_COMM_WORLD에 속한 모든 프로세스에 전달) -> master가 수행
계산 코드
MPI_Reduce(각자 계산한 값을 모음) -> 계산 값을 모음
if(id==0)                    -> Master 일 경우, 출력을 수행.
  출력
MPI_Finalize()         -> MPI 종료