<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">A while ago I created a branch in subversion for my ongoing work to implement a parallel runtime system. The URL for this is:
<div><br class="webkit-block-placeholder"></div><div>mlton.org/svnroot/mlton/branches/on-20080218-parallel-runtime-branch</div><div><br class="webkit-block-placeholder"></div><div>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.</div><div><br></div><div>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.</div><div><br class="webkit-block-placeholder"></div><div>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.</div><div><br class="webkit-block-placeholder"></div><div>I'll probably report again once I'm generating object headers and type descriptions in the formats I need.</div><br><br><div> <span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div>-- </div><div>Eric McCorkle</div><div>Brown University</div><div>CS Graduate Student</div><br class="Apple-interchange-newline"></span> </div><br></body></html>