多线程归约和前缀计算) 一个数组x[1.. n]的
归约(-reduction)就是y= x[1]x[2]...x[n]的值，其中是一个结合操作符。
下面的程序串行计算了子数组x[i..n ]的归约:
a. 应用嵌套并行实现-个多线程算法P-REDUCE,以工作量为
另一个相关问题是，在数组x[1..n].上求解一个
也就是说，使用操作符的数组x的所有前缀“和”。下面的串行SCAN过程计算了一个前缀:
遗憾的是，多线程SCAN不是直接可以得到的。例如，改for循环为parallelfor循环会产生竞争，因为循环体的每一步迭代都依赖前一个迭代。下面的P-SCAN-1过程实现了前缀计算的并行，尽管十分低效:
b.分析P- SCAN-1过程的工作量、持续时间和并行度。使用嵌套并行能得到一个更有效的前缀计算，其过程如下:
c.论证P-SCAN-2是正确的，并分析它的工作量、持续时间和并行度。我们可以通过在数据上执行两趟不同的区前缀计算来改进P SCAN-1和P-SCAN-2。第一趟，收集不同的连续子数组x的“和”项，存人到一个临时数组t中;第二趟，使用t中的“和”项来计算出最终的结果y。下面的伪代码实现了这种策略，但其中省去了一些表示：
d.对P-SCAN-UP第8行、P-SCAN-DOWN第5行和第6行中的三个缺省表示进行填空。填完空后，论证P-SCAN-3是正确的。(提示:证明值v传给P SCAN-DWON(v, x, t,y, i, j)，满足=x[1]x[2]...x[i- 1].)
e分析P-SCAN-3的工作量、持续时间和并行度。
