Unbounded Transactional Memory

C. Scott Ananian, Krste Asanović,

Bradley C. Kuszmaul, Charles E. Leiserson, Sean Lie

Computer Science and Artificial Intelligence Laboratory

Massachusetts Institute of Technology

{cananian,krste,bradley,cel}@mit.edu, sean@slie.ca

Thanks to Marty Deneroff (then at SGI)

This research supported in part by a DARPA HPCS grant with SGI, DARPA/AFRL Contract F33615-00-C-1692, NSF Grants ACI-0324974 and CNS-0305606, NSF Career Grant CCR00093354, and the Singapore-MIT Alliance

Transactional Memory
(definition)

A transaction is a sequence of memory loads and stores that either commits or aborts

If a transaction commits, all the loads and stores appear to have executed atomically

If a transaction aborts, none of its stores take effect

Transaction operations aren't visible until they commit or abort

Simplified version of traditional ACID database transactions (no durability, for example)

For this talk, we assume no I/O within transactions

Locks are not our friends

void pushFlow(Vertex v1, Vertex v2, double flow) {

lock_t lock1, lock2;

if (v1.id < v2.id) { /* avoid deadlock */

lock1 = v1.lock; lock2 = v2.lock;

} else {

lock1 = v2.lock; lock2 = v1.lock;

}

lock(lock1);

lock(lock2);

if (v2.excess > f) {

/* move excess flow */

v1.excess += f;

v2.excess -= f;

}

unlock(lock2);

unlock(lock1);

}

Deadlocks/ordering

Multi-object operations

Priority inversion

Faults in critical regions

Inefficient

Invisible transactions?

Rajwar & Goodman: Speculative Lock Elision and Transactional Lock Removal

speculatively identify locks; make xactions

Martinez & Torrellas: Speculative Synchronization

guarantee fwd progress w/ non-speculative thread

Keep transactions visible

Infrequent, Small, Mostly-Serial?

To date, xactions assumed to be:

Small

BBN Pluribus (~1975): 16 clock-
cycle bus-locked “transaction”

Knight; Herlihy & Moss:
transactions which fit in cache

Infrequent

Software Transactional Memory (Shavit & Touitou; Harris & Fraser; Herlihy et al)

Mostly-serial

Transactional Coherence & Consistency (Hammond, Wong, et al)

Transact-ifying Linux

Experiment to discover xaction
properties of large real-world app.

First complete OS investigated!

User-Mode Linux 2.4.19

instrumented every load and store, all locks

locks→xactions; locks not held over I/O!

run 2-way SMP (two processes; two processors)

Two workloads

Parallel make of Linux kernel ('make linux')

dbench running three clients

Run program to get a trace; run trace through Transactional Memory simulator

1MB 4-way set-associative 64-byte-line cache

Paper also has simulation runs for SpecJVM98

TM Cache-size requirements (Linux)

# of overflowing xactions as a function of (fully-associative) cache size for make_linux & dbench

Almost all of the xactions require < 100 cache lines

99.9% need fewer than 54 cache lines

There are, however, some very large transactions!

>500k-byte fully-associative cache required

Note: log-log scale

May Be Large, Frequent, and Concurrent

Lots of small xactions

Millions of xactions in these benchmarks

Problem for software-only schemes

Significant tail: large xactions are few, but very large

Thousands of cache lines touched

Problem for bounded transactional schemes

Potential for additional concurrency

Distribution of hot cache lines suggest that 4x more concurrency may be possible on our Linux benchmarks

Programmers want unbounded xactions…

Transactional Programming

Locks: the devil we know

Complex sync techniques: library-only

Nonblocking synchronization

Bounded transactions

Compilers don't expose memory references
(Indirect dispatch, optimizations, constants)

Not portable! Changing cache-size breaks apps.

Unbounded Transactions:

Can be thought about at high-level

Match programmer's intuition about atomicity

Allow black box code to be composed safely

Promise future excitement!

Fault-tolerance / exception-handling

Speculation / search

LTM: Visible, Large, Frequent, Scalable

“Large Transactional Memory”

not truly unbounded, but simple and cheap

Minimal architectural changes, high performance

Small mods to cache and processor core

No changes to main memory, cache coherence protocols or messages

Can be pin-compatible with conventional proc

