转载请注明出处：
即对原有图像矩阵先进行一次对折，然后再进行一次翻转，就可以得到我们需要的逆时针旋转90°之后的矩阵。

其中我们用以下结构体表示一张图像的像素点：

typedef struct {      unsigned short red;   /* R value */      unsigned short green; /* G value */      unsigned short blue;  /* B value */  } pixel;

red、green、blue分别表示一张彩色图像的红绿蓝三个通道。

原旋转函数如下：

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

图像是标准的正方形，用一维数组表示，第（i,j）个像素表示为I[RIDX(i,j,n)]，n为图像边长。

参数：

RIDX(i,j,dim)读取目标像素点，RIDX(dim-1-j,i,dim)将i、j参数位置互换，实现了斜角对折，dim-1-j实现了上下翻转。

优化目标：使旋转操作运行的更快

当前我们拥有一个driver.c文件，可以对原函数和我们优化的函数进行测试，得到表示程序运行性能的CPE（每元素周期数）参数。

我们的任务就是实现优化代码，与原有代码同时运行进行参数的对比，查看代码优化情况。

优化的主要方法

  1. 循环展开
  2. 并行计算
  3. 提前计算
  4. 分块运算
  5. 避免复杂运算
  6. 减少函数调用
  7. 提高Cache命中率

循环主体只存在一条语句，该语句为内存的读写（读取一个源像素，再写入目标像素），不涉及函数调用与计算。所以我们的优化手段有提高Cache命中率、避免复杂运算、分块运算、循环展开与并行计算。

优化一：提高Cache命中率

在矩阵运算中，提高Cache命中率是最容易想到的方法，常见的是外循环按行遍历与外循环按列遍历的对比，因为存储顺序是行序，所以前者的运行速度会明显优于后者。

在已给出的naive_rotate函数中，核心循环语句涉及到读取一个像素点与写入一个像素点，显然写入像素点比读取像素点更耗费时间，这是由存储器的性质决定的，所以我们应该优先对写入像素点的索引进行优化。
在这里插入图片描述
上图描述了8种数组索引顺序，位于上方的蓝色方块代表原始图像，黄色箭头表示原始像素的读取顺序，位于下方的蓝色方块代表旋转后图像，红色箭头表示目标像素的写入顺序。

由于循环体执行速度主要与数据写入相关，所以我们优先考虑红色箭头也就是写入像素的cache命中率。

第一组到第四组的写入像素都是按照列序，理论上写入效果应该最差，第五第六组正向行序写入执行效果应该是最好的，第七第八组逆向行序应该稍差。下面我们给出分别按照8种不同顺序索引的代码，使用driver测试出他们的运行效率：

void rotate_leftup(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)]; } void rotate_leftdown(int dim, pixel *src, pixel *dst)  {     int i, j;     for (i = dim-1; i > -1; i--)     for (j = 0; j < dim; j++)         dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)]; } void rotate_rightup(int dim, pixel *src, pixel *dst)  {     int i, j;     for (i = 0; i < dim; i++)     for (j = dim-1; j > -1; j--)         dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)]; } void rotate_rightdown(int dim, pixel *src, pixel *dst)  {