并行计算中的规约操作

以数组加为例, 有16个整数需要进行相加,那么在单核的CPU上,需要进行15次操作,而使用并行的规约操作,则可以将时间复杂度降为log(n)即4次.

其过程如下:

Step 1:

Step 2:

Step 3:

Step 4:

Result:

规约,就是将线性O(n)的过程,简化为一个log(n)的过程,除了矩阵求和之外,也可以处理求矢量分量的最大值最小值问题,是并行计算中最常用的一个操作.

发表评论

电子邮件地址不会被公开。

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>