Please find attached:
-- The revised version of our ICCS 2006 paper
as a tar.gz file with the latex source,
2 postscript figures and a .bib bibliography
-- The concatenation of the three referees reports,
with our replies inserted inside.
The paper suggests a formal approach to characterize
checkpointing sets vs taping. Both the application to
programs that do not exhibit a special looping structure
as well as the characterization of minimal solutions are new.
It is a very usefull foray into using data flow for
determining checkpointing sets and should definitly be
accepted.
The issues mentioned below should improve readability
for the general audience.
major comments:
A:
I realize notation regarding the result of
the source transformation of program subsections in
terms of forward and reverse is difficult
because it does not lend itself easily to checkpointing schemes.
E.g. on pg.3 Sect.3 states:
$\overline{C}\Doteq\overrightarrow{C};\overleftarrow{C}$
and in this notation there is no mentioning of taking
the checkpoint, running forward and later restoring the checkpoint
although this certainly belongs to the source transformation of
code section $C$ which is presumably what is denoted by $\overline{C}$
if one goes by the explanation of $P$ and $\overline{P}$ on page 2.
Then on the top of page 4 there is a different notation that does
includes the store/restore etc.
>> Right. I added notation [] to denote checkpointing.
>> \overline{C;D} is thus
>> \overrightarrow{C};\overrightarrow{D};\overleftarrow{D};\overleftarrow{C}
>> whereas \overline{[C];D} is the reverse diff program with C checkpointed
>> with the store, restore, etc.
However, on page 4 I am missing
an explanation of the notation "\hbox{\it Req} \vdash"
which is repeatedly used as something being executed while
"Req" itself is a set. The notation should be clarified.
>> Req is not a piece of code. It is a context in which
>> the code generation is done. When using rewrite rules,
>> people use \vdash to mean this.
>> Yes the rewrite rules here are ambiguous.
>> I put a box around to distinguish the rewrite terms
>> plus one line of explanation.
B:
I don't see a clear motivation for the backward snapshot
as opposed to the tape. In the paper just states it is a "hybrid".
The need for the regular checkpoints is clear.
>> Backward snapshot does not save memory space,
>> but may reduce memory traffic (e.g only one
>> push/pop pair instead of 2. Added this on page 4.
Sect 4. mentions that there can be a trade-off between
storing/restoring things in big blocks vs.
doing it one at a time. This would presumably be the implied
motivation for the backward snapshots.
It would be nice if the conclusions section could address this by
showing more detail about profile data for taping push/pops
vs. storing/restoring snapshots.
>> Our first measurements on memory traffic are too recent,
>> and not conclusive yet.
C:
I missed any mentioning of checkpoint placement as an issue.
The space constraints don't allow to go into much detail.
However, it should be pointed out that (aside from special
cases such as time stepping loops) the segmentation of the code
into the subsections U,C,D
which in this paper is predetermined can have a substantial
impact on the checkpoint size.
>> I took your words to rephrase the end of the conclusion,
>> which meant that.
minor comments:
pg 2: If there isn't a special purpose for calling the three parts
upstream/center/downstream, could they be renamed A/B/C instead?
>> I sort of like using U for Upstream, C for Checkpoint, D for Downstream ?
pg 2: Can you cite the TBR paper at the first mentioning of TBR
analysis .
>> Done
pg 2: change "... finds the Req set of these required values." to
"...finds the set of these required values denoted by Req."
>> ok
May be there is a chance to also actually
say what precisely "out()" and "use()" mean, in particular
if it is 'local use' only of cumulative with the 'use' of
a segments 'callees'. To the uninitiated
reader it is probably not clear enough from the context.
>> added a few words on bottom of page 4
pg 2: the sentence
"In other words ... must be built in such a way that:"
with the following formula should either be removed or better
explained. The assertion "must be built" wrt. the formula
becomes clear only after reading on and going back later.
>> Good. We gain 3 lines!
pg 3: I think the sentence
"This also uses memory space, although less than the tape for ..."
should really relate to the *placement* of the checkpoints, i.e.
the segmentation of the program. That is crucial and should be
mentioned to better motivate above sentence and the initial
trade-off between taping and checkpointing space.
>> agreed.
pg 5: in the condition for "\it Snp" (3rd last line),
it is not immediately apparent to me where the
\cup (\hbox{\it Req} \setminus \hbox{\it Sbk}
comes from. I suspect this is just my mistake but
without that last bit it appears
to be directly derived from eqn. (3). With
it the intersection on the right hand side may be larger
than without which makes me wonder
about the "necessary and sufficient"? Since I have
a similar problem with the Req_D eqn. I am just
guessing I am missing some step but you may want to
consider adding this.
>> This is because Snp also appears in
>> equation (4). Equation (3) alone does imply that
>> Snp >= (out(C) \cup (out(Db) \ ReqD)) \cap use(Cb)
>> in addition (4) implies that
>> Snp >= (out(C) \cup (out(Db) \ ReqD)) \cap (Req \ Sbk)
>> same happens for ReqD.
>> We do think the conditions are necessary and sufficient.
pg 6: In the solution of the set equations - what is the
optimality criterion? The text mentions "minimal" and
"optimal" solutions. Naively looking at the equations in (6)
it seems Opt_2^- is the only part occurring twice so any
partition that leaves Opt_2^- empty seems to be better
in terms of the total size of Sbk, Snp, Req_D, Req_C ?
So I suspect total memory footprint isn't the criterion.
>> Right. I added that these sets are minimal in the sense that any
>> semantics-preserving choice of the 4 sets is
>> larger or equal to one of these minimal quadruplets.
pg 8: Please clarify "... choices of the other checkpoints around."
What is around? It could be that once the notation issue raised
under the major issue "A" is addressed this may well become clear.
>> Rephrased.
--------------------------------------------------------------
[Overview]
More explanation on notation is needed.
>> added explanations on the \overline notation
>> and the rewrite rule on page 4
>> However, we will also have to spare half a page,
>> so sometimes we have to rely on commonly
>> used notation.
[Comments]
page 2, line -8 (8 from the bottom)
The term "out" is not defined here.
>> removed and explained on next occurrence page 4
page 3, line 11
The meaning of the semicolon in the notation
$\overline{D}\Doteq\overrightarrow{D};\overleftarrow{D}$
should be explained.
>> done. This use of semicolon for code sequence is widespread.
page 3, Figure 2
The term "Sbk" is not defined here.
>> Right, but it is defined upon its first occurrence in the text
page 4, line 3
The notation "$Req\vdash \overline{C;D}$" was hard to be understood
because PUSH(Sbk) is undefined here.
page 5, line 15 ( eq.(3))
The reason of disappearance of "PUSH(Sbk)" in (1) should be explained.
>> done. A PUSH does not overwrite any program variable.
--------------------------------------------
1. Introduction
You write: ... it (reverse mode AD) suffers from a high memory consumption...
That is only true for the store all or store minimal strategy
implemented in Tapenade, ADIFOR 3, and OpenAD.
If every intermediate result is recomputed then reverse mode AD needs little
memory but suffers from computational costs!
You might want to read and cite other papers about AD.
You write: This memory consumption is inherent to the nature of
gradient computation.
That is obviously wrong.
You write: to solve the adjoint equations ... is also known to consume
memory space.
What you mean by this. Almost every computation requires memory
(it doesn't consume it like eating bred).
AD generated code also solves the adjoint equation!
The first two paragraphs in the introduction need to be rewritten totally.
>> Rewritten as:
>> The methods to compute gradients can be classified in two categories.
>> In the first category, methods use CPU more intensively because
>> several operations are duplicated. This can be through
>> repeated tangent directional derivatives, or through reverse
>> Automatic Differentation using the ``Recompute-All'' strategy.
>> This is not the context of this paper. In the second category,
>> methods spare duplicated operations through increased memory use.
>> This encompasses hand-coded resolution of the ``adjoint equations''
>> and reverse Automatic Differentation using the ``Store-All'' strategy,
>> which is the context of this work.
2. Reverse Automatic Differentiation
You write: AD is a program transformation technique.
... an AD tool creates a new program ...
no, see tools based on operator overloading
>> ok. Text modified.
TBR = to be recorded not to be restored
>> Right. Fixed.
What is the definition of 'Req'?
>> Explained in section 2. Rephrased.
What is the difference between Req and use(U)?
>> In the paper we define Req as use(\overleftarrow{U}),
>> which is smaller than use(U) as said in section 2 and
>> detailed in refs [2,6]
What is the definition of OUT?
I guess what you name OUT is actually termed KILL in data flow analysis.
>> Defined now page 4. KILL usually denotes scalar and array
>> variables completely overwritten. OUT is for variables even
>> only partly overwritten.
3. The equation of checkpointing snapshots
You write: This allows the tape consumed ... to be freed ...
That is also true without checkpointing.
The tape consumed by C is relevant here,
it is needed after adjoint of D has finished.
>> Both what you write and what we wrote is true,
>> and both lead to the conclusion stated by
>> the sentence that follows.
What is Sbk?
>> Defined in detail on its first occurrence in the text, page 4.
>> True it appears on figure 2 before, but it is just a
>> support for the discussion on page 4.
You write: This also uses memory space, although less than the tape for C.
That is not always true.
>> Ok, but one can almost always write pathological examples
>> for any such assumption. In real life, the snapshot is really
>> smaller. It's an interesting question to detect those "C"'s
>> for which snapshots are larger than the tape, but
>> it's not in the scope of this paper.
4 Discussion and Experimental results
Table 1: What run-time is shown, the function or the adjoint?
One needs to see the run-time of function, eager adjoint, and lazy adjoint.
What is the memory usage and run-time without checkpointing?
>> added run-time of function.
>> Run-times with eager and lazy do not differ significantly.
>> Most examples would simply run out of memory if no
>> checkpointing was made.
5 Conclusions
I am missing an discussion of the computational cost of checkpointing,
i.e. the additional flops and the cost of writing and reading the tape.
The central question is what is the best mixture of recomputations and
taping, not memory usage alone.
>> Certainly a very general and important question.
>> This paper does not claim to answer this question.
>> But it gives an element to understand it better.
