Guillaume Aupy

Julien Herrmann

Paul Hovland

Yves Robert

Optimal Multistage Algorithm for Adjoint Computation

Keywords: Optimal algorithms, Out-of-core, Adjoint Computation, Program Reversal, Automatic Differentiation Algorithmes optimaux, out-of-core, calcul d'adjoints, retournement de programmes, différentiation automatique

We reexamine the work of Stumm and Walther on multistage algorithms for adjoint computation. We provide an optimal algorithm for this problem when there are two levels of checkpoints, in memory and on disk. Previously, optimal algorithms for adjoint computations were known only for a single level of checkpoints with no writing and reading costs; a well-known example is the binomial checkpointing algorithm of Griewank and Walther. Stumm and Walther extended that binomial checkpointing algorithm to the case of two levels of checkpoints, but they did not provide any optimality results. We bridge the gap by designing the first optimal algorithm in this context. We experimentally compare our optimal algorithm with that of Stumm and Walther to assess the difference in performance.

Introduction

The need to efficiently compute the derivatives of a function arises frequently in many areas of scientific computing, including mathematical optimization, uncertainty quantification, and nonlinear systems of equations. When the first derivatives of a scalar-valued function are desired, so-called adjoint computations can compute the gradient at a cost equal to a small constant times the cost of the function itself, without regard to the number of independent variables. This adjoint computation can arise from discretizing the continuous adjoint of a partial differential equation [START_REF] Giles | An introduction to the adjoint approach to design[END_REF][START_REF] Jameson | Aerodynamic shape optimization using the adjoint method[END_REF] or from applying the so-called reverse or adjoint mode of algorithmic (also called automatic) differentiation to a program for computing the function [START_REF] Griewank | Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation[END_REF]. In either case, the derivative computation applies the chain rule of differential calculus starting with the dependent variables and propagating back to the independent variables. Thus, it reverses the flow of the original function evaluation. In general, intermediate function values are not available at the time they are needed for partial derivative computation and must be stored or recomputed [START_REF] Giering | Recomputations in reverse mode AD[END_REF].

A popular storage or recomputation strategy for functions that have some sort of natural "time step" is to save (checkpoint) the state at each time step during the function computation (forward sweep) and use this saved state in the derivative computation (reverse sweep). If the storage is inadequate for all states, one can checkpoint only some states and recompute the unsaved states as needed. Griewank and Walther prove that given a fixed number of checkpoints, the schedule that minimizes the amount of recomputation is a binomial checkpointing strategy [START_REF] Griewank | Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation[END_REF][START_REF] Griewank | Algorithm 799: Revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation[END_REF]. The problem formulation they used implicitly assumes that reading and writing checkpoints are essentially free, but the number of available checkpoints is limited (see Problem 1 below). In [START_REF] Stumm | Multistage approaches for optimal offline checkpointing[END_REF], Stumm and Walter consider the case where checkpoints can be written to either memory or disk. The number of checkpoints to disk is effectively unlimited but the time to read or write a checkpoint can no longer be ignored (see Problem 2). We consider the same situation. In contrast to Stumm and Walther, however, we do not restrict ourselves to a single binomial schedule but instead prove that there exists a time-optimal schedule possessing certain key properties (including no checkpoints written to disk after the first checkpoint to memory has been written), and we provide a polynomial time algorithm for determining an optimal schedule.

The rest of this paper is organized as follows. Section 2 introduces terminology and the general problem framework. Section 3 establishes several properties that must hold true for some optimal schedule and provides an algorithm, Disk-Revolve, for identifying this schedule. Section 4 compares our checkpointing schedule with that of Stumm and Walther. We conclude with some thoughts on future research directions.

Framework

2.1 The AC problem

F0 F1 • • • F l-2 F l-1 F0 F1 F2 • • • Fl-1 Fl x 0 x 1 x 2 x l-2 x l-1 x l xl+1 xl xl-1 x3 x2 x1 x0 x 0 x 1 x 2 x l-1 x l
Figure 1: The AC dependence graph.

Definition 1 (Adjoint Computation (AC) [START_REF] Griewank | Algorithm 799: Revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation[END_REF][START_REF] Stumm | Multistage approaches for optimal offline checkpointing[END_REF]). An adjoint computation (AC) with l time steps can be described by the following set of equations:

F i (x i ) = x i+1 for 0 ≤ i < l (1) Fi (x i , xi+1 ) = xi for 0 ≤ i ≤ l (2)
The dependencies between these operations1 are represented by the graph G = (V, E) depicted in Figure 1.

The F computations are called forward steps. The F computations are called backward steps. If xl is initialized appropriately, then at the conclusion of the adjoint computation, x0 will contain the gradient with respect to the initial state (x 0 ). Definition 2 (Platform). We consider a platform with three storage locations:

• Buffers: there are two buffers, the top buffer and the bottom buffer. The top buffer is used to store a value x i for some i, while the bottom buffer is used to store a value xj for some j. For a computation (F or F) to be executed, its input values have to be stored in the buffers. Let B and B ⊥ denote the content of the top and bottom buffers. In order to start the execution of the graph, x 0 must be stored in the top buffer and xl+1 in the bottom buffer. Hence, without loss of generality, we assume that at the beginning of the execution, B = {x 0 } and B ⊥ = {x l+1 }.

• Memory: there are c m slots of memory where the content of a buffer can be stored. The time to write from buffer to memory is w m . The time to read from memory to buffer is r m . Let M be the set of x i and xi values stored in the memory. The memory is empty at the beginning of the execution (M = ∅).

• Disks: there are c d slots of disks where the content of a buffer can be stored. The time to write from buffer to disk is w d . The time to read from disk to buffer is r d . Let D be the set of x i and xi values stored in the disk. The disk is empty at the beginning of the execution (D = ∅).

Memory and disk are generic terms for a two-level storage system, modeling any platform with a dual memory system, including (i) a cheap-to-access firstlevel memory, of limited size; and (ii) a costly-to-access second-level memory, whose size is very large in comparison with the first-level memory. The pair (memory, disk) can be replaced by (cache, memory) or (disk, tape) or any relevant hardware combination.

Intuitively, the core of the AC problem is the following. After the execution of a forward step, its output is kept in the top buffer only. If it is not saved in memory or disk before the next forward step, it is lost and will have to be recomputed when needed for the corresponding backward step. When no disk storage is available, the problem is to minimize the number of recomputations in the presence of limited (but cheap-to-access) memory slots. When disk storage is added, the problem becomes even more challenging: saving data on disk can save some recomputation, and a trade-off must be found between the cost of disk accesses and that of recomputations.

The problem with only memory and no disk (Problem 1: Prob(l, c m ) below) has been solved by Griewank and Walther [START_REF] Griewank | Algorithm 799: Revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation[END_REF], using a binomial checkpointing algorithm called Revolve. In accordance to the scheduling literature, we use the term makespan for the total execution time.

Problem 1 (Prob(l, c m )). We want to minimize the makespan of the AC problem with the following parameters:

Initial state: AC graph: size l Steps: u f , u b Memory: c m , w m = r m = 0 M ini = ∅ Disks: c d = 0 Buffers: B , B ⊥ B ini = {x 0 }, B ⊥ ini = {x l+1 }
In this paper we consider the problem with limited memory and infinite disk (Problem Prob ∞ (l, c m , w d , r d ) below). The main goal of this paper is to provide the first optimal algorithm for Prob ∞ (l, c m , w d , r d ).

