Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used.

That is, given a graph {1 -> 3, 2 -> 3, 4 -> 5, 3 -> 5}, I'm looking for an algorithm that will decide the order of graph reduction to minimize the number of 'in-progress' nodes, in this particular case to decide that it should be reduced in the order 1-2-3-4-5; avoiding the alternative ordering, in this case 4-1-2-3-5, which would leave the output from node 4 hanging until 3 is also complete.

Naturally, if there are two nodes using the output from a third, then it only counts once; data is not copied unnecessarily, though it does hang around until both of those nodes are reduced.

I would also quite like to know what this problem is called, if it has a name. It looks similar to the graph bandwidth problem, only not quite; the problem statement may be defined in terms of path/treewidth, but I can't quite tell, and am unsure if I should prioritize learning that branch of graph theory right now.

  • $\begingroup$ The problem can be expressed as an assignment problem, but not a linear one as far as I can tell. $\endgroup$ – Raphael May 14 '12 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.