首页 > 试题广场 >

如下图，有2n个节点（N[0] 到 N[2n-1]），每n

[问答题]

如下图，有2n个节点（N[0] 到 N[2n-1]），每n个节点连接在同一交换机上，两个交换机通过n/4条链路直接互联。每个节点上有一份大小为M的数据（别用M[1], M[2] … M[2n-1]表示）。请设计一种通信策略，实现每个节点拥有所有节点的数据和（M[x] = M[1] + M[2] + … M[2n-1]），并给出总耗时（假设发送一份数据的时间为t，忽略系统延时）。

刻苦的猫头鹰在打卡

针对这个问题，可以采用双重递归算法来解决，并且总共需要进行 log(2n) 轮通信，每轮通信耗时为 t。

具体实现过程如下：

1. 每个节点 N[i] （0<=i<=2n-1）都先将自己的数据 M[i] 发送给与其相连的交换机。

2. 每个交换机分别将自己所收到的 n/4 份数据累加，将结果分别发送给与其相连的另外一个交换机。

3. 利用递归的思想，将 n/2 个节点分为一组，形成一个新的全局结构，称之为“超级节点”。

4. 对于每个“超级节点”，使用双重递归算法，将其中前 n/2 个节点的数据累加得到结果 S1，将后 n/2 个节点的数据累加得到结果 S2，将 S1 和 S2 以及相应的两个交换机中的累加结果相加，得到该“超级节点”的全局数据和。

5. 重复以上过程，直到每个节点都拥有了全局数据和。

在这个算法中，每个节点需要发送和接收 2log(2n) 次数据，每次通信的时间为 t，因此总耗时为 2log(2n) x t。

发表于 2023-03-12 21:03:37 回复(0)