PadhaikoAll subjects

Memory System

Computer Organization and Architecture (ENCT 303)

Open in the Padhaiko app

4.1 Characteristics of memory system

Every memory subsystem in a computer is characterized along seven key architectural dimensions:

  1. Location: Internal (CPU registers, L1/L2/L3 cache, main memory) versus External (magnetic disks, SSDs, optical discs, magnetic tapes accessed via I/O controllers).
  2. Capacity: Total information stored, measured in bytes or words (e.g., RAM, SSD).
  3. Unit of Transfer: Number of bits read or written in one access—typically the word for main memory and fixed-size blocks/sectors ( or ) for external storage.
  4. Access Method:
    • Sequential Access: Data accessed in linear order from the current position (e.g., magnetic tape).
    • Direct Access: Read/write head jumps near a track/block, then searches sequentially (e.g., magnetic disk).
    • Random Access: Any addressable location takes the same constant time regardless of physical position (e.g., SRAM, DRAM, ROM).
    • Associative (Content-Addressable) Access: Word retrieved based on matching a portion of its contents simultaneously rather than by address (e.g., cache tag arrays, TLBs).
  5. Performance:
    • Access Time (Latency): Time from presenting a valid address to completing the read/write.
    • Memory Cycle Time: Access time plus any recovery/precharge time before the next access can begin.
    • Transfer Rate: Rate at which data moves into/out of memory ( for random access).
  6. Physical Type: Semiconductor (SRAM, DRAM, Flash), magnetic surface (HDD, tape), or optical (CD, DVD, Blu-ray).
  7. Physical Characteristics (Volatility & Erasability): Volatile (loses data on power-off, e.g., SRAM/DRAM) vs. Non-volatile (retains data, e.g., ROM, Flash, HDD); Erasable/Rewritable vs. Non-erasable (mask ROM).

4.2 Memory classification and hierarchy

No single memory technology simultaneously offers minimal cost per bit, massive capacity, and CPU-register speed. Computers therefore arrange storage into a memory hierarchy governed by a fundamental trade-off: going down the hierarchy decreases cost per bit, increases capacity, and increases access time (slower).

The Computer Memory Hierarchy (Top to Bottom)
LevelMemory TypeTypical CapacityTypical Access TimeVolatility
1CPU RegistersHundreds of bytes – KBVolatile
2Cache Memory (L1, L2, L3)KB – tens of MBVolatile
3Main Memory (DRAM)GBsVolatile
4Solid-State Drive / FlashHundreds of GB – TBNon-volatile
5Magnetic Hard Disk (HDD)TBsNon-volatile
6Optical Disc / Magnetic TapeGBs – tens of TBSeconds – minutesNon-volatile

The hierarchy works efficiently because real programs exhibit locality of reference:

4.3 Semiconductor memory and its types, read only memory, read/write memory

Semiconductor memories are integrated circuits whose basic element is a memory cell capable of representing 0 or 1, supporting select, control, and data terminals. They divide into Read/Write Memory (RAM) and Read-Only Memory (ROM).

Read/Write Memory (RAM)

AspectStatic RAM (SRAM)Dynamic RAM (DRAM)
Storage ElementFlip-flop latch ( transistors per cell)Single transistor + storage capacitor ( cell)
Refresh RequirementNone (retains state as long as power is supplied)Periodic refresh required every few milliseconds as capacitor leaks
Density & CostLower density, higher cost per bitHigh density, low cost per bit
SpeedVery fast ()Slower ()
Primary RoleCPU Cache memory (L1/L2/L3)Main system memory

Read-Only Memory (ROM)

ROM retains data permanently without power (non-volatile) and is used for firmware, BIOS/UEFI, and bootloaders:

4.4 Ram modules and interfaces: DDR, DIMM and SODIMM

Modern main memory uses Synchronous DRAM (SDRAM) packaged on printed circuit modules rather than bare DIP chips:

4.5 Cache memory

4.5.1 Cache principles

Definition

