<meter id="pryje"><nav id="pryje"><delect id="pryje"></delect></nav></meter>
          <label id="pryje"></label>

          新聞中心

          EEPW首頁 > EDA/PCB > 設計應用 > 一種散列表的FPGA設計與實現(xiàn)

          一種散列表的FPGA設計與實現(xiàn)

          作者: 時間:2013-04-18 來源:網(wǎng)絡 收藏

          摘要:文章在簡要介紹散列表工作原理的基礎上,提出了一種分離鏈接散列表的實現(xiàn)方案,并對方案涉及的各功能模塊實現(xiàn)進行了詳細闡述。
          關鍵詞:散列表;;Wishbone總線;SRAM

          0 引言
          在軟硬件開發(fā)過程中,經(jīng)常需要通過關鍵字對數(shù)據(jù)信息進行存儲、查找、刪除等操作,從而實現(xiàn)數(shù)據(jù)信息的管理。散列表能夠以常數(shù)平均時間實現(xiàn)插入、刪除和查找,因此在實現(xiàn)過程中得到廣泛應用。本文基于設計并實現(xiàn)了一種分離鏈接法解決散列表,利用快速查找緩沖區(qū)提高查詢效率,采用空閑存儲區(qū)管理模塊實現(xiàn)存儲空間的高效分配及釋放。

          1 工作原理
          散列表根據(jù)設定的散列函數(shù)Hash(Key)和處理沖突的方法將一組關鍵字映像到一個有限的連續(xù)的地址區(qū)間上,并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置。散列表的實現(xiàn)主要研究兩個問題:散列函數(shù)的選取和沖突解決的辦法。
          1.1 散列函數(shù)選取
          一個好的散列函數(shù)可以使關鍵字盡量隨機均勻地分布在散列表中,降低沖突發(fā)生的概率,提高散列表查找的效率。理想的散列函數(shù)對于關鍵字集合中的任一個關鍵字,經(jīng)散列后映象到地址集合中任何一個地址的概率是相等的。考慮到FPGA實現(xiàn)的效率及復雜度,本文采用了CRC算法作為散列函數(shù),實現(xiàn)關鍵字到散列表地址的映射。
          1.2 沖突解決方法
          散列表解決沖突的方法主要有開放地址法和分離鏈接法。在開放定址散列算法系統(tǒng)中,如果有沖突發(fā)生,那么就要嘗試選擇另外的單元,直到找出空的單元位置。在分離鏈接散列算法系統(tǒng),通過給新單元分配地址空間,建立鏈表來解決沖突。因為所有的數(shù)據(jù)都要置于表內(nèi),所以開放定址散列法所需要的表要比分離鏈接散列用表大。一般說來,對開放定址散列算法來說,裝填因子應低于0.5。

          本文引用地址:http://www.ex-cimer.com/article/189637.htm

          a.JPG


          本文采用分離鏈接法解決散列表存在的沖突,建立如圖1所示散列表存儲結(jié)構(gòu),每個鏈表首地址存放在FPGA內(nèi)部的連續(xù)RAM中,表元存放在SRAM芯片中。每個表元主要包含關鍵字(Key)、數(shù)據(jù)(Data)和下一表元地址(Next),由于關鍵字和下一表元地址字段訪問頻繁,在FPGA實現(xiàn)過程中把這兩個字段置于每個表元的頭部,盡量在一次SRAM的Brust讀/寫操作內(nèi)完成。

          2 FPGA實現(xiàn)
          如圖2所示,分離鏈接散列表采用Wishbone總線標準接口與外部組件交互,采用接口控制器實現(xiàn)Wishbone總線管理,采用主控制器生成表元查找、表元添加、表元刪除等模塊的控制信號,采用存儲訪問仲裁器實現(xiàn)各模塊SRAM訪問的分時復用,采用基于內(nèi)部CAM的快速查找緩沖模塊實現(xiàn)表元地址的快速查找。

          b.JPG


          2.1 接口控制器
          接口控制器作為本模塊與FPGA內(nèi)部其它功能模塊之間交互的橋梁通道,采用Wishbone總線接口標準。Wishbone總線是由Silicore公司開發(fā)的完全免費的片上總線規(guī)范,具有靈活、“輕量級”的優(yōu)點。Wishone采用主/從設備架構(gòu),本模塊工作于從設備模式,支持“單次讀/寫”和“塊讀/寫”操作。接口控制器實現(xiàn)以下功能:
          (1)根據(jù)地址信息的不同,調(diào)用不同的功能邏輯處理輸入數(shù)據(jù),并返回應答;
          (2)把關鍵字(Key)送到Hash運算模塊進行運算;
          (3)把命令類型、Hash值、關鍵字按格式送入命令輸入緩沖區(qū);
          (4)把待寫入SRAM的數(shù)據(jù)送入數(shù)據(jù)輸入緩沖區(qū);
          (5)處理狀態(tài)讀取命令,返回模塊當前狀態(tài);
          (6)處理數(shù)據(jù)讀取命令,從緩沖區(qū)輸出數(shù)據(jù)、讀取數(shù)據(jù)并輸出。
          2.2 主控制器
          主控制器是散列表FPGA實現(xiàn)的核心模塊,循環(huán)讀取命令輸入緩沖區(qū)中的命令數(shù)據(jù),并根據(jù)命令類型生成表元查找、表元添加、表元刪除、空閑表元申請、空閑表元釋放及輸入/輸出等請求信號。

          c.JPG


          (1)主控制器在復位信號失效后,給空閑存儲區(qū)管理模塊發(fā)送初始化請求,在初始化完成后進入空閑狀態(tài),等待命令輸入緩沖區(qū)送入的命令數(shù)據(jù);
          (2)主控制器在收到查找命令后,給表元查找模塊發(fā)送請求,匹配成功則根據(jù)命令內(nèi)容給數(shù)據(jù)輸入/輸出模塊發(fā)送請求,完成數(shù)據(jù)讀取和寫入,否則完成本次操作返回應答;
          (3)主控制器在收到添加命令后,首先查找是否存在關鍵字匹配表元,匹配失敗則向緩沖區(qū)管理模塊發(fā)送請求獲取空閑表元,成功后根據(jù)命令內(nèi)容給數(shù)據(jù)輸入/輸出模塊發(fā)送請求,完成數(shù)據(jù)讀取和寫入。
          (4)主控制器在收到刪除命令后,首先查找是否存在關鍵字匹配表元,匹配成功則向表元刪除模塊發(fā)送請求,并在刪除成功后釋放緩沖區(qū)到空閑緩沖區(qū)池。


          上一頁 1 2 下一頁

          關鍵詞: FPGA

          評論


          相關推薦

          技術專區(qū)

          關閉
          看屁屁www成人影院,亚洲人妻成人图片,亚洲精品成人午夜在线,日韩在线 欧美成人 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();