Problem 2 (Prob ∞ (l, c m , w d , r d )). We want to minimize the makespan of the AC problem with the following parameters:

Initial state: AC graph: size l Steps: u f , u b Memory: c m , w m = r m = 0 M ini = ∅ Disks: c d = +∞, w d , r d D ini = ∅ Buffers: B , B ⊥ B ini = {x 0 }, B ⊥ ini = {x l+1 } RR n°8721

Algorithm model

We next detail the elementary operations that an algorithm can perform.

F i Execute one forward computation F i (for i ∈ {0, . . . , l -1}). Note that by definition, for F i to occur, x i should be in the top buffer before (i.e., B = {x i }) and x i+1 will be in the top buffer after (i.e., B ← {x i+1 }). This operation takes a time time

(F i ) = u f .
Fi Execute the backward computation Fi (i ∈ {0, . . . , l}). Note that by definition, for Fi to occur, x i should be in the top buffer and xi+1 in the bottom buffer (i.e., B = {x i } and B ⊥ = {x i+1 }) and xi will be in the bottom buffer after (i.e., B ⊥ ← {x i }). This operation takes a time time( Fi ) = u b .

W m i

Write the value x i of the top buffer into the memory. Note that by definition, for W m i to occur, x i should be in the top buffer (i.e., B = {x i }) and there should be enough space for x i in the memory (i.e., |M| < c m ); x i will be in the memory after (i.e., M ← M ∪ {x i }). This operation takes time time(

W m i ) = w m .
D m i Discard the value x i of the memory (i.e., M ← M\{x i }). This operation takes a time time(D m i ) = 0. This operation is introduced only to clarify the proofs, since a D m i operation is always immediately followed by a W m i operation. In other words, all write operations overwrite the content of some memory slot, and we simply decompose an overwrite operation into a discard operation followed by a write operation.

R m i Read the value x i in the memory, and put it into the top buffer. Note that by definition, for R m i to occur, x i should be in the memory (i.e., x i ∈ M) and x i will be in the top buffer after (i.e., B = {x i }). This operation takes a time time(R m i ) = r m .

W d i Write the value x i of the top buffer into the disk. Note that by definition, for W d i to occur, x i should be in the top buffer (i.e., B = {x i }) and x i will be in the disk after (i.e., D ← D ∪ {x i }). This operation takes a time time(

W d i ) = w d .
R d i Read the value x i in the disk and puts it into the top buffer. Note that by definition, for R d i to occur, then x i should be in the disk (i.e., x i ∈ D) and x i will be in the top buffer after (i.e., B = {x i }). This operation takes a time time(R d i ) = r d .

D d i Discard the value x i of the disk (i.e., D ← D\{x i }). This operation takes a time time(D d i ) = 0. The same comment as for D m i operations holds: all disk writes, just as memory writes, are overwrite operations, which we decompose as indicated above. Both discard operations are introduced for the clarity of the proofs.

For conciseness, we let F i→i denote the sequence

F i • F i+1 • . . . • F i .
Because of the shape of the AC dependence graph (see Figure 1), any algorithm solving Problem 2 will have the following unique structure,

S l • Fl • S l-1 • Fl-1 • . . . • S 0 • F0 , (3)
where for all i, S i is a sequence of operations that does not contain Fi (hence the Fi following S i is the first occurrence of Fi ).

Definition 3 (iteration i). Given an algorithm that solves the AC problem, we let iteration i (for i = l . . . 0) be the sequence of operations S i • Fi . Let l i be the execution time of iteration i.

With this definition, the makespan of an algorithm is l i=0 l i .

3 Solution of Prob ∞ (l, c m , w d , r d )

In this section we show that we can compute in polynomial time the solution to Prob ∞ (l, c m , w d , r d ). To do so, we start by showing some properties on an optimal algorithm.

• We show that iteration l starts by writing some values x i on disk checkpoints before doing any memory checkpoints (Lemma 6).

• Once this is done, we show that we can partition the initial AC graph into connected subgraphs by considering the different subgraphs between consecutive disk checkpoints (Proposition 1). Each of these subgraphs can be looked at (and solved) independently.

• We give some details on how to solve the problem on all subgraphs. In particular we show that (i) we do not write any additional values to disks in order to solve them (Lemma 2); and (ii) we show that similarly to the first iteration, the algorithm writes some values to memory checkpoints and we can partition these subgraphs by considering the different subgraphs between memory checkpoints (Lemma 3).

• To solve these subgraphs, we introduce new problems (Problems 3 and 4) that inherit the properties of the general problem.

• We show how to compute the size of the different connected subgraphs through a dynamic programming algorithm ( § 3.2).

Properties of an optimal algorithm

We show here some dominance properties. That is, there exist optimal algorithms that obey these properties, even though not all optimal algorithms do.

Lemma 1. There exists an optimal solution that has the following structure,

S l • Fl • S l-1 • Fl-1 • . . . • S 0 • F0
, and that satisfies (P0):

• • • F j i • • • F i-1 F i • • • • • • Fi Fi+1 • • • x ji x ji+1 x i-1 x i x i+1 xi xi+1 xi+2 x i x i+1
Figure 2: After executing Fi+1 , x i+1 (blue) is in the top buffer, and xi+1 (red) is in the bottom buffer. For the remainder of the execution, the algorithm will not need the grey area anymore; hence it will need to fetch x ji (green) from a checkpoint slot.

(i) There are no D d -type operations (we do not discard from disks).

(ii) Each D m -type operation is immediately followed by a W m -type operation (we discard a value from memory only to overwrite it).

(iii) Each R-type operation is not immediately followed by another R-type operation.

(iv) Each W m -type operation (resp. W d -type operation) is not immediately followed by another W m -type operation (resp. W d -type operation).

(v) Each W m -type operation is not immediately followed by another D m -type operation.

(vi) There are no F-type operations in any S i sequence (backward steps are not recomputed);

(vii) During S i (i < l), there are no F i to F l-1 operations (nor actions involving x i+1 to x l );

(viii) In particular, for all i < l, the first operation of sequence S i is a Rtype operation; in other words, there exist j i and s ∈ {m, d} such that S i = R s ji Si ;

(ix) For i such that there is a W m i operation, there is at least one R m i operation between a W m i and a D m i operations.

(x) If l > 0, the first operation of the algorithm is a W -type operation.

Proof. Some of the intuitions of this lemma can be grasped from Figure 2. Note that removing an operation from the optimal solution cannot increase the makespan.

(i) We have an infinite number of disk slots available: there is no need to discard any value from it.

(ii) Discard a value from the memory is useless if the memory is not full and if we do not need to write a new value in it.

(iii) If we had two consecutive reads in the sequence, then the only action of the first read would be to put some value x i in the top buffer. However, the second read would immediately overwrite this value, making the first read unnecessary. Thus, the first read can be removed.

(iv) It is useless to write the same value in the same storage twice in a row.

(v) Similar to the previous point, from (ii) a D m operation is immediately followed by a W m operation; hence this would be writing twice in the same storage in a row.

(vi) The reason that there are no F-type operations in all S i is that we have a dedicated buffer for the xi values. The only operations that use the xi values are F-type operations. Also, to execute Fi , we need only the value of xi+1 that is already stored in the bottom buffer at the beginning of S i . Hence, removing the additional F-type operations from S i can only improve the execution time.

(vii) Operations involving F i to F l-1 (or their output values) during S i would be useless; see Figure 2.

