c - 优化下三角矩阵转置

Question

我必须优化以下函数，使其运行得更快:注意(这是一个下三角转置)

void trans(int ** source, int** destination)
{
    for (int i = 0 ; i < sizee ; i ++) 
    { 
        for (int j = i +1 ; j < sizee ; j ++) 
        {
            destination[i][j]= source[j][i];
        } 
    }
}

我知道对源的访问没有空间局部性，因为它是按列访问的，但我不明白如何实现它。任何帮助表示赞赏。谢谢。

编辑:我尝试平铺，尽管运行时有所改善，但优化的转置产生了错误的结果:

#define b 2
for (int ii = 0 ; ii < sizee ; ii += b) { 
    for (int jj = ii +1 ; jj < sizee ; jj +=b) {
        for(int i = ii; i < std::min(ii+b-1, sizee); i++)
        {
            for(int j = jj; j < std::min(jj+b-1, sizee); j++)
            {
        destination[i][j]= source[j][i];
            }
        }
    } 
}

Answer 1

执行缓存友好转置算法的一种方法是平铺数据:

- for each square tile
    - load a square tile from source into a temporary buffer
    - transpose tile in-place
    - write out transpose tile to its correct location in dest

选择图 block 大小，使其适合缓存。

为了进一步优化，您可以使用就 map block 转置例程 - 您可以进行大量的微优化，例如8x8 或 16x16 就地转置。

<小时/>

注意:当部分转置的要求并不明显时，为问题的原始版本提供了此答案。我将答案留在这里，因为下面有一些有用的评论。