Associative Memory (Content Addressable Memory - CAM)

Definition: Memory accessed by content (data) rather than by address. CPU supplies a search word (key); memory simultaneously compares it with all stored words in parallel and marks those that match. Access time is constant $O(1)$ irrespective of location. Opposite of Random Access Memory (RAM) where $address \rightarrow data$.

Also called Associative Storage / Content Addressable Memory.

Block Diagram

                   +-----------------------------+
Search Word (Argument) -->| Argument Register (A)     |
  (key + mask)     |   Key Register (K)  Mask (M) |
                   +-------------+---------------+
                                 | (unmasked bits)
                                 v
                   +-----------------------------+
                   | Associative Memory Array    |  Word0: bit0..bit n + Match logic
                   |  Word1  } each with         |  Word1:  comparator (XNOR per bit)
                   |  ...    } comparison logic  |  ...     + AND of bits
                   |  Wordm  }                   |
                   +-------------+---------------+
                                 | Match lines Mi (Mi=1 if word i matches A on K=1 bits)
                                 v
                   +-----------------------------+
                   | Encoder / Priority or       |
                   | Match Register + Selector   |----> Matched word(s) out
                   +-----------------------------+

• Argument Register A: holds search key.
• Key Register K: 1 means compare that bit, 0 = don't care (maskable).
• Mask Register M (optional): disables masked bits.
• Match Logic per word: $M_i = \bigwedge_{j: K_j=1} (A_j \oplus \text{Word}_{ij})'$ =1 only if all unmasked bits equal.
• Output is either first matching word (priority encoder) or all matches flagged.

Operation: Load $A$ and $K$, assert search, all words compare in parallel (one clock), $M_i$ vector produced, encoder outputs address/data of matched word. Write modifies matched word(s).

Example: 4 words 1010, 1100, 1011, 0010; search $A=1010$, $K=1110$ (don't care LSB) => matches word0 (1010) and word2 (1011).

Cost & Characteristics

• Fast search $O(1)$ but hardware heavy: comparator per bit per word => $m \times n$ XNOR gates. Expensive, power hungry, so used small.
• Word size typically 16-64 bits, capacity $32$ to $4K$ words.

Effective Utilization

1. Cache Memory / TLB (Translation Lookaside Buffer): Most important use. Fully associative cache / TLB stores block tags; CPU searches tag in parallel to find hit/miss without set indexing. E.g. TLB maps virtual page -> physical frame: associative lookup of VPN yields PPN in one cycle.

2. Virtual Memory Page Table Cache: Hardware search of page table.

3. Database / Pattern Matching: Search records by field (e.g. find all employees with age=30) without scanning.

4. Networking: Router's forwarding table, packet classification, firewall ACLs, Ethernet switch MAC lookup, IP longest prefix match -> ternary CAM (TCAM) with don't-care.

5. AI / Fault tolerance: Associative recall, spare memory remapping.

In COA syllabus: used to implement fully associative cache and TLB where hit time must be minimal; otherwise direct-mapped is cheaper. Hybrid set-associative + CAM for tags is practical trade-off.