[MLton] parallel-runtime branch

[Eric McCorkle]

A while ago I created a branch in subversion for my ongoing work to  
implement a parallel runtime system.  The URL for this is:

mlton.org/svnroot/mlton/branches/on-20080218-parallel-runtime-branch

At this point, I've finished most of the runtime system, including  
the scheduler and garbage collector.  Because lock-free algorithms  
are notoriously difficult to test, I proved a number of correctness  
conditions about the scheduler and to a lesser extent, the garbage  
collector (this, and writing about everything accounts for most of my  
time in the month of February).  I've also transcribed Maged  
Michael's lock-free malloc, which is proven correct in his paper.  I  
need to make some changes to the garbage collector and the scheduler  
to reflect a few changes I had to make while writing the proofs, but  
this shouldn't take me too long.

I've begun to make some changes in the compiler itself (in the branch  
I created).  At this point, I'm making purely "software engineering"  
type changes to decouple the object representation from the rest of  
the compiler.  After this, I'll need to change the way headers are  
generated, get rid of stacks and weak objects, and change the  
representation of pointers.  I had to change the header format to  
support the lock-free garbage collection algorithms.  I decided to do  
weak references by clustering all weak pointers in an object after  
the "strong" pointers.  When a collector creates the replica, weak  
pointers will be set to null (0).  I'm replacing stacks with frames  
allocated in the same way objects are (they really screw up a  
parallel, particularly a lock-free approach, and they compromise  
other objectives).  Pointers will have to be represented as pairs of  
pointers.  Lastly, I'll need to add a command line option to choose  
between the original runtime and the parallel one.

The last step will be to change some of the code generation.  Any  
thread will have to know what garbage collection state the system is  
in (which side of pointer-pairs has the real value, and whether or  
not a collection is going on), safe-points will have to be changed  
(that shouldn't be too difficult actually), allocating from GC will  
be done using a memory pool (I think that may be the case already,  
but I'm not sure), and the threading interface will be different.  I  
decided that, in the end, generational collection requires a bit more  
modification to the compiler, but substantially less trouble building  
the garbage collector itself.  It also sets the stage for some nice  
things like allocating arrays and large objects in a big-object  
space, allocating objects in a permanent space, and allowing the  
garbage collector to trace through malloc-ed objects.

I'll probably report again once I'm generating object headers and  
type descriptions in the formats I need.


-- 
Eric McCorkle
Brown University
CS Graduate Student


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mlton.org/pipermail/mlton/attachments/20080304/c5cceb44/attachment-0001.html