Maged M. Michael
Skip Abstract Section
Abstract
What is nonblocking progress? Consider the simple example of incrementing a counter C shared among multiple threads. One way to do so is by protecting the steps of incrementing C by a mutual exclusion lock L (i.e., acquire(L); old := C ; C := old+1; release(L);). If a thread P is holding L, then a different thread Q must wait for P to release L before Q can proceed to operate on C. That is, Q is blocked by P.
- Attiya, H., Hendler, D. 2005. Time and space lower bounds for implementations using k-CAS. In Proceedings of the 19th International Conference on Distributed Computing: 169-183. Google Scholar
Digital Library
- Brown, P. J., Smith, R. M. 1973. U.S. Patent 3,886,525. Shared data controlled by a plurality of users (filed June 1973).Google Scholar
- Cain, H. W., Frey, B., Williams, D., Michael, M. M., May, C., Le, H. 2013. Robust architectural support for transactional memory in the Power architecture. ACM/IEEE 40th International Symposium on Computer Architecture (ISCA). Google ScholarDigital Library
- Dragojevic, A., Herlihy, M., Lev, Y., Moir, M. 2011. On the power of hardware transactional memory to simplify memory management. 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC): 99-108. Google ScholarDigital Library
- Fatourou, P., Kallimanis, N. D. 2011. A highly efficient wait-free universal construction. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA): 325-334. Google ScholarDigital Library
- Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer III, W. N., Shavit, N. 2005. A lazy concurrent list-based set algorithm. Ninth International Conference on Principles of Distributed Systems (OPODIS): 3-16. Google ScholarDigital Library
- Herlihy, M. 1991. Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1): 124-149. Google ScholarDigital Library
- Herlihy, M., Luchangco, V., Martin, P. A., Moir, M. 2005. Nonblocking memory management support for dynamic-sized data structures. ACM Transactions on Computer Systems 23(2): 146-196. Google ScholarDigital Library
- Herlihy, M., Luchangco, V., Moir, M. 2003. Obstruction-free synchronization: double-ended queues as an example. 23rd International Conference on Distributed Computing Systems (ICDCS): 522-529. Google ScholarDigital Library
- IBM System/370 Principles of Operation. 1975. GA22-7000-4.Google Scholar
- Intel Architecture Instruction Set Extensions Programming Reference. 2012.Google Scholar
- Jacobi, C., Slegel, T. J., Greiner, D. F. 2012. Transactional memory architecture and implementation for IBM System Z. 45th Annual IEEE/ACM International Symposium on Microarchitecture: 25-36. Google ScholarDigital Library
- McKenney, P. 2013. Structured deferral: synchronization via procrastination. ACM Queue. http://queue.acm.org/detail.cfm?id=2488549 Google ScholarDigital Library
- McKenney, P. E., Slingwine, J. D. 1998. Read-copy update: using execution history to solve concurrency problems. Proceedings of the 10th IASTED International Conference on Parallel and Distributed Computing and Systems.Google Scholar
- Michael, M. M., Scott, M. L. 1996. Simple, fast, and practical nonblocking and blocking concurrent queue algorithms. Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing: 267-275. Google ScholarDigital Library
- Michael, M. M. 2004. Hazard pointers: safe memory reclamation for lock-free objects. IEEE Transactions on Parallel Distributed Systems 15(6): 491-504. Google ScholarDigital Library
- Michael, M. M. 2004. Scalable lock-free dynamic memory allocation. In Proceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- Michael, M. M. 2004. Practical lock-free and wait-free LL/SC/VL implementations using 64-bit CAS. In Proceedings of the 18th International Conference on Distributed Computing: 144-158.Google ScholarCross Ref
- Timnat, S., Braginsky, A., Kogan, A., Petrank, E. 2012. Wait-free linked-lists. 16th International Conference on Principles of Distributed Systems: 330-344.Google ScholarCross Ref
- Valois, J. D. 1995. Lock-free linked lists using compare-and-swap. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing: 214-222. Google ScholarDigital Library
- Wang, A., Gaudet, M., Wu, P., Amaral, J. N., Ohmacht, M., Barton, C., Silvera, R., Michael, M. M. 2012. Evaluation of Blue Gene/Q hardware support for transactional memories. In Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques: 127-136. Google ScholarDigital Library
Index Terms
- The Balancing Act of Choosing Nonblocking Features: Design requirements of nonblocking systems
Index terms have been assigned to the content through auto-classification.
Recommendations
The balancing act of choosing nonblocking features
Design requirements of nonblocking systems.
Nonblocking, repackable, and rearrangeable Clos networks: fifty years of the theory evolution
The article gives an overview of major theoretical issues associated with a switching network structure proposed by C. Clos (1953). The concepts of strict-sense and wide-sense nonblocking as well as repackable and rearrangeable networks are described, ...
Scalable and Practical Nonblocking Switching Networks (Extended Abstract)
PDCAT '05: Proceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and TechnologiesSwitching networks are widely used as core components in network switches and routers, and communication subsyetems in parallel computing systems. Most switching networks are multistage interconnection networks built with small-size switching elements. ...
Comments