Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Quanquan C. Liu, “Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers”, in Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), Vienna, Austria, July 16–18, 2018, pages 195–204.

BibTeX

@InProceedings{PebblesRedBlue_SPAA2018,
  AUTHOR        = {Erik D. Demaine and Quanquan C. Liu},
  TITLE         = {Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers},
  BOOKTITLE     = {Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018)},
  ADDRESS       = {Vienna, Austria},
  MONTH         = {July 16--18},
  YEAR          = 2018,
  PAGES         = {195--204},

  withstudent   = 1,
  papers        = {PebblesInapprox_WADS2017},
  doi           = {https://dx.doi.org/10.1145/3210377.3210387},
  dblp          = {https://dblp.org/rec/conf/spaa/DemaineL18},
  comments      = {This paper is also available from the <A HREF="http://dx.doi.org/10.1145/3210377.3210387">ACM Digital Library</A>.},
}

Abstract:

The red-blue pebble game was formulated in the 1980s [14] to model the I/O complexity of algorithms on a two-level memory hierarchy. Given a directed acyclic graph representing computations (vertices) and their dependencies (edges), the red-blue pebble game allows sequentially adding, removing, and recoloring red or blue pebbles according to a few rules, where red pebbles represent data in cache (fast memory) and blue pebbles represent data on disk (slow, external memory). Specifically, a vertex can be newly pebbled red if and only if all of its predecessors currently have a red pebble; pebbles can always be removed; and pebbles can be recolored between red and blue (corresponding to reading or writing data between disk and cache, also called I/Os or memory transfers). Given an upper bound on the number of red pebbles at any time (the cache size), the goal is to compute a game execution with the fewest pebble recolorings (memory transfers) that finish with pebbles on a specified subset of nodes (outputs get computed).

In this paper, we investigate the complexity of computing this trade-off between red-pebble limit (cache size) and number of recolorings (memory transfers) in general DAGs. First we prove this problem PSPACE-complete through an extension of the proof PSPACE-hardness of black pebbling complexity [13]. Second, we consider a natural restriction on the red-blue pebble game to forbid pebble deletions, or equivalently, forbid discarding data from cache without first writing it to disk. This assumption both simplifies the model and immediately places the trade-off computation problem within NP. Unfortunately, we show that even this restricted version is NP-complete. Finally, we show that the trade-off problem parameterized by the number of transitions is W[1]-hard, meaning that there is likely no algorithm running in a fixed polynomial for constant number of transitions.

Comments:

This paper is also available from the ACM Digital Library.

Availability:

The paper is available in PDF (924k).

See information on file formats.

[Google Scholar search]

Related papers:

PebblesInapprox_WADS2017 (Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs)