计算前缀和 问题定义 n个元素{区1，X2,…x},前缀和是n个部分和： S=x1*x2*.*x,1≤i≤n这里*可以是十或X *串行算法：S=S-x 计算时间为On) *并行算法：SMD-TC上非递归算法 令A0=x,i=1~n, Bh,j1和Ch,i]为辅助数组h=0~logn,jF1~n/2) 数组B记录由叶到根正向遍历树中各结，点的信息（求和） 数组C记录由根到叶反向遍历树中各结，点的信息（播送前 缀和) 2011/9/27 5计算前缀和  问题定义 n个元素{x1,x2,…,xn}，前缀和是n个部分和： Si=x1*x2*…*xi, 1≤i≤n 这里*可以是＋或×  串行算法： Si=Si－1*xi 计算时间为 O(n)  并行算法：SIMD-TC上非递归算法 令A[i]=xi, i=1~n, B[h,j]和C[h,j]为辅助数组(h=0~logn, j=1~n/2h) 数组B记录由叶到根正向遍历树中各结点的信息(求和) 数组C记录由根到叶反向遍历树中各结点的信息(播送前 缀和) 5 2011/9/27