This capstone integrates representation, instruction-set semantics, datapath/control, pipelining, memory hierarchy, I/O, performance modeling, and parallel execution. The problem is to design a processor-backed image-filter service that accepts frames from a device, applies a configurable convolution and color transform, and emits results under a latency and energy budget. The goal is not to choose a fashionable CPU feature. It is to make a defensible architecture argument in which every abstraction, optimization, and failure mode is explicit.
System specification
Assume a sensor produces 1920×1080 frames at 30 frames per second. Pixels arrive as four 8-bit channels; the filter applies a 3×3 kernel to each channel, clamps results to 0–255, and writes an output frame. The system has a 2 GHz 64-bit RISC-style core, 32 KiB 4-way L1 data cache with 64-byte lines, 256 KiB private L2, shared DRAM bandwidth of 20 GB/s, and a DMA-capable input device. These are modeling assumptions, not facts about one real processor; change them if your design justifies it.
The service must sustain the input rate, keep 99th-percentile frame processing below 25 ms after the complete frame is available, reject malformed descriptors, and never allow the device to write outside an owned buffer. The output may be delayed by buffering, but the system must state its queue bound and behavior when input outruns processing. An energy-aware design should report memory traffic and active-core time rather than claim that SIMD is efficient.
Start with the bottleneck
What should a capstone specification identify before choosing a cache or pipeline?
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Baseline arithmetic model
A 3×3 convolution performs nine multiplies and eight additions per output channel if implemented directly. A 1920×1080 frame contains 2,073,600 pixels; at four channels this is approximately 74.65 million multiplies and 66.36 million additions per frame, before boundary handling, loads, stores, clamping, address arithmetic, and loop control. At 30 frames per second the direct arithmetic demand is roughly 2.24 billion multiplies and 1.99 billion additions per second.
This count is a first estimate, not a timing result. If the kernel coefficients are fixed, multiplication may become shifts/adds or vector instructions. If the image is tiled, input pixels can be reused across neighboring outputs. If the filter is separable, a 3×3 kernel may be expressed as two 1×3 passes, reducing arithmetic at the cost of an intermediate buffer and additional traffic. A complete proposal compares these transformations against cache and bandwidth effects.
Worked arithmetic-intensity estimate. A naive output pixel reads 9 input pixels and writes one output pixel. At four bytes per pixel, ignoring reuse, that is 40 bytes and roughly 68 arithmetic operations, giving 1.7 operations per byte. With 20 GB/s of DRAM bandwidth, the roofline bandwidth ceiling is about 34 GFLOP/s-equivalent operations per second under this simplified count. Tiling can reuse input values from cache and raise effective intensity; it cannot be credited until the tile fits and the access trace is shown.
Connect the claim to falsifiable evidence
A capstone claims a new prefetcher improves performance by reducing memory stalls, but reports only end-to-end speedup on one input.
Which evidence package can test the proposed mechanism?
Representation and ISA choices
Specify whether pixels are stored interleaved RGBA or in separate channel planes. Interleaved layout is convenient when all channels of one pixel are processed together; planar layout can improve SIMD scans of one channel and simplify separable filters. State byte order, alignment, signedness of coefficients, accumulator width, and saturation behavior. A signed 8-bit coefficient multiplied by an unsigned 8-bit pixel can require a signed 32-bit accumulator to avoid intermediate overflow.
The ISA needs loads/stores, integer or vector multiply-add, widening arithmetic, min/max or clamp, pointer increments, branches or masked operations, and a memory-ordering primitive for DMA ownership. If coefficients are programmable, define their encoding and validation. If the vector instruction saturates, verify whether it rounds, truncates, or wraps; using modular arithmetic where saturation is required produces visually subtle but systematic errors.
Worked overflow bound. If pixels are at most 255 and kernel coefficients have absolute value at most 127, one channel’s absolute convolution sum is at most That requires 19 magnitude bits plus a sign bit (20 signed bits): signed 19-bit range ends at 262,143. A 32-bit accumulator provides margin for bias, intermediate transforms, and implementation variation. The final result must be rounded and clamped after the full sum, not after each product unless the specification permits that approximation.
Datapath and pipeline implications
A scalar core may load one pixel at a time, perform arithmetic, and store output. A vector core handles multiple pixels or channels per instruction, but boundary pixels, alignment, tails, and coefficient broadcast must be designed. A pipelined multiply-add has latency greater than one cycle, so independent accumulators or software scheduling are needed to maintain throughput. A dependent single accumulator can underutilize the pipeline even if the arithmetic unit accepts one operation per cycle.
| Implementation Alternative | Issue Width & Arithmetic Units | Unrolling / Latency Hiding | Cycles per RGBA Pixel | Clock Target to Meet 30 fps |
|---|---|---|---|---|
| Scalar In-Order Core | 1-way issue; 1 pipelined MAC (latency 4) | Single accumulator (RAW stalls serialize taps) | 36 cycles (9 taps 4 cycles) | (exceeds scalar envelope) |
| Scalar Unrolled Core | 1-way issue; 1 pipelined MAC (latency 4) | 4 interleaved channel accumulators (R, G, B, A) | 9 cycles (fully hides MAC latency) | (within thermal envelope) |
| SIMD Vector Core | 4-way SIMD vector unit; 128-bit vector MAC | 16-way SIMD vector taps across 4 pixels | 2.25 cycles | (low-power edge envelope) |
| Dedicated Hardware Stencil | 9-multiplier parallel 2D convolver pipeline | Hardwired streaming systolic array | 1 cycle / pixel | (ultra-low power ASIC/FPGA) |
Branch handling matters at image boundaries. A branch per pixel for clamping or bounds can cause mispredictions and front-end pressure. Vector min/max or masked loads can make the inner loop regular. Separate a prologue, aligned steady-state kernel, and epilogue when the ISA and workload justify it; the code-size and maintenance cost belongs in the comparison.
Memory hierarchy and tiling
The frame is far larger than L1 and L2, so a naive traversal may be bandwidth-bound. A tile should include enough neighboring rows for the 3×3 stencil and fit the chosen cache level with output and coefficient data. For a tile of width and height the input footprint is approximately pixels and output footprint pixels, adjusted for channels and layout. Choose so the footprint plus other active data fits with a safety margin; associativity conflicts can invalidate a capacity-only calculation.
Row-major layout favors a row-wise inner loop. A line of 64 bytes contains 16 four-byte RGBA pixels, so sequential access can use most fetched data. A column stride of 1920 pixels is 7680 bytes, causing poor spatial locality and potentially repeated set conflicts. Tiling changes the reuse distance: neighboring output pixels reuse input rows before eviction.
Design comparison. A row streaming design minimizes temporary storage but may reload rows for each output channel. A channel-plane tiled design improves vector reuse and coefficient broadcast but may require a format conversion. A separable design cuts arithmetic but writes and rereads an intermediate image. Measure bytes moved at each hierarchy level; “fewer operations” is not enough if traffic doubles.
DMA and buffering
The input device writes into a ring of owned frame buffers. The driver validates descriptor addresses and lengths, maps them through an IOMMU if present, publishes ownership with the required memory barrier, and receives a completion with generation and length. The processing core must not read a buffer until completion is ordered and validated. After processing, ownership returns only after all CPU writes are visible to the output device or host.
| Buffer Ring Slot | Buffer State | Current Writer | Current Reader | Memory / Cache Synchronization Action | Ownership Transfer Event |
|---|---|---|---|---|---|
| Slot 0 | CAPTURING | Camera DMA Engine | None (CPU access trapped) | Driver issues acquire fence before publishing descriptor | Camera asserts frame interrupt on completion |
| Slot 1 | PROCESSING | CPU Filter Kernel | CPU Filter Kernel | CPU performs cache line prefetch; processes tiles | Kernel completes output frame checksum |
| Slot 2 | TRANSMITTING | None (writes blocked) | Display DMA Engine | CPU issues sfence / write-back dirty lines to RAM | Display engine signals VSYNC completion |
| Slot 3 | FREE | None | None | OS resets buffer generation tag; clears stale descriptors | Driver enqueues slot back to Camera receive ring |
Double buffering permits one frame to arrive while another is processed; triple buffering absorbs jitter but increases memory. If processing time occasionally exceeds the frame period, the queue grows. A bounded system must choose drop-oldest, drop-newest, backpressure, or degraded-quality behavior. The policy is an architecture requirement because it affects memory capacity, latency, and user-visible correctness.
Performance budget
At 30 frames per second, the average frame budget is 33.3 ms, but the p99 requirement is 25 ms after availability. If one core handles 2 billion useful operations per second and the model requires 4.2 billion weighted operations per second, the design needs vectorization, multiple cores, lower arithmetic, or a hardware accelerator. Estimate instruction count and CPI separately from arithmetic count. Memory stalls and DMA wait time belong in the end-to-end timeline.
| Pipeline Stage | Quantitative Budget | Limiting Resource Ceiling | Architecture Mitigations for Tail Latency (p99) |
|---|---|---|---|
| Camera DMA Ingest | PCIe Gen3 | Dedicated continuous physical frames; no IOMMU page faults | |
| L1/L2 Cache Prefetch | L2 L1 cache bandwidth | Hardware stream prefetcher tuned to row stride | |
| 2D Stencil Convolution | Vector MAC throughput | Dual 4-way vector accumulators; loop boundary peel | |
| Output Cache Write-back | L2 write-back bandwidth | Streaming non-temporal stores (movntdq) bypass L1 | |
| Display DMA Egress | Display engine memory channel | High-priority QoS traffic class on memory arbiter | |
| Total Frame Latency | Headroom: vs SLA | Deterministic margin guarantees |
Use a stage budget: input completion, cache warm-up, compute, output write-back, and scheduling. For a vector design, calculate lanes per instruction and tail fraction. For a multicore design, account for partitioning, synchronization, shared-cache traffic, and load imbalance. A design that meets mean time but not p99 must identify the source of tail variation—page faults, queueing, interrupts, contention, or device behavior.
Reliability and security
Validate every descriptor length against the allocated buffer, prevent integer overflow in stride and frame-size calculations, and reject unsupported dimensions before DMA. Device completion is untrusted input: a malformed length or status must not become an unchecked loop bound. Memory mappings must be revoked after device reset, and stale completions must be rejected by generation.
| Failure Mode / Threat Vector | Trigger Condition | System Impact | Hardware & Architectural Verification Invariant |
|---|---|---|---|
| Descriptor Integer Overflow | Untrusted camera reports | DMA writes outside allocated frame into kernel memory | Reject descriptor if before DMA setup |
| Stale DMA Overwrite | Host reallocates frame buffer before DMA engine quiesces | Active DMA corrupts newly assigned tenant process memory | Enforce generation counters; poll device status bit before reuse |
| Frame Dropping Under Jitter | Processing exceeds 33.3 ms during transient background load | Ring buffer overflows; camera DMA drops subsequent frames | Triple-buffering absorbs 1-frame jitter; fallback to drop-oldest |
| Speculative Cache Snooping | Secret camera data left resident in shared LLC | Cross-tenant Flush+Reload side channel leaks frame bytes | Explicit cache line clear / way-partitioning before core release |
If the image contains sensitive data, cache timing, DMA isolation, and buffer clearing become part of the threat model. A faster vector implementation that leaves pixels in a shared cache or recycled buffer may have a different security posture. State what confidentiality is required and which layers enforce it.
Architecture specification package
Produce a block diagram and a sequence diagram from device arrival through output completion. Specify pixel representation, ISA operations, accumulator width, pipeline schedule, cache mapping, tile dimensions, DMA ownership, queue policy, exception behavior, and security assumptions. Give a baseline and at least two alternatives, with a table of arithmetic work, estimated bytes moved, memory ceilings, compute ceilings, area/energy implications, and unverified assumptions.
Include a correctness argument for one output pixel, an invariant for buffer ownership, an AMAT or roofline calculation, and an experiment plan. The experiment must identify what would falsify the claim that the design is compute-bound, cache-bound, bandwidth-bound, or synchronization-bound. Report how you would measure p99 latency and how you would inject a delayed or malformed device completion.
Verification criteria
A rigorous design specification is precise about boundaries and uncertainty. It derives rather than asserts arithmetic cost, connects data layout to cache lines, distinguishes architectural guarantees from microarchitectural assumptions, handles tail and overflow cases, and proposes measurements that could disprove its own model. A diagram without invariants is incomplete; a benchmark without workload and measurement boundaries is weak evidence; a speedup claim without a baseline is not a result.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 5.2.1: L1 Tile Working-Set Footprint and Compulsory DRAM Traffic
Verify that a RGBA output tile with a 1-pixel halo fits inside the 32 KiB 4-way L1 data cache and calculate the compulsory DRAM traffic per output pixel compared to an untiled naive kernel.
HintExpandCollapse
Include the 1-pixel border on all four sides: input pixels plus output pixels, at 4 bytes per RGBA pixel.
Worked solutionExpandCollapse
- Input tile with halo: pixels
- Output tile: pixels
- Total working set: leaving nearly half of L1 capacity for stack frames, filter coefficients, and set-associativity conflict headroom.
- Traffic reduction: Without reuse, each output pixel reads and writes With L1 tiling, each output pixel amortizes to reducing external memory traffic by
Exercise 5.2.2: Stencil Accumulator Width and Saturation Ordering
Suppose the convolution kernel uses signed 8-bit weights and unsigned 8-bit pixels Determine the exact minimum signed two’s-complement accumulator width required to prevent intermediate overflow before final clamping to and construct a 9-tap counterexample showing why per-tap clamping violates exact convolution semantics.
HintExpandCollapse
Compute the worst-case negative sum and compare against signed -bit bounds .
Worked solutionExpandCollapse
- Minimum accumulator width: The extreme negative sum is and the extreme positive sum is A signed 19-bit integer covers which overflows both bounds. A signed 20-bit integer covers so 20 signed bits is the exact mathematical minimum (implemented in hardware with a standard 32-bit lane).
- Per-tap saturation counterexample: Suppose 8 taps yield each and the 9th tap yields (e.g., Exact accumulation gives Clamping to after every tap instead saturates at across taps and then drops to introducing a -unit error.
Exercise 5.2.3: Pipeline RAW Hazard Hiding via Accumulator Unrolling
Consider a 2 GHz core whose pipelined 4-channel MAC instruction completes all four RGBA lanes of one stencil tap with initiation interval and latency A naive loop updates one pixel accumulator across all 9 taps Show how unrolling across independent output pixels removes RAW stalls to achieve and calculate the resulting compute-only frame time for a image.
HintExpandCollapse
Interleave tap across four independent pixel accumulators before issuing tap to .
Worked solutionExpandCollapse
- Hazard elimination: With independent pixel accumulators, the loop schedules
MAC A0, tap_t,MAC A1, tap_t,MAC A2, tap_t,MAC A3, tap_tin consecutive cycles By cycle the 4-cycle latency ofA0has completed, soMAC A0, tap_{t+1}executes with zero RAW stalls. - Amortized cycle rate: Four pixels complete all 9 taps in cycles (plus negligible 3-cycle drain), giving
- Compute-only frame time: A frame has pixels. At compute requires cycles. At compute takes leaving of headroom within the p99 budget (compared to without unrolling).
Exercise 5.2.4: DMA Descriptor Integer Overflow and Generation-Counter Race
A camera driver allocates an frame buffer (1920 * 1080 * 4) and validates an incoming descriptor in 32-bit unsigned arithmetic with uint32_t bytes = width * height * 4; if (bytes <= buf_capacity) accept();. Construct a concrete (width, height) input pair that bypasses this check via wraparound, and write both the overflow-safe validation invariant and the generation-tag check required before recycling a DMA slot.
HintExpandCollapse
Choose factors of (for instance powers of two whose product times 4 wraps modulo into ).
Worked solutionExpandCollapse
- Overflow exploit vector: Let
width = 65536andheight = 16384In 32-bit unsigned arithmetic, Since the naive check accepts the descriptor while the DMA loop attempts to transfer past the buffer. (Similarly,width = 32768, height = 32769wraps to131,072bytes - Safe validation invariant: Reject zero dimensions and enforce explicit architectural bounds plus division-checked 64-bit bounds before multiplying:
width > 0 && height > 0 && width <= 4096 && height <= 2160 && (uint64_t)width * height <= buf_capacity / 4. - Buffer recycling invariant: Never return a slot to
FREEuntil an MMIO status read confirms the DMA engine is idle on that descriptor and its returned generation token matches the slot’s expected generation counter (incremented monotonically on each reuse).
Exercise 5.2.5: Falsifying Memory-Bandwidth vs. Compute Bottlenecks
Compare the untiled naive stencil intensity and the L1-tiled stencil DRAM traffic) on a core with a DRAM ceiling and a SIMD compute ceiling. Determine which roofline bound constrains each variant, and design a single controlled experiment that falsifies the hypothesis that the tiled pipeline is DRAM-bandwidth-bound.
HintExpandCollapse
Compute the roofline ridge point () and test sensitivity to core clock scaling versus DRAM bandwidth scaling.
Worked solutionExpandCollapse
- Roofline classification: The machine ridge point is
- Untiled kernel Memory roofline ceiling is theoretically if L1/L2 had infinite conflict-free streaming, though in practice poor row-strided reuse drops effective intensity below and stalls on DRAM bandwidth.
- L1-tiled kernel Exceeds the ridge point by over (DRAM ceiling placing the tiled kernel squarely under the compute ceiling.
- Falsification experiment: Hold input resolution, tile size and DRAM clock fixed while stepping CPU core frequency from down to (and measuring DRAM CAS byte counters and L2 miss stalls). If frame time doubles while total DRAM bytes stay constant at compute is the bottleneck; conversely, if frame time stays nearly invariant under core clock halving while L2/DRAM stall cycles remain high, the hypothesis of compute-boundedness is falsified and the bottleneck lies in memory stalls or cache conflicts.