[MLton] More on parallelism

[Eric McCorkle]

On Dec 5, 2006, at 11:34 AM, Matthew Fluet wrote:

> I don't think that it is as bad as you fear.  It also really  
> depends on your application scenario.  CML encourages _lots_ of  
> threads and can support them by having a very lightweight  
> representation of a suspended ML execution.
>

That is the chief argument for M:N.  And in this case, it may be  
enough to justify the model.  M:N tends to have these problems:

- Priority inversion.  In 1:1, the kernel knows who's waiting on  
whom.  In M:N, this information must be relayed up somehow, or else  
the threads package must compensate.
- Dealing with blocked OS-level threads.
- Balancing the number of user threads to OS threads.

A good paper to read about this sort of thing would be the Psyche  
paper ("First-class user level threads").

The best approach may actually be to allow the API to create both  
user and system level threads.  Someone working on a parallel  
algorithm would prefer to grab a set number of OS threads and work  
from there.  Someone taking a smaller-scale parallel approach would  
rather spawn threads to call functions and let the scheduler sort it  
out.

> Well, a MLton thread (whether in the single-threaded or multi- 
> threaded case) never uses the C stack except for making FFI calls.   
> The entire state of the ML thread is stored on the ML heap.
>

I was thinking about what happens if a thread gets suspended in mid- 
FFI call.  That would have to be dealt with.  Also, the case of SML  
calling C, calling SML and so on is troublesome.

I thought about this more, though, and it's not as bad as I thought.   
I'd say lazily allocate a C stack per MLton thread and switch  
stacks.  There'd be some politics involved, but not too bad.

-- 
Eric McCorkle,
Brown University
CS Graduate Student