针对依赖性评估的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在他的评论中所指出的,这与Register Allocation非常相似,可以使用启发式贪婪图着色算法有效地解决.但是,寄存器分配是一个更简单的问题,因为它假定您知道计算的顺序,因此可以计算每个变量的活跃度.在此之后,您可以轻松构建推理图并执行图着色.在我们的例子中,我们希望并优化计算顺序.这当然需要一些假设,例如我们没有指针,只有基本数据结构(这是我的节点所代表的).显然,由于图形着色是NP完全的,因此这个问题至少是NP完全的.我正在寻找的是某种贪婪/启发式算法,它可以为一些不太堕落的情况提供一个很好的解决方案.

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,对每个节点v.现在,X _v只写[R _v,并ÿ _v读取每个- [R _ü对应于母公司ü.添加依赖图边(x _v,y _v).将每条指令的执行时间设置为0.5.就这样.

注意,需要在不同指令之间分离寄存器写入和读取,以防止在不允许时重用父寄存器.

算法

开头引用的文章描述了一种近似解决CRISP的有效算法.它也可以用来解决这个问题 - 只需使用上面的减少并从1开始尝试每个m直到找到解决方案.

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