All to All 广播实现和 MPI

Question

我正在学习 MPI，目前正在尝试使用发送和接收操作实现全对全广播。我知道处理器的数量将是 2 的幂，我想为这个问题实施一个有效的解决方案。我的想法如下。

all to all in a balanced binary tree with 8 processors

首先，红色副本和交换操作完成。然后应该完成绿色操作，最后，紫色操作将结束 all to all 消息共享。

假设：

处理器 0 有消息 A
处理器 1 有消息 B
处理器 2 有消息 C
处理器 3 有消息 D
处理器 4 有消息 E
处理器 5 有消息 F
处理器 6 有消息 G
处理器 7 有消息 H

部分步骤：

处理器 0 与处理器 7 共享其消息，反之亦然。所以他们都有消息A和H。
处理器 1 与处理器 6 共享其消息，反之亦然。所以他们都有消息B和G.
处理器 2 与处理器 5 共享其消息，反之亦然。所以他们都有消息C和F.
处理器 3 与处理器 4 共享其消息，反之亦然。所以他们都有消息D和E。（红色操作在这一步完成。）
处理器 0 与处理器 3 共享其消息，反之亦然。所以他们都有消息A H D和E.
处理器 1 与处理器 2 共享其消息，反之亦然。所以他们都有消息 B G C 和 F

...

鉴于当前处理器的级别，我无法编写出令人满意的代码来找出这对。我想一开始就递归地找出所有可能的对，就像要使用的查找 table 一样。但我想问一下是否有更好的方法可以继续？还有这种做法是否正确？

Answer 1

根据 Gilles Gouaillardet 的评论和我对这个问题进行的其他研究，我解决了我的问题并想分享我在这样做时使用的方法。

首先，在实施 All-to-all 广播之前，我强烈建议您看一下这个 page。因为对于我的问题，我知道处理器的数量是 2 的幂，所以我使用超立方体方法实现了算法。

procedure ALL_TO_ALL_BC_HCUBE(my_id, my_msg, d, result) 
begin 
   result := my_msg; 
   for i := 0 to d - 1 do 
       partner := my id XOR 2i; 
       send result to partner; 
       receive msg from partner; 
       result := result U msg; //U for union
   endfor; 
end ALL_TO_ALL_BC_HCUBE

算法取自提到的页面

我将我的结果与内置 MPI_Alltoall 例程进行了比较。我实现的运行时似乎比内置版本快 1.5 到 2 倍。

All to All 广播实现和 MPI

All to All broadcasting implementation and MPI

parallel-processing

mpi

distributed-computing

message-passing