Document Open Access Logo

The DAG Visit Approach for Pebbling and I/O Lower Bounds

Authors Gianfranco Bilardi, Lorenzo De Stefani

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.7.pdf
  • Filesize: 0.89 MB
  • 23 pages

Document Identifiers

Author Details

Gianfranco Bilardi
  • Department of Information Engineering, University of Padova, Italy
Lorenzo De Stefani
  • Department of Computer Science, Brown University, Providence, RI, USA

Funding

  • Bilardi, Gianfranco: This work was supported in part by the Italian National Center for HPC, Big Data, and Quantum Computing; by MIUR, the Italian Ministry of Education, University and Research, under PRIN Project n. 20174LF3T8 AHeAD (Efficient Algorithms for HArnessing Networked Data); and by the University of Padova, under Project CPGA³ (Parallel and Hierarchical Computing: Architectures, Algorithms, and Applications).

Cite As Get BibTex

Gianfranco Bilardi and Lorenzo De Stefani. The DAG Visit Approach for Pebbling and I/O Lower Bounds. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.7

Abstract

We introduce the notion of an r-visit of a Directed Acyclic Graph DAG G = (V,E), a sequence of the vertices of the DAG complying with a given rule r. A rule r specifies for each vertex v ∈ V a family of r-enabling sets of (immediate) predecessors: before visiting v, at least one of its enabling sets must have been visited. Special cases are the r^(top)-rule (or, topological rule), for which the only enabling set is the set of all predecessors and the r^(sin)-rule (or, singleton rule), for which the enabling sets are the singletons containing exactly one predecessor. The r-boundary complexity of a DAG G, b_r(G), is the minimum integer b such that there is an r-visit where, at each stage, for at most b of the vertices yet to be visited an enabling set has already been visited. By a reformulation of known results, it is shown that the boundary complexity of a DAG G is a lower bound to the pebbling number of the reverse DAG, G^R. Several known pebbling lower bounds can be cast in terms of the r^{(sin)}-boundary complexity. The main contributions of this paper are as follows:  
- An existentially tight 𝒪(√{d_{out} n}) upper bound to the r^(sin)-boundary complexity of any DAG of n vertices and out-degree d_{out}. 
- An existentially tight 𝒪(d_{out}/(log₂ d_{out}) log₂ n) upper bound to the r^(top)-boundary complexity of any DAG. (There are DAGs for which r^(top) provides a tight pebbling lower bound, whereas r^(sin) does not.) 
- A visit partition technique for I/O lower bounds, which generalizes the S-partition I/O technique introduced by Hong and Kung in their classic paper "I/O complexity: The Red-Blue pebble game". The visit partition approach yields tight I/O bounds for some DAGs for which the S-partition technique can only yield a trivial lower bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Pebbling
  • Directed Acyclic Graph
  • Pebbling number
  • I/O complexity

Metrics

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

Related Versions

