Cited 0 time in webofscience Cited 1 time in scopus

Performance analysis of cache-conscious hashing techniques for multi-core CPUs

Title
Performance analysis of cache-conscious hashing techniques for multi-core CPUs
Authors
Kim, EuihyeokKim, Min-Soo
DGIST Authors
Kim, Euihyeok; Kim, Min-Soo
Issue Date
2013
Citation
International Journal of Control and Automation, 6(2), 121-134
Type
Article
Article Type
Article
Keywords
Associative ProcessingBioinformaticsCache FriendlyChained HashingCompare-and-SwapCompare-and-SwapsComputer ArchitectureData StructuresHash TableHopscotch HashingIntel MicroarchitectureLinear HashingLock-Free Hash TablesMicro ArchitecturesMicroprocessor ChipsMulti-CoresMulticoresParallel ProgrammingProgram ProcessorsRefinable Hash TablesSystems Analysis
ISSN
2005-4297
Abstract
A hash table is a fundamental data structure implementing an associative memory that maps a key to its associative value. Due to its very fast mapping operation of O(1), it has been widely used in various areas such as databases, bioinformatics, and distributed computing. Besides, the paradigm of micro-architecture design of CPUs is shifting away from faster uniprocessors toward slower chip multiprocessors. In order to fully exploit the performance of such modern computer architectures, the data structures and algorithms considering parallelism become more important than ever. This paper implements three cache-conscious hashing methods, linear hashing and chained hashing, and also, a modern hashing method, hopscotch hashing, and analyzes their performance under Intel 32-core CPU of Nehalem microarchitecture. We implement each hashing method using state-of-the-art techniques such as lock-free data structures, especially based on compare-and-swap (CAS) operations, and refinable data structures. To the best of our knowledge, the work done by this paper is the first work analyzing the performance of three all hashing methods under the same implementation framework. Experimental results using data of 223 (i.e., about eight millions) key-value pairs shows that lock-free linear hashing is the best for insert operation among three hashing methods, and lock-free chained hashing is the best for lookup operation. Hopscotch hashing shows the second best performance of lookup operation. However, hopscotch hash table size is much bigger than other hash table size. Through experiments, we have found that the hopscotch hashing is relatively not efficient than other hash methods.
URI
http://hdl.handle.net/20.500.11750/2279
Publisher
Security Engineering Research Support Center
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