7.5Interleaving
The idea
Interleaving spreads consecutive addresses over several banks so they can be accessed in overlapping time.
Think of it like this: Four cashiers handling a long queue in rotation instead of one.
Why it exists
A single bank can start a new access only after the last finishes; many banks give more bandwidth.
How it works
- Low-order interleaving: bank = address mod M.
- Consecutive words are in different banks, so accesses overlap.
- High-order: contiguous region in one bank, no overlap.
- Speedup approaches M for sequential access.
Worked example: 4 banks, 8 sequential words, access time 2 cycles
Low-order: 9 cycles. All in one bank: 16 cycles.
Now play with it
- →Compare the two tabs; see that in low-order a new word starts every cycle.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| Bank 0 | w0 | w0 | w4 | w4 | |||||
| Bank 1 | w1 | w1 | w5 | w5 | |||||
| Bank 2 | w2 | w2 | w6 | w6 | |||||
| Bank 3 | w3 | w3 | w7 | w7 |
Word i is in bank i mod 4. One word is issued per cycle and four accesses overlap: 8 words in 9 cycles (access time 2 cycles).
Check yourself
With 4-way low-order interleaving, which bank holds word address 13?
Exam notes (the dense version)
Low-order: consecutive addresses in consecutive banks → sequential access overlaps (high bandwidth). High-order: bank by top bits → contiguous region per bank, no overlap.
Previous year questions: Memory Hierarchy & Main Memory (16)
PYQs are grouped by topic, so this is the full set for Memory Hierarchy & Main Memory; try the ones that match this subtopic. Open all 16 on the topic page.