Cache Memory, Hit Ratio, and AMAT

A cache is a small, ultra-fast SRAM buffer placed between the CPU and main memory to hold copies of frequently used memory blocks.

(If cache and main memory are accessed in parallel on a miss so is total miss time without adding , then .)

4.5.2 Elements of cache design

  1. Cache Size: Large enough to keep the average hit ratio high, yet small enough to fit on-chip and maintain fast tag lookup and low power.
  2. Mapping Function: Determines where a main memory block of size bytes maps inside a cache of lines (slots). For an -bit physical address:
Comparison of Cache Mapping Techniques
Mapping TypePlacement RuleAddress Partition (Tag / Index / Offset)Hardware Cost & Conflict Rate
Direct MappingBlock maps strictly to cache line ( lines)Tag + Line Index ( bits) + Word/Byte OffsetSimplest hardware (1 comparator); high conflict misses if two active blocks share a line
Fully AssociativeAny memory block can be placed in any cache lineTag + Word/Byte Offset (no index bits)Lowest conflict misses; very expensive (parallel comparators across all lines)
Set-Associative (-way)Cache divided into sets; block maps to set and any of its linesTag + Set Index ( bits) + Word/Byte OffsetBalanced trade-off: comparators per lookup, sharp reduction in conflict misses
  1. Replacement Algorithms: Needed when a set (or full associative cache) has no empty slot on a miss:
    • LRU (Least Recently Used): Evicts the line untouched for the longest time (high hit rate; tracks recency bits).
    • FIFO (First-In, First-Out): Evicts the oldest loaded block regardless of recent hits.
    • LFU (Least Frequently Used): Evicts the block with the fewest references.
    • Random: Picks a victim slot uniformly at random (zero tracking hardware).
  2. Write Policy: Keeps cache and main memory consistent on writes:
    • Write-Through: Every write updates both the cache line and main memory immediately (simple coherence, higher memory bus traffic).
    • Write-Back: Updates only the cache line and sets a dirty bit; writes back to main memory only when the dirty line is evicted (minimizes bus traffic; requires dirty-bit coherence tracking).
  3. Block (Line) Size: Increasing block size initially raises hit rate via spatial locality, but overly large blocks reduce total number of distinct blocks in the cache and increase miss-transfer penalty.
  4. Single vs. Multilevel Caches: Modern CPUs use L1 (tiny, on-core, cycles), L2 (medium per-core), and L3 (large shared last-level cache) so misses in L1 are absorbed by L2/L3 rather than paying full DRAM latency.
  5. Unified vs. Split Cache: A unified cache stores both instructions and data together; a split cache (Harvard L1 architecture: separate L1-I and L1-D) eliminates structural hazards in pipelined CPUs by allowing simultaneous instruction fetch and data load/store in the same clock cycle.

4.6 External memory

4.6.1 Magnetic disk

A Hard Disk Drive (HDD) stores data magnetically on rigid spinning platters coated with magnetizable material:

where average rotational latency is half a revolution: , and transfer time for bytes at track capacity bytes per revolution is .

4.6.2 RAID: Level 1 to 5

RAID (Redundant Array of Independent Disks) combines multiple physical drives into one logical unit to boost throughput, fault tolerance, or both.

RAID Levels 1 through 5
RAID LevelCore MechanismMin. DisksFault ToleranceKey Characteristics
RAID 1Disk Mirroring (exact duplicate of every disk)Survives failure of 1 disk per mirrored pairHigh read speed (reads from either mirror); storage efficiency
RAID 2Bit-level striping with Hamming ECC disksSingle-bit error correctionComplex synchronized spindles; practically obsolete
RAID 3Byte-level striping with a dedicated parity diskSurvives 1 disk failureHigh sequential transfer rate; dedicated parity disk bottlenecks random writes
RAID 4Block-level striping with a dedicated parity diskSurvives 1 disk failureIndependent block reads; parity disk still bottlenecks concurrent writes
RAID 5Block-level striping with distributed parity across all disksSurvives any 1 disk failureEliminates single parity-disk bottleneck; usable capacity