(viii) After the execution of Fi , the content of the top buffer is x i . The value x i is useless for Fi-1 (see the previous point). Hence, at the begining of S i-1 , we need to read the content of a storage slot before executing any F-type, F-type, or W -type operation. Furthermore, because of property (ii), doing a D-type operation will not permit an R-type operation before the next W -type operation. Hence, the first operation of sequence S i is necessarily an R-type operation.

(ix) Assume that there exists i such that there are no R m i operations between a W m i and a D m i operations. It is useless to write the value x i in the memory and discard it without reading it in between. Thus the W m i and D m i operations can be removed at no additional time delay.

(x) The first operation of the solution cannot be an R-type or a D-type operation since at the beginning of the execution the memory and the disk are empty. If l > 0, the forward step F 0 has to be executed before the backward step Fl . Thus the first operation cannot be an F-type operation. Now assume that the first operation is an F-type operation. It then has to be F 0 . After the execution of F 0 , the value x 1 is in the top buffer, and the value x 0 is not stored anywhere. There is no way to recompute the value x 0 , thus to execute F0 , which would then prevent computing x0 (absurd). Thus, at the beginning of the execution, we have to store the value x 0 either in the memory or in the disk, and the first operation of the algorithm is a W -type operation.

Lemma 2. There exists an optimal solution to Problem 2 that satisfies (P0) and (P1):

(i) All disk checkpoints are executed during the first iteration S l .

(ii) For all i,

0 ≤ i ≤ l -1, W d i operations are executed before W m i operations.
Proof. Suppose S is an optimal solution that satisfies (P0). We will show that we can transform it into a solution that satisfies (P0) and (P1):

(i) Iteration l passes through all forward computations. If a value x i is saved on disk later on during the algorithm, we could as well save it after the first execution of F i-1 (in S l ) with no additional time delay, since we have an infinite number of slots on disk.

(ii) Let assume that there exists i,

0 ≤ i ≤ l -1, such that W m i is executed before W d i in S.
By definition, when W m i is executed, the value x i is stored in the top buffer. Thus we can execute W d i right before W m i , instead of later, at no additional time delay, since the amount of available disk slots is infinite. This new solution still satisfies (P0).

The following lemma and its proof are inspired by Lemma 3.1 by Walther [START_REF] Walther | Program reversal schedules for single-and multi-processor machines[END_REF].

Lemma 3 (Memory Checkpoint Persistence).

There exists an optimal solution to Problem 2 that satisfies (P0), (P1), and (P2):

(i) Let i < l; if W m
i is executed, then there are no D m i operations until after the execution of Fi (that is, until the beginning of iteration i -1).

(ii) Moreover, until that time, no operation involving F 0 to F i-1 or values x 0 to x i-1 is taken.

The intuition behind this result is that if we were to discard the value x i before executing Fi+1 , then a better solution would have stored x i+1 in the first place. Furthermore, because r m = 0, we can show that until Fi , all actions involving computations F 0 to F i-1 or values x 0 to x i-1 do not impact the actions that lead to an Fj operation, j ≥ i, and thus can be moved to a later time at no additional time delay (and potentially reducing the makespan of the algorithm).

Proof. Let S be an optimal solution that satisfies (P0) and (P1) but not (P2). We can transform it into a solution that satisfies (P0), (P1), and (P2). We iteratively transform S to increase the number of i values respecting (P2), without increasing the makespan of the schedule. This transformation can be applied as many times as necessary to reach a schedule that satisfies (P2). Assume, first, that S does not satisfy (P2(i)). Let x i be the first value such that at some point during S, x i is stored in the memory and discarded before executing Fi . Thus we can write

S = S 0 • W m i • S 1 • D m i • S 2 • Fi • S 3
, where S 0 , S 1 , S 2 , and S 3 are sequences of operations that does not include Fi . Since S satisfies (P0(ix)), there is at least one R m i operation in S 1 . Let us prove that all these R m i operations are immediately followed by an F i operation.

• The R m i operations cannot be immediately followed by an F-type operation, because the only F-type operation allowed after an R m i operation is Fi (since the value x i would be in the top buffer) and there are no Fi in S 1 .

• According to (P0(ix)), the R m i operations cannot be immediately followed by another R-type operation.

• The R m i operations cannot be immediately followed by a D m -type operation because, according to (P0(ii)), the next operation would be a W mtype operation. However, since the value x i would be in the top buffer, the only W m -type operation allowed would be W m i , which is useless since the value x i is already in the memory.

• The R m i operations cannot be immediately followed by a D d -type operation because, according to (P0(i)), there are no D d -type operations in S.

• The R m i operations cannot be immediately followed by a W m -type operation, because the only W m -type operation allowed after an R m i operation is W m i (since the value x i would be in the top buffer), which is useless since the value x i is already in the memory.

• The R m i operations cannot be immediately followed by a W d -type operation, because the only W d -type operation allowed after an R m i operation is W d i (since the value x i would be in the top buffer), which is impossible according to (P1(ii)) since a W m i has already been executed before S 1 . So, all these R m i operations are immediately followed by an F-type operation; since the value x i is in the top buffer, this operation is F i . Thus, any R m i in S 1 is followed by F i .

Let us now focus on the first operation in S 1 . It cannot be a F-type (the only possible F-type is Fi ), W m -type ((P0(iv))), W d -type ((P1(ii))), or D-type ((P0(v))). Hence, the first operation in S 1 is either a R-type operation or a F-type operation (in which case, it is F i since B = {x i } at the beginning of S 1 ).

• Assume that S 1 = F i • S 1 . Let S 1 be the sequence S 1 where every occurrence of R m i • F i has been replaced by R m i+1 . We know that the schedule

S = S 0 • F i • R m i+1 • S 1 • D m i+1 • S 2 • Fi • S 3
is correct and has a makespan at least as good as S (since there is at least one occurrence of R m i • F i in S 1 ).

• • • F * • • • F i-1 • • • F * • • • • • • Fi • • • F * • • • x * x * x i-1 x i x * x * x * x * xi+1 xi x i x * A B
Figure 3: Consider a subsequence of S 1 comprised between two consecutive Rtype operations: R s j and R s j . If j ≥ i, then by definition the subsequence will activate only parts of area B (and not overwrite any checkpoint from area A). If j < i, then we have shown that the subsequence will activate only parts of the area A (no forward sweep through F i-1 ).

• Assume that there exist j and s (either equal to m or d) such that S 1 = R s j • S 1 . Let S 1 be the sequence S 1 where every occurrence of R m i • F i has been replaced by R m i+1 . We know that the schedule

S = S 0 • F i • R m i+1 • R s j • S 1 • D m i+1 • S 2 • Fi • S 3
is correct and has a makespan at least as good as S (since there is at least one occurrence of R m i • F i in S 1 ).

Hence we were able to transform S into S' without increasing the makespan, so that the number of values i, 0 ≤ i < l, that does not respect (P2(i)) decreases.

We repeat this transformation until the new schedule satisfies (P2(i)).

Let us now consider (P2(ii)). Let S be an optimal solution that satisfies (P0), (P1), and (P2(i)). Let i, 0 ≤ i < l, such that there exists W m i in S. We can write

S = S 0 • W m i • S 1 • Fi • S 2 • D m i • S 3
, where S 1 is a sequence of operations that do not include D m i . There are no F i-1 in S 1 because their only impact on the memory is to put the value x i in the top buffer which could be done with R m i for no time delay. Consider now two consecutive R-type operations of S 1 . Because there are no F i-1 operations in S 1 , we know that between these two R-type operations, and with the definitions of A and B in Figure 3, either only elements of A are activated (and no element of B) or only elements of B are activated (and no element of A).

