Chapter 4 — Memory | Study Notes

Chapter 4: Memory
Complete Study Notes

1. Memory Hierarchy
Computer memory is arranged in layers — fastest and smallest at the top, slowest and largest at the
bottom.

Levels (top to bottom)

• Processor Registers — inside the CPU; fastest; holds data being used right now
• Cache (L1, L2, L3) — small, fast; copies of recently used RAM data
• Main Memory (RAM) — large working memory; volatile; directly accessible by CPU
• External Storage — hard disks, SSDs, optical, tape; non-volatile; huge capacity

Key Relationships
• Faster access time = greater cost per bit
• Greater capacity = smaller cost per bit
• Greater capacity = slower access time

Why the Hierarchy Works — Locality of Reference

• Temporal locality — if a location is accessed, it will likely be accessed again soon (e.g. loops)
• Spatial/Positional locality — nearby memory locations are also likely to be accessed soon
(e.g. arrays)

2. Memory Classification Characteristics

1. Location
• Internal — registers, cache, RAM (directly accessible by CPU)
• External — hard disks, CD/DVD, tape (accessed via I/O controller)
2. Capacity
• Internal memory measured in bytes or words (1 word = 8/16/32/64 bits)
• Address space formula: N = 2ᴬ, where N = address space size, A = address length in bits
• Disks use blocks or clusters as addressable units
3. Access Methods
• Sequential — must read from beginning in order (e.g. magnetic tape)
• Direct — go near the location, then search (e.g. disk drives)
• Random — any location accessed directly in constant time (e.g. RAM)
• Associative — locate data by comparing content, not address (e.g. cache)
4. Performance
• Access time (latency) — time from address presented to data available
Page 1
Chapter 4 — Memory | Study Notes
• Memory cycle time — access time + recovery time before next access
• Transfer rate — bits per second moved into/out of memory
5. Physical Types
• Semiconductor RAM (DRAM/SRAM), Magnetic Disk & Tape, Optical (CD/DVD), Flash
6. Physical Characteristics
• Volatile — data lost when power removed (RAM)
• Non-volatile — data retained without power (disk, flash, ROM)
• Non-erasable — cannot be changed (ROM)
7. Organization
• The physical arrangement of bits to form words; a key design issue for RAM

3. Cache Memory
Cache sits between the CPU and main memory. It holds copies of recently used data from RAM so the
CPU gets near-instant access instead of waiting for slow RAM.

Cache Hit vs Miss

• Hit — requested word is found in cache; returned immediately (fast)
• Miss — word not in cache; entire block is fetched from RAM into cache, then returned

Cache Address Types

• Logical/Virtual cache — stores data by virtual address; CPU accesses directly without MMU
• Physical cache — stores data by physical (real RAM) address; MMU translates first

Cache Size Trade-off

• Larger cache = more expensive
• Larger cache = faster, up to a point — then slows because searching takes longer

Mapping Functions — How blocks map to cache lines

A. Direct Mapping
Each memory block maps to exactly one cache line.
Formula: i = j mod m (i = cache line, j = block number, m = total cache lines)

24-bit address breakdown:

• 2 bits = Word (which word within the block)
• 14 bits = Line number (which cache line to check)
• 8 bits = Tag (which block from all those that share this line)

Advantage: Simple and inexpensive

Page 2
Chapter 4 — Memory | Study Notes
Disadvantage: Two blocks sharing the same line will keep evicting each other (thrashing)

B. Associative Mapping
Any memory block can load into any cache line. No fixed assignment.
Address = 2-bit word + 22-bit tag (no line field — any line is possible)

• All tags are checked simultaneously (parallel hardware comparators)

• Very flexible, highest hit rate
• Expensive and complex — impractical for large caches

C. Set Associative Mapping (Best Balance)

Cache is divided into v sets, each containing k lines. m = v × k
Formula: i = j mod v (block maps to one set, but any line within that set)

• Most common: 2-way set associative (k=2 lines per set)

