优化阵列转置功能

我正在做一个家庭作业任务，并且我一直在我的解决方案上停留数小时。我们给出的问题是优化以下代码，以便运行速度更快，无论它变得多么混乱。我们应该使用诸如利用缓存块和循环展开之类的东西。优化阵列转置功能

问题：

//transpose a dim x dim matrix into dist by swapping all i,j with j,i 
void transpose(int *dst, int *src, int dim) { 
    int i, j; 

    for(i = 0; i < dim; i++) { 
     for(j = 0; j < dim; j++) { 
       dst[j*dim + i] = src[i*dim + j]; 
     } 
    } 
}

我到目前为止有：

//attempt 1 
void transpose(int *dst, int *src, int dim) { 
    int i, j, id, jd; 

    id = 0; 
    for(i = 0; i < dim; i++, id+=dim) { 
     jd = 0; 
     for(j = 0; j < dim; j++, jd+=dim) { 
       dst[jd + i] = src[id + j]; 
     } 
    } 
} 

//attempt 2 
void transpose(int *dst, int *src, int dim) { 
    int i, j, id; 
    int *pd, *ps; 
    id = 0; 
    for(i = 0; i < dim; i++, id+=dim) { 
     pd = dst + i; 
     ps = src + id; 
     for(j = 0; j < dim; j++) { 
       *pd = *ps++; 
       pd += dim; 
     } 
    } 
}

一些想法，请纠正我，如果我错了：

我曾经想过循环展开，但我不认为这会有所帮助，因为我们不知道NxN矩阵是否具有素数维。如果我检查了这一点，它会包含过多的计算，这只会减慢函数的速度。

缓存块也不会是非常有用的，因为无论什么时候，我们将线性访问一个阵列（1,2,3,4），而其他的我们会在N的跳跃来访问虽然我们可以得到该功能可以更快地滥用缓存并访问src块，但将这些缓存放入dst矩阵仍需要很长时间。

我也曾尝试使用指针而不是数组访问器，但我不认为这实际上加快以任何方式程序。

任何帮助将不胜感激。

谢谢

来源

2012-05-30 Glen Takahashi

缓存阻塞可能很有用。举个例子，假设我们有一个64字节的缓存行大小（这是x86今天使用的）。所以对于一个足够大的矩阵来说，它大于缓存大小，那么如果我们转置一个16x16块（因为sizeof（int）== 4，因此16个int适合缓存行，假设矩阵在缓存行上对齐）我们需要从内存中加载32条（源矩阵16条，来自目标矩阵的16条，然后我们可以将它们弄脏），并存储另外16行（即使存储不是顺序的）。相反，如果没有高速缓存阻塞转置等效的16 * 16元素，则需要我们从源矩阵中加载16个高速缓存行，但要加载16 * 16 = 256个高速缓存行，然后存储为目标矩阵。

来源

2012-05-30 09:14:43 janneb

这是要走的路。 “缓存遗忘矩阵转置”是谷歌的短语。注意：通过采用2 * 2个16 * 16高速缓存行的瓦片，可以填充4096个字节，这是（大多数）x86机器上的内存页。 – wildplasser

是的!!!根据我的经验，优化内存访问可以产生几倍的提升。 – sharptooth

这是正确的答案。缓存优化>>其余。 –

展开对大矩阵很有用。
如果矩阵大小不是展开次数的倍数，则需要一些代码来处理多余的元素。但是这将在最关键的循环之外，所以对于大型矩阵来说它是值得的。

关于访问的方向 - 它可能是更好的线性阅读并在N跳写，而不是反之亦然。这是因为读取操作会阻塞CPU，而写入操作不会（达到限制）。

其他建议：
1.你可以使用并行？ OpenMP可以提供帮助（但如果您希望提供单CPU性能，那就不好）。
2.拆开函数并阅读它，重点关注最内层的循环。你可能会发现你在C代码中不会注意到的东西。
3.使用递减计数器（停在0）可能会稍微提高计数器的效率。
4.编译器必须假设src和dst可以别名（指向相同或重叠的存储器），这限制了它的优化选项。如果你能以某种方式告诉编译器它们不能重叠，这可能是很大的帮助。但是，我不知道如何做到这一点（也许使用restrict限定符）。

来源

2012-05-30 06:34:59 ugoren

只是一个想法如何实现展开：

void transpose(int *dst, int *src, int dim) { 
    int i, j; 
    const int dim1 = (dim/4) * 4; 

    for(i = 0; i < dim; i++) { 
     for(j = 0; j < dim1; j+=4) { 
       dst[j*dim + i]  = src[i*dim + j]; 
       dst[(j+1)*dim + i] = src[i*dim + (j+1)]; 
       dst[(j+2)*dim + i] = src[i*dim + (j+2)]; 
       dst[(j+3)*dim + i] = src[i*dim + (j+3)]; 
     } 
     for(; j < dim; j++) { 
       dst[j*dim + i] = src[i*dim + j]; 
     } 
     __builtin_prefetch (&src[(i+1)*dim], 0, 1); 
    } 
}

五言，你应该删除计数（如i*dim）从内环，因为你已经在你的努力做到了。

高速缓存预取可以被用于源矩阵。

来源

2012-05-30 09:03:37 SKi

你可能知道这个，但是register int（你告诉编译器把它放在寄存器中是明智的）。并使int的unsigned，可能会让事情变得更快一点。

来源

2012-05-30 09:52:22 fhtuft

注册关键字在这里并没有真正的帮助。问题是缓存/内存导向和微型优化寄存器的使用将无济于事。 –

凌乱不是问题，所以：我会为每个矩阵添加一个transposed标志。该标志指示矩阵的存储数据阵列是以正常还是颠倒的顺序来解释。

除了每个矩阵参数之外，所有矩阵操作都应该接收这些新标志。在每个操作内部实现所有可能的标志组合的代码。也许宏可以节省冗余写作。

在这个新的实现中，矩阵转置只是切换标志：转置操作所需的空间和时间是恒定的。

来源

2012-05-30 09:58:51

优化阵列转置功能

回答

相关问题