并行前缀求和的算法

本文参考Calvin Lin和Lawrence Snyder的&＃xff0c;《Principles of Parallel Programming》&＃xff08;并行程序设计原则&＃xff09;。

与求和紧密相关的操作是前缀求和&＃xff0c;在许多并行程序设计语言中也称为扫描&＃xff08;scan&＃xff09;。与求和操作一样&＃xff0c;首先仍有n个值的序列&＃xff0c;

但希望计算的是如下的序列&＃xff0c;

其中&＃xff0c;每个 yi 是输入前 i 个元素的和&＃xff0c;即有&＃xff0c;

以并行方式求解前缀和不如求累加和那样明显&＃xff08;累加和树形分层求和&＃xff0c;时间负责度为 logn&＃xff09;&＃xff0c;因为它需要顺序求解所有中间值。初看起来&＃xff0c;好像前缀求和既没有优势&＃xff0c;又不可能找到更好的解&＃xff0c;但事实上前缀求和能以并行的方式完成。

通过对成对求和方法的观察&＃xff0c;可以发现只要对该方法略加修改就可以计算前缀值。求解的思路是&＃xff0c;每个存储有 xi  的叶处理器能够计算值 yi &＃xff0c;只要它知道在它左边所有元素的和&＃xff0c;即他的前缀&＃xff0c;在成对求和的过程中&＃xff0c;我们知道所有子树的和&＃xff0c;而如果能保留这些信息&＃xff0c;就能确定这些前缀而无需直接对它们求和。为做到这一点&＃xff0c;我们从根开始&＃xff0c;它的前缀&＃xff08;即在序列元素之前的所有元素和&＃xff09;是0。这也是它的左子树的前缀&＃xff0c;而它的左子树的总和则是它的右子树的前缀。归纳地应用这一思路&＃xff0c;我们可以得到如下规则&＃xff1a;

• 首先&＃xff0c;从下往上&＃xff0c;一层层的并行&＃xff0c;计算出总和
• 结束后&＃xff0c;假想根从它的父节点&＃xff08;实际不存在&＃xff09;处接收一个 0 。
• 所有的非叶子节点&＃xff0c;从它的父节点处接收一个值&＃xff0c;将该值转发给它们的左子节点&＃xff0c;并将父节点值与它们的左子节点值&＃xff08;这些值在向上成对求和时已经得到&＃xff09;的和发送给右子节点&＃xff1b;这些值也是其子节点的前缀。
• 叶子节点将来自上面的前缀值与它所保存的输入值相加。