Minimizing Cuckoo Hashing Insertion Time for Networking Applications in FPGAs

Abstract

Cuckoo Hashing is a well-known scheme for maintaining a hash-based data structure with worst-case constant search time. The search can be easily pipelined in FPGAs to obtain a response every clock cycle. However, inserting new elements may require multiple iterations to reallocate elements due to collisions, a challenge that intensifies with increasing table occupancy (load). Here, we pursue an efficient implementation of Cuckoo Hashing in FPGAs that exploits the inherent parallel processing capabilities of the technology to minimize the insertion time and enhance the performance of real-time applications like communications networks. Our analysis shows that the candidate implementation alternatives can be grouped into four different categories, considering the number of iterations required to perform new element insertions relative to the hash table’s load. Within each category, the performance is similar, providing flexibility for implementation. Among these methods, one exhibits the best results under all load conditions, without incurring a large complexity penalty, reducing the number of iterations for the insertion by more than 60% for loads beyond 95% compared to the most recent works. A Cuckoo Hashing architecture for networking applications is presented and used to evaluate and verify all insertion methods through hardware evaluation. Our implementation improves on existing architectures by at least 0.2 operations per clock cycle.