47

我已经实现了一个矩阵乘法boost::numeric::ublas::matrix（请参阅我的完整工作增强代码）

Result result = read ();

boost::numeric::ublas::matrix<int> C;
C = boost::numeric::ublas::prod(result.A, result.B);

另一个使用标准算法（参见完整的标准代码）：

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
                                    vector< vector<int> > B) {
    int n = A.size();

    // initialise C with 0s
    vector<int> tmp(n, 0);
    vector< vector<int> > C(n, tmp);

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

这就是我测试速度的方式：

time boostImplementation.out > boostResult.txt
diff boostResult.txt correctResult.txt

time simpleImplementation.out > simpleResult.txt
diff simpleResult.txt correctResult.txt

两个程序都读取包含两个 2000 x 2000 矩阵的硬编码文本文件。这两个程序都是用这些标志编译的：

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic

我的实现用了15 秒，而提升实现用了4 多分钟！

编辑：编译后

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out

ikj 算法得到28.19 秒，Boost 得到60.99 秒。所以Boost仍然相当慢。

为什么 boost 比我的实现慢得多？

4

3 回答 3

51

正如 TJD 所指出的，uBLAS 版本的性能较慢可以部分解释为后者的调试功能。

这是 uBLAS 版本在调试时所花费的时间：

real    0m19.966s
user    0m19.809s
sys     0m0.112s

这是关闭调试的 uBLAS 版本所花费的时间（-DNDEBUG -DBOOST_UBLAS_NDEBUG添加了编译器标志）：

real    0m7.061s
user    0m6.936s
sys     0m0.096s

所以在关闭调试的情况下，uBLAS 版本几乎快了 3 倍。

剩余的性能差异可以通过引用uBLAS 常见问题解答“为什么 uBLAS 比（atlas-）BLAS 慢得多”的以下部分来解释：

ublas 的一个重要设计目标是尽可能通用。

这种普遍性几乎总是要付出代价。特别是prod函数模板可以处理不同类型的矩阵，例如稀疏矩阵或三角形矩阵。幸运的是，uBLAS 提供了针对密集矩阵乘法优化的替代方案，特别是axpy_prod和block_prod. 以下是比较不同方法的结果：

ijkalgorithm   prod   axpy_prod  block_prod
   1.335       7.061    1.330       1.278

如您所见，两者axpy_prod都比block_prod您的实现要快一些。仅测量没有 I/O 的计算时间，消除不必要的复制和仔细选择块大小block_prod（我使用 64）可以使差异更加深刻。

另请参阅uBLAS 常见问题解答和有效 uBlas 和一般代码优化。

于 2012-06-19T23:36:57.100 回答
13

我相信，您的编译器没有足够优化。uBLAS 代码大量使用模板，而模板需要大量使用优化。我在发布模式下通过 MS VC 7.1 编译器为 1000x1000 矩阵运行了您的代码，它给了我

10.064s 为 uBLAS

7.851s 代表向量

差异仍然存在，但绝不是压倒性的。uBLAS 的核心概念是惰性求值，因此prod(A, B)仅在需要时才对结果求值，例如，prod(A, B)(10,100)将立即执行，因为实际上只会计算一个元素。因此，实际上没有可以优化的整个矩阵乘法的专用算法（见下文）。但是你可以帮助图书馆一点，声明

matrix<int, column_major> B;

将运行时间减少到4.426s，这会在一只手被绑住的情况下击败您的功能。此声明使矩阵相乘时对内存的访问更加有序，从而优化了缓存的使用。

PS 阅读了 uBLAS 文档到最后 ;)，您应该已经发现实际上有一个专用函数可以一次将整个矩阵相乘。2 个功能 -axpy_prod和opb_prod. 所以

opb_prod(A, B, C, true);

即使在未优化的 row_major B 矩阵上，也可以在8.091sec 内执行，并且与您的向量算法相当

PPS 还有更多优化：

C = block_prod<matrix<int>, 1024>(A, B);

在 s 中执行4.4，无论 B 是 column_ 还是 row_ 专业。考虑一下描述：“函数 block_prod 是为大型密集矩阵设计的。” 为特定任务选择特定工具！

于 2012-06-21T11:23:50.883 回答
2

我用 uBLAS 创建了一个小网站Matrix-Matrix Product Experiments。这是关于将矩阵矩阵产品的新实现集成到 uBLAS 中。如果您已经拥有 boost 库，则它仅包含额外的 4 个文件。所以它几乎是独立的。

如果其他人可以在不同的机器上运行简单的基准测试，我会很感兴趣。

于 2016-01-22T22:45:32.113 回答