我可以使用什么算法来选择访问图的边缘的顺序，以最小化缓存丢失的次数？
大画卷
我正在编写一些代码来模拟晶体管级的计算机。仿真器归结为一个图，其中每个节点都是一个晶体管，每个边是连接图上任意两个晶体管节点的导线。这个图是循环的，晶体管节点可以连接到自己。
要运行模拟器的单个“步骤”，需要运行两个独立的函数：
- 每个线边被处理，从其源节点的输出设置其目标节点的输入。每一步都会访问一次每条导线，但可能会多次访问transitor。
- 每个晶体管节点输出状态都从其输入的状态更新(如何超出这个问题的范围，我很确定我正在有效地完成它)。
我相信我有优化的第二步，但我需要帮助，使第一步更有效率。
实现
代码大致如下所示：
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和2N+1在self.inputs中，以及在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),
]它现在只使用一个缓存行！快多了。(注意，这个示例有点误导，因为节点索引将被密集地压缩，即不会有任何未使用的“空”节点索引，但“交换”节点是好的)。
问题
我可以使用什么算法来选择访问线边的顺序和/或重新排序晶体管节点索引，以便在遍历图形时有最小数量的缓存遗漏？
我认为减少所有边缘的“距离”会是一个好的开始？然后对边缘进行排序，以便首先访问完全在单个缓存线内的边缘，然后按缓存线顺序访问，然后按某种顺序在不同的缓存线边之间进行访问？
回答 1
Stack Overflow用户
发布于 2021-04-06 22:04:37
总的来说，这是一个很难解决的问题。本文对各种重排序算法及其对性能和局部性的影响作了较全面的综述。本文总体上考虑了基于兔子序的算法及其变化.对特定情况的调优将取决于缓存大小、数据大小、分支因子、分区行为等。
但是，如果您要寻找的东西工作得很好，并且不太难实现，我建议使用反向Cuthill-McKee (RCM)算法。
https://stackoverflow.com/questions/66971886
复制相似问题
腾讯云开发者
