Session 16¶

Topic 2: The Go language¶

Today¶

Performance & scalability¶

metrics
strong scalability
weak scalability
case studies

Performance & scalability¶

Goal of measuring parallel performance¶

you parallelized your code — but it barely runs faster!
how do you know how much faster it should be?
we need to quantify “good” & “bad” performance:
what is a baseline runtime?
what if we had infinite parallel compute resources?
when is the algorithm as fast as possible?

Example: AXPY¶

for i := 0; i < n; i++ {
  y[i] += a * x[i]
}

\(n = 10^9\) → runs in \(T = 128\) seconds on one core
is \(T = 128\) the fastest it gets?
what about a larger problem: \(n = 10^{18}\)?
what about more cores: \(p = 2, 4, \ldots, 128\) and beyond?

Differences: scalability vs. peak performance¶

scalability tells how well a program uses more processors
peak performance tells how close the program runs to hardware limits

Concept	Focus	Metric
scalability	behavior across cores	speedup, efficiency
peak performance	hardware utilization	% of theoretical FLOPs

🧠 remember: a program could scale perfectly (double cores → half time) but still use only 5% of peak FLOPs due to memory bandwidth bottlenecks

Measuring peak performance¶

to measure percentage of peak in practice:

determine the theoretical peak (e.g., FLOPs/s from CPU or GPU specs)
measure achieved performance: count floating-point operations, then divide by the runtime
compare with peak

\[ \text{\% of peak} = 100 \times \frac{\text{measured FLOPs/s}}{\text{theoretical peak FLOPs/s}} \]

💡 reality check: Top HPC benchmarks often achieve 60–80% of peak. Real-world applications are much lower (10–30%). Especially memory-bound problems can be in single digits.

Parallel scalability¶

Metrics: speedup and efficiency¶

\(n\) is the problem size
\(p\) is the number of processors
\(T_{n}(1)\) is the best sequential time

some problems are too big for sequential execution, then use

\(T_{n,\text{best}} = T_{n}(p)\) as baseline for a suitable \(p > 1\)

Speedup¶

\[ S_p = \frac{T_{n}(1)}{T_{n}(p)} \]

Efficiency¶

\[ E_p = \frac{S_p}{p} = \frac{T_{n}(1)}{p\,T_{n}(p)} \]

Ideal speedup and efficiency¶

\[ \text{Def:}\quad S_p = \frac{T_{n}(1)}{T_{n}(p)} \quad\text{and}\quad E_p = \frac{S_p}{p} = \frac{T_{n}(1)}{p\,T_{n}(p)} \]

ideal (linear) scaling: \(S_p \propto p \Leftrightarrow E_p = 1\)
real scaling: often \(E_p < 1\) … due to overheads: worker creation, communication, synchronization, etc.

💡 reality check: even on the fastest supercomputers some algorithms may achieve only ~70% efficiency

Our goals¶

estimate speedup & efficiency theoretically
measure speedup & efficiency experimentally

Next: the framework to do this

Strong and weak scalability¶

Amdahl’s law – the max speedup¶

some part of the code is sequential — it cannot be parallelized

\[ T_{n}(p) = \alpha T_{n}(1) + (1 - \alpha) T_{n}(1) \frac{1}{p} \]

sequential part: \(~\alpha T_{n}(1)\)
parallelizable part: \(~(1 - \alpha) T_{n}(1) \frac{1}{p}~\) (idealized)

How the speedup dream breaks¶

substituting

\[ T_{n}(p) = \alpha T_{n}(1) + (1 - \alpha) T_{n}(1) \frac{1}{p} \]

into the formula for speedup, gives us the max speedup:

\[ S_p = \frac{T_{n}(1)}{T_{n}(p)} = \frac{1}{\alpha + \frac{1 - \alpha}{p}} \]

How to read the interactive diagram showing Amdahl’s law:

\(\alpha\) is the sequential fraction — the share of work that cannot be distributed across processors. Drag it up and down to see how dramatically it shifts the ceiling.
\(p\) is the number of processors. Notice that early doubling of \(p\) (1 → 2, 2 → 4) give big gains, but each subsequent doubling yields diminishing returns.
The theoretical max (shown in the cards) is what you’d get with infinite processors — it equals \(1 / \alpha\). So even with 90% parallelism, you can never exceed 10× speedup no matter what.
The green dashed line is the ideal linear scaling — what you’d get if 100% of the work were parallelizable. Real programs always fall below it.

Consequence of Amdahl¶

even with infinite processors (\(p \rightarrow \infty\)):

\[ S_p \rightarrow \frac{1}{\alpha} \]

→ if \(95\%\) is parallel, \(\alpha = 0.95\), max speedup \(= 20\times\)

🧠 remember: the serial fraction limits you forever!

—

💡 fun fact: Gene Amdahl stated this in 1967 — the same year the first ATM was installed

Reference:

Amdahl, Gene M. (1967). “Validity of the single processor approach to achieving large scale computing capabilities”. Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS ’67 (Spring). pp. 483–485. doi:10.1145/1465482.1465560

Gustafson’s law – escaping Amdahl¶

what if we increase the problem size along with the number of processors?

sequential work stays roughly constant with \(n\)
parallel work scales linearly with \(n\)

\[ T_{n}(1) = T_{0} + T_{\shortparallel}\,n \]

Gustafson states

\[ T_{n}(p) = T_{0} + T_{\shortparallel} \frac{n}{p} \]

Amdahl → Gustafson¶

Amdahl (1967):

\[ T_{n}(p) = \alpha T_{n}(1) + (1 - \alpha) T_{n}(1) \frac{1}{p} \]