References

  1. Alok Aggarwal and S. Vitter, Jeffrey. The Input/Output Complexity of Sorting and Related Problems. Communications of the ACM, 31(9):1116-1127, September 1988. URL: https://doi.org/10.1145/48529.48535.
  2. Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Oded Schwartz, Sivan Toledo, and Ichitaro Yamazaki. Communication-avoiding symmetric-indefinite factorization. SIAM Journal on Matrix Analysis and Applications, 35(4):1364-1406, 2014. Google Scholar
  3. Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, and Oded Schwartz. Brief announcement: Strong scaling of matrix multiplication algorithms and memory-independent communication lower bounds. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures, pages 77-79. ACM, 2012. Google Scholar
  4. Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. Communication-optimal parallel and sequential Cholesky decomposition. SIAM Journal on Scientific Computing, 32(6):3495-3523, 2010. Google Scholar
  5. Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. Minimizing communication in numerical linear algebra. SIAM Journal on Matrix Analysis and Applications, 32(3):866-901, 2011. Google Scholar
  6. Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. Graph expansion and communication costs of fast matrix multiplication. Journal of the ACM (JACM), 59(6):1-23, 2013. Google Scholar
  7. Gianfranco Bilardi and Lorenzo De Stefani. The I/O complexity of Strassen’s matrix multiplication with recomputation. In Workshop on Algorithms and Data Structures, pages 181-192. Springer, 2017. Google Scholar
  8. Gianfranco Bilardi and Lorenzo De Stefani. The I/O Complexity of Toom-Cook Integer Multiplication. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 2034-2052, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
  9. Gianfranco Bilardi and Lorenzo De Stefani. The dag visit approach for pebbling and i/o lower bounds, 2022. URL: https://doi.org/10.48550/arXiv.2210.01897.
  10. Gianfranco Bilardi, Andrea Pietracaprina, and Paolo D'Alberto. On the space and access complexity of computation DAGs. In Graph-Theoretic Concepts in Computer Science, pages 47-58. Springer, 2000. Google Scholar
  11. Gianfranco Bilardi and Franco Preparata. Processor-Time trade offs under bounded speed message propagation. Part 2: Lower Bounds. Theory of Computing Systems, 32(5):531-559, 1999. Google Scholar
  12. Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. Efficient Algorithms with Asymmetric Read and Write Costs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 14:1-14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.14.
  13. Timothy Carpenter, Fabrice Rastello, P. Sadayappan, and Anastasios Sidiropoulos. Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '16, pages 161-163, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2935764.2935807.
  14. Erin C. Carson, James Demmel, Laura Grigori, Nicholas Knight, Penporn Koanantakool, Oded Schwartz, and Harsha Vardhan Simhadri. Write-Avoiding Algorithms. In 2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016, Chicago, IL, USA, May 23-27, 2016, pages 648-658. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/IPDPS.2016.114.
  15. Lorenzo De Stefani. On space constrained computations. PhD thesis, University of Padova, 2016. Google Scholar
  16. Lorenzo De Stefani. Brief Announcement: On the I/O Complexity of Sequential and Parallel Hybrid Integer Multiplication Algorithms. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '22, pages 449-452, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3490148.3538551.
  17. Venmugil Elango, Fabrice Rastello, Louis-Noël Pouchet, Jagannathan Ramanujam, and Ponnuswamy Sadayappan. On characterizing the data access complexity of programs. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 567-580, 2015. Google Scholar
  18. Harvey Friedman. Algorithmic procedures, generalized turing algorithms, and elementary recursion theory. In Studies in Logic and the Foundations of Mathematics, volume 61, pages 361-389. Elsevier, 1971. Google Scholar
  19. D. Yu Grigor'ev. Application of separability and independence notions for proving lower bounds of circuit complexity. Zapiski Nauchnykh Seminarov POMI, 60:38-48, 1976. Google Scholar
  20. Yan Gu, Yihan Sun, and Guy E. Blelloch. Algorithmic building blocks for asymmetric memories. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 44:1-44:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.44.
  21. John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. Journal of the ACM (JACM), 24(2):332-337, 1977. Google Scholar
  22. Dror Irony, Sivan Toledo, and Alexander Tiskin. Communication lower bounds for distributed-memory matrix multiplication. Journal of Parallel and Distributed Computing, 64(9):1017-1026, 2004. Google Scholar
  23. Hong Jia-Wei and Hsiang-Tsung Kung. I/O complexity: The red-blue pebble game. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, pages 326-333, 1981. Google Scholar
  24. Lynn H Loomis and Hassler Whitney. An inequality related to the isoperimetric inequality. Bulletin of the American Mathematical Society, 55(10):961-962, 1949. Google Scholar
  25. Auguste Olivry, Guillaume Iooss, Nicolas Tollenaere, Atanas Rountev, P. Sadayappan, and Fabrice Rastello. Ioopt: automatic derivation of I/O complexity bounds for affine programs. In Stephen N. Freund and Eran Yahav, editors, PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Virtual Event, Canada, June 20-25, 2021, pages 1187-1202. ACM, 2021. URL: https://doi.org/10.1145/3453483.3454103.
  26. Rasmus Pagh and Morten Stöckel. The input/output complexity of sparse matrix multiplication. In European Symposium on Algorithms, pages 750-761. Springer, 2014. Google Scholar
  27. Michael S Paterson and Carl E Hewitt. Comparative schematology. In Record of the Project MAC conference on concurrent systems and parallel computation, pages 119-127. ACM, 1970. Google Scholar
  28. Wolfgang J Paul, Robert Endre Tarjan, and James R Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10(1):239-251, 1976. Google Scholar
  29. Desh Ranjan, John Savage, and Mohammad Zubair. Upper and lower I/O bounds for pebbling r-pyramids. Journal of Discrete Algorithms, 14:2-12, 2012. Google Scholar
  30. J. E. Savage. Extending the Hong-Kung model to memory hierarchies. In Computing and Combinatorics, pages 270-281. Springer, 1995. Google Scholar
  31. John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1997. Google Scholar
  32. Jacob Scott, Olga Holtz, and Oded Schwartz. Matrix multiplication I/O-complexity by path routing. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 35-45, 2015. Google Scholar
  33. Michele Scquizzato and Francesco Silvestri. Communication lower bounds for distributed-memory computations. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 627-638. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.627.
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