Preliminary results on nb-feb, a synchronization primitive for parallel programming
Abstract
We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).
References
[1]
Krste Asanovic et al. The landscape of parallel computing research: A view from berkeley. Technical Report No. UCB/EECS-2006-183, University of California, Berkeley, 2006.
[2]
Guy E. Blelloch, Phillip B. Gibbons, and S. Harsha Vardhan. Combinable memory-block transactions. In Proc. of the ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 23--34, 2008.
[3]
David E. Culler, Jaswinder Pal Singh, and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann, 1998.
[4]
Maurice Herlihy. Wait-free synchronization. ACM Transaction on Programming and Systems, 11(1):124--149, January 1991.
[5]
Clyde P. Kruskal, Larry Rudolph, and Marc Snir. Efficient synchronization of multiprocessors with shared memory. ACM Trans. Program. Lang. Syst., 10(4):579--601, 1988.
[6]
M. M. Michael and M. L. Scott. Implementation of atomic primitives on distributed shared memory multiprocessors. In Proc. of the IEEE Symp. on High-Performance Computer Architecture, pages 222--231, 1995.
[7]
Srinivas Sridharan, Arun Rodrigues, and Peter Kogge. Evaluating synchronization techniques for light-weight multithreaded/multicore architectures. In Proc. of the ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 57--58, 2007.
Index Terms
- Preliminary results on nb-feb, a synchronization primitive for parallel programming
Recommendations
Preliminary results on nb-feb, a synchronization primitive for parallel programming
PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programmingWe introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, ...
NB-FEB: A Universal Scalable Easy-to-Use Synchronization Primitive for Manycore Architectures
OPODIS '09: Proceedings of the 13th International Conference on Principles of Distributed SystemsThis paper addresses the problem of universal synchronization primitives that can support <em>scalable</em> thread synchronization for large-scale manycore architectures. The universal synchronization primitives that have been deployed widely in ...
A methodology for creating fast wait-free data structures
PPOPP '12Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. While many practical lock-free algorithms exist, wait-free algorithms are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2009322 pages
Copyright © 2009 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 February 2009
Published in SIGPLAN Volume 44, Issue 4
Check for updates
Author Tags
Qualifiers
- Poster
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 278Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)1
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in