TechnicalBeginner4 min read
Parallelism
Three ways of spreading a computation across machines, from the simplest to the most demanding, then why doubling the machines does not halve the time (strong scaling, weak scaling, Amdahl's law).
For: engineers and SREs · architects · team managers · executives and CIOsPrerequisites: Have read lesson 1 of the course.
Illustrative scenario. A project manager gets twice as many machines for a computation that used to take a whole night. He expects his results by the middle of the night. The run does finish earlier, but nowhere near twice as fast. Nobody got anything wrong: that is simply how parallelism works, parallelism being the craft of splitting a job so that several machines do it at the same time.
It all comes down to one question: how often do the pieces of the work need to talk to each other?
Three patterns, from the simplest to the most demanding
Section titled “Three patterns, from the simplest to the most demanding”Picture three work sites.
The first is like marking exam papers. You split the pile among ten markers, each works alone and you collect the grades at the end. Nobody needs to talk to anyone. In HPC this is called trivial parallelism (or embarrassingly parallel work): each task runs on its own and the results are gathered at the end. Converting a batch of images works this way, as do parameter sweeps (running the same computation with a thousand different settings) or Monte Carlo methods, which estimate a result by repeating a large number of random draws.
The second is like bricklayers building one long wall together. Each lays his own stretch but keeps checking that it lines up with his neighbours’. This is tight coupling. The computation moves forward in time steps (a simulation advancing, say, minute by minute) and at each step every processor exchanges data with its neighbours. These exchanges usually go through MPI (Message Passing Interface), the standard library that lets programs spread over several machines send each other messages. You find it in atmospheric simulation, fluid dynamics or finite element analysis, which cuts a part into small pieces to work out how strong it is.
The third is like several cooks following the same recipe, each on their own batch, who pool their notes after every batch to improve the recipe for everyone. This is data parallelism. The model is copied onto every GPU, each copy works through a different batch of data, then all copies synchronize after each batch. That is how large language models (LLMs, which produce text) are trained, along with vision and recommendation models.
The three patterns differ in the shape of their exchanges:
flowchart TB
subgraph TRI["Trivial"]
direction LR
T1["Task 1"] --> TR["Results<br/>gathered"]
T2["Task 2"] --> TR
T3["Task 3"] --> TR
end
subgraph MPI["Tight coupling, MPI"]
direction LR
M1["P1"] <--> M2["P2"]
M2 <--> M3["P3"]
M3 <--> M4["P4"]
end
subgraph DAT["Data parallelism"]
direction LR
G1["GPU 1<br/>model copy"] <--> SY["Synchronization<br/>after each batch"]
G2["GPU 2<br/>model copy"] <--> SY
end
TRI ~~~ MPI
MPI ~~~ DAT
The more frequent the communication, the more critical the interconnect becomes and the more a single slow node slows down all the others. On the wall, one tired bricklayer holds up both neighbours, who hold up theirs. With the exam papers, a slow marker gets in nobody’s way.
Scaling up
Section titled “Scaling up”To find out whether adding machines is worth it, teams run two kinds of tests. In the first, strong scaling, the problem stays fixed: you add processors and measure the time saved. That is our project manager’s question. In the second, weak scaling, the problem grows along with the number of processors (for instance a weather map twice as detailed on twice as many machines) and you check whether the time stays stable.
Amdahl’s law
Section titled “Amdahl’s law”Back to our disappointed project manager. Every computation has a part that cannot be divided: reading the configuration at start-up, gathering results, writing the final file. Think of moving house. Twenty movers empty a flat much faster than two, yet the drive in the van takes the same time however many of them there are.
This is Amdahl’s law, named after the computer scientist who stated it: the share of work that cannot be divided caps the gain. At large scale, that sequential share and the cost of communication between machines decide what you can hope for.
A worked example: if 5% of the work is sequential, the computation will never run more than 20 times faster, whatever the number of processors. Even with ten thousand machines, that 5% still has to be done one piece after another.
Who uses HPC?
Section titled “Who uses HPC?”The uses cover a good part of the economy. Weather and climate teams produce global forecasts several times a day as well as simulations spanning several decades. Energy and engineering rely on it for aerodynamics, virtual crash tests, reservoir modelling and nuclear safety. Life sciences use it for molecular screening (testing thousands of candidate molecules by computation), genomics and medical imaging. Finance uses it to value complex portfolios and to run the stress tests regulators require. Defence uses it for cryptography, signal processing and geospatial data. Public research, finally, runs astrophysics and materials science on it, often on shared national infrastructures.
In most of these fields, there is no other way to see the work through to the end.