Skip to main content

3.2 Associative Memory

While conventional memory requires the CPU to supply a specific physical address to retrieve data, Content Addressable Memory (CAM) — or Associative Memory — allows the CPU to search the entire array simultaneously by content. This chapter explores the hardware block structure of CAM, the internal circuitry of a CAM cell, and the complete Boolean derivation of Match Logic.

Learning Objectives

  • Define the terminology of Associative Memory (CAM, Argument Register, Key Register, Match Register).
  • Explain how the key register (mask) isolates specific bit columns in the argument register during search operations.
  • Compute individual bit match values ($x_j$) and overall word match outputs ($M_i$) for a given data grid and key mask.
  • Derive the Boolean logic equation for the match register output bit ($M_i$) of a specified word length $N$.
  • Compare associative memory structures with standard RAM structures in terms of search speed, cell gate count, and cost.
Prerequisites

Before studying this chapter, you should review Chapter 3.1: Memory Decoding to understand how physical addresses are partitioned.

1. Concept of Content Addressable Memory (CAM)

In traditional RAM, search operations are slow: the CPU must read memory locations sequentially to find a specific data pattern. **Content Addressable Memory (CAM)** resolves this by search-matching the entire memory array in parallel within a single clock cycle. This logic is crucial for high-speed hardware tables, such as Translation Lookaside Buffers (TLBs) and network router address directories.

2. Hardware Block Organization

An associative memory unit consists of a memory array of $M$ words with $N$ bits per word, managed by three registers:

  1. **Argument Register ($A$)**: Holds the search operand to be matched.
  2. **Key Register ($K$)**: A bit mask that selects which columns are active in the comparison. If $K_j = 1$, bit $j$ of the argument register is compared. If $K_j = 0$, that column is ignored.
  3. **Match Register ($M$)**: Contains $M$ bits, one for each word in the array. If word $i$ matches the masked argument, flag $M_i = 1$; otherwise, $M_i = 0$.
[Figure 3.2.1: Associative Memory Architecture] 
  Argument Register (A) ──► [ A1 ] [ A2 ] [ A3 ] [ A4 ]
                             │      │      │      │
  Key Register (K)      ──► [ K1 ] [ K2 ] [ K3 ] [ K4 ]
                             │      │      │      │
  Associative Array     ──► ┌──────┬──────┬──────┬──────┐
  (M words x N bits)        │ W0,1 │ W0,2 │ W0,3 │ W0,4 │ ──► Match M0
                            ├──────┼──────┼──────┼──────┤
                            │ W1,1 │ W1,2 │ W1,3 │ W1,4 │ ──► Match M1
                            └──────┴──────┴──────┴──────┘
Figure 3.2.1: Structural block diagram mapping the interaction of Argument, Key, and Match registers in CAM.

3. Logic Circuit of an Associative Memory Cell

To allow parallel matching, every bit cell in the associative array contains its own storage flip-flop plus comparison logic gates.

Let $B_{ij}$ represent the stored bit in cell $j$ of word $i$. The cell comparison output is: $$x_j = A_j B_{ij} + \bar{A}_j \bar{B}_{ij}$$ This Boolean equation is the equivalence (XNOR) logic, verifying if the argument bit matches the stored bit.

4. Derivation of Match Logic Equations

For a word $i$ to generate a match ($M_i = 1$), all unmasked bit columns must match. We integrate the Key Register mask ($K_j$): $$x_j + \bar{K}_j = A_j B_{ij} + \bar{A}_j \bar{B}_{ij} + \bar{K}_j$$ If $K_j = 0$ (column masked), the term evaluates to $1$, bypassing the bit mismatch. If $K_j = 1$ (active comparison), the term depends strictly on whether $A_j = B_{ij}$.

By combining all $N$ bits of word $i$ using a parallel AND operation, we derive the final Match Logic output equation: $$M_i = \prod_{j=1}^N (A_j B_{ij} + \bar{A}_j \bar{B}_{ij} + \bar{K}_j)$$

5. Worked Examples & Traces

Execution Trace

Worked Example 3.2.1: Parallel Match Logic Resolution

**Problem**: Trace how the Match Register bits are resolved for a 3-word CAM array given: - Argument Register $A = 1010_2$ - Key Register $K = 1100_2$ - Memory array words: Word 0 $= 1001_2$, Word 1 $= 1101_2$, Word 2 $= 1011_2$.

**Step-by-Step Trace**:

  1. **Evaluate Key Register Mask**: Since $K = 1100_2$, we only compare bits 3 and 2 ($j=4, 3$). Bits 1 and 0 ($j=2, 1$) are masked and ignored. The target search pattern is: $$A_{\text{target}} = 10\text{XX}$$
  2. **Evaluate Word 0**: Word 0 is $1001_2$. - Bit 3: $B_{0,3} = 1$, $A_3 = 1$ (Match) - Bit 2: $B_{0,2} = 0$, $A_2 = 0$ (Match) - Bits 1, 0: Masked ($K_j = 0 \Rightarrow$ evaluates to 1). - Result: $M_0 = 1 \times 1 \times 1 \times 1 = 1$.
  3. **Evaluate Word 1**: Word 1 is $1101_2$. - Bit 3: $B_{1,3} = 1$, $A_3 = 1$ (Match) - Bit 2: $B_{1,2} = 1$, $A_2 = 0$ (Mismatch) - Result: $M_1 = 1 \times 0 \times 1 \times 1 = 0$.
  4. **Evaluate Word 2**: Word 2 is $1011_2$. - Bit 3: $B_{2,3} = 1$, $A_3 = 1$ (Match) - Bit 2: $B_{2,2} = 0$, $A_2 = 0$ (Match) - Result: $M_2 = 1 \times 1 \times 1 \times 1 = 1$.
  5. **Verify Final Match Register**: $$M = 101_2 \text{ (Words 0 and 2 match).}$$
Viva Voce Q&A

Oral Exam Preparation

**Question**: "What is the physical effect on the Match Register if the Key Register is cleared to all 0s?"

**Answer**: If the Key Register is cleared to all 0s, every bit column is masked ($\bar{K}_j = 1$). Consequently, the Match equation term $(x_j + \bar{K}_j)$ evaluates to $1$ for all bits, forcing every bit in the Match Register ($M$) to $1$.

Common Mistakes to Avoid

Revision Summary & Takeaways

  • Associative Memory (CAM) searches data arrays by value rather than addresses.
  • The Key Register ($K$) acts as a column comparison mask.
  • Match Logic combines XNOR logic gates with active-high key bits in a parallel AND chain.
How this chapter connects to the next

We have analyzed how CAM cells use parallel match gates to perform single-cycle searches. In Chapter 3.3: Cache Mapping (Direct), we explore cache design, showing how these content-matching structures are simplified into direct-mapped cache indexes to balance speed and transistor cost.

Check Your Understanding

1. Which register in an associative memory unit flags which words match the search arguments?

References

  1. **ref-notes-syed-arsalaan**: Handwritten Lecture Notes, Pages 83–87 (CAM Cell Match Gates). [Local Verified]
  2. **ref-notes-class**: Class COA Lecture Notes, Pages 41–43 (Associative Arrays). [Local Verified]
  3. **ref-book-mano**: M. Morris Mano, *Computer System Architecture*, 3rd Edition, Chapter 12. [Pending Verification]
  4. **ref-lecture-sengupta-28**: Prof. Indranil Sengupta, NPTEL COA, Lecture 28 (Associative Memory). [Pending Verification]