5 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

class Worker extends Thread {

int row, col;

Worker(int row, int col) {

this.row = row; this.col = col;

}

public void run() {

double dotProduct = 0.0;

for (int i = 0; i < n; i++)

dotProduct += a[row][i] * b[i][col];

c[row][col] = dotProduct;

}}}

6 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

class Worker extends Thread {

int row, col;

Worker(int row, int col) {

this.row = row; this.col = col;

}

public void run() {

double dotProduct = 0.0;

for (int i = 0; i < n; i++)

dotProduct += a[row][i] * b[i][col];

c[row][col] = dotProduct;

}}}

a thread

7 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

class Worker extends Thread {

int row, col;

Worker(int row, int col) {

this.row = row; this.col = col;

}

public void run() {

double dotProduct = 0.0;

for (int i = 0; i < n; i++)

dotProduct += a[row][i] * b[i][col];

c[row][col] = dotProduct;

}}}

Which matrix entry to compute

8 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

class Worker extends Thread {

int row, col;

Worker(int row, int col) {

this.row = row; this.col = col;

}

public void run() {

double dotProduct = 0.0;

for (int i = 0; i < n; i++)

dotProduct += a[row][i] * b[i][col];

c[row][col] = dotProduct;

}}}

Actual computation

9 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

void multiply() {

Worker[][] worker = new Worker[n][n];

for (int row …)

for (int col …)

worker[row][col] = new Worker(row,col);

for (int row …)

for (int col …)

worker[row][col].start();

for (int row …)

for (int col …)

worker[row][col].join();

}

10 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

void multiply() {

Worker[][] worker = new Worker[n][n];

for (int row …)

for (int col …)

worker[row][col] = new Worker(row,col);

for (int row …)

for (int col …)

worker[row][col].start();

for (int row …)

for (int col …)

worker[row][col].join();

}

Create nxn threads

11 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

void multiply() {

Worker[][] worker = new Worker[n][n];

for (int row …)

for (int col …)

worker[row][col] = new Worker(row,col);

for (int row …)

for (int col …)

worker[row][col].start();

for (int row …)

for (int col …)

worker[row][col].join();

}

Start them

12 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

void multiply() {

Worker[][] worker = new Worker[n][n];

for (int row …)

for (int col …)

worker[row][col] = new Worker(row,col);

for (int row …)

for (int col …)

worker[row][col].start();

for (int row …)

for (int col …)

worker[row][col].join();

}

Wait for them to finish

13 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication

void multiply() {

Worker[][] worker = new Worker[n][n];

for (int row …)

for (int col …)

worker[row][col] = new Worker(row,col);

for (int row …)

for (int col …)

worker[row][col].start();

for (int row …)

for (int col …)

worker[row][col].join();

}

Wait for them to finish

What’s wrong with this picture?

Start them

Create nxn threads

14 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Thread Overhead

Threads Require resources

Memory for stacks
Setup, teardown

Scheduler overhead
Worse for short-lived threads

15 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Thread Pools

More sensible to keep a pool of long-lived threads
Threads assigned short-lived tasks

Runs the task
Rejoins pool
Waits for next assignment

16 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Thread Pool = Abstraction

Insulate programmer from platform

Big machine, big pool
And vice-versa

Portable code

Runs well on any platform
No need to mix algorithm/platform concerns

17 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

ExecutorService Interface

In java.util.concurrent

Task = Runnable object
If no result value expected
Calls run() method.
Task = Callable<T> object
If result value of type T expected
Calls T call() method.

18 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Future<T>

Callable<T> task = …;

…

Future<T> future = executor.submit(task);

…

T value = future.get();

19 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Future<T>

Callable<T> task = …;

…

Future<T> future = executor.submit(task);

…

T value = future.get();

Submitting a Callable<T> task returns a Future<T> object

20 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Future<T>

Callable<T> task = …;

…

Future<T> future = executor.submit(task);

…

T value = future.get();

The Future’s get() method blocks until the value is available

21 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Future<?>

Runnable task = …;

…

Future<?> future = executor.submit(task);

