Cited 0 time in webofscience Cited 0 time in scopus

Performance Analysis of Hashing Techniques for Multi-core CPUs

Title
Performance Analysis of Hashing Techniques for Multi-core CPUs
Translated Title
멀티코어 CPU를 위한 최신 해싱방법들의 성능분석
Authors
Kim, Eui Hyeok
DGIST Authors
Kim, Eui Hyeok; Kim, Min Soo; Moon, Sang Jun
Advisor(s)
Kim, Min Soo
Co-Advisor(s)
Moon, Sang Jun
Issue Date
2013
Available Date
2016-05-18
Degree Date
2013. 2
Type
Thesis
Keywords
linear hashingchained hashingcuckoo hashinghopscotch hashingparallel programming선형 해싱체인 해싱쿠쿠 해싱홉스카치해싱병렬프로그래밍
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 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
URI
http://dgist.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000002262483
http://hdl.handle.net/20.500.11750/1323
DOI
10.22677/thesis.2262483
Degree
Master
Department
Information and Communication Engineering
University
DGIST
Files:
Collection:
Information and Communication EngineeringThesesMaster


qrcode mendeley

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

BROWSE