Cliff Click Jr.’s Blog's Blog

Pausing Transactional Memory Hardware
August 20, 2007

One of the more exciting trends in multi-core memory is the idea of Transactional Memory: memory which commits all of it's state-changes atomically or not at all!  This idea is very powerful for coding concurrent algorithms, as it means a whole set of updates happen atomically.  Azul Systems felt this idea had so much merit that we included some Hardware Transactional Memory (HTM) support (as opposed to Software Transactional Memory) in our first generation product.

One of the issues with any TM system is livelock: transactions that continuously abort and retry (contrast this to programming with locks which suffer from deadlock).  At Azul, we use our HTM for accelerating Java locks so we can avoid avoid livelock by resorting back to the original Java locks.  However, we'd still like to profile what happens during HTM attempts!

Hardware event profiling is a common enough profiling technique; the hardware triggers an exception after every so many "events" and the exception handler records the event in memory.  "Events" can be things like every-1000-L2-misses or simply time-based or tick-based events.  The key issue is that the profiling data is recorded in memory.

Now mix profiling with HTM: the profile data is also stored in the transactional memory!  If the transaction commits then all is well.... but if it aborts then the profiling data is lost.  The CPU spent time doing work but there's no record of what work!  Where does the time go in a failed HTM attempt?    I don't know!  The hardware has helpfully onwound all that "speculative" work!  I'm back to the start of the transaction with all state reset... except for the endless march of time.

SO... what I want is a way to 'pause' transactional memory hardware - to allow memory updates to actually happen and not be queued awaiting the success or failure of the transaction.  Visible side effects inside a transaction, if you will.  Hardware which allows writes to participate in the transaction or not on a per-instruction basis would also work. 

This change (allowing some writes to succeed despite a failed transaction) does not have to destroy the notion of a 'transaction' at the higher language level - it just demonstrates the need for flexibility in any hardware TM support.

This article and the idea of 'pausing' a transaction are specifically placed in the public domain. 

Cliff

Category: Web/Tech | | TrackBack (0)

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d83451bd7669e200e54ee231b28834

Listed below are links to weblogs that reference Pausing Transactional Memory Hardware:

Comments

I think I'd call it "bypassing" the transactional interface rather than "pausing" it, but other than that minor quibble this sounds pretty useful!

Presumably if it was cheap, one could also use it to bypass HTM for local memory accesses, reducing the footprint of a transaction, and thereby the resources required to implement the system?

Posted by: Chris Purcell | Aug 21, 2007 2:09:39 AM

Guaranteed-thread-local accesses that only update 'throw-away' state? You mean like spill code from the compiler? Yup, sounds good.... although spill-code is probably fairly rare in transactions are that are small enough to reliably complete in our current HTM.

Cliff

Posted by: Cliff Click | Aug 21, 2007 7:51:46 AM

Isn't azul's speculative stores
handled via extra L1 cache states?
you're really just asking for a non-speculated
store instruction, that works normally
in terms of cache states, even in the speculative mode.

Another solution is saving it in some
alternative destination that's not
rolled back during speculative failure.
This could be a dedicated csr you don't
unroll via sw in the recovery, or
it could be a store to some kind of
I/O space register or memory.

Since you just mentioned the performance
monitoring need, it should be easy
to find some kind of I/O or csr space
destination you could use that doesn't
get unrolled on failure.

Posted by: CrazyLarry | Aug 22, 2007 6:49:43 PM

Yeah, the other obvious option is stores that skip the speculative state. The problem with using CSR's for profiling data is the finite size of such things.
Cliff

Posted by: Cliff Click | Aug 23, 2007 8:18:42 AM

Cliff -

The notion of pausing has been discussed in a number of academic papers, including ours:

Extending Hardware Transactional Memory to Support Non-busy Waiting and Non-transactional Actions (Transact 2006)

The problem seems to be how to handle the case where you perform non-transactional stores (be they in a paused region or individual "non-transaction" stores) to a block that has already been accessed by a transactional access (in particular stored to). I would guess that you could get quite a bit of mileage out of treating this condition a reason to abort the transaction, since most obvious uses can ensure that the "logging" can be performed to cache blocks that won't be transactionally accessed.

As far as avoiding transactional accesses for things like stack spills, our results suggest that this really doesn't buy you much in the context of an HTM, since the high reuse means that you don't touch many blocks.

- Craig

Posted by: Craig Zilles | Sep 14, 2007 8:56:28 AM

I'll check it out,
Thanks,
Cliff

Posted by: Cliff Click | Sep 14, 2007 10:29:10 AM

Post a comment