skip to main content
research-article
Free access

Data structures in the multicore age

Published: 01 March 2011 Publication History

Abstract

The advent of multicore processors as the standard computing platform will force major changes in software design.

References

[1]
Agarwal, A. and Cherian, M. Adaptive backoff synchronization techniques. In Proceedings of the 16th International Symposium on Computer Architecture (May 1989), 396--406.
[2]
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.
[3]
Arora, N.S., Blumofe, R.D. and Plaxton, C.G. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems 34, 2 (2001), 115--144.
[4]
Aspnes, J., Herlihy, M. and Shavit, N. Counting networks. J. ACM 41, 5 (1994), 1020--1048.
[5]
Blumofe, R.D. and Leiserson, C.E. Scheduling multithreaded computations by work stealing. J. ACM 46, 5 (1999), 720--748.
[6]
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.
[7]
Cypher, R. The communication requirements of mutual exclusion. In ACM Proceedings of the Seventh Annual Symposium on Parallel Algorithms and Architectures (1995), 147--156.
[8]
Dwork, C., Herlihy, M. and Waarts, O. Contention in shared memory algorithms. J. ACM 44, 6 (1997), 779--805.
[9]
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.
[10]
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.
[11]
Hendler, D., Shavit, N. and Yerushalmi, L. A scalable lock-free stack algorithm. J. Parallel and Distributed Computing 70, 1 (Jan. 2010), 1--12.
[12]
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.
[13]
Herlihy, M. and Moss, E. Transactional memory: architectural support for lock-free data structures. SIGARCH Comput. Archit. News 21, 2 (1993), 289--300.
[14]
Herlihy, M. and Shavit, N. The Art of Multiprocessor Programming. Morgan Kaufmann, San Mateo, CA, 2008.
[15]
Herlihy, M. and Wing, J. Linearizability: A correctness condition for concurrent objects. ACM Trans. Programming Languages and Systems 12, 3 (July 1990), 463--492.
[16]
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.
[17]
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.
[18]
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.
[19]
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.
[20]
Shavit, N. and Touitou, D. Elimination trees and the construction of pools and stacks. Theory of Computing Systems 30 (1997), 645--670.
[21]
Shavit, N. and Touitou, D. Software transactional memory. Distributed Computing 10, 2 (Feb. 1997), 99--116.
[22]
Shavit, N. and Zemach, A. Diffracting trees. ACM Transactions on Computer Systems 14, 4 (1996), 385--428.
[23]
Treiber, R.K. Systems programming: Coping with parallelism. Technical Report RJ 5118 (Apr. 1986). IBM Almaden Research Center, San Jose, CA.

Cited By

View all

Recommendations

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

Information & Contributors

Information

Published In

cover image Communications of the ACM
Communications of the ACM  Volume 54, Issue 3
March 2011
116 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/1897852
Issue’s Table of Contents
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: 01 March 2011
Published in CACM Volume 54, Issue 3

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article
  • Popular
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)568
  • Downloads (Last 6 weeks)88
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Recent Advances on Principles of Concurrent Data StructuresCommunications of the ACM10.1145/365329067:8(45-46)Online publication date: 11-Jul-2024
  • (2024)Decentralized lock-free distributed queue in MPI remote memory access modelE3S Web of Conferences10.1051/e3sconf/202454803007548(03007)Online publication date: 12-Jul-2024
  • (2024)How to Relax Instantly: Elastic Relaxation of Concurrent Data StructuresEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_9(119-133)Online publication date: 26-Aug-2024
  • (2023)ESH: Design and Implementation of an Optimal Hashing Scheme for Persistent MemoryApplied Sciences10.3390/app13201152813:20(11528)Online publication date: 20-Oct-2023
  • (2022)A Linearizability-based Hierarchy for Concurrent SpecificationsCommunications of the ACM10.1145/354682666:1(86-97)Online publication date: 20-Dec-2022
  • (2022)Performance Analysis and Modelling of Concurrent Multi-access Data StructuresProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538578(333-344)Online publication date: 11-Jul-2022
  • (2022)Separating lock-freedom from wait-freedom at every level of the consensus hierarchyJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.01.025163:C(181-197)Online publication date: 1-May-2022
  • (2022)Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with MultiplicityDistributed Computing10.1007/s00446-022-00440-y36:2(89-106)Online publication date: 7-Dec-2022
  • (2022)SPHT: A scalable and high‐performance hashing scheme for persistent memorySoftware: Practice and Experience10.1002/spe.308352:7(1679-1697)Online publication date: 21-Mar-2022
  • (2021)Paradigms for Effective Parallelization of Inherently Sequential Graph Algorithms on Multi-Core ArchitecturesHandbook of Research on Methodologies and Applications of Supercomputing10.4018/978-1-7998-7156-9.ch005(74-95)Online publication date: 2021
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media