[發明專利]一種解決地址空間映射哈希地址沖突的方法及裝置

有效

• 申請號: 200910161571.2
• 申請日: 2009-08-04
• 公開（公告）號: CN101655821A
• 公開（公告）日: 2010-02-24
• 發明（設計）人: 徐健;王兆豐
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: G06F12/10
• 分類號: G06F12/10;G06F9/50;H04L29/12
• 代理公司: 北京安信方達知識產權代理有限公司
• 代理人: 龍 洪;霍育棟

技術領域

本發明涉及數字集成電路(IC，Integrated?Circuit)設計中的地址空間轉 換技術，尤其涉及地址空間映射過程中解決哈希沖突的方法及裝置。

背景技術

哈希算法是一種多對一的壓縮映射算法，它將高維空間的向量映射到低 維空間上。在IC硬件設計中通常使用哈希算法來實現地址空間轉換，將高維 地址空間映射到低維地址空間上，從而能夠快速尋址，并能夠節約硬件存儲 資源。因為其高維地址空間在實際應用中是一個稀疏空間，大部分地址是不 被使用的。但是，多對一的壓縮映射很容易導致幾個高維空間的地址被壓縮 到一個低位空間地址上，從而引起地址空間沖突，導致數據無法被正常存儲 或訪問。

傳統的哈希算法通常采用鏈表的形式來解決哈希地址沖突的問題。理論 上，采用鏈表技術可以處理所有的沖突項。但是，由于哈希查找次數取決于 鏈表的長度，鏈表的長度越長，哈希查找次數就越多，從而導致哈希查找時 間越長；因此這種技術的缺陷在于，其最壞情況的哈希查找時間不確定。實 際上，硬件設計受限于存儲器資源和處理時間的要求，鏈表的長度必須受到 限制，才能保證哈希查找時間確定。因此，一般情況下應將鏈表的表項(即 哈希沖突項)控制在4個以下。這種控制哈希沖突項的做法，其優點在于， 其最壞情況的哈希查找時間確定，即最多僅需查找4次；其缺點在于，哈希 表項的資源利用率不高，一般在60％左右，甚至更低。這里所說的哈希表項 資源利用率，等于(實際使用的高維空間向量數目-沖突數目)/實際使用的 高維空間向量數目，其中，沖突數目是指由于沖突未映射成功的高維向量總 數目。實際使用的高維空間向量數目應小于等于哈希表項總數(即等于低維 地址空間總數×哈希沖突項)。為了評判標準統一，可以選用高維空間向量 數目等于哈希表項總數。

改進的哈希算法采用多個哈希函數(哈希多項式)的技術，使得哈希函 數計算出的地址離散程度更高；這種技術的優點在于，在傳統哈希算法的基 礎上提高了哈希表項的資源利用率(即減少了沖突的哈希地址)，而其缺點 在于，增加了硬件設計的復雜度，硬件資源的開銷較大。實質上，它是以增 加哈希算法的哈希沖突項為代價，來提高哈希表項的資源利用率。

綜上所述，現有的解決地址空間映射哈希地址沖突的方法，要么其哈希 地址沖突解決的效果不夠好，亦即哈希表項的資源利用率不高；要么以增加 了硬件設計的復雜度及硬件資源的開銷來提高哈希地址沖突解決的效果；因 此均有待進一步改進。

發明內容

本發明所要解決的技術問題是提供一種解決地址空間映射哈希地址沖突 的方法及裝置，能夠以較低的硬件復雜度及資源開銷為代價來提高哈希表項 的資源利用率。

為了解決上述技術問題，本發明提供了一種解決地址空間映射哈希地址 沖突的方法，包括：

根據交叉矩陣配置將索引地址交叉變換成重組地址，并對重組地址進行 哈希計算得出哈希地址；該交叉矩陣配置是根據索引地址到重組地址的映射 規則所確認的具有高硬件資源利用率的交叉矩陣配置。

進一步地，該交叉矩陣配置的確認具體包括：

根據用戶應用場景確定索引地址的取值范圍；

逐一地改變索引地址到重組地址的映射規則，將索引地址交叉變換成重 組地址，針對該重組地址計算出哈希地址，并計算出該交叉矩陣配置下的硬 件資源利用率；

找出所有計算的硬件資源利用率中具有高硬件資源利用率所對應的交叉 矩陣配置。

進一步地，該交叉矩陣配置的確認通過軟件仿真方式實現，即該交叉矩 陣配置是根據所有的索引地址到重組地址的映射規則所確認的具有最高硬件 資源利用率的交叉矩陣配置。

進一步地，用戶應用場景指的是高維空間向量的所有可能值，高維空間 向量即索引地址，該索引地址由多個劃分塊組成，該劃分塊的劃分模式為比 特劃分或為字節劃分或為多字節劃分。

進一步地，硬件資源利用率按如下公式計算：

硬件資源利用率＝(實際使用的高維空間向量的數目-沖突數目)/實際使 用的高維空間向量的數目，該沖突數目是指由于沖突未映射成功的高維向量 總數目。

為了解決上述技術問題，本發明提供了一種解決地址空間映射哈希地址 沖突的裝置，包括依次連接的交叉矩陣配置模塊、交叉矩陣處理模塊以及哈 希計算模塊，其中：