Concept 1 of 61 min
CPU time, pipelines, branches and out-of-order execution
CPU time
| Instructions | 6 billion |
|---|---|
| CPI | 0.8 |
| Clock | 4 billion cycles/s |
- Cycles = 6 × 0.8 = 4.8 billion
- Time = 4.8 ÷ 4 = 1.2 seconds
Fewer cycles per instruction or a faster clock both cut the time.
Branch mispredictions
| Branches | 25% |
|---|---|
| Mispredicted | 4% |
| Penalty | 20 cycles |
| Base CPI | 1.2 |
- Added = 0.25 × 0.04 × 20 = 0.2
- CPI = 1.2 + 0.2 = 1.4
Rare mispredictions still add 0.2 cycles to every instruction.
A pipeline
| Stages | 10 |
|---|---|
| Instructions | 1,000 |
- Pipelined = 1,000 + 10 − 1 = 1,009 cycles
- Without overlap = 1,000 × 10 = 10,000
Overlapping the stages makes the pipeline almost 10 times faster.
A pipeline overlaps stages of different instructions, so throughput nears 1 per cycle while each still takes every stage. Out-of-order execution fills stalls with independent work.
A pipeline raises throughput, not a single instruction's latency. Forgetting that only a share of instructions are branches overstates the penalty.
A test such as 'value > threshold' on sorted data is false then true in long runs that the predictor learns; on shuffled data it mispredicts about half the time.
While one instruction waits on memory, later independent ones run, and in-order retirement makes the program see the same outcome.
- Thinking a pipeline shortens each instruction.
- Applying the branch penalty to every instruction.
- Believing out-of-order execution changes a program's results.
A pricing loop runs twice as fast on sorted trades as on shuffled ones, with the same code. Explain it to a non-specialist.
A complete answer covers
- The processor guesses which way each 'if' will go to keep its pipeline full.
- On sorted data the answer repeats for long stretches, so it guesses right.
- On shuffled data it guesses wrong about half the time and throws work away.
- Branch-free code, or sorting first, removes the cost.
Also in our technical interviews, on camera, with a score.
Concept 2 of 61 min
Power, clock speed and transistor counts
The why, the charts, the worked example and the interview questions are in Essentials, with every quiz.
See the plansSign inConcept 3 of 61 min
Caches, memory layout and the memory hierarchy
The why, the charts, the worked example and the interview questions are in Essentials, with every quiz.
See the plansSign inConcept 4 of 61 min
Parallel speedup, false sharing, NUMA and SIMD
The why, the charts, the worked example and the interview questions are in Essentials, with every quiz.
See the plansSign inConcept 5 of 61 min
GPUs: arithmetic intensity, divergence and training memory
The why, the charts, the worked example and the interview questions are in Essentials, with every quiz.
See the plansSign inConcept 6 of 61 min
AdvancedThe roofline: memory-bound or compute-bound
The why, the charts, the worked example and the interview questions are in Essentials, with every quiz.
See the plansSign inRecap
- CPU time = instructions × cycles per instruction ÷ frequency; mispredicted branches add penalty × their share.
- Average access time = hit time + miss rate × miss penalty; walk memory in order and keep the working set in cache.
- Amdahl: speedup = 1/(s + p ÷ n), capped at 1/s; watch false sharing and remote NUMA (non-uniform memory access) memory.
- Dynamic power ∝ C × V² × f: clocks stalled on heat, so chips went multi-core, SIMD (single instruction, multiple data) and GPU.
- A GPU kernel is memory-bound when it does little arithmetic per byte; divergence serialises a warp; batch size grows activation memory.
25 questions on Computer architecture and GPUs
Timed, like the real one, drawn from a bank of 33. Every answer explained.