內容可定址主記憶體

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

內容可定址主記憶體

資料字辨識單元是由達德利·艾倫·巴克（英語：Dudley Allen Buck）於 1955年提出的^[2]。

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和系統。^[3]

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

替代實現

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

三元 CAM

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

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

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

應用範例

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

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

CAM的其他應用包括：

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

參見

• 內容定址網路（英語：Content-addressable network）
• 內容定址並列處理器（英語：Content-addressable parallel processor）
• 內容定址儲存（英語：Content-addressable storage）
• 稀疏分散式記憶體
• 元組空間（英語：tuple space）

參考資料

1. K. Pagiamtzis* and A. Sheikholeslami, Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, pp. 712-727, March 2006. (PDF). [2022-12-23]. （原始內容存檔 (PDF)於2007-03-15）.
2. TRW Computer Division 網際網路檔案館的存檔，存檔日期August 5, 2011，., 1963, p. 17.
3. C. Stormon, N. Troullinos, E. Saleh, A. Chavan, M. Brule and J. Oldfield, "A general-purpose CMOS associative processor IC and system", IEEE Micro, vol. 12, no. 6, pp. 68-78, December 1992.. [2022-12-23]. S2CID 206432751. doi:10.1109/40.180249. （原始內容存檔於2022-04-08）.
4. Sibercore Technologies - Silicon Solutions for Cyberspace. （原始內容存檔於2003-04-19）.
5. 16nm Heterogeneous Knowledge-Based Processors (KBPs). [2022-12-23]. （原始內容存檔於2017-05-19）.
6. Hucaby, David. CCNP BCMSN Exam Certification Guide: CCNP Self-study. 2004. ISBN 9781587200779.
7. Varghese, George, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, 2005
8. Hinton, Geoffrey E. Distributed representations. 1984 [2022-12-23]. （原始內容存檔於2016-05-02）.

參考書目

• 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