性能优化矩阵旋转

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

我想出了通过内环路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倍，压倒所有的循环展开版本。

这里有几个问题：

1. 在内环-UNROLL版本，为什么不增加减慢，如果展开因素增加，特别是展开系数从8更改为16，这不影响从4切换到8时是否一样？结果与CPU管道的深度有关系吗？如果答案是肯定的，增量的降低是否反映了管道长度？

2. 优化数据区版本的可能原因是什么？看起来与原始的天真版本没有太大的本质区别。

编辑：

我的测试环境是英特尔迅驰双核架构和gcc的优化版本是4.4

任何意见，将不胜感激！

亲切的问候！

Answer 1

你在测试这种处理器是什么样的？我记忆犹新，当处理器可以同时处理多个操作时，展开循环会有所帮助，但只能达到最大并行执行次数。所以如果你的处理器只能处理8条同步指令，那么展开到16就无济于事。但是具有更新处理器设计知识的人将不得不提供/纠正我。

编辑：根据this PDF，centrino core2 duo有两个处理器，每个处理器可以同时执行4条指令。不过，这通常不是那么简单。除非你的编译器在两个内核之间进行了优化（例如，当你运行任务管理器（如果你在windows上，如果你是在linux上，那么你会看到CPU使用率最高），你的过程将是一次运行一个内核。该处理器还具有14个执行阶段，所以如果你能保持管道充满，你会得到更快的执行。

沿着理论路线继续前进，然后，单次展开可以使速度提高33％，因为您开始利用同步指令执行的优势。去4次展示并没有什么帮助，因为你现在仍然处于4次同时指令限制内。转到8展开是有帮助的，因为处理器现在可以更完全地填充流水线，所以更多指令将在每个时钟周期执行。

对于这最后，想想麦当劳如何驾车穿越作品（我认为这是相对广泛的？）。一辆汽车进入驾驶舱，在一个窗口下单，在第二个窗口付款，并在第三个窗口接收食物。如果第二个驱动器在第一个驱动器仍然订购时进入，那么在两个驱动器完成时（假设驱动器中的每个操作都需要一个“周期”或时间单位），则在完成4个周期的时间后完成2个完整操作。如果每辆车在一个窗口中完成所有操作，那么第一辆车需要3个周期来订购，支付和获取食物，然后第二辆车还需要3个周期来订购，支付和获取食物，总计6个周期。所以，由于流水线操作时间减少。

当然，你必须保持管道充分，以获得最大的速度提高。 14个阶段是很多阶段，所以去16个unrolls会给你一些改进，因为更多的操作可能正在进行中。

去32导致性能下降可能与处理器从缓存带宽（再次猜测，不能确切地知道你没有看到你的代码，以及机器代码）有关。如果所有的指令都无法放入缓存或寄存器中，那么需要一些时间来准备它们全部运行（即人们必须首先进入他们的汽车并开车通过）。如果一次全部到达那里，速度会有所下降，为了使操作继续进行，必须进行一些洗牌。

请注意，从src到dst的每次移动都不是空闲或单个操作。你有查询到阵列，这花费时间。至于为什么第二个版本如此快速地工作，我会冒险猜测它与[]运算符有关。每次被调用时，您都在对src和dst数组进行查找，解析指向位置的指针，然后检索内存。其他代码直接访问数组的指针并直接访问它们;基本上，对于从src到dst的每个移动，移动中涉及的操作较少，因为查找已通过指针放置明确处理。如果你使用[]，这些步骤如下：

• 做[]内
• 一个指针指向该位置（startOfArray + []在内存中）
• 回报的那个位置的结果的任何数学在内存中

如果你和一个指针一起走动，你只需要做数学运算（通常只是一个加法，不要乘），然后返回结果，因为你已经完成了第二步。

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

Answer 2

问题的第一部分我不确定。我最初的想法是某种缓存问题，但你只访问每个项目一次。

其他代码可能会因coupe原因而更快。

1）循环倒数而不是up。比较循环计数器为零在大多数体系结构上都没有花费（一个标志由自动减量设置），您必须在每次迭代时明确地将其与最大值进行比较。

2）内循环没有数学。你在内循环中做了一堆数学。我在主代码中看到2次减法，并在宏中看到一次乘法（使用两次）。还有隐式的索引添加到数组的基地址，这可以通过使用指针来避免（x86上的良好寻址模式也应该消除这种惩罚）。

在编写优化代码时，您总是从内部构建它。这意味着采取最内环路并将其内容减少到接近零。在这种情况下，移动数据是不可避免的。增加一个指针是达到下一个项目的最低限度，另一个指针需要添加一个偏移量才能到达它的下一个项目。所以至少我们有4个操作：加载，存储，增加，添加。如果支持“随后增量移动”的体系结构，则总共有2条指令。在英特尔，我怀疑它是3或4条指令。比减法和乘法等任何东西都会增加重要的代码。

看看每个版本的汇编代码应该提供很多见解。

如果您在一个完全符合缓存的小矩阵（32x32）上重复执行此操作，应该会看到实现中更加显着的差异。即使数据副本的数量相同，运行在1024x1024矩阵上的速度也会比单个32x32的1024个旋转速度慢得多。

Answer 3

1. 循环展开的主要目的是减少循环控制花费的时间（完成测试，增加计数器等）。尽管这是一种收益递减的情况，因为随着循环越来越多地展开，花在循环控制上的时间变得越来越少。就像mmr说的那样，循环展开也可以帮助编译器并行执行，但只能达到一个点。

2. “数据区”算法似乎是高速缓存高效矩阵转置算法的一个版本。计算转置问题的天真方式是导致大量的缓存未命中。对于源数组，您正沿着每一行访问内存，因此它以逐个元素的线性方式访问。但是，这要求您沿列访问目标阵列，这意味着每次访问元素时都跳过dim个元素。基本上，对于输入的每一行，您正在遍历整个目标矩阵的内存。由于整个矩阵可能不适合缓存，因此内存必须经常从缓存中加载和卸载。

   “数据区域”算法采用按列访问的矩阵，并且一次只执行32行的转置，因此您所遍历的内存量为32xstride，这应该完全适合缓存。基本上，目标是处理适合缓存的子部分，并减少在内存中跳跃的次数。