• 24-bit address: 9-bit tag + 13-bit set number + 2-bit word
• Significantly better hit rate than direct mapping, less hardware than full associative

Replacement Algorithms (when cache is full)

• LRU (Least Recently Used) — evict the block unused for the longest time [most effective]
• FIFO (First In First Out) — evict the oldest block in cache
• LFU (Least Frequently Used) — evict the block accessed fewest times
• Random — evict a random block [simple, surprisingly effective]

Write Policies
• Write Through — every cache write also immediately writes to RAM. RAM always current.
Generates heavy bus traffic.
• Write Back — writes only go to cache; RAM updated only when the modified block is evicted
(UPDATE bit). Less traffic, but RAM can be temporarily stale.

Line Size
• Optimal range: 8 to 64 bytes
• Larger blocks exploit spatial locality but reduce number of cached blocks

Multilevel Caches
• L1 cache — smallest, fastest, on-chip (per core)
• L2 cache — larger, slightly slower, on-chip
• L3 cache — largest, shared among all cores, still on-chip in modern CPUs

Unified vs Split Caches

• Unified — one cache for both instructions and data; auto-balances; simpler

Page 3
Chapter 4 — Memory | Study Notes
• Split — separate instruction cache (I-cache) and data cache (D-cache) at L1; eliminates
contention between fetch and execution units

4. Internal Memory — Semiconductor RAM

All Memory Cells Share These Properties
• Two stable states representing 0 and 1
• Can be written to (at least once)
• Can be read

DRAM — Dynamic RAM

• Stores each bit as charge in a capacitor (1 = charged, 0 = uncharged)
• Capacitors leak — must be periodically refreshed
• Simple (1 transistor + 1 capacitor per bit) — very dense and cheap
• Used for: Main memory

SRAM — Static RAM

• Stores each bit using flip-flop logic circuits
• Holds data as long as power is supplied — no refresh needed
• Faster than DRAM
• More complex (4–6 transistors per bit) — less dense, more expensive
• Used for: Cache memory

SRAM vs DRAM Summary

• Both are volatile (data lost on power off)
• DRAM: denser, cheaper, slower (needs refresh) → main memory
• SRAM: faster, more expensive, no refresh → cache

5. Read-Only Memory (ROM) Types

ROM is non-volatile — retains data without power. Data is written at manufacture and cannot normally
be changed.

ROM — Read-Only Memory

• Data permanently wired in during chip fabrication
• Cannot be altered (would require destroying the chip)
• Problems: high fixed cost; any single wrong bit ruins the batch

PROM — Programmable ROM

Page 4
Chapter 4 — Memory | Study Notes
• Written once electrically by the user after manufacture (using a PROM programmer device)
• Non-volatile; more flexible than ROM

EPROM — Erasable Programmable ROM

• Erased by exposing chip to UV light (up to 20 minutes) through a quartz window
• Then reprogrammed electrically
• Can be erased and reprogrammed many times
• More expensive than PROM

EEPROM — Electrically Erasable Programmable ROM

• Erased and written electrically — no UV light needed
• Can update individual bytes without erasing the whole chip
• Writes are slower (hundreds of microseconds per byte)
• More expensive and less dense than EPROM

