c - 矩阵旋转的性能优化

Question

我现在被性能优化实验室困在“从程序员的角度来看计算机系统”一书中，描述如下：

在N * N矩阵M中，其中N是32的倍数，旋转操作可以表示为：
转置：互换元素M（i，j）和M（j，i）
交换行：第i行与第N-1-i行交换

矩阵旋转的示例（为简单起见，N为3而不是32）：

-------                          -------
|1|2|3|                          |3|6|9|
-------                          -------
|4|5|6|    after rotate is       |2|5|8|
-------                          -------
|7|8|9|                          |1|4|7|
-------                          -------

一个简单的实现是：

#define RIDX(i,j,n) ((i)*(n)+(j))

    void naive_rotate(int dim, pixel *src, pixel *dst) 
    {
        int i, j;

        for (i = 0; i < dim; i++)
        for (j = 0; j < dim; j++)
         dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
    }

我通过inner-loop-unroll提出了一个想法。结果是：

Code Version          Speed Up
  original                1x
 unrolled by 2           1.33x
 unrolled by 4           1.33x
 unrolled by 8           1.55x
 unrolled by 16          1.67x
 unrolled by 32          1.61x

我还从pastebin.com获得了一个代码片段，看来可以解决此问题：

void rotate(int dim, pixel *src, pixel *dst) 
{
    int stride = 32;
    int count = dim >> 5;
    src += dim - 1; 
    int a1 = count;
    do {
        int a2 = dim;
        do {
            int a3 = stride;
            do {
                *dst++ = *src;
                src += dim;
            } while(--a3);
            src -= dim * stride + 1;
            dst += dim - stride;
        } while(--a2);
        src += dim * (stride + 1);
        dst -= dim * dim - stride;
    } while(--a1);
}

仔细阅读代码后，我认为该解决方案的主要思想是将32行视为一个数据区，并分别执行旋转操作。该版本的速度提高了1.85倍，超过了所有循环展开版本。

这里是问题：


在内部循环展开版本中，如果展开系数增加，为什么增量会减慢，尤其是将展开系数从8更改为16，而从4切换为8却没有效果呢？结果是否与CPU管线深度有关？如果答案是肯定的，增量的下降是否可以反映管道长度？
优化数据区版本的可能原因是什么？与原始的天真的版本似乎没有太大的本质区别。


编辑：

我的测试环境是Intel Centrino Duo架构，gcc版本为4.4

任何建议将不胜感激！

亲切的问候！

Answer 1

您在哪种处理器上进行测试？我模糊地记得，展开循环有助于处理器一次处理多个操作，但最多只能并行执行最大数量。因此，如果您的处理器只能同时处理8条指令，那么展开到16条指令将无济于事。但是了解最新处理器设计的人将不得不对我进行处理/纠正。

编辑：根据this PDF，centrino core2 duo具有两个处理器，每个处理器能够同时执行4条指令。但是，这通常不是那么简单。除非您的编译器在两个内核上都进行了优化（即，当您运行任务管理器时（如果您使用的是Windows，如果您使用的是Linux，则为top），您将看到CPU使用率达到最高）。一次运行在一个内核上。该处理器还具有14个执行阶段，因此，如果您可以保持流水线满载，则可以更快地执行。

然后，按照理论路线继续进行，一次展开即可使速度提高33％，因为您开始利用同时执行指令的优势。进行4次展开并没有真正的帮助，因为您现在仍然处于4条同时指令的限制之内。进行8次展开很有帮助，因为处理器现在可以更完全地填充流水线，因此每个时钟周期将执行更多的指令。

最后，请考虑一下麦当劳如何通过工作（我认为那是相对普遍的？）。汽车进入通行通道，在一个窗口下订单，在第二个窗口付款，在第三个窗口接收食物。如果在第二个驱动器仍在订购时进入第二个驱动器，则当两个驱动器都完成时（假设驱动器中的每个操作都经过一个“周期”或时间单位），则在经过四个周期后将完成2次完整操作。 。如果每辆车在一个窗口中完成所有操作，则第一辆车将花费3个周期来订购，付款和获取食物，然后第二辆车也将花费3个周期来订购，支付和获取食物，总共6个周期。因此，由于流水线操作的时间减少了。

当然，您必须保持管道满载才能最大程度地提高速度。 14个阶段是很多阶段，因此进入16个展开阶段仍会给您带来一些改善，因为可以进行更多的操作。

转到32位会导致性能降低，这可能与从缓存到处理器的带宽有关（再次猜测，如果不能准确地看到您的代码以及机器代码，就无法确定）。如果所有指令都无法放入高速缓存或寄存器中，则需要一些时间来准备所有指令（例如，人们必须首先进入汽车并通过驱动器进入）。如果它们全部一次到达那里，将会降低速度，并且必须对生产线进行一些改组以使操作继续进行。

请注意，从src到dst的每个移动都不是免费的，也不是单个操作。您需要对阵列进行查找，这会花费时间。

至于为什么第二个版本这么快工作的原因，我将猜测它与[]运算符有关。每次调用时，您都会对src和dst数组进行一些查找，解析指向位置的指针，然后检索内存。其他代码直接进入数组的指针并直接访问它们。基本上，对于从src到dst的每个移动，移动中都涉及较少的操作，因为通过指针放置已明确处理了查找。如果使用[]，请遵循以下步骤：


在[]内进行任何数学运算
获取指向该位置的指针（内存中的startOfArray + []）
返回内存中该位置的结果


如果您与指针一起行走，则只需进行数学运算即可（通常只是加法，无乘法），然后返回结果，因为您已经完成了第二步。

如果我是对的，那么也可以通过展开第二个代码的内部循环来获得更好的结果，以便可以同时对多个操作进行流水线处理。