Memory interfacing and hierarchy

Memory hierarchy

Definition. A memory hierarchy combines storage levels with different latency, capacity, and cost per bit. Registers and caches are small and fast; main memory is larger and slower; secondary storage is much larger but slower still. Frequently used data is kept near the processor to exploit temporal and spatial locality.

Example. A cache line can retain neighboring array elements after the first element is fetched.

Exam point. A hit at an upper level avoids some lower-level accesses, but misses incur the cost of the next level.

Locality of reference

Definition. Temporal locality means recently used locations are likely to be used again soon. Spatial locality means nearby locations are likely to be accessed. Sequential instruction fetch and array traversal often exhibit both forms, while pointer chains may have limited spatial locality.

Example. Repeatedly updating one loop variable shows temporal locality.

Exam point. Block transfers mainly exploit spatial locality; keeping recently used blocks exploits temporal locality.

Memory technologies

Definition. SRAM stores bits in bistable circuits and is fast without refresh, making it common in caches. DRAM stores charge in capacitors and requires refresh, enabling higher density for main memory. ROM and flash retain data without power; secondary storage provides nonvolatile capacity with different access characteristics.

Property	SRAM	DRAM
Storage cell	Bistable circuit	Capacitor and access device
Refresh	Not required	Required
Typical role	Cache	Main memory
Relative density	Lower	Higher

Example. A processor may use SRAM for L1 and DRAM modules for main memory.

Exam point. “Faster” and “denser” are relative technology tendencies, not absolute latency values.

Memory organization and capacity

Definition. A memory with $N$ addressable words of $W$ bits has capacity $NW$ bits. Address width is $\lceil\log_2 N\rceil$ when every location is addressed directly. For byte-addressable memory, byte addresses and word width must be related explicitly.

Example. 1024 words of 16 bits occupy 16,384 bits, or 2 KiB.

Exam point. Convert bits to bytes by dividing by eight.

Solved calculation. A byte-addressable memory has 18 address bits and a 32-bit word. Find byte capacity and number of aligned words.

1. Byte locations are $2^{18}=262144$ bytes = 256 KiB.
2. Each aligned word is 4 bytes.
3. Number of aligned words is $262144/4=65536$. Answer. 256 KiB and 65,536 aligned 32-bit words.

Memory interface signals

Definition. A memory interface commonly uses address lines, data lines, and control signals such as read, write, chip select, and byte enables. Address lines choose a location; data lines carry values; control signals define the transfer. Bidirectional data buses must avoid simultaneous conflicting drivers.

Example. During a read, the processor presents an address and asserts read; the selected memory drives the data bus.

Exam point. Address and data widths describe different parts of the interface.

Address decoding and chip selection

Definition. Address decoding activates one memory device or bank for a range of addresses. High-order address bits often choose the device, while lower bits address locations within it. Decoder design must avoid overlapping chip-select ranges unless the interface intentionally supports them.

Example. If a 16 KiB device occupies addresses 0x4000–0x7FFF, the upper address pattern selects it.

Exam point. Derive range size from the number of varying low-order address bits.

Solved calculation. A 32 KiB memory chip is byte-addressable and mapped starting at 0x80000. Find its inclusive end address.

1. Size is $32\times1024=32768=0x8000$ bytes.
2. Last address is start + size − 1.
3. $0x80000+0x8000-1=0x87FFF$. Answer. 0x80000 through 0x87FFF.

Memory interleaving

Definition. Interleaved memory divides consecutive addresses across multiple banks so independent accesses can overlap or successive words can be served at higher bandwidth. Low-order interleaving selects a bank from low address bits; high-order interleaving assigns contiguous ranges to banks. The arrangement affects which addresses can be accessed in parallel.

Example. With four low-order interleaved banks, byte address 10 maps to bank $10\bmod4=2$.

Exam point. Apply the specified bank-selection bits or modulo rule.

