우와 이게 진짜 얼마만의 블로깅이냐... 작년 6월을 마지막으로 한 개도 못 올렸다. 

이유는... 나에게도 평생을 함께할 사람이 생겨서 그 준비를 좀 하느라...


아무튼 오랜만에 포스팅을 해보려고 한다. 오늘 포스팅할 내용은 HPC!! High Performance Computing이다. 고성능 컴퓨팅!! 번역하면 이렇게 되겠다. 영국 유학 중에 배웠던 데이터 마이닝 이외의 내용 중에서 가장 유용하고 잘 배웠다고 생각하는 과목이기도 했다. 그런데 이유는 모르겠지만 유학 생활 중에 이 내용을 포스팅해두지 않았었다. 그래서 지금이라도 한다.


System Programming 탭에도 성능 관련된 포스팅들이 몇 개가 있다.

http://operatingsystems.tistory.com/entry/SP-Optimizing-a-program?category=495589

http://operatingsystems.tistory.com/entry/SP-Optimizing-a-Program-with-a-hardware-dependent-perspective?category=495589


이 포스팅들은 코딩을 효율적으로 해서 프로그램의 성능을 높이는데 초점을 맞추고 있다. 즉, 어떻게 하면 레지스터로부터 바로 값을 가져오고, 캐시를 바로 사용할 수 있고, 메모리 접근을 최대한 지양하고 등등. 그런데 오늘 포스팅할 내용들은 관점을 조금 달리한다. HPC에서 성능은 어떻게 하면 한 작업을 여럿이서 수행할 수 있게 할 수 있을까? 이다. 즉 Parallel Computing(병렬 컴퓨팅)이다. Parallel Computing을 하기 위해서 보통 아래의 세가지 접근 방법을 택할 수 있다.

1. multi-thread

2. multi-process

3. GPU


multi-thread는 thread를 여러 개 생성해서 각자가 동작하는 것이고, multi-process는 프로세스를 여러 개 생성해서 각자가 동작하도록 하는 것이다. GPU는 말할 것도 없다. 여기서는 multi-process에 대해서 이야기 해보려고 한다. 그것을 할 수 있게 하는 것이 이 포스팅의 제목!! MPI(Message Passing Interface)이다.


우선, multi-thread와 multi-process의 차이를 설명하면서 왜 MESSAGE PASSING Interface인지 설명해보려고 한다. thread는 하나의 프로세스에서 생성된다. 그리고 그 프로세스에서 생성된 여러 개의 thread 끼리는 자원을 서로 공유한다. 여기서 말하는 자원은 하나의 프로세스에게 할당된 virtual memory address이다. 즉, 하나의 virtual memory address를 공유한다. 반면 multi-process는 프로세스를 여러 개 띄운다. 즉 서로 다른 프로세스가 같은 일을 하게 한다는 것이다. 쉽게 말하면, p1.c 하나, p2.c 하나, p3.c 하나, p4.c 하나를 각각 컴파일해서 p1,exe, p2.exe, p3.exe, p4.exe가 하나의 연산을 수행하도록 하는 것과 같은 개념이라는 말이다. (물론 MPI에서 서로 다른 소스코드를 작성해서 하나로 합치고 그러지는 않는다.) 여러 개의 프로세스는 완전히 서로 독립돼 있다. 마치 메모장이라는 프로그램과 크롬 브라우저가 서로 어떤 것도 공유하고 있지 않는 것처럼, 여러 개의 프로세스는 완전히 서로 독립된 프로세스이다.


'아 그럼 서로 독립된 프로세스가 같은 작업을 할 수 있게 하면 되는구나?!'


그렇다. 그런데 여기서 문제가 있다. 하나의 작업을 수행하려면 중간 연산 결과를 서로 서로 공유해야 할 때가 있다. 예를 들어, 1부터 100까지 더하는 연산을 생각해보자. 이것을 하나의 프로세스로 하면 아래와 같이 하면 된다.


그런데 여러 개의 프로세스로 하면 아래와 같이 할 수 있다.

위의 그림에서 보면 각각의 프로세스가 25개씩 부분적으로 SUM을 하고, 그 결과를 한 프로세스에 몰아준다. 즉, 프로세스끼리 연산 결과를 보내고 받는 등의 작업이 필요하다는 것이다. 이것이 MESSAGE PASSING이다. 그래서 MPI라는 것은 작업한 결과물을 다른 프로세스에게 전달할 수 있게 하는 인터페이스라는 의미이다. 


이 포스팅에서 MPI에서 사용되는 함수들의 개념과 MPI를 사용한 예제 프로그램, 그리고 그것을 이용해서 어느 정도의 성능 향상을 이뤘는지를 알아보도록 하자.


1. MPI에서 사용되는 함수들의 개념

MPI에서 사용되는 함수들이 있다. 보통 Python이든, C++이든 무슨 언어든 간에 MPI에서 지원해주는 공통적인 함수를 의미한다. 여기서는 C++을 기반으로 이야기하려고 한다. 아래의 함수는 모두 C++에서 지원하는 정확한 함수명이다. 


보통 요즘 CPU들은 4코어까지 사용할 수 있게 하므로, 4개의 프로세스를 가정하고 설명을 해보려고 한다. 그리고 각각의 프로세스를 0, 1, 2, 3 이렇게 번호로 나타내보자.


MPI_Send

