nach oben

Cluster Computing

Erschienen in:

01.09.2014

Enhanced chained and Cuckoo hashing methods for multi-core CPUs

verfasst von: Euihyeok Kim, Min-Soo Kim

Erschienen in: Cluster Computing | Ausgabe 3/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A hash table is a fundamental data structure implementing an associative memory that maps a key to its associative value. Besides, the paradigm of micro-architecture design of CPUs is shifting away from faster uniprocessors toward slower chip multiprocessors. In this paper, we propose enhanced chained hashing and Cuckoo hashing methods for modern computers having a lot of CPU cores with exploiting CPU cache line and hardware level lock-free operations. The proposed methods outperform the existing methods in most cases and are very scalable in terms of the number of CPU cores. In addition, their performances do not degrade much even with a high fill factor (e.g., 90 %). Through extensive experiments using Intel 32-core machine, we have shown our proposed methods improve performance compared with the state-of-the-art version of the four exiting major hashing methods of linear, chained, Cuckoo, and Hopscotch.

Vorheriger Artikel Implementation of load management application system using smart grid privacy policy in energy management service environment

Nächster Artikel Distributed Electronic Commerce cluster for small enterprise

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ijtihadie, R., Hidayanto, B., Affandi, A., Chisaki, Y., Usagawa, T.: Dynamic content synchronization between learning management systems over limited bandwidth network. HCIS Hum. Cent. Comput. Inf. Sci. 2(1), 1–16 (2012)CrossRef

Chen, C.-W., Tsai, Y.-R., Shiuh-Jeng, W.: Cost-saving key agreement via secret sharing in two-party communication systems. JoC J. Convergence 3(4), 29–36 (2012)

Tsai, C.-L., Chen, C.-J., Zhuang, D.-J.: Trusted M-banking verification scheme based on a combination of OTP and biometrics. JoC J. Convergence 3(3), 23–30 (2012)

Agarwal, S., Rungta, A., Padmavathy, R., Shankar, M., Rajan, N.: An improved fast and secure hash slgorithm. JIPS J. Inf. Process. Syst. 8(1), 119–132 (2012)

Litwin, W.: Linear hashing: a new tool for file and table addressing. In: Proceedings of the 6th International Conference on Very Large Data, Bases, pp. 212–223 (1980)

Fagin, R., Nievergelt, J., Pippenger, N., Strong, H.R.: Extendible hashing: a fast access method for dynamic files. ACM Trans. Datab. Syst. 4(3), 315–344 (1979). doi:10.1145/320083.320092 CrossRef

Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004)CrossRefMATHMathSciNet

Herlihy, M., Shavit, N., Tzafrir, M.: Hopscotch hashing. In: Taubenfeld, G. (ed.) Distributed Computing, LNCS, vol. 5218, pp. 350–364. Springer, Heidelberg (2008)

Gao, H., Groote, J.F., Hesselink, W.H.: Lock-free dynamic hash tables with open addressing. Distributed Comput. 18(1), 21–42 (2005)CrossRefMATH

10.

Owre, S., Shankar, N., Rushby, J.M., Stringer-Calvert, D.W.J.: PVS Language Reference (Version 2.4). Computer Science Laboratory, SRI International, Menlo Park, CA (2001)

11.

Dietzfelbinger, M., Schellbach, U.: On risks of using cuckoo hashing with simple universal hash classes. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 795–804 (2009)

12.

Kutzelnigg, R.: An improved version of cuckoo hashing: average case analysis of construction cost and search operations. Math. Comput. Sci. 3(1), 47–60 (2010)CrossRefMATHMathSciNet

13.

Kutzelnigg, R.: A further analysis of cuckoo hashing with a stash and random graphs of excess r. Discret. Math. Theor. Comput. Sci. 12(3), 81–102 (2010)MATHMathSciNet

14.

Ferdman, M., Lotfi-Kamran, P., Balet, K., Falsafi, B.: Cuckoo directory: A scalable directory for many-core systems. In: High Performance Computer Architecture (HPCA), 2011 IEEE 17th International Symposium, pp. 169–180 (2011)

15.

Frieze, A., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, LNCS, vol. 5687, pp. 490–503. Springer, Heidelberg (2009)

16.

Porat, E., Shalem, B.: A cuckoo hashing variant with improved memory utilization and insertion time. In: Data Compression Conference (DCC), pp. 347–356 (2012)

17.

Drmota, M., Kutzelnigg, R.: A precise analysis of cuckoo hashing. ACM Trans. Algorithms (TALG) 8(2), 11 (2012)MathSciNet

18.

Purcell, C., Harris, T.: Non-blocking hashtables with open addressing. In: Distributed Computing, pp. 108–121. Springer, (2005)

19.

Stivala, A., Stuckey, P.J., Garcia de la Banda, M., Hermenegildo, M., Wirth, A.: Lock-free parallel dynamic programming. J. Parallel Distributed Comput. 70(8), 839–848 (2010)CrossRefMATH

20.

Shalev, O., Shavit, N.: Split-ordered lists: lock-free extensible hash tables. J. ACM (JACM) 53(3), 379–405 (2006)CrossRefMathSciNet

21.

Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, New York (2012)

22.

DIMACS.: New York City Shortest Paths. 9th DIMACS Implementation Challenge. http://www.dis.uniroma1.it/challenge9 (2010). Accessed 14 June 2010

23.

Chilimbi, T.: Cache-Conscious Data Structures -Design and Implementation. Ph.D. thesis, University of Wisconsin-Madison (1999)

24.

Askitis, N.: Efficient Data Structures for Cache Architectures. Ph.D. thesis, RMIT University (2007)

25.

Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space efficient hash tables with worst case constant access time. In: Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 271–282 (2003)

26.

Pan, J., Manocha, D.: Fast GPU-based Locality Sensitive Hashing for K-Neares Neighbor Computation. In: ACM SIGSPATIAL, GIS, pp. 211–220 (2011)

27.

Valgrind: an open-source memory debugger for x86-GNU/Linux. http://valgrind.kde.org. Accessed 2 April 2013

Titel: Enhanced chained and Cuckoo hashing methods for multi-core CPUs
verfasst von: Euihyeok Kim
Min-Soo Kim
Publikationsdatum: 01.09.2014
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 3/2014
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-013-0343-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2014

PhishTackle—a web services architecture for anti-phishing

Bi-level optimization programming for the shipper-carrier network problem

FastMPJ: a scalable and efficient Java message-passing library

A smartphone based real-time daily activity monitoring system

Towards autonomic performance management of large scale data centers using interaction balance principle

Fault tolerance and QoS scheduling using CAN in mobile social cloud computing