Consider now the last R-type operation R s j of S 1 such that j < i (s being equal to m or d). All W m -type operations written after this operation and before the next R-type operation of S 1 involve some values in A. Hence by (P2(i)), they are not discarded until after Fi . Furthermore, because R s j is the last such operation, we know that they are not used in S 1 either. Hence we can move this sequence of operations (the sequence between R s j and the next R-type operation) right after Fi at no additional time delay. This operation can be repeated until there are no more such operations in S 1 . We then proceed with RR n°8721 these operations recursively in the appearance order of the W m i . This shows that we can construct an optimal schedule that satisfies (P2(ii)). Lemma 4. There exists an optimal algorithm for Problem 2 that satisfies (P0), (P1), (P2), and (P3): There is only one R-type operation (the first one) in every iteration S i , where i < l.

Proof. Let S be an optimal schedule that satisfies (P0), (P1), and (P2). We show that we can transform it into an optimal schedule that satisfies (P0-3).

To show this result, for any i ≥ 0, we inductively show that if we have a solution such that the property is true in iterations l to i + 1, then we can transform it into a solution such that this property in true in iterations l to i.

Assume that S does not satisfies (P3). Let S i be the first iteration of S that includes more than one R-type operation.

If i = 0, then all R-type operations are R 0 by (P2). Hence we can remove any of them until there is only one.

Otherwise assume that i ≥ 1. Let R s1 j1 and R s2 j2 (where s 1 , s 2 ∈ {m, d}) be the last two R-type operations in S i . According to (P0(iv)), we know that iteration i does not involve x i+1 to x l , so j 1 ≤ i and j 2 ≤ i. We can write

S i = S (1) • R s1 j1 • S (2) • R s2 j2 • S (3) ,
where S (2) and S (3) are sequences of operations that do not include any R-type operation. According to (P0(vi)), there are no F-type operations in S (2) and S (3) either. Since the value x j2 is in the top buffer at the beginning of S (3) , we know that the first F-type operation of S (3) has to be F j2 . We know that the first operation after S i is Fi . Thus the last F-type operation of S (3) is F i-1 .

Since there are no R-type operations in S (3) , we know that the sequence S (3) includes all F-type operations from F j2 to F i-1 .

Similarly, the sequence S (2) includes all F-type operations from F j1 to F jmax operations with j max ≤ i -1.

• If j max ≥ j 2 , we note j min = min(j 1 , j 2 ) and s min the corresponding value of s 1 or s 2 . Iteration S i includes each F-type operations from F jmin to F i (possibly twice). Let us build the sequence of operations S (4) from the sequence F jmin→i where each operation F k if immediately followed by W m k if W m k is present in either S (2) or S (3) (see Figure 4 for this transformation). Thus we know that the sequence S i = S (1) • R smin jmin • S (4) will have the exact same impact on the memory as S i without increasing the makespan. Transforming iteration S i into sequence S i reduces by one the number of readings in iteration i.

• If j max < j 2 , sequences of operations S (2) and S (3) are disjoint. Thus S (2) has no impact on iteration i and can be moved to the beginning of the next operation. Thus transforming iteration S i into S i = S (1) • R s2 j2 • S (3) and moving R s1 j1 • S (2) to the beginning of iteration S i+1 will not increase the makespan of S and will reduce by one the number of readings in iteration i.

RR n°8721 S(2) = R s 0 F 1 W m 1 F 2 F 3 F 4 F 5 W m 5 F 6 W m 6 S(3) = R s 3 F 4 F 5 F 6 W m 6 F 7 F 8 F 9 W m 9 S(4) = R s 0 F 1 W m 1 F 2 F 3 F 4 F 5 W m 5 F 6 W m 6 F 7 F 8 F 9 W m 9
Hence we have shown that until there is only one R-type operation in iteration i, we can reduce by one the number of R-type operations in iteration i (and leave as they were iterations l to i + 1). Thus, if the property is true in iteration l to i + 1, then we can transform it into a solution such that this property in true in iteration l to i. This concludes the proof.

Corollary 1 (Description of iteration i < l). Given an optimal algorithm for Problem 2 that satisfies (P0-3), each iteration i < l can be written as

S i = R si ji Si (4)
for some j i and for some s i ∈ {m, d}, where Si is composed only of F-type, W mtype, and D m -type operations (possibly empty). Furthermore, it goes through all operations F j for j from j i to i -1.

Lemma 5 (Description of iteration l).

There exists an optimal algorithm for Problem 2 that satisfies (P0-3) and (P4): There are no R-type operations in iteration S l . Hence, every F-type operation is executed once and only once in iteration S l .

Proof. Let S be an optimal schedule that satisfies (P0-3). We can write

S = S l • Fl • S l-1 • Fl-1 • . . . • S 0 • F0 .
We know that at the end of the execution of S l , the top buffer contains the value x l and the bottom buffer contains the value xl+1 . Let M l and D l be the state of the memory and the disk at the end of the execution of S l . Let S l be the sequence of operations F 0→l-1 where every operation F i is immediately followed by (i)

W d i W m i if x i ∈ M l ∩ D l ; (ii) else, W m i if x i ∈ M l ; (iii) else W d i if x i ∈ D l .
At the end of the execution of S l , the memory and the disk will be in the states M l and D l . Furthermore, if x i ∈ M l (resp. if x i ∈ D l ), the sequence S l contains the operation W m i (resp. W d i ). Thus all W -type operations of S l are in S l . Moreover, S l has to contain all the forward steps from F 0 to F l-1 . Thus, every operation in S l is included in S l . Hence, the sequence S = S l • Fl • S l-1 • Fl-1 • . . . • S 0 • F0 is valid and has a makespan not larger than S. S is then optimal and satisfies (P0-4). Lemma 6. There exists an optimal algorithm for Problem 2 that satisfies (P0-4) and (P5): Given i, j, 0 ≤ i, j ≤ l -1, all W d i operations are executed before any W m j operation.

Hence, during the first iteration S l , we first assign the disk checkpoints before assigning the memory checkpoints.

Proof. Let S be an optimal algorithm that satisfies (P0-4), but not (P5). We show that we can transform it into an optimal algorithm that also satisfies (P5) without increasing the makespan.

By contradiction, assume that there exist i and j such that W m i is executed before W d j . According to (P1(i)), every write on the disk occurs during the first iteration S l . Thus W m i also occurs in iteration S l . According to (P4), the F-type operations are not re-executed in iteration S l . Thus, necessarily, i < j.

According to (P0(ix)), since the algorithm wrote the value x i in the memory and the value x j in the disk, they are read later in the schedule. Let S im be a step when R m i occurs and S i d a step when R d j occurs. Then we have: i ≤ i m by (P0(iv)) and j ≤ i d by (P0(iv)). Finally, there is only one R-type operation per step (Corollary 1); thus i m = i d .

Assume first that i m > i d . From Corollary 1, the first operation of S im is R m i . Thus the value x i is in the top buffer at the beginning of S im . Furthermore, by definition of the steps, the value x im has to be in the top buffer at the end of S im . Since there are no other R-type operations in S im , all forward steps from F i to F im are executed in S im . In particular F j-1 is executed in S im . Let n be the number of consecutive F-type operations right before F j-1 . Thus S im has the shape:

S im = R m i • S 1 • F (j-n)→(j-1) • S 2
where the last operation of S 1 is not a F-type operation. Recall that the time for a disk read is r d and for a forward step is u f .

