CS1760

Multiprocessor
Synchronization
 Staff

Maurice Herlihy (instructor)

Daniel Engel (grad TA)

Jonathan Lister (HTA)

Bhrath Kayyer (UTA)

Art of Multiprocessor Programming
 Grading

8 Homeworks (40%)

5 programming assignments (20%)

3 Midterms (40%)

Art of Multiprocessor Programming

 Collaboration
Permitted
talking about the homework
problems with other students; using
other textbooks; using the Internet.

NOT Permitted
obtaining the answer directly from
anyone or anything else in any
form.

Art of Multiprocessor Programming

 Capstone

Yes, you can take this course as a

capstone course

Only one project possible

(concurrent packet filter)

Requires reading ahead of the course

See web page for details

Art of Multiprocessor Programming
See Course Web Page for …

TA Hours

Piazza

Other important matters

Art of Multiprocessor Programming

Moore’s Law
Transistor
count still
rising

Clock
speed
flattening
sharply

Art of Multiprocessor Programming 7

Moore’s Law (in practice)

Art of Multiprocessor Programming 8

Extinct: the Uniprocesor

cpu

memory

Art of Multiprocessor Programming 9

 Extinct:
The Shared Memory Multiprocessor
(SMP)

cache cache cache

Bus Bus

shared memory

Art of Multiprocessor Programming 10

 The New Boss:
The Multicore Processor
(CMP)

All on the Sun

cache cache cache
same chip Bus Bus
T2000
Niagara
shared memory

Art of Multiprocessor Programming 11

 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 12

 Why is Kunle Smiling?

Niagara 1

Art of Multiprocessor Programming 13

 Why do we care?
• Time no longer cures software bloat
– The “free ride” is over
• When you double your program’s path
length
– You can’t just wait 6 months
– Your software must somehow exploit twice as
much concurrency

Art of Multiprocessor Programming 14

 Traditional Scaling Process
7x
Speedup 3.6x
1.8x

User code

Traditional
Uniprocessor

Time: Moore’s law

Art of Multiprocessor Programming 15
 Ideal Scaling Process
7x
Speedup 3.6x
1.8x

User code

Multicore

Unfortunately, not so simple…

Art of Multiprocessor Programming 16

 Actual Scaling Process
Speedup
2x 2.9x
1.8x

User code

Multicore

Parallelization and Synchronization

require great care…
Art of Multiprocessor Programming 17
 Multicore Programming:
Course Overview

• Fundamentals
– Models, algorithms, impossibility
• Real-World programming
– Architectures
– Techniques

Art of Multiprocessor Programming 18

 Sequential Computation

thread

memory

object object
Art of Multiprocessor Programming 19
 Concurrent Computation

memory

object object
Art of Multiprocessor Programming 20
 Asynchrony

• Sudden unpredictable delays

– Cache misses (short)
– Page faults (long)
– Scheduling quantum used up (really long)

Art of Multiprocessor Programming 21

 Model Summary
• Multiple threads
– Sometimes called processes
• Single shared memory
• Objects live in memory
• Unpredictable asynchronous delays

Art of Multiprocessor Programming 22

 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 23

 Concurrency Jargon
• Hardware
– Processors
• Software
– Threads, processes
• Sometimes OK to confuse them,
sometimes not.

Art of Multiprocessor Programming 24

 Parallel Primality Testing
• Challenge
– Print primes from 1 to 1010
• Given
– Ten-processor multiprocessor
– One thread per processor
• Goal
– Get ten-fold speedup (or close)

Art of Multiprocessor Programming 25

 Load Balancing

1 109 2·109 … 1010

P0 P1 … P9

• Split the work evenly

• Each thread tests range of 109

Art of Multiprocessor Programming 26

 Procedure for Thread i

void primePrint {
int i = [Link](); // IDs in {0..9}
for (j = i*109+1, j<(i+1)*109; j++) {
if (isPrime(j))
print(j);
}
}

Art of Multiprocessor Programming 27

 Issues
• Higher ranges have fewer primes
• Yet larger numbers harder to test
• Thread workloads
– Uneven
– Hard to predict

Art of Multiprocessor Programming 28

 Issues
