Parallelism

Parallelism is when we can do more than one thing at the same time, like two trains running along separate tracks next to each other.

Parallelism typically increases throughput—how much total work gets done—not latency—how quickly any given piece of work gets done.

Throughput: Number of trains moving from point A to point B in a day.
Latency: How quickly one train can travel from point A to point B.

There’s a complicated relationship between parallelism, throughput, and latency.

If we can divide a problem into pieces that can be executed in parallel, we can decrease the latency of solving the whole problem.

But if the cost of coordination between parallel work is high enough, it can be slower than just solving one problem at a time with no parallelism.

Easily parallelizable

If one person can eat a slice of pizza in 90 seconds it will take them 12 minutes to eat an 8-slice pizza.

Two people can’t eat one piece of pizza in 45 seconds but they can eat two pieces in 90 seconds. Their throughput has doubled without affecting the per-piece latency.

Thus two people can eat the whole pizza in 6 minutes, halving the eat-a-whole-pizza latency.

Coordination costs

People working on a project together spend part of their time talking about who’s going to do what.

Thus it might take them more total time (in person-hours) to do the project than if either one of them had done the whole thing themselves.

And sometimes one person will have to wait for the other before they can do their next thing. This is a pipeline stall that reduces throughput.

For many projects however the latency will still be reduced.

Amdahl’s Law

Parallel computation version

\(S = \frac{1}{(1 - P) + \frac{P}{N}}\)

\(S\) is the overall speedup of the program; \(P\) is the proportion of the program that is parallelizable; and \(N\) is the amount of parallelism.

If 90% of a program can be run with infinite parallelism, you can still only speed up the program by 10x.

CPU-level pipelining

By processing instructions in a multi-stage pipeline, we can execute instructions in parallel (fetching one instruction at the same time as we are decoding another one) which increases our instruction throughput.

Instruction latency might be worse but whole-program latency will be better.

Other important forms of parallelism

Multi-core CPUs
GPUs

Multi-core CPU

Each core is essentially a whole CPU except there’s another level of caching (L3) and all memory access is controlled through the CPU’s memory controller.

On a single-core CPU the operating system gives us the illusion of multiple things happening at once by very quickly switching between tasks.

On a multi-core CPU, each core can actually execute instructions independently so multiple things really are happening at once.

IB note

The IB CS Guide has this learning objective:

A1.1.6 Describe the process of pipelining in multi-core architectures.

This is kind of nonsense. Instruction pipelining and multi-core are two independent concepts.

However, CPUs advanced enough to be multi-core are also probably going to have instruction-level pipelining.

GPUs

Some work in a computer is inherently parallelizable.

One of the first examples was rendering graphics which consists of doing the same basic computation over and over to compute the color of every pixel displayed on the screen.

To make video games run fast while taking load off the CPU, we made GPUs (Graphics Processing Units) that could compute pixel values in parallel. The CPU would then hand off that work to the GPU.

The R, G, and B color components of each pixel are computed from the corresponding components of a texture at that pixel, the light at that pixel, and the ambient level of that color.

Conceptually we need to do this computation:

for (int i = 0; i < pixels.length; i++) {
  pixels[i].r = texture[i].r * light[i].r + ambient[i].r;
  pixels[i].g = texture[i].g * light[i].g + ambient[i].g;
  pixels[i].b = texture[i].b * light[i].b + ambient[i].b;
}

We could obviously run this loop on a single-core CPU. But it’s also easily parallelizable.

If we had a 2-core CPU we could split it up so one core computes half the pixels and the other core computes the other half.

But what if we had as many cores as we have pixels (about 1 to 8 million)? Each core could compute one pixel.

GPUs are designed for this kind of workload.

They also slice the problem up differently than CPUs.

Instead of having lots of complete cores that can all fetch and execute instructions independently, they have lots of ALUs that all execute the same instructions at the same time but on different data, e.g. different pixel data.

These days

In the age of Large Language Models, instead of using GPUs to do linear algebra to figure out what color pixels should be, we use GPUs to do linear algebra to figure out what word is most likely to come next in a series of words.

On a modern gaming GPU we might have 76 SMs, each with 4 processing blocks, so up to 304 independent instructions being executed at any given time.

And each instruction is executed across 32 ALUs giving us up to 9,728 parallel computations.

Datacenter GPU are similar but their SMs have more of the special processors needed for matrix math and fewer or none of the ones needed specifically for graphics processing.