High-Throughput Online Hash Table on FPGA
High-Throughput Online Hash Table on FPGA
复制标题
FPGA 上的高吞吐量在线哈希表
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
V. Prasanna
中科院分区：
文献类型：
--
作者：
Da Tong;Shijie Zhou;V. Prasanna
哈希表广泛应用于报文分类、流分类、重攻击检测等网络应用中。本文提出了一种在FPGA上实现高吞吐量在线哈希表的流水线架构。该架构支持对存储在片外存储器中的海量哈希表进行行速率的搜索、插入和删除操作。我们提出了两种哈希表访问方案：(1)第一种方案为每个哈希条目分配多个槽，以减少哈希冲突率；每个槽可以存储该哈希表项对应的哈希键；(2)第二种方案比第一种方案具有更高的哈希碰撞率，但对片外内存带宽的要求较低。两种方案都保证了在使用具有足够访问带宽的存储设备时的线速率处理。我们设计了一个特定于应用程序的数据转发单元来处理潜在的数据危害。我们的体系结构确保在处理任何并发操作序列时不需要延迟，同时容忍较大的外部内存访问延迟。在最先进的FPGA上，所提出的架构实现了66-85 Gbps的吞吐量，同时支持各种条目数量的哈希表，具有各种密钥大小，用于各种DRAM访问延迟。我们的设计在各种哈希表配置的吞吐量方面也显示出良好的可扩展性。
Hash tables are widely used in many network applications such as packet classification, traffic classification, and heavy hitter detection, etc. In this paper, we present a pipelined architecture for high throughput online hash table on FPGA. The proposed architecture supports search, insert, and delete operations at line rate for the massive hash table which is stored in off-chip memory. We propose two hash table access schemes: (1) the first scheme assigns each hash entry multiple slots to reduce the hash collision rate; each slot can store the corresponding hash key of the hash entry; (2) the second scheme has a higher hash collision rate but a lower off-chip memory bandwidth requirement than the first scheme. Both schemes guarantee the line rate processing when using the memory devices with sufficient access bandwidth. We design an application specific data forwarding unit to deal with the potential data hazards. Our architecture ensures that no stalling is required to process any sequence of concurrent operations while tolerating large external memory access latency. On a state-of-the-art FPGA, the proposed architecture achieves 66-85 Gbps throughput while supporting a hash table of various number of entries with various key sizes for various DRAM access latency. Our design also shows good scalability in terms of throughput for various hash table configurations.