c – MPI Odd-Even排序如何工作？

int MPI_OddEven_Sort(int n,double *a,int root,MPI_Comm comm)
{
    int rank,size,i,sorted_result;
    double *local_a;

// get rank and size of comm
    MPI_Comm_rank(comm,&rank); //&rank = address of rank
    MPI_Comm_size(comm,&size);

    local_a = (double *) calloc(n / size,sizeof(double));


// scatter the array a to local_a
    MPI_Scatter(a,n / size,MPI_DOUBLE,local_a,root,comm);

// sort local_a
    merge_sort(n / size,local_a);

//odd-even part
    for (i = 0; i < size; i++) {

        if ((i + rank) % 2 == 0) {  // means i and rank have same nature
            if (rank < size - 1) {
                MPI_Compare(n / size,rank,rank + 1,comm);
            }
        } else if (rank > 0) {
            MPI_Compare(n / size,rank - 1,comm);
        }

        MPI_Barrier(comm);
        // test if array is sorted
        MPI_Is_Sorted(n / size,comm,&sorted_result);

        // is sorted gives integer 0 or 1,if 0 => array is sorted
        if (sorted_result == 0) {
            break;
        }           // check for iterations
    }

// gather local_a to a
    MPI_Gather(local_a,a,comm)
    return MPI_SUCCESS;
}

这些年来,看到这些PRAM类型的分拣网络再次出现,这很有趣.这些东西的并行计算的原始心智模型是作为“比较器”的大型并行微处理器阵列,例如 Connection Machines – 当时网络与CPU / RAM相比便宜.当然,最终看起来与80年代中后期的超级计算机大不相同,甚至比90年代后期的x86集群更加不同;但现在他们开始回归流行 with GPUs和其他加速器,如果你眯着眼睛,它实际上看起来有点像未来的过去.

看起来你上面的东西更像是Baudet-Stevenson odd-even sort,它已经开始向假设处理器本地存储多个项目的方向发展,你可以通过在两者之间对这些本地列表进行排序来充分利用处理器沟通步骤.

充实代码并简化它,我们有这样的事情：

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

int merge(double *ina,int lena,double *inb,int lenb,double *out) {
    int i,j;
    int outcount=0;

    for (i=0,j=0; i<lena; i++) {
        while ((inb[j] < ina[i]) && j < lenb) {
            out[outcount++] = inb[j++];
        }
        out[outcount++] = ina[i];
    }
    while (j<lenb)
        out[outcount++] = inb[j++];

    return 0;
}

int domerge_sort(double *a,int start,int end,double *b) {
    if ((end - start) <= 1) return 0;

    int mid = (end+start)/2;
    domerge_sort(a,start,mid,b);
    domerge_sort(a,end,b);
    merge(&(a[start]),mid-start,&(a[mid]),end-mid,&(b[start]));
    for (int i=start; i<end; i++)
        a[i] = b[i];

    return 0;
}

int merge_sort(int n,double *a) {
    double b[n];
    domerge_sort(a,n,b);
    return 0;
}

void printstat(int rank,int iter,char *txt,double *la,int n) {
    printf("[%d] %s iter %d: <",txt,iter);
    for (int j=0; j<n-1; j++)
        printf("%6.3lf,",la[j]);
    printf("%6.3lf>n",la[n-1]);
}

void MPI_Pairwise_Exchange(int localn,double *locala,int sendrank,int recvrank,MPI_Comm comm) {

    /*
     * the sending rank just sends the data and waits for the results;
     * the receiving rank receives it,sorts the combined data,and returns
     * the correct half of the data.
     */
    int rank;
    double remote[localn];
    double all[2*localn];
    const int mergetag = 1;
    const int sortedtag = 2;

    MPI_Comm_rank(comm,&rank);
    if (rank == sendrank) {
        MPI_Send(locala,localn,recvrank,mergetag,MPI_COMM_WORLD);
        MPI_Recv(locala,sortedtag,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
    } else {
        MPI_Recv(remote,sendrank,MPI_STATUS_IGNORE);
        merge(locala,remote,all);

        int theirstart = 0,mystart = localn;
        if (sendrank > rank) {
            theirstart = localn;
            mystart = 0;
        }
        MPI_Send(&(all[theirstart]),MPI_COMM_WORLD);
        for (int i=mystart; i<mystart+localn; i++)
            locala[i-mystart] = all[i];
    }
}

int MPI_OddEven_Sort(int n,i;
    double *local_a;

// get rank and size of comm
    MPI_Comm_rank(comm,comm);
// sort local_a
    merge_sort(n / size,local_a);

//odd-even part
    for (i = 1; i <= size; i++) {

        printstat(rank,"before",n/size);

        if ((i + rank) % 2 == 0) {  // means i and rank have same nature
            if (rank < size - 1) {
                MPI_Pairwise_Exchange(n / size,comm);
            }
        } else if (rank > 0) {
            MPI_Pairwise_Exchange(n / size,comm);
        }

    }

    printstat(rank,i-1,"after",n/size);

// gather local_a to a
    MPI_Gather(local_a,comm);

    if (rank == root)
        printstat(rank," all done ",n);

    return MPI_SUCCESS;
}

int main(int argc,char **argv) {

    MPI_Init(&argc,&argv);

    int n = argc-1;
    double a[n];
    for (int i=0; i<n; i++)
        a[i] = atof(argv[i+1]);

    MPI_OddEven_Sort(n,MPI_COMM_WORLD);

    MPI_Finalize();

    return 0;
}

因此,这种方式的工作方式是列表在处理器之间平均分配(非均等分布也很容易处理,但这是很多额外的簿记,这对本次讨论没有太大影响).

我们首先对本地列表进行排序(即O(n / P ln n / P)).当然,没有理由它必须是合并排序,除了在这里我们可以通过以下步骤重用该合并代码.然后我们做P邻居交换步骤,每个方向一半.这里的模型是有一个线性网络,我们可以直接和快速地与直接邻居进行通信,也许根本不会与邻居相距甚远.

original odd-even sorting network是每个处理器都有一个密钥的情况,在这种情况下,通信很容易 – 您将项目与邻居进行比较,并在必要时进行交换(这样基本上是并行冒泡排序).在这种情况下,我们在成对的进程之间进行简单的并行排序 – 这里,每对只是将所有数据发送到其中一对,该对合并已经本地排序的列表O(N / P),然后给出适当的一半将数据返回给另一个处理器.我拿出你的支票 – 如果完成了;可以证明它是在P邻居交换中完成的.如果提前终止,您当然可以将其添加回来;然而,所有的处理器都必须在完成所有工作时达成一致,这需要类似于all reduce的东西,这在某种程度上打破了原始模型.

所以我们每个链路有O(n)数据传输,(每个发送和接收n / P项P次),每个处理器确实(n / P ln n / P)(2 n / P – 1)* P / 2 = O(n / P ln n / PN)比较;在这种情况下,还有一个分散和聚集也要考虑,但一般来说,这种类型是使用数据完成的.

运行上面 – 为了清楚起见,同样的例子in that document linked给出了(重新排序输出以使其更容易阅读)：

$mpirun -np 4 ./baudet-stevenson 43 54 63 28 79 81 32 47 84 17 25 49
[0] before iter 1: <43.000,54.000,63.000>
[1] before iter 1: <28.000,79.000,81.000>
[2] before iter 1: <32.000,47.000,84.000>
[3] before iter 1: <17.000,25.000,49.000>

[0] before iter 2: <43.000,63.000>
[1] before iter 2: <28.000,32.000,47.000>
[2] before iter 2: <79.000,81.000,84.000>
[3] before iter 2: <17.000,49.000>

[0] before iter 3: <28.000,43.000>
[1] before iter 3: <47.000,63.000>
[2] before iter 3: <17.000,49.000>
[3] before iter 3: <79.000,84.000>

[0] before iter 4: <28.000,43.000>
[1] before iter 4: <17.000,47.000>
[2] before iter 4: <49.000,63.000>
[3] before iter 4: <79.000,84.000>

[0] after iter 4: <17.000,28.000>
[1] after iter 4: <32.000,43.000,47.000>
[2] after iter 4: <49.000,63.000>
[3] after iter 4: <79.000,84.000>

[0]  all done  iter 5: <17.000,28.000,49.000,63.000,84.000>