Chapter 24 of 39

Main Memory Organization & Memory Chips

Suppose you are given a box of small memory chips, each holding only 1 KB, and asked to build 4 KB of memory for a processor. How do you wire them so the processor sees one smooth memory with addresses 0 to 4095? Which chip should answer when the CPU asks for address 2500? And what if each chip gives you 4 bits but the CPU wants 8 at a time?

These are the questions of main memory organization. In RAM & ROM: SRAM, DRAM & Types of ROM we looked inside a single memory cell. Now we zoom out: how cells are arranged inside a chip, how chips are combined into a full memory, how the CPU's address is split to select the right chip, and how memory is interleaved to make it faster. These are some of the most calculation-heavy topics in exams, and every number in this chapter has been checked with a script.

Main memory organization describes how memory cells are arranged into addressable words inside a chip, and how several chips are connected to the address, data and control lines to form a memory of the required capacity and word length.


Memory Chip Notation

A memory chip is described as m × n (read "m by n"):

  • m = number of locations (words) in the chip

  • n = number of bits in each location (word length)

For example, a 1K × 8 chip has 1024 locations of 8 bits each, so it stores 8192 bits = 1 KB. From this notation you can read off the pins it needs:

Address lines = log2(m)        (to choose one of m locations)
Data lines    = n              (one per bit of a location)
ChipLocationsAddress linesData linesCapacity
128 × 8128 = 2778128 B
1K × 41024 = 210104512 B
64K × 1665536 = 2161616128 KB
256M × 8228288256 MB

Apart from address and data pins, a typical chip also has:

  • CS (chip select) or CE (chip enable): the chip responds only when this is active. When it is inactive, the chip's data pins go into a high-impedance state, so several chips can share the same data bus.

  • R/W (read/write) (or separate WE, write enable, and OE, output enable): chooses between read and write.

  • VCC and GND: power.

Example: a 64K × 16 SRAM chip with one CS pin, one R/W pin, one VCC and one GND needs 16 + 16 + 1 + 1 + 2 = 36 pins.


Byte-Addressable vs Word-Addressable Memory

The number of address bits the CPU needs depends on what one address points to.

  • Byte-addressable: each address names one byte. This is what almost all modern computers use. A 32-bit word occupies four consecutive addresses.

  • Word-addressable: each address names a whole word.

Example: a memory of 4 MB with 32-bit (4-byte) words.

Byte-addressable: 4 MB = 2^22 bytes          -> 22 address bits
Word-addressable: 2^22 / 4 = 2^20 words      -> 20 address bits

Byte Ordering (Endianness)

When a multi-byte word is stored at byte address A, which byte goes into address A?

  • Big-endian: the most significant byte goes at the lowest address ("big end first"). Used by many network protocols (network byte order), older Motorola 68000, IBM mainframes.

  • Little-endian: the least significant byte goes at the lowest address. Used by x86 and, in practice, by most ARM and RISC-V systems.

Store 0x12345678 at address 100:

Address        100   101   102   103
Big-endian     12    34    56    78
Little-endian  78    56    34    12

You can check your own machine with C:

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    uint32_t word = 0x12345678;
    unsigned char *p = (unsigned char *)&word;   /* look at it byte by byte */

    printf("word = 0x%08X\n", (unsigned)word);
    for (int i = 0; i < 4; i++)
        printf("byte at address base+%d : 0x%02X\n", i, p[i]);

    printf("This machine is %s-endian\n", (p[0] == 0x78) ? "little" : "big");
    return 0;
}

Output on an x86-64 PC (GCC on Linux):

word = 0x12345678
byte at address base+0 : 0x78
byte at address base+1 : 0x56
byte at address base+2 : 0x34
byte at address base+3 : 0x12
This machine is little-endian

Inside a Chip: 2D and 2.5D Organization

A chip with 2k locations must turn a k-bit address into the selection of one location. There are two classic ways.

2D (Linear) Organization

All locations are rows of one array. One big k-to-2k decoder drives one word line per location, and each word's n bits are read out in parallel.

               +--------------------------+
  k address    |  k-to-2^k  | word 0      |
  bits   ----> |  decoder   | word 1      |
               |            | ...         |
               |            | word 2^k-1  |
               +--------------------------+
                              | n data bits

