一种散列表的FPGA设计与实现

摘要：文章在简要介绍散列表工作原理的基础上，提出了一种分离链接散列表的FPGA实现方案，并对方案涉及的各功能模块实现进行了详细阐述。
关键词：散列表；FPGA；Wishbone总线；SRAM

0 引言
    在软硬件开发过程中，经常需要通过关键字对数据信息进行存储、查找、删除等操作，从而实现数据信息的管理。散列表能够以常数平均时间实现插入、删除和查找，因此在实现过程中得到广泛应用。本文基于FPGA设计并实现了一种分离链接法解决散列表，利用快速查找缓冲区提高查询效率，采用空闲存储区管理模块实现存储空间的高效分配及释放。

1 工作原理
    散列表根据设定的散列函数Hash(Key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址区间上，并以关键字在地址集中的“像”作为记录在表中的存储位置。散列表的实现主要研究两个问题：散列函数的选取和冲突解决的办法。
1．1 散列函数选取
    一个好的散列函数可以使关键字尽量随机均匀地分布在散列表中，降低冲突发生的概率，提高散列表查找的效率。理想的散列函数对于关键字集合中的任一个关键字，经散列后映象到地址集合中任何一个地址的概率是相等的。考虑到FPGA实现的效率及复杂度，本文采用了CRC算法作为散列函数，实现关键字到散列表地址的映射。
1．2 冲突解决方法
    散列表解决冲突的方法主要有开放地址法和分离链接法。在开放定址散列算法系统中，如果有冲突发生，那么就要尝试选择另外的单元，直到找出空的单元位置。在分离链接散列算法系统，通过给新单元分配地址空间，建立链表来解决冲突。因为所有的数据都要置于表内，所以开放定址散列法所需要的表要比分离链接散列用表大。一般说来，对开放定址散列算法来说，装填因子应低于0．5。

    本文采用分离链接法解决散列表存在的冲突，建立如图1所示散列表存储结构，每个链表首地址存放在FPGA内部的连续RAM中，表元存放在SRAM芯片中。每个表元主要包含关键字(Key)、数据(Data)和下一表元地址(Next)，由于关键字和下一表元地址字段访问频繁，在FPGA实现过程中把这两个字段置于每个表元的头部，尽量在一次SRAM的Brust读／写操作内完成。

2 FPGA实现
    如图2所示，分离链接散列表采用Wishbone总线标准接口与外部组件交互，采用接口控制器实现Wishbone总线管理，采用主控制器生成表元查找、表元添加、表元删除等模块的控制信号，采用存储访问仲裁器实现各模块SRAM访问的分时复用，采用基于内部CAM的快速查找缓冲模块实现表元地址的快速查找。

2．1 接口控制器
    接口控制器作为本模块与FPGA内部其它功能模块之间交互的桥梁通道，采用Wishbone总线接口标准。Wishbone总线是由Silicore公司开发的完全免费的片上总线规范，具有灵活、“轻量级”的优点。Wishone采用主／从设备架构，本模块工作于从设备模式，支持“单次读／写”和“块读／写”操作。接口控制器实现以下功能：
    (1)根据地址信息的不同，调用不同的功能逻辑处理输入数据，并返回应答；
    (2)把关键字(Key)送到Hash运算模块进行运算；
    (3)把命令类型、Hash值、关键字按格式送入命令输入缓冲区；
    (4)把待写入SRAM的数据送入数据输入缓冲区；
    (5)处理状态读取命令，返回模块当前状态；
    (6)处理数据读取命令，从缓冲区输出数据、读取数据并输出。
2．2 主控制器
    主控制器是散列表FPGA实现的核心模块，循环读取命令输入缓冲区中的命令数据，并根据命令类型生成表元查找、表元添加、表元删除、空闲表元申请、空闲表元释放及输入／输出等请求信号。

    (1)主控制器在复位信号失效后，给空闲存储区管理模块发送初始化请求，在初始化完成后进入空闲状态，等待命令输入缓冲区送入的命令数据；
    (2)主控制器在收到查找命令后，给表元查找模块发送请求，匹配成功则根据命令内容给数据输入／输出模块发送请求，完成数据读取和写入，否则完成本次操作返回应答；
    (3)主控制器在收到添加命令后，首先查找是否存在关键字匹配表元，匹配失败则向缓冲区管理模块发送请求获取空闲表元，成功后根据命令内容给数据输入／输出模块发送请求，完成数据读取和写入。
    (4)主控制器在收到删除命令后，首先查找是否存在关键字匹配表元，匹配成功则向表元删除模块发送请求，并在删除成功后释放缓冲区到空闲缓冲区池。
2．3 空闲存储区管理
    为了实现存储区的快速分配和有效管理，空闲存储区管理模块根据用户设定的存储区大小、分块大小，把缓冲区分块并组织成链表，并根据主控制器请求完成表元的删除和添加。
    (1)本模块在接到复位信号后进入空闲状态；
    (2)接收到空闲存储区初始化请求后，修改SRAM中每一表元的头部数据建立链表，存储链表首地址；
    (3)接收到获取缓冲区请求后，直接返回链表首地址，并根据链表首地址访问SRAM中的表元头部数据，得到下一表元地址并作为新的链表首地址进行存储；
    (4)接收到释放缓冲区请求后，把链表首地址写入到待释放表元的下一表元地址字段，把链表首地址修改为待释放表元地址。
2．4 表元查找
    表元查找模块在接到复位、放弃请求信号后，进入空闲状态，等待主控制器发起查找请求。在收到查找请求后根据输入的链表首地址从SRAM读取第一块数据区的头部数据(含关键字、下一表元地址)，在访问成功后进行关键字比较，成功则查找结束并返回当前表元地址和前一表元地址，否则根据下一表元地址循环查找直至最后一个表元，状态转换如图4所示。表元删除模块需要使用当前表元地址及前一表元地址。

2．5 表元添加
    表元添加模块在接到复位信号后，进入空闲状态，等待主控制器发起表元添加请求。在收到添加请求后把链表首地址添加到新表元头部数据的下一表元地址字段，修改链表首地址为新添加表元地址。
2．6 表元删除
    表元删除模块在接到复位信号后，进入空闲状态，等待主控制器发起表元删除请求。在收到待删除表元地址及其前一表元地址后，读取待删除表元头部数据，获取下一表元地址(A-NEXT)字段，并写入前一表元的下一表元地址(BA-NEXT)字段，完成表元删除。

2．7 数据输入／输出
    数据输入／输出模块主要完成输入缓冲区、输出缓冲区与SRAM之间的数据搬移，输入参数有SRAM地址、操作类型、数据长度等信息。
2．8 快速查找缓冲模块
    为了提高散列表的查找效率，使用FPGA构建小容量的CAM，CAM表中存储HASH值、关键字、表元地址及前一表元地址。主控制器在生成表元查找请求时，使用CAM进行查找，如果CAM查找成功则放弃表元查找，否则在表元查找成功后，把新的表元HASH值、关键字、表元地址等信息写入CAM表项。
    CAM表采用简单的循环更换方式作为表元替换策略，具有简单高效的特点，但并不排除某些特定应用命中率不高的问题。FPGA逻辑实现过程中，保证CAM表中没有两个HASH值相同的表项。
2．9 存储访问仲裁器
    存储访问仲裁器采用Wishbone接口方式，可处理空闲缓冲区管理、表元查找、表元添加、表元删除、数据输入／输出等五个模块的SRAM访问请求信号，仲裁器采用轮询方式处理各个模块的请求信号，建立与SRAM接口控制器之间的连接。SRAM接口控制器采用Brust方式实现对SRAM芯片的读／写操作。

3 结论
    本设计方案通过模块仿真和在Spartan-3EXC3S1600E芯片的实际测试，实验结果表明，基于FPGA和SRAM实现的分离链接散列表对于大数据量管理具有良好的应用价值。但是，由于每个散列表应用场景不同，如关键字长度、管理数据量、FPGA资源等，因此具体实现过程中，需要根据实际情况对散列表各功能模块进行差异化处理。