c++ - 通过矩阵转置进行矩阵乘法优化

我正在分配一个矩阵，以减少矩阵乘法操作的高速缓存未命中的工作。据我从几个同学那里了解到，我应该得到8倍的改进。但是，我只得到2倍...我可能做错了什么？

Full Source on GitHub

void transpose(int size, matrix m) {
    int i, j;
    for (i = 0; i < size; i++)
        for (j = 0; j < size; j++)
            std::swap(m.element[i][j], m.element[j][i]);
}

void mm(matrix a, matrix b, matrix result) {
    int i, j, k;
    int size = a.size;
    long long before, after;

    before = wall_clock_time();
    // Do the multiplication
    transpose(size, b); // transpose the matrix to reduce cache miss
    for (i = 0; i < size; i++)
        for (j = 0; j < size; j++) {
            int tmp = 0; // save memory writes
            for(k = 0; k < size; k++)
                tmp += a.element[i][k] * b.element[j][k];
            result.element[i][j] = tmp;
        }
    after = wall_clock_time();
    fprintf(stderr, "Matrix multiplication took %1.2f seconds\n", ((float)(after - before))/1000000000);
}

到目前为止我做得对吗？

仅供引用:我需要做的下一个优化是使用SIMD/Intel SSE3

最佳答案

否。您的移调有问题。在开始担心性能之前，您应该已经看到了此问题。当您进行各种形式的优化时，使用幼稚但次优的实现作为测试始终是一个好主意。如果无法给出正确的答案，那么实现100倍加速的优化将毫无值(value)。

另一个有用的优化方法是通过引用传递。您正在传递拷贝。实际上，您的matrix result可能永远不会消失，因为您正在传递拷贝。再一次，您应该已经测试过。

有助于加速的另一个优化是缓存一些指针。这仍然很慢:

for(k = 0; k < size; k++)
    tmp += a.element[i][k] * b.element[j][k];
result.element[i][j] = tmp;

优化程序可能会找到解决指针问题的方法，但可能不会。如果您不使用非标准的__restrict__关键字来告诉编译器您的矩阵不重叠，至少不会。缓存指针，因此您不必执行a.element[i]，b.element[j]和result.element[i]。而且仍然可能有助于告诉编译器这些数组与__restrict__关键字不重叠。

附录
查看代码后，需要帮助。首先要稍作评论。您不是在编写C++。您的代码是C，带有一点C++提示。您使用的是struct而不是class，而不是malloc，而不是new，而不是typedef struct，是struct，是C头文件而不是C++头文件。

由于您执行了struct matrix，因此我对由于复制构造函数而导致的运行缓慢的评论不正确。那是不正确的，甚至更糟!将隐式定义的拷贝构造函数与包含裸指针的类或结构结合使用，真是火上浇油。如果有人调用m(a, a, a_squared)来获取矩阵a的平方，那么您将被极大地烫伤。如果有人期望m(a, a, a)对a 2进行就地计算，那么您将被烧得更糟。

从数学上讲，您的代码仅涵盖了矩阵乘法问题的一小部分。如果有人想将100x1000矩阵乘以1000x200矩阵怎么办？完全正确，但是您的代码无法处理它，因为您的代码仅适用于平方矩阵。另一方面，您的代码将允许某人将100x100矩阵乘以200x200矩阵，这没有任何意义。

从结构上讲，您的代码几乎可以保证100％的保证，因为您使用的是参差不齐的数组，它会变慢。 malloc可以在整个内存中喷射矩阵的行。如果矩阵在内部表示为连续数组，但就像NxM矩阵一样被访问，则将获得更好的性能。 C++为此提供了一些不错的机制。