Loading study handbook…

Computer Systems

5% of exam

Microprocessors, memory technology and hierarchy, interfacing.

3 concepts

A. Microprocessors

Microprocessors

How a CPU fetches, decodes, and executes instructions — datapath, registers, the ISA, addressing modes, pipelining, and interrupts — and the timing math the FE tests.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders

B. Memory technology and systems

Memory Technology and Hierarchy

SRAM/DRAM/ROM/flash, the cache-driven memory hierarchy, address decoding and cache mapping, virtual memory, and the effective-access-time math the FE rewards.

Memory is the great compromise of computing: the fastest storage is tiny and expensive, the cheapest is enormous and slow, and no single technology is both fast and big. The answer is a hierarchy — registers, cache, main memory, disk — arranged so the processor almost always finds what it needs in a fast level, falling back to slow levels only rarely. The FE Reference Handbook's Computer Systems section lays out the technology vocabulary (RAM volatile, ROM nonvolatile, L1/L2 cache) and the cache address split (tag, index, block offset) but leaves the quantitative payoff — effective access time, hit rates, locality — to you. That payoff is where the points are, and this concept is built to deliver it.

Memory technologies

Know each cell type and its defining trait. SRAM (static RAM) stores each bit in a 6-transistor latch: fast, no refresh, low density, expensive — it is the cache material. DRAM (dynamic RAM) stores each bit as charge on a tiny capacitor: dense and cheap but leaks, so it must be refreshed periodically, and it is slower — it is main memory. Both are volatile (lose data without power). ROM and its descendants are nonvolatile: mask ROM is fixed at manufacture, PROM is one-time programmable, EPROM is UV-erasable, EEPROM is byte-erasable electrically, and flash is block-erasable EEPROM optimized for density — the basis of SSDs and firmware storage. The handbook's one-liner is that RAM is volatile primary memory and ROM is nonvolatile instruction/constant storage; the table below fills in the rest.

The memory hierarchy and locality

Stack the technologies by speed: CPU registers (sub-nanosecond), L1/L2/L3 SRAM cache (1–30 ns), DRAM main memory (~50–100 ns), then flash/disk (microseconds to milliseconds). The hierarchy works only because real programs exhibit locality of reference. Temporal locality: a location used now is likely to be used again soon (loop counters, the top of the stack). Spatial locality: locations near one used now are likely to be used soon (array walks, sequential code) — which is why memory moves in blocks/lines, not single bytes. A well-designed hierarchy gives near-cache speed at near-DRAM cost precisely because locality keeps the hit rate high.

Cache operation: hits, misses, and the three-field address

On each access the cache checks whether the requested block is present. A hit returns it at cache speed; a miss must fetch the whole block from the next level and costs a miss penalty. The handbook gives the capacity relation

C = S\cdot A\cdot B

(sets times associativity times block size) and the address breakdown the hardware uses to find a block: the low bits are the block offset, the middle bits are the index that selects a set, and the high bits are the tag stored alongside the data and compared on lookup.

\#\,offset = \log_2 B,\quad \#\,index = \log_2 S,\quad \#\,tag = \#\,addr - \#\,index - \#\,offset

Cache mapping and replacement

Mapping fixes which cache locations a memory block may occupy. Direct-mapped (

A=1

): each block has exactly one slot, given by its index — simple and fast but prone to conflict misses. Fully associative: a block may go anywhere, eliminating conflict misses at the cost of comparing all tags. Set-associative (the practical middle): the index selects a set of

A

ways, and the block may go in any way of that set. When a set is full on a miss, a replacement policy chooses the victim; the handbook lists LRU (least recently used), FIFO, random, and LFU. Write policy matters too: write-through updates cache and memory together, while write-back updates only the cache and marks a dirty bit, deferring the memory write until eviction.

Effective (average) access time

The single most testable quantity is the average memory access time (AMAT): the hit time always paid, plus the miss rate times the miss penalty. With hit rate

h

(so miss rate

1-h

), cache time

t_c

, and memory time

t_m

as the penalty, AMAT is below. The same idea chains down the hierarchy — a multi-level cache nests an L2 AMAT inside the L1 miss penalty — and it underlies virtual-memory timing too, where a page fault is just a very expensive miss. A small drop in miss rate buys a large drop in AMAT precisely because the penalty is so large relative to the hit time.

AMAT = t_c + (1-h)\,t_m

Virtual memory and address translation

