內容可定址內存

內容可定址內存

內容可定址內存(content-addressable memory, CAM) 是一種特殊類型的電腦記憶體，用於某些超高速搜尋應用程式。它也稱為關聯內存或關聯儲存，將輸入搜尋數據與儲存數據表進行比較，並返回匹配數據的地址。

數據字辨識單元是由達德利·艾倫·巴克於 1955年提出的。

CAM 經常用於網絡裝置中，它可以加速轉發資訊庫和路由表操作。這種關聯記憶體也用於高速緩衝記憶體。在相聯高速緩衝記憶體中，地址和內容並排儲存。當地址匹配時，從快取中取出相應的內容。

硬件相聯陣列

標準電腦內存隨機存取記憶體(RAM) 工作方式為用戶提供內存地址，RAM 返回儲存在該地址的數據字。而CAM與RAM不同。CAM 的設計使得用戶提供數據字，而 CAM 搜尋其整個內存，檢視該數據字是否存在。如果找到數據字，CAM 會返回一個包含一個或多個找到該字的儲存地址的列表。因此，CAM 是軟件術語中稱為關聯陣列的硬件體現。

標準

CAM 和其他網絡搜尋引擎的主要介面定義在網絡處理器討論區開發的稱為Look-Aside Interface（LA-1 和 LA-1B）的互操作性協定中指定。Integrated Device Technology 、賽普拉斯半導體 、IBM、博通有限等公司已經生產了許多符合互操作性協定的裝置。2007年12月11日，OIF發佈了串行後備（SLA）介面協定。

半導體實現

CMOS 二元 CAM 單元由 6T SRAM 單元和 4 個比較電晶體組成。當搜尋線 (SL) 上的數據與通過位線 (BL) 儲存在單元中的數據不同時，匹配線 (ML) 將被拉低以指示不匹配。如果匹配線上的儲存格均未指示位不匹配，則匹配線將在預充電電平上保持高電平以指示字匹配。兩條搜尋線都可以保持為邏輯「0」，作為don't care的搜尋條件。搜尋線和位線可以合併為一對數據線。

在數據搜尋應用程式中，CAM 比 RAM 快得多。然而，CAM 存在成本劣勢。與具有簡單儲存單元的 RAM晶片不同，完全並列 CAM 中的每個單獨的儲存位都必須有自己的比較電路，以檢測儲存位和輸入位之間的匹配。此外，必須組合數據字中每個單元的匹配輸出以產生完整的數據字匹配訊號。額外的電路增加了 CAM 晶片的物理尺寸和製造成本。額外的電路還增加了功耗，因為每個比較電路在每個時鐘周期都處於活動狀態。因此，CAM 僅適合於無法使用成本較低的方法實現搜尋速度的專用應用場景。一個成功的早期實施是通用關聯處理器IC和系統。

在 2000 年代初期，包括賽普拉斯半導體 、IDT、Netlogic 、Sibercore 和MOSAID在內的幾家半導體公司推出了針對網絡應用的CAM產品。這些產品包裝為網絡搜尋引擎（NSE）、網絡搜尋加速器（NSA）和基於知識處理器 （KBP），但本質上是具有針對網絡最佳化的專用介面和功能的CAM。目前， 博通有限提供多個 KBP 家族。

替代實現

為了在速度、內存大小和成本之間實現平衡，一些實現通過在硬件中使用標準樹搜尋或雜湊設計來模擬 CAM 的功能，使用複製或管線化等硬件技巧來加速有效效能。這些設計通常用於路由器。呂勒奧演算法是Internet 路由表中所需的最長字首匹配搜尋的有效實現。

三元 CAM

CMOS 三元 CAM 單元由兩個 6T SRAM 單元和 4 個比較電晶體組成。 通常情況下，相反的邏輯電平，即 「0」 和 「1」 或 「1」 和 「0」 將儲存在兩個單元中。 對於無關的邏輯，「0」 將儲存在兩個儲存格中，以便匹配線 ML 不會因搜尋線 (SL) 數據的任何組合而被拉低。