• Assume that (n + 1)u f > r d . Then the sequence R m i • S 1 • R d j • S 2
has a smaller execution time than S im contradicting the optimality.

• Assume that (n + 1)u f ≤ r d . According to Corollary 1, if S 1 is not empty, then its last operation is W m j-n-1 (if it is empty, then i = jn -1). (P2) ensures that x j-n-1 will not be discarded until after x j has become useless (after Fj ). Since (n+1)u f ≤ r d , we could replace all future instances of R d j by R m j-n-1 •F (j-n)→j . Hence W d j would be useless, which would contradict the optimality of the schedule. Hence, i m < i d . In particular, this is true for any i m and i d . Then we can show with similar arguments that this is true until Fi . Hence, there are not any R d j until after Fi . Since j > i, this means that there will not be anymore R d j operations at all. Finally, this shows that the execution of W d j is useless and can be removed.

Proposition 1 (Disk Checkpoint Persistence). Given an optimal algorithm for Problem 2 that satisfies (P0-5), then after any operation W d i , there are no F j

RR n°8721

operations for 0 ≤ j ≤ i-1 (nor actions involving the values x j for 0 ≤ j ≤ i-1) until after the execution of Fi .

Proof. Let S be an optimal algorithm that satisfies (P0-5). Assume by contradiction that S includes W d i and there exists j ≥ i and i < i such that iteration S j involves F i . In particular, according to Corollary 1, it involves F i-1 . According to Corollary 1, there exist k, s ∈ {m, d}, and n maximum such that

S j = R s k S 1 • F (i-1-n)→(i-1) • S 2 . We can first show that r d > n. Indeed, otherwise, S 1 • R d i • S 2
has a smaller execution time than does S j for the same result, contradicting the optimality. Let us now show that we can remove all appearances of R d i in the schedule, hence decreasing the execution time, which would contradict the optimality of the algorithm.

• Consider the occurrence of R d i after S j . By maximality of n, if S 1 is not empty, then the last operation of

S 1 is W m i-1-n (Corollary 1). If S 1 is empty, then k = i -1 -n and s = m (otherwise we could replace R d k F (i-1-n)→(i-1
) by R d i which would contradict the optimality of the algorithm). Thus, in both cases the value x i-1-n is stored in the memory during S j , and (P2) ensures that it will not be discarded until after x i-1-n has become useless (after Fi ). Because r d > n, we can replace all later appearances of R d i by R m i-1-n F (i-1-n)→(i-1) at no additional time delay.

• Let us now consider the eventual occurrences of R d i anterior to iteration j. Necessarily, all R d i anterior to S j are followed by F i (otherwise one of them is followed by W m i and it is not permitted by the memory checkpoint persistence property (P2)). Hence, we can store the value x i+1 in the disk instead of the value x i during S l (S l goes through all forward operation according to (P4)). Then, it is possible to replace all R d i F i operations by R d i+1 reducing the execution time.

Hence, we can decrease the execution time by removing all appearances of R d i in the schedule, which shows the contradiction.

Optimal execution times

We construct here a dynamic program that solves Problem 2 optimally. To do so we introduce two auxiliary dynamic programs during the construction. The time complexity of our optimal algorithm is O(l 2 ).

Definition 4 (Opt 0 (l, c m )). Let l ∈ N and c m ∈ N, Opt 0 (l, c m ) is the execution time of an optimal solution to Prob(l, c m ).

Note that Opt 0 (l, c m ) is the execution time of the routine Revolve(l, c m ), from Griewank and Walther [START_REF] Griewank | Algorithm 799: Revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation[END_REF].

Definition 5 (Opt ∞ (l, c m , w d , r d )). Let l ∈ N, c m ∈ N, w d ∈ R and r d ∈ R, Opt ∞ (l, c m , w d , r d ) is the execution time of an optimal solution to Prob ∞ (l, c m , w d , r d ).
To compute Opt ∞ (l, c m , w d , r d ), we first focus on the variant of Problem 2 where the input value x 0 is initially in both the top buffer and the disk:

Problem 3 (Prob (d) ∞ (l, c m , w d , r d ))
. We want to minimize the makespan of the AC problem with the following parameters:

Initial state: AC graph: size l Steps: u f , u b Memory: c m , w m = r m = 0 M ini = ∅ Disks: c d = +∞, w d , r d D ini = {x 0 } Buffers: B , B ⊥ B ini = {x 0 }, B ⊥ ini = {x l+1 } Definition 6 (Prob (d) ∞ (l, c m , w d , r d )). Let l ∈ N, c m ∈ N, w d ∈ R and r d ∈ R, Prob (d) ∞ (l, c m , w d , r d ) is the subproblem of Prob (d) ∞ (l, c m , w d , r d )
where the space of solution is restricted to the schedules that satisfy the following properties: (P6):

(i) (P0(i)), (P0(ii)), (P0(iii)), (P0(iv)), and (P0(v)) are matched.

(ii) Given i, there are no operations F j for i ≤ j ≤ l -1 after the execution of Fi .

(iii) (Memory and disk checkpoint persistence) Let s ∈ {m, d} and i < l, if W s i is executed, then there are no D s i until after the execution of Fi . Moreover no operations involving F 0 to F i-1 or values x 0 to x i-1 are taken until after the execution of Fi .

(iv) Let 0 ≤ i, j ≤ l -1. All W d i operations are executed before any W m j operation. Moreover, all W d i operations are executed during iteration l. Note that (P6) is a subset of (P0-5). Let Opt (d) ∞ (l, c m , w d , r d ) be the execution time of an optimal solution to Prob

(d) ∞ (l, c m , w d , r d ). Theorem 1 (Optimal solution to Prob ∞ (l, c m , w d , r d )). Let l ∈ N, c m ∈ N, w d ∈ R, and r d ∈ R. Opt ∞ (l, c m , w d , r d ) = min Opt 0 (l, c m ) w d + Opt (d) ∞ (l, c m , w d , r d ) Proof. Let A = Opt ∞ (l, c m , w d , r d ) B = min Opt 0 (l, c m ) w d + Opt (d) ∞ (l, c m , w d , r d ) RR n°8721
• If it is a W d -type, then it occurs before the first F-type according to (P6(iv))

• If it is a W m -type, then obviously c m > 0. If no W m -operation occured during iteration l, then at the beginning of iteration l -1, R d 0 is executed. Hence a better solution would be better to start with W m 0 and D m 0 at the beginning of iteration l -1, which contradicts the optimality of S ∞ occurs before the first F-type operation. Then two possibilities exist.

• The first operation in S (d) ∞ is W m 0 . Since S (d)
∞ satisfies (P6(iv)), there are no W d -type operations in S (d) ∞ . Thus no other value than x 0 will be stored in the disk during the execution. Furthermore, because x 0 is stored in memory, it will not be read from the disk (otherwise S (d)

∞ will not be optimal). Thus S (d)
∞ is also a solution to Prob

(d) 1 (l, c m , r d ) and Opt (d) ∞ (l, c m , w d , r d ) ≥ Opt (d) 1 (l, c m , r d ).
• Otherwise, the first operation in S

∞ is not W m 0 . Consider the first Wtype operation. Because it occurs before the first F-type operation, it cannot be W m 0 (otherwise it would be the first operation in S

∞ ), nor W d 0 (x 0 is already stored on disk). Let W s j (s ∈ {m, d}) be the first W -type operation in S (d) ∞ , then j > 0. We proved that there are no F-type operations before W s j in S

