Compress-and-Conquer for Optimal Multicore Computing

Authors:

Zhijing G. Mou, Hai Liu, and Paul Hudak

Abstract:

We propose a programming paradigm called compress-and-conquer (CC) that leads to optimal performance on multicore platforms.  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 problems, a compressed version of the same problem of size O(p) is deduced and solved (the global phase).  The solution to the original problem is then derived from the solution to the compressed problem together with the solutions of the smaller problems (the expansion phase).

The CC paradigm reduces the complexity of multicore programming by allowing the best-known sequential algorithm for a problem to be used in each of the three phases.  In this paper we apply the CC paradigm to a range of problems including scan, nested scan, difference equations, banded linear systems, and linear tridiagonal systems.  The performance of CC programs is analyzed, and their optimality and linear speedup are proven.  Characteristics of the problem space subject to CC are formally examined, and we show that its computational power subsumes that of scan, nested scan, and mapReduce.

The CC paradigm has been implemented in Haskell as a modular, 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.

Bibtex:

 @inproceedings{DivaConCore,
 author = {Mou, Zhijing G. and Liu, Hai and Hudak, Paul},
 title = {Compress-and-conquer for optimal multicore computing},
 booktitle = {Proceedings of the 5th ACM SIGPLAN workshop on 
              Declarative aspects of multicore programming},
 series = {DAMP '10},
 year = {2010},
 isbn = {978-1-60558-859-9},
 location = {Madrid, Spain},
 pages = {35--44},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {compress and conquer, divide and conquer, functional 
             programming, multicore programming, parallel computing, 
             programming paradigm, scan},
} 

Links:

DAMPFinalPaper.pdf