4.6.3 Optical memory

Optical storage uses a laser beam to read (and write) microscopic pits and lands (or phase-change marks) along a spiral track on a polycarbonate disc:

4.6.4 Magnetic tape

Magnetic tape stores data sequentially on a flexible polyester ribbon coated with magnetic oxide (e.g., LTO cartridges). Because access requires winding past earlier blocks (sequential access), latency is tens of seconds, making tapes unsuitable for primary random I/O. However, with ultra-low cost per terabyte, multi-decade shelf life, and air-gapped removability, magnetic tape remains widely used for archival backups and disaster recovery.

4.6.5 SSD

A Solid-State Drive (SSD) uses non-volatile NAND Flash memory managed by an embedded SSD Controller and Flash Translation Layer (FTL), with zero moving mechanical parts:

Worked Out Examples

Example 1

1 (6 marks)

A computer has a byte-addressable main memory (-bit physical address) and a direct-mapped cache with a block (line) size of .

  1. Determine the number of cache lines, and break down the -bit address into Tag, Line Index, and Byte Offset fields.
  2. Repeat the address breakdown if the same cache is organized as -way set-associative with -byte blocks.

Finding block offset and number of cache lines:

  • Block size .
  • Total cache lines .

Partitioning the 32-bit address for Direct Mapping:

  • Line Index bits .
  • Tag bits .
  • Partition: Tag = 16 bits | Line Index = 10 bits | Offset = 6 bits.

Partitioning the 32-bit address for 4-Way Set-Associative Mapping:

  • Set Index bits .
  • Byte Offset remains .
  • Tag bits .
  • Partition: Tag = 18 bits | Set Index = 8 bits | Offset = 6 bits.
Answer:
  1. cache lines; Direct-mapped: 16 Tag, 10 Index, 6 Offset bits. 2. 4-way set-associative: 18 Tag, 8 Set Index, 6 Offset bits.
Example 2

2 (5 marks)

A CPU has an L1 cache with an access time of and a hit ratio of . Main memory access time on a miss is . Calculate the Average Memory Access Time (AMAT) assuming:

  1. Sequential lookup (cache is checked first; on a miss, main memory is then accessed).
  2. Simultaneous/overlapped lookup (cache and memory start together, so a miss takes total).

Computing AMAT for sequential (hierarchical) lookup: With , miss ratio , , and :

Computing AMAT for simultaneous lookup:

Answer:
  1. Sequential lookup ; 2. Simultaneous lookup .
Example 3

3 (6 marks)

A magnetic hard disk rotates at , has an average seek time of , and stores () per track. Estimate the total time required to read a single (-byte) sector from this disk.

Computing rotation period and average rotational latency:

Computing data transfer time for one sector:

Summing total disk access time:

Answer:

Average rotational latency , transfer time , and total access time .

Exercises

Exercise — Memory System

Question 1

Explain the memory hierarchy in a modern computer system and show how temporal locality and spatial locality justify using small fast caches alongside large slow DRAM and secondary storage.

Describing the memory hierarchy trade-off: Storage levels progress from CPU registers L1/L2/L3 SRAM cache DRAM main memory SSD/HDD secondary storage tape/optical archival media. Moving down the hierarchy increases capacity and lowers cost per bit, while increasing access latency.

Connecting locality of reference to cache effectiveness:

  • Temporal locality: Programs reuse the same variables and loop instructions repeatedly within short intervals; keeping them in upper-level cache turns slow memory fetches into rapid cache hits.
  • Spatial locality: Programs access sequential instructions and contiguous array elements; fetching entire cache blocks () on a single miss preloads adjacent words that are about to be requested.
Answer:

The memory hierarchy bridges the speed-cost gap between CPU registers and bulk storage by exploiting temporal locality (reused items stay in fast cache) and spatial locality (adjacent items are prefetched together in cache blocks).

Question 2

