Concurrency without Locking in Parallel Hash Structures used for Data Processing

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.

Authors:

• Ákos Dudás
• Sándor Juhász

Keywords:

• Lock-free synchronization
• mutual exclusion
• parallel hash tables
• parallel performance

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.