int MPI_Send(

    const void *buf,                 # 보내려는 데이터의 시작 주소

    int count,                           # 보내려는 데이터의 개수

    MPI_Datatype datatype,   # 보내려는 데이터의 타입

    int dest,                             # 보내려는 프로세스의 번호(etc, 0, 1, 2, 3)

    int tag,                               # 태그

    MPI_Comm comm            # MPI handler

)

조금 더 상세하게 설명해보자. A라는 프로세스가 B라는 프로세스에 Integer 타입의 Array 10개를 보내려고 한다면, A라는 프로세스에서 그 Integer Array의 시작 주소를 우선 파라미터로 넣어야 한다. 그것이 buf이다. 그러면 그 메모리 주소에서 어떤 데이터 타입을 기준으로 몇 개를 보낼 것인지 결정해야 하는데, 그것이 각각 datatype과 count이다. dest는 보내려는 프로세스의 번호로, 0이라고 넣으면 0번 프로세스에게 보내겠다는 뜻이다. tag는 아무런 값이나 넣어도 된다. optional한 파라미터이고, 가령 Double Type에 대해서는 1, Integer Type에 대해서는 2와 같이 구분해주기 위한 태그일 뿐이고, 프로그램 동작 상에는 전혀 영향을 주지 않는다. 마지막으로 comm은 MPI Handler이고 나중에 실제 사용 예제를 통해서 더 확실하게 알아볼 수 있을 것 같다.


MPI_Recv

int MPI_Recv(

    void *buf,                         # 데이터를 받을 곳의 시작 주소

    int count,                         # 받을 데이터의 개수 

    MPI_Datatype datatype, # 받을 데이터의 타입

    int source,                       # 데이터를 받을 프로세스의 번호

    int tag,                             # 태그

    MPI_Comm comm,         # MPI handler

    MPI_Status *status         # 상태

)

다른 내용은 MPI_Send를 통해 모두 설명했고, status만 더 설명하면 될 것 같다. status는 말 그대로 상태이다. 데이터를 받아들이는데 상태를 나타낸다. 이는 MPI_Status 라는 구조체를 통해 정의되어 있는데 그 구조체는 아래와 같다.


typedef struct _MPI_Status {

    int count;

    int cancelled;

    int MPI_SOURCE;

    int MPI_TAG;

    int MPI_ERROR;

} MPI_Status, *PMPI_Status;


이것에 대한 해석은 그냥 독자에게 맞기려고 한다.


MPI_Bcast

여기서부터는 함수의 파라미터를 자세하게 설명하지 않고 동작 방식을 위주로 설명하려고 한다. 파라미터는 어짜피 MPI_Recv나 MPI_Send에서 했었던 것과 크게 다르지 않다. 여기서부터는 동작 방식이 더 중요하므로 그것에 더 초점을 맞춰보자. MPI_Bcast는 Broadcast이다. 즉, 한 프로세스가 모든 프로세스에게 값을 전달해주겠다는 뜻이다. 하나의 프로세스의 데이터를 모든 프로세스가 공유해야 할 경우 이 함수를 사용하면 된다.


MPI_Gather

Gather는 반대로 모든 프로세스로부터의 데이터를 한 프로세스가 필요로 할 때 사용한다.


MPI_Scatter

Scatter는 하나의 프로세스에서의 데이터를 다른 프로세스에 골고루 나눠줄 때 필요하다. 즉 데이터를 쪼개서 보내준다는 뜻이다. 예를 들어, 1부터 100까지 더하는 프로그램에서, 제일 처음 할 일은, 특정 프로세스가 1부터 100까지의 데이터를 만들어서 그것을 4개 단위로 쪼개서 나머지 프로세스에게 보내주는 과정이다. 이 과정을 Scatter 함수를 통해야 한다.

MPI_Allgather

각각의 프로세스의 결과를 모든 프로세스가 공유해야 할 때 사용한다. 즉, 모든 프로세스가 각각 Bcast 함수를 수행하는 것과 같다.

MPI를 이용한 예제 프로그램

아래와 같은 프로그램이 있다.



이 프로그램을 아래와 같이 바꿨다.

# MPI handler 추가


# 처리할 데이터 Scatter


# move() 함수에 대한 병렬 처리 구현


참고로 이 프로그램은 Force Directed Graph라는 알고리즘을 어떤 사람이 Python으로 구현해둔 것을 내가 C++과 MPI를 이용한 C++으로 구현해둔 것이다. 


MPI를 이용한 C++ 프로그램은 아래와 같이 컴파일하고 실행하면 된다.

# mpic++ -std=c++11 -o test spring_mpi.cpp

# mpirun -n 4 ./test



성능 향상

위 두 프로그램의 연산 결과는 정확하게 일치하는데 성능 차이는 약 3.96배(13.34초/3.3651초) 차이 난다.


Reference:

http://mpitutorial.com/tutorials/mpi-scatter-gather-and-allgather/

https://www.mpich.org/




'etc...' 카테고리의 다른 글

[Semantic Web] OWL (Web Ontology Language)  (2) 2017.02.06
[Semantic Web] RDFS  (0) 2017.02.06
[Semantic Web] Linked Data and RDF  (0) 2017.02.06
[Semantic Web] Basic of Semantic Web  (2) 2017.02.06
[Tensorflow] Multi linear Regreassion  (1) 2016.11.27
Posted by 빛나유
,