Computer Science › How Computers Actually Work
CPU time = Instruction Count × CPI × Clock Cycle Time — the "Iron Law" of processor performance, splitting speed into three independently movable levers (the ISA/compiler, the microarchitecture, and the silicon) that every design decision in this discipline trades off against.
The single-cycle CPU already built in Digital Logic & Computer Organization is correct but wasteful — every instruction's clock cycle must be as long as the slowest instruction ever needs. Pipelining overlaps instructions in flight, trading a longer per-instruction latency for a dramatically higher throughput.
Splitting the single-cycle datapath at five natural points — Fetch, Decode, Execute, Memory, Write-Back — with a pipeline register latching state between each stage, so five different instructions can occupy the five stages simultaneously, one cycle apart.
Two instructions in different stages want the same physical resource in the same cycle — classically, one instruction's Fetch and another's Memory access both wanting the one memory port — resolved in real designs by giving instructions and data their own separate caches.
A register written by one instruction is read by the very next one before the write has actually reached the register file — a read-after-write hazard fixed not by waiting, but by forwarding the not-yet-written-back result directly into the dependent instruction's ALU input.
One data hazard forwarding cannot fully erase: a load's value isn't available until after the Memory stage, so an immediately-dependent instruction still needs one bubble cycle — a stall that a smart compiler can often hide entirely by reordering independent instructions into that gap.
A branch's taken/not-taken outcome isn't known until well after the next instructions have already been fetched — naively flushing the pipeline on every branch costs real, quantifiable cycles, and is the exact problem branch prediction exists to reduce.
Guessing a branch's outcome before it's known — static prediction (always/backward-taken), and dynamic prediction with a branch history table of 1-bit or 2-bit saturating counters — turns most branch penalties into the common case of a correct guess instead of a guaranteed stall.
Executing past a predicted branch before its outcome is confirmed, and letting independent instructions issue out of program order around one that's stalled — covered here only at the concept level (what problem it solves and what a misprediction rollback costs), with the full mechanics (reorder buffers, Tomasulo-style scheduling) left to a more advanced course.
A pyramid of storage technologies — registers, on-chip cache, main memory, disk — trading capacity for speed at every level; temporal and spatial locality are the empirical properties of real programs that let a small, fast cache behave, most of the time, as if all of memory were that fast.
An address splits into a tag, an index, and a block offset; a direct-mapped cache uses the index to pick exactly one slot per address and the tag to check whether the resident block is actually the one being asked for.
Relaxing direct mapping's one-slot-per-address rigidity to N possible slots ("ways") per set trades extra comparison hardware for far fewer conflict misses; a fully associative cache is the limiting case of one giant set with every line a candidate.
When a set is full and a new block must be brought in, something has to be evicted — least-recently-used (and its cheaper hardware approximations), FIFO, and random are the real policies in use, each a different bet on which resident line is least likely to be reused soon.
A write can either update main memory immediately every time (write-through) or only mark the line dirty and defer the update until it's evicted (write-back) — paired with write-allocate/no-write-allocate for what happens on a write miss; this exact dirty-line bookkeeping is what a multicore coherence protocol later has to generalize across several caches at once.
AMAT = Hit Time + Miss Rate × Miss Penalty, applied recursively across a real L1/L2/L3/DRAM hierarchy with representative latency numbers — the single formula this whole cluster has been building toward, and the one CS2013 names directly as a required computational skill.
Row-major traversal order and cache blocking (tiling) turn everything in this cluster into a measurable, real-world effect: the same algorithm, the same asymptotic complexity, and a dramatically different wall-clock time depending only on the order memory is touched.
Around 2004-2005, chipmakers hit a real physical wall: Pollack's Rule (performance scales only with the square root of added logic, while power scales linearly with it) made single-core designs increasingly power-inefficient, prompting the industry-wide pivot to multiple simpler cores — the historical turn Herb Sutter named "the free lunch is over" for software.
A typical multicore chip gives each core its own private L1 (and often L2) cache but shares one L3 and one main memory across all of them — a layout that immediately raises a new correctness question this discipline hasn't had to face yet: what happens when two cores cache the same line?
The coherence problem, precisely stated: every core must eventually observe every write to a shared line, in some consistent order. MESI's four per-line states — Modified, Exclusive, Shared, Invalid — and the snooped bus messages between them are the standard protocol real multicore chips use to guarantee exactly that.
Two threads touching two completely unrelated variables can still fight over the same cache line if those variables happen to land in it — MESI keeps the data correct, but the line ping-pongs Modified/Invalid between cores on every access, turning a correctness protocol into a real, measurable performance bug.
Flynn's classification of machines by instruction and data streams — SISD, SIMD, MISD, MIMD — places the multicore chip just covered squarely in MIMD (many independent instruction streams); SIMD is the different axis this cluster turns to next: one instruction stream driving many data lanes at once.
A GPU packs thousands of simple lanes into streaming multiprocessors, executing groups of 32 threads (a warp) in lockstep under SIMT — SIMD's more flexible cousin, which lets individual threads take different branches at the cost of serializing the divergent paths. Scoped to the hardware execution model only; the CUDA/OpenCL programming model belongs to `systems/parallel-computing`.
Three real historical walls, tied together: the ILP wall (speculation and out-of-order issue ran out of independent work to exploit), the memory wall (AMAT increasingly dominated by DRAM latency no cache level fully hides), and the power wall (Pollack's Rule) — the same three forces that ended the single-core "free lunch" and made pipelining depth, cache hierarchy, multicore, and SIMD/GPU architecture the four real answers this discipline covered, in the order it covered them.
Part of the Computer Science curriculum.
CPU time = Instruction Count × CPI × Clock Cycle Time — the "Iron Law" of processor performance, splitting speed into three independently movable levers (the ISA/compiler, the microarchitecture, and the silicon) that every design decision in this discipline trades off against.
The single-cycle CPU already built in Digital Logic & Computer Organization is correct but wasteful — every instruction's clock cycle must be as long as the slowest instruction ever needs. Pipelining overlaps instructions in flight, trading a longer per-instruction latency for a dramatically higher throughput.
Splitting the single-cycle datapath at five natural points — Fetch, Decode, Execute, Memory, Write-Back — with a pipeline register latching state between each stage, so five different instructions can occupy the five stages simultaneously, one cycle apart.
Two instructions in different stages want the same physical resource in the same cycle — classically, one instruction's Fetch and another's Memory access both wanting the one memory port — resolved in real designs by giving instructions and data their own separate caches.
A register written by one instruction is read by the very next one before the write has actually reached the register file — a read-after-write hazard fixed not by waiting, but by forwarding the not-yet-written-back result directly into the dependent instruction's ALU input.
One data hazard forwarding cannot fully erase: a load's value isn't available until after the Memory stage, so an immediately-dependent instruction still needs one bubble cycle — a stall that a smart compiler can often hide entirely by reordering independent instructions into that gap.
A branch's taken/not-taken outcome isn't known until well after the next instructions have already been fetched — naively flushing the pipeline on every branch costs real, quantifiable cycles, and is the exact problem branch prediction exists to reduce.
Guessing a branch's outcome before it's known — static prediction (always/backward-taken), and dynamic prediction with a branch history table of 1-bit or 2-bit saturating counters — turns most branch penalties into the common case of a correct guess instead of a guaranteed stall.
Executing past a predicted branch before its outcome is confirmed, and letting independent instructions issue out of program order around one that's stalled — covered here only at the concept level (what problem it solves and what a misprediction rollback costs), with the full mechanics (reorder buffers, Tomasulo-style scheduling) left to a more advanced course.
A pyramid of storage technologies — registers, on-chip cache, main memory, disk — trading capacity for speed at every level; temporal and spatial locality are the empirical properties of real programs that let a small, fast cache behave, most of the time, as if all of memory were that fast.
An address splits into a tag, an index, and a block offset; a direct-mapped cache uses the index to pick exactly one slot per address and the tag to check whether the resident block is actually the one being asked for.
Relaxing direct mapping's one-slot-per-address rigidity to N possible slots ("ways") per set trades extra comparison hardware for far fewer conflict misses; a fully associative cache is the limiting case of one giant set with every line a candidate.
When a set is full and a new block must be brought in, something has to be evicted — least-recently-used (and its cheaper hardware approximations), FIFO, and random are the real policies in use, each a different bet on which resident line is least likely to be reused soon.
A write can either update main memory immediately every time (write-through) or only mark the line dirty and defer the update until it's evicted (write-back) — paired with write-allocate/no-write-allocate for what happens on a write miss; this exact dirty-line bookkeeping is what a multicore coherence protocol later has to generalize across several caches at once.
AMAT = Hit Time + Miss Rate × Miss Penalty, applied recursively across a real L1/L2/L3/DRAM hierarchy with representative latency numbers — the single formula this whole cluster has been building toward, and the one CS2013 names directly as a required computational skill.
Row-major traversal order and cache blocking (tiling) turn everything in this cluster into a measurable, real-world effect: the same algorithm, the same asymptotic complexity, and a dramatically different wall-clock time depending only on the order memory is touched.
Around 2004-2005, chipmakers hit a real physical wall: Pollack's Rule (performance scales only with the square root of added logic, while power scales linearly with it) made single-core designs increasingly power-inefficient, prompting the industry-wide pivot to multiple simpler cores — the historical turn Herb Sutter named "the free lunch is over" for software.
A typical multicore chip gives each core its own private L1 (and often L2) cache but shares one L3 and one main memory across all of them — a layout that immediately raises a new correctness question this discipline hasn't had to face yet: what happens when two cores cache the same line?
The coherence problem, precisely stated: every core must eventually observe every write to a shared line, in some consistent order. MESI's four per-line states — Modified, Exclusive, Shared, Invalid — and the snooped bus messages between them are the standard protocol real multicore chips use to guarantee exactly that.
Two threads touching two completely unrelated variables can still fight over the same cache line if those variables happen to land in it — MESI keeps the data correct, but the line ping-pongs Modified/Invalid between cores on every access, turning a correctness protocol into a real, measurable performance bug.
Flynn's classification of machines by instruction and data streams — SISD, SIMD, MISD, MIMD — places the multicore chip just covered squarely in MIMD (many independent instruction streams); SIMD is the different axis this cluster turns to next: one instruction stream driving many data lanes at once.
A GPU packs thousands of simple lanes into streaming multiprocessors, executing groups of 32 threads (a warp) in lockstep under SIMT — SIMD's more flexible cousin, which lets individual threads take different branches at the cost of serializing the divergent paths. Scoped to the hardware execution model only; the CUDA/OpenCL programming model belongs to `systems/parallel-computing`.
Three real historical walls, tied together: the ILP wall (speculation and out-of-order issue ran out of independent work to exploit), the memory wall (AMAT increasingly dominated by DRAM latency no cache level fully hides), and the power wall (Pollack's Rule) — the same three forces that ended the single-core "free lunch" and made pipelining depth, cache hierarchy, multicore, and SIMD/GPU architecture the four real answers this discipline covered, in the order it covered them.