Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS

ABSTRACT

This paper partly addresses the question of whether, in principle, there is any point in adding richer hardware synchronization primitives when the existing set is "universal", and therefore sufficient to synchronize any data structure in a non-blocking manner. The context of this paper is the ongoing investigation of the utility of adding a DCAS instruction to modern processors to aid the design and performance of non-blocking algorithms. We add one more piece of evidence in support of this instruction.In particular, we demonstrate that DCAS is sufficient to enable a technique called "two-handed emulation" which yields efficient and understandable implementations of a class of data structures. We present a non-blocking implementation of a doubly-linked list to show the basic technique. We describe a non-blocking implementation of a dynamically resizable hash-table to illustrate how the technique is amenable to optimizations that improve performance and increase concurrency.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 2: Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Guy L. Steele, Jr., DCAS-based concurrent deques, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.137-146, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341817]
• 3: Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277678]
• 4: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 5: E. A. Brewer , C. N. Dellarocas , A. Colbrook , W. E. Weihl, PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: David Detlefs , Christine H. Flood , Alex Garthwaite , Paul Martin , Nir Shavit , Guy L. Steele, Jr., Even Better DCAS-Based Concurrent Deques, Proceedings of the 14th International Conference on Distributed Computing, p.59-73, October 04-06, 2000
• 8: David L. Detlefs , Paul A. Martin , Mark Moir , Guy L. Steele, Jr., Lock-free reference counting, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.190-199, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384016]
• 9: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 10: Michael Greenwald, Non-blocking Synchronization and System Design, Stanford University, Stanford, CA, 1999
• 11: Michael Greenwald , David Cheriton, The synergy between non-blocking synchronization and operating system structure, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.123-136, October 29-November 01, 1996, Seattle, Washington, United States
• 12: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 13: Maurice Herlihy , Victor Luchangco , Paul Martin , Mark Moir, Dynamic-sized lock-free data structures, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571847]
• 14: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 15: Prince Kohli, Gil Neiger, and Mustaque Ahamad. A characterization of scalable shared memories. In Proceedings of the 1993 International Conference on Parallel Processing, volume I - Architecture, pages 332-334, Boca Raton, FL, 1993. CRC Press.
• 16: David M. Koppelman. Version L3.11 Proteus Changes. Louisiana State University, Baton Rouge, August 1997. ftp://ftp.ee.lsu.edu/pub/koppel/proteus/proteusl.pdf.
• 17: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 18: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 19: CORPORATE Motorola, Inc., M68000 family programmer's reference manual, Motorola Inc., Phoenix, AZ, 1991
• 20: R.K.Treiber. Systems programming: Coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center, April 1986.