Folding in Parallel

Summary

Parallel Fun with Monoids Playing with monoids and discovering for oneself how frequently they pop up in various guises and how much is expressed by them is a delight. Not only it brightens the day of important but frankly boring data analytics. Not only it challenges to discover efficient (with the constant time and space operation) monoids, which demands ingenuity. In the words of Guy Steele, inventing efficient associative combining operators is a very big deal. An efficient monoid opens up parallel implementations -- not just parallel but embarrassingly parallel: The input sequence arbitrarily partitioned among workers, all running in parallel with no races, dependencies or even memory bank conflicts. This is the ideal for multi-core, GPU or distributed processing. We show why monoids are a big deal, and also a big fun -- even more than expected. Horner rule and Boyer-Moore majority voting -- commonly regarded as prototypically inherently sequential -- turn out monoids, and hence embarrassingly parallelizable. As we generalize monoids to observable monoids, we discover a new, vertical way to combine them, enabling efficient iterated grouping and aggregation directly on raw deserialized (big) data, on multicore or multi-processor. Introduction: Fold v. Monoid Reduction At ICFP 2009, Guy Steele gave a keynote calling ``foldl and foldr considered slightly harmful'' and advocating (map)reduce instead. Recall, folding over a sequence is an inherently sequential stateful accumulation; using lists for concreteness, it is defined as fold_left : ('z -> 'a -> 'z) -> 'z -> 'a list -> 'z fold_right : ('a -> 'z -> 'z) -> 'a list -> 'z -> 'z Actually, there are two operations: the left and the right fold. Their meaning should be clear from the following example: fold_left (+) 0 [1;2;3;4] ≡ (((0 + 1) + 2) + 3) + 4 fold_right (+) [1;2;3;4] 0 ≡ 1 + (2 + (3 + (4 + 0))) In this case, of the folding function being addition, the results are identical: both expressions sum the list. ...