Transactional Memory
Transactional Memory Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: A A A A A
Our Vision for the Future
2 Our Vision for the Future In this course, we covered …. Best practices … New and clever ideas … And common-sense observations. Art of Multiprocessor Programming
Our Vision for the Future
3 Our Vision for the Future In this course, we covered …. Best practices … New and clever ideas … And common-sense observations. Nevertheless … Concurrent programming is still too hard … Here we explore why this is …. And what we can do about it. Art of Multiprocessor Programming
Locking
4 Locking Art of Multiprocessor Programming
Coarse-Grained Locking
5 Coarse-Grained Locking Easily made correct … But not scalable. Art of Multiprocessor Programming
Fine-Grained Locking
6 Fine-Grained Locking Can be tricky … Art of Multiprocessor Programming
Locks are not Robust
7 Locks are not Robust If a thread holding a lock is delayed … No one else can make progress Art of Multiprocessor Programming
Locking Relies on Conventions
Locking Relies on Conventions Relation between Lock bit and object bits Exists only in programmer’s mind /* * When a locked buffer is visible to the I/O layer * BH_Launder is set. This means before unlocking * we must clear BH_Launder,mb() on alpha and then * clear BH_Lock, so no reader can see BH_Launder set * on an unlocked buffer and then risk to deadlock. */ Actual comment from Linux Kernel (hat tip: Bradley Kuszmaul) Art of Multiprocessor Programming
Simple Problems are hard
9 Simple Problems are hard enq(x) enq(y) double-ended queue No interference if ends “far apart” Interference OK if queue is small Clean solution is publishable result: [Michael & Scott PODC 97] Art of Multiprocessor Programming
Locks Not Composable
Art of Multiprocessor Programming 10 Locks Not Composable Transfer item from one queue to another Must be atomic : No duplicate or missing items
Locks Not Composable
Art of Multiprocessor Programming 11 Locks Not Composable Lock source Lock target Unlock source & target
Locks Not Composable
Art of Multiprocessor Programming 12 Locks Not Composable Lock source Lock target Unlock source & target Methods cannot provide internal synchronization Objects must expose locking protocols to clients Clients must devise and follow protocols Abstraction broken!
Monitor Wait and Signal
13 Monitor Wait and Signal zzz Empty buffer Yes! Art of Multiprocessor Programming If buffer is empty, wait for item to show up
Wait and Signal do not Compose
14 Wait and Signal do not Compose empty empty zzz… Art of Multiprocessor Programming Wait for either?
The Transactional Manifesto
Art of Multiprocessor Programming 15 15 The Transactional Manifesto Current practice inadequate to meet the multicore challenge Research Agenda Replace locking with a transactional API Design languages or libraries Implement efficient run-times
Transactions
Art of Multiprocessor Programming 16 16 Transactions Block of code …. Atomic : appears to happen instantaneously Serializable : all appear to happen in one-at-a-time order Commit : takes effect (atomically) Abort : has no effect (typically restarted)
Atomic Blocks
Art of Multiprocessor Programming 17 17 atomic { x.remove(3); y.add(3); } atomic { y = null ; } Atomic Blocks
Atomic Blocks
Art of Multiprocessor Programming 18 18 atomic { x.remove(3); y.add(3); } atomic { y = null ; } Atomic Blocks No data race
A Double-Ended Queue
Art of Multiprocessor Programming 19 19 public void LeftEnq(item x) { Qnode q = new Qnode(x); q.left = this .left; this .left.right = q; this .left = q; } A Double-Ended Queue Write sequential Code
A Double-Ended Queue
Art of Multiprocessor Programming 20 20 public void LeftEnq(item x) atomic { Qnode q = new Qnode(x); q.left = this .left; this .left.right = q; this .left = q; } } A Double-Ended Queue
A Double-Ended Queue
Art of Multiprocessor Programming 21 21 public void LeftEnq(item x) { atomic { Qnode q = new Qnode(x); q.left = this.left; this.left.right = q; this.left = q; } } A Double-Ended Queue Enclose in atomic block
Warning
Art of Multiprocessor Programming 22 22 Warning Not always this simple Conditional waits Enhanced concurrency Complex patterns But often it is…
Composition?
Art of Multiprocessor Programming 23 Composition?
Composition?
Art of Multiprocessor Programming 24 Composition? public void Transfer(Queue<T> q1, q2) { atomic { T x = q1.deq(); q2.enq(x); } } Trivial or what?
Conditional Waiting
Art of Multiprocessor Programming 25 25 public T LeftDeq() { atomic { if ( this .left == null ) retry ; } } Conditional Waiting Roll back transaction and restart when something changes
Composable Conditional Waiting
Art of Multiprocessor Programming 26 26 Composable Conditional Waiting atomic { x = q1.deq(); } orElse { x = q2.deq(); } Run 1 st method. If it retries … Run 2 nd method. If it retries … Entire statement retries
Hardware Transactional Memory
Art of Multiprocessor Programming 27 27 Hardware Transactional Memory Exploit Cache coherence Already almost does it Invalidation Consistency checking Speculative execution Branch prediction = optimistic synch!
HW Transactional Memory
Art of Multiprocessor Programming 28 28 HW Transactional Memory Interconnect caches memory read active T
Transactional Memory
Art of Multiprocessor Programming 29 29 Transactional Memory read active T T active caches memory
Transactional Memory
Art of Multiprocessor Programming 30 30 Transactional Memory active T T active committed caches memory
Transactional Memory
Art of Multiprocessor Programming 31 31 Transactional Memory write active committed T D caches memory
Rewind
Art of Multiprocessor Programming 32 32 Rewind active T T active write aborted D caches memory
Transaction Commit
Art of Multiprocessor Programming 33 33 Transaction Commit At commit point If no cache conflicts, we win. Mark transactional entries Read-only: valid Modified: dirty (eventually written back) That’s all, folks! Except for a few details …
Not all Skittles and Beer
Art of Multiprocessor Programming 34 34 Not all Skittles and Beer Limits to Transactional cache size Scheduling quantum Transaction cannot commit if it is Too big Too slow Actual limits platform-dependent
HTM Strengths & Weaknesses
HTM Strengths & Weaknesses Ideal for lock-free data structures
HTM Strengths & Weaknesses
HTM Strengths & Weaknesses Ideal for lock-free data structures Practical proposals have limits on Transaction size and length Bounded HW resources Guarantees vs best-effort
HTM Strengths & Weaknesses
HTM Strengths & Weaknesses Ideal for lock-free data structures Practical proposals have limits on Transaction size and length Bounded HW resources Guarantees vs best-effort On fail Diagnostics essential Retry in software?
Composition