banner above paper title Compress-and-Conquer for Optimal Multicore Computing ∗

We propose a multicore programming paradigm called compress-and-conquer (CC) that can be applied to a fairly broad range of problems with optimal performance. Given a multicore system of p cores and a problem of size n, the problem is first reduced to p smaller problems, each of which can be solved independently of the others (the compression phase). From the solutions to the p prob-lems, a compressed version of the same problem of size O(p) is deduced and solved (the global phase). The solution to the orig-inal problem is then derived from the solution to the compressed problem together with the solutions of the smaller problems (the expansion phase). There are several advantages of the CC paradigm. First, it re-duces the complexity of multicore programming by allowing the best-known conventional algorithm for a problem to be used in each of the three phases. Second, it delivers programs with asymp-totically optimal communication and operation-count complexity, with speedup linear in the number of cores. Third, the expressive-ness and computational power of CC subsumes that of mapReduce and scan. Finally, it can be applied to a wide range of problems, including scan, nested scan, second-order linear difference equa-tions, banded linear systems, linear difference equations, and linear tridiagonal systems. CC is not without limitations, however, and therefore the class of problems that can be solved by CC is care-fully examined and identified. The CC paradigm has been implemented in Haskell as a mod-ular, higher-order function, whose constituent functions can be shared by seemingly unrelated problems. This function is compiled into low-level Haskell threads that run on a multicore machine, and performance benchmarks confirm the theoretical analysis