|
- UID
- 1029342
- 性别
- 男
|
在软硬件开发过程中，经常需要通过关键字对数据信息进行存储、查找、删除等操作，从而实现数据信息的管理。散列表能够以常数平均时间实现插入、删除和查找，因此在实现过程中得到广泛应用。本文基于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)主控制器在收到删除命令后，首先查找是否存在关键字匹配表元，匹配成功则向表元删除模块发送请求，并在删除成功后释放缓冲区到空闲缓冲区池。 |
|
