Parallel Prefix-Sum and Filters

In this note, we continue our discussion of parallel algorithms. Previously, we discussed the powerful and general fork-join framework (which we can really just think of as divide-and-conquer in parallel), and discussed how it can be applied not only to our running example of list summation but also to maps and reductions in general.

There is yet another very natural type of list operation one may be interested in parallelizing that we have not yet touched on yet, and that is a filter. A filter refers to a list operation where we output a sublist of items that satisfy a certain predicate. For example, we may wish to only keep elements of our integer array that are at most 9.

So, starting with the list [2,3,12,11,87,74,8,7,9], we would like to output [2,3,8,7,9].

How might we accomplish this in parallel? In particular, what happens if we apply our fork-join framework from before?

Divide-and-Conquer Filtering Attempt

Let’s try it. Suppose our sequential cutoff is 1, and at the base case, suppose we simply appended the current element to an output list if the current element was at most 9, and otherwise did nothing.

The issue with this approach is one of concurrency, which we have not discussed so much yet. But imagine that multiple threads/processors are trying to append to the output list at the same time. This will create issues (for example, both threads may read that output is a (linked) list at the same time with last node last, and then try and append their elements by setting last.next = new Node(...) at the same time. Only one of these threads can succeed!), and is akin to multiple cooks trying to use the oven in different ways at the same time (we will see later that this would be a so-called “write-write” data race).

A Different Approach

Note that this issue would not be present if somehow, the parallel algorithm somehow knew where it should be placing a specific element in the output. For example, if we magically knew beforehand that 9 was the fifth element in the list satisfying the predicate x ≤ 9, then it could simply insert 9 at index 4 in output without any of the concurrency issues we had in the linked-list type approach.

Knowing where to put a specific element in the output list seems like a pretty daunting task. Is such a thing even possible in parallel, and how might we even start to tackle this?

Well, something that is easy in parallel using the fork-join machinery we saw earlier would be to apply a map to our input list, which applies the function

\[ f(x)= \begin{cases} 1, & x \le 9,\\ 0, & x > 9. \end{cases} \]

So, for example, applying this map to [2,3,12,11,87,74,8,7,9] results in B = [1,1,0,0,0,0,1,1,1]. A 1 in the above list at index i indicates that we should be placing input[i] somewhere in output. Recalling our goal, observe that where we should place index[i] in the output is precisely the sum(B[0:i])-1, i.e. the sum of the prefix of B up to index i, minus 1. More generally, if we could somehow, in parallel, produce the list C = [1,2,2,2,2,2,3,4,5], where C[i] is the sum of the elements of B up to index i, then computing our filter quickly in parallel would be easy.

In summary, we have reduced our task of finding where to place index[i] inside output to computing the prefix sums of a given list. Let us now discuss how to accomplish this.

Parallel Prefix Sum

In the prefix sum problem, our input is a list, and our task is to compute output where output[i] is the sum of the elements in input up to index i.

Before exhibiting an efficient parallel algorithm for our prefix sum problem, we remark that the idea that this could be done in parallel seems like a pretty magical result. Indeed, if one contemplates how to achieve this task in parallel, it is not at all obvious how to do so. Computing the prefix sums of a list seems almost inherently sequential: I need to compute the prefix sum up to i − 1 before I can compute it for index i, right? Right??? Before reading onward, it is worth it to pause here and think about this intuition, see if you agree with it, and see if you have any ideas for getting around it.

As it turns out, there is a fast parallel algorithm for this task, with some pretty clever ideas in it.

The idea behind the algorithm is to create (in parallel) a tree-like structure with nodes corresponding to sublists/subproblems of our input list that contain the following information: 1) the range = [lo, hi): this specifies the sublist, 2) sum: this specifies the sum between lo and hi, 3) LeftSum: this specifies the sum of all the elements to the left of lo. Note that this quantity is essentially what we need to compute (we just need to add in input[lo])!

parallel prefix tree

The algorithm then proceeds into two phases:

Phase 1: In this phase, we build the tree itself, and fill in the sum values. This step is not really much different than the list summing in parallel we saw previously – the only difference is we need to build the tree itself as well. Here is the pseudocode.

BuildTree(arr, lo, hi)
    1. If hi-lo < C:
        Create new TreeNode Leaf;
        Set Leaf.sum = sum(arr);
        return Leaf;
    2. Else:
        mid = (lo + hi)//2;
        in NEW THREAD : TreeNode leftChild = BuildTree(arr, lo, mid);
        in THIS THREAD : TreeNode rightChild = BuildTree(arr, mid + 1, hi) ;
    3. WAIT  for parallel computations to finish;
    4. COMBINE :
        new TreeNode parent;
        parent.sum = leftChild.sum + rightChild.sum;
        parent.left = leftChild;
        parent.right = rightChild;
    5. Return parent;

In some sense, we are building the tree from the leaves upward.

Phase 2: In the second phase, we use the sum values we have computed at each node in order to compute the leftSum values in parallel. This time, we will proceed from the root of the tree down to the leaves, which crucially allows us to use the leftSum value of the parent. Note that at the root, the leftSum will be zero.

CompleteTree(treeNode curr):
    If curr is the root: 
        set curr.leftSum = 0;
    If curr is a left child:
        Set curr.LeftSum = curr.parent.LeftSum;
    Else:
        Set curr.LeftSum = curr.parent.LeftSum + curr.sibling.Sum;
    If curr is not a leaf:
        in NEW THREAD: call CompleteTree(curr.left);
        in THIS THREAD: call CompleteTree(curr.right);
    Else (curr is a leaf):
        Set output[curr.lo] = curr.LeftSum + input[curr.lo];
        for i = curr.lo + 1 to curr.hi:
            Set output[i] = output[i-1] + input[i];

The key insights above are that if the node is a left child, then we can simply copy over the leftSum value of the parent, which we have already computed. Otherwise, if curr is a right child, then its leftSum should of course be its parent’s leftSum plus its sibling’s sum value, which we computed in the first phase.

Note that both of the phases above will take O(logn) time if we have access to infinitely many processors.

Conclusion

In this note, we discussed a very clever two-phase parallel algorithm for the prefix-sum problem. With this algorithm, we are able to compute arbitrary filters on lists quickly in parallel, wherein we are given a predicate f and tasked with removing those x in the input list such that f(x) = 0

Map/Reduce/Filter Example:

Suppose we would like to multiply together all the odd integers in a given list. We could accomplish this quickly in parallel in a couple of different ways:

  1. we could apply a map which maps all even integers to 1, and keeps all odd integers the same, and then apply a reduction that multiplies all the elements of the list together.
  2. Alternatively, we could apply a filter that removes all the even integers, and then apply a reduction that multiplies all the elements of the list together.

In general, many list operations can be written as combinations of maps/reduces/filters!