Software Transactional Memory

As I men­tioned a few weeks ago, I’m writ­ing my master’s the­sis on soft­ware trans­ac­tional mem­ory (STM).

Of course it is still early in the process, and while I’ve got some ideas for my imple­men­ta­tion, and have started pro­to­typ­ing parts of it, most of the time has been spent catch­ing up on all the exist­ing work in the field.

Lit­tle did I know when I accepted the sub­ject that there’d been writ­ten that many papers about it over the last decade. Phew… A com­menter asked me for the ref­er­ences I found use­ful, so here’s an incom­plete list:

Tran­ac­tional Mem­ory Bib­li­og­ra­phy: This site con­tains an up-to-date and extremely com­pre­hen­sive list of ref­er­ences to every­thing writ­ten aobut STM. Just the sheer num­ber of links out from that site is depress­ing, but it’s obvi­ously a won­der­ful place to get an overview of what’s available.

Trans­ac­tional Mem­ory: I bought this book after notic­ing that almost every paper on STM ref­er­enced it. And it was money well spent. The book is well writ­ten, explains the sub­ject clearly, and cov­ers pretty much every­thing I wanted to know. It is split into three main chap­ters (not count­ing the introduction):

The first chap­ter dis­cusses TM purely from a user’s per­spec­tive. What should the API look like, what do we, as pro­gram­mers want or need from a TM imple­men­ta­tion, what should the seman­tics be, and what exten­sions might be use­ful? It explains a num­ber of impor­tant con­cepts, such as weak/strong iso­la­tion, seri­al­iz­abil­ity and lin­eariz­abil­ity, direct and deferred update and many oth­ers. But mostly, this chap­ter is fan­tas­tic as a dis­cus­sion of what TM research should aim towards. With­out get­ting bogged down in imple­men­ta­tion details, it focuses sim­ply on how we’d like it to work (and on the many open ques­tions where we still don’t know which seman­tics would make sense or be most useful).

The sec­ond chap­ter is use­ful as a short­cut, allow­ing new­com­ers such as me to catch up on the last decade’s research. It sum­ma­rizes all the impor­tant papers on STM, from the ear­li­est pre­cur­sors dat­ing back to the 70’s, up to 2006 when the book was pub­lished. The var­i­ous imple­men­ta­tions and results are briefly described, in enough detail for me to under­stand the main ideas pre­sented, and deter­mine whether to look up the paper in ques­tion and read it in full.

The third chap­ter gives a sim­i­lar treat­ment to Hard­ware Trans­ac­tional Mem­ory, and since that is out­side the scope of my project, I’ve skipped lightly over this for now, although I may just read it out of curios­ity later on. In short, it’s a great book for any­one try­ing to find their way in the jun­gle of TM papers.

Haskell STM: Simon Pey­ton Jones and oth­ers at Microsoft Research have done some truly impres­sive work on a STM imple­men­ta­tion for Con­cur­rent Haskell. While those of us work­ing in a messy lan­guage like C++ can’t aspire for such a clean and ele­gant imple­men­ta­tion, there are still many good ideas we can borrow.

And finally, a few indi­vid­ual papers I’ve got­ten a lot out of:

Soft­ware Trans­ac­tional Mem­ory Should Not be Obstruction-Free: As STM grew out of research into lock-free datas­truc­tures and dis­trib­uted sys­tems, the early work was down­right obsessed about mak­ing trans­ac­tions non­block­ing. It took this paper to take a step back and ask whether this require­ment actu­ally makes sense for the rest of us. And guess what? It doesn’t. It com­pli­cates the STM imple­men­ta­tions, and pre­vents some very use­ful optimizations.

What Really Makes Trans­ac­tions Faster fol­lowed up on the above, dis­cussing a num­ber of other ways in which the per­for­mance of STM sys­tems could be improved.

And finally, the ear­lier the­sis that drew me into the subject:

A Soft­ware Trans­ac­tional Mem­ory Library for C++: This is the first imple­men­ta­tion I’ve seen which seri­ously tar­gets C++. Of course many prior C++ imple­men­ta­tions exist, but they’ve gen­er­ally relied on either C or Java idioms, result­ing in an uglier, more error-prone inter­face, and the inabil­ity to per­form a num­ber of opti­miza­tions. This paper describes a proper mod­ern C++ imple­men­ta­tion, rely­ing on generic pro­gram­ming, tem­plate metapro­gram­ming and all the other tricks in a C++ programmer’s toolbox.

Tags: diku, stm, thesis, transactional-memory

Programming | RSS 2.0 | Respond | Trackback |