Basic Communication Operations（基本通信操作）

下文所讨论的所有通信操作都是使用直通路由选择而不是存储转发机制

一对多广播以及多对一规约

一对多广播：广播结束后会有p个原始数据的副本。
多对一规约：所有进程的数据通过一个相关的操作符结合起来，累加到一个目标进程中的缓冲区。

环或线性阵列

使用一种递归加倍的技术，在logp步广播完成。每一步都要仔细选择消息发送的目标节点，以免出现阻塞。

格网

行和列分别看成线性阵列

超立方体

看成一个d维的格网

平衡二叉树

每一个中间节点是开关节点。

算法实现

算法是在所有节点上跑的，通信从最高维向最低维进行。只有节点标号的i位最低有效位全为0的节点才参与第i维的通信。

成本分析

---

多对多广播和规约

多对对广播：一种执行方法是执行p个一对多广播
多对多规约：每个节点是多对一规约的目标节点

线性阵列和环

规约就是正好相反的步骤。

格网

行和列分别作为线性阵列

超立方体

需要分logP步完成（先从相邻节点最低位不同的交换，接着第二个最低位，第三个…）

成本

多对对广播中的超立方体算法不能不做修改地应用于环和格网结构，否则会引起阻塞

---

全规约与前缀和操作

全规约操作：等同于先进行一个多对一规约，再执行一个一对多广播。每个节点的缓冲区是全部p个节点的缓冲区组合得到的。使用多对多广播通信模式，可以更快完成。

将每次的消息相加而不是连接，就能得到全规约。注意每次传的消息长度并没有加倍了，是原来的大小（因为消息是相加合并了）

求前缀和：

---

散发和收集

散发：单个节点发送一个大小为m的唯一消息给每一个其他的节点。这也称为一对多私自通信。不设计任何数据复制，发送的消息是不一样的。

算法可以不做修改地应用于线性阵列和格网中。

时间复杂度

---

多对多私自通信（总体交换）

矩阵的转置 ：每一行给一个处理器管理，转置涉及到不同进程间的多对多私自通信

成本

格网

每个节点首先根据它的目标节点的列把p个消息分组。

超立方体

优化算法：E立方体路由选择
在第j次通信中，节点i和节点j异或所得节点进行通信（In the jth communication step, node i exchanges data with node (i XOR j).）保证了不拥塞，

---

循环移位

在一个p节点的总体中，节点i发送一个数据包给节点（i+q）mod p

环和双向线性阵列：移动min{q, p -q}次相邻节点之间沿一个方向的通信来实现。

格网：先沿行的方向移动（q mod 根号p），再沿列的方向移动（q / 根号p）步。对于行移动之后从高节点到低节点的，需要补一次列移动（行移动，补偿列移动，列移动）

超立方体：

提高某些通信操作的速度

单端口通信（也可以同时接收和发送数据，但是只能在一个端口上）和全端口通信