<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><BR><DIV><DIV>On Apr 19, 2007, at 8:31 PM, Suresh Jagannathan wrote:</DIV><BLOCKQUOTE type="cite"></BLOCKQUOTE><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-style-span">As Matthew rightly points out, the stabilizer implementation is easily adapted to support</SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">concurrent transactions.<SPAN class="Apple-converted-space"> </SPAN>Our current implementation provides an STM interface that</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">implements a pessimistic write/optimistic read incarnation, although we have</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">experimented in the past with an optimistic (logging) write version as well.</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>McRT papers suggest that read versioning/undo-logging is the best approach. These strategies are much better for compiler optimizations as well. The biggest problem with undo logging, however, is that you either have to do eager conflict detection on every access, or you have to somehow deal with the possibility of seeing inconsistent data (McRT opts for the former).</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>I have a list of ideas for how a compiler can do things that a library can't possibly do. To name a few: generate undo logs as actual code, rather than building a data structure (similar to implementing exceptions with continuations versus unwinding the stack), use knowledge of transaction behavior available at compile time to do things better.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>There's also several optimizations one can perform on transactions themselves (most of these require very sophisticated analysis)</DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Of course, porting this implementation to a multiprocessor/multi-core environment is</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">significantly more challenging, requiring modifying the garbage collector, atomic</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">primitives</DIV></BLOCKQUOTE></DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>The most advanced schedulers, like FreeBSD's ULE scheduler maintain a separate structure for each OS-level thread, and only communicate between schedulers to steal work. You need a barrier to make sure no one tries to steal work while legitimate scheduling is going on, but aside from that, with lock-free data structures, one could should be able to implement a scheduler with no locks at all.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>I know significantly less about garbage collectors. If I recall, cheng-blelloch (which is the only one I know anything about) claims only to need a barrier and a room, though I'm not sure.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>Modern STM systems use locks and memory allocation, and in the worst case can invoke arbitrarily complex contention managers.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>My intuition at this point would be to have the scheduler run separate from everything, the garbage collector use locks, and the TM system allocate from the heap and use locks. The sticking point for me is how to implement the scheduler. If you do it in C or something else, then communicating with SML efficiently becomes an issue. However, if you do it in SML, you have to somehow avoid allocating memory while in the scheduler context. How do you and philip deal with this, or do you organize things differently than what I'm imagining?</DIV><DIV><BR class="khtml-block-placeholder"></DIV><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><DIV><BR class="khtml-block-placeholder"></DIV><BR class="Apple-interchange-newline"></SPAN> </DIV><BR></BODY></HTML>