…

future.get();

22 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Future<?>

Runnable task = …;

…

Future<?> future = executor.submit(task);

…

future.get();

Submitting a Runnable task returns a Future<?> object

23 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Future<?>

Runnable task = …;

…

Future<?> future = executor.submit(task);

…

future.get();

The Future’s get() method blocks until the computation is complete

24 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Note

Executor Service submissions

Like New England traffic signs
Are purely advisory in nature

The executor

Like the New England driver
Is free to ignore any such advice
And could execute tasks sequentially …

25 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition

4 parallel additions

26 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition Task

class AddTask implements Runnable {

Matrix a, b; // multiply this!

public void run() {

if (a.dim == 1) {

c[0][0] = a[0][0] + b[0][0]; // base case

} else {

(partition a, b into half-size matrices a_ij and b_ij)

Future<?> f₀₀ = exec.submit(add(a₀₀,b₀₀));

…

Future<?> f₁₁ = exec.submit(add(a₁₁,b₁₁));

f₀₀.get(); …; f₁₁.get();

…

}}

This is not real Java

code (see notes)

27 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition Task

class AddTask implements Runnable {

Matrix a, b; // multiply this!

public void run() {

if (a.dim == 1) {

c[0][0] = a[0][0] + b[0][0]; // base case

} else {

(partition a, b into half-size matrices a_ij and b_ij)

Future<?> f₀₀ = exec.submit(add(a₀₀,b₀₀));

…

Future<?> f₁₁ = exec.submit(add(a₁₁,b₁₁));

f₀₀.get(); …; f₁₁.get();

…

}}

Base case: add directly

28 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition Task

class AddTask implements Runnable {

Matrix a, b; // multiply this!

public void run() {

if (a.dim == 1) {

c[0][0] = a[0][0] + b[0][0]; // base case

} else {

(partition a, b into half-size matrices a_ij and b_ij)

Future<?> f₀₀ = exec.submit(add(a₀₀,b₀₀));

…

Future<?> f₁₁ = exec.submit(add(a₁₁,b₁₁));

f₀₀.get(); …; f₁₁.get();

…

}}

Constant-time operation

29 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition Task

class AddTask implements Runnable {

Matrix a, b; // multiply this!

public void run() {

if (a.dim == 1) {

c[0][0] = a[0][0] + b[0][0]; // base case

} else {

(partition a, b into half-size matrices a_ij and b_ij)

Future<?> f₀₀ = exec.submit(add(a₀₀,b₀₀));

…

Future<?> f₁₁ = exec.submit(add(a₁₁,b₁₁));

f₀₀.get(); …; f₁₁.get();

…

}}

Submit 4 tasks

30 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition Task

class AddTask implements Runnable {

Matrix a, b; // multiply this!

public void run() {

if (a.dim == 1) {

c[0][0] = a[0][0] + b[0][0]; // base case

} else {

(partition a, b into half-size matrices a_ij and b_ij)

Future<?> f₀₀ = exec.submit(add(a₀₀,b₀₀));

…

Future<?> f₁₁ = exec.submit(add(a₁₁,b₁₁));

f₀₀.get(); …; f₁₁.get();

…

}}

Let them finish

31 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Dependencies

Matrix example is not typical
Tasks are independent

Don’t need results of one task …
To complete another

Often tasks are not independent

32 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Fibonacci

{

n if n < 2

F(n)

F(n-1) + F(n-2) otherwise

Note

potential parallelism
Dependencies

33 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Disclaimer

This Fibonacci implementation is

Egregiously inefficient
So don’t deploy it!
But illustrates our point
How to deal with dependencies

Exercise:

Make this implementation efficient!

34 of 170

Digression…

Efficient Fibonacci in Python

r5 = 5**(.5)

gold = (r5+1)/2

def fib(n):

return round((gold**n-(gold)**(-n))/r5)

35 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multithreaded Fibonacci

class FibTask implements Callable<Integer> {

static ExecutorService exec = Executors.newCachedThreadPool();

int arg;

public FibTask(int n) {

arg = n;

}

public Integer call() {

if (arg > 2) {

Future<Integer> left = exec.submit(new FibTask(arg-1));

Future<Integer> right = exec.submit(new FibTask(arg-2));

return left.get() + right.get();

} else {

return 1;

}}}

36 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multithreaded Fibonacci

class FibTask implements Callable<Integer> {

static ExecutorService exec = Executors.newCachedThreadPool();

int arg;

public FibTask(int n) {

arg = n;

}

public Integer call() {

if (arg > 2) {

Future<Integer> left = exec.submit(new FibTask(arg-1));

Future<Integer> right = exec.submit(new FibTask(arg-2));

return left.get() + right.get();

} else {

return 1;

}}}

Parallel calls

37 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multithreaded Fibonacci

class FibTask implements Callable<Integer> {

static ExecutorService exec = Executors.newCachedThreadPool();

int arg;

public FibTask(int n) {

arg = n;

}

public Integer call() {

if (arg > 2) {

Future<Integer> left = exec.submit(new FibTask(arg-1));

Future<Integer> right = exec.submit(new FibTask(arg-2));

return left.get() + right.get();

} else {

return 1;

}}}

Pick up & combine results

38 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Dynamic Behavior

Multithreaded program is

A directed acyclic graph (DAG)
That unfolds dynamically

Each node is

A single unit of work

39 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Fib DAG

fib(4)

fib(3)

fib(2)

submit

get

fib(2)

fib(1)

40 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Arrows Reflect Dependencies

fib(4)

fib(3)

fib(2)

submit

get

fib(2)

fib(1)

41 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

How Parallel is That?

Define work:

Total time on one processor

Define critical-path length:

Longest dependency path
Can’t beat that!

42 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Fib Work

fib(4)

fib(3)

fib(2)

submit

get

fib(2)

fib(1)

43 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Fib Work

work is 17

44 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Fib Critical Path

fib(4)

fib(3)

fib(2)

submit

get

fib(2)

fib(1)

45 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Fib Critical Path

fib(4)

Critical path length is 8

46 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Notation Watch

T_P = time on P processors
T₁ = work (time on 1 processor)
T_∞ = critical path length (time on ∞ processors)

47 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Simple Bounds

T_P ≥ T₁/P

In one step, can’t do more than P work

T_P ≥ T_∞

Can’t beat infinite resources

48 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

More Notation Watch

Speedup on P processors

Ratio T₁/T_P
How much faster with P processors

Linear speedup

T₁/T_P = Θ(P)

Max speedup (average parallelism)

T₁/T_∞

49 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition

50 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Addition

4 parallel additions

51 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Let A_P(n) be running time

For n x n matrix
on P processors

For example

A₁(n) is work
A_∞(n) is critical path length

52 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Work is

A₁(n) = 4 A₁(n/2) + Θ(1)

4 spawned additions

Partition, synch, etc

53 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Work is

A₁(n) = 4 A₁(n/2) + Θ(1)

= Θ(n²)

Same as double-loop summation

54 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Verify...

A₁(n) = n²

A₁(n) / (4 A₁(n/2)+1) = n²/(4 (n/2)²+1)

= n²/(n²+1) → 1 as n →∞

Check! But also check out

Master_theorem_(analysis_of_algorithms)

On Wikipedia

55 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Critical Path length is

A_∞(n) = A_∞(n/2) + Θ(1)

spawned additions in parallel

Partition, synch, etc

56 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Critical Path length is

A_∞(n) = A_∞(n/2) + Θ(1)

= Θ(log n)

57 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Addition

Verify....

A_∞(n) = log n

A_∞(n) / (A_∞(n/2) + 1) =�(log n)/(log (n/2) + 1) =�(log n/(log n - log 2 + 1)→ 1 � as n →∞

check!

58 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication Redux

59 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Matrix Multiplication Redux

60 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

First Phase …

8 multiplications

61 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Second Phase …

4 additions

62 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multiplication

Work is

M₁(n) = 8 M₁(n/2) + A₁(n)

8 parallel multiplications

Final addition

63 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multiplication

Work is

M₁(n) = 8 M₁(n/2) + Θ(n²)

= Θ(n³)

Same as serial triple-nested loop

64 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multiplication

Verify...

M₁(n) = n³

M₁(n) /( 8 M₁(n/2) + n² ) =

n³ /(8 (n/2)³+n²) =

n³/(n³+n²) → 1 as n →∞

check!

65 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multiplication

Critical path length is

M_∞(n) = M_∞(n/2) + A_∞(n)

Half-size parallel multiplications

Final addition

66 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multiplication

Critical path length is

M_∞(n) = M_∞(n/2) + A_∞(n)

= M_∞(n/2) + Θ(log n)

= Θ(log² n)

67 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Multiplication

Verify...

M_∞(n) = log² n

M_∞(n) /( M_∞(n/2) + log n) =

log² n/(log² (n/2)+log n) =

log² n/((logn-log2)²+log n) =

log² n/(log² n+(1-2 log 2)log n+log² 2) =

log² n/(log² n+...) → 1 as n →∞

check!

68 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Parallelism

M₁(n)/ M_∞(n) = Θ(n³/log² n)
To multiply two 1000 x 1000 matrices

1000³/10²=10⁷

More than number of processors on any real machine (but Fugaku has 7,299,072 cores and is the fastest machine in the world in 2020)

69 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Shared-Memory Multiprocessors

Parallel applications

Do not have direct access to HW processors

Mix of other jobs

All run together
Come & go dynamically

70 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Ideal Scheduling Hierarchy

Tasks

Processors

User-level scheduler

71 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Realistic Scheduling Hierarchy

Tasks

Threads

Processors

User-level scheduler

Kernel-level scheduler

72 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

For Example

Initially,

All P processors available for application

Serial computation

Takes over one processor
Leaving P-1 for us
Waits for I/O
We get that processor back ….

73 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Speedup

Map threads onto P processes
Cannot get P-fold speedup

What if the kernel doesn’t cooperate?

Can try for speedup proportional to

time-averaged number of processors

the kernel gives us

74 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Scheduling Hierarchy

User-level scheduler

Tells kernel which threads are ready

Kernel-level scheduler

Synchronous (for analysis, not correctness!)
Picks p_i threads to schedule at step i
Processor average

over T steps is:

75 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Greed is Good

Greedy scheduler

Schedules as much as it can
At each time step

Optimal schedule is greedy (why?)
But not every greedy schedule is optimal

76 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Theorem

Greedy scheduler ensures that

T ≤ T₁/P_A + T_∞(P-1)/P_A

77 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Deconstructing

T ≤ T₁/P_A + T_∞(P-1)/P_A

78 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Deconstructing

Assume P = P_A

T ≤ T₁/P + T_∞(P-1)/P

When P=1, T=T₁,

as P->∞, T-> T_∞

79 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Deconstructing

T ≤ T₁/P_A + T_∞(P-1)/P_A

Actual time

80 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Deconstructing

T ≤ T₁/P_A + T_∞(P-1)/P_A

Work divided by processor average

81 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Deconstructing

T ≤ T₁/P_A + T_∞(P-1)/P_A

Cannot do better than critical path length

82 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Deconstructing

T ≤ T₁/P_A + T_∞(P-1)/P_A

The higher the average the better it is …

83 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Proof Strategy

Bound this!

84 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Put Tokens in Buckets

idle

work

Processor found work

Processor available but couldn’t find work

85 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

At the end ….

idle

work

Total #tokens =

86 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

At the end ….

idle

work

T₁ tokens

87 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Must Show

idle

work

≤ T_∞(P-1) tokens

88 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Idle Steps

An idle step is one where there is at least one idle processor
Only time idle tokens are generated
Focus on idle steps

89 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Every Move You Make …

Scheduler is greedy
At least one node ready
Number of idle threads in one idle step

At most p_i-1 ≤ P-1

How many idle steps?

90 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Counting Tokens

At most P-1 idle threads per step
At most T_∞ steps (critical path len)
So idle bucket contains at most

T_∞(P-1) tokens

Both buckets contain

T₁ + T_∞(P-1) tokens

91 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Recapitulating

92 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Turns Out

This bound is within a factor of 2 of optimal
Actual optimal is NP-complete

93 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Work Distribution

zzz…

94 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Work Dealing

Yes!

95 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

The Problem with �Work Dealing

D’oh!

96 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Work Stealing

No work…

zzz

Yes!

97 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Lock-Free Work Stealing

Each thread has a pool of ready work
Remove work without synchronizing
If you run out of work, steal someone else’s
Choose victim at random

98 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Local Work Pools

Each work pool is a Double-Ended Queue

99 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

Work DEQueue¹

pushBottom

popBottom

work

1. Double-Ended Queue

100 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

100

Obtain Work

Obtain work
Run thread until
Blocks or terminates

popBottom

101 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

101

New Work

Unblock node
Spawn node

pushBottom

102 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

102

Whatcha Gonna do When the Well Runs Dry?

@&%$!!

empty

103 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

103

Steal Work from Others

Pick random guy’s DEQeueue

104 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

104

Steal this Thread!

popTop

105 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

105

Thread DEQueue

Methods

pushBottom
popBottom
popTop

Never happen concurrently

}

106 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

106

Thread DEQueue

Methods

pushBottom
popBottom
popTop

These are most common – make them fast

(minimize use of CAS)

107 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

107

Ideal

Wait-Free
Linearizable
Constant time

108 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

108

Compromise

Method popTop may fail if

Concurrent popTop succeeds, or a
Concurrent popBottom takes last work

109 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

109

Dreaded ABA Problem

top

CAS

110 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

110

Dreaded ABA Problem

top

111 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

111

Dreaded ABA Problem

top

112 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

112

Dreaded ABA Problem

top

113 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

113

Dreaded ABA Problem

top

114 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

114

Dreaded ABA Problem

top

115 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

115

Dreaded ABA Problem

top

116 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

116

Dreaded ABA Problem

top

CAS

Uh-Oh …

Yes!

117 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

117

Fix for Dreaded ABA

stamp

top

bottom

118 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

118

Bounded DEQueue

public class BDEQueue {

AtomicStampedReference<Integer> top;

volatile int bottom;

Runnable[] tasks;

…

}

119 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

119

Bounded DQueue

public class BDEQueue {

AtomicStampedReference<Integer> top;

volatile int bottom;

Runnable[] tasks;

…

}

Index & Stamp (synchronized)

120 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

120

Bounded DEQueue

public class BDEQueue {

AtomicStampedReference<Integer> top;

volatile int bottom;

Runnable[] deq;

…

}

Index of bottom thread (no need to synchronize

The effect of a write must be seen – so we need a memory barrier)

121 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

121

Bounded DEQueue

public class BDEQueue {

AtomicStampedReference<Integer> top;

volatile int bottom;

Runnable[] tasks;

…

}

Array holding tasks

122 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

122

pushBottom()

public class BDEQueue {

…

void pushBottom(Runnable r){

tasks[bottom] = r;

bottom++;

}

…

}

123 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

123

pushBottom()

public class BDEQueue {

…

void pushBottom(Runnable r){

tasks[bottom] = r;

bottom++;

}

…

}

Bottom is the index to store the new task in the array

124 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

124

pushBottom()

public class BDEQueue {

…

void pushBottom(Runnable r){

tasks[bottom] = r;

bottom++;

}

…

}

Adjust the bottom index

stamp

top

bottom

125 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

125

Steal Work

public Runnable popTop() {

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = oldTop + 1;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom <= oldTop)

return null;

Runnable r = tasks[oldTop];

if (top.CAS(oldTop, newTop, oldStamp, newStamp)) return r;

return null;

}

126 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

126

Steal Work

public Runnable popTop() {

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = oldTop + 1;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom <= oldTop)

return null;

Runnable r = tasks[oldTop];

if (top.CAS(oldTop, newTop, oldStamp, newStamp)) return r;

return null;

}

Read top (value & stamp)

127 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

127

Steal Work

public Runnable popTop() {

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = oldTop + 1;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom <= oldTop)

return null;

Runnable r = tasks[oldTop];

if (top.CAS(oldTop, newTop, oldStamp, newStamp)) return r;

return null;

}

Compute new value & stamp

128 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

128

Steal Work

public Runnable popTop() {

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = oldTop + 1;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom <= oldTop)

return null;

Runnable r = tasks[oldTop];

if (top.CAS(oldTop, newTop, oldStamp, newStamp)) return r;

return null;

}

Quit if queue is empty

stamp

top

bottom

129 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

129

Steal Work

public Runnable popTop() {

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = oldTop + 1;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom <= oldTop)

return null;

Runnable r = tasks[oldTop];

if (top.CAS(oldTop, newTop, oldStamp, newStamp)) return r;

return null;

}

Try to steal the task

stamp

top

CAS

bottom

130 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

130

Steal Work

public Runnable popTop() {

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = oldTop + 1;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom <= oldTop)

return null;

Runnable r = tasks[oldTop];

if (top.CAS(oldTop, newTop, oldStamp, newStamp)) return r;

return null;

}