Compare SRAM vs. DRAM, and briefly differentiate among PROM, EPROM, EEPROM, and NAND Flash memory, as well as DIMM vs. SODIMM RAM modules.

Comparing SRAM, DRAM, and ROM variants:

  • SRAM vs. DRAM: SRAM uses 6-transistor flip-flop latches, needs no refresh, and serves as fast CPU cache; DRAM uses 1-transistor + 1-capacitor cells, requires periodic refresh, and offers much higher density and lower cost for main memory.
  • PROM / EPROM / EEPROM / Flash: PROM is one-time fuse-programmable; EPROM is UV-light erasable; EEPROM is byte-wise electrically erasable; Flash is block-wise electrically erasable high-density memory used in SSDs and firmware.

Differentiating DIMM and SODIMM:

  • DIMM: Full-length dual in-line DDR module used in desktops and servers (e.g., 288 pins for DDR4/DDR5).
  • SODIMM: Compact small-outline version roughly half as wide, designed for laptops and compact embedded boards.
Answer:

SRAM (flip-flops, no refresh, cache) contrasts with DRAM (capacitors, refresh needed, main RAM). PROM/EPROM/EEPROM/Flash differ by erasability granularity (none, UV, byte-electrical, block-electrical). DIMMs serve desktops/servers while compact SODIMMs serve laptops.

Question 3

A CPU generates -bit byte addresses and uses an (-byte) -way set-associative cache with -byte blocks. Find:

  1. Total number of cache lines and number of sets.
  2. The bit widths of the Tag, Set Index, and Byte Offset fields.

Computing lines, sets, and offset bits:

  • Block size .
  • Total cache lines .
  • With ways per set, number of sets .

Computing Set Index and Tag bit widths:

  • .
  • .
Answer:
  1. lines arranged into sets. 2. Address partition: Tag = 13 bits, Set Index = 7 bits, Byte Offset = 4 bits.
Question 4

A processor uses a sequential-lookup cache with and main memory latency . Calculate the AMAT when the hit ratio is , and again if a larger block size raises the hit ratio to . Also explain the difference between write-through and write-back cache policies.

Computing AMAT at and hit ratios:

  • At : .
  • At : .

Explaining write-through vs. write-back:

  • Write-Through: Updates both cache and main memory on every write; simple and always coherent, but generates heavy memory write traffic.
  • Write-Back: Updates only the cache line and marks a dirty bit, deferring the main memory write until that cache line is evicted; lowers bus traffic at the cost of dirty-bit tracking.
Answer:

at hit rate and at hit rate. Write-through writes to memory immediately on every store, whereas write-back writes to memory only upon evicting a modified (dirty) line.

Question 5

Compare RAID levels 1, 3, 4, and 5 in terms of striping granularity, parity placement, fault tolerance, and write performance. If an array uses identical disks, what is the usable capacity under RAID 1 (two mirrored pairs / RAID 10-equivalent mirroring) versus RAID 5?

Comparing RAID 1, 3, 4, and 5:

  • RAID 1: Full disk mirroring; no striping/parity; tolerates 1 disk failure per mirrored pair; fast reads, usable capacity.
  • RAID 3: Byte-level striping with a dedicated parity disk; requires synchronized spindles; tolerates 1 failure; good for large sequential transfers.
  • RAID 4: Block-level striping with a dedicated parity disk; supports independent reads, but all writes hit the single parity disk (write bottleneck).
  • RAID 5: Block-level striping with distributed parity rotated across all disks; tolerates any 1 disk failure while eliminating the dedicated parity bottleneck.

Computing usable capacity for disks of each:

  • Mirrored (RAID 1): Only half the disks store unique data: (). (Raw mirrored total is , with usable.)
  • RAID 5: One disk's worth of space holds distributed parity: ().
Answer:

RAID 1 mirrors entire disks ( usable on ), RAID 3/4 use a dedicated parity disk (byte vs. block striping), and RAID 5 distributes parity across all blocks ( usable) to remove the single-parity-disk bottleneck.

← Control UnitComputer Arithmetic →