MPIの各ノードのリストからグローバルtop-kを収集

Question

私はMPIインスタンスを並列に実行しています。ある時点では、すべてのインスタンスに100個のランク付けされた値のリストがあります。私は今、すべてのインスタンスから上位100の値を収集したいと思っています。

これはどのようにMPIで実行できますか？特化した機能はありますか？

ありがとうございます！

Answer 1

各インスタンスのトップ値を収集する場合は、MPI_Gather()が適切です。

すべてのインスタンスの100個の上位値（100個の上位値はn * 100個の値）を収集する場合は、それを達成するための「ネイティブ」な方法はないと思います。 /*あなたがlistを書くとき、私はあなたが二つのアレイ上で動作オペレータを作成し、事前に定義された演算子でMPI_Reduce()を呼び出すためにMPI_Op_create()を使用することができ、あなたが本当に言われていることを

*/

arrayを意味願っています。

Answer 2

ギルズの提案は非常にエレガントなものなので、私は単純なサンプルコードを書くと思います。これは、MPIを学習するユーザー定義の操作で優れた演習を行うためです。

ユーザー定義操作の引数 "len"の意味を乱用しています。これは、実行する削減の数を意味し、ではなく、それぞれの削減のサイズはです。つまり、len = 5は、各プロセスで5つの独立したリストをソートすることを意味し、各プロセスには長さが5の単一のリストを持たないことを意味します。これを修正するには、完全なリストに適した新しいMPIデータ型を定義する必要がありますMPI_Type_contiguousなど）が、私はそれを今は動作させることができません。

しかし、この技術的に間違ったコードでも、基本的なアプローチが示されています。

3つのプロセス上の長さ5のリストの出力例は次のとおりです。

rank 0, mysortedlist[0] = 12 
rank 0, mysortedlist[1] = 9 
rank 0, mysortedlist[2] = 6 
rank 0, mysortedlist[3] = 3 
rank 0, mysortedlist[4] = 0 

rank 2, mysortedlist[0] = 14 
rank 2, mysortedlist[1] = 11 
rank 2, mysortedlist[2] = 8 
rank 2, mysortedlist[3] = 5 
rank 2, mysortedlist[4] = 2 

rank 1, mysortedlist[0] = 13 
rank 1, mysortedlist[1] = 10 
rank 1, mysortedlist[2] = 7 
rank 1, mysortedlist[3] = 4 
rank 1, mysortedlist[4] = 1 

rank 0, sortedlist[0] = 14 
rank 0, sortedlist[1] = 13 
rank 0, sortedlist[2] = 12 
rank 0, sortedlist[3] = 11 
rank 0, sortedlist[4] = 10 

ここではコードです。

#include <stdio.h> 
#include <stdlib.h> 

#include <mpi.h> 

#define N 5 

void mergesortint(void *vinvec, void *vinoutvec, int *n, MPI_Datatype *type); 
void mergelist(int *merge, int *a, int *b, int n); 

int main(void) 
{ 
    int i; 

    // local sorted list 

    int mysortedlist[N]; 

    // global sorted list 

    int sortedlist[N]; 

    MPI_Comm comm; 

    MPI_Op MPI_MERGESORT; 

    // int rank, size; 

    int size, rank; 

    comm = MPI_COMM_WORLD; 

    MPI_Init(NULL, NULL); 

    MPI_Comm_size(comm, &size); 
    MPI_Comm_rank(comm, &rank); 

    // Register new reduction operation 

    MPI_Op_create(mergesortint, 1, &MPI_MERGESORT); 

    // Generate sorted lists on each rank 

    for (i=0; i < N; i++) 
    { 
     mysortedlist[i] = rank+size*(N-i-1); 
     sortedlist[i] = -1; 
    } 

    for (i=0; i < N; i++) 
    { 
     printf("rank %d, mysortedlist[%d] = %d\n", rank, i, mysortedlist[i]); 
    } 
    printf("\n"); 

    // Perform reduction to rank 0 

    MPI_Reduce(mysortedlist, sortedlist, N, MPI_INT, MPI_MERGESORT, 0, comm); 

    if (rank == 0) 
    { 
     for (i=0; i < N; i++) 
     { 
      printf("rank %d, sortedlist[%d] = %d\n", rank, i, sortedlist[i]); 
     } 
     printf("\n"); 
    } 

    MPI_Finalize(); 

    return 0; 
} 


void mergesortint(void *vinvec, void *vinoutvec, int *n, MPI_Datatype *type) 
{ 
    int i; 
    int nvec = *n; 

    int *invec = (int *) vinvec; 
    int *inoutvec = (int *) vinoutvec; 
    int *mergevec = (int *) malloc(nvec*sizeof(int)); 

    mergelist(mergevec, invec, inoutvec, nvec); 

    for (i=0; i < nvec; i++) 
    { 
     inoutvec[i] = mergevec[i]; 
    } 

    free(mergevec); 
} 


void mergelist(int *merge, int *a, int *b, int n) 
{ 
    int i, ia, ib; 

    ia = 0; 
    ib = 0; 

    for (i=0; i < n; i++) 
    { 
     if (a[ia] > b[ib]) 
     { 
      merge[i] = a[ia]; 
      ia++; 
     } 
     else 
     { 
      merge[i] = b[ib]; 
      ib++; 
     } 
    } 
} 

Answer 3

はここで完全なMPI_Reduceに「カウント」引数は（）が正しく、個々のリストの数として解釈され、複数のリストのために動作するコード、すなわちなく、各リストの長さです。リスト長Nはmainでは定数ですが、リダクション演算はより一般的であり、リスト型エクステントから長さを計算します。

ここでは4つのプロセス上の長さが5の3つのリストの出力です：

