Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

N. Gleinig, T. 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)

Publisher Reference

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 find 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 satisfies 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 define 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={06},
  booktitle={Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings (to appear)},
  doi={},
}