Give up if

conflict occurs

131 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

131

Take Work

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

132 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

132

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

Make sure queue is non-empty

133 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

133

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

Prepare to grab bottom task

134 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

134

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

Read top, & prepare new values

135 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

135

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

return null;

}

Take Work

If top & bottom 1 or more

apart, no conflict

stamp

top

bottom

136 of 170

Art of Multiprocessor Programming© Herlihy –Shavit 2007

136

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

At most one item left

stamp

top

bottom

137 of 170

137

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

Try to steal last item.

In any case reset Bottom

because the DEQueue will be empty

even if unsucessful (why?)

138 of 170

138

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

failed to get last item

Must still reset top

139 of 170

139

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

stamp

top

CAS

bottom

I win CAS

140 of 170

140

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

stamp

top

CAS

bottom

I lose CAS

Thief must

have won…

141 of 170

141

Runnable popBottom() {

if (bottom == 0) return null;

bottom--;

Runnable r = tasks[bottom];

int[] stamp = new int[1];

int oldTop = top.get(stamp), newTop = 0;

int oldStamp = stamp[0], newStamp = oldStamp + 1;

if (bottom > oldTop) return r;

if (bottom == oldTop){

bottom = 0;

if (top.CAS(oldTop, newTop, oldStamp, newStamp))

return r;

}

top.set(newTop,newStamp); return null;

}

