Cited 0 time in webofscience Cited 0 time in scopus

Performance Analysis of Hashing Techniques for Multi-core CPUs

Performance Analysis of Hashing Techniques for Multi-core CPUs
Translated Title
멀티코어 CPU를 위한 최신 해싱방법들의 성능분석
Kim, Eui Hyeok
DGIST Authors
Kim, Eui Hyeok; Kim, Min Soo; Moon, Sang Jun
Kim, Min Soo
Moon, Sang Jun
Issue Date
Available Date
Degree Date
2013. 2
linear hashingchained hashingcuckoo hashinghopscotch hashingparallel programming선형 해싱체인 해싱쿠쿠 해싱홉스카치해싱병렬프로그래밍
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 four cache-conscious hashing methods, linear hashing and chained hashing, and also, a modern hashing methods, cuckoo hashing and 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 four 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 four hashing methods, and lock-free chained hashing is the best for lookup operation. Hopscotch hashing shows the second best per-formance of lookup operation. However, cuckoo hashing and hopscotch hash size is much bigger than other hash table size. Through experiments, we have found that the cuckoo hashing and hopscotch hashing are relatively not efficient than other hash methods. ⓒ 2013 DGIST
Table Of Contents
Ⅰ. INTRODUCTION 1 -- Ⅱ. Related work 3 -- 2.1 linear hashing 3 -- 2.2 chained hashing 3 -- 2.3 cuckoo hashing 4 -- 2.4 hopscotch hashing 6 -- Ⅲ. Implementation 6 -- 3.1 Lock-free linear hashing 6 -- 3.2 Lock-free chained hashing 8 -- 3.3 Refinable lock-based cuckoo hashing 10 -- 3.3 Refinable lock-based hopscotch hashing 16 -- Ⅳ. Performance evaluation 18 -- 4.1 Experimental data and experiment environment 18 -- 4.2 Insert operation performance 18 -- 4.3 Lookup operation performance 20 -- 4.4 Hash table size 21 -- 4.5 The performance of table-level lock-based hash methods 22 -- 4.6 Detailed performance analysis 24 -- Ⅴ. Conclusions 26
Information and Communication Engineering
Related Researcher
  • Author Kim, Min-Soo InfoLab
  • Research Interests Big Data Systems; Big Data Mining & Machine Learning; Big Data Bioinformatics; 데이터 마이닝 및 빅데이터 분석; 바이오인포메틱스 및 뉴로인포메틱스; 뇌-기계 인터페이스(BMI)
Department of Information and Communication EngineeringThesesMaster

qrcode mendeley

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