运行-任意大小的矩形矩阵的时间高效转置

Question

我时间紧迫，无法优化一大段 C 代码以提高速度，我正在寻找一种算法---最好是 C "snippet"---转置矩形源矩阵u[r][c]任意大小（r行数，c 列数）到目标矩阵 v[s][d]（s = c 行数，d = r 列数）在 "cache-friendly" 一世。 e.数据局部性尊重方式。 u 的典型大小约为 5000 ... 15000 行乘以 50 到 500 列，显然按行访问元素的缓存效率非常低。

网上有很多关于这个话题的讨论（在这个thread), but as far as I see all of them discuss the spacial cases like square matrices, u[r][r], or the definition an on-dimensional array, e. g. u[r * c], not the above mentioned "array of arrays" (of equal length) used in my context of Numerical Recipes (background see here附近）。

如果有任何提示可以帮助我免除 "reinvention of the wheel"，我将非常感谢。

马丁

Answer 1

所以，我猜你有一个 floats/doubles 的数组。这种设置对于缓存性能来说已经很糟糕了。原因是对于一维数组，编译器可以输出导致预取操作的代码，并且（在非常新的编译器的情况下）生成 SIMD/vectorized 代码。对于指针数组，每个步骤都有一个遵从操作，这使得预取更加困难。更不用说内存对齐没有任何保证。

如果这是为了作业而你别无选择只能从头开始编写代码，我建议你看看 CBLAS 是如何做到的（注意你仍然需要你的数组是"flattened")。否则，你 much 更好地使用高度优化的 BLAS 实现，例如 OpenBLAS。它经过近十年的优化，将为您的目标处理器生成最快的代码（针对缓存大小和矢量指令集等进行调整）。

tl;dr 是无论如何使用数组的数组都会导致糟糕的性能。通过使用 #define 访问数组元素，展平数组并使代码易于阅读。

Answer 2

我不认为数组的数组比一般的线性数组更难转置。但是，如果每个数组中有 50 列，这听起来很糟糕：它可能不足以隐藏指针取消引用的开销。

我认为缓存友好实现的总体策略是相同的：以块的形式处理矩阵，根据实验选择性能最佳的块大小。

template<int BLOCK>
void TransposeBlocked(Matrix &dst, const Matrix &src) {
    int r = dst.r, c = dst.c;
    assert(r == src.c && c == src.r);
    for (int i = 0; i < r; i += BLOCK)
        for (int j = 0; j < c; j += BLOCK) {
            if (i + BLOCK <= r && j + BLOCK <= c)
                ProcessFullBlock<BLOCK>(dst.data, src.data, i, j);
            else
                ProcessPartialBlock(dst.data, src.data, r, c, i, j, BLOCK);
        }
}

我尝试优化 r = 10000，c = 500 时的最佳情况（使用 float 类型） .在我的本地机器上，128 x 128 tiles 提供了 2.5 倍的加速。另外，我曾尝试使用 SSE 来加速换位，但它确实 not 显着改变时间。我认为那是因为问题是内存限制。

以下是 Core2 E4700 2.6GHz 上各种实现的完整计时（每次启动 100 次）：

Trivial: 6.111 sec
Blocked(4): 8.370 sec
Blocked(16): 3.934 sec
Blocked(64): 2.604 sec
Blocked(128): 2.441 sec
Blocked(256): 2.266 sec
BlockedSSE(16): 4.158 sec
BlockedSSE(64): 2.604 sec
BlockedSSE(128): 2.245 sec
BlockedSSE(256): 2.036 sec

这里是使用的full code。

运行-任意大小的矩形矩阵的时间高效转置

Run-time efficient transposition of a rectangular matrix of arbitrary size

c

performance

transpose

matrix

cache-oblivious