Computer Science › Section C · Data manipulation › Topic C.7
Other architectures: pipelining and multiprocessors
There is a limit to how fast one instruction can be carried out, so modern processors get more done by doing several things at once: overlapping the steps of the machine cycle, and putting many processors to work together.
Faster, or more at once?
Electrical signals cannot travel faster than light, which covers about 30 cm in a nanosecond in a vacuum, and signals in wires are slower still. A request to memory and its reply must make a round trip, so every machine cycle has a physical floor, and making single instructions faster becomes largely a matter of making circuits smaller. There is another route. Latency is the time one task takes from start to finish; throughput is the amount of work completed per unit of time. A processor can raise its throughput without cutting the latency of any single instruction, simply by working on several at once.
Pipelining
In the machine cycle of "Program execution and the machine cycle", the circuits for fetching sit idle while an instruction executes. Pipelining puts them to work by overlapping the steps, like an assembly line. While instruction 1 is executing, instruction 2 is being decoded and instruction 3 fetched. Each stage passes its work on at every clock tick, so once the pipeline is full, one instruction finishes per tick, even though each still passes through every stage. Many real designs split the cycle into five or more stages, such as fetch, decode, read registers, execute and write back.
Worked example: timing a pipeline
A processor has 4 stages of 1 ns each. How long do 100 instructions take, with and without pipelining? 1. Without pipelining, each instruction takes 4 ns and the next cannot start until it finishes: 100 × 4 = 400 ns. 2. With pipelining, the first instruction finishes after 4 ns, and one more finishes every 1 ns after that. 3. So the total is 4 + 99 × 1 = 103 ns. 4. The speedup is 400 ÷ 103, about 3.9, close to the number of stages. In general, k stages and n instructions need k + (n − 1) ticks. Check: each individual instruction still takes 4 ns, so the gain is in throughput, not latency.
Hazards: when the pipeline stalls
The ideal is spoiled by hazards. A jump is the obvious one: by the time the CPU learns that a jump is taken, it has already fetched the instructions after it, which are now the wrong ones and must be thrown away. To limit the damage, processors use branch prediction, guessing which way each conditional jump will go, often from how it went before, and fetching from the guessed address. A data hazard arises when an instruction needs a result that is still in the pipe. In the Sparrow pair 0x5312 then 0x3380, the STORE needs R3 before the ADD has finished writing it, so the pipeline must pause or pass the result straight across.
Doing even more per tick
Modern processors push the idea further. A superscalar processor fetches several instructions at once and has several execution units, so it can complete more than one instruction per tick, which is why IPC can exceed 1. Many processors also execute instructions out of order: if one instruction is waiting for data from memory, later instructions that do not depend on it go ahead, and the results are then put back into program order. The program still behaves exactly as if its instructions ran one at a time.
Flynn's categories
Pipelining overlaps the steps of one instruction stream. True parallel processing needs several processing units. A classification proposed by Michael Flynn in the 1960s sorts machines by how many instruction streams and data streams they handle. SISD (single instruction, single data) is the traditional single processor running one program on one stream of data. SIMD (single instruction, multiple data) applies the same instruction to many data items in lock step. MIMD (multiple instruction, multiple data) has several processors each running its own instructions on its own data, which describes multicore computers. The fourth combination, MISD, is rare in practice.
Multicore processors and shared memory
A multicore processor puts two or more complete CPUs, called cores, on one chip, usually sharing some cache and the same main memory. For decades processors got faster mainly by raising the clock rate, but from about the mid-2000s the power use and heat of faster clocks became too great. Designers turned the extra transistors into more cores instead. Cores cooperate through shared memory, one writing results that another later reads, which brings risks: two cores updating the same cell at once can lose an update, as "Competition among processes: semaphores and deadlock" shows. A program gains from extra cores only if its work is divided into parts, such as threads, that can run at the same time.
SIMD, GPUs and clusters
SIMD suits jobs that do the same thing to many items, such as brightening every pixel of an image. Most desktop, laptop and phone processors include SIMD instructions, such as SSE and AVX on x86 or NEON on ARM, that add or multiply several numbers in one instruction. A graphics processing unit (GPU) takes the idea much further, with thousands of simple cores; built for graphics, GPUs are now central to training machine-learning models. At the other extreme, a cluster links many separate computers, each with its own memory, by a fast network, as "Network fundamentals" describes. A big job is cut into pieces that need nothing from each other, and the machines process them side by side.
Amdahl's law
Parallel hardware only speeds up the part of a job that can be split. If a fraction p of a program's running time can be shared perfectly among n processors and the rest must run in sequence, the overall speedup is
This is Amdahl's law, named after the computer architect Gene Amdahl. However many processors you add, the sequential part never shrinks, so the speedup can never exceed \(\frac{1}{1 - p}\). The same reasoning applies to any upgrade of one part of a system.
Worked example: eight cores
A video-processing program spends 80% of its time on work that can be split evenly across cores, and 20% on work that cannot. 1. With 8 cores, the split part takes \(\frac{0.8}{8} = 0.1\) of the original time. 2. The sequential part still takes 0.2. 3. Total time: \(0.2 + 0.1 = 0.3\) of the original, so the speedup is \(\frac{1}{0.3} \approx 3.3\). 4. With unlimited cores the split part shrinks towards 0, leaving 0.2, so the limit is \(\frac{1}{0.2} = 5\). Check: 8 cores give far less than an eightfold speedup, and no number of cores can beat 5. Shrinking the sequential 20% would pay off more than adding cores.
Common mistakes to avoid
First, thinking pipelining makes each instruction faster; it raises throughput, while each instruction still passes through every stage. Second, forgetting the fill time: n instructions on a k-stage pipeline take k + (n − 1) ticks, not n. Third, ignoring hazards; jumps and data dependencies make real pipelines slower than ideal. Fourth, expecting n cores to give an n-fold speedup; Amdahl's law limits it. Fifth, mixing up SIMD, one instruction on many data items, with MIMD, many processors running their own instructions.
Key takeaways
The speed of light and circuit size limit how fast one instruction can run, so designers raise throughput instead. Pipelining overlaps the stages of the machine cycle: k stages handle n instructions in k + (n − 1) ticks. Jumps and data dependencies cause hazards; branch prediction reduces the cost. Superscalar and out-of-order processors finish several instructions per tick. Flynn's categories are SISD, SIMD and MIMD; multicore chips are MIMD, while SIMD instructions and GPUs apply one operation to many items. Amdahl's law: speedup is limited by the part that cannot be parallelised.
Flashcards
Flashcard
Time one task takes from start to finish
Test your understanding
Question 1 of 5
A processor has a 5-stage pipeline with 2 ns per stage. About how long do 50 instructions take?
Question 2 of 5
What does pipelining improve?
Question 3 of 5
A GPU brightens a million pixels by applying the same add instruction to many pixels at once. Which of Flynn's categories is this?
Question 4 of 5
A program spends 90% of its time on work that can be split perfectly across cores. Using Amdahl's law, what speedup do 10 cores give?
Question 5 of 5
Why does a taken jump reduce the benefit of pipelining?