Simple, but for a large chip the decoder becomes enormous (a 1M × 1 chip would need 220 = 1,048,576 decoder outputs) and the array would be extremely tall and thin.

2.5D Organization (Row and Column Decoding)

The cells are arranged as a roughly square array. The address is split into a row address and a column address. A row decoder selects a whole row; a column decoder (a multiplexer) picks the required bits out of that row.

  1M x 1 chip as a 1024 x 1024 array of cells

  address bits A19..A10  --->  row decoder (10-to-1024)  ---> selects 1 row
  address bits A9..A0    --->  column decoder/MUX (1024-to-1) ---> selects 1 bit

Now we need only 1024 + 1024 = 2048 decoder outputs instead of 1,048,576, and the square shape keeps wires short. This row/column structure is exactly what DRAM uses: the row is activated into the row buffer, then the column picks the bits (see the DRAM access steps in the previous chapter).

DRAM Address Multiplexing

Because a DRAM receives the row address and the column address at different times, both can be sent on the same pins, one after the other, with the RAS and CAS signals telling the chip which one is on the pins.

Example: a 64M × 8 DRAM chip needs log2(64M) = 26 address bits. With a square split into 13 row bits and 13 column bits, it needs only 13 address pins. (Real chips also have bank address pins and do not always split evenly, but the principle is the same.) SRAM chips do not multiplex their address pins, because they want the whole address at once for speed.


Building a Larger Memory from Small Chips

Suppose the required memory is M × W and the chips available are m × w.

Number of chips = (M x W) / (m x w)
                = (M / m) rows  x  (W / w) chips per row
  • W / w chips side by side make one full-width "row" (or bank). This increases the word length.

  • M / m such rows increase the number of words. A decoder chooses which row responds.

1. Width (Bit) Expansion

Build 1K × 8 from 1K × 4 chips. We need 8 / 4 = 2 chips, both receiving the same 10 address lines and the same CS. One chip supplies data bits D7–D4 and the other D3–D0.

   A9..A0 ----+---------------+
              |               |
          +---v----+      +---v----+
   CS --->| 1K x 4 |  +-->| 1K x 4 |
      |   | chip 1 |  |   | chip 2 |
      |   +---+----+  |   +---+----+
      +---------------+       |
              |               |
              v               v
           D7..D4          D3..D0

No decoder is needed: both chips are always selected together.

2. Depth (Word) Expansion

Build 4K × 8 from 1K × 8 chips. We need 4K / 1K = 4 chips. 4K locations need 12 address lines (A11–A0).

  • The low 10 lines (A9–A0) go to every chip to select a location inside it.

  • The high 2 lines (A11, A10) go to a 2-to-4 decoder whose outputs drive the CS of the four chips.

  • All chips share the same 8 data lines; only the selected one drives them.

                  +------------+
   A11, A10 ----->| 2-to-4     |--0--> CS chip 0  (addresses    0 - 1023)
                  | decoder    |--1--> CS chip 1  (addresses 1024 - 2047)
                  |            |--2--> CS chip 2  (addresses 2048 - 3071)
                  |            |--3--> CS chip 3  (addresses 3072 - 4095)
                  +------------+
   A9..A0  ------> all four chips
   D7..D0  <-----> all four chips (shared data bus)

So for address 2500: 2500 = 1001 1100 0100 in binary. A11 A10 = 10 selects chip 2, and A9–A0 = 01 1100 0100 = 452 is the location inside it. Check: 2048 + 452 = 2500.

3. Both Together: Worked Example

A 2048 × 16 memory is to be built from 128 × 8 chips. Find (a) the number of chips, (b) the address lines needed, (c) how many go to each chip, and (d) the decoder size.

(a) Chips = (2048 x 16) / (128 x 8) = 32
          = (2048/128) rows x (16/8) per row = 16 rows x 2 chips

(b) 2048 words = 2^11  -> 11 address lines (A10..A0)

(c) 128 locations per chip = 2^7 -> 7 lines (A6..A0) go to every chip

(d) Remaining 11 - 7 = 4 lines (A10..A7) choose one of 16 rows
    -> a 4-to-16 decoder; each output drives the CS of the 2 chips in that row

