Amdahl’s Law: Revisited

1
𝑆𝑃 =
(1 − 𝑠)
𝑠+
𝑃
𝑠 = fraction of serial code

serial execution time

Speedup =
parallel execution time

Photo: [Link]
Amdahl’s Law: Revisited
1
𝑆𝑃 =
(1 − (𝑠 + 𝑜(𝑃)))
(𝑠 + 𝑜(𝑃)) +
𝑃
𝑠 = fraction of serial code
𝑜(𝑃) = overhead for P processors
Gustafson’s Law (1988) John Gustafson

Scaled speedup
𝑠 = fraction of serial code
𝑠+𝑝∙𝑃 𝑝 = 1 − 𝑠 = fraction of parallel code
𝑆𝑃 = = 𝑠 + 𝑝𝑃
1
Time on 1 proc
=s+p∙P
s p∙P

s p Time on P processors = s + p = 1

Photo: [Link]
Using parallelism to solve a larger problem in the same amount of time.
How does problem size scale?
Problem size N
Serial time:

𝑡 = 𝑐𝑁 𝑥
With P processors,
grow problem size by
a factor m:

𝑡 = 𝑐(𝑚𝑁)𝑥 /𝑃
Setting both times equal...

𝑚 = 𝑃1/𝑥

E.g., if computational complexity is 𝑂(𝑁 3 ), would need 1000 processors

to solve a problem 10x larger in the same time.
 Primary Programming Models

Shared Memory Message Passing

K. Bobrov, Grokking Concurrency, 2024

 Task 0 Task 1
Compute A, B Print A+B
Print all done
 Task 0 Task 1
Compute A, B Print A+B
Print all done

Task 0 Task 1
Compute A, B Print A+B Dependencies

Print all done

 Task 0 Task 1
Compute A, B Print A+B
Print all done

Task 0 Task 1
Compute A, B Print A+B Dependencies

Print all done

Task 0 Task 1 time

Ordering
Compute A, B
Print A+B Communication
Print all done
 main

0
ST 0,signal doSum
create 0
LD signal
0
LD signal
0
LD signal
5 0
ST 5,a LD signal
3 0
ST 3,b LD signal
0
1 LD signal
ST 1,signal 1
LD signal
1 5
LD signal LD a
1 3
LD signal LD b
1
LD signal print “8”
1 0
LD signal ST 0,signal
0
LD signal
print “done”

MEMORY
 main

fork doSum
ST 5,a recv 0,a,b
ST 3,b
send 1,a,b
wait print “8”

print “done”
 Based on this example, what are some
main
pros and cons of shared memory vs.
ST 0,signal
0
doSum message passing?
create 0
LD signal
0
LD signal
0
LD signal
5 0
ST 5,a LD signal
0 main
3 LD signal
ST 3,b
0
1 LD signal
ST 1,signal 1 fork doSum
LD signal
1 5 recv 0,a,b
LD signal LD a ST 5,a
1 3
LD signal LD b ST 3,b
1
LD signal print “8” send 1,a,b
1 0
LD signal ST 0,signal wait print “8”
0
LD signal
print “done” print “done”

MEMORY
Matrix Multiply

element 𝒊, 𝒋
element 𝒊, 𝒋 row 𝒊 col 𝒋
row 𝒊

col 𝒋

Y = A ∗ B
Shared Memory P=2 This illustration is based on

Parallel Strategy Code 2.4.

Task 0 * * Task 1

element 𝒊, 𝒋
+=

+=

col 𝒋

Y = row 𝒊
A ∗ B
Shared Memory

1. create two tasks

2. divide iterations between tasks
3. wait for all tasks to complete
Shared Memory
Task 0 Task 1

for k = 0..(N/2-1) for k = N/2..(N-1)

LD R1, A[i][k] LD R1, A[i][k]
LD R2, B[k][j] LD R2, B[k][j]
R1 = R1 * R2 R1 = R1 * R2
LD R3, Y[i][j] LD R3, Y[i][j]
R3 = R1 + R3 R3 = R1 + R3
ST R3, Y[i][j] ST R3, Y[i][j]
Shared Memory
Task 0 Task 1 Problem #1:
Each task needs its
for k = 0..(N/2-1) for k = N/2..(N-1) own value of k, but it’s
LD R1, A[i][k] LD R1, A[i][k] in shared memory.
LD R2, B[k][j] LD R2, B[k][j]
R1 = R1 * R2 R1 = R1 * R2
LD R3, Y[i][j] LD R3, Y[i][j]
R3 = R1 + R3 R3 = R1 + R3
ST R3, Y[i][j] ST R3, Y[i][j]
Privatization
 Shared Memory
Task 0 Task 1 Problem #2:
Conflicting access
for k[0] = 0..(N/2-1) for k[1] = N/2..(N-1) to Y[i][j]. Must be ordered
LD R1, A[i][k[0]] LD R1, A[i][k[1]] properly to get the
LD R2, B[k[0]][j] LD R2, B[k[1]][j] correct answer.
R1 = R1 * R2 R1 = R1 * R2
LD R3, Y[i][j] LD R3, Y[i][j]
R3 = R1 + R3 R3 = R1 + R3
ST R3, Y[i][j] ST R3, Y[i][j]
Critical section
Only one thread can execute the code at a time.
Implemented with locks or atomic operations (e.g., fetch-and-add).

Performance: Forces serial execution of this code -- not parallel!

 Shared Memory
Task 0 Task 1 Problem #2:
Conflicting access
for k[0] = 0..(N/2-1) for k[1] = N/2..(N-1) to Y[i][j]. Must be ordered
LD R1, A[i][k[0]] LD R1, A[i][k[1]] properly to get the
LD R2, B[k[0]][j] LD R2, B[k[1]][j] correct answer.
R1 = R1 * R2 R1 = R1 * R2
critical critical
LD R3, Y[i][j]
R3 = R1 + R3
ST R3, Y[i][j]
end critical LD R3, Y[i][j]
R3 = R1 + R3
ST R3, Y[i][j]
end critical
What sort of speedup would
you expect from this code?
Are there performance
bottlenecks?
Think of a few suggestions
on how to improve the
performance.
Message Passing This illustration is based on
Parallel Strategy P=2 Code 2.5 (but not exactly).

Task 0 * * Task 1

+= temp
temp +=

+
col 𝒋

B0
element 𝒊, 𝒋 row 𝒊

Y0 = A0 A1 ∗
B1
In this code, both tasks (processes) allocate memory for all variables.
These are private variables, and each task has its own address space.

Assumption: Task 0 has all input data (A, B),

and only Task 0 will contain all output data (Y).
“right half” of A
columns N/2-1 .. N-1
“bottom half” of B
rows N/2-1 .. N-1
Each task computes its local portion of the inner-product.
Task 0 collects the partial inner-product from Task 1.
Adds to its own result, and stores in Y.
Blocking vs.
non-blocking
What happens if
Task 0 gets interrupted
and swapped out for an
extended time?

Does Task 1 keep going?

Think of a few suggestions
on how to improve the
performance.