1

我有一个巨大的二进制矩阵，比如100000 x 100000。

阅读这篇文章http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf，我似乎明白记忆和使用二进制矩阵的最佳权衡是使用boost::dynamic_bitsets。

由于在“表 2：实现数据结构的程序的相对时间性能”中： std::vector<bool>位于最后一个位置，而boost::dynamic_bitset位于第一个位置。

在“表 3：实现数据结构的程序的相对内存使用情况”中： std::vector<bool>位于第一位置，但boost::dynamic_bitset位于第二位置。

此外，在论文的第 7 页，有以下声明：

“尽管 std::vector 的内存性能令人印象深刻，但其糟糕的时间性能使其无法在大规模应用程序中使用。”

在结论中：

“我们已经证明 boost::dynamic_bitset 在执行速度方面比大多数其他实现要高效得多，而使用 std::vector<char> 的实现在内存效率方面优于其他实现。”

现在就我而言，我的目标机器是XEON PHI。
我的目标应用程序是Game Of Life。
我已经将二进制矩阵表示为 ROWS x COLS 单元的二进制数组。

我已经尝试了具有 3 种不同配置的代码，使用带有-O3优化标志的 -the icpc编译器来构建它们：

  1. 布尔数组
  2. 布尔数组 + 矢量化，即使用此处描述的数组表示法更改代码

  3. boost::dynamic_bitsets。在这种情况下，我无法使用数组表示法更改代码，因为当我尝试时，我收到以下错误：

    error: base of array section must be pointer or array type

    使用std::vector<bool>时出现同样的错误。

观察 100000 x 100000 大小的矩阵的游戏主循环的一次迭代的性能，我发现：解决方案 2的工作速度几乎比解决方案 1快六倍，但出乎意料的是，解决方案 1的工作速度比解决方案 3快两倍。

总之，我有以下问题要问：

  1. 一般来说，存储/使用HUGE MATRIX最有效的数据结构是什么？
  2. 知道我的目标机器是XEON PHI ，我能比“回答 1”做得更好吗？
  3. 是否可以将矢量化应用于vector<bool>或boost::dynamic_bitsets？

感谢您对特定目标应用程序的回答：生命游戏。
但是在其他情况下使用巨大的二进制矩阵呢？

4

1 回答 1

1

如果你真的关心康威人生游戏中的表现，你应该改用纯粹的并行布尔数学设计。计算 8 个邻居的简单任务作为并行布尔运算非常困难，但值得一试。仅 64 路直接并行就可以收回成倍的按位成本。

在具有相同基本设计的某些 CPU 上，您可能具有一些 128 位或更高的直接并行性。

一旦您使用 64 位或更大的整数而不是布尔值，所有有效存储布尔值的问题都变得无关紧要。

几十年前我在汇编程序中这样做时，我发现一个重要的优化是在连续行之间共享信息。这样做时，查看总共九个单元而不是八个相邻单元变得更容易。所以它可能有助于实现规则可以兼容地重述：
当它的 9 个单元中有 3 个时，一个单元打开（无论它之前是否打开）。
当它的 9 个集合中有 4 个时，一个单元格保持不变。
否则它会关闭。

跨行共享信息的方式在很大程度上取决于几十年前该机器的 asm 语言和寄存器集。因此，您可能会也可能不会发现查看完整的 9 个（而不是 8 个邻居）对您有帮助。

于 2015-12-30T18:33:14.070 回答