c++ - 使用 HUGE 二进制矩阵的最有效方法？

Question

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

阅读本文http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf ，我似乎明白，内存和使用二进制矩阵的最佳折衷是使用 boost::dynamic_bitsets。

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

并且在“表 3:实现数据结构的程序的相对内存使用情况”:std::vector 排在第一位，但 boost::dynamic_bitset 排在第二位。

此外，在论文第 7 页，有以下内容声明:

"Despite the impressive memory performance of std::vector, its dismal time performance renders it unusable in large-scale applications."

结论:

"We have shown that boost::dynamic_bitset is considerably more efficient than most of the other implementations in terms of execution speed, while the implementation using std::vector<char> outperformed the other implementations in terms of memory efficiency."

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

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

1. bool 数组
2. bool 数组 + 矢量化，即使用数组表示法更改代码，如here所述

3. boost::dynamic_bitsets。在这种情况下，我无法使用 Array Notation 更改代码，因为当我尝试时，出现以下错误:

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

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

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

最后，我有以下问题要提出:

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

感谢您对具体目标应用:Game Of Life 的回答。
但是如何处理其他上下文中的巨大二进制矩阵？

Answer 1

如果您真的关心 Conway 人生游戏中的性能，您应该切换到纯位并行 bool 数学设计。计算 8 个邻居的简单任务作为并行 bool 运算非常困难，但值得麻烦。仅 64 路直接并行就可以收回按位成本的数倍。

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

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

当我几十年前在汇编程序中这样做时，我发现一个重要的优化是在连续的行之间共享信息。这样做时，查看一个包含九个单元格而不是八个邻居的 block 的总数变得更容易。因此，了解可以兼容地重述规则可能会有所帮助:
当其 9 组中有 3 个时，一个单元格将打开(无论之前是否打开)。
当它的一组 9 中有 4 个时，一个单元格不变。
否则它会关闭。

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