Parallel d-Pipeline: A Cuckoo Hashing Implementation for Increased Throughput Articles uri icon

publication date

  • January 2016

start page

  • 326

end page

  • 331

issue

  • 1

volume

  • 65

International Standard Serial Number (ISSN)

  • 0018-9340

Electronic International Standard Serial Number (EISSN)

  • 1557-9956

abstract

  • Cuckoo hashing has proven to be an efficient option to implement exact matching in networking applications. It provides good memory utilization and deterministic worst case access time. The continuous increase in speed and complexity of networking devices creates a need for higher throughput exact matching in many applications. In this paper, a new Cuckoo hashing implementation named parallel d-pipeline is proposed to increase throughput. The scheme presented is targeted to implementations in which the tables are accessed in parallel. A parallel implementation increases the throughput and therefore is well suited to high speed applications. Parallel schemes are common for ASIC/FPGA implementations in which the tables are stored in several embedded memories. Using the proposed technique, the throughput can be significantly increased with gains that in practical scenarios can reach 60 percent compared to existing parallel implementations. The new scheme has been evaluated using a case study and detailed results for performance and implementation costs are reported.

keywords

  • high speed packet processing; cuckoo hashing; parallel pipelined; packet switching; throughput; field programmable gate arrays; computer architecture; radiation detectors