Gustafson (1988):

\[ T_{n}(p) = T_{0} + T_{\shortparallel} \frac{n}{p} \]

A weak notion of speedup¶

substituting

\[ T_{n}(p) = T_{0} + T_{\shortparallel} \frac{n}{p} \]

into the formula for speedup, gives us the max weak speedup: simultaneously increase \(n = cp\) (\(c\) is fixed)

\[ S_{n,p} = \frac{T_{n}(1)}{T_{n}(p)} = \frac{T_{0} + T_{\shortparallel}\,n}{T_{0} + T_{\shortparallel} \frac{n}{p}} = \frac{T_{0} + T_{\shortparallel}\,cp}{T_{0} + T_{\shortparallel}\,c} \]

\[ S_{n,p} = \frac{T_{0} + T_{\shortparallel}\,cp}{T_{0} + T_{\shortparallel}\,c} = \gamma + (1 - \gamma) p \]

with

\[ \gamma = \frac{T_{0}}{T_{0} + T_{\shortparallel}\,c} \quad\text{and}\quad (1 - \gamma) = \frac{T_{\shortparallel}\,c}{T_{0} + T_{\shortparallel}\,c} \]

Fixed problem size → scaled problem size¶

Amdahl (1967):

\[ S_p = \frac{1}{\alpha + \frac{1 - \alpha}{p}} < \frac{1}{\alpha} \quad\text{for all } p \]

Gustafson (1988):

\[ S_{n,p} = \gamma + (1 - \gamma) p \propto p \]

Consequence of Gustafson¶

parallel portion dominates!

more processors → more total work
constant work per processor
communication overheads are amortized

💡 idea: don’t just make it faster — make it bigger

Reference:

Gustafson, John L. (1988). “Reevaluating Amdahl’s Law”. Communications of the ACM. 31 (5): 532–3. doi:10.1145/42411.42415

Example: parallel mean¶

parallel local computation:

mean_local[j] = 0.0;
for i=lo[j]; i<hi[j]; i++ {
  mean_local[j] += y[i];
}

sequential reduction:

mean_global = 0.0;
for j=0; j<p; j++ {
  mean_global += mean_local[j];
}

what if \(n\) is fixed and \(p\) increases? → Amdahl
what if \(n\) and \(p\) grow together? → Gustafson

Strong vs weak scalability¶

Amdahl → strong scalability¶

fix \(n\)
increase \(p\)
measures how efficiently a fixed problem runs on more processors

Gustafson → weak scalability¶

increase both \(n\) and \(p\) proportionally
measures how performance holds when the problem size per processor stays constant

Real-world challenges¶

even if the math looked great…

communication overhead: data transfers cost time
synchronization delays: one slow task can stall everyone
network topology: neighboring processors in code may be far apart in hardware
load imbalance: some processors do more work
memory bandwidth limits: cores compete and “starve”

💡 fun fact: On supercomputers like Frontier, even nearby ranks can be in different compute racks connected by kilometers of cables!

What makes an algorithm scalable¶

minimize sequential work
balance workloads evenly
overlap communication with other computation (which must be independent of the comm.)
strong scaling can be limited → scale the problem size when possible

Case studies¶

We look at two regimes¶

computation bound
communication bound

key considerations:

Flops — floating point operations: add/multiply
Memory — how much memory is read → written

Case study 1: Computation bound¶

Characterizing compute bound¶

small amounts of memory in/out, but large numbers of Flops
many independent operations, results in small amounts of synchronization or communication

Why compute bound matters¶

1. Strong scaling works well here!¶

… because the workload is dominated by computation:

parallelizing across processors is effective
less waiting on memory or communication

→ these are the best-case scenarios for Amdahl-style scaling

2. Hardware utilization is high¶

CPUs/GPUs stay busy doing useful work; less idle time waiting on:

memory
network
disk

→ ideal for accelerators that can handle massive parallel arithmetic (GPUs, TPUs)

Hands-on: scalability for a compute bound problem¶

func doWork(start, end int64) float64 {
    sum := 0.0
    for i := start; i < end; i++ {
        sum += math.Sqrt(float64(i))
    }
    return sum
}

with

i = 0, ..., 10_000_000_000 = problemSize

(Note: The line above is pseudocode, not actual Go code.)

How to split the work?¶

// fix load per worker
chunkSize := problemSize / int64(numWorkers)

for i := range numWorkers {
    lo := int64(i) * chunkSize
    hi := lo + chunkSize
    if i == numWorkers-1 {
        hi = problemSize
    }
    wg.Add(1)
    go func(start, end int64) {
        defer wg.Done()
        doWork(start, end)
    }(lo, hi)
}

(code/go/scalability_staticload)

Case study 2: Communication bound¶

… next time

Key takeaways¶

1. Amdahl’s law and max strong speedup¶

\[ T_{n}(p) = \alpha T_{n}(1) + (1 - \alpha) T_{n}(1) \frac{1}{p}, \]

where \(n\), the problem size, stays fixed

\[ S_p = \frac{T_{n}(1)}{T_{n}(p)} = \frac{1}{\alpha + \frac{1 - \alpha}{p}} \]

2. Gustafson’s law and max weak speedup¶

\[ T_{n}(p) = T_{0} + T_{\shortparallel} \frac{n}{p} \]

where \(n\), the problem size, scales with \(p\)

\[ S_{n,p} = \frac{T_{n}(1)}{T_{n}(p)} = \gamma + (1 - \gamma) p \]

Looking ahead¶

case studies with parallel algorithms

developing parallel algorithms for common problems
analyzing scalability in practice

Prepare for the next session 🌱¶

sessions/17-todo