17 Speedup vs resources#
What this notebook is about#
In Notebook 16 you wrote #SBATCH --ntasks=? and --cpus-per-task=? and simply
guessed the numbers. This notebook answers the question properly, and it does
so with the one bash skill that runs through all of Part II: extract a table and
compute on it with awk. The scaling ideas (efficiency, Amdahl, the knee) are
just enough context to read the numbers; this is a shell notebook, not a
parallel-computing course.
The data is a table of (cores, walltime) for the same job run on different
core counts, physics-optional, as ever. We will treat it as a strong-scaling
benchmark of a DFT geometry optimization on Euler (ETH Zürich), but you need
know nothing about the calculation: it is a column of cores and a column of
seconds. From it you will compute speedup and efficiency, find where adding cores
stops paying off, and write the short data-backed paragraph that justifies an
allocation request.
About this dataset
The timing table is synthetic: generated (data/scaling/generate.py) from an
Amdahl model with light, reproducible noise, so the exercises are cleanly gradeable
while the curve still looks measured. Its schema (cores,walltime_s) is the plain
one a real benchmark produces, so real anonymized scaling data could replace it with
no change to a single command below.
A. The question: how many cores?#
The temptation is to ask for as many cores as possible: surely more is faster? It is not, and the cost makes the mistake expensive. A cluster bills you in core-hours:
core-hours = cores × walltime.
A job on 256 cores for 1 hour costs 256 core-hours, the same as 1 core for 256 hours. So if doubling the cores does not roughly halve the walltime, you are paying double for little gain, and on a finite allocation, burning hours you will want later. The whole notebook is about finding the core count where you are still getting your money’s worth, and stopping there.
B. Strong scaling from data#
Here is the sweep: one row per run, the same problem on more and more cores. It is
a CSV with a header line, so we will tell awk to use comma as the separator:
cat data/scaling/strong_scaling.csv
cores,walltime_s
1,7200
2,3781
4,1952
8,1021
16,584
32,368
64,249
128,197
256,170
Two derived quantities turn this into an answer. Speedup is how many times faster
you got relative to one core, S(N) = T(1) / T(N); efficiency is how much of
each core you are actually using, E(N) = S(N) / N. E = 1 (100%) is the ideal,
where N cores give exactly N× the speed. Both are pure arithmetic on the table, so
awk computes them in one pass: -F, sets the comma separator, and we skip the
header row and capture the 1-core baseline T(1):
awk -F, '
NR == 1 { next } # skip the header line
{ if (t1 == "") t1 = $2 # first data row is the 1-core baseline
S = t1 / $2 # speedup S(N) = T(1)/T(N)
E = S / $1 # efficiency E(N) = S/N
printf "%6d %9d %8.1f %7.0f%%\n", $1, $2, S, E*100 }
BEGIN { printf "%6s %9s %8s %8s\n", "cores", "time_s", "speedup", "efficncy" }
' data/scaling/strong_scaling.csv
cores time_s speedup efficncy
1 7200 1.0 100%
2 3781 1.9 95%
4 1952 3.7 92%
8 1021 7.1 88%
16 584 12.3 77%
32 368 19.6 61%
64 249 28.9 45%
128 197 36.5 29%
256 170 42.4 17%
Read down the efficiency column and the story jumps out: near-perfect at first, then a steady decline. Here it is as a picture:
cores speedup parallel efficiency E = S(N)/N
1 1.0× ████████████████████ 100%
2 1.9× ███████████████████ 95%
4 3.7× ██████████████████ 92%
8 7.1× ██████████████████ 88%
16 12.3× ███████████████ 77% ◀ knee (E still ≥ 75%)
32 19.6× ████████████ 61%
64 28.9× █████████ 45%
128 36.5× ██████ 29%
256 42.4× ███ 17% nearing the Amdahl ceiling (~50×)
ideal speedup would be S = N (linear); the gap is the serial fraction
The knee is the useful core count: the largest N where efficiency is still
respectable: convention puts the line around 75–80%. Past it, you spend cores
to buy almost nothing. Find it directly: the largest N with E ≥ 0.75:
awk -F, '
NR == 1 { next }
{ if (t1 == "") t1 = $2
if ((t1/$2)/$1 >= 0.75) knee = $1 }
END { print "knee (largest core count with E >= 0.75):", knee, "cores" }
' data/scaling/strong_scaling.csv
knee (largest core count with E >= 0.75): 16 cores
16 cores. Up to there each added core still pulls its weight; beyond it, efficiency slides (61% at 32, 45% at 64) because a fixed, un-parallelizable slice of the work is becoming an ever-larger share of the shrinking remainder. That slice has a name, and a law.
C. Why it bends: Amdahl’s law#
The bend is not bad luck; it is arithmetic. Almost every job has a serial
fraction s (setup, I/O, reductions) that cannot be parallelized. If a fraction
s of the work is stuck on one core and the rest (1 − s) splits perfectly, then
S(N) = 1 / ( s + (1 − s)/N ) (Amdahl’s law).
As N → ∞, the (1 − s)/N term vanishes and speedup hits a ceiling of 1/s,
no matter how many cores you throw at it. You can estimate s straight from the
data: rearranging Amdahl for a single measured point N (using the ratio
r = T(N)/T(1)) gives s = (r·N − 1) / (N − 1). Take a mid-range point:
awk -F, '
NR == 1 { next }
{ if (t1 == "") t1 = $2 }
$1 == 16 {
r = $2 / t1
s = (r*$1 - 1) / ($1 - 1)
printf "serial fraction s = %.3f -> Amdahl ceiling S_max = 1/s = %.0f\n", s, 1/s
}
' data/scaling/strong_scaling.csv
serial fraction s = 0.020 -> Amdahl ceiling S_max = 1/s = 50
About two percent of this job is serial, which caps speedup near 50×, and sure
enough the measured curve flattens toward that ceiling (≈42× at 256 cores), never
approaching the linear ideal. That single number, s, explains the whole shape.
(The mirror image is Gustafson’s law / weak scaling: if you grow the problem
with the cores instead of fixing it, efficiency holds up far better: the optional
stretch below.)
D. Measure your own#
The dataset shows the serial-fraction ceiling. You can feel a different limit
on this very machine. Take a fixed batch of CPU work, run it split across 1, then 2,
then 4 parallel workers (xargs -P, from Notebook 5), and time each with the
date/awk stopwatch from Notebook 13:
# A "work unit" is one short, CPU-bound awk loop (no I/O, repeatable). bench runs
# a fixed batch of 4 of them across W parallel workers and returns the wall time.
bench() {
local W="$1" t0 t1
t0=$(date +%s.%N)
seq 1 4 | xargs -P "$W" -I{} bash -c 'awk "BEGIN{s=0;for(i=0;i<4000000;i++)s+=sqrt(i)}"'
t1=$(date +%s.%N)
awk "BEGIN{ printf \"%.3f\", $t1 - $t0 }"
}
t1=$(bench 1)
printf "%7s %7s %7s\n" workers time_s speedup
for W in 1 2 4; do
tw=$(bench "$W")
awk "BEGIN{ printf \"%7d %7.2f %7.2f\n\", $W, $tw, $t1/$tw }"
done
workers time_s speedup
1 1.12 1.00
2 0.95 1.18
4 0.95 1.17
You should see speedup climb and then flatten: going from 2 to 4 workers buys much less than 1 to 2, because once you ask for more workers than the machine has physical cores, they fight over the same hardware (oversubscription). Different cause from §C’s serial fraction, same moral.
⚠ The shape is the lesson, not the numbers
This page runs on a small, shared cloud machine (often only 1–2 cores you do not have to yourself), so your exact times will be noisy and your speedup may stall at 2 workers or wobble. That is fine, even expected. Read the shape (more workers → diminishing returns → a rolloff), not the decimals. Real benchmarking pins a job to dedicated cores and averages several runs; here we are after the idea.
Put the two together and you have the whole picture: the dataset shows the ceiling set by a job’s serial fraction (Amdahl), and your own run shows the wall you hit by asking for more workers than cores (oversubscription). Both say the same thing: there is a point past which more resources stop helping.
E. The justification#
The payoff is a decision you can defend. An allocation committee (CSCS, LUMI, your PI) does not want “we’d like a lot of cores”; it wants a number with evidence. The efficiency table writes the paragraph for you:
We request 16 cores per job. Strong-scaling tests of this calculation show parallel efficiency holding at 77% through 16 cores, then falling steadily to 61% at 32 cores and below half by 64, as the job’s fixed serial fraction (≈2%) comes to dominate. Running at 16 cores therefore uses our allocation efficiently; larger jobs would burn roughly double the core-hours for well under double the speed.
Numbers in, a defensible decision out. That is the entire point of the exercise, and the reason the shell work mattered: it turned a raw timing table into the one sentence that gets the allocation approved.
Exercises#
The dataset analysis is read-only and deterministic: graded on the numbers. The live
micro-benchmark’s times vary with the machine, so it is graded on structure (the
right rows, a rolloff), not exact seconds. Saved results go to a fresh scratch/.
Warm-up 1 (worked) — Speedup and efficiency#
Compute the full S and E table from the dataset with awk, and read off the
efficiency at 16 cores.
cores time_s speedup effic.
1 7200 1.00 100%
2 3781 1.90 95%
4 1952 3.69 92%
8 1021 7.05 88%
16 584 12.33 77%
32 368 19.57 61%
64 249 28.92 45%
128 197 36.55 29%
256 170 42.35 17%
✓ awk computed the speedup/efficiency table correctly (S=12.3x, E=77% at 16 cores)
Warm-up 2 (your turn) — Find the knee#
Identify the largest core count whose efficiency is still at least 75%.
knee: 16 cores (efficiency stays >= 75% up to here)
✓ the knee — the largest core count with E >= 0.75 — is 16
Applied 1 (your turn) — Amdahl’s serial fraction#
Estimate the serial fraction s from a data point with s = (r·N − 1)/(N − 1),
r = T(N)/T(1), and report the Amdahl ceiling 1/s.
from N=8: s = 0.0192 -> S_max = 1/s = 52
✓ the estimated serial fraction s (0.0192) is small and in the expected range (~0.02)
Applied 2 (your turn) — Measure your own speedup#
Time a fixed batch of CPU work at 1, 2, and 4 parallel workers (xargs -P + the
date/awk stopwatch), build the speedup table, and note where it rolls off. Times
vary, so only the structure is graded.
workers time_s speedup
1 1.12 1.00
2 0.95 1.18
4 0.95 1.18
✓ the micro-benchmark produced a 3-row speedup table (1, 2, 4 workers)
Composite — putting it together (justify an allocation)#
The real proposal skill: from the dataset, recommend a core count and back it with the efficiency evidence. Compute the knee, then write a short justification paragraph that cites the efficiency at the knee and the decline beyond it. Save it to a file.
We request 16 cores per job. Strong-scaling tests show parallel efficiency
holding at 77% through 16 cores, then falling to 61% at the next
step as the job's fixed serial fraction comes to dominate. Running at 16 cores
uses the allocation efficiently; larger jobs would cost far more core-hours for
little extra speed.
✓ the justification recommends 16 cores and cites the efficiency evidence
Optional stretch — Plot it, or weak scaling#
No grade. Two directions. (a) Turn the speedup column into a quick ASCII bar chart
with awk (no new tools): the shell’s instant plot:
1 cores S= 1.0 #
2 cores S= 1.9 ##
4 cores S= 3.7 ####
8 cores S= 7.1 #######
16 cores S= 12.3 ############
32 cores S= 19.6 ####################
64 cores S= 28.9 #############################
128 cores S= 36.5 #####################################
256 cores S= 42.4 ##########################################
(b) The second dataset, weak_scaling.csv, is a weak-scaling run: the work
grows with the cores, so the ideal is constant walltime and weak efficiency is
T(1)/T(N). Compute it and see how much better it holds up than strong scaling:
1 cores T= 600 s weak efficiency 100%
2 cores T= 633 s weak efficiency 95%
4 cores T= 640 s weak efficiency 94%
8 cores T= 681 s weak efficiency 88%
16 cores T= 686 s weak efficiency 87%
32 cores T= 727 s weak efficiency 83%
64 cores T= 744 s weak efficiency 81%
128 cores T= 771 s weak efficiency 78%
256 cores T= 788 s weak efficiency 76%
Weak efficiency stays high (still ~76% at 256 cores) where strong efficiency had
collapsed to ~17%, because each core keeps a full, fixed share of work. (For a real
plot, pipe the columns to gnuplot in your terminal, or into Python/matplotlib.)
Outlook#
You can now turn a timing table into a defensible core count: speedup and efficiency
with awk, the knee, the Amdahl ceiling, and the paragraph that justifies the request.
That is the last piece of working on a cluster, and it closes Part IV.
What is left is to stop doing all of this by hand. You have a scaling sweep
(Notebook 16), text extraction (Part II), and the analysis above: separate steps you
run and re-run manually. Part V ties the whole course together with make
(Notebook 18): a single make that orchestrates the sweep, the parsing, and the
analysis as one automated, repeatable pipeline: scripting, text processing, and HPC
awareness composed into the tool that runs them all.
No new commands this time: this is a pure-analysis notebook, and every tool in it
you have already met: awk (Notebook 8), xargs -P (Notebook 5),
time/date (Notebook 13). The Compendium is unchanged.