Virtual memory gives each process a large, contiguous address space independent of physical RAM. The address space is divided into fixed-size pages mapped to physical frames by a per-process page table; the high bits of a virtual address index the page table to get a frame number, and the low bits (the page offset) pass through unchanged. Because walking the page table itself costs memory accesses, a small fast cache called the translation lookaside buffer (TLB) holds recent translations. A reference to a page not in physical memory triggers a page fault, and the OS fetches it from disk — the slowest miss in the hierarchy. The structure mirrors caching exactly: a fast directory (TLB), a hit/miss outcome, and a heavy penalty on a miss.

Address decoding in a memory system

Building a memory bank from smaller chips is an address-bit accounting problem. A chip with

W

addressable words needs

\log_2 W

address lines. To assemble

T

total words from chips of

W

words each requires

T/W

chips, and the high-order

\log_2(T/W)

address lines drive a decoder whose outputs are the chip-select lines — each chip responds to one block of the address map. The low-order

\log_2 W

lines go to every chip in parallel to pick the word within the selected chip. Getting these counts right is a recurring FE item and the same arithmetic as the cache offset/index split.

Exam strategy

B-area questions cluster into three templates. First, technology identification: match SRAM/DRAM/ROM/flash to a trait (volatile? refreshed? nonvolatile? erase granularity?). Second, address arithmetic: split an address into tag/index/offset using

\log_2

of the block size and set count, or count chips and chip-select lines for a memory bank — write the three field widths before plugging in. Third, timing: compute AMAT as hit time plus miss-rate times penalty, and for two-level systems substitute the lower-level AMAT as the upper-level penalty. Always convert capacities to powers of two first (

16\,\text{KB}=2^{14}

bytes), and keep block size in bytes consistent with the address being byte-addressed.

Key equations

Average memory access time (AMAT)

AMAT = t_{hit} + (1-h)\,t_{penalty}

$h$ = hit rate, $t_{hit}$ = fast-level access time, $t_{penalty}$ = extra time to service a miss. Hit time is always paid; the penalty only on misses.

Two-level cache AMAT

AMAT = t_{L1} + m_{L1}\big(t_{L2} + m_{L2}\,t_{mem}\big)

Cache capacity

C = S\times A\times B

$C$ = data capacity (bytes), $S$ = number of sets, $A$ = associativity (ways),

Cache address field widths

\#offset=\log_2 B,\;\; \#index=\log_2 S,\;\; \#tag=n-\#index-\#offset

Number of cache sets

S = \dfrac{C}{A\times B}

Solve the capacity relation for sets. Direct-mapped has $A=1$ ; fully associative has $S=1$

Hit and miss rate

h + m = 1

$h$ = fraction of accesses found in the level, $m=1-h$ = fraction that miss. Dimensionless.

Address lines for a memory size

\#\text{addr lines} = \log_2(\#\text{addressable words})

A $W$ -word chip needs $\log_2 W$

Chip count and select lines

N_{chips}=\dfrac{T}{W},\qquad \#\text{select} = \log_2\!\frac{T}{W}

Effective access time with page faults

EAT = (1-p)\,t_{mem} + p\,t_{fault}

DRAM vs SRAM

\text{SRAM: 6T latch, no refresh};\;\;\text{DRAM: 1T1C, periodic refresh}

SRAM is faster/lower-density (cache); DRAM is denser/cheaper but must be refreshed (main memory). Both volatile.

Worked examples

Average memory access time from hit rate

Problem. A cache has an access time of $2\,\text{ns}$ and a hit rate of $95\%$ . On a miss, the block is fetched from main memory in an additional $80\,\text{ns}$ . Find the average memory access time.

Solution. Miss rate

= 1-0.95 = 0.05

.

AMAT = t_{hit} + m\,t_{penalty} = 2 + 0.05(80) = 2 + 4.0 = 6.00\,\text{ns}

. Sanity check:

6\,\text{ns}

sits just above the

2\,\text{ns}

hit time and far below the

82\,\text{ns}

full miss time, exactly because 95% of accesses hit. Units are all ns, consistent.

Splitting an address into tag, index, and offset

Problem. A byte-addressed system has $32$ -bit addresses and a $16\,\text{KB}$ direct-mapped cache with $32$ -byte blocks. Find the number of offset, index, and tag bits.

Solution. Offset:

\log_2 32 = 5

Two-level cache effective access time

