Memory Interfacing and Organization: short notes (Computer Organization & Architecture)

Introduction

Memory interfacing is the design of the connection between a processor and its main memory: how memory chips of a given size are combined into a memory of the required size and word width, how each address selects exactly one location, and how the memory is organised so that it can deliver words fast enough. The processor sees one linear array of addressable locations; underneath, that array is built from many identical chips, selected by decoders driven by the high-order address bits.

GATE asks for the number of chips and decoders needed, the address lines of each chip, the address range a chip answers, the effect of incomplete decoding, the byte order of a stored word, DRAM refresh overhead, and the speed-up that memory interleaving gives. The time cost of memory inside the hierarchy is the subject of Memory Hierarchy and Performance.

Prerequisites

Multiplexers, Decoders and Encoders: an $n$ -to- $2^n$ decoder activates exactly one output for each input combination; that output drives a chip-select line.

Core concepts

Memory chips

A chip described as $N \times w$ stores $N$ words of $w$ bits. It has:

Signal	Count	Purpose
Address lines	$\lg N$	Select one of the $N$ words
Data lines	$w$	Carry the word in or out
Chip select $\overline{CS}$ (or CE)	1	The chip responds only when selected
Read/write $R/\overline{W}$	1	Direction of the transfer

Technology	Cell	Properties
SRAM	Flip-flop (about 6 transistors)	Fast, no refresh, low density; used for caches
DRAM	One transistor and a capacitor	Dense and cheap, slower, the charge leaks so every row must be refreshed periodically; used for main memory
ROM, PROM, EPROM, EEPROM, flash	Fixed or electrically programmed	Non-volatile; holds firmware and boot code

DRAM addressing. A DRAM chip stores its cells in a square-ish array of rows and columns. To save pins, the row address and the column address share the same pins and are latched one after the other by the row-address strobe (RAS) and the column-address strobe (CAS). A chip with $2^{2m}$ addressable locations then needs only $m$ address pins.

Building a memory from chips

To build an $M \times W$ memory from $N \times w$ chips:

Width expansion (more bits per word): place $W/w$ chips side by side. They share every address line and the chip select; each supplies $w$ of the $W$ data bits.
Depth expansion (more words): stack $M/N$ rows of chips. The low $\lg N$ address bits go to every chip; the high $\lg(M/N)$ bits drive a decoder whose outputs select one row.
Number of chips $= \dfrac{M}{N} \times \dfrac{W}{w}$ . Decoder: $\lg(M/N)$ -to- $(M/N)$ .

Address decoding

Full decoding: every address bit above the chip's own address lines takes part in selecting the chip, so each memory word has exactly one address.
Partial (incomplete) decoding: some high-order bits are ignored. The chip then answers at $2^u$ different addresses, where $u$ is the number of ignored bits (aliases, foldback or mirror images). Cheaper decoders, wasted address space.

Byte order and alignment

In a byte-addressable memory, a multi-byte word occupies consecutive addresses.

Big-endian: the most significant byte is at the lowest address.
Little-endian: the least significant byte is at the lowest address.
Alignment: a $w$ -byte item is aligned if its address is a multiple of $w$ . Misaligned accesses may need two memory accesses or may be forbidden.

Interleaving

Main memory is often split into $m$ independent modules (banks), each with its own address and data registers, so that several accesses can be in progress at once.

Scheme	Module of address $a$	Address within module	Good for
High-order interleaving	the top $\lg m$ bits of $a$	the remaining bits	Expanding memory module by module; a sequential block within one module has no bank overlap; independent requests to different modules can overlap
Low-order interleaving	$a \bmod m$ (the low $\lg m$ bits)	$\lfloor a/m \rfloor$	Block transfers: consecutive words are in different modules, so their accesses overlap

With low-order interleaving, a block of consecutive words keeps all modules busy at once, which is why it cuts the cache miss penalty.

How it works

A 16K x 16 memory built from eight 4K x 8 chips with a 2-to-4 decoder — Figure 1. A 16K × 16 memory from eight 4K × 8 chips in four rows of two: A11 to A0 go to every chip, A13 and A12 drive a 2-to-4 decoder that selects one row, and the two chips of a row supply data bits D15 to D8 and D7 to D0.

High-order and low-order interleaving of 16 words over four modules — Figure 2. Sixteen words over four modules: with high-order interleaving module $m$ holds words $4m$ to $4m + 3$ ; with low-order interleaving module $m$ holds words $m$ , $m + 4$ , $m + 8$ and $m + 12$ .

Algorithms and pseudocode

Text

DESIGN-MEMORY(M, W, N, w)                  // target M x W, chips N x w
  rows   <- M / N                          // depth expansion
  cols   <- W / w                          // width expansion
  chips  <- rows * cols
  chipAddressBits <- lg N                  // A(lgN - 1) .. A0 to every chip
  decoderInputs   <- lg rows               // next address bits
  return (chips, rows, cols, decoderInputs)

SELECT(address)                            // full decoding
  row    <- floor(address / N)             // decoder output that goes active
  within <- address mod N                  // word inside every chip of that row
  return (row, within)

Every quantity is a power of 2 in practice, so the divisions are bit-field splits of the address.

Mathematical explanation

Address bits. A memory of $M$ addressable units needs $\lg M$ address bits. A chip of $N$ words uses $\lg N$ of them; the decoder uses $\lg(M/N)$ ; the two add up to $\lg M$ .

Chip address range (full decoding). Row $r$ answers addresses $rN$ to $rN + N - 1$ .

Aliases (partial decoding). If $u$ address bits are unused, each location appears at $2^u$ addresses.

DRAM refresh overhead. If a chip has $R$ rows, each row refresh takes $t_r$ , and every row must be refreshed once per period $T$ , then the fraction of time unavailable for normal accesses is $R\,t_r / T$ .

