Divide-and-conquer checkpointing for arbitrary programs with no user annotation
Divide-and-conquer checkpointing for arbitrary programs with no user annotation
复制标题
DOI：
10.1080/10556788.2018.1459621
复制
发表时间：
2017-08
影响因子：
2.2
通讯作者：
J. Siskind;Barak A. Pearlmutter
中科院分区：
文献类型：
--
作者：
J. Siskind;Barak A. Pearlmutter
经典的反向模式自动微分（AD）在原始计算的运算计数中仅施加小的常数因子开销，但是在最坏的情况下，存储需求与原始计算消耗的时间成比例地增长。这种存储爆炸可以通过检查点来改善，检查点是一种在执行间隔内对经典反向模式AD的应用程序进行重新排序以权衡空间与时间的过程。以分治方式将检查点应用于策略性选择的嵌套执行间隔可以将经典的反向模式AD分解为多个阶段，这些阶段可以将存储中的最坏情况增长从线性减少到次线性。这样做已经完全自动化，只有特别简单的计算形式，检查点跨越执行间隔，从一组有限的程序结构。在这里，我们将展示如何将该技术自动化用于任意计算。本质的创新是在语言实现本身的级别上应用该技术，从而允许检查点跨越任何执行间隔。
Classical reverse-mode automatic differentiation (AD) imposes only a small constant-factor overhead in operation count over the original computation, but has storage requirements that grow, in the worst case, in proportion to the time consumed by the original computation. This storage blowup can be ameliorated by checkpointing, a process that reorders application of classical reverse-mode AD over an execution interval to tradeoff space vs. time. Application of checkpointing in a divide-and-conquer fashion to strategically chosen nested execution intervals can break classical reverse-mode AD into stages which can reduce the worst-case growth in storage from linear to sublinear. Doing this has been fully automated only for computations of particularly simple form, with checkpoints spanning execution intervals resulting from a limited set of program constructs. Here we show how the technique can be automated for arbitrary computations. The essential innovation is to apply the technique at the level of the language implementation itself, thus allowing checkpoints to span any execution interval.