|
- UID
- 1029342
- 性别
- 男
|
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资源等，因此具体实现过程中，需要根据实际情况对散列表各功能模块进行差异化处理。 |
|
