Memory Organization

Introduction

How can a computer execute billions of instructions per second, maintain terabytes of data, and switch seamlessly between dozens of applications—all without costing a fortune or running out of storage space? The secret lies in memory organization, an architectural masterpiece that blends high-speed physical components with ingenious software abstractions.

In this lesson, we will explore the complete landscape of computer memory systems as outlined in classic computer architecture:

• Analyze the structural and economic trade-offs across the memory hierarchy.
• Differentiate between SRAM, DRAM, ROM, and auxiliary storage devices like disks and tapes.
• Evaluate fast-access searching techniques using Associative Memory (CAM).
• Compare cache mapping procedures, write policies, and virtual memory address translations.
• Examine Memory Management Hardware (MMU), segmented-page mapping, and memory protection mechanism.

Memory Hierarchy

The memory unit is an essential component in any digital computer, serving as the central storage hub for programs and data. While a tiny single-purpose microcontroller might survive on a modest block of onboard memory, general-purpose computers demand vastly more capacity than a single memory device can supply. Most computer users accumulate massive software applications and large datasets—far more than can fit inside a computer's high-speed primary memory at one time.

Fortunately, a processor doesn't need access to all stored information simultaneously. It is far more economical to construct a memory hierarchy using devices of varying speeds, capacities, and costs:

• Cache Memory: A small, extremely fast memory built right near the CPU logic to store instructions and temporary data currently being executed. Its access time closely matches the processor's clock cycle.
• Main Memory: The central memory unit that communicates directly with the CPU and through an Input/Output (I/O) processor. It contains only the active programs and data needed right now.
• Auxiliary Memory: High-capacity, low-cost backup storage devices—primarily magnetic disks and magnetic tapes—used for storing long-term files, system software, and inactive programs.

Economic and Performance Dynamics

Why not build the entire computer out of super-fast cache memory? The answer boils down to economics and physics. As storage capacity increases, the cost per bit decreases, but access time becomes longer. Cache memory is very fast but small and expensive per bit; auxiliary memory is vast and inexpensive per bit but remarkably slow.

Multiprogramming and Memory Management

In modern operating systems, multiprogramming enables the CPU to execute multiple independent programs concurrently. When one running program requests an I/O transfer from auxiliary memory, the CPU delegates that transfer to an I/O processor and immediately switches execution to another program sitting ready in main memory. The subsystem that supervises this seamless flow of active and inactive information between auxiliary memory and main memory is called the memory management system.

Main Memory

Main memory acts as the primary workbench for the CPU during active operation. It is predominantly constructed from semiconductor integrated circuit chips, divided into two key functional families: RAM (Random-Access Memory) and ROM (Read-Only Memory).

RAM Technologies: Static vs. Dynamic

In modern terminology, RAM refers specifically to read/write memory. It comes in two primary internal operating modes:

• Static RAM (SRAM): Consists internally of logic flip-flops that store binary state. Information remains valid as long as electrical power is applied. SRAM features shorter read/write cycles and easier interfacing, making it the premier choice for implementing cache memory.
• Dynamic RAM (DRAM): Stores binary information as electric charges on micro-capacitors inside MOS transistors. Because capacitors naturally discharge over time, DRAM requires periodic refreshing (cycling through memory words every few milliseconds). Despite this complexity, DRAM offers significantly reduced power consumption and vastly higher storage density per chip, making it ideal for main memory (e.g., SDRAM, multibank DRAM).

ROM and the Computer Startup Sequence

While RAM holds volatile user programs that disappear when power is cut, ROM stores permanent system routines. Crucially, ROM holds the bootstrap loader—the initial startup program executed when the computer is powered on.

When power is applied, hardware automatically initializes the Program Counter (PC) to the first address of the bootstrap loader in ROM. This routine reads a portion of the operating system from disk into RAM and transfers execution control to it.

Chip Structure and Control Signals

To allow multiple chips to share common system address and data buses, RAM and ROM chips utilize three-state buffers. Outputs can exist in logic 1, logic 0, or a high-impedance state (which behaves like an open circuit, disconnecting the output from the bus).

A typical $128 \times 8$ RAM chip requires:

1. 7 address lines ($2^7 = 128$ bytes).
2. 8-bit bidirectional data bus.
3. Read ($RD$) and Write ($WR$) control inputs.
4. Chip Select inputs ($CS1$ and $\overline{CS2}$): The chip is active only when $CS1 = 1$ and $\overline{CS2} = 0$. Otherwise, the data bus is placed in high-impedance mode.

