Cited 0 time in webofscience Cited 1 time in scopus

Enhanced chained and Cuckoo hashing methods for multi-core CPUs

Title
Enhanced chained and Cuckoo hashing methods for multi-core CPUs
Authors
Kim, E[Kim, Euihyeok]Kim, MS[Kim, Min-Soo]
DGIST Authors
Kim, E[Kim, Euihyeok]; Kim, MS[Kim, Min-Soo]
Issue Date
2014-09
Citation
Cluster Computing: the Journal of Networks Software Tools and Applications, 17(3), 665-680
Type
Article
Article Type
Article
Keywords
Associative ProcessingCache LineCache MemoryChained HashingCuckoo HashingHopscotch HashingLinear HashingLock-FreeLocks (Fasteners)Microprocessor ChipsProgram Processors
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
Related Researcher
Files:
There are no files associated with this item.
Collection:
Information and Communication EngineeringETC1. Journal Articles


qrcode mendeley

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

BROWSE