Interleaved block read. With $m$ low-order-interleaved modules, memory access latency $t_a$ before the bus transfer, with each bank remaining occupied until its subsequent $t_b$ transfer ends, and a bus that moves one word per $t_b$ , a block of $m$ consecutive words takes about $t_a + m\,t_b$ instead of $m\,(t_a + t_b)$ .

Worked examples

Example 1: chips and decoder (Figure 1)

Build a $16\text{K} \times 16$ memory ( $2^{14}$ words) from $4\text{K} \times 8$ chips.

Chips: $\frac{16K}{4K} \times \frac{16}{8} = 4 \times 2 = 8$ .
Address bits: 14 in total. A11 to A0 (12 bits) go to every chip; A13 and A12 drive a 2-to-4 decoder.
Address ranges (hexadecimal, word addresses): row 0 0000 to 0FFF, row 1 1000 to 1FFF, row 2 2000 to 2FFF, row 3 3000 to 3FFF.
Address 2ABC: A13 A12 $= 10$ , so row 2 is selected, word ABC inside both chips of that row.

Example 2: partial decoding

A $1\text{K} \times 8$ chip sits in a 16-bit address space. Its select logic checks only A15 $= 1$ and A14 $= 0$ ; A13 to A10 are ignored and A9 to A0 go to the chip. The chip responds to every address from 8000 to BFFF: $2^4 = 16$ aliases of each byte, for example 8000, 8400, 8800, ..., BC00 all reach byte 0. Adding A13 to A10 to the select logic (all four 0) would confine the chip to 8000 to 83FF.

Example 3: interleaving speed

Each module needs 80 ns per access, and the bus moves one word in 20 ns; a module stays busy until its word has been transferred. Read 8 consecutive words.

One module, or high-order interleaving when the 8 words lie inside the same module: $8 \times (80 + 20) = 800$ ns.
Four low-order-interleaved modules: words 0 to 3 are ready at 80 ns and leave at 100, 120, 140 and 160 ns; modules 0 to 3 then start words 4 to 7 at 100, 120, 140 and 160 ns, which leave at 200, 220, 240 and 260 ns. Total 260 ns, a speed-up of about 3.1.

Example 4: DRAM refresh

A DRAM has $2^{14} = 16384$ rows, each row must be refreshed every 64 ms, and one row refresh takes 50 ns. Refresh time per period: $16384 \times 50$ ns $= 819.2$ $\mu$ s, so $819.2\,\mu\text{s} / 64$ ms $= 1.28\%$ of the time is spent refreshing. Spreading the refreshes evenly means one row every $64\text{ ms}/16384 \approx 3.9\,\mu$ s.

Example 5: byte order

The 32-bit value 0x12345678 is stored at byte address 100.

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

Reading the byte at address 100 gives 0x12 on a big-endian machine and 0x78 on a little-endian one; reading the 16-bit half-word at 100 gives 0x1234 and 0x5678.

Example 6: DRAM pins

A $256\text{K} \times 4$ DRAM has $2^{18}$ locations, so 18 address bits. With row and column addresses multiplexed on the same pins (9 row bits, then 9 column bits), it needs only 9 address pins and 4 data pins.

Important properties and observations

Chips in one row share the address and select lines; chips in one column share the data lines.
The decoder uses the high-order bits in depth expansion; the low-order bits go to every chip.
Partial decoding saves logic but creates aliases; two devices whose aliases overlap would conflict.
Low-order interleaving helps sequential access; high-order interleaving can overlap independent requests to different modules, from one or more request sources, but not a sequential block wholly inside one module.
Endianness matters only for multi-byte items. A byte array looks the same on both.
DRAM refresh overhead is small but must be included when a question asks for the available bandwidth.
Common misconceptions.
- "Number of chips $= M/N$ ." Width expansion multiplies it by $W/w$ .
- "A 4K chip needs 4 address lines." It needs $\lg 4096 = 12$ .
- "Interleaving makes one access faster." Each access still takes the module's full access time; interleaving overlaps accesses.

GATE examination perspective

CHIP COUNT. $(M/N) \times (W/w)$ , after converting both to the same units.
DECODER SIZE. $\lg(\text{rows})$ -to-rows; for width expansion only, no decoder is needed.
ADDRESS RANGE. Fix the decoder bits for the chosen row; the chip bits run from all 0s to all 1s.
ALIASES. Count the address bits that neither the chip nor the decoder uses: $2^u$ copies.
INTERLEAVED TIMING. Draw the module timeline; low-order interleaving overlaps consecutive requests; high-order interleaving can overlap independent requests to different modules.
REFRESH. Rows times refresh time divided by the refresh period.
BYTE ORDER. Write the bytes out address by address before answering.

Summary

Multiplexers, Decoders and Encoders: prerequisite. Decoders drive chip selects.
Memory Hierarchy and Performance: related. Interleaving lowers the block miss penalty.
I/O Interface and Interrupts: related. Memory-mapped I/O places device registers in the same address space, decoded the same way.

Memory Interfacing and Organization

Introduction

Prerequisites

Core concepts

Memory chips

Building a memory from chips

Address decoding

Byte order and alignment

Interleaving

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: chips and decoder (Figure 1)

Example 2: partial decoding

Example 3: interleaving speed

Example 4: DRAM refresh

Example 5: byte order

Example 6: DRAM pins

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Memory chips

Building a memory from chips

Address decoding

Byte order and alignment

Interleaving

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: chips and decoder (Figure 1)

Example 2: partial decoding

Example 3: interleaving speed

Example 4: DRAM refresh

Example 5: byte order

Example 6: DRAM pins

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps