计算前缀和
问题定义
n个元素{x1,x2,…,xn},前缀和是n个部分和:
Si=x1*x2*…*xi, 1≤i≤n 这里*可以是+或×
串行算法: Si=Si-1*xi 计算时间为 O(n)
并行算法:p154算法6.9 SIMD-TC上非递归算法
令A[i]=xi, i=1~n,
B[h,j]和C[h,j]为辅助数组(h=0~logn, j=1~n/2h)
数组B记录由叶到根正向遍历树中各结点的信息(求和)
数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)
2022-04-28 19:50:24
8.4MB
并行计算
1