0

我有一个静态图（拓扑不会随时间变化，并且在编译时已知），其中图中的每个节点都可以具有三种状态之一。然后我模拟一个动态，其中一个节点有可能随时间改变其状态，而这个概率取决于其邻居的状态。随着图表变大，模拟开始变得非常慢，但经过一些分析后，我发现大部分计算时间都花在了遍历邻居列表上。

我能够通过更改用于访问图中邻居的数据结构来提高模拟速度，但想知道是否有更好（更快）的方法来做到这一点。我目前的实现是这样的：

对于一个N节点标记为从0到N-1且平均邻居数为 的图K，我将每个状态作为整数存储在 an 中std::vector<int> states，并将每个节点的邻居数存储在 中std::vector<int> number_of_neighbors。

为了存储邻居信息，我创建了另外两个向量：std::vector<int> neighbor_lists它按顺序存储与 node 0、 node 1、 ... 、 node相邻的节点N，以及一个索引向量std::vector<int> index，它为每个节点存储其第一个邻居的索引neighbor_lists.

所以我总共有四个向量：

printf( states.size()              );    // N
printf( number_of_neighbors.size() );    // N
printf( neighbor_lists.size()      );    // N * k
printf( index.size()               );    // N

更新节点时i，我像这样访问它的邻居：

// access neighbors of node i:
for ( int s=0; s<number_of_neighbors[i]; s++ ) {
    int neighbor_node = neighbor_lists[index[i] + s];
    int state_of_neighbor = states[neighbor_node];

    // use neighbor state for stuff...
}

总结一下我的问题：是否有更快的实现来访问固定图结构中的相邻节点？

目前，我已经在相当长的模拟时间内达到了 N = 5000，但如果可能的话，我的目标是 N ~ 15.000。

4

2 回答 2

1

了解数量级很重要，N因为如果它不是很高，您可以使用您知道拓扑的编译时间这一事实，因此您可以将数据放入std::array已知维度的 s（而不是std::vectors）中，使用最小可能的类型，以（如果需要）节省堆栈内存，将其中一些定义为constexpr（除了states）。

所以，如果N不是太大（堆栈限制！），你可以定义

  • states作为std::array<std::uint_fast8_t, N>（3个状态的8位就足够了）

  • number_of_neighbors作为constexpr std::array<std::uint_fast8_t, N>（如果最大邻居数小于 256，则为更大的类型）

  • neighbor_listconstexpr std::array<std::uint_fast16_t, M>如果16位M足以满足N; 否则更大的类型

  • index好像constexpr std::array<std::uint_fast16_t, N>16位就足够了M；否则更大的类型

我认为（我希望）使用已知维度的数组constexpr（如果可能的话）编译器可以创建最快的代码。

关于更新代码...我是一个老C程序员，所以我习惯于尝试以现代编译器做得更好的方式优化代码，所以我不知道下面的代码是否是个好主意；无论如何，我会这样写代码

auto first = index[i];
auto top   = first + number_of_neighbors[i];

for ( auto s = first ; s < top ; ++s ) {
   auto neighbor_node = neighbor_lists[s];
   auto state_of_neighbor = states[neighbor_node];

   // use neighbor state for stuff...
}

- 编辑 -

OP指定

目前，我已经在相当长的模拟时间内达到了 N = 5000，但如果可能的话，我的目标是 N ~ 15.000。

所以 16 位应该足够了——对于输入neighbor_list和输入index——和

  • statesnumber_of_neighbors每个大约 15 kB（使用 16 位变量为 30 kB ）

  • index大约是 30 kB。

在我看来，堆栈变量的值是合理的。

问题可能是neighbor_list；如果邻居的中等数量很少，比如 10 来固定一个数字，我们有M（邻居的总和）大约是 150'000，所以neighbor_list大约是 300 kB；不低但在某些环境下是合理的。

如果中等数字很高——比如 100，固定另一个数字——neighbor_list变成大约 3 MB；在某些环境中，它应该很高。

于 2017-10-15T13:05:14.680 回答
0

目前，您正在为每次迭代访问 sum(K) 节点。这听起来并不那么糟糕......直到你点击访问缓存。

对于少于 2^16 个节点，您只需要一个uint16_t来标识一个节点，但是对于 K 个邻居，您将需要一个uint32_t来索引邻居列表。如前所述，这 3 个状态可以存储在 2 位中。

所以有

// your nodes neighbours, N elements, 16K*4 bytes=64KB
// really the start of the next nodes neighbour as we start in zero.
std::vector<uint32_t> nbOffset;
// states of your nodes, N elements, 16K* 1 byte=16K
std::vector<uint8_t> states;
// list of all neighbour relations, 
// sum(K) > 2^16, sum(K) elements, sum(K)*2 byte (E.g. for average K=16, 16K*2*16=512KB
std::vector<uint16_t> nbList;

你的代码：

// access neighbors of node i:
for ( int s=0; s<number_of_neighbors[i]; s++ ) {
    int neighbor_node = neighbor_lists[index[i] + s];
    int state_of_neighbor = states[neighbor_node];

    // use neighbor state for stuff...
}

将您的代码重写为

uint32_t curNb = 0;
for (auto curOffset : nbOffset) {
  for (; curNb < curOffset; curNb++) {
    int neighbor_node = nbList[curNb]; // done away with one indirection.
    int state_of_neighbor = states[neighbor_node]; 

    // use neighbor state for stuff...
  } 
}

因此，要更新一个节点，您需要从 中读取当前状态，从中states读取偏移量nbOffset并使用该索引来查找邻居列表nbList，并使用索引nbList来查找 中的邻居状态states。

如果您在列表中线性运行，前 2 个很可能已经在 L1$ 中。如果您以线性方式计算节点，则从每个节点读取的第一个值nbList可能在 L1$ 中，否则很可能会导致 L1$ 并且可能会导致 L2$ 未命中，以下读取将是硬件预取的。

线性读取节点有一个额外的优势，即每个邻居列表在节点集的每次迭代中只会被读取一次，因此states留在 L1$ 中的可能性将显着增加。

减小 的大小states可以进一步提高它停留在 L1$ 中的机会，稍加计算就可以在每个字节中存储 4 个 2 位的状态，将大小减小states到 4KB。因此，根据您做了多少“东西”，您的缓存未命中率可能非常低。

但是，如果您在节点中跳来跳去并“填充”，情况很快就会变得更糟，从而导致nbList当前节点几乎可以保证 L2$ 未命中和潜在 L1$ 未命中，并且 K 调用state. 这可能会导致减速 10 到 50 倍。

如果您在后一种情况下使用随机访问，您应该考虑在邻居列表中存储一个额外的状态副本，以节省访问statesK 次的成本。您必须衡量这是否更快。

关于在程序中内联数据，您不必访问向量会有所收获，在这种情况下，我会估计它的收益不到 1%。

内联和 constexpr 激进的编译器会使您的计算机沸腾多年，并回复“ 42 ”作为程序的最终结果。你必须找到一个中间立场。

于 2017-10-21T17:36:46.837 回答