[發(fā)明專利]一種快速搜索CAM的方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201210385491.7
• 申請(qǐng)日: 2012-10-12
• 公開（公告）號(hào): CN102937969A
• 公開（公告）日: 2013-02-20
• 發(fā)明（設(shè)計(jì)）人: 周恒釗;陳繼承
• 申請(qǐng)（專利權(quán)）人: 浪潮電子信息產(chǎn)業(yè)股份有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06F12/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及集成電路設(shè)計(jì)領(lǐng)域,?具體地說是一種快速搜索CAM的方法。

背景技術(shù)

CAM（Content?Addressable?Memory），是一種特殊類型的計(jì)算機(jī)存儲(chǔ)器，被廣泛運(yùn)用于計(jì)算機(jī)和通信領(lǐng)域。標(biāo)準(zhǔn)的存儲(chǔ)器RAM的功能為根據(jù)用戶提供的讀地址返回存儲(chǔ)在該地址上的數(shù)據(jù)字。不同于RAM，CAM的功能為根據(jù)用戶提供的一個(gè)數(shù)據(jù)字，搜索全部的存儲(chǔ)以判斷該數(shù)據(jù)字是否存儲(chǔ)在其中。如果找到這個(gè)數(shù)據(jù)字，則返回匹配地址，即該數(shù)據(jù)字在存儲(chǔ)器中的位置，因此CAM就是軟件術(shù)語associative?array的硬件具體化。

通常的CAM設(shè)計(jì)原理為在一個(gè)操作中搜索整個(gè)存儲(chǔ)，即讀出存儲(chǔ)器中每一組數(shù)據(jù)，并將外部接收的數(shù)據(jù)與之逐一進(jìn)行比較，然后根據(jù)比較結(jié)果對(duì)其進(jìn)行優(yōu)先譯碼，優(yōu)先譯碼器產(chǎn)生一個(gè)二進(jìn)制的匹配位置定位和一個(gè)匹配命中信號(hào)。常規(guī)的CAM實(shí)現(xiàn)方法有兩種，一種為將數(shù)據(jù)存儲(chǔ)在SRAM中，搜索時(shí)逐一讀出SRAM中的內(nèi)容與查找字進(jìn)行比較。另一種為將數(shù)據(jù)存儲(chǔ)在Register搭建存儲(chǔ)器組中，搜索時(shí)將查找字廣播到每一組Register中進(jìn)行比較，再由優(yōu)先譯碼器根據(jù)各組的比較結(jié)果產(chǎn)生匹配位置和匹配命中信號(hào)。

但上述兩種實(shí)現(xiàn)方法均存在不同程度的弊端，第一種方法受到RAM讀端口數(shù)量的限制，且完成一個(gè)CAM搜索過程需要的延時(shí)很大，L?=?（存儲(chǔ)器深度/RAM讀端口個(gè)數(shù)）*?Tclk?，需要多個(gè)時(shí)鐘周期。在RAM器件規(guī)格確定，端口不變的前提下，存儲(chǔ)器深度越大，CAM搜索延遲也就越大。以一個(gè)1讀1寫兩端口SRAM實(shí)現(xiàn)的CAM為例，若存儲(chǔ)深度為64，則需要64個(gè)時(shí)鐘周期才能完成一次搜索。第二種方法則受到資源和面積的約束，使用Register搭建的存儲(chǔ)器組雖然能并行對(duì)查找字進(jìn)行比較，但占用的芯片面積比同等容量的SRAM大。查找字?jǐn)?shù)據(jù)寬度越大，這種面積差距就越明顯，為芯片的資源分配和布局布線帶來很大的挑戰(zhàn)。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種快速搜索CAM的方法。

本發(fā)明的目的是按以下方式實(shí)現(xiàn)的，快速搜索CAM是基于SRAM存儲(chǔ)器和邏輯控制模塊來實(shí)現(xiàn)，以搜索內(nèi)容作為讀地址，同時(shí)進(jìn)行多塊SRAM存儲(chǔ)器訪問，SRAM存儲(chǔ)器中存儲(chǔ)的內(nèi)容均為寬度等同于CAM搜索深度的位向量，位向量中的有效位即指示搜索匹配結(jié)果和匹配項(xiàng)地址，經(jīng)過邏輯控制模塊合并多塊SRAM存儲(chǔ)器輸出的結(jié)果，得到完整搜索內(nèi)容在CAM中的匹配結(jié)果和匹配項(xiàng)的地址；具體步驟如下：

1）SRAM存儲(chǔ)器存放寬度等同于CAM搜索深度的位向量，每次進(jìn)行CAM搜索時(shí)以被檢索的數(shù)據(jù)作為讀地址，發(fā)起相應(yīng)的SRAM存儲(chǔ)器讀操作，SRAM存儲(chǔ)器返回對(duì)應(yīng)地址上的位向量；

2）SRAM存儲(chǔ)器的讀使能由CAM搜索使能驅(qū)動(dòng)，讀地址由CAM搜索內(nèi)容驅(qū)動(dòng)，將CAM的查找字以存儲(chǔ)器深度為基數(shù)劃分為若干個(gè)搜索子區(qū)間，每個(gè)子區(qū)間各對(duì)應(yīng)一片SRAM存儲(chǔ)器，所有SRAM存儲(chǔ)器之間互不相干；

3）并行讀出每個(gè)子區(qū)間所對(duì)應(yīng)的SRAM存儲(chǔ)器中的位向量，每個(gè)位向量都代表了它所在查找字子區(qū)間的匹配信息，由CAM控制邏輯模塊完成對(duì)每個(gè)位向量的合并操作，即每次輸入的相同數(shù)據(jù)寬度的二進(jìn)制操作數(shù)逐位與&操作，計(jì)算出一個(gè)完整寬度的查找字在CAM中的匹配信息；

4）SRAM存儲(chǔ)器中每個(gè)地址上均存放著數(shù)據(jù)寬度等同于CAM搜索深度的位向量，位向量每一位指代一個(gè)CAM的有效入口，1表示該入口有效，0表示無效，指示CAM有效入口的位向量，位向量中值為1的位所在位向量中的位置即為該有效入口在CAM中的匹配地址；位向量某一位值等于1，說明CAM中同等位置上存在與查找字相同的數(shù)據(jù)，搜索完成，匹配成功，位向量所有位都等于0，說明CAM中不存在與查找字相同的數(shù)據(jù)，搜索完成，匹配失敗；

5）CAM控制邏輯模塊在接收到SRAM存儲(chǔ)器控制單元發(fā)出的每個(gè)位向量后對(duì)其進(jìn)行合并，縮減和優(yōu)先譯碼，計(jì)算出最終的搜索匹配結(jié)果和匹配地址,并在端口上輸出對(duì)應(yīng)內(nèi)容，完成對(duì)多個(gè)SRAM存儲(chǔ)器讀出數(shù)據(jù)的合并操作和各子區(qū)間對(duì)應(yīng)的位向量的與操作，得到完整搜索數(shù)據(jù)所對(duì)應(yīng)的位向量；

6）CAM控制邏輯模塊合并操作完成后，對(duì)合并結(jié)果進(jìn)行縮減運(yùn)算或（|）操作和優(yōu)先譯碼pri-encoder操作，合并位向量的縮減運(yùn)算或操作的結(jié)果即為CAM的搜索匹配結(jié)果，1表示匹配成功，0表示匹配失敗，合并位運(yùn)算的優(yōu)先譯碼操作的結(jié)果即為CAM的匹配項(xiàng)在CAM中的地址；