4
$\begingroup$

I have some jobs, which calculate values. Some of these jobs require the calculated values of other jobs for their own calculation. An execution plan for these jobs can be found with a topological sort on the dependency graph.

However, these calculated values are huge and occupy a large chunk of memory. I want to find a topological order that minimizes memory usage.

To give a simple example, consider the following dependency graph:

Simple dependency graph

There are three possible topological orders: $1\, 2\, 3\, 4$, $1\, 3\, 2\, 4$, and $3\, 1\, 2\, 4$. Let's look at each of them.

In the first case, the values of $1$ and $3$ can be discarded immediately after $2$ and $4$ have finished, respectively, so each of them must be kept in memory for one additional step. The value of $2$ has to be kept for two additional steps until $4$ has finished. So in total we have to keep $4$ results in memory over the whole execution.

In the second case the values of $1$ and $3$ have to be kept for two steps and the value of $2$ for one step. This makes $5$ in total, so this ordering is worse in terms of memory usage.

In the third case the value of $3$ has to be kept for three steps and the values of $1$ and $2$ for one step each. Again we have a total of $5$, so this ordering is also worse than the first one. Thus the first ordering should be chosen.

Is there an efficient algorithm to find an optimal ordering without needing to inspect all possible orderings?

Bonus: is it also possible to give an optimal solution, if the values would need different amounts of memory per job?

$\endgroup$
  • 2
    $\begingroup$ The version in which one is interested in the maximum number of values kept in memory at any single time is known as one-shot (black) pebbling, and according to this paper is probably hard to calculate exactly: arxiv.org/pdf/1109.4910v1.pdf. $\endgroup$ – Yuval Filmus Jul 19 '16 at 21:16
  • $\begingroup$ ipsec, if Yuval's comment answered your question, can I encourage you to write an answer to your own question? That might benefit others with the same question. $\endgroup$ – D.W. Jul 22 '16 at 17:57
  • $\begingroup$ The reference to pebbling was very valuable, but it solves not quite the problem I am facing. But I suspect, that my problem is hard to solve as well. $\endgroup$ – ipsec Jul 24 '16 at 7:36
  • $\begingroup$ Does this help? cstheory.stackexchange.com/q/36230/5038 $\endgroup$ – D.W. Jul 25 '16 at 3:29
  • $\begingroup$ @D.W. Yes, this looks more like my problem. So it seems I am facing NP-hardness. $\endgroup$ – ipsec Jul 26 '16 at 9:44
6
$\begingroup$

This problem is called the Minimum Linear Arrangement of a Directed Graph and it is indeed NP-hard.

See the reduction from the MLA to MLAD on page 11 of this (old) technical report: S. Even and Y. Shiloah, NP-completeness of several arrangement problems, Technical Report no. 43 of the Department of Computer Science, Israel Institute of Technology (Technion), 1975 (PDF).

$\endgroup$

Your Answer

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

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