1. 분할정복기법을 이용한 버킷정렬(Bucket sort Using Divide and Conquer Approach)
버킷정렬은 정렬하고자 하는 숫자의 전체 범위를 알고 있을 때 사용하는 정렬 방법이다. 전체 범위를 여러 버킷으로 나누고, 배열을 읽어가며 숫자들을 해당 버킷에 넣는다. 버킷들을 독립적으로 정렬하여 순서대로 모으면 정렬이 완료된다. 순차 알고리즘의 시간 복잡도는 버킷수를 m개라 가정했을 때 O(n log(n/m))이다. 숫자들이 균등분포를 이루어 버킷으로 이동하게 되는 숫자들의 개수가 서로 비슷할 때 효율적인 정렬방법이다. 하지만 숫자들이 균등분포를 이루지 않는 경우에는 어떤 프로세스는 할일이 많아 시간이 오래걸리고, 어떤 프로세스는 할일이 적어 일이 일찍 끝날 수 있다. 따라서 프로세스 하나에 버킷 하나를 지정하는 방법보다 더 나은 것을 생각해야한다.
배열을 프로세스 개수만큼의 블록으로 나누고, 각 프로세스에게 해당배열을 전송해준다. 각 프로세스는 p개의 작은 버킷을 가지고 있어 자신에게 전송된 배열을 읽으면서 작은 버킷에 담는다. 모든 프로세스는 작은 버킷을 이동시켜 각 프로세스의 최종 큰 버킷에 쏟아준다. 각 프로세스는 자신의 버킷을 정렬하고, master는 정렬된 버킷들을 worker프로세스로부터 받아서 merge한다. 이때 집합통신이 사용되는 순서는 다음과 같다.
1) MPI_Scatter(): 같은 양의 숫자들을 모든 프로세스들한테 보낸다.
2) MPI_Alltoallv(): 모든 프로세스들은 다른 모든 프로세스들에게 작은 버킷들을 보내준다. (각 버킷에 담긴 숫자들이 개수가 다를 수 있기 때문에 alltoallv를 이용한다.)
3) MPI_Gatherv(): 각 프로세스들이 정렬한 숫자들이 프로세스 0으로 모아진다. (각 프로세스가 가지고 있는 숫자들의 개수가 서로 다를 수 있으므로 gatherv를 사용한다.)
*Synchronous computation이란?
동기화계산에서는 모든 프로세스들이 일정한 위치에서 동기화된다. 모든 프로세스들이 기다려야 하는 곳에 Barrier() 호출을 삽입하고, 모든 프로세스가 Barrier() 지점에 도착을 해야 프로세스들은 그 지점을 떠날 수 있다. 이때 barrier는 트리형태로 실행되기 때문에 log(n)의 시간이 걸린다.
-MPI_Barrier(MPI_COMM_WORLD): 커뮤니케이터 내의 모든 프로세스가 호출해야하며, 프로세스들은 모두가 도달할때까지 blocking된다.
2. 완전동기화를 이용한 선형 연립방정식의 해 구하기 (Linear Equations Using Fully Synchronous Computation)
x[i]=b[i];
for(iteration=0;iteration<limit;iteration++){
sum=-a[i][i]*x[i]
for(j=0;j<n;j++)
sum+=a[i][j]*x[j];
new_x[i]=(b[i]-sum)/a[i][i];
allgather(&new_x[i]);
global_barrier();
}위의 수도코드에서 global_barrier는 생략가능하다. allgather는 자동 동기화를 하기때문이다.
3. 부분동기화를 이용한 벽난로 문제 (Heat Distribution Problem Using Locally Synchronous Computation)
방의 초기온도와 벽난로의 온도가 주어졌을 때, 한참 후의 방안 모든 곳의 온도를 계산하는 문제이다. 각 지점의 온도는 주변 네곳 온도의 평균으로 계산된다. 프로세스 p는 담당하는 구역을 배정받은 후, 온도를 업데이트 하고 상하좌우 프로세스에게 온도를 전달한다.
각 프로세스는 for문 iteration 1회 수행후에 색칠해져 있는 부분의 갑을 이웃 프로세스들에게 전달해야한다. 또한 가장자리 셀의 온도를 갱신하기 위해서 다른 프로세스가 가지고 있는 가장자리 셀의 온도를 추가로 저장해 놓고 있어야한다. 루프 1회 실행 후 각 프로세스는 이웃 프로세스들과 MPI_Sendrecv()를 4회 실행해야한다.