[發(fā)明專利]基于散列鏈表的內(nèi)容尋址方法及相應(yīng)的存儲器電路

有效

• 申請?zhí)枺?/td>: 201210579916.8
• 申請日: 2012-12-27
• 公開（公告）號: CN103064948A
• 公開（公告）日: 2013-04-24
• 發(fā)明（設(shè)計）人: 田澤;張榮華;張玲;劉航
• 申請（專利權(quán)）人: 中國航空工業(yè)集團公司第六三一研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/02
• 代理公司: 西安智邦專利商標代理有限公司 61211
• 代理人: 王少文

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

本發(fā)明屬于計算機硬件技術(shù)，涉及一種內(nèi)容尋址存儲器實現(xiàn)方法。

背景技術(shù)

內(nèi)容尋址存儲器（Content?Addressable?Memory，簡稱CAM）是一種特殊的存儲器陣列，它的主要工作機制就是將一個輸入數(shù)據(jù)項與存儲在CAM中的所有數(shù)據(jù)項自動進行比較，并輸出該數(shù)據(jù)項對應(yīng)的匹配信息，具有檢索速度快，使用靈活等特點，被廣泛應(yīng)用于網(wǎng)絡(luò)通信等領(lǐng)域。現(xiàn)有技術(shù)主要采用晶體管級全定制電路設(shè)計實現(xiàn)，其優(yōu)點是檢索速度快，缺點是需要專門工藝、成本高昂，不利于大規(guī)模使用；目前基于RTL設(shè)計的電路一般采用串行、并行、二分法、散列法等設(shè)計思路，設(shè)計的電路不是檢索速度慢，就是消耗資源太多，不利于檢索深度和寬度的擴展，無法滿足現(xiàn)代網(wǎng)絡(luò)通信和數(shù)據(jù)處理對檢索深度和速度的使用要求。

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

本發(fā)明的目的是提供一種采用RTL設(shè)計語言，綜合散列查找、鏈表存儲、并行比較等技術(shù)的內(nèi)容尋址存儲器電路實現(xiàn)方法。

本發(fā)明的解決方案是：

一種基于鏈接散列的內(nèi)容尋址方法，其包括以下步驟：

步驟1、用戶定義檢索關(guān)鍵字和檢索深度，其中檢索關(guān)鍵字位寬為M，檢索關(guān)鍵字關(guān)聯(lián)內(nèi)容位寬為C，檢索深度為2^S；

步驟2、取檢索關(guān)鍵字最高位作為分支BR，從次高位開始依次取3位作為迷你關(guān)鍵字MKEY，檢索關(guān)鍵字剩余位作為散列地址HASHADD；

步驟3、定義檢索散列函數(shù)，將檢索關(guān)鍵字作為散列函數(shù)的輸入，散列地址HASHADD作為散列函數(shù)的結(jié)果；

步驟4、構(gòu)造鏈表存儲器，在鏈表存儲器中動態(tài)創(chuàng)建散列函數(shù)結(jié)果沖突的檢索數(shù)據(jù)鏈表，其中沖突數(shù)目大于1且小于等于4時，創(chuàng)建一級鏈表存儲器，沖突數(shù)目大于4時，創(chuàng)建二級鏈表存儲器；鏈表存儲器地址寬度為S/2,存儲器數(shù)據(jù)寬度為W=4×（關(guān)鍵字有效位+迷你關(guān)鍵字+偏移地址），存儲4個檢索關(guān)鍵字對應(yīng)的關(guān)鍵字有效位#_VAL、迷你關(guān)鍵字#_MKEY、偏移地址#_OFFSET，所述#_VAL代表3_VAL，2_VAL，1_VAL，0_VAL；所述#_MKEY代表3_MKEY，2_MKEY，1_MKEY，0_MKEY；所述#_OFFSET代表3_OFFSET，2_OFFSET，1_OFFSET，0_OFFSET；

當3_VAL為1時，鏈表存儲器3_VAL、3_MKEY、3_OFFSET字段為一個有效的數(shù)據(jù)項對應(yīng)的檢索信息；當3_VAL為0且3_MKEY為111時，字段3_OFFSET為一個二級鏈表指針；當3_VAL為0且3_MKEY為100時，字段3_OFFSET為下一個空閑鏈表指針；當3_VAL為0且3_MKEY為其他值時，3_MKEY、3_OFFSET字段為無效的數(shù)據(jù)項；

步驟5、構(gòu)造鏈表存儲器管理電路，包括位寬為S/2的空閑鏈表頭指針、位寬為S/2的空閑鏈表尾指針、位寬為S/2+1的空閑鏈表計數(shù)器、位寬為S/2+1的鏈表使用計數(shù)器；

步驟5.1，內(nèi)容尋址存儲器復(fù)位后，空閑鏈表頭指針為0，空閑鏈表尾指針為2^S/2-1，空閑鏈表計數(shù)為2^S/2，鏈表初始化狀態(tài)信號為0，鏈表使用計數(shù)器為2；

步驟5.2，當內(nèi)容尋址存儲器新增數(shù)據(jù)項的散列結(jié)果沖突，且為第2個或第5個沖突數(shù)據(jù)項，將動態(tài)分配空閑鏈表頭指針作為新的散列沖突數(shù)據(jù)項存儲位置；當鏈表使用計數(shù)器小于2^S/2時，空閑鏈表計數(shù)器減1，空閑鏈表頭指針加1，鏈表使用計數(shù)器加1；當鏈表使用計數(shù)器大于等于2^S/2時，首先按照空閑頭指針訪問鏈表存儲器，將獲取的下一個空閑鏈表指針作為新的空閑鏈表頭指針，然后空閑鏈表計數(shù)器減1，鏈表使用計數(shù)器不變。

步驟5.3，當內(nèi)容尋址存儲器刪除某數(shù)據(jù)項時，如果刪除前該地址散列結(jié)果沖突數(shù)目為2或5，要求對刪除后的散列沖突數(shù)據(jù)項排列進行移位，釋放一個鏈表存儲器地址。并將釋放的鏈表存儲器地址作為下一個空閑鏈表指針寫到空閑鏈表尾指針指向的鏈表存儲器地址，然后將釋放的鏈表存儲器地址作為新的空閑鏈表尾指針，然后空閑鏈表計數(shù)器加1，鏈表使用計數(shù)器不變。

步驟6、構(gòu)造一個散列存儲器，散列存儲器地址寬度為（M-4），數(shù)據(jù)寬度＝2×(迷你關(guān)鍵字位寬+檢索關(guān)鍵字對應(yīng)的偏移地址位寬+鏈表存儲器地址位寬+鏈表指針有效位)；存儲器數(shù)據(jù)內(nèi)容包括位數(shù)相等的高字段和低字段，其中高字段對應(yīng)分支BR=1的數(shù)據(jù)、低字段對應(yīng)分支BR=0的數(shù)據(jù)，字段數(shù)據(jù)依次為鏈表指針有效位EXL，一級鏈表指針LINK,關(guān)鍵字有效位VAL，迷你關(guān)鍵字MKEY,偏移地址OFFSET；