∞ . By definition, there are no W -type operations before W s j in S

∞ . Since before W s j the memory is empty, there are no D-type operations in S

∞ . Since the only value in one of the storage is x 0 (in the disk), the only possible R-type operation before W s j would be R d 0 . The only reason to execute R d 0 would be to perform F 0 . However, F 0 can be executed at the beginning of S

∞ at no cost, since the value x 0 is already in the top buffer. Thus, there are only F-type operations before W s j in S

∞ (P6(i)). According to (P6(iii)), after W s j , there are no operations involving values x 0 to x j-1 until after the operation Fj .

According to (P6(ii)), there are no operations involving values x j to x l after the operation Fj .

Since after the operation Fj the content of the top buffer is useless, the first operation after Fj has to be an R-type operation.

Moreover, since the only value from x 0 to x j-1 in one of the storage after Fj is x 0 (in the disk), it has to be R d 0 . Thus, based on all these considerations, S

∞ has the following shape:

S (d) ∞ = F 0→j • W s j • S 1 • R d 0 • S 2
where every index of the operations are increased by j (F i becomes F i+j , W

(m) i+j . . . ). S 1 is still valid and has the same makespan as S 1 . Then, the sequence

F 0→j •S 1 •R d 0 •S 2 is a solution to Prob (d) 1 (l, c m , w d , r d ).
By construction this sequence does not contain any W d -type operation since neither S 1 nor S 2 do. Its execution time is

ju f + Opt 0 (l -j, c m ) + r d + Opt (d) 1 (j -1, c m , r d ). Thus, for all 1 ≤ j ≤ l -1: Opt (d) 1 (l, c m , r d ) ≤ ju f + Opt 0 (l -j, c m ) + r d + Opt (d) 1 (j -1, c m , r d )}.
In particular it is smaller than the minimum over all j, hence the result.

Let us show that

A ≥ B. Let S (d)
1 be an optimal solution to Prob

(d) 1 (l, c m , r d ). S (d) 1
satisfies (P6) and does not contain any W d -type operations. Its makespan is Opt

(d) 1 (l, c m , r d ). First, note that if c m > 0, then there is a W m -type operation in iteration l of S (d) 1 .
Otherwise, if no W m -operation occured during iteration l, then at the beginning of iteration l -1, R d 0 is executed. Hence a better solution would be better to start with W m 0 and D m 0 at the beginning of iteration l -1, which contradicts the optimality of S is W m 0 . Because x 0 is stored in memory, it will not be read from the disk (otherwise S (d) ∞ will not be optimal). Thus S (d) ∞ is also a solution to Prob • Otherwise, the first operation in S (d) 1 is not W m 0 . Consider the first W -type operation. It occurs before the first F-type operation and hence cannot be W m 0 (otherwise it would be the first operation in S

). Let W m j (there are no W d -type operations) be the first W -type operation in S (d) 1 , j > 0. We proved that there are no F-type operations before W m j in S

∞ . By definition, there are no W -type operations before W m j in S

1 . Since the only value in one of the storage slots is x 0 (in the disk), the only possible R-type operation before W s j would be R d 0 . The only reason to execute R d 0 would be to perform F 0 . However, F 0 can be executed at the beginning of S (d) 1

at no cost, since the value x 0 is already in the top buffer. Thus, there are only F-type operations before W m j in S

∞ (P6(i)). According to (P6(iii)), after W m j , there are no operations involving values x 0 to x j-1 until after the operation Fj .

According to (P6(ii)), there are no operations involving values x j to x l after the operation Fj .

Since after the operation Fj , the content of the top buffer is useless, the

RR n°8721

first operation after Fj has to be an R-type operation. Moreover, since the only value from x 0 to x j-1 in one of the storage slots after Fj is x 0 (in the disk), it has to be R d 0 . Thus, based on all this considerations, S (d) 1 has the following shape:

S (d) 1 = F 0→j • W m j • S 1 • R d 0 • S 2
where (i) no operations involve values x 0 to x j-1 in S 1 and (ii) no operations involve values x j to x l in S 2 .

Let S 1 br the sequence W m j • S 1 , where every index of the operations is decreased by j (F i becomes F i-j , W m i becomes W m i-j ,. . . ). Then S 1 is a solution to Prob(lj, c m ), whose makespan is necessarily not smaller than Opt 0 (lj, c m , w d , r d ).

On the other hand, the sequence S 2 executes all the F-type operations from Fj-1 down to F0 with no operations involving values x j to x l . Furthermore, S 2 does not use disk slots, except the one already used by value x 0 . Thus S 2 is a solution to Prob (d) 1 (j -1, c m , r d ), and its makespan is greater than Opt (d) ∞ (j -1, c m , r d ). Finally, we have

Opt (d) ∞ (l, c m , w d , r d ) ≥ ju f +Opt ∞ (l-j, c m , w d , r d )+r d +Opt (d) 1 (j-1, c m , r d ); in particular it is smaller than B.
Note that if there is no W -type operation, because we do not use any additional disk slot, S

∞ is also a solution to Prob

w d + min 1≤j≤l-1 ju f +Opt ∞ (l -j, c m , w d , r d )+r d +Opt (d) 1 (j -1, c m , r d ) Opt (d) 1 (l, c m , r d ) = min Opt 0 (l, c m ) min 1≤j≤l-1 ju f + Opt 0 (l -j, c m ) + r d + Opt (d) 1 (j -1, c m , r d )
Proof. Theorem 1 states that:

Opt ∞ (l, c m , w d , r d ) = min Opt 0 (l, c m ) w d + Opt (d) ∞ (l, c m , w d , r d ) Let us show that if Opt ∞ (l, c m , w d , r d ) = w d +Opt (d) ∞ (l, c m , w d , r d ) < Opt 0 (l, c m ), then: Opt (d) ∞ (l, c m , w d , r d ) = min 1≤j≤l-1 {ju f +Opt ∞ (l-j, c m , w d , r d )+r d +Opt (d) 1 (j-1, c m , r d )}.

RR n°8721

Algorithm 1 1D-Revolve Let j such that

Opt (d) 1 (l, cm, r d ) = ju f + Opt 0 (l -j, cm) + r d + Opt (d) 1 (j -1, cm, r d ) 7:
S ← F 0→(j-1)

8:

S ← S • Shift (Revolve(l -j, cm), j) return S 12: end procedure the binomial checkpointing strategy Revolve when using more checkpoint slots than actually available in memory (and therefore storing the extra values onto disk). While their objective is different, their algorithm can still be viewed as an algorithm for multilevel checkpointing, and we use it as a comparison basis because it is the closest related work. In fact, to the best of our knowledge, it is the only known algorithm for multilevel checkpointing. (having more than l storage slots is useless).

Simulation setup

For the simulations we have tested our algorithm and Stumm and Walther's algorithm on AC graphs of size up to 20,000 with different numbers of memory checkpoints. In global ocean circulation modeling [START_REF] Heimbach | An efficient exact adjoint of the parallel MIT general circulation model, generated via automatic differentiation[END_REF], a graph of size 8,640 represents one year of results with an hourly timestep.

In the experiments, we normalize all time values by setting u f to 1. We take u b = 2.5 as a representative value [START_REF] Heimbach | An efficient exact adjoint of the parallel MIT general circulation model, generated via automatic differentiation[END_REF]. Here we present results for c m ∈ {2, 5, 10, 25} and w d = r d ∈ {1, 2, 5, 10}.

