[Haskell-cafe] Automatic parallelism in Haskell, similar to "make -j4"?

[Austin Seipp]

Excerpts from t.r.willingham's message of Sun Nov 02 17:28:08 -0600 2008:
> What would it take to implement a -j equivalent for, say, GHC?  Or if
> this is not possible, what is wrong with my reasoning?
> 
> Thanks,
> TW

Hi,

The main issue has to do with the decisions the compiler needs to make
in order to generate adequate code for a general case. The problem is
the compiler has to make decisions about the *granularity* of the
threading in particular - the generated code for example may waste a
lot of time sparking off threads using 'par' or something, for
computations that take less time than the thread-creation itself,
meaning the overall cost of that thread being spawned was negative. So
your code would need the threading to be more coarse-grained. On the
other hand, if you have some computation, the compiler may not
adequately sprinkle enough par's throughout the program, and therefore
we miss opportunities where the parallelism could give us a speed up -
in this case, we need more fine-grained threading.

So the problem is (in the general case): given an arbitrary input
program, how do you adequately decide what should and should not be
parallelized in that program? Even then, how do you decide the
granularity at which the threads should operate?

It's a pretty tough problem, and I don't think we're even close to
full-blown automagically-parallelizing compilers (although with things
like parallel strategies and DPH we can get close.) But there is work
in this area using profiling information to guide these optimizations,
see "Feedback directed implicit parallelism" here:

http://research.microsoft.com/~tharris/papers/2007-fdip.pdf

Austin