Take Work

failed to get last item

Must still reset top

142 of 170

142

Old English Proverb

“May as well be hanged for stealing a sheep as a goat”
From which we conclude

Stealing was punished severely
Sheep were worth more than goats

143 of 170

143

Variations

Stealing is expensive

Pay CAS
Only one thread taken

What if

Randomly balance loads?

144 of 170

144

Work Balancing

b2+5 c/2=3

d2+5e/2=4

145 of 170

145

Work-Balancing Thread

public void run() {

int me = ThreadID.get();

while (true) {

Runnable task = queue[me].deq();

if (task != null) task.run();

int size = queue[me].size();

if (random.nextInt(size+1) == size) {

int victim = random.nextInt(queue.length);

int min = …, max = …;

synchronized (queue[min]) {

synchronized (queue[max]) {

balance(queue[min], queue[max]);

}}}}}

146 of 170

146

Work-Balancing Thread

public void run() {

int me = ThreadID.get();

while (true) {

Runnable task = queue[me].deq();

if (task != null) task.run();

int size = queue[me].size();

if (random.nextInt(size+1) == size) {

int victim = random.nextInt(queue.length);

int min = …, max = …;

synchronized (queue[min]) {

synchronized (queue[max]) {

balance(queue[min], queue[max]);

}}}}}

