[發明專利]一種地址查找、關鍵字存儲方法及設備

有效

• 申請號: 201710571150.1
• 申請日: 2017-07-13
• 公開（公告）號: CN107506310B
• 公開（公告）日: 2020-04-24
• 發明（設計）人: 秦增杰
• 申請（專利權）人: 北京東土軍悅科技有限公司;北京物芯科技有限責任公司
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 黃志華

本發明公開了一種地址查找、關鍵字存儲方法及設備，用于減少對存儲空間的浪費，提高存儲空間的利用率。該地址查找方法包括：獲取待查找關鍵字，并確定待查找關鍵字的位寬；根據TCAM的單位存儲單元的位寬和待查找關鍵字的位寬，確定存儲待查找關鍵字所需單位存儲單元的數量2^N；將待查找關鍵字劃分成2^N個子關鍵字，并在2^N個子關鍵字中的每個子關鍵字中增加位寬標識，位寬標識用于指示待查找關鍵字的位寬；將2^N個子關鍵字與TCAM中存儲的關鍵字進行匹配；其中，當2^N個子關鍵字與TCAM中存儲的關鍵字的位寬標識相同時能夠匹配成功；根據2^N個子關鍵字與TCAM中存儲的關鍵字的匹配結果，確定TCAM中與待查找關鍵字相匹配的關鍵字的地址。

技術領域

本發明涉及通信技術領域，特別涉及一種地址查找、關鍵字存儲方法及設備。

背景技術

三態內容尋址存儲器(Ternary Content Addressable Memory，TCAM)主要用于關鍵字(Key)存儲與查找。具體的，首先在TCAM中存儲一定數量的關鍵字，再在存儲該關鍵字的地址對應的隨機存取存儲器(random access memory，RAM)中存儲該關鍵字相關聯的數據；這樣，就可以通過查找該關鍵字，進而查找到TCAM中存儲該關鍵字的地址，進一步地查找到存儲RAM中該地址所對應的該關鍵字相關聯的數據。

目前，在芯片內部實現時，由于會有不同長度的關鍵字要存放在TCAM中，在設置TCAM塊的位寬時，通常是根據需要存儲的關鍵字的最大的位寬來進行設置的。例如，需要存儲的關鍵字的位寬分別為36bit、72bit和144bit，那么在設置TCAM塊的位寬時則會按照最長關鍵字的位寬(例如上述144bit)來設置，那么在存放36bit和72bit的關鍵字時，由于只能占據一個存儲單元的一部分，而剩余的一部分存儲單元不會再用于存儲其他的關鍵字，所以就造成了存儲單元的浪費。或者，還可以通過根據不同位寬的關鍵字設置不同位寬的TCAM塊，在同一TCAM塊中存儲相同位寬的關鍵字，不同TCAM塊存儲不同的位寬的關鍵字，即將不同位寬的關鍵字進行分開存儲，但是這樣不同位寬的關鍵字則無法達到TCAM存儲空間動態共享的效果。

發明內容

本發明實施例提供一種地址查找、關鍵字存儲方法及設備，用于減少對存儲單元的浪費，提高存儲單元的利用率。

第一方面，提供一種地址查找方法，該方法包括：

獲取待查找關鍵字，并確定所述待查找關鍵字的位寬；

根據TCAM的單位存儲單元的位寬和所述待查找關鍵字的位寬，確定存儲所述待查找關鍵字所需的單位存儲單元的數量2^N；其中，2^N為存儲所述待查找關鍵字所需的單位存儲單元的最小數量；所述TCAM中包括至少一個單位存儲單元，所述單位存儲單元的位寬不大于存儲的位寬最小的關鍵字的位寬；N為大于或等于零的整數；

將所述待查找關鍵字劃分成2^N個子關鍵字，并在所述2^N個子關鍵字中的每個子關鍵字中增加位寬標識，所述位寬標識用于指示所述待查找關鍵字的位寬；

將所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字進行匹配；其中，所述2^N個增加了位寬標識的子關鍵字分別與存儲在不同的且地址連續的單位存儲單元的關鍵字進行匹配；所述TCAM中存儲的關鍵字攜帶有指示所述存儲的關鍵字的位寬的位寬標識，當所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字的位寬標識相同時能夠匹配成功；

根據所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字的匹配結果，確定所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址。