It seems there is quite some interest in compiling code for multi-processor machines. As a research student, I am always looking for interesting projects to do. However, I am no haskell guru and have certainly never written a compiler. All the comments so far have been very interesting, but too many go over my head and I am not gettting a coherent view of what is going on. Let me try to tie this up. The basic computational model of functional languages seems inherantly parallilisable, but there are clearly many problems - and I don't really understand them. I just picked up the book on implementing the back end of a Haskell compiler and so I will eventually get there. For the meantime, and for all the others out there in my situation, could someone who knows tell us the fundamental reason it is hard to compile Haskell for multiple processor machines - in broad strokes. Cheers, Matt
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 parallelism. 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, -- Alastair Reid
On Sat, 31 Jul 2004, Alastair Reid wrote:
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 parallelism.
How well does GPH solve the first two of these problems (I think it solves the third by asking the programmer for parallel annotations)? Also, if you use forkOS, doesn't your app inevitably distribute itself accross multiple processors if the OS runs threads that way? If the OS does run threads that way, are you saying that forkOS is *very* inefficient (or does the forkOS implementation in e.g. GHC solve the problems you describe)? -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
participants (3)
-
Alastair Reid -
Matthew Roberts -
S. Alexander Jacobson