COMP526 3-7 §3.6 Parallel primitives, Prefix sum

This paragraph introduces the concept of parallel algorithmic problems, emphasizing the challenge of transitioning from simple sequential solutions to efficient parallel executions. The focus is on primitive problems that may seem artificial initially but are crucial for parallelizing efficient sorting algorithms like quicksort and merge sort. The first primitive discussed is the prefix sum, also known as cumulative sums or running totals, which involves creating an array where each element is the sum of the elements up to and including its position. The example provided illustrates the sequential approach to solving this problem, with a hint at the need for a more sophisticated method for parallel execution.

This section delves into the sequential algorithm for computing prefix sums, highlighting its efficiency and the linear time complexity. The algorithm involves a single loop that iterates through the array, accumulating the sum of previous elements to update the current position's value. The paragraph also discusses the limitations of this approach when it comes to parallelization due to data dependencies, where each step relies on the result of the previous step. A simple problem of computing the sum of an array's elements is introduced as a warm-up to the more complex prefix sum problem, with the sequential solution involving a binary addition tree that results in a logarithmic time complexity.

The paragraph discusses the challenges of parallelizing the prefix sum problem due to data dependencies and introduces the concept of using a balanced binary tree to reduce these dependencies. The parallel algorithm involves computing prefix sums in a hierarchical manner, where each level of the tree represents a parallel step. The algorithm starts with the lowest level of the tree, adding pairs of adjacent numbers, and progresses upwards, doubling the step size at each level. The goal is to achieve a parallel time complexity of logarithmic order, which is the best possible outcome given the need for n-1 additions.

This paragraph provides a detailed look at the pseudocode for the parallel prefix sum algorithm, emphasizing the importance of in-place computation and the use of parallel loops without data dependencies. The algorithm is broken down into rounds, each corresponding to a level of the binary tree, and involves reading the array, computing the new sums, and writing them back. The analysis focuses on the parallel time complexity, which is determined by the longest iteration time, and the work done, which is the total number of operations. The algorithm is found to have a logarithmic parallel time and linear work, making it efficient and scalable.

The paragraph introduces an improved parallel prefix sum algorithm that achieves linear work, making it work-efficient. The algorithm involves dividing the array into blocks of size log(n), computing local prefix sums within each block, and then using a reduced version of the inefficient algorithm to combine the block sums. The final step involves adding the previous block's sum to the current block's elements. The time complexity of the algorithm remains logarithmic, but the work is reduced to linear, which is optimal for this problem. The paragraph also touches on the application of this algorithm in compacting subsequences, a problem that arises in sorting methods.

This section explores the application of parallel prefix sums in compacting subsequences, a problem where the goal is to select and contiguously store elements from one array based on a binary indicator array. The sequential solution is straightforward, but the challenge lies in parallelizing this process. The key insight is to use prefix sums to determine the exact position in the output array for each selected element. The parallel algorithm involves two main steps: computing prefix sums in parallel and then using these sums to copy the selected elements to their correct positions in a single pass. The analysis shows that this approach achieves optimal parallel time and work complexity, making it an efficient solution for the problem.