Introduction
Introduction 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
Moore’s Law
Art of Multiprocessor Programming 2 Moore’s Law Clock speed flattening sharply Transistor count still rising
Moore’s Law (in practice)
Moore’s Law (in practice) Art of Multiprocessor Programming 3
Nearly Extinct: the Uniprocesor
Art of Multiprocessor Programming 4 Nearly Extinct: the Uniprocesor memory cpu
Endangered: The Shared Memory Multiprocessor (SMP)
Art of Multiprocessor Programming 5 Endangered: The Shared Memory Multiprocessor (SMP) cache Bus Bus shared memory cache cache
The New Boss: The Multicore Processor (CMP)
Art of Multiprocessor Programming 6 The New Boss: The Multicore Processor (CMP) cache Bus Bus shared memory cache cache All on the same chip Sun T2000 Niagara
From the 2008 press…
Art of Multiprocessor Programming 7 From the 2008 press… …Intel has announced a press conference in San Francisco on November 17th, where it will officially launch the Core i7 Nehalem processor… …Sun’s next generation Enterprise T5140 and T5240 servers, based on the 3rd Generation UltraSPARC T2 Plus processor, were released two days ago…
Art of Multiprocessor Programming 8 Why is Kunle Smiling? Niagara 1
Traditional Scaling Process
Art of Multiprocessor Programming 10 Traditional Scaling Process User code Traditional Uniprocessor Speedup 1.8x 7x 3.6x Time: Moore’s law
Ideal Scaling Process
Ideal Scaling Process Art of Multiprocessor Programming 11 User code Multicore Speedup 1.8x 7x 3.6x Unfortunately, not so simple…
Actual Scaling Process
Actual Scaling Process Art of Multiprocessor Programming 12 1.8x 2x 2.9x User code Multicore Speedup Parallelization and Synchronization require great care…
Multicore Programming: Course Overview
Art of Multiprocessor Programming 13 Multicore Programming : Course Overview • Fundamentals – Models, algorithms, impossibility • Real-World programming – Architectures – Techniques
Sequential Computation
Art of Multiprocessor Programming 14 Sequential Computation memory object object thread
Concurrent Computation
Art of Multiprocessor Programming 15 Concurrent Computation memory object object threads
Asynchrony
Art of Multiprocessor Programming 16 Asynchrony • Sudden unpredictable delays – Cache misses ( short ) – Page faults ( long ) – Scheduling quantum used up ( really long )
Model Summary
Art of Multiprocessor Programming 17 Model Summary • Multiple threads – Sometimes called processes • Single shared memory • Objects live in memory • Unpredictable asynchronous delays
Road Map
18 Road Map • We are going to focus on principles first, then practice – Start with idealized models – Look at simplistic problems – Emphasize correctness over pragmatism – “Correctness may be theoretical, but incorrectness has practical impact” Art of Multiprocessor Programming
Concurrency Jargon
19 Concurrency Jargon • Hardware – Processors • Software – Threads, processes • Sometimes OK to confuse them, sometimes not. Art of Multiprocessor Programming
Parallel Primality Testing
20 Parallel Primality Testing • Challenge – Print primes from 1 to 10 10 • Given – Ten-processor multiprocessor – One thread per processor • Goal – Get ten-fold speedup (or close) Art of Multiprocessor Programming
Load Balancing
Art of Multiprocessor Programming 21 Load Balancing • Split the work evenly • Each thread tests range of 10 9 … … 10 9 10 10 2·10 9 1 P 0 P 1 P 9
Procedure for Thread i
22 Procedure for Thread i void primePrint { int i = ThreadID.get(); // IDs in {0..9} for (j = i*10 9 +1, j<(i+1)*10 9 ; j++) { if (isPrime(j)) print(j); } } Art of Multiprocessor Programming
Issues
23 Issues • Higher ranges have fewer primes • Yet larger numbers harder to test • Thread workloads – Uneven – Hard to predict Art of Multiprocessor Programming
Issues
Art of Multiprocessor Programming 24 Issues • Higher ranges have fewer primes • Yet larger numbers harder to test • Thread workloads – Uneven – Hard to predict • Need dynamic load balancing rejected
Shared Counter
Art of Multiprocessor Programming 25 17 18 19 Shared Counter each thread takes a number
Procedure for Thread i
26 Procedure for Thread i int counter = new Counter(1); void primePrint { long j = 0; while (j < 10 10 ) { j = counter.getAndIncrement(); if (isPrime(j)) print(j); } } Art of Multiprocessor Programming
Procedure for Thread i
Art of Multiprocessor Programming 27 Counter counter = new Counter(1); void primePrint { long j = 0; while (j < 10 10 ) { j = counter.getAndIncrement(); if (isPrime(j)) print(j); } } Procedure for Thread i Shared counter object
Where Things Reside
Art of Multiprocessor Programming 28 Where Things Reside cache Bus Bus cache cache 1 shared counter shared memory void primePrint { int i = ThreadID.get(); // IDs in {0..9} for (j = i*10 9 +1, j<(i+1)*10 9 ; j++) { if (isPrime(j)) print(j); } } code Local variables
Procedure for Thread i
Art of Multiprocessor Programming 29 Procedure for Thread i Counter counter = new Counter(1); void primePrint { long j = 0; while (j < 10 10 ) { j = counter.getAndIncrement(); if (isPrime(j)) print(j); } } Stop when every value taken
Procedure for Thread i
Art of Multiprocessor Programming 30 Counter counter = new Counter(1); void primePrint { long j = 0; while (j < 10 10 ) { j = counter.getAndIncrement(); if (isPrime(j)) print(j); } } Procedure for Thread i Increment & return each new value
Counter Implementation
31 Counter Implementation public class Counter { private long value ; public long getAndIncrement() { return value++; } } Art of Multiprocessor Programming
Counter Implementation
Art of Multiprocessor Programming 32 Counter Implementation public class Counter { private long value; public long getAndIncrement() { return value++; } } OK for single thread, not for concurrent threads
What It Means
Art of Multiprocessor Programming 33 What It Means public class Counter { private long value; public long getAndIncrement() { return value++; } }
What It Means
Art of Multiprocessor Programming 34 What It Means public class Counter { private long value; public long getAndIncrement() { return value++; } } temp = value; value = temp + 1; return temp;
Not so good…
Art of Multiprocessor Programming 35 time Not so good… Value… 1 read 1 read 1 write 2 read 2 write 3 write 2 2 3 2
Is this problem inherent?
Art of Multiprocessor Programming 36 Is this problem inherent? If we could only glue reads and writes together… read write read write !! !!
Challenge
37 Challenge public class Counter { private long value; public long getAndIncrement() { temp = value; value = temp + 1; return temp; } } Art of Multiprocessor Programming
Challenge
Art of Multiprocessor Programming 38 Challenge public class Counter { private long value; public long getAndIncrement() { temp = value; value = temp + 1; return temp; } } Make these steps atomic (indivisible)
Hardware Solution
Art of Multiprocessor Programming 39 Hardware Solution public class Counter { private long value; public long getAndIncrement() { temp = value; value = temp + 1; return temp; } } ReadModifyWrite() instruction
An Aside: Java™
Art of Multiprocessor Programming 40 An Aside: Java™ public class Counter { private long value; public long getAndIncrement() { synchronized { temp = value; value = temp + 1; } return temp; } }
An Aside: Java™
Art of Multiprocessor Programming 41 An Aside: Java™ public class Counter { private long value; public long getAndIncrement() { synchronized { temp = value; value = temp + 1; } return temp; } } Synchronized block
An Aside: Java™
Art of Multiprocessor Programming 42 An Aside: Java™ public class Counter { private long value; public long getAndIncrement() { synchronized { temp = value; value = temp + 1; } return temp; } } Mutual Exclusion
Mutual Exclusion, or “Alice & Bob share a pond”
43 Mutual Exclusion, or “Alice & Bob share a pond” A B Art of Multiprocessor Programming
Alice has a pet
44 Alice has a pet A B Art of Multiprocessor Programming
Bob has a pet
45 Bob has a pet A B Art of Multiprocessor Programming
The Problem
46 The Problem A B The pets don’t get along Art of Multiprocessor Programming
Formalizing the Problem
47 Formalizing the Problem • Two types of formal properties in asynchronous computation: • Safety Properties – Nothing bad happens ever • Liveness Properties – Something good happens eventually Art of Multiprocessor Programming
Formalizing our Problem
48 Formalizing our Problem • Mutual Exclusion – Both pets never in pond simultaneously – This is a safety property • No Deadlock – if only one wants in, it gets in – if both want in, one gets in. – This is a liveness property Art of Multiprocessor Programming
Simple Protocol
49 Simple Protocol • Idea – Just look at the pond • Gotcha – Not atomic – Trees obscure the view Art of Multiprocessor Programming
Interpretation
50 Interpretation • Threads can’t “see” what other threads are doing • Explicit communication required for coordination Art of Multiprocessor Programming
Cell Phone Protocol
51 Cell Phone Protocol • Idea – Bob calls Alice (or vice-versa) • Gotcha – Bob takes shower – Alice recharges battery – Bob out shopping for pet food … Art of Multiprocessor Programming
Interpretation
52 Interpretation • Message-passing doesn’t work • Recipient might not be – Listening – There at all • Communication must be – Persistent (like writing) – Not transient (like speaking) Art of Multiprocessor Programming
Can Protocol
53 Can Protocol cola cola Art of Multiprocessor Programming
Bob conveys a bit
54 Bob conveys a bit A B cola Art of Multiprocessor Programming
Bob conveys a bit
55 Bob conveys a bit A B cola Art of Multiprocessor Programming
Can Protocol
56 Can Protocol • Idea – Cans on Alice’s windowsill – Strings lead to Bob’s house – Bob pulls strings, knocks over cans • Gotcha – Cans cannot be reused – Bob runs out of cans Art of Multiprocessor Programming
Interpretation
57 Interpretation • Cannot solve mutual exclusion with interrupts – Sender sets fixed bit in receiver’s space – Receiver resets bit when ready – Requires unbounded number of interrupt bits Art of Multiprocessor Programming
Flag Protocol
58 Flag Protocol A B Art of Multiprocessor Programming
Alice’s Protocol (sort of)
59 Alice’s Protocol (sort of) A B Art of Multiprocessor Programming
Bob’s Protocol (sort of)
60 Bob’s Protocol (sort of) A B Art of Multiprocessor Programming
Alice’s Protocol
61 Alice’s Protocol • Raise flag • Wait until Bob’s flag is down • Unleash pet • Lower flag when pet returns Art of Multiprocessor Programming
Bob’s Protocol
Art of Multiprocessor Programming 62 Bob’s Protocol • Raise flag • Wait until Alice’s flag is down • Unleash pet • Lower flag when pet returns danger!
Bob’s Protocol (2nd try)
63 Bob’s Protocol (2 nd try) • Raise flag • While Alice’s flag is up – Lower flag – Wait for Alice’s flag to go down – Raise flag • Unleash pet • Lower flag when pet returns Art of Multiprocessor Programming
Bob’s Protocol
Art of Multiprocessor Programming 64 Bob’s Protocol • Raise flag • While Alice’s flag is up – Lower flag – Wait for Alice’s flag to go down – Raise flag • Unleash pet • Lower flag when pet returns Bob defers to Alice
The Flag Principle
65 The Flag Principle • Raise the flag • Look at other’s flag • Flag Principle: – If each raises and looks, then – Last to look must see both flags up Art of Multiprocessor Programming
Proof of Mutual Exclusion
66 Proof of Mutual Exclusion • Assume both pets in pond – Derive a contradiction – By reasoning backwards • Consider the last time Alice and Bob each looked before letting the pets in • Without loss of generality assume Alice was the last to look… Art of Multiprocessor Programming
Proof
Art of Multiprocessor Programming 67 Proof time Alice’s last look Alice last raised her flag Bob’s last look QED Alice must have seen Bob’s Flag. A Contradiction Bob last raised flag
Proof of No Deadlock
68 Proof of No Deadlock • If only one pet wants in, it gets in. Art of Multiprocessor Programming
Proof of No Deadlock
69 Proof of No Deadlock • If only one pet wants in, it gets in. • Deadlock requires both continually trying to get in. Art of Multiprocessor Programming
Proof of No Deadlock
Art of Multiprocessor Programming 70 Proof of No Deadlock • If only one pet wants in, it gets in. • Deadlock requires both continually trying to get in. • If Bob sees Alice’s flag, he gives her priority (a gentleman…) QED
Remarks
71 Remarks • Protocol is unfair – Bob’s pet might never get in • Protocol uses waiting – If Bob is eaten by his pet, Alice’s pet might never get in Art of Multiprocessor Programming
Moral of Story
72 Moral of Story • Mutual Exclusion cannot be solved by – transient communication (cell phones) – interrupts (cans) • It can be solved by – one-bit shared variables – that can be read or written Art of Multiprocessor Programming
The Arbiter Problem (an aside)
Art of Multiprocessor Programming 73 The Arbiter Problem (an aside) Pick a point Pick a point
The Fable Continues
74 The Fable Continues • Alice and Bob fall in love & marry Art of Multiprocessor Programming
The Fable Continues
75 The Fable Continues • Alice and Bob fall in love & marry • Then they fall out of love & divorce – She gets the pets – He has to feed them Art of Multiprocessor Programming
The Fable Continues
76 The Fable Continues • Alice and Bob fall in love & marry • Then they fall out of love & divorce – She gets the pets – He has to feed them • Leading to a new coordination problem: Producer-Consumer Art of Multiprocessor Programming
Bob Puts Food in the Pond
77 Bob Puts Food in the Pond A Art of Multiprocessor Programming
Alice releases her pets to Feed
78 mmm… Alice releases her pets to Feed B mmm… Art of Multiprocessor Programming
Producer/Consumer
79 Producer/Consumer • Alice and Bob can’t meet – Each has restraining order on other – So he puts food in the pond – And later, she releases the pets • Avoid – Releasing pets when there’s no food – Putting out food if uneaten food remains Art of Multiprocessor Programming
Producer/Consumer
80 Producer/Consumer • Need a mechanism so that – Bob lets Alice know when food has been put out – Alice lets Bob know when to put out more food Art of Multiprocessor Programming
Surprise Solution
81 Surprise Solution A B cola Art of Multiprocessor Programming
Bob puts food in Pond
82 Bob puts food in Pond A B cola Art of Multiprocessor Programming
Bob knocks over Can
83 Bob knocks over Can A B cola Art of Multiprocessor Programming
Alice Releases Pets
84 Alice Releases Pets A B cola yum… B yum… Art of Multiprocessor Programming
Alice Resets Can when Pets are Fed
85 Alice Resets Can when Pets are Fed A B cola Art of Multiprocessor Programming
Pseudocode
Art of Multiprocessor Programming 86 Pseudocode while ( true ) { while (can.isUp()){}; pet.release(); pet.recapture(); can.reset(); } Alice’s code
Pseudocode
Art of Multiprocessor Programming 87 Pseudocode while ( true ) { while (can.isUp()){}; pet.release(); pet.recapture(); can.reset(); } Alice’s code while ( true ) { while (can.isDown()){}; pond.stockWithFood(); can.knockOver(); } Bob’s code
Correctness
88 Correctness • Mutual Exclusion – Pets and Bob never together in pond Art of Multiprocessor Programming
Correctness
89 Correctness • Mutual Exclusion – Pets and Bob never together in pond • No Starvation if Bob always willing to feed, and pets always famished, then pets eat infinitely often. Art of Multiprocessor Programming
Correctness
Art of Multiprocessor Programming 90 Correctness • Mutual Exclusion – Pets and Bob never together in pond • No Starvation if Bob always willing to feed, and pets always famished, then pets eat infinitely often. • Producer/Consumer The pets never enter pond unless there is food, and Bob never provides food if there is unconsumed food. safety liveness safety
Could Also Solve Using Flags
91 Could Also Solve Using Flags A B Art of Multiprocessor Programming
Waiting
92 Waiting • Both solutions use waiting – while (mumble){} • In some cases waiting is problematic – If one participant is delayed – So is everyone else – But delays are common & unpredictable Art of Multiprocessor Programming
The Fable drags on …
93 The Fable drags on … • Bob and Alice still have issues Art of Multiprocessor Programming
The Fable drags on …
94 The Fable drags on … • Bob and Alice still have issues • So they need to communicate Art of Multiprocessor Programming
The Fable drags on …
95 The Fable drags on … • Bob and Alice still have issues • So they need to communicate • They agree to use billboards … Art of Multiprocessor Programming
Billboards are Large
96 E 1 D 2 C 3 Billboards are Large B 3 A 1 Letter Tiles From Scrabble™ box Art of Multiprocessor Programming
Write One Letter at a Time …
97 E 1 D 2 C 3 Write One Letter at a Time … B 3 A 1 W 4 A 1 S 1 H 4 Art of Multiprocessor Programming
To post a message
98 To post a message W 4 A 1 S 1 H 4 A 1 C 3 R 1 T 1 H 4 E 1 whew Art of Multiprocessor Programming
Let’s send another message
99 S 1 Let’s send another message S 1 E 1 L 1 L 1 L 1 V 4 L 1 A 1 M 3 A 1 A 1 P 3 Art of Multiprocessor Programming
Uh-Oh
100 Uh-Oh A 1 C 3 R 1 T 1 H 4 E 1 S 1 E 1 L 1 L 1 L 1 OK Art of Multiprocessor Programming
Readers/Writers
101 Readers/Writers • Devise a protocol so that – Writer writes one letter at a time – Reader reads one letter at a time – Reader sees “snapshot” • Old message or new message • No mixed messages Art of Multiprocessor Programming
Readers/Writers (continued)
102 Readers/Writers (continued) • Easy with mutual exclusion • But mutual exclusion requires waiting – One waits for the other – Everyone executes sequentially • Remarkably – We can solve R/W without mutual exclusion Art of Multiprocessor Programming
Esoteric?
Art of Multiprocessor Programming 103 Esoteric? • Java container size() method • Single shared counter? – incremented with each add() and – decremented with each remove() • Threads wait to exclusively access counter performance b ottleneck
Readers/Writers Solution
104 Readers/Writers Solution • Each thread i has size[i] counter – only it increments or decrements. • To get object’s size, a thread reads a “snapshot” of all counters • This eliminates the bottleneck Art of Multiprocessor Programming
Why do we care?
105 Why do we care? • We want as much of the code as possible to execute concurrently (in parallel) • A larger sequential part implies reduced performance • Amdahl’s law: this relation is not linear… Art of Multiprocessor Programming
Amdahl’s Law
Art of Multiprocessor Programming 106 Amdahl’s Law Speedup= 1 -thread execution time n -thread execution time
Amdahl’s Law
Art of Multiprocessor Programming 107 Amdahl’s Law Speedup=
Amdahl’s Law
Art of Multiprocessor Programming 108 Amdahl’s Law Speedup= Parallel fraction
Amdahl’s Law
Art of Multiprocessor Programming 109 Amdahl’s Law Speedup= Parallel fraction Sequential fraction
Amdahl’s Law
Art of Multiprocessor Programming 110 Amdahl’s Law Speedup= Parallel fraction Sequential fraction Number of threads
Amdahl’s Law (in practice)
Amdahl’s Law (in practice) Art of Multiprocessor Programming 111
Example
112 Example • Ten processors • 60% concurrent, 40% sequential • How close to 10-fold speedup? Art of Multiprocessor Programming
Example
113 Example • Ten processors • 60% concurrent, 40% sequential • How close to 10-fold speedup? Speedup = 2.17= Art of Multiprocessor Programming
Example
114 Example • Ten processors • 80% concurrent, 20% sequential • How close to 10-fold speedup? Art of Multiprocessor Programming
Example
115 Example • Ten processors • 80% concurrent, 20% sequential • How close to 10-fold speedup? Speedup = 3.57 = Art of Multiprocessor Programming
Example
116 Example • Ten processors • 90% concurrent, 10% sequential • How close to 10-fold speedup? Art of Multiprocessor Programming
Example
Art of Multiprocessor Programming 117 Example • Ten processors • 90% concurrent, 10% sequential • How close to 10-fold speedup? Speedup = 5.26=
Example
118 Example • Ten processors • 99% concurrent, 01% sequential • How close to 10-fold speedup? Art of Multiprocessor Programming
Example
Art of Multiprocessor Programming 119 Example • Ten processors • 99% concurrent, 01% sequential • How close to 10-fold speedup? Speedup = 9.17=
Back to Real-World Multicore Scaling
Back to Real-World Multicore Scaling 1.8x 2x 2.9x User code Multicore Speedup Not reducing sequential % of code Art of Multiprocessor Programming
Shared Data Structures
Shared Data Structures 75% Unshared 25% Shared Coarse Grained Fine Grained 75% Unshared 25% Shared
Shared Data Structures
Shared Data Structures 75% Unshared 25% Shared Coarse Grained Fine Grained Why only 2.9 speedup 75% Unshared 25% Shared Honk! Honk! Honk!
Shared Data Structures
Shared Data Structures 75% Unshared 25% Shared Coarse Grained Fine Grained Why fine-grained parallelism maters 75% Unshared 25% Shared Honk! Honk! Honk!
Art of Multiprocessor Programming 125   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.