Foundations of Shared Memory
Foundations of Shared Memory Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit Art of Multiprocessor Programming
Last Lecture
2 Last Lecture • Defined concurrent objects using linearizability and sequential consistency • Fact : implemented linearizable objects (Two thread FIFO Queue) in read-write memory without mutual exclusion • Fact : hardware does not provide linearizable read-write memory Art of Multiprocessor Programming
Fundamentals
3 Fundamentals • What is the weakest form of communication that supports mutual exclusion? • What is the weakest shared object that allows shared-memory computation? Art of Multiprocessor Programming
Alan Turing
4 Alan Turing • Showed what is and is not computable on a sequential machine. • Still best model there is. Art of Multiprocessor Programming
5 Turing Computability • Mathematical model of computation • What is (and is not) computable • Efficiency (mostly) irrelevant 0 1 1 0 1 0 1 Art of Multiprocessor Programming
6 Shared-Memory Computability? • Mathematical model of concurrent computation • What is (and is not) concurrently computable • Efficiency (mostly) irrelevant 10011 Shared Memory Art of Multiprocessor Programming
Foundations of Shared Memory
7 Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions … Art of Multiprocessor Programming
Foundations of Shared Memory
8 Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions … What is the weakest useful form of shared memory? Art of Multiprocessor Programming
Foundations of Shared Memory
9 Foundations of Shared Memory To understand modern multiprocessors we need to ask some basic questions … What is the weakest useful form of shared memory? What can it do? Art of Multiprocessor Programming
Register*
10 Register* 10011 Holds a (binary) value * A memory location: name is historical Art of Multiprocessor Programming
Register
11 Register Can be read 10011 Art of Multiprocessor Programming 10011
Register
10011 12 Register Can be written 01100 Art of Multiprocessor Programming
Registers
13 public interface Register<T> { public T read(); public void write(T v); } Registers Art of Multiprocessor Programming
Registers
14 public interface Register <T> { public T read(); public void write( T v ); } Registers Type of register (usually Boolean or m -bit Integer) Art of Multiprocessor Programming
Single-Reader/Single-Writer Register
10011 15 Single-Reader/Single-Writer Register 01100 10011 Art of Multiprocessor Programming
Multi-Reader/Single-Writer Register
16 Multi-Reader/Single-Writer Register 10011 Art of Multiprocessor Programming 10011 01100
Multi-Reader/Multi-Writer Register
10011 17 mumble mumble 11011 Multi-Reader/Multi-Writer Register mumble 10011 10011 01010 Art of Multiprocessor Programming
Jargon Watch
18 Jargon Watch • SRSW – Single-reader single-writer • MRSW – Multi-reader single-writer • MRMW – Multi-reader multi-writer Art of Multiprocessor Programming
Safe Register
19 Safe Register write( 1001 ) read( 1001 ) OK if reads and writes don’t overlap Art of Multiprocessor Programming
Safe Register
20 Safe Register write( 1001 ) Some valid value if reads and writes do overlap read( ???? ) 0000 1001 1111 $*&v Art of Multiprocessor Programming
Regular Register
21 Regular Register write( 0 ) read( 1 ) write( 1 ) read( 0 ) • Single Writer • Readers return: – Old value if no overlap ( safe ) – Old or one of new values if overlap Art of Multiprocessor Programming
Regular or Not?
22 Regular or Not? write( 0 ) read( 1 ) write( 1 ) read( 0 ) Art of Multiprocessor Programming
Regular or Not?
23 Regular or Not? write( 0 ) read( 1 ) write( 1 ) read(0) Overlap: returns new value Art of Multiprocessor Programming
Regular or Not?
24 Regular or Not? write( 0 ) write( 1 ) read( 0 ) Overlap: returns old value Art of Multiprocessor Programming
Regular or Not?
25 Regular or Not? write( 0 ) read( 1 ) write( 1 ) read( 0 ) regular Art of Multiprocessor Programming
Regular ≠ Linearizable
26 Regular ≠ Linearizable write( 0 ) read( 1 ) write( 1 ) read( 0 ) write(1) already happened can’t explain this! Art of Multiprocessor Programming
Atomic Register
27 Atomic Register write( 1001 ) read( 1001 ) Linearizable to sequential safe register write( 1010 ) read( 1010 ) read( 1010 ) Art of Multiprocessor Programming
Atomic Register
28 Atomic Register write(1001) read(1001) write(1010) read(1010) read(1010) Art of Multiprocessor Programming
Register Space
29 Register Space MRMW MRSW SRSW Safe Regular Atomic m -valued Boolean Art of Multiprocessor Programming
Weakest Register
30 Weakest Register 1 0 1 Single reader Single writer Safe Boolean register Art of Multiprocessor Programming
Weakest Register
31 Weakest Register Single reader Single writer Get correct reading if not during state transition flipflop 0 1 0 0 1 0 Art of Multiprocessor Programming
Results
32 Results • From SRSW safe Boolean register – All the other registers – Mutual exclusion • But not everything! – Consensus hierarchy Foundations of the field The really cool stuff … Art of Multiprocessor Programming
Locking within Registers
33 Locking within Registers • Not interesting to rely on mutual exclusion in register constructions • We want registers to implement mutual exclusion! • It’s cheating to use mutual exclusion to implement itself! Art of Multiprocessor Programming
Definition
34 Definition An object implementation is wait-free if every method call completes in a finite number of steps No mutual exclusion – Thread could halt in critical section – Build mutual exclusion from registers Art of Multiprocessor Programming
From Safe SRSW Boolean to Atomic Snapshots
Art of Multiprocessor Programming 35 From Safe SRSW Boolean to Atomic Snapshots MRMW MRSW SRSW Saf e Regular Atomic M-valued Boolean Snapshot
Road Map
36 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Art of Multiprocessor Programming
Road Map
37 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Next Art of Multiprocessor Programming
Register Names
38 public class SafeBoolMRSWRegister implements Register< Boolean > { public boolean read() { … } public void write( boolean x) { … } } Register Names Art of Multiprocessor Programming
Register Names
39 public class SafeBoolMRSWRegister implements Register<Boolean> { public boolean read() { … } public void write(boolean x) { … } } Register Names property Art of Multiprocessor Programming
Register Names
40 public class SafeBoolMRSWRegister implements Register<Boolean> { public boolean read() { … } public void write(boolean x) { … } } Register Names property type Art of Multiprocessor Programming
Register Names
41 public class SafeBoolMRSWRegister implements Register<Boolean> { public boolean read() { … } public void write(boolean x) { … } } (3) Register Names property type how many readers & writers? Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
42 Safe Boolean MR SW from Safe Boolean SR SW 0 0 0 0 0 0 0 0 0 0 0 zzz readers writer Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
43 Safe Boolean MRSW from Safe Boolean SRSW 0 0 0 0 0 0 0 0 0 0 0 Let’s write 1! Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
44 Safe Boolean MRSW from Safe Boolean SRSW 0 or 1 1 0 0 0 0 0 0 0 0 0 Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
45 Safe Boolean MRSW from Safe Boolean SRSW 1 0 or 1 1 0 0 0 0 0 0 0 1 Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
46 Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 0 or 1 0 0 0 0 0 1 Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
47 Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 1 1 1 1 1 1 Whew! Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
48 Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements Register<Boolean> { private SafeBoolSRSWRegister[] r = new SafeBoolSRSWRegister[N]; public void write( boolean x) { for ( int j = 0; j < N; j++) r[j].write(x); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
49 Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r = new SafeBoolSRSWRegister[N]; public void write(boolean x) { for (int j = 0; j < N; j++) r[j].write(x); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} Each thread has own safe SRSW register Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
50 Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r = new SafeBoolSRSWRegister[N]; public void write( boolean x) { for (int j = 0; j < N; j++) r[j].write(x); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} write method Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
51 Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r = new SafeBoolSRSWRegister[N]; public void write(boolean x) { for ( int j = 0; j < N; j++) r[j].write(x); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} Write each thread’s register one at a time Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
52 Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r = new SafeBoolSRSWRegister[N]; public void write(boolean x) { for (int j = 0; j < N; j++) r[j].write(x); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} read method Art of Multiprocessor Programming
Safe Boolean MRSW from Safe Boolean SRSW
53 Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister { private SafeBoolSRSWRegister[] r = new SafeBoolSRSWRegister[N]; public void write(boolean x) { for (int j = 0; j < N; j++) r[j].write(x); } public boolean read() { int i = ThreadID.get(); return r[i].read(); }} Read my own register Art of Multiprocessor Programming
Safe Multi-Valued MRSW from Safe Multi-Valued SRSW?
54 1000 1000 1000 Safe Multi-Valued MRSW from Safe Multi-Valued SRSW? 1011 1011 1011 any value in range 1000 1000 Yes, it works! 1011 Art of Multiprocessor Programming
Road Map
55 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
56 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Next Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
57 Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 1 0 1 1 1 Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
58 Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0 1 1 1 Art of Multiprocessor Programming Uh, oh!
Regular Boolean MRSW from Safe Boolean MRSW
59 Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0 Last written: 0 Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
60 Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register<Boolean> { private boolean old; private SafeBoolMRSWRegister value; public void write( boolean x) { if (old != x) { value.write(x); old = x; }} public boolean read() { return value.read(); }} Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
61 Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register<Boolean> { threadLocal boolean old; private SafeBoolMRSWRegister value; public void write(boolean x) { if (old != x) { value.write(x); old = x; }} public boolean read() { return value.read(); }} Last bit this thread wrote (made-up syntax) Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
62 Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register<Boolean> { threadLocal boolean old; private SafeBoolMRSWRegister value; public void write(boolean x) { if (old != x) { value.write(x); old = x; }} public boolean read() { return value.read(); }} Actual value Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
63 Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register<Boolean> { threadLocal boolean old; private SafeBoolMRSWRegister value; public void write(boolean x) { if (old != x) { value.write(x); old = x; }} public boolean read() { return value.read(); }} Is new value different from last value I wrote? Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
64 Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register<Boolean> { threadLocal boolean old; private SafeBoolMRSWRegister value; public void write(boolean x) { if (old != x) { value.write(x); old = x; }} public boolean read() { return value.read(); }} If so, change it (otherwise don’t!) Art of Multiprocessor Programming
Regular Boolean MRSW from Safe Boolean MRSW
65 Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register<Boolean>{ threadLocal boolean old; private SafeBoolMRSWRegister value; public void write(boolean x) { if (old != x) { value.write(x); old = x; }} public boolean read() { return value.read(); }} Overlap? What overlap ? No problem either Boolean value works Art of Multiprocessor Programming
Regular Multi-Valued MRSW from Safe Multi-Valued MRSW?
66 Regular Multi-Valued MRSW from Safe Multi-Valued MRSW ? 0101 0101 Does not work! 0101 Art of Multiprocessor Programming Safe register can return any value in range when value changes Regular register can return only old or new when value changes
Road Map
67 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
68 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Next Art of Multiprocessor Programming
Representing m Values
69 Representing m Values 0 1 2 3 4 5 6 7 1 0 0 0 0 1 Initially 0 Unary representation: bit[i] means value i 0 0 Art of Multiprocessor Programming
Writing m-Valued Register
70 Writing m -Valued Register 1 0 0 0 0 1 Write 5 Art of Multiprocessor Programming 0 1 2 3 4 5 6 7
Writing m-Valued Register
71 Writing m -Valued Register 1 1 0 0 0 0 Write 5 Initially 0 Art of Multiprocessor Programming 0 1 2 3 4 5 6 7
Writing m-Valued Register
0 1 2 3 4 5 6 7 72 Writing m -Valued Register 1 1 0 0 0 0 Write 5 5 0 Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
73 MRSW Regular m -valued from MRSW Regular Boolean public class RegMRSWRegister implements Register{ RegBoolMRSWRegister[M] bit; public void write(int x) { this .bit[x].write(true); for ( int i=x-1; i>=0; i--) this .bit[i].write( false ); } public int read() { for ( int i=0; i < M; i++) if ( this .bit[i].read()) return i; }} Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
74 MRSW Regular m -valued from MRSW Regular Boolean public class RegMRSWRegister implements Register{ RegBoolMRSWRegister[M] bit; public void write(int x) { bit[x].write(true); for (int i=x-1; i>=0; i--) bit[i].write(false); } public int read() { for (int i=0; i < M; i++) if (bit[i].read()) return i; }} Unary representation: bit[i] means value i Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
75 MRSW Regular m -valued from MRSW Regular Boolean public class RegMRSWRegister implements Register { RegBoolMRSWRegister[m] bit; public void write(int x) { bit[x].write( true ); for (int i=x-1; i>=0; i--) bit[i].write(false); } public int read() { for (int i=0; i < M; i++) if (bit[i].read()) return i; }} set bit x Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
76 MRSW Regular m -valued from MRSW Regular Boolean public class RegMRSWRegister implements Register { RegBoolMRSWRegister[m] bit; public void write(int x) { bit[x].write(true); for ( int i=x-1; i>=0; i--) bit[i].write( false ); } public int read() { for (int i=0; i < M; i++) if (bit[i].read()) return i; }} Clear bits from higher to lower Art of Multiprocessor Programming
MRSW Regular m-valued from MRSW Regular Boolean
77 MRSW Regular m -valued from MRSW Regular Boolean public class RegMRSWRegister implements Register { RegBoolMRSWRegister[m] bit; public void write(int x) { bit[x].write(true); for (int i=x-1; i>=0; i--) bit[i].write(false); } public int read() { for ( int i=0; i < M; i++) if (bit[i].read()) return i; }} Scan from lower to higher & return first bit set Art of Multiprocessor Programming
Road Map
78 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
79 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Art of Multiprocessor Programming
Road Map (Slight Detour)
80 Road Map (Slight Detour) • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot SRSW Atomic Art of Multiprocessor Programming
SRSW Atomic From SRSW Regular
Concurrent Reading 81 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678 … When is this a problem ? Art of Multiprocessor Programming
SRSW Atomic From SRSW Regular
82 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 5678 5678 time write( 5678 ) read( 5678 ) Initially 1234 Art of Multiprocessor Programming Same as Atomic
SRSW Atomic From SRSW Regular
83 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678… time write( 5678 ) read( 1234 ) Initially 1234 Same as Atomic Art of Multiprocessor Programming
SRSW Atomic From SRSW Regular
84 SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678 Instead of 5678… time write( 5678 ) read( 1234 ) Initially 1234 Reg read( 5678 ) not Atomic! Write 5678 happened Art of Multiprocessor Programming
Timestamped Values
85 Timestamped Values Writer writes value and stamp together Reader saves last value & stamp read returns new value only if stamp is higher 1234 1:45 5678 2:00 5678 2:00 Art of Multiprocessor Programming 1234 1:45 5678 2:00
SRSW Atomic From SRSW Regular
86 SRSW Atomic From SRSW Regular writer reader 1:45 1234 < 2:00 5678 So stick with 5678 time write( 2:00 5678 ) read( 1:45 1234 ) 1:45 1234 read( 2:00 5678 ) Art of Multiprocessor Programming 1234 1:45 5678 2:00 Same as Atomic
Atomic Single-Reader to Atomic Multi-Reader
87 Atomic Single-Reader to Atomic Multi-Reader 1:45 1234 1:45 1234 1:45 1234 1:45 1234 stamp value One per reader Art of Multiprocessor Programming
Another Scenario
88 Another Scenario 1:45 1234 2:00 5678 1:45 1234 1:45 1234 stamp value Writer starts write… Art of Multiprocessor Programming
Another Scenario
89 Another Scenario 1:45 1234 2:00 5678 1:45 1234 1:45 1234 stamp value reader reads 2:00, 5678 zzz… 1:45 1234 later reader Yellow was completely after Blue but read earlier value…not linearizable! Art of Multiprocessor Programming
Multi-Reader Redux
90 Multi-Reader Redux 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 one per thread 1:45 1234 1:45 1234 1:45 1234 1 2 3 1 2 3 Art of Multiprocessor Programming
Multi-Reader Redux
91 Multi-Reader Redux 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 Writer writes column… 2:00 5678 2:00 5678 2:00 5678 1:45 1234 reader reads row 2:00, 5678 1 1 2 3 1 2 3 2 Art of Multiprocessor Programming
Multi-Reader Redux
92 Multi-Reader Redux 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 1:45 1234 2:00 5678 1:45 1234 reader writes column to notify others of what it read 1 1 2 3 1 2 3 2 2:00 5678 2:00 5678 2:00 5678 2:00 5678 zzz…after second write 2:00, 5678 Yellow reader will read new value in column written by earlier Blue reader Art of Multiprocessor Programming
Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap…
93 Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap… time write(2:00 5678 ) read(1:45 1234) 1:45 1234 read(2:00 5678) In which case its OK to read 1234 Art of Multiprocessor Programming
Bad Case Only When Readers Don’t Overlap
94 Bad Case Only When Readers Don’t Overlap time write(2:00 5678 ) read(2:00 5678) 1:45 1234 read(2:00 5678) In which case Blue will complete writing 2:00 5678 to its column Art of Multiprocessor Programming
Road Map
95 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Next Art of Multiprocessor Programming
Multi-Writer Atomic From Multi-Reader Atomic
96 Multi-Writer Atomic From Multi- Reader Atomic 1:45 1234 1:45 1234 1:45 1234 1:45 1234 stamp value Readers read all and take max (Lexicographic like Bakery) Each writer reads all then writes Max+1 to its register 2:00 5678 2:15 XYZW Max is 2:15, return XYZW Art of Multiprocessor Programming
Atomic Execution Means it is Linearizable
97 Atomic Execution Means it is Linearizable time write(1) time Read(max= 2) write(4) write(2) write(3) Read(max = 3) Read (max = 1) write(2) Read(max = 4) Art of Multiprocessor Programming
Linearization Points
98 Linearization Points time write(1) time Read(max= 2) write(4) write(2) write(3) Read(max = 3) Read (max = 1) write(2) Read(max = 4) Art of Multiprocessor Programming
Linearization Points
99 Linearization Points time write(1) time Look at Writes First write(4) write(2) write(3) write(2) Art of Multiprocessor Programming
Linearization Points
100 Linearization Points time write(1) time write(4) write(2) write(3) write(2) Order writes by TimeStamp Art of Multiprocessor Programming
Linearization Points
101 Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max = 3) Read (max = 1) Read(max = 4) Order reads by max stamp read Art of Multiprocessor Programming
Linearization Points
102 Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max = 3) Read (max = 1) Read(max = 4) Order reads by max stamp read Art of Multiprocessor Programming
Linearization Points
103 Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max = 3) Read (max = 1) Read(max = 4) The linearization point depends on the execution (not a line in the code)! Art of Multiprocessor Programming
Road Map
104 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Questions? Art of Multiprocessor Programming
Road Map
105 Road Map • SRSW safe Boolean • MRSW safe Boolean • MRSW regular Boolean • MRSW regular • MRSW atomic • MRMW atomic • Atomic snapshot Next Art of Multiprocessor Programming
Atomic Snapshot
106 Atomic Snapshot update scan Art of Multiprocessor Programming
Atomic Snapshot
107 Atomic Snapshot • Array of SWMR atomic registers • Take instantaneous snapshot of all • Generalizes to MRMW registers … Art of Multiprocessor Programming
Snapshot Interface
108 Snapshot Interface public interface Snapshot { public int update( int v); public int[] scan(); } Art of Multiprocessor Programming
Snapshot Interface
109 Snapshot Interface public interface Snapshot { public int update( int v); public int[] scan(); } Thread i writes v to its register Art of Multiprocessor Programming
Snapshot Interface
110 Snapshot Interface public interface Snapshot { public int update(int v); public int[] scan(); } Instantaneous snapshot of all theads’ registers Art of Multiprocessor Programming
Atomic Snapshot
111 Atomic Snapshot • Collect – Read values one at a time • Problem – Incompatible concurrent collects – Result not linearizable Art of Multiprocessor Programming
Clean Collects
112 Clean Collects • Clean Collect – Collect during which nothing changed – Can we make it happen? – Can we detect it? Art of Multiprocessor Programming
Simple Snapshot
113 Simple Snapshot • Put increasing labels on each entry • Collect twice • If both agree, – We’re done • Otherwise, – Try again x y z w r z x = Collect 2 Collect 1 x y z w r z x Problem: Scanner might not be collecting a snapshot! Art of Multiprocessor Programming
Claim: We Must Use Labels
114 Claim: We Must Use Labels time x y x y z z x z x z Scanner Updater Updater But scanner sees x and z together! x and z are never in memory together w Art of Multiprocessor Programming
Must Use Labels
115 Must Use Labels time 1,x 2,y 3,x 4,y 1,z 3,z 1,x 1,z 3,x 3,z Scanner Updater Updater 2,w Scanner reads x and z with different labels and recognizes collect not clean Art of Multiprocessor Programming
Simple Snapshot
116 Simple Snapshot • Collect twice • If both agree, – We’re done • Otherwise, – Try again 1 22 1 7 13 18 12 = Collect 2 Collect 1 1 22 1 7 13 18 12 Art of Multiprocessor Programming
Simple Snapshot: Update
117 Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register; public void update( int value) { int i = Thread.myIndex(); LabeledValue oldValue = register[i].read(); LabeledValue newValue = new LabeledValue(oldValue.label+1, value); register[i].write(newValue); } Art of Multiprocessor Programming
Simple Snapshot: Update
118 Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register; public void update(int value) { int i = Thread.myIndex(); LabeledValue oldValue = register[i].read(); LabeledValue newValue = new LabeledValue(oldValue.label+1, value); register[i].write(newValue); } One single-writer register per thread Art of Multiprocessor Programming
Simple Snapshot: Update
119 Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register; public void update(int value) { int i = Thread.myIndex(); LabeledValue oldValue = register[i].read(); LabeledValue newValue = new LabeledValue(oldValue.label+1, value); register[i].write(newValue); } Write each time with higher label Art of Multiprocessor Programming
Simple Snapshot: Collect
120 Simple Snapshot: Collect private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n]; for ( int j = 0; j < n; j++) copy[j] = this .register[j].read(); return copy; } Art of Multiprocessor Programming
Simple Snapshot
121 Simple Snapshot private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n]; for ( int j = 0; j < n; j++) copy[j] = this .register[j].read(); return copy; } Just read each register into array Art of Multiprocessor Programming
Simple Snapshot: Scan
122 Simple Snapshot: Scan public int [] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while ( true ) { newCopy = collect(); if (!equals(oldCopy, newCopy)) { oldCopy = newCopy; continue collect; } return getValues(newCopy); }} Art of Multiprocessor Programming
Simple Snapshot: Scan
123 Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true) { newCopy = collect(); if (!equals(oldCopy, newCopy)) { oldCopy = newCopy; continue collect; } return getValues(newCopy); }} Collect once Art of Multiprocessor Programming
Simple Snapshot: Scan
124 Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true) { newCopy = collect(); if (!equals(oldCopy, newCopy)) { oldCopy = newCopy; continue collect; } return getValues(newCopy); }} Collect once Collect twice Art of Multiprocessor Programming
Simple Snapshot: Scan
125 Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true) { newCopy = collect(); if (!equals(oldCopy, newCopy)) { oldCopy = newCopy; continue collect; } return getValues(newCopy); }} Collect once Collect twice On mismatch, try again Art of Multiprocessor Programming
Simple Snapshot: Scan
126 Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy = collect(); collect: while (true) { newCopy = collect(); if (!equals(oldCopy, newCopy)) { oldCopy = newCopy; continue collect; } return getValues(newCopy); }} Collect once Collect twice On match, return values Art of Multiprocessor Programming
Simple Snapshot
127 Simple Snapshot • Linearizable • Update is wait-free – No unbounded loops • But Scan can starve – If interrupted by concurrent update Art of Multiprocessor Programming
Wait-Free Snapshot
128 Wait-Free Snapshot • Add a scan before every update • Write resulting snapshot together with update value • If scan is continuously interrupted by updates, scan can take the update’s snapshot Art of Multiprocessor Programming
Wait-free Snapshot
129 Wait-free Snapshot If A ’s scan observes that B moved twice , then B completed an update while A ’s scan was in progress time Update B ≠ ≠ 26 24 12 Collect 26 24 12 Collect 26 24 12 Collect Art of Multiprocessor Programming
Wait-free Snapshot
130 Wait-free Snapshot time ≠ ≠ 26 24 12 Collect 26 24 12 Collect 26 24 12 Collect Update A B Art of Multiprocessor Programming
Wait-free Snapshot
131 Wait-free Snapshot time ≠ ≠ 26 24 12 Collect 26 24 12 Collect 26 24 12 Collect A B Scan Write Update Art of Multiprocessor Programming
Wait-free Snapshot
132 Wait-free Snapshot time ≠ ≠ 26 24 12 Collect 26 24 12 Collect 26 24 12 Collect A B Scan Write Update Scan Write B’s 1 st update must have written during 1 st collect So scan of B ’s second update must be within interval of A ’s scan So A can steal result of B ’s scan Art of Multiprocessor Programming
Wait-free Snapshot
133 Wait-free Snapshot time ≠ ≠ 26 24 12 Collect 26 24 12 Collect 26 24 12 Collect A B Scan Write Scan Write But no guarantee that scan of B ’s 1 st update can be used… Why? Art of Multiprocessor Programming
Once is not Enough
134 Once is not Enough time ≠ 26 24 12 Collect 26 24 12 Collect Update A B Scan Write Why can’t A steal B ’s scan? Because another update might have interfered before the scan Update Art of Multiprocessor Programming
Someone Must Move Twice
135 Someone Must Move Twice time Update B ≠ ≠ 26 24 12 Collect 26 24 12 Collect 26 24 12 Collect If we collect n times…some thread must move twice (pigeonhole principle) Art of Multiprocessor Programming
Scan is Wait-free
136 Scan is Wait-free scan update So some thread must have had clean collect scan update scan At most n-1 depth Art of Multiprocessor Programming
Wait-Free Snapshot Label
137 Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap; } Art of Multiprocessor Programming
Wait-Free Snapshot Label
138 Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap; } Counter incremented with each snapshot Art of Multiprocessor Programming
Wait-Free Snapshot Label
139 Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap; } Actual value Art of Multiprocessor Programming
Wait-Free Snapshot Label
140 Wait-Free Snapshot Label public class SnapValue { public int label; public int value; public int[] snap; } most recent snapshot Art of Multiprocessor Programming
Wait-Free Snapshot Label
141 Wait-Free Snapshot Label 11011110101000101100…00 label value Last snapshot Art of Multiprocessor Programming
Wait-free Update
142 Wait-free Update public void update(int value) { int i = Thread.myIndex(); int [] snap = this .scan(); SnapValue oldValue = r[i].read(); SnapValue newValue = new SnapValue(oldValue.label+1, value, snap); r[i].write(newValue); } Art of Multiprocessor Programming
Wait-free Scan
143 Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int [] snap = this .scan(); SnapValue oldValue = r[i].read(); SnapValue newValue = new SnapValue(oldValue.label+1, value, snap); r[i].write(newValue); } Take scan Art of Multiprocessor Programming
Wait-free Scan
144 Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int [] snap = this .scan(); SnapValue oldValue = r[i].read(); SnapValue newValue = new SnapValue(oldValue.label+1, value, snap); r[i].write(newValue); } Take scan Label value with scan Art of Multiprocessor Programming
Wait-free Scan
145 Wait-free Scan public int [] scan() { SnapValue[] oldCopy, newCopy; boolean [] moved = new boolean [n]; oldCopy = collect(); collect: while ( true ) { newCopy = collect(); for ( int j = 0; j < n; j++) { if (oldCopy[j].label != newCopy[j].label) { … }} return getValues(newCopy); }}} Art of Multiprocessor Programming
Wait-free Scan
146 Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean [] moved = new boolean [n]; oldCopy = collect(); collect: while (true) { newCopy = collect(); for (int j = 0; j < n; j++) { if (oldCopy[j].label != newCopy[j].label) { … }} return getValues(newCopy); }}} Keep track of who moved Art of Multiprocessor Programming
Wait-free Scan
147 Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved = new boolean[n]; oldCopy = collect(); collect: while ( true ) { newCopy = collect(); for (int j = 0; j < n; j++) { if (oldCopy[j].label != newCopy[j].label) { … }} return getValues(newCopy); }}} Repeated double collect Art of Multiprocessor Programming
Wait-free Scan
148 Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved = new boolean[n]; oldCopy = collect(); collect: while (true) { newCopy = collect(); for (int j = 0; j < n; j++) { if (oldCopy[j].label != newCopy[j].label) { … }} return getValues(newCopy); }}} If mismatch detected… Art of Multiprocessor Programming
Mismatch Detected
149 Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second move return newCopy[j].snap; } else { moved[j] = true ; oldCopy = newCopy; continue collect; }}} return getValues(newCopy); }}} Art of Multiprocessor Programming
Mismatch Detected
150 Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { return newCopy[j].snap; } else { moved[j] = true; oldCopy = newCopy; continue collect; }}} return getValues(newCopy); }}} If thread moved twice, just steal its second snapshot Art of Multiprocessor Programming
Mismatch Detected
151 Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second move return newCopy[j].snap; } else { moved[j] = true ; oldCopy = newCopy; continue collect; }}} return getValues(newCopy); }}} Remember that thread moved Art of Multiprocessor Programming
Observations
152 Observations • Uses unbounded counters – can be replaced with 2 bits • Assumes SWMR registers – for labels – can be extended to MRMW Art of Multiprocessor Programming
Summary
153 Summary • We saw we could implement MRMW multi valued snapshot objects • From SRSW binary safe registers (simple flipflops) • But what is the next step to attempt with read-write registers? Art of Multiprocessor Programming
Grand Challenge
154 Grand Challenge • Snapshot means – Write any one array element – Read multiple array elements Art of Multiprocessor Programming
Grand Challenge
155 Grand Challenge Writes to 0 and 1 Writes to 1 and 2 What about atomic writes to multiple locations? Write many and snapshot Art of Multiprocessor Programming
156   creativecommons.org/licenses/by-sa/2.5/ Creative Commons Attribution-ShareAlike 2.5 License . • You are free: – to Share — to copy, distribute and transmit the work – to Remix — to adapt the work • Under the following conditions: – Attribution . You must attribute the work to “The Art of Multiprocessor Programming” (but not in any way that suggests that the authors endorse you or your use of the work). – Share Alike . If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license. • For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to – http://creativecommons.org/licenses/by-sa/3.0/. • Any of the above conditions can be waived if you get permission from the copyright holder. • Nothing in this license impairs or restricts the author's moral rights. Art of Multiprocessor Programming