• Higher ranges have fewer primes
• Yet larger numbers harder to test
• Thread workloads
– Uneven
– Hard to predict
• Need dynamic load balancing

Art of Multiprocessor Programming 29

Shared Counter

19

18 each thread
takes a number
17
Art of Multiprocessor Programming 30
 Procedure for Thread i

int counter = new Counter(1);

void primePrint {
long j = 0;
while (j < 1010) {
j = [Link]();
if (isPrime(j))
print(j);
}
}

Art of Multiprocessor Programming 31

 Procedure for Thread i

Counter counter = new Counter(1);

void primePrint {
long j = 0;
while (j < 1010) {
j = [Link]();
if (isPrime(j)) Shared counter
print(j);
object
}
}

Art of Multiprocessor Programming 32

 Where Things Reside
void primePrint {
int i =
[Link](); // IDs
in {0..9}
for (j = i*109+1,
j<(i+1)*109; j++) {

}
}
if (isPrime(j))
print(j);
Local
variables
code

cache cache cache

Bus Bus

shared
1 memory

shared counter

Art of Multiprocessor Programming 33

 Procedure for Thread i

Counter counter = new Counter(1);

void primePrint {
long j = 0;
while (j < 1010) {
j = [Link]();
if (isPrime(j))
print(j);
Stop when every
}
} value taken

Art of Multiprocessor Programming 34

 Procedure for Thread i

Counter counter = new Counter(1);

void primePrint {
long j = 0;
while (j < 1010) {
j = [Link]();
if (isPrime(j))
print(j);
}
} Increment & return each
new value
Art of Multiprocessor Programming 35
 Counter Implementation

public class Counter {

private long value;

public long getAndIncrement() {

return value++;
}
}

Art of Multiprocessor Programming 36

 Counter Implementation

public class Counter {

private long value;

public long getAndIncrement() {

return value++;
}
}

Art of Multiprocessor Programming 37

 What It Means

public class Counter {

private long value;

public long getAndIncrement() {

return value++;
}
}

Art of Multiprocessor Programming 38

 What It Means

public class Counter {

private long value;

public long getAndIncrement() {

return value++; temp = value;
} value = temp + 1;
} return temp;

Art of Multiprocessor Programming 39

 Not so good…
Value… 1 2 3 2

read write read write

1 2 2 3

read write
1 2

time
Art of Multiprocessor Programming 40
Is this problem inherent?
!! !!
write
read

write read

If we could only glue reads and writes

together…

Art of Multiprocessor Programming 41

 Challenge

public class Counter {

private long value;

public long getAndIncrement() {

temp = value;
value = temp + 1;
return temp;
}
}

Art of Multiprocessor Programming 42

 Challenge

public class Counter {

private long value;

public long getAndIncrement() {

temp = value;
value = temp + 1;
return temp;
} Make these steps
} atomic (indivisible)
Art of Multiprocessor Programming 43
 Hardware Solution

public class Counter {

private long value;

public long getAndIncrement() {

temp = value;
value = temp + 1;
return temp;
}
} ReadModifyWrite()
instruction 44
Art of Multiprocessor Programming
 An Aside: Java™

public class Counter {

private long value;

public long getAndIncrement() {

synchronized {
temp = value;
value = temp + 1;
}
return temp;
}
}
Art of Multiprocessor Programming 45
 An Aside: Java™

public class Counter {

private long value;

public long getAndIncrement() {

synchronized {
temp = value;
value = temp + 1;
}
return temp;
} Synchronized block
}
Art of Multiprocessor Programming 46
 An Aside: Java™

public class Counter {

private long value;

public long getAndIncrement() {

Mutual Exclusion
synchronized {
temp = value;
value = temp + 1;
}
return temp;
}
}
Art of Multiprocessor Programming 47
 Mutual Exclusion,
or “Alice & Bob share a pond”

A B

Art of Multiprocessor Programming 48

 Alice has a pet

A B

Art of Multiprocessor Programming 49

 Bob has a pet

A B

Art of Multiprocessor Programming 50

 The Problem

A B

The pets don’t

get along

Art of Multiprocessor Programming 51

 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 52

 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 53

 Simple Protocol
• Idea
– Just look at the pond
• Gotcha
– Not atomic
– Trees obscure the view

