c - 使用分而治之的矩阵乘法

Question

问题是速度非常慢，慢得可怕，即使在很小的n下，例如:当n=1024时，一定有什么问题，有人吗？

每当函数调用时，我都没有创建新的矩阵 C，当基本情况发生时，我将新结果添加到存储在原始矩阵 C 中的先前结果中。

int **matA,**matB,**matC;

    void matmul_div_rec(int Arow,int Acol,int Brow,int Bcol,int n) {
        if(n==1)
        {
            matC[Arow][Bcol]+=matA[Arow][Acol]*matB[Brow][Bcol];
        }
        else
        {
            matmul_div_rec(Arow+0,Acol+0,Brow+0,Bcol+0,n/2);
            matmul_div_rec(Arow+0,Acol+n/2,Brow+n/2,Bcol+0,n/2);
            matmul_div_rec(Arow+0,Acol+0,Brow+0,Bcol+n/2,n/2);
            matmul_div_rec(Arow+0,Acol+n/2,Brow+n/2,Bcol+n/2,n/2);
            matmul_div_rec(Arow+n/2,Acol+0,Brow+0,Bcol+0,n/2);
            matmul_div_rec(Arow+n/2,Acol+n/2,Brow+n/2,Bcol+0,n/2);
            matmul_div_rec(Arow+n/2,Acol+0,Brow+0,Bcol+n/2,n/2);
            matmul_div_rec(Arow+n/2,Acol+n/2,Brow+n/2,Bcol+n/2,n/2);
        }
        return; }
int main()
{
    matmul_div_rec(0,0,0,0,n); //n must be the power of 2

}

Answer 1

正如 this 中简要讨论的那样论文中指出，只有使用一些额外的想法，施特拉森算法的实现(即使它是正确的)才具有竞争性的性能。其中包括例如使用所谓的 Morton order内存中矩阵存储的布局，以获得更简单的方式来寻址子矩阵，并通过更好的内存局部性改进缓存行为。此外，使用SIMD还有潜在的改进。用于在递归的基本情况下并行化矩阵加法。