DAG reversal is NP-complete

被引:12
|
作者
Naumann, Uwe [1 ]
机构
[1] Rhein Westfal TH Aachen, LuFG Informat Software & Tools Computat Engn 12, D-52056 Aachen, Germany
基金
英国工程与自然科学研究理事会;
关键词
Data-flow reversal; NP-completeness; Adjoint code;
D O I
10.1016/j.jda.2008.09.008
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Runs of numerical computer programs can be visualized as directed acyclic graphs (DAGs). We consider the problem of restoring the intermediate values computed by such a program (the vertices in the DAG) in reverse order for a given upper bound on the available memory. The minimization of the associated computational cost in terms of the number of performed arithmetic operations is shown to be NP-complete. The reversal of the data-flow finds application, for example, in the efficient evaluation of adjoint numerical programs. We derive special cases of numerical programs that require the intermediate values exactly in reverse order, thus establishing the NP-completeness of the optimal adjoint computation problem. Last but not least we review some state-of-the-art approaches to efficient dataflow reversal taken by existing software tools for automatic differentiation. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:402 / 410
页数:9
相关论文
共 50 条