A High Throughput Parallel Hash Table Accelerator on HBM-enabled FPGAs
Yang Yang, Sanmukh R. Kuppannagari, Viktor K. Prasanna · 2020
Hash table is a key component in a number of AI algorithms such as Graph Convolutional Neural Networks, Approximate Nearest Neighbor Search, Bag-of-Words based Text Mining algorithms, etc. Efficient implementation of hash tables is needed for a wide range of AI applications. High bandwidth memory (HBM), which provides significantly higher memory bandwidth than traditional DDR, has recently gained popularity. In this work, we propose a high throughput parallel hash table targeting HBM-enabled FPGAs. Our design is tailored for HBM architecture, allowing flexible and balanced mapping between processing engines and HBM channels at design time given query distribution and hash table properties (key/value length, collision handling, and hash table size). We further develop a novel data organization and query flow which enable our accelerator to scale up to 16 processing engines (PEs). The proposed design supports parallel search, insert, and delete queries. Experimental results demonstrate that our hash table accelerator can achieve up to 3575 million operations per second (MOPS) for search-only queries and up to 1470 MOPS for 50%/50% distributed search/update queries on HBM-enabled FPGAs. It achieves better throughput than the state-of-the-art GPU and FPGA designs by up to 3.5× and 3.2× respectively.