A High Throughput Parallel Hash Table on FPGA using XOR-based Memory
A High Throughput Parallel Hash Table on FPGA using XOR-based Memory
复制标题
DOI：
10.1109/hpec43674.2020.9286199
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Ruizhi Zhang;Sasindu Wijeratne;Yang Yang-Yang;S. Kuppannagari;V. Prasanna
中科院分区：
文献类型：
--
作者：
Ruizhi Zhang;Sasindu Wijeratne;Yang Yang-Yang;S. Kuppannagari;V. Prasanna
哈希表是用于快速搜索和检索数据的基本数据结构。它是复杂图分析和AI/ML应用程序中的关键组件。最新的并行哈希表实现要么做出一些简化的假设，例如仅支持哈希表操作的子集，要么采用优化的优化，从而导致高度数据依赖性的性能，并且在最坏的情况下可以类似于顺序实现。相比之下，在这项工作中，我们开发了一个动态哈希表，该表支持所有哈希表查询 - 搜索，插入，删除，更新，同时允许我们每个时钟周期支持$ p $ PURALLALT查询（P> 1）。在最坏的情况下，加工引擎（PES），即性能不可知。我们通过在FPGA上实现基于XOR的新型多端口块记忆来实现这一目标。此外，如果事先知道搜索与插入/update/删除查询的比率，我们开发了一种技术来优化哈希表的内存需求。我们在最先进的FPGA设备上实施设计。我们的设计可扩展到16 pes，并支持高达5926 MOP的吞吐量。它与最新的哈希表设计 - Fasthash的吞吐量相匹配，Fasthash仅支持搜索和插入操作。与支持相同操作的最佳FPGA设计相比，我们的哈希表达到了高达12.3 X的速度。
Hash table is a fundamental data structure for quick search and retrieval of data. It is a key component in complex graph analytics and AI/ML applications. State-of-the-art parallel hash table implementations either make some simplifying assumptions such as supporting only a subset of hash table operations or employ optimizations that lead to performance that is highly data dependent and in the worst case can be similar to a sequential implementation. In contrast, in this work we develop a dynamic hash table that supports all the hash table queries - search, insert, delete, update, while allowing us to support $p$ parallel queries (p > 1) per clock cycle via $p$ processing engines (PEs) in the worst case i.e. the performance is data agnostic. We achieve this by implementing novel XOR based multi-ported block memories on FPGAs. Additionally, we develop a technique to optimize the memory requirement of the hash table if the ratio of search to insert/update/delete queries is known beforehand. We implement our design on state-of-the-art FPGA devices. Our design is scalable to 16 PEs and supports throughput up to 5926 MOPS. It matches the throughput of the state-of-the-art hash table design - FASTHash, which only supports search and insert operations. Comparing with the best FPGA design that supports the same set of operations, our hash table achieves up to 12.3 x speedup.