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.