我可以使用什么算法来选择我访问图形边缘的顺序，以最大限度地减少缓存未命中的次数？

Question

大图

我正在编写一些代码来模拟晶体管级别的计算机。仿真器归结为一个图形，其中每个节点都是一个晶体管，每条边是连接图形上任意两个晶体管节点的导线。这个图是循环的，晶体管节点可能连接到它们自己。

为了运行模拟器的一个“步骤”，两个独立的函数是运行:

处理每条线边，从其源节点的输出设置其目标节点的输入。每条线每一步都被访问一次，但一个传输器可能被访问多次。
每个晶体管节点输出状态都从其输入状态更新（如何超出这个问题的范围，我很确定我正在有效地做到这一点）。

我相信我已经优化了第二步，但我需要帮助来提高第一步的效率。

实施

代码大致如下：

type InputBit = usize;
type OutputBit = usize;

struct Emulator {
    inputs: Vec<u64>,
    outputs: Vec<u64>,
    wires: Vec<(InputBit, OutputBit)>,
}

impl Emulator {
    fn step(&mut self) {
        step_wires(&mut self);
        step_transistors(&mut self);
    }

    fn step_wires(&mut self) {
        for (input, output) in self.wires.iter() {
            // NB omitted bit-twiddling to get bit indices
            self.outputs[output] = self.inputs[input];
        }
    }

    fn step_transistors(&mut self) {
        // ... omitted for brevity ...
    }
}

每个晶体管节点N由2N和self.inputs中的两个输入位和2N和2N中的两个输出位组成2N+1 在 self.outputs.

我看到的问题是我的电线（和晶体管）列表是任意顺序的。这意味着它确实缓存效率低下。例如，假设这组导线（输入节点位，输出节点位）：

[
    (0, 1000),
    (1000, 2000),
    (1, 1001),
    (1001, 2001),
]

如果我的内存缓存大小小于 1000 位，这意味着我的大部分读取和写入都发生了缓存未命中。如果重组为：

[
    (0, 1000),
    (1, 1001),
    (1000, 2000),
    (1001, 2001),
]

那么缓存未命中率就会降低。同样，我也可以“移动”晶体管节点以给出以下等效图：

[
    (0, 2),
    (1, 3),
    (2, 4),
    (3, 5),
]

现在只使用一个缓存行！快多了。（请注意，这个例子有点误导，因为节点索引将被密集打包，即不会有任何未使用的“空”节点索引，但“交换”节点是可以的）。

问题

我可以使用什么算法来选择我访问线边缘的顺序，and/or 重新排序晶体管节点索引，以便在遍历图形时缓存未命中的次数最少？

我认为减少所有边缘的总“距离”的东西会是一个好的开始？然后对边缘进行排序，以便首先访问完全位于单个缓存行内的边缘，按缓存行顺序访问，然后按某种顺序访问不同缓存行之间的边缘？

Answer 1

一般来说这是一个很难解决的问题。论文 Vertex Reordering for Real-World Graphs and Applications: An Empirical Evaluation 很好地概述了各种重新排序算法及其对性能和局部性的影响。该论文总体上倾向于基于 Rabbit-order 的算法及其变体。针对您的具体情况进行调整将取决于缓存大小、数据大小、分支因子、分区行为等。

但是，如果您正在寻找运行良好且不太难实现的算法，我建议您使用 Reverse Cuthill-McKee (RCM) 算法。

我可以使用什么算法来选择我访问图形边缘的顺序，以最大限度地减少缓存未命中的次数？

What algorithm can I use to chose which order I visit the edges of a graph to minimize the number of cache misses?

sorting

algorithm

caching

graph

rust

大图

实施

问题