Solved calculation. Four low-order banks serve word addresses 0 through 11. Give the bank sequence and addresses in bank 2.

1. Bank number is address modulo 4.
2. Sequence is 0,1,2,3 repeated three times.
3. Bank 2 holds addresses 2,6,10. Answer. Sequence 0,1,2,3,0,1,2,3,0,1,2,3; bank 2 contains 2,6,10.

Cache basics and cache lines

Definition. A cache stores copies of memory blocks in lines containing data and metadata. A block offset selects a byte or word within a line; a tag identifies which memory block occupies that line; an index or set field selects a candidate location. Valid and dirty bits support occupancy and write-back behavior.

Example. A 64-byte line has six byte-offset bits in a byte-addressed system.

Exam point. Offset bits depend on block size, not cache capacity.

Address breakdown

Definition. For a byte-addressed cache, if block size is $B=2^b$ bytes, the offset uses $b$ low bits. A direct-mapped cache with $L=2^i$ lines uses $i$ index bits; the remaining high address bits are tag. For a set-associative cache, index bits select sets and tag distinguishes blocks within the set.

Example. A 32-bit address and 64-byte blocks use 6 offset bits.

Exam point. First compute number of lines or sets, then derive index and tag widths.

Solved calculation. A 32-bit byte-addressed machine has a 16 KiB direct-mapped cache with 64-byte blocks. Find lines and tag/index/offset widths.

1. Lines: $16\text{ KiB}/64=16384/64=256=2^8$.
2. Index bits: 8.
3. Block offset bits: $\log_2 64=6$.
4. Tag bits: $32-8-6=18$.
5. Address format is tag 18 | index 8 | offset 6. Answer. 256 lines; 18 tag bits, 8 index bits, 6 offset bits.

Direct-mapped cache

Definition. A direct-mapped cache places each memory block in exactly one cache line, selected by line index = block number modulo number of lines. It has one candidate line per access, so tag comparison is simple. Blocks that map to the same line can evict one another even when other lines are unused.

Example. With 64 lines, blocks 3, 67, and 131 all map to line 3.

Exam point. Direct mapping index is block number modulo line count.

Solved calculation. A cache has 128 lines and 16-byte blocks. Which line receives byte address 0x1234?

1. Block number is $\lfloor0x1234/16\rfloor=0x123=291$.
2. Line index is $291\bmod128=35$.
3. Offset is $0x1234\bmod16=4$. Answer. Line 35, offset 4.

Set-associative cache

Definition. A $k$-way set-associative cache has $k$ lines in each set. A block maps to one set by block number modulo set count, but may occupy any way in that set. The tag is compared against all valid ways in parallel; a replacement policy chooses a victim on a miss when the set is full.

Example. A 4-way cache with 64 sets offers four candidate lines per set.

Exam point. Set count equals total lines divided by associativity.

Solved calculation. A 32 KiB cache has 4-way associativity and 32-byte blocks. On a 32-bit byte-addressed machine, find sets and address fields.

1. Total lines: $32768/32=1024$.
2. Sets: $1024/4=256=2^8$.
3. Offset bits: $\log_2 32=5$.
4. Index bits: 8.
5. Tag bits: $32-8-5=19$. Answer. 256 sets; tag 19 bits, index 8 bits, offset 5 bits.

Fully associative cache

Definition. A fully associative cache has one set containing all lines; any memory block may be placed in any line. It has no set-index bits, but all tags may need comparison. Replacement is required when no invalid line remains. Fully associative placement reduces conflict misses at the cost of more comparison hardware.

Example. A 16-line fully associative cache can place a block in any of its 16 lines.

Exam point. The offset remains; index width is zero.

Solved calculation. A 4 KiB fully associative cache has 64-byte blocks and 32-bit addresses. Find tag and offset widths.

1. Offset width is $\log_2 64=6$.
2. There is one set, so index width is 0.
3. Tag width is $32-6=26$. Answer. 26 tag bits, 0 index bits, 6 offset bits.