Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 67 ยท Memory Hierarchy

Memory Interleaving and Main-Memory Design

Build main memory from chips: size and expand RAM, decode addresses, and use low-order interleaving across banks to raise bandwidth, with Python simulations.

One memory chip is rarely big enough or fast enough. Real main memory is made of many chips (or modules) wired together, and the way you arrange them decides both the capacity and the speed you get. In this lesson you will learn how to combine chips to reach the size and word width you need, how an address decoder picks the right chip, and how interleaving spreads consecutive addresses across banks so that several accesses can overlap.

You should know the memory types from RAM, ROM, SRAM, DRAM and Flash. A memory chip is described as words x bits, for example 1K x 8, meaning 1,024 words of 8 bits each.

Capacity and chip expansion

Suppose you need a 4K x 16 memory and only have 1K x 8 chips. You can expand in two directions.

  • Width expansion: put chips side by side so each supplies part of the word. Two 1K x 8 chips share the same address and together deliver 16 bits: this gives 1K x 16.
  • Depth expansion: stack groups of chips so each group covers a different range of addresses. Four such groups give 4K x 16.

The number of chips is simply total bits divided by bits per chip: (4096 x 16) / (1024 x 8) = 8 chips, arranged as 4 groups of 2.

The address then splits in two: the low bits go to every chip (selecting a word inside a chip), and the high bits go to a decoder that enables exactly one group via its chip select line.

flowchart LR
  A["12-bit address"] --> LOW["Low 10 bits<br/>to every chip"]
  A --> HIGH["High 2 bits"]
  HIGH --> DEC["2-to-4 decoder"]
  DEC --> G0["Group 0<br/>0 to 1023"]
  DEC --> G1["Group 1<br/>1024 to 2047"]
  DEC --> G2["Group 2<br/>2048 to 3071"]
  DEC --> G3["Group 3<br/>3072 to 4095"]

High address bits select the chip group; low bits select the word inside it.

Python Plan a memory from smaller chips

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why speed is a problem

A DRAM chip needs time between the start of an access and the moment data is available (the access time) and also a recovery time before the next access to the same chip (the cycle time). A processor wants a word every clock cycle, but a single memory chip can deliver one only every few cycles. You can wait, build faster chips, or use many chips in parallel.

Memory interleaving

In interleaved memory the address space is divided over N independent banks, each with its own access circuit. While one bank recovers, another can start. With low-order interleaving, consecutive addresses go to consecutive banks: the lowest address bits select the bank, and the remaining bits select the word in the bank.

Text
bank   = address mod N
offset = address div N

For 4 banks, addresses 0, 1, 2, 3 are in banks 0, 1, 2, 3, then 4 falls in bank 0 again. A burst of sequential accesses, which is exactly what filling a cache block needs, touches a different bank each time, so up to N accesses overlap.

Compare with high-order interleaving, where the highest address bits pick the bank. Each bank then holds one contiguous range, which is useful for chip expansion (the decoder above is exactly this), but sequential accesses all hit the same bank and no overlap is possible.

Python Banks, conflicts and bandwidth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table. With one bank each of the 16 accesses must wait for the previous to finish. With four low-order banks and sequential addresses the accesses overlap and the whole burst finishes in less than a third of the time (20 cycles instead of 65). High-order interleaving gives no speedup for sequential data because the accesses all hit one bank. (Its stride-4 result is better only because that stride happens to walk across all four contiguous ranges.) And look at stride 4: with 4 banks, every address is a multiple of 4 so it maps to bank 0, and low-order interleaving is no better than a single bank. That is a bank conflict.

The classic ideal is that N banks give about N times the bandwidth for sequential access, as long as N is at least the ratio of access time to the CPU clock. Choosing the number of banks as a prime number removes the conflict for most strides, which is why some vector supercomputers used 17 or 31 banks, at the cost of a more complex modulo calculation.

Interleaving in today's machines

Modern systems apply the same idea at several levels:

  • Channels: a PC has two or four independent memory channels, each with its own bus, and consecutive cache lines alternate between them.
  • Banks and bank groups inside a DRAM chip: a chip contains several banks, and the controller reorders requests to keep different banks busy.
  • Ranks and DIMMs: more modules on a channel add more banks.

A memory controller may use a hashed address mapping instead of plain modulo so that common strides do not collide. Interleaving raises bandwidth (bytes per second) much more than it lowers latency (time for one access), a theme you will see again in storage systems and GPU memory.

Interleaving helps a stream of independent accesses. A single access still takes a full access time. If every access depends on the previous one (pointer chasing), interleaving does not help.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many 1K x 8 chips are needed to build a 4K x 16 memory?

    Total bits are 4096 x 16 = 65536; each chip has 8192 bits; so 8 chips (2 wide by 4 deep).
  2. 2. In depth expansion, what do the high address bits do?

    The decoder turns the high bits into a chip-select line for exactly one group.
  3. 3. With low-order interleaving across 4 banks, which bank holds address 10?

    10 mod 4 = 2, so the address is in bank 2.
  4. 4. Why does a stride of 4 defeat 4-way low-order interleaving?

    All multiples of 4 have address mod 4 equal to 0, so every access conflicts in bank 0.
  5. 5. What does interleaving mainly improve?

    Banks work in parallel, so more words per second flow, while one access still takes the same time.

Summary

  • Main memory is built from chips combined in width (more bits per word) and depth (more addresses).
  • Low address bits select a word inside a chip; high bits go through a decoder to select the chip group.
  • Interleaving divides memory into independent banks so several accesses overlap.
  • Low-order interleaving (address mod N) suits sequential access; high-order interleaving gives contiguous ranges per bank.
  • Bank conflicts from regular strides hurt; prime bank counts or hashed mappings reduce them.

Continue with Cache Memory Basics.