矩阵乘法的矩阵乘法优化

Question

我正在进行一项任务,我转换矩阵以减少矩阵乘法运算的缓存未命中.根据我对几个同学的理解,我应该得到8倍的提升.但是,我只得到2倍......我可能做错了什么？

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

Answer 1

我到目前为止做得对吗？

不,你的转置有问题.在开始担心性能之前,您应该已经看过这个问题.当你正在做的任何一种黑客周围的优化它总是一个好主意,用天真的,但不理想的实现作为一个测试.如果没有得到正确的答案,那么实现100倍加速的优化是没有价值的.

另一个有用的优化是通过引用传递.你正在传递副本.事实上,你matrix result可能永远不会因为你传递副本而离开.再一次,你应该测试一下.

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

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

优化器可能会看到指针问题的方法,但可能没有.至少不是如果你不使用nonstandard __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²的就地计​​算,你会被烧得更厉害 .

在数学上,您的代码仅涵盖矩阵乘法问题的一小部分.如果有人想将100x1000矩阵乘以1000x200矩阵怎么办？这是完全有效的,但是您的代码无法处理它,因为您的代码仅适用于方形矩阵.另一方面,你的代码会让某人将100x100矩阵乘以200x200矩阵,这没有多大意义.

从结构上讲,由于您使用了不规则的数组,因此您的代码几乎可以100%保证它会很慢.malloc可以在内存中喷洒矩阵的行.如果矩阵在内部表示为连续数组但是被访问就好像它是NxM矩阵,那么你将获得更好的性能.C++为此提供了一些很好的机制.