A quick sanity check: 16 rows × 128 words = 2048 words, and 2 chips × 8 bits = 16 bits. Both match.


Memory Address Map

A real system usually has both RAM and ROM in the same address space. The designer draws an address map: a table showing which addresses belong to which chip, and which address bits are used to decode them.

Worked Example

A CPU has a 12-bit address bus (A11–A0) and an 8-bit data bus. Connect 1 KB of RAM made from four 256 × 8 chips at the bottom of memory, and one 1K × 8 ROM starting at address 800 (hex).

Each RAM chip needs 8 address lines (A7–A0); the ROM needs 10 (A9–A0). We choose:

  • RAM selected when A11 = 0 and A10 = 0; then A9 A8 pick one of the four RAM chips through a 2-to-4 decoder.

  • ROM selected when A11 = 1 and A10 = 0.

ChipHex address rangeA11 A10 A9 A8A7–A0
RAM 1000 – 0FF0 0 0 0x x x x x x x x
RAM 2100 – 1FF0 0 0 1x x x x x x x x
RAM 3200 – 2FF0 0 1 0x x x x x x x x
RAM 4300 – 3FF0 0 1 1x x x x x x x x
ROM800 – BFF1 0 x xx x x x x x x x

Here x means "this bit goes to the chip itself and can be 0 or 1". The resulting selection logic is:

RAM enable  = (NOT A11) AND (NOT A10)   -> enables the 2-to-4 decoder driven by A9, A8
ROM CS      = A11 AND (NOT A10)
Unused      = addresses 400-7FF and C00-FFF (A10 = 1): no chip responds

We checked this map by decoding all 4096 addresses with a script: exactly 0x000–0x3FF go to RAM 1–4 (256 each) and 0x800–0xBFF go to the ROM.

Full vs Partial Decoding

The example uses full decoding: every address bit not going to a chip is checked, so each location has exactly one address. If the designer saved logic by ignoring A10 (partial decoding), RAM would also answer at 400–7FF and ROM at C00–FFF. These duplicate addresses are called aliases (or fold-back). Partial decoding is cheaper but wastes address space.


Memory Interleaving

A single memory module can serve only one access at a time, and a DRAM access takes many CPU cycles. If memory is split into several independent modules (banks) that can work in parallel, several words can be in progress at once. How addresses are spread across the modules decides whether this parallelism is useful.

With 2a modules, a bits of the address select the module and the rest select the word inside it.

High-Order Interleaving

The most significant a bits choose the module. Each module holds a contiguous chunk of addresses.

Low-Order Interleaving

The least significant a bits choose the module. Consecutive addresses go to consecutive modules.

Example: 16 words, 4 modules (2 module bits, 2 word bits).

High-order:  address = [ module (2 bits) | word (2 bits) ]
  Module 0: 0  1  2  3
  Module 1: 4  5  6  7
  Module 2: 8  9 10 11
  Module 3: 12 13 14 15

Low-order:   address = [ word (2 bits) | module (2 bits) ]
  Module 0: 0  4  8 12
  Module 1: 1  5  9 13
  Module 2: 2  6 10 14
  Module 3: 3  7 11 15

Address 13 = 1101: with high-order interleaving it is in module 11 = 3, word 01 = 1; with low-order interleaving it is in module 01 = 1, word 11 = 3.

Since programs and cache blocks access consecutive addresses, low-order interleaving puts consecutive words in different modules, which can all work at the same time. High-order interleaving puts them all in the same module, so they are served one by one; its advantages are easy expansion (add a module to add a chunk of addresses) and fault isolation.

Worked Example: Fetching a Cache Block

A cache block of 8 words is read from memory. Sending an address to memory takes 1 cycle, a module needs 8 cycles to access a word, and sending one word over the bus takes 1 cycle. Compare a single (non-interleaved) module with 8-way low-order interleaving.

Non-interleaved: each word is a separate access
  per word = 1 (address) + 8 (access) + 1 (transfer) = 10 cycles
  8 words  = 8 x 10 = 80 cycles

8-way low-order interleaved: the 8 words are in 8 different modules
  1 cycle  : send the block address to all modules
  8 cycles : all modules access their word in parallel
  8 cycles : the 8 words are transferred one per cycle
  total    = 1 + 8 + 8 = 17 cycles

Interleaving makes the block transfer about 4.7 times faster (80 / 17). This reduces the cache miss penalty, a topic continued in Cache Performance & Multi-level Caches.

FeatureHigh-order interleavingLow-order interleaving
Module selected byMost significant bitsLeast significant bits
Consecutive addressesSame moduleDifferent modules
Parallel access to a blockNoYes
Main benefitEasy expansion, a faulty module affects only one address range, different processes can use different modulesHigher bandwidth for sequential access (cache block fills)

Common Mistakes

  • Counting chips by capacity but forgetting the shape. (M × W)/(m × w) gives the total, but you also need rows = M/m and chips per row = W/w to wire them.

  • Sending all address lines to every chip. Only log2(m) lines go to each chip; the remaining high-order lines feed the decoder.

  • Using a decoder for width expansion. Chips placed side by side to widen the word share the same CS.

  • Mixing byte and word addresses. 4 MB of byte-addressable memory needs 22 bits; the same memory word-addressed with 4-byte words needs 20.

  • Forgetting multiplexing for DRAM pin counts. A DRAM with 2k address bits split evenly has k address pins.

  • Swapping high-order and low-order interleaving. Low-order = low bits pick the module = consecutive words in different modules.

  • Getting endianness backwards. Little-endian puts the little (least significant) end at the lowest address.


GATE / Interview Questions

How many address and data lines does a 32K × 8 memory chip have?

32K = 215, so 15 address lines and 8 data lines.

How many 256 × 4 chips are needed for a 4K × 16 memory, and what decoder is required?

(4096 × 16)/(256 × 4) = 64 chips, arranged as 16 rows × 4 chips. Memory needs 12 address lines; 8 go to each chip and 4 go to a 4-to-16 decoder selecting a row.

A 1M × 1 chip uses 2.5D organization with a square array. What decoders does it need?

A 1024 × 1024 array: a 10-to-1024 row decoder and a 1024-to-1 column multiplexer (10 address bits each), i.e. 2048 decoder outputs instead of 220 for a 2D organization.

How many address pins does a 16M × 4 DRAM chip with equal row/column multiplexing need?

16M = 224, so 24 address bits, split 12 + 12, sent on 12 pins.

In a 4-module memory with low-order interleaving, which module holds byte address 27 (word = byte here)?

Module = 27 mod 4 = 3, word 27 div 4 = 6 inside it. With high-order interleaving over 32 addresses (8 per module), it would be module 27 div 8 = 3, word 3.

How is 0xAABBCCDD stored at address 200 on a little-endian machine?

200: DD, 201: CC, 202: BB, 203: AA. (Big-endian would store AA, BB, CC, DD.)

Why does low-order interleaving reduce cache miss penalty?

A cache block consists of consecutive words, which low-order interleaving places in different modules. All modules access their words in parallel, so the block takes roughly one access time plus one transfer per word, instead of one full access per word.

What is address aliasing in partial decoding?

When some address bits are ignored by the decoding logic, the same physical location responds to more than one address. It saves decoding hardware but wastes address space and can cause confusing bugs.


Summary

  • An m × n chip has m locations of n bits: log2(m) address lines and n data lines, plus CS, R/W and power.

  • Address bits depend on the addressable unit: byte-addressable 4 MB needs 22 bits. Endianness decides byte order inside a word; x86 is little-endian.

  • Inside a chip, 2D organization uses one huge decoder; 2.5D uses row and column decoders on a square array. DRAM multiplexes row and column addresses on the same pins.

  • To build M × W from m × w chips: (M/m) rows × (W/w) chips per row. Low log2(m) address lines go to every chip; the rest go to a decoder that drives CS. Example: 2048 × 16 from 128 × 8 = 32 chips, 4-to-16 decoder.

  • An address map lists each chip's address range and decoding bits. Full decoding gives unique addresses; partial decoding creates aliases.

  • Interleaving: high-order (top bits pick the module) vs low-order (bottom bits pick the module). Low-order lets consecutive words be fetched in parallel: 17 cycles instead of 80 for an 8-word block in our example.

Even well-organized DRAM is far slower than the CPU. The next chapter, Cache Memory, shows how a small SRAM memory between them hides most of that delay.