Keep running tasks

147 of 170

147

Work-Balancing Thread

public void run() {

int me = ThreadID.get();

while (true) {

Runnable task = queue[me].deq();

if (task != null) task.run();

int size = queue[me].size();

if (random.nextInt(size+1) == size) {

int victim = random.nextInt(queue.length);

int min = …, max = …;

synchronized (queue[min]) {

synchronized (queue[max]) {

balance(queue[min], queue[max]);

}}}}}

With probability

1/|queue|

148 of 170

148

Work-Balancing Thread

public void run() {

int me = ThreadID.get();

while (true) {

Runnable task = queue[me].deq();

if (task != null) task.run();

int size = queue[me].size();

if (random.nextInt(size+1) == size) {

int victim = random.nextInt(queue.length);

int min = …, max = …;

synchronized (queue[min]) {

synchronized (queue[max]) {

balance(queue[min], queue[max]);

}}}}}

Choose random victim

149 of 170

149

Work-Balancing Thread

public void run() {

int me = ThreadID.get();

while (true) {

Runnable task = queue[me].deq();

if (task != null) task.run();

int size = queue[me].size();

if (random.nextInt(size+1) == size) {

int victim = random.nextInt(queue.length);

int min = …, max = …;

synchronized (queue[min]) {

synchronized (queue[max]) {

balance(queue[min], queue[max]);

}}}}}

