멀티코어 CPU를 위한 최신 해싱 방법들의 성능분석 = Performance Analysis of Modern Hashing Techniques for Multi-core CPUs

국문 초록 (Abstract)

해시테이블은 키 값으로 연관된 메모리를 매핑하는 방식으로 구현하는 기본적인 데이터 구조이다. O(1)의 매우 빠른 매핑작업으로 인해, 데이터베이스, 바이오인포매틱스, 그리고 분산 컴퓨팅등 다양한 분야에서 사용되고 있다. 한편, CPU의 마이크로 아키텍쳐 디자인의 패러다임이 빠른 하나의 코어를 사용하는 것에서 여러 개의 느린 다중코어를 사용하는 것으로 변하고 있다. 이러한 최신의 컴퓨터 구조의 성능을 최대한 이용하기 위해서 병렬처리방법은 그 어느 때보다 중요해졌다. 본 논문은 두 가지 잘 알려진 해싱 방법인 선형 해싱과 체인 해싱을 구현하였고 또한 최신 해싱 방법인 쿠쿠 해싱을 구현하여 세 가지 해싱 방법을 인텔 Nehalem 마이크로 아키텍쳐의 32개의 코어를 사용한 환경에서 성능을 분석하였다. 특히 compare-and-swap (CAS) 명령어의 락-프리(lock-free) 데이터 구조와 버킷-레벨(bucket-level) 락 데이터 구조 등의 가장 앞선 기술들을 사용하여 해시 방법들을 구현했다. 본 저자들이 아는 범위에서 본 논문은 위의 세 가지 해싱 방법들을 동일한 구현 프레임워크 하에서 최선의 성능을 발휘하도록 구현하고, 동일한 실험환경에서 성능분석을 한 최초의 논문이다. 223의 데이터(즉, 약 8백만) key-value 쌍을 사용한 실험 결과에서 락 프리 선형 해싱이 삽입 연산에서 가장 좋은 성능을 보였고, 락 프리 체인 해싱이 검색연산에서 가장 좋은 성능을 보였다. 또한, 실험을 통해, 쿠쿠 해싱이 해당 논문 저자들의 주장만큼 효율적인 것은 아니라는 것을 보였다.

다국어 초록 (Multilingual 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 2<SUP>23</SUP> (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.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 구현방법
• 4. 성능측정
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 "Valgrind: an open-source memory debugger for x86-GNU/Linux"

2 Herlihy, M., "The Art of Multiprocessor Programming" Morgan Kaufmann 2008

3 Knuth, E., "The Art of Computer Programming Volume 3: Sorting and Searching" Addison-Wesley Professional 1998

4 Shalev, O., "Split-Ordered Lists, Lock-Free Extensible Hash Tables" 53 (53): 379-405, 2006

5 Micahel, M., "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" 267-275, 1996

6 "PVS Language Reference"

7 Dietzfelbinger, M., "On risks of using cuckoo hashing with simple universal hash classes" 795-804, 2009

8 Purcell, C., "Non-blocking Hashtables with Open Addressing" 3724 : 108-121, 2005

9 Stivala, A., "Lock-free Parallel Dynamic Programming" 70 (70): 839-848, 2010

10 Gao, H., "Lock- free dynamic hash tables with open addressing" 18 (18): 21-42, 2005

11 Litwin, W., "Linear hashing: a new tool for file and table addressing" 212-233, 1980

12 IBM, "IBM System/370 Extended Architecture: Principles of Operation"

13 Stone, S., "High Performance Computer Architecture" Addison-Wesley Professional 1987

14 Michael, M., "Hazard pointers: Safe memory reclamation for lock-free objects" 15 (15): 2004

15 Fagin, R., "Extendible Hashing-A Fast Access Method for Dynamic Files" 4 (4): 315-344, 1979

16 Pagh, R., "Cuckoo hashing" 51 (51): 122-144, 2004

17 Ferdman, M., "Cuckoo directory: A scalable directory for many-core systems" 169-180, 2011

18 Michael, M., "CAS-Based Lock-Free Algorithm for Shared Deques" 651-660, 2003

19 Kutzelnigg, Reinhard, "An Improved Version of Cuckoo Hashing: Average Case Analysis of Construction Cost and Search Operations" 3 (3): 47-60, 2010

20 Frieze, Alan., "An Analysis of Random-Walk Cuckoo Hashing" 40 (40): 291-308, 2011

21 Drmota, M., "A precise analysis of Cuckoo hashing" 8 (8): 2012

22 Kutzelnigg, Reinhard, "A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r" 12 (12): 81-, 2010

23 Erlingsson, Ú., "A cool and practical alternative to traditional hash tables" 2006

24 Porat, E., "A Cuckoo Hashing Variant with Improved Memory Utilization and Insertion Time" 347-356, 2012