In Figure 5 we reproduce Stumm and Walther's results in order to study the behavior of SWA. We plot the execution time of SWA as a function of c d for a fixed graph size (note that we used a logarithmic scale for the horizontal axis for better readability). We compare it with the optimal solution Opt ∞ (l, c m , w d , r d ).

In Figures 6 and7 we plot the ratio between SWA and Opt ∞ (l, c m , w d , r d ) as a function of the size of the AC graph with different values of c m , w d and r d .

Simulation results

First we observe the behavior of SWA given the amount of available disk slots for different disk access costs. The two plots in Figure 5 are representative of the two behaviors we observed for SWA during our experiments. We can see that the makespan of SWA(l, c m , c d , w d , r d ) is always strictly higher than the optimal one for an infinite number of disk slots Opt ∞ (l, c m , w d , r d ) (see the dotted line). For all values studied, the evolution of the execution time of SWA when the amount of storage increases follows a specific pattern that can be divided into three phases.

1. A very fast decrease with the first additional disk slots.

A succession of small increases and decreases.

3. A slow but steady decrease until all steps are stored (remember that the horizontal axis has a logarithmic scale for better readability). In all our experiments, the minimum for SWA is reached either at the end of step 1 with a very low number of disk checkpoints (c d = r d = 5 in Figure 5) or at the end of step 3 with a very high number of disk checkpoints (c d = r d = 2 in Figure 5), depending on the disk access costs and the number of memory slots. Eventually, given the general shape of the SWA performances, we assume that when the size of the graph increases enough, the minimum value is always reached at the end of step 3, when every output of the AC graph is stored in one of the storage slots.

Note that Stumm and Walther observed a fourth phase [START_REF] Stumm | Multistage approaches for optimal offline checkpointing[END_REF] where the computational time increases again when the number of disk checkpoints gets closer to the total number of steps. They explained it by saying that when the volume of data stored on the disk reaches a threshold, the cost of a disk access increases, which in turn increases the computational time. We do not observe such a fourth step because we plot the computational time obtained when giving the model parameters as input to SWA (and the cost of disk access remains constant).

In the following, the time complexity of SWA does not allow us to run large instances of l. To be able to plot SWA for large AC graphs, we plot a faster version of SWA that takes the previous remarks into account, namely, that assume that the minimum is either reached at the end of phase 1 (for small values of c d ) or at the end of phase 3. More precisely, we consider that the end of phase 1 is reached before a number of disk size equal to 200 (for the problem sizes This assumption allows us to compute SWA for large values of l and to compare it with the optimal computational time for an infinite number of disk slots. Figures 6 and 7 depict the overhead of using SWA compared with the optimal solution Opt ∞ (l, c m , w d , r d ) that we designed in § 3.2. For unlimited disk slots, SWA returns the best solution among the solutions returned by SWA, and this solution is always greater or equal to Opt ∞ (l, c m , w d , r d ). When w d = r d = 0.25, the cost of writing and reading a value to/from the disks is smaller than the cost of one forward step. It means that it is always better to store a value onto the disk than recomputing the corresponding forward step. The optimal solution will store onto the disk every value x i except c m of them that will be stored onto the memory. In figure 7, we can see that in this context, SWA is optimal.

We also observe that the ratio between SWA and Opt ∞ (l, c m , w d , r d ) increases until the size of the graph reaches a threshold where the ratio becomes constant. This is particularly visible in Figure 6a where we can see that the value of this threshold increases with the number of memory slots c m . In practice, the threshold delimits the moment when the number of disk slots used by SWA goes from a relatively small number (when the minimum for SWA(l, c m , c d , w d , r d ) is reached at the end of phase 1) to c d = lc m (when the minimum for SWA(l, c m , c d , w d , r d ) is reached when all forward steps are checkpointed, at the end of phase 3). We are interested in the limit ratio reached after the threshold because we are considering the problem for very large graphs. In Figures 6a and7 we can see that this ratio increases when c m or w d and r d increase. When r d = w d = 1, the ratio limit for c m = 2 is approximately 1.14, which means that SWA is 14% slower than the optimal algorithm we designed in §3.2. For a memory of size c m = 10, this overhead increases to 20% for large AC graphs. When r d = w d = 5, the ratio limit is not reached for AC graphs of size inferior to 20,000. But since the ratio for c m = 2 will be higher than 1.6, we can state that SWA will perform at least 60% slower than the optimal algorithm on large AC graphs for any memory sizes.

Conclusion and future work

In this paper we have provided optimal algorithms for the adjoint checkpointing problem with two storage locations: a bounded number of memory slots with zero access cost and an infinite number of disk slots with a given write and read costs. We have compared our optimal solution with existing work, showing that our solution gives significantly better execution time.

We have identified applications in computational fluid dynamics and earth systems modeling that could benefit from our approach. We will examine whether the theoretical benefits of the optimal multistage schedule can be realized in practice. Future theoretical directions include the solution to the online AC problem (where the size l of the AC graph is not known before execution), within the same framework. Another possible extension could be to solve the same problem as in this paper but with a limited number of disk checkpoints or with nonzero memory costs; furthermore, having tackled both issues, an extension to three or more levels of the storage hierarchy should be possible.Also, it would be interesting to solve the problem when the values of u f and u b are different at each step. In fact, this would require an extension to the Revolve algorithm to solve the latter problem when only memory checkpoints are avail-able.

Finally, large-scale platforms are failure-prone, and checkpointing for resilience in addition to checkpointing for performance will lead to challenging algorithmic problems. As an intermediate step, we will examine the problem of maximizing progress during a fixed time period. This situation arises in practice when the job scheduler limits the maximum duration of jobs (limits such as 12 hours are common).

The submitted manuscript has been created by UChicago Argonne, LLC, Operator of Argonne National Laboratory ("Argonne"). Argonne, a U.S. Department of Energy Office of Science laboratory, is operated under Contract No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government.

RR n°8721

Figure 4 :

 4 Figure 4: Example of the merging operation.

  first W -type operation in S (d)

  first W -type operation in S (d) 1 occurs before the first F-type operation. Then there are two possibilities. • The first operation in S (d) 1

  , c m , r d ) and Opt (d) 1 (l, c m , r d ) ≥ Opt 0 (l, c m ).

  , c m , r d ) and Opt (d) ∞ (l, c m , w d , r d ) ≥ Opt

  , c m , r d ). This shows that A ≥ B and concludes the proof. Theorem 4 (Simplification). Let l ∈ N, c m ∈ N, w d ∈ R and r d ∈ R: Opt ∞ (l, c m , w d , r d ) = min Opt 0 (l, c m )

1 :

 1 procedure 1D-Revolve(l, cm, r d ) cm, r d ) = Opt 0 (l, cm) then

9 : 1 : 3 : 6 :

 9136 S ← S • R d 0 • 1D-Revolve (j -1, cm, r d ) procedure Disk-Revolve(l, cm, w d , r d ) if Opt ∞ (l, cm, w d , r d ) = Opt 0 (l, cm) then 4:S ← Revolve(l, cm)Let j such that Opt ∞ (l, cm, w d , r d ) = w d + ju f + Opt ∞ (l -j, cm, w d , r d ) + r d + Opt

  • Shift (Disk-Revolve(l -j, cm, w d , r d ), j)9: S ← S • R d 0 • 1D-Revolve (j -1, cm, r d )

