The question this layer answers
How are instructions, data, compute, and storage organized?
The programmable machine. This layer connects CPU, ISA, Caches, RAM to the rest of the computing stack.
Architecture is an interface; implementation is a set of choices
An instruction-set architecture defines observable operations: registers, instructions, memory behavior, and exceptions. Different processors can implement the same interface with different pipelines, caches, and execution units. Software compatibility does not imply equal performance.
For a fixed execution, a useful accounting equation is CPU time = instruction count × average cycles per instruction ÷ clock rate. Each term depends on assumptions. A compiler may reduce instruction count but choose slower instructions. A longer pipeline may permit a faster clock while increasing the cost of a mispredicted branch. Use elapsed workload time as the final measure.
Work a complete cache trace
Consider a direct-mapped cache with four lines, one memory block per line, initially empty. Memory block b must use line b mod 4. Its tag distinguishes it from other blocks using the same line. Trace block requests 0, 1, 0, 4, 0, 1:
| Request | Line | Hit or miss? | Reason |
|---|
| 0 | 0 | Miss | Empty line |
| 1 | 1 | Miss | Empty line |
| 0 | 0 | Hit | Block 0 remains |
| 4 | 0 | Miss | Replaces block 0 |
| 0 | 0 | Miss | Block 4 occupied line 0 |
| 1 | 1 | Hit | Block 1 was untouched |
There are two hits and four misses. Blocks 0 and 4 conflict even though other lines are unused. A larger total memory capacity would not itself resolve this mapping conflict; changing placement options or the access pattern might.
If hit lookup time is 1 ns and the additional miss penalty is 50 ns, this trace has average access time 1 + (4/6) × 50 ≈ 34.33 ns. If a problem defines miss time as the entire access time instead, use a weighted average of total hit and miss times. Naming the convention prevents double-counting.
Speed up the part that matters
Suppose memory stalls account for 40% of an execution, and an improvement halves only that component. Normalizing original time to 1 gives new time 0.6 + 0.4/2 = 0.8, so speedup is 1.25×. Even eliminating that component entirely caps speedup at 1/0.6 ≈ 1.67×. This is Amdahl's reasoning: unchanged work limits overall improvement.
Try a counterfactual: reorder the same six requests to improve locality, then state whether reordering is legal for the program. Performance engineering must preserve behavior. A faster benchmark with different semantics is not an optimization of the original task. Use the lab to keep mechanism, measurement, and assumptions in one trace.
Free Architecture & memory lessons
Instructions and data share an organized machine
The instruction set architecture defines visible instructions, registers, data types, addressing, exceptions, and memory behaviour. A microarchitecture implements that contract with datapaths, control, pipelines, and caches. Different processors can run the same binary while arranging the internal work very differently.
A load encodes an operation, destination register, and address calculation. Control decodes it; the datapath computes the address; the memory system locates the bytes; the result is extended or interpreted as specified and written to the destination. Exceptions must leave an architecturally defined state.
Locality turns a speed gap into a workable illusion
Registers are tiny and immediate; caches hold recently useful blocks; DRAM supplies larger working memory; storage provides capacity and persistence. The hierarchy works because programs often reuse recent data and nearby addresses. A miss pays the cost of moving a whole block from a farther layer.
If a cache hit costs 1 ns and one access in 100 misses at a 100 ns extra penalty, misses add about 1 ns on average, roughly doubling the effective time. A small miss-rate change matters because the distant access is so expensive.
The processor is not the whole computer
Devices expose control and status through registers, often memory-mapped. Polling repeatedly asks for progress; interrupts let a device request CPU attention; direct memory access moves blocks between a device and memory with limited CPU involvement. Drivers translate operating-system requests into device-specific protocols.
When an enabled event arrives, the processor preserves enough execution context, identifies an appropriate handler, and transfers control. The handler acknowledges or services the source, schedules deferred work if needed, and eventually restores the interrupted context. Priority and masking keep urgent work bounded.
Reason with bottlenecks, parallelism, and measurement
Instruction count, cycles per instruction, and clock period offer one decomposition, but memory stalls, I/O waits, contention, and parallel work complicate it. Amdahl’s law states that improving one fraction of execution limits total speedup according to how much time that fraction originally consumed.
Wall time says the user-visible outcome. Hardware counters can show instructions, cycles, branches, and cache misses; system tools expose I/O and scheduling. Compare a hypothesis with several measurements: high last-level misses plus stalled cycles supports a memory-bound diagnosis more than instruction count alone.
Calculate placement, conflict misses, and coherence traffic.
Derive stalls from when a result exists and when a consumer needs it.
Trace a predictor and account for speculative recovery.
Analyze vector lanes, independent work, and shared bottlenecks.
Use elapsed time, controlled comparisons, and defensible summaries.
Practice lab: Trace a tiny cache
About 30 minutes. Use integer division and remainders. Memory stores values at numbered addresses. A cache holds copies of blocks near the processor.
Use an initially empty direct-mapped cache with two lines. Each block contains two words. A word address maps to block = floor(address / 2), line = block mod 2, tag = floor(block / 2). Read word addresses 0, 1, 4, 0, 1, 4 in that order. A hit takes 1 ns; a miss adds 20 ns.
- Record block, line, tag, and hit/miss for every access. Show the resident block after each miss.
- Calculate the miss rate and average access time under this serial model.
- Repeat for 0, 1, 2, 3, 0, 1 and explain why the same cache behaves differently.
Hint
Addresses 0 and 4 map to different blocks but the same cache line. A matching line number alone is not a hit.
Worked solution
For the first trace, blocks are 0, 0, 2, 0, 0, 2; every access selects line 0. Tags are 0, 0, 1, 0, 0, 1. Outcomes are miss, hit, miss, miss, hit, miss. The miss rate is 4/6; average time is 1 + (4/6) × 20 ≈ 14.33 ns. The second trace gives miss, hit, miss, hit, hit, hit: blocks 0 and 1 occupy different lines. Its average is 1 + (2/6) × 20 ≈ 7.67 ns. Capacity alone does not predict performance: placement and access order matter. Real machines can overlap requests, so this simple average is not a complete execution-time model.
- Use the tag to identify a hit.
- Count the compulsory first fills as misses.
- Explain conflict misses without claiming all memory accesses are serial in real CPUs.
Change one assumption
For a program spending 40% of its time on work you can double in speed, compute 1 / (0.6 + 0.4/2) = 1.25× overall speedup.
Explain a performance result with a machine model
Trace a small machine before estimating a large one. Keep latency, throughput, correctness, and measurement uncertainty separate.
1. Cache simulation · allow 40 minutes
A larger hit rate can come from placement
A byte-addressed cache has four 16-byte lines and starts empty. Trace addresses 0,64,0,16,64,80,0 in a direct-mapped organization. Show block number, set, tag, hit/miss, and eviction. Repeat with two sets of two ways, using LRU within each set.
Both have the same data capacity. Explain every changed outcome. If direct-mapped lookup takes 1 ns, two-way lookup takes 1.3 ns, and each miss adds 50 ns after lookup, calculate average access time for this trace. State why this workload does not establish a universal winner.
Get a starting hint
Block=floor(address/16). Direct mapping uses block mod 4; the two-way organization uses block mod 2.
Compare your reasoning with the worked solution
Block numbers are 0,4,0,1,4,5,0. Direct mapping sends 0 and 4 to set 0 and 1 and 5 to set 1. Every access misses: repeated 0/4 references evict each other, and 5 replaces 1. Tags for direct mapping are floor(block/4), giving 0,1,0,0,1,1,0.
For two ways, set 0 can hold blocks 0 and 4 and set 1 can hold 1 and 5. Results are M,M,H,M,H,M,H, with four compulsory misses and no evictions. Two-way tags are floor(block/2):0,2,0,0,2,2,0. This trace never needs LRU replacement after both ways fill.
Average times are 1+1×50=51 ns for direct mapping and 1.3+(4/7)×50≈29.871 ns for two ways. The lookup cost is charged on every access, and the penalty is additional. Other traces can have identical hit rates or capacity misses in both designs, and associativity may affect timing, energy, and area. Preserve the declared cache size and penalty convention when comparing results.
Check your reasoning
- Track tags and sets, not only hit counts.
- Identify conflict misses through a same-capacity comparison.
- Charge hit time once per access and state what the miss penalty includes.
2. Pipeline trace · allow 40 minutes
Count stalls from value availability
Use a five-stage IF,ID,EX,MEM,WB pipeline. Each stage takes one cycle. Assume no structural hazards, with separate instruction and data memory paths. Arithmetic results can forward from EX to a later EX; load results become available after MEM. A load followed immediately by an instruction using that value needs one stall. Store data can be forwarded, and all instructions occupy five stage slots even when a slot does no work.
Trace LD r1,[r0]; ADD r2,r1,r3; ADD r4,r2,r5; STORE r4,[r0+8]. Draw a cycle table and determine when the last instruction leaves the pipeline. Explain why adding clock stages does not automatically reduce the latency of one instruction, even when it improves steady throughput.
Get a starting hint
Without hazards n instructions take n+4 cycles. Locate the specific consumer whose EX stage arrives before its input exists.
Compare your reasoning with the worked solution
The load occupies cycles 1..5. The first ADD begins IF2,ID3, waits through cycle 4, then uses EX5,MEM6,WB7. The second ADD begins IF3, is held while the front end stalls, then ID5,EX6,MEM7,WB8. The STORE uses IF5,ID6,EX7,MEM8,WB9. The final stage slot ends at cycle 9, matching 4+4+1. The store's architectural memory update is in MEM8 under this simplified model; the specified five-slot accounting ends one cycle later.
The load-use pair needs the bubble because the loaded value is not ready for EX4. The next ADD receives r2 through forwarding into EX6, and STORE receives r4 through the stated store-data path. Without that path, the result could differ, which is why the assumptions belong in the problem.
More stages can shorten a clock period and permit more overlap, but add register overhead and may increase an instruction's cycle latency, branch recovery cost, or hazard exposure. Compare time per completed workload, not stage count alone.
Check your reasoning
- Show the single load-use bubble and the held front end.
- Use the explicitly provided forwarding paths.
- Distinguish last-stage accounting from the store update event.
3. Expected cost · allow 30 minutes
Evaluate a predictor using the right denominator
A workload has one million retired instructions. Twenty percent are branches. A predictor is wrong on 5% of branches, and each mistake adds 12 cycles. Base CPI excluding misprediction penalties is 1. Compute total cycles and effective CPI.
A new predictor lowers the branch error rate to 2% but makes the clock period 10% longer. Compare execution time at an original 1 ns clock. Derive the largest tolerable clock-period increase for the new predictor to break even. Explain why “accuracy improved by 3%” is an ambiguous description.
Get a starting hint
Count branch mistakes as instruction count × branch fraction × error rate. Compare cycles times period.
Compare your reasoning with the worked solution
There are 200,000 branches and 10,000 mispredictions, adding 120,000 cycles. Total cycles are 1,120,000 and CPI 1.12, giving 1.12 ms at 1 ns per cycle. The new predictor makes 4,000 mistakes and uses 1,048,000 cycles. At 1.1 ns its time is 1.1528 ms, about 2.93% slower despite fewer wrong predictions.
Break-even requires Tnew/Told≤1.12/1.048≈1.068702, so the maximum period increase is about 6.87%. The 5% to 2% error change is a 3-percentage-point drop or a 60% relative reduction in error. Accuracy rises from 95% to 98%, which is a different relative comparison. State the denominator instead of using an unlabeled percent.
The simplified calculation assumes the same instruction mix, penalty, base CPI, and useful work. A real predictor can affect energy, warm-up, speculative traffic, and workloads differently. Better prediction accuracy is a component metric; performance depends on the complete cost model.
Check your reasoning
- Apply the error rate to branches rather than all instructions.
- Compare time, not cycles alone.
- Distinguish percentage points from relative percentage changes.
4. Speedup bound · allow 35 minutes
Locate the serial cost after adding processors
A task takes 100 seconds on one processor. Exactly 80 seconds can be divided perfectly among workers;20 seconds remains serial. Estimate runtime and speedup on 8 workers, then add 5 seconds of coordination overhead. Derive the no-overhead limit as worker count grows.
A different workload spends 60% of elapsed time waiting on a memory bottleneck unaffected by an arithmetic optimization. The optimization makes the remaining 40% four times faster. Calculate whole-workload speedup. Explain why measuring only the optimized loop gives a misleading product claim.
Get a starting hint
Normalize each unaffected fraction to the original total. Overhead adds time; it is not part of the fraction already divided among workers.
Compare your reasoning with the worked solution
Eight-worker time without overhead is 20+80/8=30 seconds, speedup 100/30≈3.333. Adding 5 seconds gives 35 seconds and speedup≈2.857. As workers grow without overhead, parallel time tends to zero while 20 seconds remains, so the speedup limit is 5. If coordination grows with workers, even that asymptotic estimate can be unattainable.
For the memory-bound workload, normalized new time is 0.60+0.40/4=0.70, yielding speedup 1/0.70≈1.429. The optimized portion is four times faster; the application is about 1.43 times faster under the stated assumptions. Reporting the former as the latter changes the measured object.
Both models hold workload size and unaffected costs fixed. They do not predict scaled-workload throughput, contention, cache changes, or load imbalance. A measured faster loop is useful evidence, but the end-to-end claim requires measuring or justifying the rest of the execution path.
Check your reasoning
- Compute absolute runtime before reporting speedup.
- State the fixed-workload and perfect-division assumptions.
- Account for overhead and unaffected bottlenecks.
5. Protocol and experiment design · allow 45 minutes
Separate a fast device from correct data ownership
In a toy noncoherent DMA platform, CPU cache holds a dirty buffer value 7 while main memory still contains 3. The CPU tells a device to read the buffer from memory. Predict what the device sees. Later the device writes 9 to memory while the CPU retains a clean cached 3; predict a CPU read without invalidation.
Specify the required ownership transitions before device reads and before CPU reads device-written data. Then design a benchmark comparing copying with DMA: name the completion event, setup costs, transfer sizes, cache state, and validation needed to avoid timing an operation that has only been submitted.
Get a starting hint
The toy platform has no automatic cache coherence. Separate cache maintenance, ordering, and device completion; an actual platform API must supply their precise semantics.
Compare your reasoning with the worked solution
The device reads 3 because the dirty CPU value 7 has not reached its memory view. In the second situation the CPU can read cached 3 despite memory containing 9. For CPU-to-device transfer, finish writes, make the buffer visible using the platform's required cache maintenance, apply required ordering, and then transfer ownership or submit the descriptor. For device-to-CPU transfer, wait for actual completion, perform the required visibility/invalidation and ordering steps, then read. Concurrent access while ownership is transferred needs an explicit protocol.
A benchmark should time through a documented completion event, not merely queue submission. Include allocation, mapping, cache maintenance, interrupt or polling costs, and copying where relevant. Test several transfer sizes, control or report cache warmth, repeat measurements, and verify the entire payload with known patterns. Record latency distributions as well as throughput.
Coherent DMA platforms have different maintenance requirements. The correct implementation uses the operating system's DMA interfaces rather than assuming these toy operations map directly to portable instructions. Fast completion with stale data is not successful transfer.
Check your reasoning
- Predict both stale-data cases from the stated coherence model.
- Define when each participant owns the buffer.
- Measure verified completion and include setup costs.
Study the underlying methods
Section project: Build a cache simulator with auditable costs
5 to 7 hours. Implement a byte-addressed, direct-mapped cache simulator and compare locality patterns. Inputs are a cache configuration and a trace of reads and writes to nonnegative integer addresses. Start with four cache lines, four-byte blocks, write-back, and write-allocate. Main memory is a byte dictionary initialized to zero; writes supply values from zero through 255. Outputs include each access’s block number, index, tag, hit or miss, evicted block, dirty write-back, and returned value, followed by aggregate counters. Model a hit as one cycle and a block fill as fifty additional cycles; dirty eviction costs another fifty. These are declared synthetic costs, with no overlap or prefetching. Keep the functional memory result separate from the timing calculation. Use sequential, repeated-working-set, and conflicting-stride traces to explain locality and conflict misses. Compare results against a simple uncached reference store, and include an explicit final flush operation so dirty data is not silently omitted from traffic accounting. Python standard-library code and CSV output are sufficient. Keep demand fills, dirty evictions, and explicit flush writes as separate counters. A low miss rate alone does not account for every modeled memory transaction, particularly under a write-heavy workload.
Milestones
- Derive address decomposition and implement valid, tag, dirty, and block-data state.
- Implement read/write behavior and compare values with an uncached reference.
- Add cycle and memory-traffic accounting with a separate flush operation.
- Run three locality experiments and explain the misses from actual indices and tags.
Acceptance criteria
- For read addresses 0,4,0,16,4 under the initial configuration, the simulator records three misses and two hits.
- The same clean read trace costs 155 modeled cycles: five access cycles plus three fifty-cycle fills.
- Writing address 0 and then address 16 evicts one dirty block; a final flush writes the remaining dirty block exactly once.
- Every read value matches the uncached reference after the same write history, including offsets within a block.
- A second flush without intervening writes generates zero additional write-backs.
- Invalid negative addresses and out-of-range byte values are rejected without modifying cache or memory state.
Add two-way associativity with an explicit LRU replacement rule, then construct a trace that improves and one that does not change under the new configuration.
Practise Architecture & memory free →