DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2022.7

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

Authors: Gianfranco Bilardi and Lorenzo De Stefani

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bilardi_et_al:LIPIcs.FSTTCS.2022.7,
  author =	{Bilardi, Gianfranco and De Stefani, Lorenzo},
  title =	{{The DAG Visit Approach for Pebbling and I/O Lower Bounds}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.7},
  URN =		{urn:nbn:de:0030-drops-173999},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.7},
  annote =	{Keywords: Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.33

The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication

Authors: Lorenzo De Stefani

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

Asymptotically tight lower bounds are derived for the I/O complexity of a general class of hybrid algorithms computing the product of n x n square matrices combining "Strassen-like" fast matrix multiplication approach with computational complexity Theta(n^{log_2 7}), and "standard" matrix multiplication algorithms with computational complexity Omega (n^3). We present a novel and tight Omega ((n/max{sqrt M, n_0})^{log_2 7}(max{1,(n_0)/M})^3M) lower bound for the I/O complexity of a class of "uniform, non-stationary" hybrid algorithms when executed in a two-level storage hierarchy with M words of fast memory, where n_0 denotes the threshold size of sub-problems which are computed using standard algorithms with algebraic complexity Omega (n^3). The lower bound is actually derived for the more general class of "non-uniform, non-stationary" hybrid algorithms which allow recursive calls to have a different structure, even when they refer to the multiplication of matrices of the same size and in the same recursive level, although the quantitative expressions become more involved. Our results are the first I/O lower bounds for these classes of hybrid algorithms. All presented lower bounds apply even if the recomputation of partial results is allowed and are asymptotically tight. The proof technique combines the analysis of the Grigoriev’s flow of the matrix multiplication function, combinatorial properties of the encoding functions used by fast Strassen-like algorithms, and an application of the Loomis-Whitney geometric theorem for the analysis of standard matrix multiplication algorithms. Extensions of the lower bounds for a parallel model with P processors are also discussed.

Cite as

Lorenzo De Stefani. The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{destefani:LIPIcs.ISAAC.2019.33,
  author =	{De Stefani, Lorenzo},
  title =	{{The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.33},
  URN =		{urn:nbn:de:0030-drops-115299},
  doi =		{10.4230/LIPIcs.ISAAC.2019.33},
  annote =	{Keywords: I/O complexity, Hybrid Algorithm, Matrix Multiplication, Recomputation}
}

Search Results

Documents authored by De Stefani, Lorenzo

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

Abstract

Cite as

The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication

Abstract

Cite as

Thanks for your feedback!

Could not send message