Cited time in webofscience Cited time in scopus

Enhanced chained and Cuckoo hashing methods for multi-core CPUs

Title
Enhanced chained and Cuckoo hashing methods for multi-core CPUs
Author(s)
Kim, EuihyeokKim, Min-Soo
Issued Date
2014-09
Citation
Cluster Computing: the Journal of Networks Software Tools and Applications, v.17, no.3, pp.665 - 680
Type
Article
Author Keywords
Linear hashingChained hashingCuckoo hashingHopscotch hashingLock-freeCache line
ISSN
1386-7857
Abstract
A hash table is a fundamental data structure implementing an associative memory that maps a key to its associative value. Besides, the paradigm of micro-architecture design of CPUs is shifting away from faster uniprocessors toward slower chip multiprocessors. In this paper, we propose enhanced chained hashing and Cuckoo hashing methods for modern computers having a lot of CPU cores with exploiting CPU cache line and hardware level lock-free operations. The proposed methods outperform the existing methods in most cases and are very scalable in terms of the number of CPU cores. In addition, their performances do not degrade much even with a high fill factor (e.g., 90 %). Through extensive experiments using Intel 32-core machine, we have shown our proposed methods improve performance compared with the state-of-the-art version of the four exiting major hashing methods of linear, chained, Cuckoo, and Hopscotch. © 2014 Springer Science+Business Media New York.
URI
http://hdl.handle.net/20.500.11750/3051
DOI
10.1007/s10586-013-0343-y
Publisher
Springer
Files in This Item:

There are no files associated with this item.

Appears in Collections:
Department of Electrical Engineering and Computer Science InfoLab 1. Journal Articles

qrcode

  • twitter
  • facebook
  • mendeley

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE