FASTHash: FPGA-Based High Throughput Parallel Hash Table
FASTHash: FPGA-Based High Throughput Parallel Hash Table
复制标题
DOI：
10.1007/978-3-030-50743-5_1
复制
发表时间：
2020-05-22
期刊：
影响因子：
--
通讯作者：
Prasanna VK
中科院分区：
文献类型：
--
作者：
Yang Y;Kuppannagari SR;Srivastava A;Kannan R;Prasanna VK
哈希表是一种基本的数据结构，可提供有效的数据存储和访问权限。 Fasthash，使用FPGA ON-CHIP SRAM的“真正”高吞吐量平行表实现。我们设计中的并行性是独立的，使我们可以通过P处理引擎（PES）在我们的最坏情况下通过P处理引擎（PES）支持P平行查询（）。 CHIP SRAM和无冲突并发插入。由于宽松的事件一致性，我们的设计量（真正的负面搜索，重复的插入）。支持吞吐量高达5.3.6亿秒，PES的静态哈希运行量为335 MHz，每秒运行4.48亿次操作，PES运行280 MHz用于动态哈希，它们的表现分别超过5.7倍和8.7倍。
Hash table is a fundamental data structure that provides efficient data store and access. It is a key component in AI applications which rely on building a model of the environment using observations and performing lookups on the model for newer observations. In this work, we develop FASTHash, a “truly” high throughput parallel hash table implementation using FPGA on-chip SRAM. Contrary to state-of-the-art hash table implementations on CPU, GPU, and FPGA, the parallelism in our design is data independent, allowing us to support p parallel queries () per clock cycle via p processing engines (PEs) in the worst case. Our novel data organization and query flow techniques allow full utilization of abundant low latency on-chip SRAM and enable conflict free concurrent insertions. Our hash table ensures relaxed eventual consistency - inserts from a PE are visible to all PEs with some latency. We provide theoretical worst case bound on the number of erroneous queries (true negative search, duplicate inserts) due to relaxed eventual consistency. We customize our design to implement both static and dynamic hash tables on state-of-the-art FPGA devices. Our implementations are scalable to 16 PEs and support throughput as high as 5360 million operations per second with PEs running at 335 MHz for static hashing and 4480 million operations per second with PEs running at 280 MHz for dynamic hashing. They outperform state-of-the-art implementations by 5.7x and 8.7x respectively.