從MPI中的每個節點列表中收集全局top-k

Question

我正在並行運行MPI實例。在某些時候，每個實例都有一個100個排名值的列表。我現在想收集所有實例中的前100個值。

這怎麼能在MPI中完成？有專門的功能嗎？

謝謝！

Answer 1

如果你想收集每個實例的最高值，那麼MPI_Gather()是正確的選擇。

如果你想收集所有實例的100個最高值（例如100個最高值不超過100個值），那麼我不認爲有一個「本地」的方式來實現這一目標。 /*當你寫list，我希望你的真正用意array */

這樣說，你可以以創建在兩個數組起作用的操作，然後與預先定義的操作調用MPI_Reduce()使用MPI_Op_create()。

Answer 2

吉爾的建議是一個非常優雅的一個，所以我想我會寫一個簡單的例子代碼，這將使用戶定義操作的極好的鍛鍊對於那些學習MPI。

請注意，我濫用了用戶定義操作的「len」參數的含義。這意味着要減少的數量和不是每個減少的規模。換句話說，LEN = 5應該意味着要對每個進程5對獨立的列表進行排序，而不是每個進程都有長度爲5的一個列表要解決這個問題就需要定義一個完整的列表中的新數據類型的MPI適當（例如MPI_Type_contiguous），但我現在無法正常工作。

但是，即使是這種技術上不正確的代碼也說明了基本方法。

示例輸出用於長度爲5的列表上3個過程是：

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是主一個常數，歸約運算是更一般的，並計算從該列表類型程度的長度。

這裏有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++; 
     } 
    } 
}