0

我必须优化以下函数，使其运行得更快：注意（这是一个较低的三角形转置）

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];
            }
        }
    } 
}
4

2 回答 2

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

选择切片大小，使其舒适地放入缓存中。

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

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

于 2012-11-30T17:19:25.847 回答
0

您可以从反转循环开始。放在j外面和i里面。原因如下：以下位置在内存中彼此相邻：

source[j][0];
source[j][1];
source[j][2];
source[j][3];

但这些位置不是：

source[0][i];
source[1][i];
source[2][i];
source[3][i];

CPU 完成对寄存器的读source[j][0]入的那一刻，您的 L1 高速缓存中就有了整个高速缓存行的数据。通过让您的读取在地址空间上线性进行而不是分散读取来利用这一点。

您也可以展开您的循环。当您可以在没有分支的情况下执行大量指令时，CPU 会喜欢它。

    for (int j = i +1 ; j < sizee ; j += 8) 
    {
        destination[i][j]= source[j][i];
        destination[i][j+1]= source[j+1][i];
        destination[i][j+2]= source[j+2][i];
        destination[i][j+3]= source[j+3][i];
        destination[i][j+4]= source[j+4][i];
        destination[i][j+5]= source[j+5][i];
        destination[i][j+6]= source[j+6][i];
        destination[i][j+7]= source[j+7][i];
    }

如果您的 CPU 具有预取指令，那么您可以在完成当前内存块之前要求它开始加载下一行数据。

于 2012-11-30T17:47:05.077 回答