정보과학회 논문지 D : 데이타베이스
Current Result Document : 3 / 4
| 한글제목(Korean Title) |
멀티코어 CPU를 위한 최신 해싱 방법들의 성능분석 |
| 영문제목(English Title) |
Performance Analysis of Modern Hashing Techniques for Multi-core CPUs |
| 저자(Author) |
김의혁
김민수
Euihyeok Kim
Min-Soo Kim
|
| 원문수록처(Citation) |
VOL 40 NO. 03 PP. 0189 ~ 0201 (2013. 06) |
한글내용
(Korean Abstract) |
해시테이블은 키 값으로 연관된 메모리를 매핑하는 방식으로 구현하는 기본적인 데이터 구조이다. O(1)의 매우 빠른 매핑작업으로 인해, 데이터베이스, 바이오인포매틱스, 그리고 분산 컴퓨팅등 다양한 분야에서 사용되고 있다. 한편, CPU의 마이크로 아키텍쳐 디자인의 패러다임이 빠른 하나의 코어를 사용하는 것에서 여러 개의 느린 다중코어를 사용하는 것으로 변하고 있다. 이러한 최신의 컴퓨터 구조의 성능을 최대한 이용하기 위해서 병렬처리방법은 그 어느 때보다 중요해졌다. 본 논문은 두 가지 잘 알려진 해싱 방법인 선형 해싱과 체인 해싱을 구현하였고 또한 최신 해싱 방법인 쿠쿠 해싱을 구현하여 세 가지 해싱 방법을 인텔 Nehalem 마이크로 아키텍쳐의 32개의 코어를 사용한 환경에서 성능을 분석하였다. 특히 compare-and-swap (CAS) 명령어의 락-프리(lock-free) 데이터 구조와 버킷-레벨(bucket-level) 락 데이터 구조 등의 가장 앞선 기술들을 사용하여 해시 방법들을 구현했다. 본 저자들이 아는 범위에서 본 논문은 위의 세 가지 해싱 방법들을 동일한 구현 프레임워크 하에서 최선의 성능을 발휘하도록 구현하고, 동일한 실험환경에서 성능분석을 한 최초의 논문이다. 223의 데이터(즉, 약 8백만) key-value 쌍을 사용한 실험 결과에서 락 프리 선형 해싱이 삽입 연산에서 가장 좋은 성능을 보였고, 락 프리 체인 해싱이 검색 연산에서 가장 좋은 성능을 보였다. 또한, 실험을 통해, 쿠쿠 해싱이 해당 논문 저자들의 주장만큼 효율적인 것은 아니라는 것을 보였다. |
영문내용
(English 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 two well-known hashing methods, linear hashing and chained hashing, and also, a modern hashing method, cuckoo 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 bucket-level 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. Through experiments, we also show that cuckoo hashing is not as efficient as the authors of cuckoo hashing claimed. |
| 키워드(Keyword) |
선형 해싱
체인 해싱
쿠쿠 해싱
락 프리
멀티코어
캐시 인식
linear hashing
chained hashing
cuckoo hashing
lock-free
multi-core
cache conscious
|
| 파일첨부 |
PDF 다운로드
|
