Home Publications edited volumes Awards Research Teaching Miscellaneous Full CV [pdf] BLOG
Events
Past Events

Publications of Torsten Hoefler
Niels Gleinig, Torsten Hoefler:
  The RedBlue 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)
AbstractData 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 redblue pebble game, we investigate the I/Ocomplexity of directed acyclic graphs (DAGs) with a large proportion of input vertices. For trees, we show that the number of leaves is a 2approximation 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/Oinefficiencies, which we will deﬁne precisely, a pebbling strategy is guaranteed to satisfy those bounds and asymptotics. We extend the I/Obounds for trees to a multiprocessor setting with fast individual memories and a slow shared memory.
Documentsdownload article:
  BibTeX  @inproceedings{, author={Niels Gleinig and Torsten Hoefler}, title={{The RedBlue 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/}, } 

