Á¤º¸°úÇÐȸ ³í¹®Áö 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) |
¼±Çü ÇؽÌ
üÀÎ ÇؽÌ
ÄíÄí ÇؽÌ
¶ô ÇÁ¸®
¸ÖƼÄÚ¾î
ij½Ã ÀνÄ
linear hashing
chained hashing
cuckoo hashing
lock-free
multi-core
cache conscious
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|