In contrast, a same-sized physical footprint for a $512 \times 8$ ROM chip provides four times the capacity because internal ROM cells take less physical space than RAM flip-flops or charge circuits. ROM requires 9 address lines and operates in output-only mode during reads.

Memory Address Map Example

To assign memory addresses across multiple chips, engineers create a memory address map. Suppose a system requires 512 bytes of RAM (built with four $128 \times 8$ chips) and 512 bytes of ROM (built with one $512 \times 8$ chip):

• Address lines 1 to 7 select specific bytes inside the RAM chips.
• Address lines 1 to 9 select specific bytes inside the ROM chip.
• Address lines 8 and 9 connect to a $2 \times 4$ decoder to select among the four RAM chips.
• Address line 10 selects between RAM ($0$) and ROM ($1$).

Hexadecimal Range  | Line 10 | Lines 9-8 | Lines 7-1 | Component
-------------------|---------|-----------|-----------|-----------
0000 - 007F        |    0    |    0 0    |  xxxxxxx  | RAM 1
0080 - 00FF        |    0    |    0 1    |  xxxxxxx  | RAM 2
0100 - 017F        |    0    |    1 0    |  xxxxxxx  | RAM 3
0180 - 01FF        |    0    |    1 1    |  xxxxxxx  | RAM 4
0200 - 03FF        |    1    |    x x    | xxxxxxxxx | ROM

Auxiliary Memory

Auxiliary storage provides long-term, non-volatile memory capable of holding large program files and bulk datasets. The two dominant electromechanical auxiliary storage media are magnetic disks and magnetic tapes.

Key Performance Parameters

Regardless of physical design, auxiliary devices are evaluated using key logical characteristics:

• Access Time: The average time needed to reach a memory location and retrieve its content. For moving mechanical parts, access time consists of seek time (positioning the head over the desired track) plus transfer time (time taken to read data).
• Transfer Rate: The speed at which characters or words are transmitted per second after positioning is complete.

Magnetic Disks

A magnetic disk is a circular metal or plastic plate coated with magnetic material. Both sides of the disk are frequently coated, and multiple disks can be stacked on a single rotating spindle. Bits are recorded as microscopic magnetized spots along concentric circular tracks, which are subdivided into sectors.

• Hard Disks: Permanently mounted assemblies providing high density, fast rotation speeds, and massive storage capacity.
• Floppy Disks: Removable, flexible plastic disks enclosed in protective jackets (e.g., 3.5-inch formats historically used for software distribution).
• Constant Recording Density: Because outer tracks near the circumference are longer than inner tracks near the center, some systems equalize sector capacity by utilizing higher recording density on inner tracks.

Magnetic Tape

A magnetic tape system moves a plastic ribbon coated with magnetic material past stationary read/write heads. Typically, 7 or 9 bits (including a parity bit) are recorded simultaneously across the width of the tape to represent a character.

Because tape cannot stop or start instantaneously between individual characters, data is organized into blocks or records. Unrecorded areas called inter-record gaps are placed between records to allow the tape to accelerate to full constant speed before reaching data.

Associative Memory

In traditional RAM, finding a specific item requires searching sequentially or using complex search software algorithms. Associative Memory, also known as Content Addressable Memory (CAM), dramatically reduces search times by accessing stored items directly by their data content rather than by physical address.

Hardware Architecture

An associative memory consists of a memory array of $m$ words ($n$ bits per word) paired with three specialized hardware registers:

1. Argument Register ($A$): Holds the bit pattern being searched for.
2. Key Register ($K$): Serves as a bitmask to specify which fields in the argument register should be compared ($1 = \text{compare}$, $0 = \text{ignore}$).
3. Match Register ($M$): Contains $m$ individual match bits (one per word in memory). A word that matches all unmasked bits sets its corresponding $M_i$ bit to 1.

Argument (A):  1 0 1  1 1 1 1 0 0
Key (K):       1 1 1  0 0 0 0 0 0  (Mask: compare only 3 leftmost bits)
--------------------------------------------------------------------
Word 1:        1 0 0  1 1 1 1 0 0  --> No Match  (M1 = 0)
Word 2:        1 0 1  0 0 0 0 0 1  --> MATCH!    (M2 = 1)

Cell Logic and Boolean Equations

