內容可尋址內存
內容可尋址內存(content-addressable memory, CAM) 是一種特殊類型的電腦記憶體,用於某些超高速搜索應用程序。它也稱為關聯內存或關聯存儲,將輸入搜索數據與存儲數據表進行比較,並返回匹配數據的地址。 [1]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Content-addressable-memory.png/220px-Content-addressable-memory.png)
數據字識別單元是由達德利·艾倫·巴克於 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)接口協議。
半導體實現
編輯在數據搜索應用程序中,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
編輯二進制 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的其他應用包括:
參見
編輯參考資料
編輯- ^ 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).
- ^ TRW Computer Division 網際網路檔案館的存檔,存檔日期August 5, 2011,., 1963, p. 17.
- ^ 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).
- ^ Sibercore Technologies - Silicon Solutions for Cyberspace. (原始內容存檔於2003-04-19).
- ^ 16nm Heterogeneous Knowledge-Based Processors (KBPs). [2022-12-23]. (原始內容存檔於2017-05-19).
- ^ Hucaby, David. CCNP BCMSN Exam Certification Guide: CCNP Self-study. 2004. ISBN 9781587200779.
- ^ Varghese, George, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, 2005
- ^ 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.