6
$\begingroup$

Suppose we have a set of equations like this

p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f()

It can be represented by computational graph below

If each intermediate value takes 1 unit of memory, you need at least 4 units to compute p7 without any duplicate computation.

Is there an algorithm for estimating memory needed in this setting for a general DAG?

I found a paper called "Adjoint Dataflow Analysis" for estimating this for restricted set of graphs, but it feels like this ought to be a problem that is covered more generally in graph theory.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you mean memory for storing the graph, or how much memory the represented computation needs? $\endgroup$
    – Raphael
    Commented Dec 21, 2016 at 6:16
  • $\begingroup$ I haven't thought about this very hard, but it may be an application of Dilworth's theorem. There's also a lot of literature on register allocation from DAG representations that is worth checking out. en.wikipedia.org/wiki/Dilworth's_theorem $\endgroup$
    – Pseudonym ♦
    Commented Dec 21, 2016 at 6:33
  • $\begingroup$ @Raphael -- need to know how much intermediate memory you need to compute p7 $\endgroup$
    – Yaroslav Bulatov
    Commented Dec 21, 2016 at 20:35

1 Answer 1

Reset to default
4
$\begingroup$

Your problem sounds similar to one-shot (black) pebbling. Wu, Austrin, Pitassi, and Liu, in their paper titled Inapproximability of treewidth, one-shot pebbling, and related layout problems (J. Artificial Intelligence Res. 49 (2014), 569–600), show that it is (probably) hard to compute the optimal cost (which corresponds to your memory).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! I followed background link to find "Complete Register Allocation Problems", which shows how "pebbling" maps to memory allocation $\endgroup$
    – Yaroslav Bulatov
    Commented Dec 21, 2016 at 20:42
  • 1
    $\begingroup$ BTW, this answer led to the memory saving package being implemented in TensorFlow, thanks! :) medium.com/tensorflow/… $\endgroup$
    – Yaroslav Bulatov
    Commented Oct 17, 2021 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.