Lock queues in canonical order

150 of 170

150

Work-Balancing Thread

public void run() {

int me = ThreadID.get();

while (true) {

Runnable task = queue[me].deq();

if (task != null) task.run();

int size = queue[me].size();

if (random.nextInt(size+1) == size) {

int victim = random.nextInt(queue.length);

int min = …, max = …;

synchronized (queue[min]) {

synchronized (queue[max]) {

balance(queue[min], queue[max]);

}}}}}

Rebalance queues

151 of 170

151

Work Stealing & Balancing

Clean separation between app & scheduling layer
Works well when number of processors fluctuates.
Works on “black-box” operating systems

152 of 170

152

153 of 170

153

I AM

LORD

VOLDEMORT

154 of 170

154

Limitations of Java Futures

import java.util.concurrent.*;

public class FibExec {

final static ExecutorService exec =

Executors.newFixedThreadPool(400);

static int fcall(int n) throws Exception {

if(n < 2)

return n;

Future<Integer> f1 = exec.submit(()->fcall(n-1));

int n2 = fcall(n-2);

return f1.get()+n2;

}

public static void main(String[] args) throws Exception {

for(int n=0;n<=45;n++) {

final int fibn = n;

Future<Integer> fib = exec.submit(()->fcall(fibn));

System.out.printf("fib(%d)=%d%n",n,fib.get());

}

exec.shutdown();

}}

