We study an extension of the well-known red-blue pebble game (RBP) with partial computation steps, inspired by the recent work of Sobczyk. While the original RBP assumes that we need to have all the inputs of an operation in fast memory at the same time, in many concrete computations, the inputs can be aggregated one by one into the final output value. These partial computation steps can enable pebbling strategies with much smaller I/O cost, and in settings where such a step-by-step aggregation is possible, this extended red-blue pebble game offers a much more realistic cost model. We establish the fundamental properties of this partial-computing red-blue pebble game (PRBP), and compare it to the original RBP. We begin with some simple examples where allowing partial computations can decrease the optimal I/O cost. It is also shown that the cost can decrease by up to a linear factor this way, but in general, it is NP-hard to decide whether partial computations allow for a smaller cost in a specific DAG. We then discuss how $S$-partitions, a crucial tool for deriving I/O lower bounds in RBP, can be adapted to the PRBP model. These new tools are then used to establish lower bounds on the I/O cost of some prominent computational tasks. Finally, we also adapt a hardness result from RBP, showing that the optimum cost is still NP-hard to approximate in PRBP to any reasonable factor.

翻译：我们研究了在部分计算步骤扩展下的经典红蓝卵石游戏（RBP），该扩展受到Sobczyk近期工作的启发。传统RBP假设操作的所有输入必须同时存在于快速内存中，但在许多实际计算中，输入可以逐个累积到最终输出值。这些部分计算步骤能够实现I/O成本显著更低的卵石放置策略，在支持这种逐步累积的场景中，扩展的红蓝卵石游戏提供了更贴近现实的成本模型。我们建立了这种部分计算红蓝卵石游戏（PRBP）的基本性质，并将其与原始RBP进行比较。首先通过简单示例说明允许部分计算可降低最优I/O成本，并证明成本最多可因此线性降低，但一般而言，判定特定有向无环图（DAG）中部分计算能否降低成本属于NP难问题。随后探讨了如何将S-划分（RBP中推导I/O下界的关键工具）适配至PRBP模型，并运用新工具为若干重要计算任务建立I/O成本下界。最后，我们将RBP的硬度结果扩展至PRBP，证明在PRBP中仍无法以任何合理近似比逼近最优成本。