Using elimination to implement scalable and lock-free FIFO queues

ABSTRACT

This paper shows for the first time that elimination, a scaling technique formerly applied only to counters and LIFO structures, can be applied to FIFO data structures, specifically, to linearizable FIFO queues. We show how to transform existing nonscalable FIFO queue implementations into scalable implementations using the elimination technique, while preserving lock-freedom and linearizablity.We apply our transformation to the FIFO queue algorithm of Michael and Scott, which is included in the Java™ Concurrency Package. Empirical evaluation on a state-of-the-art CMT multiprocessor chip shows that by using elimination as a backoff technique for the Michael and Scott queue algorithm, we can achieve comparable performance at low loads, and improved scalability as load increases.

REFERENCES

• 1: A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel
• 2: W. Aiello, C. Busch, M. Herlihy, M. Mavronicolas, N. Shavit, and D. Touitou. Supporting increment and decrement operations in balancing networks. Lecture Notes in Computer Science, 1563:393--403, 1999.
• 3: Danny Dolev , Nir Shavit, Bounded Concurrent Time-Stamping, SIAM Journal on Computing, v.26 n.2, p.418-455, April 1997 [doi>10.1137/S0097539790192647]
• 4: James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
• 5: A. Gottlieb, R. Grishman, C. Kruskal, K. McAuliffe, L. Rudolph, and M. Snir. The NYU ultracomputer - designing an MIMD parallel computer. IEEE Transactions on Computers, C-32(2):175--189, February 1984.
• 6: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 7: Danny Hendler , Nir Shavit , Lena Yerushalmi, A scalable lock-free stack algorithm, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007944]
• 8: Maurice Herlihy , Victor Luchangco , Paul Martin , Mark Moir, Nonblocking memory management support for dynamic-sized data structures, ACM Transactions on Computer Systems (TOCS), v.23 n.2, p.146-196, May 2005 [doi>10.1145/1062247.1062249]
• 9: 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]
• 10: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 11: E. Ladan-Mozes and N. Shavit. An optimistic approach to lock-free fifo queues. In proceedings of the 18th International Conference on Distributed Computing (DISC), pages 117--131. Springer-Verlag GmbH, 2004.
• 12: Leslie Lamport, Specifying Concurrent Program Modules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.190-222, April 1983 [doi>10.1145/69624.357207]
• 13: D. Lea. The java concurrency package (JSR-166). http://gee.cs.oswego.edu/dl/concurrency-interest/index.html.
• 14: J. M. Mellor-Crummey. Concurrent queues: Practical fetch-and-φ algorithms. Technical Report Technical Report 229, University of Rochester, November 1987.
• 15: 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]
• 16: Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259442]
• 17: S. Prakash, Y.-H. Lee, and T. Johnson. Non-blocking algorithms for concurrent data structures. Technical Report 91--002, Department of Information Sciences, University of Florida, 1991.
• 18: S. Prakash , Yann Hang Lee , T. Johnson, A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap, IEEE Transactions on Computers, v.43 n.5, p.548-559, May 1994 [doi>10.1109/12.280802 ]
• 19: W. N. Scherer and M. L. Scott. Nonblocking concurrent data structures with condition synchronization. In Proceedings of the 18th International Symposium on DIStributed Computing, pages 174--187, Berlin, Heidelberg, New York, October 2004. Springer.
• 20: N. Shavit and D. Touitou. Elimination trees and the construction of pools and stacks. Theory of Computing Systems, 30:645--670, 1997.
• 21: Nir Shavit , Asaph Zemach, Combining funnels: a dynamic approach to software combining, Journal of Parallel and Distributed Computing, v.60 n.11, p.1355-1387, Nov. 2000 [doi>10.1006/jpdc.2000.1621 ]
• 22: Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 23: Janice M. Stone, A simple and correct shared-queue algorithm using Compare-and-Swap, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.495-504, November 12-16, 1990, New York, New York
• 24: R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
• 25: J. Valois. Implementing lock-free queues. In Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, pages 64--69, 1994.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Design, Theory, Verification

Keywords:
FIFO queues, elimination, linearizability, lock-free, multiprocessors, nonblocking synchronization, scalability