A RISC Approach to Transactional Instructions

This is a different approach, taking a more low-level, RISC-based approach. Ultimately, we'd like either instructions or intrinsics that help us implement a transactions using whatever strategy we'd like, and do so efficiently, with the ability to optimize away much of the cost.

As an analogy, look at early CPU research, which was concerned with the "semantic gap". This produced instruction sets like VAX, which were a nightmare to implement in silicon, and had the effect of forcing compilers to follow very specific idioms (and generally were very difficult to optimize in any meaningful way). For a modern example, look at JVM. It was built to map directly from Java expressions, and it's been a tragedy of errors ever since. Then along came the RISC idea: present instructions that can be implemented efficiently in silicon, and semantic gaps are good: they give you space in which to optimize.

So in transactional memory, what does this equate to? Throw out begin/end transaction, specialized styles of nesting, commit handlers, abort, and all that and start over. What do I end up implementing when I do a pure STM system? Logging/watching and commit/rollback, and validation. I use some combination of these depending on exactly what strategy I'm employing (write-locking vs read-validation, lazy vs eager conflict detection, write-buffering vs undo-logging).

Going down the list we need a way to say "watch for activity on this location(s)", as well as a way to say "notify people of activity on this location(s)", and a way to say "make sure no one has conflicted with my watched set". In terms of actually doing things, we need a way to say "buffer this write" or "log the previous value", as well as a way to say "roll back/perform this action(s)" And lastly, we need the ability to discard watched locations.

I present the following:

watch (r | w), %ptr*

Add %ptr to the watch set, alerting on read or write.

touch (r | w), %ptr*

Notify watchers of activity on %ptr.

discard (r | w), %ptr*

Stop watching activity on %ptr.

validate (r | w), [%ptr*]

Check for conflicts on all watched locations, or just %ptr.

log (undo/redo), %ptr, [%val]

Log activity on %ptr, either saving the old value at %ptr or logging a write of %val.

commit [%ptr*]

Perform all buffered actions, or just those on %ptr.

rollback [%ptr*]

Rollback all buffered actions, or just those on %ptr.

Perhaps commit and rollback should be combined into a flush instruction. This isn't finished yet, except I don't quite like this since they do opposing things. We need specific watch-sets and logs so we can do nesting. We also need the ability to store logging information in SSA values, so the illustrious flatten can squish it out of the logs, as I describe in earlier posts. The watch-sets would also give a straightforward implementation of retry functionality (perhaps we want a modified halt instruction).

But this gives you the flexibility without forcing you into a particular regime. It also (hopefully) gives you the space to optimize.