dsh@laptop> mpirun -n 4 ./mergesortlist 

rank 1, mysortedlist[0] = 17 117 217 
rank 1, mysortedlist[1] = 13 113 213 
rank 1, mysortedlist[2] = 9 109 209 
rank 1, mysortedlist[3] = 5 105 205 
rank 1, mysortedlist[4] = 1 101 201 

rank 2, mysortedlist[0] = 18 118 218 
rank 2, mysortedlist[1] = 14 114 214 
rank 2, mysortedlist[2] = 10 110 210 
rank 2, mysortedlist[3] = 6 106 206 
rank 2, mysortedlist[4] = 2 102 202 

rank 3, mysortedlist[0] = 19 119 219 
rank 3, mysortedlist[1] = 15 115 215 
rank 3, mysortedlist[2] = 11 111 211 
rank 3, mysortedlist[3] = 7 107 207 
rank 3, mysortedlist[4] = 3 103 203 

rank 0, mysortedlist[0] = 16 116 216 
rank 0, mysortedlist[1] = 12 112 212 
rank 0, mysortedlist[2] = 8 108 208 
rank 0, mysortedlist[3] = 4 104 204 
rank 0, mysortedlist[4] = 0 100 200 

rank 0, sortedlist[0] = 19 119 219 
rank 0, sortedlist[1] = 18 118 218 
rank 0, sortedlist[2] = 17 117 217 
rank 0, sortedlist[3] = 16 116 216 
rank 0, sortedlist[4] = 15 115 215 

が、ここのコードです：

#include <stdio.h> 
#include <stdlib.h> 

#include <mpi.h> 

#define NUMLIST 3 // Number of distinct lists (of integers) 
#define N 5  // Length of each list 

void mergesortlist(void *vinvec, void *vinoutvec, int *n, MPI_Datatype *type); 
void mergelist(int *merge, int *a, int *b, int n); 

int main(void) 
{ 
    int i, ilist; 

    // local sorted list 

    int mysortedlist[NUMLIST][N]; 

    // global sorted list 

    int sortedlist[NUMLIST][N]; 

    MPI_Comm comm; 

    MPI_Datatype MPI_LIST; 
    MPI_Op MPI_MERGELIST; 

    int size, rank; 

    comm = MPI_COMM_WORLD; 

    MPI_Init(NULL, NULL); 

    MPI_Comm_size(comm, &size); 
    MPI_Comm_rank(comm, &rank); 

    // Define datatype appropriate for a single array of N integers 

    MPI_Type_contiguous(N, MPI_INT, &MPI_LIST); 
    MPI_Type_commit(&MPI_LIST); 

    // Register new reduction operation to merge two sorted lists 

    MPI_Op_create(mergesortlist, 1, &MPI_MERGELIST); 

    // Generate sorted lists on each rank 

    for (i=0; i < N; i++) 
    { 
     for (ilist=0; ilist < NUMLIST; ilist++) 
     { 
     mysortedlist[ilist][i] = rank+size*(N-i-1) + 100*ilist; 
     sortedlist[ilist][i] = -1; 
     } 
    } 

    for (i=0; i < N; i++) 
    { 
    printf("rank %d, mysortedlist[%d] =", rank, i); 

    for (ilist=0; ilist < NUMLIST; ilist++) 
     { 
     printf(" %3d", mysortedlist[ilist][i]); 
     } 
    printf("\n"); 
    } 

    printf("\n"); 

    // Perform reduction to rank 0 

    MPI_Reduce(mysortedlist, sortedlist, NUMLIST, MPI_LIST, MPI_MERGELIST, 
     0, comm); 

    if (rank == 0) 
    { 
     for (i=0; i < N; i++) 
     { 
     printf("rank %d, sortedlist[%d] =", rank, i); 

     for (ilist=0; ilist < NUMLIST; ilist++) 
     { 
      printf(" %3d", sortedlist[ilist][i]); 
     } 
     printf("\n"); 
     } 

     printf("\n"); 
    } 

    MPI_Finalize(); 

    return 0; 
} 


void mergesortlist(void *vinvec, void *vinoutvec, int *n, MPI_Datatype *type) 
{ 
    MPI_Aint lb, listextent, intextent; 

    int i, ilist; 
    int nvec, nlist; 

    int *invec = (int *) vinvec; 
    int *inoutvec = (int *) vinoutvec; 

    // the count is the number of individual lists 

    nlist = *n; 

    // Infer length of each list from the extents 
    // Should really check "type" is valid, i.e. a contiguous block of ints 

    MPI_Type_get_extent(MPI_INT, &lb, &intextent); 
    MPI_Type_get_extent(*type, &lb, &listextent); 

    nvec = listextent/intextent; 

    // Need a temporary as "mergelist" does not work in-place 

    int *mergevec = (int *) malloc(nvec*sizeof(int)); 

    // Merge each of the "nlist" lists in turn 

    for (ilist=0; ilist < nlist; ilist++) 
    { 
     mergelist(mergevec, &invec[ilist*nvec], &inoutvec[ilist*nvec], nvec); 

     for (i=0; i < nvec; i++) 
     { 
     inoutvec[ilist*nvec+i] = mergevec[i]; 
     } 
    } 

    free(mergevec); 
} 


void mergelist(int *merge, int *a, int *b, int n) 
{ 
    int i, ia, ib; 

    ia = 0; 
    ib = 0; 

    for (i=0; i < n; i++) 
    { 
     if (a[ia] > b[ib]) 
     { 
      merge[i] = a[ia]; 
      ia++; 
     } 
     else 
     { 
      merge[i] = b[ib]; 
      ib++; 
     } 
    } 
}