Chapter 7. Communicator and Topologies
Chapter 7. Communicator and Topologies
병렬 프로그램에서 프로세서간의 통신을 위해 MPI는 communicator와 topology를 지원한다.
communicator라는 것은 하나의 프로세서가 message를 send하면 그것을 receive할 수 있는
프로세서의 집합이다. Topology는 communicator에 속하는 프로세서들의 공간상 배열 형태를 정의하는 것이다.
이 장은 matrix multiplication 구현을 통해 MPI programming에서 communicator와 topology를
어떻게 이용할 수 있는지 보여 준다.
7.1 Matrix Multiplication
일반적인 matrix multiplication에서 cij는
= ai0b0j + ai1b1j + … +
ai,n-1bn-1,j -----(1)
로 표현되며 serial program은
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j];
이다. 이것을 병렬화 시키는 알고리즘은 아주 다양하며 그 중의 하나인 Fox's Algorithm을 이용하여
병렬 프로그램을 구현한다.
7.2 Fox's Algorithm
n by n matrix A, B를 곱해 n by n matrix C를 계산하는 데 n2개의 프로세서를 사용할 수 있고
프로세서 p(i,j)가 cij의 계산을 담당하고 aik, bkj의 값을 가지고
있다고 하면 (1)의 식에 의해 n 단계 뒤에 C가 계산된다.
Fox's algorithm은 여기서 각 프로세서 p(i, j)가 k-1, k, k+1 단계에서 aik, bkj를
어떤 pattern으로 요구하는 지에 주목한다.예를 들어 3 by 3 matrix A, B를 곱해 3 by 3 matrix C를
계산하는 경우를 생각해 보자.
0 단계에서 주목할 점은 p(0,*)는 a00를 동시에 사용하고, p(1,*)는 a11, p(2,*)는
a22를 동시에 사용한다.(*는 0, 1, 2) 즉, a00는 p(0,0)이 소유하고 있으므로
다른 p(0, 1), p(0,2)에게 broadcast 해주어야 하고 a11은 p(1,1)이 p(1,0)와 p(1,2)에게
broadcast해주어야 한다. 마찬가지로 p(2,2)도 p(2,0), p(2,1)에게 broadcast해준다. 1단계에서는
p(0,1)이 자신이 속한 0행에 broadcast해 주며, p(1,2)는 1행에 p(2,0)은 2행에 broadcast 해준다.
2단계에서도 각 프로세서는 자신이 속한 행에 자신이 가진 data를 broadcast 해준다.
각 프로세서가 B 행렬의 data도 일정한 pattern으로 사용한다. 그림 iii의 부분에서 각 프로세서는
열로 구분된 뒤, 각 단계에서 cycle의 형태로 위로 data를 전달하여 사용하는 것을 알 수 있다.
이런 일정한 data사용 패턴을 통해 각 프로세서가 어떤 group들에 속해야 하고 어떤 형태로 통신을
하는 지 알 수 있다. Fox’s algorithm은 전체 프로세서를 2D-grid의 형태로 배치하고 각 row
와 column별로 grouping하여 각 row별 group는 broadcasting을 통해 data를 전달하며, column별
group은 cycle의 형태로 data를 전달한다.
프로세서의 개수 p 가 n2보다 작을 경우 각 프로세서는 aij, bij대신
n/
X n/ sub matrix를 가지게 된다.
/* my process row = i, my process column = j */
q = sqrt(p);
dest = ((i-1) mod q, j);
source = ((i+1) mod q, j);
for (stage = 0; stage < q; stage++) {
k_bar = (i + stage) mod q;
Broadcast A[i, k_bar] across row i;
C[i, j] = C[i, j] + A[i, k_bar]*B[k_bar, j];
Send B[k_bar, j] to dest;
Receive B[(k_bar+1) mod q, j] from source;
}
7.3 Communicator
Communicator란 message를 주고 받을 수 있는 프로세서의 group이다. 앞의 matrix multiplication을
예로 들면, 각 row들이 하나의 communicator를 형성하고 각 column이 또 하나의 communicator를 형성한다.
하나의 프로세서는 여러 communicator에 속할 수 있다. 이 communicator는 intra-communicator와
inter-communicator의 두 가지 종류로 나뉘는 데, Intra는 communicator안에서 그 속에 속하는 프로세서들이
message를 상호 교환하는 것을 말하며, Inter는 그러한 Communicator들간의 message 상호 교환을 말한다.
Communicator는 group과 context로 결정되는 데, group은 프로세서들의 집합으로 여기에 속한 프로세서들의
몇 개가 선택되어 동일한 context를 가지게 되면 하나의 communicator를 형성하게 된다. 즉, 동일한 context를
가진 프로세서만이 상호 message교환이 가능하다.
7.4 Working with Groups, Contexts, and Communicators
Communicator를 생성하기 위해서는 먼저 Group과 Context를 생성해야 한다.
MPI_Group goup_world;
MPI_Group first_row_group;
MPI_Comm first_row_comm;
int * process_ranks;
/* 새로운 communicator에 참여할 프로세서의 list구성 */
process_ranks = (int *) malloc (q * sizeof(int));
for (proc = 0; proc < q; proc++)
process_ranks[proc] = proc; ------------------(1)
/* MPI_COMM_WORLD 를 구성하는 group을 구함 */
MPI_Comm_group(MPI_COMM_WORLD, &group_world); ------------------(2)
/* 새로운 group을 생성 */
MPI_Group_incl(group_world, q, process_ranks, &first_row_group); -----(3)
/* 새로운 communicator를 생성 */
MPI_Comm_create(MPI_COMM_WORLD, first_row_group, &first_row_comm); ---(4)
위의 code는 어떻게 새로운 communicator가 생성되는 지 보여준다. MPI병렬 프로그램은 기본적으로
MPI_COMM_WORLD라는 기본적인 communicator를 가지고 이 communicator를 다른 작은 communicator들로
분리한다. 먼저 MPI_COMM_WORLD에 속하는 프로세서 중에서 어떤 프로세서를 새로운 sub group으로
분리 시킬 지 (1)을 통해 결정한다. (2)를 통해 그 프로세서들이 속해 있는 기존 group을 알아낸다.
(3)을 통해 (1)에서 선택한 프로세서로 구성되는 새로운sub group을 형성한다. (4)를 통해 이 프로세서들이
새로운 communicator라는 것을 선언하는데 이때 이 프로세서들에게 동일한 context가 부여된다.
이런 순서로 first_row_comm이라는 새로운 communicator가 생성되었다. 이 communicator내에서는
서로간에 data를 broadcast할 수 있다. 다음은 프로세서 0이 자신이 속한 communicator에 data를
broadcast하는 예이다.
int my_rank_in_first_row;
float *A_00;
/* my_rank는 group_world에서 프로세서 rank를 의미 */
if( my_rank < q) {
MPI_Comm_rank( first_row_comm, &my_rank_in_first_row);
/* A_00를 위한 memory 할당 */
A_00 = (float *)malloc(n_bar * n_bar * sizeof(float));
if(my_rank_in_first_row == 0) {
/* Initialize A_00 */
……
MPI_Bcast(A_00, n_bar*n_bar, MPI_FLOAT, 0, first_row_comm);
}
각각의 syntax는 다음과 같다.
int MPI_Comm_group(
MPI_Comm comm /* 입력 */,
MPI_Group * group /* 출력 */ )
int MPI_Group_incl(
MPI_Group old_group /* 입력 */,
int new_group_size /* 입력 */,
int ranks_in_old_group[] /* 입력 */,
MPI_Group* new_group /* 출력 */)
int MPI_Comm_Create(
MPI_Comm old_comm /* 입력 */,
MPI_Group new_group /* 입력 */,
MPI_Comm* new_comm /* 출력 */)
7.5 MPI_Comm_split
앞 절의 방법보다 좀더 간단하게 하나의 communicator를 몇 개의 communicator로 분할 하는 방법은
MPI_Comm_split 함수를 이용하는 것이다. 이것은 key를 기준으로 같은 key를 가진 프로세서들을
하나의 communicator로 분리시켜 준다. 다음의 예는 같은 행을 동일한 key로 하여 동일 행에 있는
프로세서들을 같은 communicator로 분리하는 것이다.
MPI_Comm my_row_comm;
int my_row;
/* my_rank는 MPI_COMM_WORLD의 rank를 의미 */
/* q는 sub matrix의 행을 의미 */
my_row = my_rank / q;
MPI_Comm_split(MPI_COMM_WORLD, my_row, my_rank, &my_row_comm);
위의 함수를 통해 MPI_COMM_WORLD는 q개의 새로운 communicator들로 분리된다. 여기서 key는
my_row가 되고 자신이 어떤 communicator에 속하는지는 my_row_comm을 통해 알 수 있다.
MPI_Comm_split의 syntax는 다음과 같다.
int MPI_Comm_split(
MPI_Comm old_comm /* 입력 */,
int split_key /* 입력 */,
int rank_key /* 입력 */,
MPI_Comm* new_comm /* 출력 */)
7.6 Toplogies
Topology는 프로세서들의 공간상의 배열을 말하는 것으로 MPI에서는 Cartesian(grid)과 graph가 가능하다.
MPI는 topology는 가상의 배열을 말하는 것으로 실제 프로세서의 배열과 다를 수 있다.
Fox’s algorithm 구현을 위해 topology를 grid로 지정할 경우 고려해야 할 요소들은
1. grid의 차원 --> 2차로 지정하고
2. 각 차원의 크기를 지정 --> q행과 q열이라고 지정
3. 차원의 끝이 서로 연결(wrap around) 되었는지 아닌지를 지정
4. 실제 배열과 가상 배열을 동일하게 할 것인지 아닌지를 지정한다.
위의 4가지 조건들을 다음의 코드로 써주면 grid topology가 형성된다.
MPI_Comm grid_comm;
int dim_sizes[2];
int wrap_around[2];
int reorder = 1;
dim_sizes[0] = dim_sizes[1] = q;
wrap_around[0] = wrap_around[1] = 1;
MPI_Cart_create(MPI_COMM_WORLD, 2, dim_sizes, wrap_around, reorder, &grid_comm);
int MPI_Cart_create(
MPI_Comm old_comm /* in */,
Int number_of_dims /* in */,
Int dim_sizes[] /* in */,
Int wrap_around[] /* in */,
Int reorder /* in */,
MPI_Comm* cart_comm /* out */)
배열상의 프로세서 위치와 rank는 다음의 함수들을 통해서 알 수 있다.
int MPI_Cart_rank (
MPI_Comm comm /* in */,
int coordinates[] /* in */,
int * rank /* out */)
int MPI_Cart_coords(
MPI_Comm comm /* in */,
int rank /* in */,
int number_of_dims /* in */,
int coordinates[] /* out */)
7.7 MPI_Cart_sub
MPI_Cart_sub함수를 이용하여 grid를, 예를 들어 3차원의 grid를 2차원 grid로 2차원 grid를 1차원 grid 등,
더 낮은 차원으로 분리할 수 있다. 예를 들어 2D-grid를 row별 1-D grid로 분리하는 경우,
int free_coords[2];
MPI_Comm row_comm;
free_coords[0] = 0; /* boolean 값 */
free_coords[1] = 1;
MPI_Cart_sub(grid_comm, free_coords, &row_comm);
을 수행하면 free_coords[0]를 통해 row가 서로 다른 communicator에 속하고, free_coords[1]를 통해
column은 같은communicator에 속한다는 것을 알려 준다. 위의 예는 2D grid를 1D-row별로 분리하는 것이다.
int MPI_Cart_sub(
MPI_Comm cart_comm /* in */,
int free_coords[] /* in */,
MPI_Comm* new_comm /* out */)
7.8 Fox’s algorithm 구현
앞 절에서 소개한 여러 함수들을 토대로 7.2에서 소개한 fox’s 알고리즘을 구현했다. 먼저 topology를
grid로 설정하고 각 row별, 각 column별로 communicator를 지정한다. 그리고 알고리즘에서 기술한데로
각 프로세서들간 동작을 수행한다.
typedef struct {
int p; /* Total number of processes */
MPI_Comm comm; /*communicator for entire grid */
MPI_Comm row_comm; /* communicator for my row */
MPI_Comm col_comm; /* communicator for my col */
int q; /* order of grid */
int my_row; /* my column number */
int my_col; /* my column number */
int my_rank; /* my rank in the grid comm */
} GRID_INFO_T;
void Setup_grid(GRID_INFO_T* grid /* out */) {
int old_rank;
int dimensions[2];
int wrap_arround[2];
int coordinates[2];
int free_coords[2];
/* set up global grid information */
MPI_Comm_size(MPI_COMM_WORLD, &(grid->p));
MPI_Comm_rank(MPI_COMM_WORLD, &old_rank);
/* We assume p is a perfect square */
grid->q = (int) sqrt((double) grid->p);
dimensions[0] = dimensions[1] = grid->q;
/* We want a circular shift in second dimension */
wrap_around[0] = wrap_around[1] = 1;
MPI_Cart_create(MPI_COMM_WORLD, 2, dimensions, wrap_around, 1, &(grid->comm));
MPI_Comm_rank(grid->comm, &(grid->my_rank));
MPI_Cart_coords(grid->comm, grid->my_rank, 2, coordinates);
grid->my_row = coordinates[0];
grid->my_col = coordinates[1];
/* Set up row communicators */
free_coords[0] = 0;
free_coords[1] = 1;
MPI_Cart_sub(grid->comm, free_coords, &(grid->row_comm));
/* Setup column communicators */
free_coords[0] = 1;
free_coords[1] = 0;
MPI_Cart_sub(grid->comm, free_coords, &(grid->col_comm));
} /* Setup_grid */
void Fox(int n /* in */,
GRID_INFO_T* grid /* in */,
LOCAL_MATRIX_T* local_A /* in */,
LOCAL_MATRIX_T* local_B /* in */,
LOCAL_MATRIX_T* local_C /* out */ ) {
LOCAL_MATRIX_T * tmp_A; /* Storage for the sub matrix of A used during the current stage */
int stage;
int bcast_root;
int n_bar;
int source;
int dest;
MPI_Status status;
n_bar = n/grid->q;
Set_to_zero(local_C);
/* Calculate addresses for circular shift of B */
source = (grid->my_row + 1) % grid->q;
dest = (grid->my_row + grid->q - 1) % grid->q;
/* Set aside storage for the broadcast block of A */
tmp_A = Local_matrix_allocate(n_bar);
for(stage = 0; stage < grid->q; stage++) {
bcast_root = (grid->my_row + stage) % grid->q;
if(bcast_root == grid->my_col) {
MPI_Bcast(local_A, 1, local_matrix_mpi_t, bcas_root, grid->row_comm);
Local_matrix_multiply(local_A, local_B, local_C);
} else {
MPI_Bcast(temp_A, 1, local_matrix_mpi_t, bcast_root, grid->row_comm);
Local_matrix_multiply(temp_A, local_B, local_C);
}
MPI_Sendrecv_replace(local_B, 1, local_matrix_mpi_t, dest, 0, source, 0, grid->col_comm, &status);
} /* for */
} /* Fox */
MPI_Sendrecv_replace란 새로운 함수가 사용되었는데, 이 함수를 사용하는 프로세서의 rank가 source와
같으면, dest로 data를 send하고 dest와 같으면 source로부터 data를 receive한다.
Int MPI_Sendrecv_replace(
Void* buffer /* in./out */,
Int count /* in */,
MPI_Datatype datatype /* in */,
Int dest /* in */,
Int send_tag /* in */,
Int source /* in */,
Int recv_tag /* in */,
MPI_Comm comm /* in */,
MPI_Status* status /* out */)
7.9 요약
이 장에서는 MPI병렬 프로그램에서 프로세서들의 group화를 위한 communicator와 topology를 사용하는 방법과
그것들을 지원하는 함수들을 살펴 보았고, 그 함수들을 사용하여 fox’s algorithm을 구현해 보았다.