Publications of Torsten Hoefler

Niels Gleinig, Torsten Hoefler:

The Red-Blue Pebble Game on Trees and DAGs with Large Input

(In Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings (to appear), Jun. 2022)

Abstract

Data movements between different levels of a memory hierarchy (I/Os) are a principal performance bottleneck. This is particularly noticeable in computations that have low complexity but large amounts of input data, often occurring in ''big data''. Using the red-blue pebble game, we investigate the I/O-complexity of directed acyclic graphs (DAGs) with a large proportion of input vertices. For trees, we show that the number of leaves is a 2-approximation for the optimal number of I/Os. Similar techniques as we use in the proof of the results for trees allow us to ﬁnd lower and upper bounds of the optimal number of I/Os for general DAGs. The larger the proportion of input vertices, the stronger those bounds become. For families of DAGs with bounded degree and a large proportion of input vertices (meaning that there exists some constant c>0 such that for every DAG G of this family, the proportion p of input vertices satisﬁes p>c) our bounds give constant factor approximations, improving the previous logarithmic approximation factors. For those DAGs, by avoiding certain I/O-inefficiencies, which we will deﬁne precisely, a pebbling strategy is guaranteed to satisfy those bounds and asymptotics. We extend the I/O-bounds for trees to a multiprocessor setting with fast individual memories and a slow shared memory.

Documents

download article:

BibTeX

@inproceedings{,
  author={Niels Gleinig and Torsten Hoefler},
  title={{The Red-Blue Pebble Game on Trees and DAGs with Large Input}},
  year={2022},
  month={Jun.},
  booktitle={Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings (to appear)},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 3.133.109.141:2024	© Torsten Hoefler