MPI_Alltoall 能比 MPI_Alltoallv 好多少？
How much can MPI_Alltoall outperform MPI_Alltoallv?
我想知道当传输的数据量大致相同时，执行 MPI_Alltoallv 和 MPI_Alltoall 函数的 运行 时间有何不同？我找不到任何这样的基准测试结果。我对大规模实例感兴趣，其中使用了数万甚至数十万个 MPI 进程，并且这些进程对应于给定 HPC 系统的重要部分（最多考虑一些现代的，例如 BG/Q、Cray XC30、Cray XE6、...）。
概览
MPI_Alltoall 的一大优势是可以快速做出协议决策，因为它们依赖于少数标量。相比之下，如果库实现者想要优化 MPI_Alltoallv，他们必须扫描四个向量以确定通信是否接近同质、高度稀疏或其他模式。
另一个问题是 MPI_Alltoall 可以轻松地将输出缓冲区用作临时 space，因为每个进程提供和使用相同数量的数据。对于 MPI_Alltoallv，做所有的簿记是不切实际的，所以任何划痕 space 都将被分配。我不记得这个问题的细节，但我想我已经在 MPI 规范的某个地方读过它。
实施骨架
alltoallv 至少有两种特殊情况，其中一种可以比 MPI 库优化得更好：
几乎同质的通信，即计数向量几乎恒定。当您的分布式阵列未在进程网格中均匀分布时，就会发生这种情况。在这种情况下，您可以：
填充数组并直接使用 MPI_Alltoall。
对具有同构通信的进程子集使用MPI_Alltoall，对其余进程使用MPI_Alltoallv 或一批Send-Recv。如果您可以缓存关联的通信器，则效果最佳。使用非阻塞通信也应该有所帮助。
编写您自己的 Bruck 实现来处理计数变化的情况，这很可能在向量的末尾。自己没做过，不知道这个有多难，多值得。
稀疏通信，即计数向量包含大量零。对于这种情况，只需使用一批非阻塞的 Send-Recv 和 Waitall，因为这可能是 MPI 库所能做的最好的事情，而且你自己做的话可以让你根据需要调整批大小。
论文
MPI on a Million Processors 描述了与向量集合相关的可扩展性问题。诚然，您可能看不到在大多数 CPU 上扫描矢量参数的成本，但这是一个 O(n) 问题，促使实施者不要过多地接触矢量参数。
HykSort: a new variant of hypercube quicksort on distributed memory architectures 描述了一个自定义实现，其性能比优化库好得多。这种优化很难在 MPI 库内部实现，因为它可能相当专业。 （顺便说一下，这个参考是针对 Hristo 的评论，而不是你的问题。）
代码
通过比较 MPICH 中这些操作的实现，您可以发现一些有趣的事情 (https://github.com/pmodels/mpich/blob/main/src/mpi/coll/alltoall.c and https://github.com/pmodels/mpich/blob/main/src/mpi/coll/alltoallv.c). Only MPI_Alltoall uses Bruck's algorithm and pairwise exchange. Similar conclusions can be drawn from the available options for I_MPI_ADJUST_ALLTOALL and I_MPI_ADJUST_ALLTOALLV on https://software.intel.com/en-us/node/528906。这些限制是基本的还是仅仅是实用的，留给 reader 的练习。
实践经验
当MPI_Alltoall on Blue Gene/P使用DCMF_Alltoallv（source code），所以相对于MPI_Alltoallv没有区别，后者可能自从应用程序预先填充矢量参数以来，甚至更好。
我为 Blue Gene/Q 编写了一个与 MPI_Alltoall 一样快的 all-to-all exchange 版本。我的版本对于常量参数与向量参数是不可知的，所以这个结果意味着 MPI_Alltoallv 的性能与 MPI_Alltoall 类似。但是，我现在找不到代码来绝对确定细节。
然而，Blue Gene 网络相当特殊，尤其是 w.r.t。 all-to-all，所以在 CPU 比网络快得多的系统上，fat-tree 或 dragonly 网络的行为将大不相同。
我建议您编写一个基准并在您打算 运行 您的应用程序的地方对其进行测量。一旦你有了一些数据，就可以更容易地找出可能遗漏了哪些优化。
我想知道当传输的数据量大致相同时，执行 MPI_Alltoallv 和 MPI_Alltoall 函数的 运行 时间有何不同？我找不到任何这样的基准测试结果。我对大规模实例感兴趣，其中使用了数万甚至数十万个 MPI 进程，并且这些进程对应于给定 HPC 系统的重要部分（最多考虑一些现代的，例如 BG/Q、Cray XC30、Cray XE6、...）。
概览
MPI_Alltoall 的一大优势是可以快速做出协议决策，因为它们依赖于少数标量。相比之下，如果库实现者想要优化 MPI_Alltoallv，他们必须扫描四个向量以确定通信是否接近同质、高度稀疏或其他模式。
另一个问题是 MPI_Alltoall 可以轻松地将输出缓冲区用作临时 space，因为每个进程提供和使用相同数量的数据。对于 MPI_Alltoallv，做所有的簿记是不切实际的，所以任何划痕 space 都将被分配。我不记得这个问题的细节，但我想我已经在 MPI 规范的某个地方读过它。
实施骨架
alltoallv 至少有两种特殊情况，其中一种可以比 MPI 库优化得更好：
几乎同质的通信，即计数向量几乎恒定。当您的分布式阵列未在进程网格中均匀分布时，就会发生这种情况。在这种情况下，您可以：
填充数组并直接使用 MPI_Alltoall。
对具有同构通信的进程子集使用MPI_Alltoall，对其余进程使用MPI_Alltoallv 或一批Send-Recv。如果您可以缓存关联的通信器，则效果最佳。使用非阻塞通信也应该有所帮助。
编写您自己的 Bruck 实现来处理计数变化的情况，这很可能在向量的末尾。自己没做过，不知道这个有多难，多值得。
稀疏通信，即计数向量包含大量零。对于这种情况，只需使用一批非阻塞的 Send-Recv 和 Waitall，因为这可能是 MPI 库所能做的最好的事情，而且你自己做的话可以让你根据需要调整批大小。
论文
MPI on a Million Processors 描述了与向量集合相关的可扩展性问题。诚然，您可能看不到在大多数 CPU 上扫描矢量参数的成本，但这是一个 O(n) 问题，促使实施者不要过多地接触矢量参数。
HykSort: a new variant of hypercube quicksort on distributed memory architectures 描述了一个自定义实现，其性能比优化库好得多。这种优化很难在 MPI 库内部实现，因为它可能相当专业。 （顺便说一下，这个参考是针对 Hristo 的评论，而不是你的问题。）
代码
通过比较 MPICH 中这些操作的实现，您可以发现一些有趣的事情 (https://github.com/pmodels/mpich/blob/main/src/mpi/coll/alltoall.c and https://github.com/pmodels/mpich/blob/main/src/mpi/coll/alltoallv.c). Only MPI_Alltoall uses Bruck's algorithm and pairwise exchange. Similar conclusions can be drawn from the available options for I_MPI_ADJUST_ALLTOALL and I_MPI_ADJUST_ALLTOALLV on https://software.intel.com/en-us/node/528906。这些限制是基本的还是仅仅是实用的，留给 reader 的练习。
实践经验
当MPI_Alltoall on Blue Gene/P使用DCMF_Alltoallv（source code），所以相对于MPI_Alltoallv没有区别，后者可能自从应用程序预先填充矢量参数以来，甚至更好。
我为 Blue Gene/Q 编写了一个与 MPI_Alltoall 一样快的 all-to-all exchange 版本。我的版本对于常量参数与向量参数是不可知的，所以这个结果意味着 MPI_Alltoallv 的性能与 MPI_Alltoall 类似。但是，我现在找不到代码来绝对确定细节。
然而，Blue Gene 网络相当特殊，尤其是 w.r.t。 all-to-all，所以在 CPU 比网络快得多的系统上，fat-tree 或 dragonly 网络的行为将大不相同。
我建议您编写一个基准并在您打算 运行 您的应用程序的地方对其进行测量。一旦你有了一些数据，就可以更容易地找出可能遗漏了哪些优化。