Concurrency without Locking in Parallel Hash Structures used for Data Processing

Authors: Ákos Dudás, Sándor Juhász

Abstract:

Various mechanisms providing mutual exclusion and thread synchronization can be used to support parallel processing within a single computer. Instead of using locks, semaphores, barriers or other traditional approaches in this paper we focus on alternative ways for making better use of modern multithreaded architectures and preparing hash tables for concurrent accesses. Hash structures will be used to demonstrate and compare two entirely different approaches (rule based cooperation and hardware synchronization support) to an efficient parallel implementation using traditional locks. Comparison includes implementation details, performance ranking and scalability issues. We aim at understanding the effects the parallelization schemes have on the execution environment with special focus on the memory system and memory access characteristics.

Keywords: Lock-free synchronization, mutual exclusion, parallel hash tables, parallel performance

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1055206

References:

[1] S. Ansari, R. Kohavi, L. Mason, and Z. Zheng, "Integrating ECommerce and Data Mining: Architecture and Challenges," in IEEE International Conference on Data Mining, 2001, pp. 27-34.
[2] S. Juhász, and R. Iváncsy,"Tracking Activity of Real Individuals in Web Logs,"International Journal of Computer Science, Vol. 2, No. 3, pp. 172-177, 2007.
[3] W. Litwin,"Linear hashing: A new tool for file and table addressing," In Proceedings of the Sixth International Conference on Very Large Data Bases, New York, pp. 212-223, 1980.
[4] M. Mitzenmacher,"Good Hash Tables & Multiple Hash Functions," Dr. Dobbs Journal, No. 336, pp. 28-32, May 2002.
[5] G. L. Heileman and W. Luo,"How caching affects hashing," In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, Vancouver, Canada, pp. 141-154, 2005.
[6] S. Juhász and Á. Dudás, "Optimising Large Hash Tables for Lookup Performance," In proceedings of the IADIS International Conference Informatics 2008, Amsterdam, The Netherlands, pp. 107-114, 2008.
[7] M. Greenwald, "Two-handed emulation: How to build non-blocking implementations of complex data-structures using DCAS," In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing. ACM, New York, pp. 260-269, 2002.
[8] D. Lea, "Hash table util.concurrent.ConcurrentHashMap, revision 1.3, in JSR-166, the proposed Java Concurrency Package", 2003, http://gee.cs.oswego.edu/cgibin/ viewcvs.cgi/jsr166/src/main/java/util/concurrent/
[9] O. Shalev and N. Shavit, "Split-ordered lists: Lock-free extensible hash tables,"Journal of the ACM 53(3): pp. 379-405, 2006.
[10] A. Sachedina, M. A. Huras and K. K. Romanufa,"Resizable cache sensitive hash table," US Patent number: 7085911, 2003.
[11] P.-A. Larson, M. R. Krishnan,and G. V. Reilly, "Scaleable hash table for shared-memory multiprocessor system," US Patent number: 6578131, 2003.
[12] M. M. Michael, "High performance dynamic lock-free hash tables and list-based sets," In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, pp. 73-82, 2002.