How to paralellize a divide and conquer algorithm in Clojure

Question

First of all say I have a problem, calculating 1 Billion digits of Pi, calculating the factorial of a large number, or performing mergesort over a large list. I would like to divide the problem into smaller tasks and execute each of the tasks concurrently and combine the results. First of all what is the name of this type of concurrency and how would you do it in Clojure?

Answer 1

In the current Clojure 1.4, you could accomplish this using maybe pmap, pcalls, or pvalues. The pmap function is a parallel version of map, whereas pcalls and pvalues don't really have analogous non-parallel versions (although, I suppose list is a "non-parallel version" of pvalues).

However, for the problems you describe, it sounds like you would want to use a parallel version of reduce. There is an old one from Clojure 1.2 ( see here), which I've never used, so I'm not able to speak about its utility.

Coming with Clojure 1.5 will be this new "reducers" library, which Rich Hickey blogs about here. Here, fold seems to be a parallel version of reduce.