1

I am pressed for time to optimize a large piece of C code for speed and I am looking for an algorithm---at the best a C "snippet"---that transposes a rectangular source matrix u[r][c] of arbitrary size (r number of rows, c number of columns) into a target matrix v[s][d] (s = c number of rows, d = r number of columns) in a "cache-friendly" i. e. data-locality respecting way. The typical size of u is around 5000 ... 15000 rows by 50 to 500 columns, and it is clear that a row-wise access of elements is very cache-inefficient.

There are many discussions on this topic in the web (nearby this 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).

I would by very thankful for any hint that helps to spare me the "reinvention of the wheel".

Martin

4

2 回答 2

1

我不认为数组数组比一般的线性数组更难转置。但是，如果您要在每个数组中有 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 瓦片可以加速 2.5 倍。另外，我尝试使用 SSE 来加速转置，但它并没有显着改变时间。我认为那是因为问题是内存受限的。

以下是 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

这是使用的完整代码。

于 2015-11-30T06:14:01.320 回答
0

所以，我猜你有一个浮点数/双精度数组。这种设置对于缓存性能已经非常不利。原因是，对于一维数组，编译器可以输出导致预取操作的代码，并且（在非常新的编译器的情况下）生成 SIMD/矢量化代码。使用指针数组，每一步都有一个尊重操作，使预取更加困难。更不用说内存对齐没有任何保证。

如果这是为了分配而您别无选择，只能从头开始编写代码，我建议您查看CBLAS是如何做到的（请注意，您仍然需要将数组“展平”）。否则，您最好使用像 OpenBLAS这样高度优化的 BLAS 实现。它经过近十年的优化，将为您的目标处理器生成最快的代码（调整缓存大小和向量指令集等内容）。

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

于 2015-11-29T16:19:42.647 回答