优化数组转置功能

Question

我正在完成一项家庭作业,而且我的解决方案已经被困了几个小时.我们给出的问题是优化以下代码,以便它运行得更快,无论它变得多么混乱.我们应该使用诸如利用缓存块和循环展开之类的东西.

问题:

//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矩阵中.

我也尝试过使用指针代替数组访问器,但我认为实际上并没有以任何方式加速程序.

任何帮助将不胜感激.

谢谢

Answer 1

缓存阻塞可能很有用.举个例子,假设我们的缓存行大小为64字节(这是x86目前使用的).因此,对于足够大的矩阵,使其大于缓存大小,那么如果我们转置16x16块(因为sizeof(int)== 4,因此16个整数适合缓存行,假设矩阵在缓存行边界上对齐) )我们需要从内存中加载32(来自源矩阵的16个,来自目标矩阵的16个)来自内存的缓存行并存储另外16行(即使存储不是连续的).相反,如果没有高速缓存阻塞转置等效的16*16元素,则需要我们从源矩阵加载16个高速缓存行,但是16*16 = 256个高速缓存行要加载然后存储用于目标矩阵.