Each internal cell $C_{ij}$ contains a storage flip-flop $F_{ij}$ and comparison logic. First, two bits $A_j$ and $F_{ij}$ are equal if both are 1 or both are 0:

$$x_j = A_j F_{ij} + A_j' F_{ij}'$$

To account for the mask bit $K_j$, we OR the expression with $K_j'$ so that when $K_j = 0$, the term forces a logic 1 (no match penalty):

$$\text{Term}_j = x_j + K_j' = A_j F_{ij} + A_j' F_{ij}' + K_j'$$

For a full word $i$ to match, all $n$ bits must produce a logic 1 through an $n$-input AND gate:

$$M_i = \prod_{j=1}^{n} \left( A_j F_{ij} + A_j' F_{ij}' + K_j' \right)$$

Reading and Writing in CAM

To write data, CAM searches a tag register (which tracks active vs. inactive locations) to locate the first empty slot. During read operations, if multiple words match simultaneously, the system scans through the match register bits sequentially to read matched items one by one.

Cache Memory

Analysis of computer program execution reveals a fundamental property known as locality of reference: over short time intervals, memory references tend to be confined to localized address regions (e.g., program loops, subroutine calls, iterative counters, and array processing).

By placing a small, high-speed cache memory between the CPU and main memory, frequently accessed instructions and data can be delivered at near-processor speeds. Cache performance is measured by the hit ratio:

$$\text{Hit Ratio} = \frac{\text{Number of Hits}}{\text{Total Memory References (Hits + Misses)}}$$

Real-world hit ratios frequently exceed $0.90$, dropping average memory access time dramatically (e.g., reducing access time from $1000\text{ ns}$ down to $200\text{ ns}$ when cache access is $100\text{ ns}$).

Mapping Procedures

When the CPU requests a word, the virtual or physical address must be translated to check if the word is currently in cache. Three mapping techniques are widely used:

1. Associative Mapping: Stores both the full memory address and data together inside associative cache memory. Any word from main memory can reside in any cache location. It is extremely flexible but requires expensive hardware registers.
2. Direct Mapping: Divides a memory address into a Tag field and an Index field. The length of the Index field equals the address length of the cache memory ($2^k$ words in cache $\rightarrow k$ index bits). When accessing memory, the index bits pick the cache line, and the stored tag is compared against the CPU address tag.
   • Block Size > 1 Word: The index field is further divided into a Block field and a Word field so multi-word blocks transfer from main memory on a miss.
3. Set-Associative Mapping: Combines direct and associative mapping. Each cache index points to a set containing $k$ tag-data pairs (e.g., a 2-way set associative cache stores two data words per index). This eliminates collision misses when two active memory locations share the same index address.

Replacement Algorithms

When a cache set is full and a miss occurs, a block must be evicted. Common replacement policies include:

• First-In, First-Out (FIFO): Replaces the item that has resided in the set the longest.
• Least Recently Used (LRU): Replaces the item that has gone unreferenced for the longest time.
• Random: Selects a target item randomly.

Cache Write Strategies & Initialization

• Write-Through: Updates main memory simultaneously with every cache write. Guarantees main memory always contains valid data, which is critical for DMA I/O operations.
• Write-Back: Updates only the cache entry during a write and sets a dirty flag. Main memory is updated only when the block is evicted from cache.
• Cache Initialization: At boot, all lines are cleared by setting a Valid Bit to 0. The valid bit transitions to 1 only when valid blocks are fetched from main memory.

Virtual Memory

Virtual Memory gives programmers the illusion that the system possesses a vast main memory space equal to the full capacity of auxiliary memory. Hardware and software dynamically translate program-generated addresses into actual physical main memory locations while programs run.

Address Space vs. Memory Space

• Virtual Address (Address Space $N$): An address generated by software programs.
• Physical Address (Memory Space $M$): An actual location inside main memory.

For example, if auxiliary storage holds $1024\text{K} = 2^{20}$ words and main memory holds $32\text{K} = 2^{15}$ words, the virtual address requires 20 bits while the physical memory address requires only 15 bits.

Address Mapping using Pages and Blocks

To simplify mapping, address space is divided into equal fixed-sized chunks called pages, and physical memory space is divided into equal chunks called blocks (or page frames):

$$\text{Virtual Address} = [\text{Page Number}] + [\text{Line / Word Offset}]$$

Because page size equals block size, the lower-order line bits pass directly through unchanged. Only the page number must be translated into a block number.

Page Tables & Associative Page Translation

In a standard Memory Page Table, the page number serves as an index address into a RAM table. The table entry yields the assigned block number along with a Presence Bit (1 = in RAM, 0 = on disk).

However, a RAM page table for $1024$ pages where main memory holds only $32$ blocks wastes $992$ unused entries! To eliminate this inefficiency, systems use an Associative Memory Page Table, which stores only active mappings (page number paired with block number).

Page Faults and Replacement

If the CPU references a virtual address whose presence bit is 0, a page fault occurs:

1. Execution of the current program is suspended.
2. An interrupt alerts the operating system to initiate an I/O fetch from auxiliary disk storage.
3. The CPU switches to execute another task while the I/O processor transfers the page into RAM.
4. If main memory is full, the operating system uses FIFO or LRU (tracked via aging registers) to select a resident page for eviction.

Memory Management Hardware

In multiprogramming environments, a dedicated Memory Management Unit (MMU) provides three essential services:

1. Dynamic storage relocation mapping logical memory references to physical memory addresses.
2. Sharing common programs (e.g., shared library compilers) across multiple users.
3. Protecting system programs and user data from unauthorized access or corruption.

Segmented-Page Mapping

Fixed page sizes don't always match software structures. Modern systems divide programs into variable-length logical units called segments (e.g., subroutines, symbol tables, arrays).

To combine the flexibility of segmentation with the ease of fixed page management, systems partition logical addresses into three distinct fields:

$$\text{Logical Address} = [\text{Segment Number}] + [\text{Page Number}] + [\text{Word Offset}]$$

Address translation follows a two-tier lookup process:

1. The Segment Number indexes into a Segment Table to retrieve a pointer address for the corresponding Page Table base.
2. The Page Table Base is added to the Page Number to index into the Page Table, yielding the physical Block Number.
3. Concatenating the Block Number with the Word Offset produces the final physical memory address.

Accelerating Translation with the TLB

Performing two sequential table lookups for every memory reference would slow the system to one-third speed. To solve this, MMUs incorporate a fast associative cache called a Translation Lookaside Buffer (TLB).

The TLB keeps the most recently used mapping entries (Segment + Page $\rightarrow$ Block). If an associative search matches the TLB, the physical address is formed instantly, bypassing the two-level lookup process.

[Logical Address: Segment | Page | Word]
          |
          +---> [ Search TLB Associative Cache ]
                      |                       |
                 (TLB Hit)               (TLB Miss)
                      |                       |
                      v                       v
            [Extract Block No.]   [Segment Table -> Page Table]
                      |                       |
                      +-----------+-----------+
                                  |
                                  v
                [Physical Address: Block | Word]

Memory Protection and Descriptors

Protection parameters are integrated into segment entries called Descriptors. A segment descriptor contains:

• Base Address: Pointer to the page table or memory block.
• Length Field: The maximum number of pages assigned to the segment. If a program attempts an offset exceeding this boundary, a size violation error occurs.
• Protection Field: Defines access rights for the segment:
  1. Full Read and Write: Standard user workspace.
  2. Read Only (Write Protection): Shared utility functions and routines.
  3. Execute Only (Program Protection): Prevents copying executable source code.
  4. System Only (OS Protection): Restricts critical kernel code to operating system mode.

Summary

Computer memory systems bridge the divide between high-speed CPU execution logic and vast, low-cost long-term storage. By structuring memory into a dynamic hierarchy—utilizing cache memory, main memory (RAM/ROM), content-addressable memory (CAM), virtual memory paging, and hardware MMU protection—modern computer architectures achieve high average processing speeds while maximizing capacity and ensuring multi-user security.

Key Takeaways

• Memory Hierarchy Trade-offs: Strives for the highest average access speed at the lowest overall cost by layering cache (SRAM), main memory (DRAM), and auxiliary storage (disks/tapes).
• RAM vs ROM: SRAM uses flip-flops for fast cache; DRAM uses capacitors needing refresh for dense main memory; ROM holds permanent bootstrap startup code.
• Associative Memory (CAM): Matches stored data by content rather than physical address using mask registers and parallel match logic.
• Cache Mapping Strategies: Employs Associative, Direct, or Set-Associative mapping alongside Write-Through or Write-Back policies to capitalize on locality of reference.
• Virtual Memory & MMU: Translates logical/virtual addresses to physical memory using pages, blocks, page tables, TLB acceleration, and descriptor-based access protection.