MPI Odd-Even排序如何工作？

只是在面试之前查看一些注释，并且正在努力理解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, n / size, MPI_DOUBLE, 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  0) { MPI_Compare(n / size, local_a, rank - 1, rank, comm); } MPI_Barrier(comm); // test if array is sorted MPI_Is_Sorted(n / size, local_a, root, 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, n / size, MPI_DOUBLE, a, n / size, MPI_DOUBLE, root, comm) return MPI_SUCCESS; } 

是我为此函数编写的一些代码（不是今天也不是昨天！）。 有人可以分解它是如何工作的吗？

我正在将我的数组散布到每个处理器，它正在获取local_a的副本（其大小为n / size）

正在每个local_a上调用合并排序。

这之后发生了什么？ （假设到目前为止我是正确的！）

Answer 1

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

看起来你上面的东西更像是Baudet-Stevenson奇偶类 ，它已经开始朝着假设处理器本地存储多个项目的方向发展，你可以通过以下方式充分利用处理器在通信步骤之间对这些本地列表进行排序

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

 #include  #include  #include  int merge(double *ina, int lena, double *inb, int lenb, double *out) { int i,j; int outcount=0; for (i=0,j=0; i\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, MPI_DOUBLE, recvrank, mergetag, MPI_COMM_WORLD); MPI_Recv(locala, localn, MPI_DOUBLE, recvrank, sortedtag, MPI_COMM_WORLD, MPI_STATUS_IGNORE); } else { MPI_Recv(remote, localn, MPI_DOUBLE, sendrank, mergetag, MPI_COMM_WORLD, MPI_STATUS_IGNORE); merge(locala, localn, remote, localn, all); int theirstart = 0, mystart = localn; if (sendrank > rank) { theirstart = localn; mystart = 0; } MPI_Send(&(all[theirstart]), localn, MPI_DOUBLE, sendrank, sortedtag, MPI_COMM_WORLD); for (int i=mystart; i 0) { MPI_Pairwise_Exchange(n / size, local_a, rank - 1, rank, comm); } } printstat(rank, i-1, "after", local_a, n/size); // gather local_a to a MPI_Gather(local_a, n / size, MPI_DOUBLE, a, n / size, MPI_DOUBLE, root, comm); if (rank == root) printstat(rank, i, " all done ", a, 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 

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

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

原始奇偶排序网络是每个处理器都有一个密钥的情况，在这种情况下，通信很容易 - 您将项目与邻居进行比较，并在必要时进行交换（这样基本上是并行冒泡排序）。 在这种情况下，我们在成对进程之间进行简单的并行排序 - 这里，每对只是将所有数据发送到其中一对，该对合并已经本地排序的列表O（N / P），然后给出适当的一半将数据返回给另一个处理器。 我拿出你的支票 - 如果完成了; 可以certificate它在P邻居交换中完成。 如果提前终止，您当然可以将其添加回来; 然而，所有处理器必须在完成所有事情时达成一致，这需要像所有减少一样 ，这在一定程度上打破了原始模型。

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

运行上面的 - 为了清楚起见， 链接的那个文档中的相同示例给出了（重新排序输出以使其更容易阅读）：

 $ 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,54.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,25.000,49.000> [0] before iter 3: <28.000,32.000,43.000> [1] before iter 3: <47.000,54.000,63.000> [2] before iter 3: <17.000,25.000,49.000> [3] before iter 3: <79.000,81.000,84.000> [0] before iter 4: <28.000,32.000,43.000> [1] before iter 4: <17.000,25.000,47.000> [2] before iter 4: <49.000,54.000,63.000> [3] before iter 4: <79.000,81.000,84.000> [0] after iter 4: <17.000,25.000,28.000> [1] after iter 4: <32.000,43.000,47.000> [2] after iter 4: <49.000,54.000,63.000> [3] after iter 4: <79.000,81.000,84.000> [0] all done iter 5: <17.000,25.000,28.000,32.000,43.000,47.000,49.000,54.000,63.000,79.000,81.000,84.000>