multithreading - 如何减少 DFS 和 BFS 等图遍历算法的缓存未命中？

Question

我想知道如何修改基本的 BFS 和 DFS 算法，以便在顺序或并行实现时减少缓存未命中。

我读到顶点(或)节点的排序有助于在一定程度上减少缓存未命中，但我无法完全理解像 RCM(Reverse Cuthill–McKee) 这样的排序算法有助于减少基本英特尔架构(比如具有专用 L1、L2 和共享 L3 的多核)上的缓存未命中？

除了对顶点排序之外，还有其他减少缓存未命中的想法吗？

Answer 1

我的意见是重新排序可以帮助，但不能保证这样做。让我们以下面的结构为例，在每一行上，您都有节点的邻居。

Node 1: 4, 5, 37, 12, 11, 2, 3
Node 2: 67, 11, 33, 45
Node 3:
......
Node N: 65, 56, 99, 44, 32, 1, 3

例如当你做 DFS 时，你在节点 1。当你找到节点 37 时，你需要跳转到节点 37，但是 节点 2 可能更接近内存，因此被缓存的机会更高。因此，对顶点进行排序减少了通过内存的跳跃步骤，从而减少了缓存未命中。

不过，我认为排序可以做得更聪明一些。例如，当您对节点的顶点进行排序时，比如说 100，节点 1、2、3 很远，因此您可能有兴趣首先放置更接近节点 100 的相邻节点。所以基本上 对节点进行排序根据与目标节点的距离。

这些技术可能有助于处理非常大的图，但在很大程度上取决于图的拓扑结构。

要提出一个图结构，我会这样做:

我会使用 2 x 1D 数组:

• 一个存储每个节点的所有邻居
• 为每个节点存储第一个数组中其邻居开始的索引

示例:

Neighbors: 1 2 3 4 2 4 5 6 7 9 0
Neighbor Indexes: 0 2 5 7 9

The neighbors of Node 0 will start from Neighbors[Neighbor Indexes[0]] until Neighbors[Neighbor Indexes[1]].
The neighbors of Node 1 will start from Neighbors[Neighbor Indexes[1]] until Neighbors[Neighbor Indexes[2]].

等等。