Unit 5: Memory Unit

The memory system stores instructions and data and supplies them to the CPU. Because no single technology is simultaneously fast, large and cheap, computers layer several memory types into a hierarchy, exploiting the locality of programs so that the CPU mostly sees the speed of the fastest level while paying, on average, close to the cost of the cheapest.

• Locality of reference: the empirical basis of the hierarchy — programs reuse recently used addresses (temporal locality) and nearby addresses (spatial locality), so keeping active data in fast memory pays off.
• Access time (tₐ): time between issuing an address and receiving the word; falls sharply as you descend toward registers.
• Cost per bit and capacity: inversely related to speed — fast SRAM is expensive per bit, slow disk is cheap, so fast levels are small.
• Hit and miss: a hit is data found in a given level; a miss forces access to the next slower level.

II. Memory Hierarchy — Speed, Cost and Locality

The hierarchy arranges memory in levels ordered by speed, so that most references are satisfied near the top.

A. Levels from top to bottom

• Registers: inside the CPU, ~1 ns, holding a few hundred bytes; fastest and most expensive.
• Cache (SRAM): 1–10 ns, KB–MB, bridges the CPU–main-memory gap.
• Main memory (DRAM): ~50–100 ns, GB scale, holds the running program.
• Auxiliary memory: magnetic disk / SSD, ms-scale, holds programs not currently executing.

B. Effective access time

• Two-level formula: for a cache with hit ratio h,

t_avg = h · t_cache + (1 − h) · t_main

• Symbols: h = fraction of hits (0–1); t_cache, t_main = access times of each level.
• Numeric example: with t_cache = 5 ns, t_main = 70 ns, h = 0.95:
  t_avg = 0.95×5 + 0.05×70 = 4.75 + 3.5 = 8.25 ns, close to cache speed.

III. Main Memory — The Working Store

Main memory holds the instructions and data of currently executing programs, addressed directly by the CPU.

A. Definition and organisation

• RAM (Random Access Memory): read/write, volatile; realised as dynamic RAM (DRAM), which uses one transistor–capacitor cell and must be refreshed.
• ROM (Read Only Memory): non-volatile, stores the bootstrap loader and firmware; variants PROM, EPROM, EEPROM allow limited programming/erasure.
• Word and address: memory of 2ᵏ words needs a k-bit address; e.g. 1K×16 memory has a 10-bit address bus and 16 data lines.
• Chip expansion: small chips are combined via a decoder that selects a chip using high-order address bits while low-order bits address within a chip.

IV. Auxiliary Memory — Backing Storage

Auxiliary (secondary) memory provides large, cheap, non-volatile storage for data not immediately needed by the CPU.

A. Devices and access model

• Magnetic disk: data on concentric tracks divided into sectors; access time = seek time + rotational latency + transfer time.
• Magnetic tape: sequential access only, used for archival backup.
• Solid-state drive (SSD): flash memory, no moving parts, far lower latency than disk.
• Access characteristic: not random — location influences access time, unlike main memory.

V. Cache Memory — Bridging the CPU–Memory Gap

Cache is a small, fast SRAM buffer between CPU and main memory that holds recently and nearby used blocks, so most references become hits.

A. Principle of operation

• Block transfer: data moves between cache and main memory in fixed-size blocks (lines), exploiting spatial locality.
• Hit ratio: performance metric h = hits / total references; typical caches achieve h > 0.9.

B. Writing into Cache concept

The write policy governs how a modification in cache is reflected in main memory, and there are two opposed schemes.

1. Write-through: every write updates both cache and main memory immediately.
   • Trait: memory always consistent with cache; simple but slower, as each write incurs a main-memory access.
2. Write-back (copy-back): writes update only the cache; a dirty bit marks modified blocks, written to memory only on replacement.
   • Trait: fast repeated writes, but memory temporarily stale — a concern in multiprocessor coherence.

• Write miss handling: write-allocate loads the block into cache first; no-write-allocate writes straight to memory.

C. Mapping Techniques

Mapping decides which cache line a main-memory block may occupy, trading hardware cost against hit ratio.