4. 1

 1 Stumm and Walther's algorithm (SWA (l, c m , w d , r d ))Stumm and Walther[START_REF] Stumm | Multistage approaches for optimal offline checkpointing[END_REF] solve Problem 2 using a variant of Revolve[START_REF] Walther | Program reversal schedules for single-and multi-processor machines[END_REF]. Revolve takes l the size of the AC graph and s the number of storage slots as argument and returns an optimal solution for Problem 1. Stumm and Walther show that in Revolve(l, s), some storage slots are less used than others. They design the SWA algorithm that takes l the size of the AC graph, c m the number of memory slots, and c d the number of disk slots as argument and returns the solution Revolve(l, c d + c m ) where the c d storage slots that are the least used are considered as disk slots and all the others are considered as memory slots.To solve Problem 2, SWA returns the best solution among the solutions returned by SWA(l, c m , c d , w d , r d ), that is, SWA (l, c m , w d , r d ) = min c d =0...l-cm SWA(l, c m , c d , w d , r d )

  RR n°8721 SWA(l, c m , c d , w d , r d ) SWA (l, c m , w d , r d ) Opt ∞ (l, c m , w d , r d ) w d = r d = 2 w d = r d = 5

Figure 5 :

 5 Figure 5: Makespan of SWA on an AC graph of size 10,000 as a function of c d for c m = 5. SWA and Opt ∞ (l, c m , w d , r d ) are also plotted for comparison.

  considered in this paper), and we plot a faster version of SWA (l, c m , w d , r d ): SWA (l, c m , w d , r d ) = min min c d =0...200 SWA(l, c m , c d , w d , r d ), SWA(l, c m , l-c m , w d , r d ) .

  w d = r d = 5

Figure 6 :Figure 7 :

 67 Figure 6: Ratio SWA (l, c m , w d , r d )/Opt ∞ (l, c m , w d , r d ) as a function of l.

RR n°8721

In the original approach by Griewank[START_REF] Griewank | Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation[END_REF], an extra F l operation was included. It is not difficult to take this extra operation into account.RR n°8721

Acknowledgments

We thank Sri Hari Krishna Narayanan and Vladimir Ufimtsev for constructive conversations. This material is based upon work supported by the French Research Agency (ANR) through the Rescue project and the Joint Laboratory for Extreme-Scale Computing and by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program, under contract number DE-AC02-06CH11357. Yves Robert is with Institut Universitaire de France.

Let us show that A ≤ B. Every solution to Prob(l, c m ) is also a solution to Prob ∞ (l, c m , w d , r d ). Hence, Opt ∞ (l, c m , w d , r d ) ≤ Opt 0 (l, c m ).

Let S(d)

∞ be a solution to Prob According to § 3.1, there exists at least an optimal algorithm S ∞ to solve Prob ∞ (l, c m , w d , r d ) that satisfies (P0-5). According to (P0(x)), the first operation of S ∞ is a W -type operation.

• If it is a W m -type operation, according to (P5), there are no W d -type operations is S ∞ . Hence the disk is not used at all in S ∞ , and S ∞ is also a solution to Prob(l, c m ). Thus

, where S ∞ is a solution to Prob (d) ∞ (l, c m , w d , r d ). Since S ∞ satisfies (P0), (P1), (P2), (P3), (P4), and (P5), S ∞ satisfies (P6). Hence S ∞ is a solution to

To compute Opt (d) ∞ (l, c m , w d , r d ), we need to consider the problem with only one disk slot containing x 0 at the beginning of the execution:

. We want to minimize the makespan of the AC problem with the following parameters.

Initial state: AC graph: size l

Steps:

, where the space of solution is restricted to the schedules that satisfy (P6). Note that we put w d = +∞, to enforce the property that there are no W d -type operation (and, therefore, the value x 0 is never discarded from the disk) in this schedule. Theorem 2 (Optimal solution to Prob

Let Opt

Proof. For l = 0, the result is immediate. Let us prove the result for l ≥ 1. Let

be an optimal solution to Prob

Let S ∞ be an optimal solution to Prob ∞ (lj, c m , w d , r d ) that satisfies (P0-5). Let S ∞ be the sequence S ∞ where every index of the operations are increased by j

is still valid and has the same makespan as S ∞ . Then, the sequence

By construction this sequence also satisfies (P6). Its execution time is

In particular it is smaller than the minimum over all j, hence the result.

Let us show that

∞ be an optimal solution to Prob

∞ satisfies (P6) and its makespan is Opt (d) ∞ (l, c m , w d , r d ). Assume first that there is at least one W -type operation in S (d) ∞ . Consider the first one. We can prove that it occurs before the first F-type operation.

RR n°8721

where (i) no operations involve values x 0 to x j-1 in S 1 and (ii) no operations involve values x j to x l in S 2 .

Let S 1 be the sequence W s j • S 1 , where every index of the operations is decreased by j (F i becomes F i-j , W m i becomes W m i-j ,. . . ). Then S 1 is a solution to Prob ∞ (lj, c m , w d , r d ), whose makespan is necessarily not smaller than Opt ∞ (lj, c m , w d , r d ).

On the other hand, the sequence S 2 executes all the F-type operations from Fj-1 down to F0 with no operations involving values x j to x l . Furthermore, S 2 does not use disk slots, except the one already used by value x 0 . Since S (d) ∞ satisfies (P0(5)), S 2 satisfies (P6). Hence S 2 is a solution to Prob (d) ∞ (j -1, c m , w d , r d ), and its makespan is greater than Opt (d) ∞ (j -1, c m , w d , r d ). Finally, we have

in particular it is smaller than B.

We note that if there is no W -type operation, because we do not use any additional disk slot, S

∞ is also a solution to Prob

Proof. For l = 0, the result is immediate. Let us prove the result for l ≥ 1.

Let

Let us show that A ≤ B. Every solution to Prob(l, c m ) is also a solution to

Given j, 1 ≤ j ≤ l-1, let S 2 be an optimal solution to Prob (d) 1 (j -1, c m , r d ). Let S 1 be an optimal solution to Prob(lj, c m ). Let S 1 be the sequence S 1

RR n°8721

For convenience, let us note

1 (l, c m , r d ) = Opt 0 (l, c m ), we would have w d +Opt 0 (l, c m ) < Opt 0 (l, c m ), which is absurd. So, according to Theorem 2, there exists a j ∈ {1, ..., l -1}, such that

Optimal algorithms

Based on the dynamic programs presented in Theorem 4, we can design two polynomial algorithms to compute an optimal solution to Prob [START_REF] Walther | Program reversal schedules for single-and multi-processor machines[END_REF], that returns an optimal solution to Prob(l, c m ). We also define Shift, the routine that takes a sequence S and an index ind and returns S shifted by ind (meaning for all i ≤ l, s ∈ {m, d}, W s i are replaced by W s i+ind , R s i are replaced by R s i+ind , F i by F i+ind , and Fi by Fi+ind ). Note that sequence Shift (S, ind) has the same execution time as sequence S.

We design the polynomial algorithm 1D-Revolve (Algorithm 1) that, given the auto-adjoint graph size l ∈ N, c m ∈ N memory slots and a cost r d ≥ 0 to read from disk, returns 1D-Revolve(l, c m , r d ) an optimal schedule for Prob

Simulations

In this section we compare our optimal algorithm with the algorithm introduced by Stumm and Walther [START_REF] Stumm | Multistage approaches for optimal offline checkpointing[END_REF]. Stumm and Walther [START_REF] Stumm | Multistage approaches for optimal offline checkpointing[END_REF] had the objective to study