在内存中布置有向无环图以最大化数据局部性的算法

Question

说我有优势

A -> C
A -> D
A -> E
B -> D
B -> E

为了最大化数据局部性，我安排 DAG 按此顺序存储在内存中(作为数组)，以最小化节点与其依赖项之间的距离。

C, A, D, E, B

因此 A 到 C 的距离为 1，到 D 的距离为 1，到 E 的距离为 2。

B 到 E 的距离是 1，到 D 的距离是 2。

是否有执行此操作的算法的名称？如果没有，将如何实现？

Answer 1

您似乎想要线性化 DAG。我不知道你是否用它来解决依赖关系。 Topological_sorting看起来很熟悉你的问题。还有程序 tsort做的事情非常相似。

不过是依赖线性化。

neel@gentoo:~$ tsort
C A
D A
E A
D B
E B

C
D
E
B
A

打印任务必须执行的顺序。如果有一个循环，它可能无法工作。正如您提到的那样，它是非循环的。

我不知道是否有任何这样的算法用于 data locality ordering string 或任何类似的但是看起来你的 data locality string 有一些问题。

如果 C 接近 (1) A 并且也接近 (1) B 和 B 距离 A 太远 (4) 您将如何使用数据位置字符串表示它？

我现在不知道你到底想做什么。如果您想线性化依赖关系以按正确顺序执行任务，请进行拓扑排序。