155 of 170

155

Limitations of Java Futures

Eventually Blocks
Java implementation can only handle Fib(15) or so

156 of 170

156

Better Java "Futures"

import java.util.concurrent.*;

public class FibExec2 {

final static ExecutorService exec = new ForkJoinPool(8);

static int fcall(int n) throws Exception {

if(n < 2) return n;

Future<Integer> f1 = exec.submit(()->fcall(n-1));

int n2 = fcall(n-2);

return f1.get()+n2;

}

public static void main(String[] args) throws Exception {

for(int n=0;n<=45;n++) {

final int fibn = n;

System.out.printf("fib(%d)=%d%n",n,fcall(n));

}

exec.shutdown();

}}

157 of 170

157

Limitations of Java Futures

It is still based on blocking operations.
Relies on sophisticated ExecutorService to work well

158 of 170

158

Better Java "Futures" v3

public class FibExec3 {

final static ExecutorService exec = new ForkJoinPool(8);

public static<T> CompletableFuture<T> supplyAsyncFut(

Supplier<CompletableFuture<T>> supplier,

Executor executor) {...}

static CompletableFuture<Integer> fcall(int n) {

if (n < 2) return CompletableFuture.completedFuture(n);

CompletableFuture<Integer> f1 = supplyAsyncFut(()->fcall(n-1), exec);

CompletableFuture<Integer> f2 = fcall(n - 2);

return f1.thenCombine(f2, (a, b) -> a + b);

}}

159 of 170

159

Where

