c++ - C中1的稀疏矩阵的快速矩阵乘法

Question

我正在尝试执行包含稀疏数量的 1 的乘法矩阵，并将结果转换为另一个 1 的所有值 > =1。例如:

[ 1 1 0 ]   [ 1 0 0 ]    [ 2 0 0 ]    [ 1 0 0 ]
[ 0 0 0 ] x [ 1 0 0 ] => [ 0 0 0 ] => [ 0 0 0 ] (output)
[ 0 0 0 ]   [ 0 0 0 ]    [ 0 0 0 ]    [ 0 0 0 ]

(这些矩阵代表等权有向图，有助于解决一些理论问题。)到目前为止，我发现的最简单的策略是替换标准

output[i][j] += A[i][k] * B[k][j]

按位运算利用了我的输入矩阵中只有 0 和 1 并且只需要 1 这一事实s 在输出中，像这样:

void mult(int n, int A[][n], int B[][n], int output[n][n])
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                output[i][j] = output[i][j] | A[i][k] & B[k][j];
}

但是，这仍然很慢!对于中等大小的密集矩阵 (n>100)，快速基准测试表明 MATLAB 的底层 BLAS 子例程比我上面的方法快大约 3 倍!

我该怎么办？在不进行缓存级优化的情况下，我能想到的唯一主要步骤是将这些矩阵表示为仅包含 1 坐标的数组，以利用任何稀疏性，但即使在密集情况下，似乎我可以做些什么来加快速度。

Answer 1

也许你应该去缓存级别优化。其实并不难。您可以使用 C code from ulmBLAS .

在您的情况下，没有必要在汇编程序中实现微内核。根据您的实现修改第 135-143 行应该就足够了。

编辑:此外，按照 nwellnhof 的建议在 int/long 中存储/压缩 32/64 位应该会给您进一步的性能提升。尽管如此，使用阻塞(缓存友好)算法仍然是高效矩阵矩阵乘积的必要条件。