Content-addressable memory (CAM) — Hinglish notes

4.1.13 · Hardware › Memory Technologies

CAM kyun exist karta hai?

Classic killer app hai: ek router ka forwarding table. Ek packet aata hai, tumhe instantly pata karna hota hai ki uski destination IP ke liye kaunsa output port match karta hai. Sequential search line-rate networking ke liye bahut slow hai — isliye routers CAM use karte hain.

CAM exactly kya hai?

Do flavours hain:

Yeh kaise banta hai? (First principles se derivation)

Hum CAM ko ek humble ek bit ki comparison se shuru karke build karte hain, phir ek word, phir poora array.

Step 1 — Ek bit compare karo

Hum chahte hain ek signal jo kahe "stored bit $D$ ≠ search bit $S$ ". Do bits ki inequality ka logic function XOR hai:

$mismatch = D \oplus S$

Yeh step kyun? Kyunki ek match ke liye har bit ka agree karna zaroori hai. Ek circuit banana zyada aasan hai jo disagreement detect kare aur ek shared wire pull kare, bajaaye hazaaron agreements ko AND karne ke.

Step 2 — Shared Match Line (ML)

Ek row ka har cell ek single match line (ML) se wired hota hai, jo search se pehle HIGH precharge hoti hai. Har cell mein ek transistor path hota hai jo ML ko LOW discharge karta hai agar woh bit mismatch kare.

Toh $n$ bits ke ek word ke liye, match line HIGH rehti hai tabhi jab koi bit use discharge na kare:

$ML_{row} = \overline{⋁_{i = 0}^{n - 1} (D_{i} \oplus S_{i})} = ⋀_{i = 0}^{n - 1} \overline{(D_{i} \oplus S_{i})} = ⋀_{i = 0}^{n - 1} (D_{i} ⊙ S_{i})$

jahan $⊙$ XNOR (equality) hai. Yeh bas De Morgan hai: "NOT (koi bhi mismatch)" = "saari bits equal hain".

Yeh step kyun? ML par wired-OR woh trick hai jo search ko parallel banati hai: row ke liye ek shared wire, aur koi bhi ek disagreeing cell akele poore match ko khatam kar sakta hai. Koi adder ya comparator tree ki zaroorat nahi — physics OR free mein karta hai.

Step 3 — Poora array + encoder

$R$ rows, har ek $n$ -bit word hai, har ek ka apna match line $ML_{r}$ hai.
Saari match lines simultaneously search hoti hain — poori memory ke liye ek comparison cycle.
Ek priority encoder (possibly bahut saari) HIGH match lines ko ek single output address mein convert karta hai (highest-priority / lowest-index match).

$search time \propto O (1) (independent of R, n in principle)$

Figure — Content-addressable memory (CAM)

Worked examples

Common mistakes (steel-manned)

CAM actually kahan use hota hai

Recall Feynman: ek 12-saal ke bacche ko explain karo

Ek badi classroom imagine karo. Normal memory (RAM) aisa hai jaise teacher kahe "seat number 42, khade ho jao" — tum ek seat dhundhte ho aur dekhte ho wahan kaun hai. CAM iska ulta hai: teacher chillata hai "jiska bhi naam Sam hai, haath uthao!" aur usi pal har student jiska naam Sam hai ek saath haath uthata hai. Tumne ek-ek karke check nahi kiya — sab ne ek saath khud ko check kiya. Yahi "sabne ek saath khud ko check kiya" wajah hai ki CAM itna fast kyun hai, lekin isliye bhi har seat mein ek chhota sa brain chahiye (extra transistors) aur bahut saari energy.

Active-recall flashcards

#flashcards/hardware

CAM kaunsa question answer karta hai, RAM ke mukable mein?

CAM: "is data ko kaunsa address hold karta hai?" (data→address). RAM: "is address par kya data hai?" (address→data).

CAM cell mein single-bit mismatch detect karne ke liye kaunsa logic gate use hota hai?

XOR (

D \oplus S

); poori row NOT-OR-of-mismatches = AND of XNORs (equality) use karti hai.

Search se pehle match line HIGH kyun precharge ki jaati hai?

Taaki ek mismatching cell use jaldi discharge kar sake; matched line HIGH rehti hai. Dynamic-logic style

O (1)

parallel search deta hai.

CAM mein priority encoder kyun chahiye?

Multiple rows simultaneously match kar sakti hain; encoder ek deterministic output address select karta hai (jaise lowest index / longest prefix).

BCAM aur TCAM mein kya fark hai?

BCAM 0/1 store karta hai (exact match). TCAM ek X don't-care state add karta hai (0 ya 1 se match karta hai) ek mask bit use karke, longest-prefix matching enable karta hai.

BCAM vs TCAM cell mein roughly kitne transistors hote hain?

BCAM ≈ 9–10T (6T SRAM + compare logic); TCAM ≈ 16T (0/1/X ke liye 2 storage bits chahiye).

CAM general-purpose memory ki tarah kyun use nahi hota?

High area, cost, aur power — har cell mein compare logic hai aur har search har match line charge karta hai.

CAM ke teen real uses batao.

TLBs, fully-associative cache tag lookup, network router forwarding/ACL tables (TCAM).

Mask

M_{i}

ke saath TCAM per-bit match condition likho.

match_{i} = M_{i} + (D_{i} ⊙ S_{i})

— ek don't-care (

M_{i} = 1

) hamesha match karta hai.

Connections

Static RAM (SRAM) — CAM cell = SRAM storage + comparison logic
Cache Memory — fully-associative caches tag matching ke liye CAM use karti hain
Translation Lookaside Buffer (TLB) — associative address translation
Priority Encoder — multiple simultaneous matches resolve karta hai
Boolean Algebra & De Morgan's Laws — match-line = NOT(OR of mismatches) = AND of equalities
Longest Prefix Matching — IP routing ke liye TCAM + priority
Dynamic Logic (Precharge/Evaluate) — match line ka electrical style