一種散列表的FPGA設(shè)計(jì)與實(shí)現(xiàn)

摘要：文章在簡(jiǎn)要介紹散列表工作原理的基礎(chǔ)上，提出了一種分離鏈接散列表的FPGA實(shí)現(xiàn)方案，并對(duì)方案涉及的各功能模塊實(shí)現(xiàn)進(jìn)行了詳細(xì)闡述。
關(guān)鍵詞：散列表；FPGA；Wishbone總線；SRAM

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

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

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

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

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

    (1)主控制器在復(fù)位信號(hào)失效后，給空閑存儲(chǔ)區(qū)管理模塊發(fā)送初始化請(qǐng)求，在初始化完成后進(jìn)入空閑狀態(tài)，等待命令輸入緩沖區(qū)送入的命令數(shù)據(jù)；
    (2)主控制器在收到查找命令后，給表元查找模塊發(fā)送請(qǐng)求，匹配成功則根據(jù)命令內(nèi)容給數(shù)據(jù)輸入／輸出模塊發(fā)送請(qǐng)求，完成數(shù)據(jù)讀取和寫入，否則完成本次操作返回應(yīng)答；
    (3)主控制器在收到添加命令后，首先查找是否存在關(guān)鍵字匹配表元，匹配失敗則向緩沖區(qū)管理模塊發(fā)送請(qǐng)求獲取空閑表元，成功后根據(jù)命令內(nèi)容給數(shù)據(jù)輸入／輸出模塊發(fā)送請(qǐng)求，完成數(shù)據(jù)讀取和寫入。
    (4)主控制器在收到刪除命令后，首先查找是否存在關(guān)鍵字匹配表元，匹配成功則向表元?jiǎng)h除模塊發(fā)送請(qǐng)求，并在刪除成功后釋放緩沖區(qū)到空閑緩沖區(qū)池。
2．3 空閑存儲(chǔ)區(qū)管理
    為了實(shí)現(xiàn)存儲(chǔ)區(qū)的快速分配和有效管理，空閑存儲(chǔ)區(qū)管理模塊根據(jù)用戶設(shè)定的存儲(chǔ)區(qū)大小、分塊大小，把緩沖區(qū)分塊并組織成鏈表，并根據(jù)主控制器請(qǐng)求完成表元的刪除和添加。
    (1)本模塊在接到復(fù)位信號(hào)后進(jìn)入空閑狀態(tài)；
    (2)接收到空閑存儲(chǔ)區(qū)初始化請(qǐng)求后，修改SRAM中每一表元的頭部數(shù)據(jù)建立鏈表，存儲(chǔ)鏈表首地址；
    (3)接收到獲取緩沖區(qū)請(qǐng)求后，直接返回鏈表首地址，并根據(jù)鏈表首地址訪問(wèn)SRAM中的表元頭部數(shù)據(jù)，得到下一表元地址并作為新的鏈表首地址進(jìn)行存儲(chǔ)；
    (4)接收到釋放緩沖區(qū)請(qǐng)求后，把鏈表首地址寫入到待釋放表元的下一表元地址字段，把鏈表首地址修改為待釋放表元地址。
2．4 表元查找
    表元查找模塊在接到復(fù)位、放棄請(qǐng)求信號(hào)后，進(jìn)入空閑狀態(tài)，等待主控制器發(fā)起查找請(qǐng)求。在收到查找請(qǐng)求后根據(jù)輸入的鏈表首地址從SRAM讀取第一塊數(shù)據(jù)區(qū)的頭部數(shù)據(jù)(含關(guān)鍵字、下一表元地址)，在訪問(wèn)成功后進(jìn)行關(guān)鍵字比較，成功則查找結(jié)束并返回當(dāng)前表元地址和前一表元地址，否則根據(jù)下一表元地址循環(huán)查找直至最后一個(gè)表元，狀態(tài)轉(zhuǎn)換如圖4所示。表元?jiǎng)h除模塊需要使用當(dāng)前表元地址及前一表元地址。

2．5 表元添加
    表元添加模塊在接到復(fù)位信號(hào)后，進(jìn)入空閑狀態(tài)，等待主控制器發(fā)起表元添加請(qǐng)求。在收到添加請(qǐng)求后把鏈表首地址添加到新表元頭部數(shù)據(jù)的下一表元地址字段，修改鏈表首地址為新添加表元地址。
2．6 表元?jiǎng)h除
    表元?jiǎng)h除模塊在接到復(fù)位信號(hào)后，進(jìn)入空閑狀態(tài)，等待主控制器發(fā)起表元?jiǎng)h除請(qǐng)求。在收到待刪除表元地址及其前一表元地址后，讀取待刪除表元頭部數(shù)據(jù)，獲取下一表元地址(A-NEXT)字段，并寫入前一表元的下一表元地址(BA-NEXT)字段，完成表元?jiǎng)h除。

2．7 數(shù)據(jù)輸入／輸出
    數(shù)據(jù)輸入／輸出模塊主要完成輸入緩沖區(qū)、輸出緩沖區(qū)與SRAM之間的數(shù)據(jù)搬移，輸入?yún)?shù)有SRAM地址、操作類型、數(shù)據(jù)長(zhǎng)度等信息。
2．8 快速查找緩沖模塊
    為了提高散列表的查找效率，使用FPGA構(gòu)建小容量的CAM，CAM表中存儲(chǔ)HASH值、關(guān)鍵字、表元地址及前一表元地址。主控制器在生成表元查找請(qǐng)求時(shí)，使用CAM進(jìn)行查找，如果CAM查找成功則放棄表元查找，否則在表元查找成功后，把新的表元HASH值、關(guān)鍵字、表元地址等信息寫入CAM表項(xiàng)。
    CAM表采用簡(jiǎn)單的循環(huán)更換方式作為表元替換策略，具有簡(jiǎn)單高效的特點(diǎn)，但并不排除某些特定應(yīng)用命中率不高的問(wèn)題。FPGA邏輯實(shí)現(xiàn)過(guò)程中，保證CAM表中沒(méi)有兩個(gè)HASH值相同的表項(xiàng)。
2．9 存儲(chǔ)訪問(wèn)仲裁器
    存儲(chǔ)訪問(wèn)仲裁器采用Wishbone接口方式，可處理空閑緩沖區(qū)管理、表元查找、表元添加、表元?jiǎng)h除、數(shù)據(jù)輸入／輸出等五個(gè)模塊的SRAM訪問(wèn)請(qǐng)求信號(hào)，仲裁器采用輪詢方式處理各個(gè)模塊的請(qǐng)求信號(hào)，建立與SRAM接口控制器之間的連接。SRAM接口控制器采用Brust方式實(shí)現(xiàn)對(duì)SRAM芯片的讀／寫操作。

3 結(jié)論
    本設(shè)計(jì)方案通過(guò)模塊仿真和在Spartan-3EXC3S1600E芯片的實(shí)際測(cè)試，實(shí)驗(yàn)結(jié)果表明，基于FPGA和SRAM實(shí)現(xiàn)的分離鏈接散列表對(duì)于大數(shù)據(jù)量管理具有良好的應(yīng)用價(jià)值。但是，由于每個(gè)散列表應(yīng)用場(chǎng)景不同，如關(guān)鍵字長(zhǎng)度、管理數(shù)據(jù)量、FPGA資源等，因此具體實(shí)現(xiàn)過(guò)程中，需要根據(jù)實(shí)際情況對(duì)散列表各功能模塊進(jìn)行差異化處理。