The Memory Hierarchy

No single memory technology is simultaneously fast, large and cheap. The solution is a hierarchy: a small fast memory close to the CPU backed by progressively larger, slower, cheaper levels.

   Going DOWN the hierarchy:
      capacity  INCREASES
      cost/bit  DECREASES
      access time INCREASES
      frequency of access by the CPU DECREASES

1. Why the Hierarchy Works — Locality of Reference

   TEMPORAL LOCALITY:
      A memory location accessed now is likely to be accessed again soon.
      Cause: loops, repeated variables, recursive calls.

   SPATIAL LOCALITY:
      Locations NEAR a recently accessed address are likely to be accessed soon.
      Cause: sequential instruction fetch, arrays, structure fields.

   SEQUENTIAL LOCALITY (a special case of spatial):
      Instructions are usually executed in address order.

   The 90/10 rule:  a program spends about 90% of its execution time
                    in about 10% of its code.

   -> Keep that 10% in the fastest memory and the whole hierarchy behaves
      almost as fast as the top level, at almost the cost of the bottom level.

2. Main Memory

Main memory (primary memory) holds the programs and data currently in use. It is directly addressable by the CPU.

SRAM vs DRAM — a guaranteed exam table

   Why DRAM needs refreshing:
      The capacitor storing each bit leaks its charge in a few
      milliseconds. A REFRESH CIRCUIT reads and rewrites every row
      periodically (typically every 64 ms for the whole array).
      Reading a DRAM cell is DESTRUCTIVE, so every read is followed
      by an automatic rewrite.

ROM family

   ROM holds: the bootstrap loader (BIOS/UEFI), firmware, microcode,
              lookup tables that must survive power-off.

3. Memory Chip Organization

   A memory chip is specified as  (number of words) x (bits per word).

   A 1K x 8 chip:
      1024 words, each 8 bits
      Address lines: log2(1024) = 10
      Data lines   : 8
      Control      : CS (chip select), RD, WR

   Internal structure:
      An address decoder selects one ROW of the memory array.
      For large arrays a two-dimensional (coincident) decoding scheme is used:

         1K words = 32 rows x 32 columns
         5 address bits -> row decoder (1-of-32)
         5 address bits -> column decoder (1-of-32)

      Two 5-to-32 decoders (64 gates) replace one 10-to-1024 decoder
      (1024 gates) -> an enormous saving.

4. Memory Expansion — the standard numericals

Increasing the word SIZE (more bits per word)

   Build 1K x 16 memory using 1K x 8 chips.

   Chips needed = 16 / 8 = 2
   Both chips receive the SAME 10 address lines and the SAME chip select.
   Chip 1 supplies data bits D7-D0;  chip 2 supplies D15-D8.

Increasing the NUMBER of words (more capacity)

   Build 4K x 8 memory using 1K x 8 chips.

   Chips needed = 4K / 1K = 4
   A10 and A11 feed a 2-to-4 DECODER whose outputs are the four chip selects.
   A9-A0 go to all four chips.

   Address map:
      Chip 0: 0000H - 03FFH      Chip 2: 0800H - 0BFFH
      Chip 1: 0400H - 07FFH      Chip 3: 0C00H - 0FFFH

Both at once

   Q: Design 8K x 16 memory using 2K x 8 chips.

      Chips for word size  = 16/8 = 2
      Chips for capacity   = 8K/2K = 4
      TOTAL chips          = 2 x 4 = 8

      Address lines per chip = log2(2K) = 11   (A10-A0)
      Chip-select lines      = log2(4)  = 2    (A12, A11) -> a 2-to-4 decoder
      Total address lines    = 13              (8K = 2^13)

   Q: How many 128 x 8 RAM chips are needed to provide 2048 bytes
      of memory, and how many address lines are needed?

      Chips = 2048 / 128 = 16 chips
      Address lines per chip = log2(128) = 7
      Chip select lines      = log2(16)  = 4
      Total address lines    = 11  (2048 = 2^11)

5. Memory Address Map

   A system has 512 bytes of RAM (four 128x8 chips) and 512 bytes of ROM.

   Component | Hex address | A9 A8 A7 A6 A5 A4 A3 A2 A1 A0
   ----------+-------------+-------------------------------
   RAM 1     | 0000 - 007F |  0  0  0  x  x  x  x  x  x  x
   RAM 2     | 0080 - 00FF |  0  0  1  x  x  x  x  x  x  x
   RAM 3     | 0100 - 017F |  0  1  0  x  x  x  x  x  x  x
   RAM 4     | 0180 - 01FF |  0  1  1  x  x  x  x  x  x  x
   ROM       | 0200 - 03FF |  1  x  x  x  x  x  x  x  x  x

   A9 distinguishes RAM (0) from ROM (1).
   A8 A7 select which RAM chip (via a 2-to-4 decoder).
   A6-A0 address the byte within the chip.

6. Memory Performance Terms

   Memory interleaving example (4-way):

      Address mod 4 = 0  ->  Bank 0
      Address mod 4 = 1  ->  Bank 1
      Address mod 4 = 2  ->  Bank 2
      Address mod 4 = 3  ->  Bank 3

   Sequential access can start Bank 1 while Bank 0 is still busy
   -> up to 4x the bandwidth of a single bank.

Summary

   Hierarchy   : registers -> cache -> main memory -> disk -> tape
   Works because of TEMPORAL and SPATIAL LOCALITY
   SRAM        : flip-flops, fast, no refresh, expensive -> cache
   DRAM        : capacitors, dense, needs refresh, cheap -> main memory
   ROM family  : Mask, PROM, EPROM, EEPROM, Flash
   Expansion   : chips = (needed capacity/chip capacity) x (word width ratio)

The next three lessons cover the specialised memories the syllabus names: auxiliary, associative and cache.