1. Direct mapping: each block maps to exactly one line via line = block address mod (number of lines).
   • Address split: tag | line (index) | word offset. Simplest and cheapest, but two blocks contending for one line cause repeated misses.
   • Example: 128 lines, block 260 → 260 mod 128 = 4; block stored in line 4 with tag ⌊260/128⌋ = 2.
2. Associative mapping: any block may sit in any line; the full block address is stored as a tag and searched in parallel.
   • Trait: highest flexibility and hit ratio, but expensive comparators for parallel tag search.
3. Set-associative mapping: the compromise — lines are grouped into sets, a block maps to one set but any line within it.
   • Address split: tag | set | word. An n-way set-associative cache searches n tags per set; e.g. 4-way balances cost and conflict misses.

D. Replacement policies

• LRU (Least Recently Used): evicts the block unused for the longest time; best matches temporal locality.
• FIFO / Random: cheaper approximations used when tracking recency is costly.

VI. Virtual Memory — Address Space Beyond Physical RAM

Virtual memory lets programs use a logical address space larger than physical main memory by keeping only active portions in RAM and the rest on disk.

A. Address translation

• Logical vs physical address: the CPU issues virtual addresses; a mapping table converts them to physical addresses.
• Paging: address space split into fixed-size pages, memory into equal frames; a page table maps page number → frame number.
• Page fault: reference to a page not in memory triggers a fault, and the OS loads it from disk, possibly evicting another page.
• TLB (Translation Lookaside Buffer): small associative cache of recent page-table entries, avoiding a table lookup on every access.

B. Segmentation

• Segments: variable-length logical units (code, stack, data) mapped by a segment table holding base and limit; may be combined with paging.

VII. Introduction to Parallel Processing — Doing More at Once

Parallel processing performs many operations simultaneously to raise throughput beyond what a single sequential stream allows.

A. Flynn's classification

• SISD: single instruction, single data — the classic uniprocessor.
• SIMD: one instruction on many data streams — vector/array processors.
• MISD: multiple instructions on one data stream — rare, largely theoretical.
• MIMD: multiple instructions, multiple data — true multiprocessors.

B. Pipelining

Pipelining overlaps the execution of successive instructions by dividing processing into stages, like an assembly line.

• Stages: a typical instruction pipeline uses IF (fetch), ID (decode), EX (execute), MEM (memory), WB (write-back).
• Speedup: for k stages and n tasks,

Speedup S = (n · k) / (k + n − 1)

approaching k as n grows; k = stage count, n = task count.

• Hazards limit gains:
  • Structural: two stages need the same resource.
  • Data: an instruction needs a result not yet written — eased by forwarding.
  • Control: branches invalidate prefetched instructions, causing stalls.
• Arithmetic pipeline: separate example — floating-point add split into align-exponent, add-mantissa, normalise, round stages.

VIII. Multiprocessors — Multiple CPUs, Shared Work

A multiprocessor system contains two or more CPUs sharing memory and I/O under one operating system to increase reliability and throughput.

A. Characteristics of Multiprocessors

• Coupling:
  1. Tightly coupled: CPUs share a common main memory (shared-memory / UMA); communication through that memory.
  2. Loosely coupled: each CPU has private memory, communicating by message passing over a network (distributed memory).
• Cache coherence: private caches may hold stale copies of a shared block; protocols (e.g. MESI) enforce a consistent view.
• Benefits: higher throughput, graceful degradation if one CPU fails, and better resource utilisation.

B. Interconnection Structures

The interconnection network links processors, memory modules and I/O, and its topology sets communication cost.

• Time-shared / common bus: all units share one bus — cheap, but the bus is a bottleneck and single point of contention.
• Multiport memory: each memory module has separate ports for each CPU with built-in priority — fast, but costly and fixed in size.
• Crossbar switch: a grid of switch points connects any processor to any memory simultaneously — high bandwidth, but hardware grows as processors × modules.
• Multistage switching network: stages of small switches (e.g. Omega network built from 2×2 elements) route requests, balancing cost and concurrency between bus and crossbar.
• Hypercube: each of 2ⁿ nodes connects to n neighbours differing by one address bit; scalable for loosely coupled systems, with routing along differing bit positions.