algorithm - 依赖评估的 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 完全的。我正在寻找的是某种贪婪/启发式算法，它可以在一些不太退化的情况下给出一个很好的解决方案。

Answer 1

实际上，在某种意义上，这个问题比图形着色问题更容易，因为这个问题的决策版本是Combined Register Allocation and Instruction Scheduling Problem (CRISP)的决策版本的一个特例。 ，这比图形着色问题更容易解决(至少在不需要精确解的情况下)。

这个问题的决策版本可以表述为是否存在使用最多 m 个内存槽的调度？

减少到 CRISP

请注意，下面我将使用引用文章中的术语。

对于问题中的每个节点 v，让我们介绍 virtual 寄存器 r_v 和指令 x CRISP中的_v，指令写入寄存器r_v并读取每个寄存器r_u对应节点v的父节点u。此外，对于 DAG 的每条边 (u, v)，我们引入边 (x_u , x_v) 在 CRISP 的依赖图中。每条指令的执行时间等于 1，每个依赖边的延迟等于 0，溢出成本等于 ∞。可用物理寄存器的数量等于m。

如果CRISP中有一个时间长度最多为节点数的schedule，那么原问题中就有对应的schedule最多使用m个内存槽。我们完成了。

如果 parent 使用的内存不能被 child 重用

上面提出的减少假设当不再需要父级时，子级可以重用父级使用的内存。不允许时，需要进行如下修改:

为每个节点 v 添加一条指令 y_v。现在，x_v 只写 r_v，而 y_v 读取与父 u 对应的每个 r_u。添加依赖图边(x_v，y_v)。将每条指令的执行时间设置为 0.5。就是这样。

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

算法

开头引用的文章描述了一种近似求解 CRISP 的有效算法。它也可以用来解决这个问题——只需使用上面的归约，然后从 1 开始尝试每个 m 直到找到解决方案。

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