Flash Memory
• Between EPROM and EEPROM in cost and functionality
• Electrically erased — entire chip or individual blocks (not individual bytes)
• Erases in seconds (much faster than EPROM's UV method)
• Same density as EPROM
• Used in: USB drives, SD cards, SSDs

6. External Memory — Magnetic Disk

A disk is a circular platter of non-magnetic substrate (aluminum or glass) coated with magnetizable
material. Data is stored as magnetic regions.

Data Organization on Disk

• Tracks — concentric rings on the platter surface (thousands per surface)
• Sectors — tracks divided into sectors, typically 512 bytes each
• Intertrack gaps — separate adjacent tracks to prevent read errors
• Intersector gaps — separate adjacent sectors

CAV — Constant Angular Velocity

• Disk spins at fixed RPM
• Outer tracks have longer physical length — bits are spaced farther apart to compensate
• Disadvantage: outer tracks store same amount of data as inner tracks — space is wasted

Disk Access Time Components

• Seek time — time for head to move to the correct track
• Rotational latency — wait for the right sector to spin under the head

Page 5
Chapter 4 — Memory | Study Notes
• Transfer time — time to actually read/write the data

7. RAID — Redundant Array of Independent Disks

RAID uses multiple disks to improve performance and/or reliability. Parity data allows recovery if a disk
fails.

RAID 0 — Striping
• Minimum 2 disks
• Data is striped (spread evenly) across all disks — reads/writes happen in parallel
• Excellent performance
• No redundancy — if one disk fails, ALL data is lost
• Use only for non-critical data

RAID 1 — Mirroring
• Minimum 2 disks
• Every block is written identically to both disks
• Excellent redundancy — if one disk fails, the other has a perfect copy
• Good performance; costs 50% of total disk space

RAID 5 — Striping with Distributed Parity

• Minimum 3 disks
• Data is striped; parity is distributed across all disks (no single parity disk bottleneck)
• Can survive failure of any one disk
• Best cost-effective balance of performance and redundancy
• Ideal for read-heavy databases; write performance is lower (parity must be recalculated)

RAID 10 — Stripe of Mirrors (RAID 1+0)

• Minimum 4 disks
• Mirrors pairs of disks, then stripes across the mirror pairs
• Excellent redundancy AND excellent performance
• Best option for mission-critical applications (e.g. databases) if cost allows
• Costs 50% of total disk space

8. Optical Memory
CD-ROM
• Non-erasable; stores ~700 MB
• Data recorded as microscopic pits on polycarbonate using a laser

Page 6
Chapter 4 — Memory | Study Notes
• Pits vs lands (flat areas) read by a low-power laser + photosensor
• Read-only — cannot be changed after manufacture

CD-R (Write-Once)
• Written once with a laser; can then be read many times
• Compatible with standard CD-ROM drives
• Ideal for permanent archival storage

CD-RW (Rewritable)
• Uses phase change material — laser switches it between two reflectivity states
• Can be written and overwritten repeatedly

DVD
• Greater capacity than CD: up to 4.7 GB (single layer), 8.5 GB (dual layer), 17 GB (double-sided)
• Bits packed more closely using a red laser (shorter wavelength)
• Available read-only, write-once, and rewritable versions

Blu-ray
• Uses blue-violet laser (shorter wavelength than DVD) — smaller pits, higher density
• Single layer: 25 GB
• Versions: BD-ROM (read-only), BD-R (write-once), BD-RE (rewritable)

9. Magnetic Tape & Flash as External Storage

Magnetic Tape
• Oldest secondary memory type
• Flexible polyester tape coated with magnetizable material
• Sequential access only — must read from beginning
• Lowest cost, slowest speed in the memory hierarchy
• Used for: offline backups, archival storage

Flash Memory (External)

• Used in SD cards (SD, mini-SD, micro-SD), USB drives
• Non-volatile — retains data without power
• USB flash drives connect via USB interface
• Memory cards used in: cameras, phones, MP3 players

Quick Reference — Key Formulas & Facts

• Address space: N = 2ᴬ (N = locations, A = address bits)
Page 7
Chapter 4 — Memory | Study Notes
• Direct mapping: i = j mod m (cache line = block number mod cache size)
• Set associative: i = j mod v (set = block number mod number of sets)
• Memory blocks: M = 2ⁿ / K (n = address bits, K = words per block)
• Optimal cache line size: 8 to 64 bytes
• DRAM refresh needed; SRAM does not need refresh
• RAID 0 = best speed, no redundancy
• RAID 1 = best redundancy, 50% storage cost
• RAID 5 = best cost-effective balance
• RAID 10 = best overall, 50% storage cost
• Flash: no byte-level erasure (whole block or chip)
• EEPROM: byte-level erasure possible

Page 8