二進制 CAM 是最簡單的CAM類型，使用完全由1 與 0 組成的搜尋詞。 三元 CAM (Ternary CAM, TCAM) 允許在儲存的字中對一個或多個位元一種使用 X 或 無關 的 三值邏輯 進行搜尋， 因此增強了搜尋的靈活性。

例如，三元 CAM 中儲存的字 「10XX0」 與 「10000」、「10010」、「10100」、「10110」 這四個搜尋詞均能匹配。 與二進制 CAM 相比，由於搜尋靈活性的增加帶來了額外的成本，因為內部儲存單元現在必須編碼 3 種可能的狀態，而不是二進制 CAM 的 2 種。 這些附加狀態通常通過向每個儲存單元添加遮罩位（「相關」或「無關」位）來實現。

應用範例

可定址內容記憶體通常用於電腦網絡裝置。例如，當網絡交換機從其埠之一接收數據幀，它會使用幀的源MAC地址和接收它的埠更新內部表，然後它在表中尋找目標 MAC 地址以確定幀需要轉發到哪個埠，並在該埠上將其傳送出去。MAC地址表通常使用二元 CAM實現，因此可以非常快速地找到目標埠，從而減少交換機的延遲。

三元CAM 通常用於網絡路由器，其中每個地址都有兩部分：網絡字首（大小取決於子網絡組態），以及佔據其餘位的主機地址。每個子網絡都有一個網絡遮罩，用於指定地址的哪些位是網絡字首，哪些位是主機地址。路由是通過查詢由路由器維護的路由表來完成的，該表包含每個已知的目的地網絡字首、相關的網絡遮罩以及將封包路由到該目的地所需的資訊。在簡單的軟件實現中，路由器將要路由的封包的目標地址與路由表中的每個條目進行比較，對網絡遮罩執行按位元與運算，並將其與網絡字首進行比較。如果相等，則使用相應的路由資訊轉發封包。路由表使用三元 CAM 使尋找過程非常高效。地址使用不關心地址的主機部分儲存，因此在 CAM 中尋找目標地址會立即檢索正確的路由條目；封鎖和比較都是由 CAM 硬件完成的。如果（a）條目按網絡遮罩長度遞減的順序儲存，並且（b）硬件僅返回第一個匹配條目，則此方法有效；因此，使用具有最長網絡遮罩的匹配（最長字首匹配）。

CAM的其他應用包括：

• 全相聯快取控制器和轉譯後備緩衝區
• 資料庫引擎
• 數據壓縮硬件
• 類神經網絡
• 入侵防禦系統
• 網絡處理器
• 一些客製化電腦，如固特異STARAN ，使用CAM實現。

參見

• 內容定址網絡
• 內容定址並列處理器
• 內容定址儲存
• 稀疏分散式記憶體
• 元組空間

參考書目

• Anargyros Krikelis, Charles C. Weems (editors) (1997). Associative Processing and Processors, IEEE Computer Science Press. ISBN 0-8186-7661-2ISBN 0-8186-7661-2
• 6823434 
• Pagiamtis, K.; Sheikholeslami, A. Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey (PDF). IEEE Journal of Solid-State Circuits. 2006, 41 (3): 712–727 [2022-12-23]. Bibcode:2006IJSSC..41..712P. doi:10.1109/JSSC.2005.864128. （原始內容存檔 (PDF)於2022-12-23）. 
• Stormon, C.D.; Troullinos, N.B.; Saleh, E.M.; Chavan, A.V.; Brule, M.R.; Oldfield, J.V.; A general-purpose CMOS associative processor IC and system, Coherent Research Inc., East Syracuse, NY, USA, IEEE Micro, Dec. 1992, Volume: 12 Issue:6.
• TRW Computer Division. (1963). First interim report on optimum utilization of computers and computing techniques in shipboard weapons control systems. (BuWeps-Project RM1004 M88-3U1). Alexandria, Virginia:Defence Documentation Center for Scientific and Technical Information.

外部連結

• CAM Primer （頁面存檔備份，存於互聯網檔案館）
• Arithmetic Processing using Associative memory