Given an array A[0..n-1], prefix sum on array A is given by array PS[0..n-1] such that PS[i]=Pi j=0 A[j]. Thus, PS[0] = A[0], PS[1] = A[0]+A[1], PS[2] = A[0]+A[1]+A[2], etc. One can find the prefix sum in parallel as follows using p processors: (i) partition the array into p subarrays, assigning processor Pi to the ith subarray, for 0 ≤ i ≤ p − 1, (ii) find local sums of individual subarrays, si , for 0 ≤ i ≤ p − 1, (iii) find prefix sums on the local sums, (iv) Pi uses the prefix sum value for the previous partition (i.e., Pi−1 j=0 sj ) to calculate the prefix sum of its own subarray. For Step (iii), one processor can do this, or all processors can replicate this process.
Given an array A[0..n-1], prefix sum on array A is given by array PS[0..n-1] such that PS[i]=Pi
j=0 A[j]. Thus, PS[0] = A[0],
PS[1] = A[0]+A[1], PS[2] = A[0]+A[1]+A[2], etc.
One can find the prefix sum in parallel as follows using p processors: (i) partition the array into p subarrays, assigning
processor Pi to the ith subarray, for 0 ≤ i ≤ p − 1, (ii) find local sums of individual subarrays, si
, for 0 ≤ i ≤ p − 1, (iii)
find prefix sums on the local sums, (iv) Pi uses the prefix sum value for the previous partition (i.e., Pi−1
j=0 sj ) to calculate
the prefix sum of its own subarray. For Step (iii), one processor can do this, or all processors can replicate this process.
Analyze the previous
range does the algorithm achieves O(p) speedup).
Step by step
Solved in 4 steps
