一个DAG的最佳内存跟踪方式，用于依赖评估。

Question

我正在寻找一种算法来优化DAG上的评估顺序，以使用最少的内存。可能有点难以解释，所以我会举个例子来说明我的意思。考虑一个具有多个根节点的DAG，它表示某种依赖关系的评估顺序。因此，每个子节点只能在其父节点执行后执行其操作。另外，我们可以从内存中释放不再需要的每个节点。任务是找到最优的顺序评估时间表，以在任何时候使用最少的内存。例如，考虑下面的图：

还有两个时间表：

load A - 1 node in memory
load B - 2 
eval C - 3
eval D - 4
eval F - 5
unload C - 4
eval H - 5
unload A,F - 3
eval E - 4
eval G - 5
unload D,E - 3
eval I - 4
unload B,G - 2
eval J - 3
unload H,I

Maximum memory trace - 5

而这一个：

load A - 1 node in memory
load B - 2 
eval C - 3
eval D - 4
eval E - 5
eval F - 6
unload C - 5
eval G - 6
unload D,E - 4
eval H - 5
unload A,F - 3
eval I - 4
unload B,G - 2
eval J - 3
unload H,I - 1
unload C - 4
eval H - 5
unload A,F - 3
eval E - 4
eval G - 5
unload D,E - 3
eval I - 4
unload B,G - 2
eval J - 3
unload H,I

Maximum memory trace - 6

假设所有节点占用相同的内存，是否存在一种最优算法来实现此目标？第一个算法类似于深度优先遍历，而第二个算法类似于广度优先遍历，但我不知道它们是否是最优的以及原因。

PS：

仅为澄清，正如@Evgeny Kluev在评论中所指出的那样，这非常类似于寄存器分配，可以使用启发式贪婪的图形着色算法有效地解决。然而，寄存器分配是一个更简单的问题，因为它假定您知道计算顺序，因此可以计算每个变量的生命周期。然后您可以轻松地构建推理图并进行图形着色。在我们的情况下，我们希望实现这一点，同时优化计算顺序。当然，这需要一些假设，例如我们没有指针，并且只有基本数据结构（这就是我的节点代表的东西）。显然，由于图形着色是NP完全的，因此此问题至少是NP完全的。我正在寻找一种某种贪心/启发式算法，在一些不太退化的情况下提供一个良好的解决方案。

- Alex Botev

---

@Belov，你有内存限制吗？还是你想要最优解决方案？因为我知道一种适用于内存限制版本的解决方案。 - Ashkan Kazemi

如果你使用 BFS，那么在内存中存储的节点数量不能小于你的分支因子，而如果你使用 DFS，则这个数字不能小于从根到叶子的最长路线。所以这取决于你的需求。 - Ashkan Kazemi

这个问题与寄存器分配非常相似，可以通过图着色算法来解决。 - Evgeny Kluev

从理论上讲是可以的，但实际上不行，因为那需要写入磁盘，这显然会极大地减慢速度。而且如果你在GPU上做这个，你知道会发生什么... - Alex Botev

@EvgenyKluev，你说得对，这个问题是相似的，但并不完全相同。寄存器分配问题实际上是这个问题的简化版本，因为在那里，您已经有了预定义的评估时间表，因此您已经拥有了每个变量的所有生命周期，并且可以构建所谓的推理图并进行着色。然而，在这里，我们正在做同样的事情+我们需要找到最优的评估顺序，考虑到没有指针或高阶结构。 - Alex Botev

Answer 1

实际上，在某种意义上，这个问题比图着色问题更容易，因为此问题的“决策版本”是组合寄存器分配和指令调度问题(CRISP)决策版本的一个特例，相对于要求精确解时的图着色问题，此问题较容易求解。

此问题的决策版本可以被制定为：是否存在一种使用不超过m个内存插槽的时间表？

转化为CRISP问题：

对于您问题中的每个节点v，让我们在CRISP中引入虚拟寄存器r_v和指令x_v，该指令写入寄存器r_v并读取每个与节点v的父节点u对应的寄存器r_u。 同样，对于DAG的每条边（u，v），我们在CRISP的依赖关系图中引入边（x_u，x_v）。每个指令的执行时间为1，每个依赖边的延迟为0，溢出成本为∞。可用物理寄存器的数量等于m。

如果在CRISP中存在一个时间长度不超过节点数的时间表，则在原始问题中存在使用不超过m个内存插槽的相应时间表。我们完成了。

如果父亲使用的内存不能被孩子重复使用：

上述转换假设当父母不再需要时，孩子可以重复使用父母使用的内存。 当不允许这样做时，需要进行以下修改：

为每个节点v添加一条指令y_v。现在，x_v仅写入r_v，并且y_v读取与父项u对应的每个r_u。添加依赖图边（x_v，y_v）。将每个指令的执行时间设置为0.5。就这样。

请注意，必须在不同指令之间分离寄存器的写入和读取，以防止在不允许时重复使用父寄存器。

算法：

开头引用的文章描述了一种解决CRISP问题的高效算法。该算法也可以用于解决本问题——只需使用上述规约，并从1开始尝试每个m，直到找到解决方案。

还要注意，该算法由两个参数α和β参数化，其中α是控制寄存器压力的权重，β是控制指令并行性的权重。对于此问题，将α设置为1，将β设置为0，因为此问题不需要指令并行性。

- dened

---

上帝保佑您！那正是我在寻找的，确实更简单，虽然一开始并不那么明显（如我所想）。 - Alex Botev