Hierarchy & main memory

ACompressed recap

🧾

Hierarchy: registers, SRAM caches, DRAM main memory, SSD/disk: down = slower, bigger, cheaper; average cost Σ cᵢSᵢ / Σ Sᵢ. Temporal and spatial locality; misses move whole blocks; h = hits/accesses. AMAT: hierarchical t_c + (1−h)t_m; simultaneous h·t_c + (1−h)t_m; multi-level versions; speedup t_m/T. Chips: SRAM (no refresh, caches) vs DRAM (refresh, main memory); 2ᵏ × n chip has k address and n data lines; refresh overhead = rows × row time / period; multiplexed DRAM pins = half the address bits. Interfacing: chips = (W/w)(B/b); common lines log₂ w; decoder log₂(W/w) inputs. Disk: access = seek + half rotation + transfer. Low-order interleaving: t_a + k·t_b per block.

BMerged rule card

4.1.1 Why a hierarchy: speed, cost, size; locality; hit, miss, hit ratio

• Down the hierarchy: slower, larger, cheaper per bit. Avg cost = Σ cᵢSᵢ / Σ Sᵢ.
• Temporal locality: reuse soon; spatial locality: neighbours soon.
• Hit ratio h = hits / accesses; miss ratio = 1 − h.
• Misses move whole blocks; a cache slot is a line.

4.1.2 Average memory access time: hierarchical vs simultaneous access; multi-level formulas

• Given hit and miss times directly: T = h·t_hit + (1−h)·t_miss.
• Hierarchical: T = t_c + (1−h)t_m. Simultaneous: T = h·t_c + (1−h)t_m.
• 3 levels hierarchical: t₁ + (1−h₁)[t₂ + (1−h₂)t₃]; simultaneous: h₁t₁ + (1−h₁)h₂t₂ + (1−h₁)(1−h₂)t₃.
• Default to hierarchical unless the question says parallel/simultaneous.
• Speedup = t_m / T.

4.1.3 Memory chips: SRAM vs DRAM, ROM types, DRAM refresh; chip organisation 2ᵏ × n

• SRAM: flip-flop, fast, no refresh, caches. DRAM: capacitor, dense, cheap, refresh, main memory.
• ROM, PROM (once), EPROM (UV), EEPROM (byte, electrical), Flash (block, electrical).
• 2ᵏ × n chip: k address lines, n data lines, CS.
• DRAM refresh overhead = rows × row time / refresh period; multiplexed address pins = half the bits (square array).

4.1.4 Memory interfacing: building larger memories from chips, address decoding, chip counts

• Chips = (W/w)(B/b). Address lines = log₂ W; common = log₂ w; decoder log₂(W/w) → W/w.
• Width expansion: shared address and CS; depth expansion: decoder on high bits drives CS.
• Address range: fixed high bits, all combinations of the low bits.
• Partial decoding → aliasing.

4.1.5 Secondary storage and bandwidth: disk access time, transfer rate, interleaved memory

• Capacity = surfaces × tracks × sectors × bytes. Cylinder = same track on all surfaces.
• Access = seek + ½ rotation + transfer; rotation = 60/rpm s; transfer rate = bytes per track × rps.
• Low-order interleaving: block of k words in t_a + k·t_b vs k(t_a + t_b).

CInterleaved GATE-style questions

Q1NAT2 marksAMAT

t_c = 3 ns, t_m = 90 ns, h = 0.96, hierarchical. Average (ns)?

Numerical answer: ________

Q2NAT2 marksSimultaneous

Same numbers, simultaneous access. Average (ns)?

Numerical answer: ________

Q3NAT1 markMisses from blocks

A cold cache with 128-byte blocks; a loop reads 4,096 consecutive 4-byte integers starting at a block boundary. Misses?

Numerical answer: ________

Q4NAT2 marksRefresh

A DRAM has 8,192 rows, each refreshed every 64 ms, at 60 ns per row. Refresh overhead in percent?

Numerical answer: ________

Q5NAT2 marksChips

How many 16K × 4 chips make a 256 KB byte-addressable memory?

Numerical answer: ________

Q6MCQ1 markRange

In a 16-bit address space, a 4 KB chip is selected when A15–A12 = 0011. Its range is:

• (A) 0x3000–0x37FF
• (B) 0x0300–0x03FF
• (C) 0x1100–0x1FFF
• (D) 0x3000–0x3FFF

Q7NAT2 marksDisk

15,000 rpm disk, average seek 3 ms, 500 sectors per track. Average time to read one sector (ms)?

Numerical answer: ________

Q8MSQ2 marksConcepts

Which are true?

• (A) SRAM needs refresh.
• (B) A 2ᵏ × n chip has n data lines.
• (C) Flash memory is non-volatile.
• (D) DRAM row and column addresses can share pins.

DAnswer Vault