Problem. An L1 cache has a $1\,\text{ns}$ access time and a $5\%$ local miss rate. L2 has a $10\,\text{ns}$ access time and a $40\%$ local miss rate. Main memory takes $100\,\text{ns}$ . Find the AMAT.

Address decoding for a memory bank

Problem. Build a $64\,\text{KB}$ ( $\times 8$ ) memory from $8\,\text{K}\times 8$ chips. How many chips, how many address lines per chip, how many total address lines, and how many chip-select lines from the decoder?

Solution. Chips

= 64\,\text{K}/8\,\text{K} = 8

Common pitfalls

•Adding the hit time into the miss penalty twice. AMAT pays $t_{hit}$ once on every access; the penalty $t_{penalty}$ is the EXTRA time on a miss, not the full miss time. If a problem gives the full miss time $t_{miss}$ , use $AMAT = h\,t_{hit} + (1-h)\,t_{miss}$ instead.
•Calling DRAM nonvolatile because it is 'main memory.' Both SRAM and DRAM are volatile; only ROM/EEPROM/flash retain data without power.
•Forgetting that DRAM needs refresh while SRAM does not — the classic distractor pairing on technology questions.
•Computing index bits from total cache size instead of the number of sets. Index bits are $\log_2 S$ where $S = C/(A\cdot B)$ ; associativity and block size both shrink $S$
•Mixing bits and bytes in the address split. With a byte-addressed cache, block size and capacity must be in bytes so the offset is $\log_2 B$ bytes.
•Treating local and global miss rates as the same in multi-level caches. The L2 penalty uses L2's LOCAL miss rate (misses among accesses that reach L2), nested inside the L1 miss rate.
•Confusing write-through with write-back: write-back needs a dirty bit and only writes memory on eviction; write-through writes memory every time.

References

NCEES FE Reference Handbook — Electrical and Computer Engineering: Computer Systems (Memory/Storage Types, Cache, Tag/Index/Offset, C = S·A·B) — Source of the cache capacity relation, address-field split, replacement and write policies.
Patterson & Hennessy, Computer Organization and Design — The Memory Hierarchy — AMAT, locality, cache mapping, and virtual memory/TLB.
Hennessy & Patterson, Computer Architecture: A Quantitative Approach — Appendix B (Memory Hierarchy) — Multi-level cache timing and miss-rate definitions.

C. Interfacing

Interfacing

How a CPU talks to the outside world — memory- vs port-mapped I/O, polling vs interrupts vs DMA, buses, serial (UART/SPI/I2C) vs parallel, ADC/DAC, and handshaking.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders

$m_{L1},m_{L2}$ are local miss rates. The L2 AMAT is nested as the L1 miss penalty; extend the same way for L3.

B

= block size (bytes). From the FE handbook.

$n$ = total address bits. Offset selects a byte in the block, index selects a set, tag is stored and compared.

.

lines; a

T

-word bank needs

\log_2 T

total lines.

$T$ = total words, $W$ = words per chip. High-order lines decode to chip-selects; low-order $\log_2 W$ lines address within a chip.

$p$ = page-fault rate, $t_{mem}$ = in-memory access time, $t_{fault}$ = fault service time (disk). Same form as AMAT for virtual memory.

bits. Sets: direct-mapped means

A=1

, so

S = C/(A\,B) = 16384/(1\times32) = 512

. Index

= \log_2 512 = 9

bits. Tag

= 32 - 9 - 5 = 18

bits. Sanity check:

5+9+18 = 32

bits total — the fields exactly partition the address, as they must.

Solution. Work inside-out. L2 effective penalty

= t_{L2} + m_{L2}\,t_{mem} = 10 + 0.40(100) = 50\,\text{ns}

.

AMAT = t_{L1} + m_{L1}\times 50 = 1 + 0.05(50) = 1 + 2.5 = 3.50\,\text{ns}

. Sanity check: AMAT lies between the L1 hit time (

1\,\text{ns}

) and L2's effective

50\,\text{ns}

, weighted toward L1 because 95% of accesses never leave L1.

. Per chip:

8\,\text{K}=2^{13}

words, so

\log_2(8192)=13

address lines. Total:

64\,\text{K}=2^{16}

, so

16

total address lines. Chip-select lines

= \log_2 8 = 3

(a 3-to-8 decoder). Sanity check:

13

within-chip lines

+\,3

select lines

=16

total lines, consistent with

2^{16}=64\,\text{K}

.