Nir Shavit
Abstract
The advent of multicore processors as the standard computing platform will force major changes in software design.
- Agarwal, A. and Cherian, M. Adaptive backoff synchronization techniques. In Proceedings of the 16th International Symposium on Computer Architecture (May 1989), 396--406. Google Scholar
Digital Library
- Anderson, J. and Kim, Y. An improved lower bound for the time complexity of mutual exclusion. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing (2001), 90--99. Google ScholarDigital Library
- Arora, N.S., Blumofe, R.D. and Plaxton, C.G. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems 34, 2 (2001), 115--144.Google ScholarCross Ref
- Aspnes, J., Herlihy, M. and Shavit, N. Counting networks. J. ACM 41, 5 (1994), 1020--1048. Google ScholarDigital Library
- Blumofe, R.D. and Leiserson, C.E. Scheduling multithreaded computations by work stealing. J. ACM 46, 5 (1999), 720--748. Google ScholarDigital Library
- Chase, D. and Lev, Y. Dynamic circular work-stealing deque. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (2005). ACM Press, NY, 21--28. Google ScholarDigital Library
- Cypher, R. The communication requirements of mutual exclusion. In ACM Proceedings of the Seventh Annual Symposium on Parallel Algorithms and Architectures (1995), 147--156. Google ScholarDigital Library
- Dwork, C., Herlihy, M. and Waarts, O. Contention in shared memory algorithms. J. ACM 44, 6 (1997), 779--805. Google ScholarDigital Library
- Fich, F.E., Hendler, D. and Shavit, N. Linear lower bounds on real-world implementations of concurrent objects. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (2005). IEEE Computer Society, Washington, D.C., 165--173. Google ScholarDigital Library
- Gibbons, P.B., Matias, Y. and Ramachandran, V. The queue-read queue-write PRAM model: Accounting for contention in parallel algorithms. SIAM J. Computing 28, 2 (1999), 733--769. Google ScholarDigital Library
- Hendler, D., Shavit, N. and Yerushalmi, L. A scalable lock-free stack algorithm. J. Parallel and Distributed Computing 70, 1 (Jan. 2010), 1--12. Google ScholarDigital Library
- Herlihy, M., Luchangco, V., Moir, M. and Scherer III, W.N. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing. ACM, NY, 2003, 92--101. Google ScholarDigital Library
- Herlihy, M. and Moss, E. Transactional memory: architectural support for lock-free data structures. SIGARCH Comput. Archit. News 21, 2 (1993), 289--300. Google ScholarDigital Library
- Herlihy, M. and Shavit, N. The Art of Multiprocessor Programming. Morgan Kaufmann, San Mateo, CA, 2008. Google ScholarDigital Library
- Herlihy, M. and Wing, J. Linearizability: A correctness condition for concurrent objects. ACM Trans. Programming Languages and Systems 12, 3 (July 1990), 463--492. Google ScholarDigital Library
- Moir, M., Nussbaum, D., Shalev, O. and Shavit, N. Using elimination to implement scalable and lock-free fifo queues. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press, NY, 2005, 253--262. Google ScholarDigital Library
- Moir, M. and Shavit, N. Concurrent data structures. Handbook of Data Structures and Applications, D. Metha and S. Sahni, eds. Chapman and Hall/CRC Press, 2007, 47--14, 47--30.Google Scholar
- Scherer III, W.N., Lea, D. and Scott, M.L. Scalable synchronous queues. In Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM Press, NY, 2006, 147--156. Google ScholarDigital Library
- Scherer III, W.N. and Scott, M.L. Advanced contention management for dynamic software transactional memory. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing. ACM, NY, 2005, 240--248. Google ScholarDigital Library
- Shavit, N. and Touitou, D. Elimination trees and the construction of pools and stacks. Theory of Computing Systems 30 (1997), 645--670.Google ScholarDigital Library
- Shavit, N. and Touitou, D. Software transactional memory. Distributed Computing 10, 2 (Feb. 1997), 99--116.Google ScholarCross Ref
- Shavit, N. and Zemach, A. Diffracting trees. ACM Transactions on Computer Systems 14, 4 (1996), 385--428. Google ScholarDigital Library
- Treiber, R.K. Systems programming: Coping with parallelism. Technical Report RJ 5118 (Apr. 1986). IBM Almaden Research Center, San Jose, CA.Google Scholar
Index Terms
- Data structures in the multicore age
Recommendations
Massively LDPC Decoding on Multicore Architectures
Unlike usual VLSI approaches necessary for the computation of intensive Low-Density Parity-Check (LDPC) code decoders, this paper presents flexible software-based LDPC decoders. Algorithms and data structures suitable for parallel computing are proposed ...
Parallelism via Multithreaded and Multicore CPUs
Multicore and multithreaded CPUs have become the new approach to obtaining increases in CPU performance. Numeric applications mostly benefit from a large number of computationally powerful cores. Servers typically benefit more if chip circuitry is used ...
Software Standards for the Multicore Era
Systems architects commonly use multiple cores to improve system performance. Unfortunately, multicore hardware is evolving faster than software technologies. New multicore software standards are necessary in light of the new challenges and capabilities ...
Reviews
John P. Dougherty
Multicore is here; that is the reality. This article looks at the impact of this new reality on data structures. It provides a path from traditional structures that assume sequential access to modern structures that support concurrent access, including the context and motivation for this transition path. The author makes his points using the standard stack as a representative data structure example. He offers a series of stack designs that support various degrees of concurrency, each potentially better-performing than the previous, but also more complex. The final design, a pool, no longer mandates last-in-first-out (LIFO) access, but leverages the potential parallelism offered by multicore and (arguably) provides appropriate storage and access for many applications. The author defines and investigates each implementation for performance, safety, and liveness; he gives optimizations for a few. The article reads well, and provides plenty of resources in the references for more in-depth reading. The illustrations-especially the elimination tree-facilitated my comprehension of each design. The author explicitly expects that more conventional data structures will "soon disappear," to be replaced by new "unordered" ones. The article makes a compelling case for this expectation. As a computer science educator, I now have more motivation for my expectation that students in the data structure course (eventually) appreciate concurrency. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments