Document Open Access Logo

Fast Arrays: Atomic Arrays with Constant Time Initialization

Authors Siddhartha Jayanti , Julian Shun

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.25.pdf
  • Filesize: 1.1 MB
  • 19 pages

Document Identifiers

Author Details

Siddhartha Jayanti
  • MIT CSAIL, Cambridge, MA, USA
Julian Shun
  • MIT CSAIL, Cambridge, MA, USA

Funding

  • Jayanti, Siddhartha: NDSEG Fellowship from the US Department of Defense
  • Shun, Julian: DOE Early Career Award #DESC0018947, NSF CAREER Award #CCF-1845763, a Google Faculty Research Award, a Google Research Scholar Award, DARPA SDH Award #HR0011-18-3-0007, and Applications Driving Architectures (ADA) Research Center, and a JUMP Center co-sponsored by SRC and DARPA

Cite As Get BibTex

Siddhartha Jayanti and Julian Shun. Fast Arrays: Atomic Arrays with Constant Time Initialization. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.25

Abstract

Some algorithms require a large array, but only operate on a small fraction of its indices. Examples include adjacency matrices for sparse graphs, hash tables, and van Emde Boas trees. For such algorithms, array initialization can be the most time-consuming operation. Fast arrays were invented to avoid this costly initialization. A fast array is a software implementation of an array, such that the entire array can be initialized in just constant time.

While algorithms for sequential fast arrays have been known for a long time, to the best of our knowledge, there are no previous algorithms for concurrent fast arrays. We present the first such algorithms in this paper. Our first algorithm is linearizable and wait-free, uses only linear space, and supports all operations - initialize, read, and write - in constant time. Our second algorithm enhances the first to additionally support all the read-modify-write operations available in hardware (such as compare-and-swap) in constant time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • fast array
  • linearizable
  • wait-free
  • asynchronous
  • multiprocessor
  • constant time
  • space efficient
  • data structure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. Richard J. Anderson and Heather Woll. Algorithms for the certified write-all problem. SIAM J. Comput., 26(5):1277-1283, 1997. Google Scholar
  3. Hagit Attiya, Danny Hendler, and Philipp Woelfel. Tight RMR lower bounds for mutual exclusion and other problems. In Rida A. Bazzi and Boaz Patt-Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, page 447. ACM, 2008. URL: https://doi.org/10.1145/1400751.1400843.
  4. Jon Louis Bentley. Programming pearls. Addison-Wesley, 1986. Google Scholar
  5. Jonathan F. Buss, Paris C. Kanellakis, Prabhakar L. Ragde, and Alex Allister Shvartsman. Parallel algorithms with processor failures and delays. Journal of Algorithms, 20(1):45-86, 1996. Google Scholar
  6. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  7. Robert Cypher. The communication requirements of mutual exclusion. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, pages 147-156, 1995. Google Scholar
  8. Laxman Dhulipala, Changwan Hong, and Julian Shun. Connectit: A framework for static and incremental parallel graph connectivity algorithms. Proc. VLDB Endow., 14(4):653–667, 2020. Google Scholar
  9. Kimmo Fredriksson and Pekka Kilpeläinen. Practically efficient array initialization. Softw. Pract. Exp., 46(4):435-467, 2016. Google Scholar
  10. Hui Gao, Jan Friso Groote, and Wim H. Hesselink. Almost wait-free resizable hashtable. In International Parallel and Distributed Processing Symposium, 2004. Google Scholar
  11. Hui Gao, Jan Friso Groote, and Wim H. Hesselink. Lock-free dynamic hash tables with open addressing. Distributed Comput., 18(1):21-42, 2005. Google Scholar
  12. Jan Groote, Wim Hesselink, and Sjouke Mauw. An algorithm for the asynchronous write-all problem based on process collision. Distributed Computing, 14:75-81, April 2001. Google Scholar
  13. Torben Hagerup and Frank Kammer. On-the-fly array initialization in less space. In International Symposium on Algorithms and Computation, volume 92, pages 44:1-44:12, 2017. Google Scholar
  14. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, 1991. Google Scholar
  15. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. Google Scholar
  16. Changwan Hong, Laxman Dhulipala, and Julian Shun. Exploring the design space of static and incremental graph connectivity algorithms on GPUs. In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, pages 55-69, 2020. Google Scholar
  17. Intel. Intel 64 and IA-32 architectures software developer manuals, 2020. URL: https://software.intel.com/content/www/us/en/develop/articles/intel-sdm.html.
  18. Masakazu Ishihata, Shan Gao, and Shin-ichi Minato. Fast message passing algorithm using ZDD-based local structure compilation. In Proceedings of the Workshop on Advanced Methodologies for Bayesian Networks, volume 73, pages 117-128, 2017. Google Scholar
  19. Siddhartha V. Jayanti and Robert E. Tarjan. A randomized concurrent algorithm for disjoint set union. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 75-82, 2016. Google Scholar
  20. Paris C. Kanellakis and Alex A. Shvartsman. Efficient parallel algorithms can be made robust. In Proceedings of the ACM Symposium on Principles of Distributed Computing, page 211–219, 1989. Google Scholar
  21. Takashi Katoh and Keisuke Goto. In-place initializable arrays. CoRR, abs/1709.08900, 2017. Google Scholar
  22. Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional, 12th edition, 2009. Google Scholar
  23. Jacob Teo Por Loong, Jelani Nelson, and Huacheng Yu. Fillable arrays with constant time operations and a single bit of redundancy. CoRR, abs/1709.09574, 2017. URL: http://arxiv.org/abs/1709.09574.
  24. C. Martel, R. Subramonian, and A. Part. Asynchronous PRAMs are (almost) as good as synchronous PRAMs. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 590-599, 1990. Google Scholar
  25. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1 of EATCS Monographs on Theoretical Computer Science. Springer, 1984. Google Scholar
  26. John M. Mellor-Crummey and Michael L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21-65, 1991. Google Scholar
  27. Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the International Design Automation Conference, page 272–277, 1993. Google Scholar
  28. Shin-ichi Minato. Counting by ZDD. In Encyclopedia of Algorithms, pages 454-458. Springer Publishing Company, 2016. Google Scholar
  29. Shin-ichi Minato. Power of enumeration - recent topics on BDD/ZDD-based techniques for discrete structure manipulation. IEICE Trans. Inf. Syst., 100-D(8):1556-1562, 2017. Google Scholar
  30. Dana Moshkovitz and Bruce Tidor. Lecture notes 15: van Emde Boas data structure. URL: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec15.pdf.
  31. Gonzalo Navarro. Constant-time array initialization in little space. In Proceedings of the International Conference of the Chilean Computer Science Society (SCCC), 2012. Google Scholar
  32. Gonzalo Navarro. Spaces, trees, and colors: The algorithmic landscape of document retrieval on sequences. ACM Comput. Surv., 46(4):52:1-52:47, 2013. Google Scholar
  33. Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables. J. ACM, 53(3):379-405, 2006. Google Scholar
  34. Hirofumi Suzuki and Shin-ichi Minato. Fast enumeration of all pareto-optimal solutions for 0-1 multi-objective knapsack problems using ZDDs. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 101-A(9):1375-1382, 2018. Google Scholar
  35. Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. Finding all solutions and instances of numberlink and slitherlink by ZDDs. Algorithms, 5(2):176-213, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact