Abstract
Two key synchronization paradigms for the construction of scalable concurrent data-structures are software combining and elimination. Elimination-based concurrent data-structures allow operations with reverse semantics (such as push and pop stack operations) to “collide” and exchange values without having to access a central location. Software combining, on the other hand, is effective when colliding operations have identical semantics: when a pair of threads performing operations with identical semantics collide, the task of performing the combined set of operations is delegated to one of the threads and the other thread waits for its operation(s) to be performed. Applying this mechanism iteratively can reduce memory contention and increase throughput.
The most highly scalable prior concurrent stack algorithm is the elimination-backoff stack [5]. The elimination-backoff stack provides high parallelism for symmetric workloads in which the numbers of push and pop operations are roughly equal, but its performance deteriorates when workloads are asymmetric.
We present DECS, a novel Dynamic Elimination-Combining Stack algorithm, that scales well for all workload types. While maintaining the simplicity and low-overhead of the elimination-bakcoff stack, DECS manages to benefit from collisions of both identical- and reverse-semantics operations. Our empirical evaluation shows that DECS scales significantly better than both blocking and non-blocking best prior stack algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Korland, G., Natanzon, M., Shavit, N.: Scalable Producer-Consumer Pools Based on Elimination-Diffraction Trees. In: D’Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010, Part II. LNCS, vol. 6272, pp. 151–162. Springer, Heidelberg (2010)
Hendler, D., Incze, I., Shavit, N., Tzafrir, M.: Flat combining and the synchronization-parallelism tradeoff. In: SPAA, pp. 355–364 (2010)
Hendler, D., Kutten, S.: Bounded-wait combining: constructing robust and high-throughput shared objects. Distributed Computing 21(6), 405–431 (2009)
Hendler, D., Kutten, S., Michalak, E.: An Adaptive Technique for Constructing Robust and High-Throughput Shared Objects. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol. 6490, pp. 318–332. Springer, Heidelberg (2010)
Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free stack algorithm. J. Parallel Distrib. Comput. 70(1), 1–12 (2010)
Herlihy, M.: Wait-free synchronization. ACM Transactions On Programming Languages and Systems 13(1), 123–149 (1991)
Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12(3), 463–492 (1990)
IBM. IBM System/370 Extended Architecture, Principles of Operation, publication no. SA22-7085 (1983)
Michael, M.M., Scott, M.L.: Nonblocking algorithms and preemption-safe locking on multiprogrammed shared — memory multiprocessors. Journal of Parallel and Distributed Computing 51(1), 1–26 (1998)
Shavit, N., Touitou, D.: Elimination trees and the construction of pools and stacks. Theory of Computing Systems (30), 645–670 (1997)
Taura, K., Matsuoka, S., Yonezawa, A.: An efficient implementation scheme of concurrent object-oriented languages on stock multicomputers. In: Principles Practice of Parallel Programming, pp. 218–228 (1993)
Treiber, R.K.: Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center (April 1986)
Yew, P., Tzeng, N., Lawrie, D.: Distributing hot-spot addressing in large-scale multiprocessors. IEEE Transactions on Computers C-36(4), 388–395 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Nissan, G., Hendler, D., Suissa, A. (2011). A Dynamic Elimination-Combining Stack Algorithm. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds) Principles of Distributed Systems. OPODIS 2011. Lecture Notes in Computer Science, vol 7109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25873-2_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-25873-2_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25872-5
Online ISBN: 978-3-642-25873-2
eBook Packages: Computer ScienceComputer Science (R0)