Art of Multiprocessor Programming 54

 Interpretation
• Threads can’t “see” what other threads are
doing
• Explicit communication required for
coordination

Art of Multiprocessor Programming 55

 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 56

 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 57

Can Protocol

cola
cola

Art of Multiprocessor Programming 58

 Bob conveys a bit

A B
cola

Art of Multiprocessor Programming 59

 Bob conveys a bit

A B

Art of Multiprocessor Programming 60

 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 61

 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 62

 Flag Protocol

A B

Art of Multiprocessor Programming 63

Alice’s Protocol (sort of)

A B

Art of Multiprocessor Programming 64

 Bob’s Protocol (sort of)

A B

Art of Multiprocessor Programming 65

 Alice’s Protocol

• Raise flag
• Wait until Bob’s flag is down
• Unleash pet
• Lower flag when pet returns

Art of Multiprocessor Programming 66

 Bob’s Protocol

• Raise flag
• Wait until Alice’s flag is down
• Unleash pet
• Lower flag when pet returns

Art of Multiprocessor Programming 67

 Bob’s Protocol (2nd 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 68

 Bob’s Protocol

Bob defers
• Raise flag to Alice
• 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 69

 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 70

 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 71

 Proof
Bob last raised
flag Alice last raised her flag

Alice’s last look

Bob’s last
look

time

Alice must have seen Bob’s Flag. A Contradiction

Art of Multiprocessor Programming 72
 Proof of No Deadlock
• If only one pet wants in, it gets in.

Art of Multiprocessor Programming 73

 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 74

 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 backs off, gives
her priority (Alice’s lexicographic privilege)

Art of Multiprocessor Programming 75

 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 76

 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 77

The Arbiter Problem (an aside)

Pick a
point

Pick a
point

Art of Multiprocessor Programming 78

 The Fable Continues
• Alice and Bob fall in love & marry

Art of Multiprocessor Programming 79

 The Fable Continues
• Alice and Bob fall in love & marry
• Then they fall out of love & divorce
– After a coin flip, she gets the pets
– He has to feed them

Art of Multiprocessor Programming 80

 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 81

Bob Puts Food in the Pond

Art of Multiprocessor Programming 82

Alice releases her pets to Feed

mmm… B
mmm…

Art of Multiprocessor Programming 83

 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 84

 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 85

 Surprise Solution

A B
cola

Art of Multiprocessor Programming 86

 Bob puts food in Pond

A B
cola

Art of Multiprocessor Programming 87

 Bob knocks over Can

A B

Art of Multiprocessor Programming 88

 Alice Releases Pets

A yum… B
yum…

Art of Multiprocessor Programming 89

 Alice Resets Can when Pets are
Fed

A B
cola

Art of Multiprocessor Programming 90

 Pseudocode

while (true) {
while ([Link]()){};
[Link]();
[Link]();
[Link]();
}

Alice’s code
Art of Multiprocessor Programming 91
 Pseudocode

while (true) {
while ([Link]()){};
[Link]();
Bob’s code
[Link]();
[Link](); while (true) {
} while ([Link]()){};
[Link]();
[Link]();
}
Alice’s code
Art of Multiprocessor Programming 92
 Correctness
• Mutual Exclusion
– Pets and Bob never together in pond

Art of Multiprocessor Programming 93

 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 94

 Correctness
• Mutual Exclusion safety
– Pets and Bob never together in pond
• No Starvation liveness
if Bob always willing to feed, and pets always
famished, then pets eat infinitely often.
• Producer/Consumer safety
The pets never enter pond unless there is
food, and Bob never provides food if there
is unconsumed food.

Art of Multiprocessor Programming 95

Could Also Solve Using Flags

A B

Art of Multiprocessor Programming 96

 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 97

 The Fable drags on …
• Bob and Alice still have issues

Art of Multiprocessor Programming 98

 The Fable drags on …
• Bob and Alice still have issues
• So they need to communicate

Art of Multiprocessor Programming 99

 The Fable drags on …
• Bob and Alice still have issues
• So they need to communicate
• They agree to use billboards …

Art of Multiprocessor Programming 100

Billboards are Large

B D Letter
A C E
1
3
3
2
Tiles
1
From Scrabble™ box
Art of Multiprocessor Programming 101
Write One Letter at a Time …

W A S
4 1 1

H 4

B D
A C E
1
3
3
2

Art of Multiprocessor Programming 102

 To post a message

W A S H T H E C A R
4 1 1 4 1 4 1 3 1 1

whew

Art of Multiprocessor Programming 103

Let’s send another message

L A
S E L L L A V A 1
1

M PS
1 1 1 1 1 1 4 1

3 3 1

Art of Multiprocessor Programming 104

 Uh-Oh

S E L L
1 1 1 1
T H E
1 4 1
C A R
3 1 1

L 1

OK

Art of Multiprocessor Programming 105

 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 106

 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 107

 Esoteric?
• Java container size() method
• Single shared counter?
– incremented with each add() and
– decremented with each remove()
• Threads wait to exclusively access counter

Art of Multiprocessor Programming 108

 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 109

 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 110

 Amdahl’s Law

1-thread execution time

Speedup= n-thread execution time

Art of Multiprocessor Programming 111

 Amdahl’s Law

1
Speedup=
𝑝
1 −𝑝+
𝑛

Art of Multiprocessor Programming 112

 Amdahl’s Law

Parallel
fraction
1
Speedup=
𝑝
1 −𝑝+
𝑛

Art of Multiprocessor Programming 113

 Amdahl’s Law

Sequential
fraction Parallel
fraction
1
Speedup=
𝑝
1 −𝑝+
𝑛

Art of Multiprocessor Programming 114

 Amdahl’s Law

Sequential
fraction Parallel
fraction
1
Speedup=
𝑝
1 −𝑝+
𝑛
Number of
threads

Art of Multiprocessor Programming 115

Amdal’s Law

Bad synchronization ruins everything

 Example
• Ten processors
• 60% concurrent, 40% sequential
• How close to 10-fold speedup?

Art of Multiprocessor Programming 117

 Example
• Ten processors
• 60% concurrent, 40% sequential
• How close to 10-fold speedup?

1
Speedup = 2.17= 0 .6
1 − 0 .6 +
10

Art of Multiprocessor Programming 118

 Example
• Ten processors
• 80% concurrent, 20% sequential
• How close to 10-fold speedup?

Art of Multiprocessor Programming 119

 Example
• Ten processors
• 80% concurrent, 20% sequential
• How close to 10-fold speedup?

1
Speedup = 3.57= 0 .8
1 − 0 .8 +
10

Art of Multiprocessor Programming 120

 Example
• Ten processors
• 90% concurrent, 10% sequential
• How close to 10-fold speedup?

Art of Multiprocessor Programming 121

 Example
• Ten processors
• 90% concurrent, 10% sequential
• How close to 10-fold speedup?

1
Speedup = 5.26= 0 .9
1 − 0 .9 +
10

Art of Multiprocessor Programming 122

 Example
• Ten processors
• 99% concurrent, 01% sequential
• How close to 10-fold speedup?

Art of Multiprocessor Programming 123

 Example
• Ten processors
• 99% concurrent, 01% sequential
• How close to 10-fold speedup?

1
Speedup = 9.17= 0.99
1 − 0.99 +
10

Art of Multiprocessor Programming 124

 Back to Real-World Multicore
Scaling
Speedup
2x 2.9x
1.8x

User code

Multicore

Not reducing
sequential % of code
Art of Multiprocessor Programming
 Shared Data Structures

Coarse Fine
Grained Grained
25% 25%
Shared Shared

75% 75%
Unshared Unshared
 Shared Data Structures
Honk!
Honk!
Honk!
Why only 2.9 speedup

Coarse Fine
Grained Grained
25% 25%
Shared Shared

75% 75%
Unshared Unshared
 Shared Data Structures
Honk!
Honk! Why fine-grained
Honk! parallelism maters

Coarse Fine
Grained Grained
25% 25%
Shared Shared

75% 75%
Unshared Unshared
 Diminishing Returns
4.5
4
3.5
3
2.5
speedup
2
1.5
1
0.5
0

This course is about the parts that

are hard to make concurrent …
but still have a big influence on speedup!
Art of Multiprocessor Programming