依赖评估 DAG 的最佳记忆轨迹
Optimal memory trace for a DAG of dependency evaluations
我正在寻找一种算法来优化 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 完全的。我正在寻找的是某种 greedy/heuristic 算法，它可以在一些不太退化的情况下提供一个好的解决方案。
实际上，从某种意义上说，这个问题比图形着色问题更容易，因为这个问题的决策版本是[=10]决策版本的特例=]，这比图形着色问题更容易解决（至少在不需要精确解的情况下）。
这个问题的决策版本可以表述为是否存在最多使用 m 个内存槽的调度？
还原为 CRISP
请注意，下面我将使用参考文章中的术语。
对于问题中的每个节点 v 让我们引入 virtual register rv和CRISP中的指令xv，指令写入寄存器rv并读取父节点u[=对应的每个寄存器ru节点 v 的 78=]。此外，对于 DAG 的每条边 (u, v) 我们引入边 (xu, xv)在CRISP的依赖图中。每条指令的执行时间等于1，每条依赖边的延迟等于0，溢出成本等于∞。可用 physical 寄存器的数量等于 m.
如果CRISP中有时间长度最多为节点数的schedule，则原题中有相应schedule最多使用m个内存槽.我们完成了。
如果父进程使用的内存不能被子进程重用
上面介绍的缩减假设当不再需要父项时，子项可以重复使用父项使用的内存。不允许时，需要做如下修改：
为每个节点v再添加一条指令yv。现在，xv 只写 rv，并且yv读取每个ru对应父u。添加依赖图边(xv,yv ).将每条指令的执行时间设置为0.5。就这些了。
请注意，需要将不同指令之间的寄存器写入和读取分开，以防止在不允许时重用父寄存器。
算法
开头引用的文章介绍了一种近似求解CRISP的高效算法。它也可以用来解决这个问题——只需使用上面的归约并尝试从 1 开始的每个 m，直到找到解决方案。
另请注意，该算法由两个参数参数化：α和β，其中α是控制寄存器压力的权重，β是控制指令并行度的权重。对于此问题，将 α 设置为 1，将 β 设置为 0，因为此问题不需要指令并行性。
我正在寻找一种算法来优化 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 完全的。我正在寻找的是某种 greedy/heuristic 算法，它可以在一些不太退化的情况下提供一个好的解决方案。
实际上，从某种意义上说，这个问题比图形着色问题更容易，因为这个问题的决策版本是[=10]决策版本的特例=]，这比图形着色问题更容易解决（至少在不需要精确解的情况下）。
这个问题的决策版本可以表述为是否存在最多使用 m 个内存槽的调度？
还原为 CRISP
请注意，下面我将使用参考文章中的术语。
对于问题中的每个节点 v 让我们引入 virtual register rv和CRISP中的指令xv，指令写入寄存器rv并读取父节点u[=对应的每个寄存器ru节点 v 的 78=]。此外，对于 DAG 的每条边 (u, v) 我们引入边 (xu, xv)在CRISP的依赖图中。每条指令的执行时间等于1，每条依赖边的延迟等于0，溢出成本等于∞。可用 physical 寄存器的数量等于 m.
如果CRISP中有时间长度最多为节点数的schedule，则原题中有相应schedule最多使用m个内存槽.我们完成了。
如果父进程使用的内存不能被子进程重用
上面介绍的缩减假设当不再需要父项时，子项可以重复使用父项使用的内存。不允许时，需要做如下修改：
为每个节点v再添加一条指令yv。现在，xv 只写 rv，并且yv读取每个ru对应父u。添加依赖图边(xv,yv ).将每条指令的执行时间设置为0.5。就这些了。
请注意，需要将不同指令之间的寄存器写入和读取分开，以防止在不允许时重用父寄存器。
算法
开头引用的文章介绍了一种近似求解CRISP的高效算法。它也可以用来解决这个问题——只需使用上面的归约并尝试从 1 开始的每个 m，直到找到解决方案。
另请注意，该算法由两个参数参数化：α和β，其中α是控制寄存器压力的权重，β是控制指令并行度的权重。对于此问题，将 α 设置为 1，将 β 设置为 0，因为此问题不需要指令并行性。