[Haskell-cafe] Multiprocessor compiling.
alastair at reid-consulting-uk.ltd.uk
Sat Jul 31 16:45:38 EDT 2004
On Saturday 31 July 2004 09:11, Matthew Roberts wrote:
> tell us the fundamental reason it is hard to compile Haskell
> for multiple processor machines - in broad strokes.
Unpredictability, heavy use of heap and overly fine granularity of inherent
Unpredictability: Haskell's laziness (also being higher order, overloaded and
polymorphic) makes it harder to predict what is related to what: if I start
to evaluate X, will I certainly/maybe evaluate Y; if X raises an exception,
is it ok for Y to raise an exception too; does X contain a pointer to Y; etc.
You can tackle this using a static analysis (e.g., strictness analysis) or
using a dynamic mechanism (e.g., revertible grey holes). Your analysis will
have to be good enough to cope with very heavy use of higher order functions
and overloading in typical Haskell code - though inlining and optimization of
overloading will eliminate a lot of these features for you.
Heavy use of heap means that any locking required to implement memory
allocation can easily be a significant overhead. In single-processor
systems, the cost of heap allocation might be 3 instructions: register add,
register compare, branch. In multi-processor systems, you probably need to
have a separate allocation arena for each processor to get close to this cost
since a single allocation arena would require locking.
Fine granularity of inherent parallelism is a problem because you really don't
want to fork 3 threads to compute "a*b + c*d" because it would probably take
10s of instructions (very optimistic minimum) to fork each thread but only 3
instructions to do the actual work. What you want to do is recognise that
the three are strongly related and do them all in the same thread.
Hope this helps,
More information about the Haskell-Cafe