c - C 语言中克罗内克积的高效计算

Question

我是 C 的新手，在我的大部分研究中，不需要比 Python 更快的东西。然而，事实证明我最近一直在做的工作需要计算相当大的 vector/矩阵，因此 C+MPI 解决方案可能是合适的。

从数学上讲，这个任务非常简单。我有很多维度 vector ~40k 并希望计算 Kronecker Product选择这些 vector 对，然后对这些克罗内克积求和。

问题是，如何有效地做到这一点？下面的代码结构，使用for循环，或者获取效果有什么问题吗？

下面描述的函数 kron 传递长度为 vector_size 的 vector A 和 B，并计算它们的 kronecker 乘积，它存储在 C 中，一个 vector_size*vector_size 矩阵。

void kron(int *A, int *B, int *C, int vector_size) {

    int i,j;

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

这对我来说似乎很好，当然(如果我没有犯一些愚蠢的语法错误)会产生正确的结果，但我暗暗怀疑嵌入的 for 循环不是最优的。如果我还有其他方法可以解决这个问题，请告诉我。欢迎提出建议。

感谢您的耐心等待和任何建议。再说一次，我对 C 语言非常缺乏经验，但是谷歌搜索并没有给我带来这个查询的乐趣。

Answer 1

既然你的循环体都是完全独立的，当然有办法加速它。在考虑 MPI 之前，最简单的方法就是已经利用了多个内核。 OpenMP 在这方面应该做得很好。

#pragma omp parallel for
for(int i = 0; i < vector_size; i++) {
    for (int j = 0; j < vector_size; j++) {
        C[i][j] = A[i] * B[j];
    }
}

现在很多编译器都支持这一点。

您也可以尝试将一些常见的表达式拖出内部循环，但是像 gcc、icc 或 clang 这样的编译器本身应该可以很好地完成这项工作:

#pragma omp parallel for
for(int i = 0; i < vector_size; ++i) {
    int const x = A[i];
    int * vec = &C[i][0];
    for (int j = 0; j < vector_size; ++j) {
        vec[j] = x * B[j];
    }
}

顺便说一句，使用 int 进行索引通常不是正确的做法。 size_t 是正确的 typedef，适用于与对象的索引和大小有关的所有内容。