Design presented here based on SGI Origin 3000 shared-memory multi-proc

distributed memory

directory-based write-invalidate coherency protocol

Two new instructions

XBEGIN pc

Begin a new transaction. Entry point
to an abort handler specified by pc.

If transaction must fail, roll back processor and memory state to what it was when
XBEGIN was executed, and jump to pc.

Think of this as a mispredicted branch.

XEND

End the current transaction. If XEND completes, the xaction is committed and appeared atomic.

Nested transactions are subsumed into outer transaction.

Transaction Semantics

Two transactions

“A” has an abort handler at L1

“B” has an abort handler at L2

Here, very simplistic retry. Other choices!

Always need “current” and “rollback” values for both registers and memory

A

B

Handling conflicts

We need to track locations read/written by transactional and non-transactional code

When we find a conflict, transaction(s) must be aborted

We always “kill the other guy”

This leads to non-blocking systems

Restoring register state

Minimally invasive changes; build on existing rename mechanism

Both “current” and “rollback” architectural register values stored in physical registers

In conventional speculation, “rollback” values stored until the speculative instruction graduates (order 100 instrs)

Here, we keep these until the transaction commits or aborts (unbounded # of instrs)

But we only need one copy!

only one transaction in the memory system per processor

Multiple in-flight transactions

This example has two transactions, with abort handlers at L1 and L2

Assume instruction window of length 5

allows us to speculate into next transaction(s)

A

B

Instruction Window

Multiple in-flight transactions

During instruction decode:

Maintain rename table and “saved” bits

“Saved” bits track registers mentioned in current rename table

Constant # of set bits: every time a register is added to “saved” set we also remove one

graduate

decode

Multiple in-flight transactions

When XBEGIN is decoded:

Snapshots taken of current Rename table and S-bits.

This snapshot is not active until XBEGIN graduates

graduate

decode

Multiple in-flight transactions

graduate

decode

Multiple in-flight transactions

graduate

decode

Multiple in-flight transactions

When XBEGIN graduates:

Snapshot taken at decode becomes active, which will prevent P1 from being reused

1st transaction queued to become active in memory

To abort, we just restore the active snapshot's rename table

graduate

decode

active
snapshot

Multiple in-flight transactions

graduate

decode

We're only reserving registers in the active set

This implies that exactly #AR registers are saved

This number is strictly limited, even as we speculatively execute through multiple xactions

active
snapshot

Multiple in-flight transactions

graduate

decode

Normally, P1 would be freed here

Since it's in the active snapshot's “saved” set, we put it on the register reserved list instead

active
snapshot

Multiple in-flight transactions

When XEND graduates:

Reserved physical registers (P1) are freed, and active snapshot is cleared.

Store queue is empty

graduate

decode

Multiple in-flight transactions

Second transaction becomes active in memory.

graduate

decode

active
snapshot

Cache overflow mechanism

Need to keep “current” values as well as “rollback” values

Common-case is commit, so keep “current” in cache

What if uncommitted “current” values don't all fit in cache?

Use overflow hashtable as extension of cache

Avoid looking here if we can!

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Cache overflow mechanism

T bit per cache line

set if accessed during xaction

O bit per cache set

indicates set overflow

Overflow storage in physical DRAM

allocated/resized by OS

probe/miss: complexity of search ≈ page table walk

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Cache overflow mechanism

Start with non-transactional data in the cache

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Cache overflow: recording reads

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Transactional read sets the T bit.

Cache overflow: recording writes

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Most transactional writes fit in the cache.

Cache overflow: spilling

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Overflow sets O bit

New data replaces LRU

Old data spilled to DRAM

Cache overflow: miss handling

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Miss to an overflowed line checks overflow table

If found, swap overflow and cache line; proceed as hit

Else, proceed as miss.

Cache overflow: commit/abort

ST 1000, 55

XBEGIN L1

LD R1, 1000

ST 2000, 66

ST 3000, 77

LD R1, 1000

XEND

Abort:

invalidate all lines with T set

discard overflow hashtable

clear O and T bits

Commit:

write back hashtable; NACK interventions during this

clear O and T bits

Cycle-level LTM simulation

LTM implemented on top of UVSIM (itself built on RSIM)

shared-memory multiprocessor model

directory-based write-invalidate coherence

Contention behavior:

C microbenchmarks w/ inline assembly

Up to 32 processors

Overhead measurements:

Modified MIT FLEX Java compiler

Compared no-sync, spin-lock, and LTM xaction

Single-threaded, single processor

Contention behavior

Contention microbenchmark: 'Counter'

1 shared variable; each processor repeatedly adds

locking version uses global LLSC spinlock

Small xactions commit even with high contention

Spin-lock causes lots of cache interventions even when it can't be taken (standard SGI library impl)

LTM Overhead: SPECjvm98

Is this good enough?

Problems solved:

Xactions as large as physical memory

Scalable overflow and commit

Easy to implement!

Low overhead

May speed up Linux!

Open Problems...

Is “physical memory” large enough?

What about duration?

Time-slice interrupts!

Beyond LTM: UTM

We can do better!

The UTM architecture
allows transactions as large as virtual memory, of unlimited duration, which can migrate without restart

Same XBEGIN pc/XEND ISA; same register rollback mechanism

Canonical transaction info is now stored in single xstate data struct in main memory

xstate data structure

Transaction log in DRAM for each active transaction

commit record: PENDING, COMMITTED, ABORTED

vector of log entries w/ “rollback” values

each corresponds to a block in main memory

Log ptr & RW bit for each application memory block

Log ptr/next reader form linked list of all log entries for a given block

Current values

Caching in UTM

Most log entries don't need to be created

Transaction state stored in cache/overflow DRAM and monitored using cache-coherence, as in LTM

Only create transaction log when thread is descheduled, or run out of physical mem.

Can discard all log entries when xaction commits or aborts

Commit – block left in X state in cache

Abort – use old value in main memory

In-cache representation need not match xstate representation

Performance/Limits of UTM

Limits:

More-complicated implementation

Best way to create xstate from LTM state?

Performance impact of swapping.

When should we abort rather than swap?

Benefits:

Unlimited footprint

Unlimited duration

Migration and paging possible

Performance may be as fast as LTM in the common case

Conclusions

First look at xaction properties of Linux:

99.9% of xactions touch ≤ 54 cache lines

but may touch > 8000 cache lines

4x concurrency?

Unbounded, scalable, and efficient Transactional Memory systems can be built.

Support large, frequent, and concurrent xactions

What could software for these look like?

Allow programmers to (finally!) use our parallel systems!

Two implementable architectures:

LTM: easy to realize, almost unbounded

UTM: truly unbounded

Open questions

I/O interface?

Transaction ordering?

Sequential threads provide inherent ordering

Programming model?

Conflict resolution strategies

Graveyard of Unused slides

Outline

What's Transactional Memory good for?

Why don't we have it yet?

The promise of unbounded transactions

Two implementations of unbounded transactional memory

LTM

UTM

Evaluation

Conclusion

Why Transactions?

Concurrency control

Locking discliplines are awkward, error-prone, and limit concurrency

Especially with multiple objects!

Nonblocking transaction primitives can express optimistic concurrency more simply

Focus on “performance” instead of “correctness”

Fault-tolerance

Locks are irreversible; semantics for exceptions/crashes unclear

Also: “priority inversion”

Programming languages in general are irreversible

Transactions allow clean “undo”

Non-blocking synchronization

Although transactions can be implemented with mutual exclusion (locks), we are interested only in non-blocking implementations.

In a non-blocking implementation, the failure of one process cannot prevent other processes from making progress. This leads to:

Scalable parallelism

Fault-tolerance

Safety: freedom from some problems which require careful bookkeeping with locks, including priority inversion and deadlocks

Little known requirement: limits on trans. suicide

Transactional Memory Systems

Hardware Transactional Memory (HTM)

Knight, Herlihy & Moss, BBN Pluribus

atomicity through architectural means

Software Transactional Memory (STM)

atomicity through languages, compiler, libraries

Traditionally assume:

Transactions are “small” and thus it is reasonable to bound their size (esp. HTM)

Transactions are “infrequent” and thus overhead is acceptable (esp. STM)

Transaction Size Distribution

Lots of small xactions

Millions of xactions in these benchmarks

Use hardware support to make these fast

Significant tail: large xactions are few, but very large

Thousands of cache lines touched

Unbounded Transactional Memory makes these possible

Free the compiler/programmer/ISA from arbitrary limits on transaction size

Our Thesis

Transactional memory should support transactions of arbitrary size and duration. Such support should be provided with hardware assistance, and it should be made visible to the software through the machine's instruction-set architecture (ISA).

An unbounded TM can handle transactions of arbitrary duration with footprints comparable to its virtual memory space

LTM implementation, cont.

Info about pending transactions stored in the cache

No special fully-associative cache needed

Main memory contains “committed” data

Conflicts among pending transactions detected using existing cache-coherency mechanisms

Request from another proc for cache line with transactional data indicates conflict

Overflow mechanism allows large transactions to spill from the cache into main memory

LTM pipeline modifications

Register snapshot stored with rename mechanism

Limited # of regs reserved even if multiple xactions are in-flight

Architectural changes are kept small

LTM cache modifications

O bit per cache set

indicates if set has overflowed

T bit per cache line

set if accessed during current transaction

Overflow storage in uncached DRAM

maintained by hardware

OS sets size/location via OBR, etc

xstate data structure

Xaction log for each active transaction

commit record: PENDING, COMMITTED, ABORTED

vector of log entries w/ “old” values

each corresponds to a block in main memory

Log ptr and RW bit for each memory block

linked list of entries for each block

xstate data structure

Xaction log for each
active transaction

commit record: PENDING, COMMITTED, ABORTED

vector of log entries w/ “rollback” values

each corresponds to a block in main memory

Log ptr and RW bit for each memory block

Log ptr/next reader form linked list of all log entries for a given block

Current values

SPECjvm98 LTM benchmarks

Compiled three versions of each benchmark using modified FLEX compiler

Base with no synchronization

Locks with spinlocks

Trans with LTM xactions for synchronization

Run on one processor of UVSIM

Looking at overhead, not contention

Hardware/Software Implementation

Hardware transaction implementation is very fast! But it is limited:

Slow once you exceed Cache capacity

Transaction lifetime limits (context switches)

Limited semantic flexibility (nesting, etc)

Software transaction implementation is unlimited and very flexible!

But transactions may be slow

Solution: failover from hardware to software

Simplest mechanism: after first hardware abort, execute transaction in software

Need to ensure that the two algorithms play nicely with each other (consistent views)

Overcoming HW size limitations

Simple node-push benchmark

As xaction size increases, we eventually run out of cache space in the HW transaction scheme

HTM Transactions stop fitting after this point

Overcoming HW size limitations

Simple node-push benchmark

Hybrid scheme best of both worlds!

Conventional Locking: Ordering

When more than one object is involved in a critical region, deadlocks may occur!

Thread 1 grabs A then tries to grab B

Thread 2 grabs B then tries to grab A

No progress possible!

Solution: all locks ordered

A before B

Thread 1 grabs A then B

Thread 2 grabs A then B

No deadlock

Conventional Locking: Ordering

Maintaining lock order is a lot of work!

Programmer must choose, document, and rigorously adhere to a global locking protocol for each object type

development overhead!

All symmetric locked objects must include lock order field, which must be assigned uniquely

space overhead!

Every multi-object lock operation must include proper conditionals

which lock do I take first? which do I take next?

execution-time overhead!

No exceptions!

Multi-object atomic update

Programmer's mental model of locks can be faulty

Monitor synchronization: associates locks with objects

Promises modularity: locking code stays with encapsulated object implementation

Often breaks down for multiple-object scenarios

End result: unreliable software, broken modularity

A problem with multiple objects

public final class StringBuffer ... {

private char value[ ];

private int count;

...

public synchronized StringBuffer append(StringBuffer sb) {

...

A:int len = sb.length();

int newcount = count + len;

if (newcount > value.length)

expandCapacity(newcount);

// next statement may use state len

B:sb.getChars(0, len, value, count);

count = newcount;

return this;

}

public synchronized int length() { return count; }

public synchronized void getChars(...) { ... }

}

Fault-tolerance

Locks are irreversible

When a thread fails holding a lock, the system will crash

it's only a matter of time before someone else attempts to grab that lock

What are the proper semantics for exceptions thrown within a critical region?

data structure consistency not guaranteed

Asynchronous exceptions?

Priority Inversion

Well-known problem with locks

Described by Lampson/Redell in 1980 (Mesa)

Mars Pathfinder in 1997, etc, etc, etc

Low-priority task takes a lock needed by a high-priority task -> the high priority task must wait!

Clumsy solution: the low priority task must become high priority

What if the low priority task takes a long time?

Related Work

HTM work

Knight, Herlihy&Moss, BBN Pluribus

Oklahoma Update (Stone et al)

Speculative Lock Elision/Transactional Lock Removal (Rajwar & Goodman)

Use “locks” as the API, dynamically translate to transactional regions

Speculative Synchronization (Martinez & Torrellas)

Speculatively execute locking code

TM Coherency and Consistency (Hammond et al)

Relies on broadcast for large transactions

Software Transactional Memory

Harris&Fraser, Shavit&Touitou, Herlihy et al

Conclusions

Transactional Memory systems should support unbounded transactions in hardware

Both fully-scalable (UTM) and easily-implemented (LTM) systems are possible

Big step towards making parallel computing practical and ubiquitous!

Title, we're all at MIT CSAIL. My advisor is Martin Rinard. Acknowledge Marty Deneroff.

I'm the software guy, and it's okay...

Real colloration: Sean Lie did the hardware design and simulations, I did the compiler support, and Krste, Charles and Bradley cracked the whips. Bradley did the linux study.

Emphasize “disparate memory locations” when presenting this.

Emphasize “visible to other threads or processors”

Take the time to explain this.

c-ize; expose unlock.

Stop sign on top.

Keep transactions visible: makes programming easier.

Existing work on transactional memory has assumed they were infrequent, small, and mostly-serial.

I was looking for raisins in my breakfast this morning, and found the same thing.

Convert the existing locks to transactions.

Stress the log-log scale.

Are lots of small xactions

But also some large transactions

They commit in parallel

This focuses on existing applications. What do we want for new systems?

It turns out that programmer really want unbounded transactions...

I'm a software guy; I know you don't want to rely on how many memory ops are in your code.

“Old” == committed, and “new” == speculative

Missing: multiple transactions can commit in parallel? [Earlier slide]

Multiple XBEGIN/XENDs decoded speculatively in the processor; only one active at a given time. Corrolary: only #AR addition registers need to be saved.

Only one copy of the code, step down it with decode and graduate pointers.

S bits get set and cleared. S bits are simply registered mentioned in rename table; always exactly 32 of them.

Mention or show abort.

Describe arrow, and renaming.

Hopefully by this point i've already talked about how locks are converted to transactions. 'synchronized' keyword.

Each memory block (and on disk when paging). Implicit log ptr per entry.

RW bit – R=all transactions did read, W=some may have written.

When a processor in a transaction reads or writes a block, log pointer made to point to transaction log entry and RW set.

If already part of transaction, look at RW bit and log pointer to determine what to do.

Change the commit record to commit; clean up by clearing the log pointers

BASED ON SOFTWARE TM but in hw

Doesn't have to match xstate, but it must be createable. Still can be done in hardware.

OPTIONAL

Locking: deadlock, pressimitic

Non-blocking synchronization, mutual exclusion w/o locks. Perform better (optimistic), but programming is even more error-prone! Library limits generality.

Once you have transactions, you can use them to add fault tolerance and other cool things.

Puts some limits on how you handle conflict resolution: obviously if a particular transaction always aborts when faced with a conflict, it might never make progress and thus block its task.

Tom Knight (1986), H/M (1992), Pluribus1972-1975

Each memory block (and on disk when paging)

RW bit – R=all transactions did read, W=some may have written.

When a processor in a transaction reads or writes a block, log pointer made to point to transaction log entry and RW set.

If already part of transaction, look at RW bit and log pointer to determine what to do.

Change the commit record to commit; clean up by clearing the log pointers

BASED ON SOFTWARE TM but in hw

Each memory block (and on disk when paging). Implicit log ptr per entry.

RW bit – R=all transactions did read, W=some may have written.

When a processor in a transaction reads or writes a block, log pointer made to point to transaction log entry and RW set.

If already part of transaction, look at RW bit and log pointer to determine what to do.

Change the commit record to commit; clean up by clearing the log pointers

BASED ON SOFTWARE TM but in hw

Unbounded Transactional Memory

HPCA 2005 talk

transactional memory UTM LTM transactions

2005-02-04T11:58:22