public static<T> CompletableFuture<T> supplyAsyncFut(

Supplier<CompletableFuture<T>> supplier,

Executor executor) {

final CompletableFuture<T> result = new CompletableFuture<>();

CompletableFuture.runAsync(() -> {

supplier.get().thenAccept((v) -> {

result.complete(v);

});

}, executor);

return result;

}

160 of 170

160

Better Java "Futures" v4

import java.util.concurrent.CompletableFuture;

import java.util.concurrent.Executor;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.ForkJoinPool;

import java.util.function.Supplier;

public class FibExec4 {

final static ExecutorService exec = new ForkJoinPool(8);

public static long fcallSync(int n) {

if( n < 2 ) return 1L;

return fcallSync(n-1) + fcallSync(n-2);

}

static CompletableFuture<Long> fcall(int n) {

if (n < 2) return CompletableFuture.completedFuture((long)n);

if (n < 23) return CompletableFuture.completedFuture(fcallSync(n));

final CompletableFuture<Long> f1 = supplyAsyncFut(()->fcall(n-1), exec);

final CompletableFuture<Long> f2 = fcall(n - 2);

return f1.thenCombine(f2, (a, b) -> a + b);

}

161 of 170

161

Futures in C++

#include <future>

#include <iostream>

int fib(int n) {

if(n < 2) return n;

std::future<int> n1 = std::async(std::launch::async,fib,n-1);

int n2 = fib(n-2);

return n1.get()+n2;

}

int main() {

for(int n=0;n<=45;n++) {

std::cout << "fib(" << n << ")=" << fib(n) << std::endl;

}

return 0;

}

162 of 170

162

Futures in C++

$ g++ -std=c++11 fibfut.cc -lpthread

$ ./a.out

fib(0)=0

fib(1)=1

fib(2)=1

fib(3)=2

fib(4)=3

fib(5)=5

fib(6)=8

fib(7)=13

fib(8)=21

...

Can handle fib(19) or so

163 of 170

163

Futures in C++

#include <future>

#include <iostream>

int fib(int n) {

if(n < 2) return n;

if(n > 23) {

std::future<int> n1 = std::async(std::launch::async,fib,n-1);

int n2 = fib(n-2);

return n1.get()+n2;

} else return fib(n-1)+fib(n-2);

}

int main() {

for(int n=0;n<=45;n++)

std::cout << "fib(" << n << ")=" << fib(n) << std::endl;

return 0;

}

164 of 170

164

Futures in C++

$ g++ -std=c++11 fibfut.cc -lpthread

$ ./a.out

fib(0)=0

fib(1)=1

fib(2)=1

fib(3)=2

fib(4)=3

fib(5)=5

fib(6)=8

fib(7)=13

fib(8)=21

...

Can handle fib(41) or so

165 of 170

165

Futures in C++

HPX
Main page - http://stellar.cct.lsu.edu
Source code - https://github.com/STEllAR-GROUP/hpx
Provides distributed futures-based computation for C++
Futures have .then() member, which does the job of continuations.

166 of 170

166

Futures in C++

#include <hpx/hpx.hpp>

#include <hpx/hpx_main.hpp>

#include <iostream>

int fib(int n) {

if(n < 2) return n;

if(n > 23) {

hpx::future<int> n1 = hpx::async(fib,n-1);

int n2 = fib(n-2);

return n1.get()+n2;

} else return fib(n-1)+fib(n-2);

}

int main(int argc,char **argv) {

for(int n=0;n<=45;n++)

std::cout << "fib(" << n << ")=" << fib(n) << std::endl;

return 0;

}

167 of 170

167

Actor Model

Actors are objects that communicate with asynchronous messages
In response to a message,

an actor may change state
create more actors
send more messages

168 of 170

168

Actor Model Implementation

Messages are method calls
Each actor has a queue

Process incoming messages one at a time, gives coarse-grained concurrency

Return values are futures
No deadlocks, many races avoided, objects can move

169 of 170

169

High Performance Computing

Actors can move for load balancing
Asynchronous workflow between objects hides latency
Primary concept for Charm++

170 of 170

170

�This work is licensed under a 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.