AIB 2007-18: Call Tree Reversal is NP-Complete

The following technical report is available from http://aib.informatik.rwth-aachen.de: Call Tree Reversal is NP-Complete Uwe Naumann AIB 2007-18 The data-flow of a numerical program is reversed in its adjoint. We discuss the combinatorial optimization problem that aims to find optimal checkpointing schemes at the level of call trees. For a given amount of persistent memory the objective is to store selected arguments and/or results of subroutine calls such that the overall computational effort (the total number of floating-point operations performed by potentially repeated forward evaluations of the program) of the data-flow reversal is minimized. Call Tree Reversal is shown to be NP-complete.