深入理解计算机系统CSAPP-perfLab：kernels.c性能优化实验：smooth优化详细实验日志（含四个优化版本）

客官°小女子只卖身不卖艺 2023-05-30 09:03 1阅读 0赞

### 目录 ###

*   *  一、实验内容
     *  二、相关知识
     *   *   *  1、 平滑处理流程
             *  2、 平滑计算过程
             *   *  1) 四个顶点
                 *  2) 除顶点外的四条边上的像素点
                 *  3) 其他像素点
             *  3、 服务器与本地计算机之间复制文件的方法
             *   *  1) 把本地文件拷贝到服务器
                 *  2) 把服务器文件拷贝到本地计算机
             *  4、 常见性能优化方法
             *  5、 Makefile规则
             *  6、64位系统中RGB像素点(结构体)的存储
             *  7、 数组在内存中的存储原理
     *  三、实验步骤
     *  四、 程序优化各个版本
     *   *   *  写在前面
             *   *  1、 添加版本的方法
                 *  2、 声明版本描述的方法
             *  初始版本
             *  版本一：消除不必要的函数调用并独立计算不同位置的像素点
             *  版本二：纵向的动态规划
             *  版本三：使用三个指针
             *  版本四：结合上述三个版本
     *  五、遇到的问题及解决方法

## 一、实验内容 ##

1、 学习图像平滑功能的实现方法与平滑处理流程；  
2、 学习基本的性能优化方法；  
3、 修改kernels.c文件，测试每个版本的CPE；  
4、 本次实验需要优化smooth函数，尽可能提高程序性能。

## 二、相关知识 ##

#### 1、 平滑处理流程 ####

![在这里插入图片描述][20191108185645990.png]

#### 2、 平滑计算过程 ####

![在这里插入图片描述][20191108185704381.png]

##### 1) 四个顶点 #####

取相邻四个像素点的平均值；

##### 2) 除顶点外的四条边上的像素点 #####

取相邻六个像素点的平均值；

##### 3) 其他像素点 #####

取相邻九个像素点的平均值。

#### 3、 服务器与本地计算机之间复制文件的方法 ####

##### 1) 把本地文件拷贝到服务器 #####

scp 本地文件路径 用户名@服务器地址:/服务器路径

##### 2) 把服务器文件拷贝到本地计算机 #####

scp 用户名@服务器地址:/服务器路径 本地文件路径

#### 4、 常见性能优化方法 ####

代码移动、减少函数调用、减少访存次数、分支预测、循环展开、并行处理、cache友好等。

#### 5、 Makefile规则 ####

target …:prerequisites …  
command 1  
command 2

target：即目标文件，可以是Object File、执行文件、一个标签；  
prerequisites：即要生成该target所需要（依赖）的文件或是目标；  
command即make需要执行的命令，可以是任意的Shell命令。

注意，要执行的命令行一定要以一个Tab键作为开头。在Makefile中的定义的变量，就像是C/C++语言中的宏一样，代表了一个文本字串，Makefile中执行的时候其会自动原模原样地展开。变量在声明时需要给予初值，而在使用时，需要给在变量名前加上“$”符号，但最好用小括号“()”或是大括号“\{\}”。

#### 6、64位系统中RGB像素点(结构体)的存储 ####

![在这里插入图片描述][2019110423484818.png]  
可以看到，每一个像素点占0.75个字长。  
进一步分析可知，只有1/2的像素点存储在一个块中，读或写余下的像素点需要访问两个块。

#### 7、 数组在内存中的存储原理 ####

内存是一维的，因此不管是一维数组、二维数据、n维数组，在内存中都是以一维的方式存储的。二维数组是以行优先的规则在内存中存储的。

![在这里插入图片描述][20191104235005672.png]

## 三、实验步骤 ##

说明：由于我的老师是把实验文件直接放在了服务器里并且设置好了每位同学的用户名，这里我将整个perfLab文件夹复制到本地计算机，通过本地编译器编译，以便进一步研究优化方案。如果老师是通过课程中心、通知群、邮箱等下发的实验文件，直接下载文件之后修改kernels.c就好啦！

1、 进入终端。若为Windows操作系统，按下”Windows”+”R”，输入”cmd”进入；若为Linux操作系统，在首页选择”Terminal”。

2、 输入指令” ssh 域名-l用户名”，输入密码。登陆服务器。

3、 成功登陆之后，可以通过pwd命令与ls命令查看当前所在目录与当前目录下的文件。如果需要退出登录，输入exit。

4、 在登录状态下，cd进入perfLab文件夹内，执行perf\_init命令进行初始化。  
![在这里插入图片描述][20191105003124534.png]

5、 从服务器中拷贝文件到本地：  
通过”scp 本地文件路径 用户名@服务器地址:/服务器路径”将本地文件拷贝到服务器，也可以通过” scp 用户名@服务器地址:/服务器路径 本地文件路径”将服务器文件拷贝到本地。对于文件夹的拷贝，需要在scp后加”-r”参数。

这里我先将实验文件从服务器中拷贝到本地，修改完成之后再上传回服务器。也可以直接在服务器通过vim修改文件。

6、 回到服务器，在perfLab文件夹下执行make。  
![在这里插入图片描述][20191105003059869.png]

7、 输入“./driver”命令进行评分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70]

## 四、 程序优化各个版本 ##

#### 写在前面 ####

关于kernels.c的优化作如下说明：

##### 1、 添加版本的方法 #####

建议通过添加新版本而不是修改smooth()函数的方式进行优化。

首先，我们新增函数并在函数体内实现图像平滑处理功能，函数参数同smooth函数保持一致。比如，我新增了函数名为”smooth1”的函数：

void smooth1(int dim, pixel *src, pixel *dst) {  … }

然后，我们通过add\_smooth\_function()方法添加该函数版本，如：

add_smooth_function(&smooth1, smooth_descr);

##### 2、 声明版本描述的方法 #####

尽管我们添加了不同的优化版本，但由于我们没有声明版本描述，因此在评分过程中，程序提示：

> Smooth: Version = smooth: Current working version:

我们并不能在评分页面区分不同的版本。为解决这一问题，我们需要声明版本描述：

首先，在新增函数之后，我们定义一个字符数组，并令其初值为我们想要的版本描述信息。如：

char smooth1_descr[] = "smooth1: Current working version";

然后，我们将add\_smooth\_function()方法的第二个参数改为字符数组名，如：

add_smooth_function(&smooth1, smooth1_descr);

#### 初始版本 ####

void naive_smooth(int dim, pixel *src, pixel *dst) { 
    	int i, j;
    	for (i = 0; i < dim; i++)
    		for (j = 0; j < dim; j++)
    			//调用avg函数，得到所需均值
    			dst[RIDX(i, j, dim)] = avg(dim, i, j, src);
    }

naive\_smooth()函数调用了avg()函数，我们分析一下avg()函数的内容：

static pixel avg(int dim, int i, int j, pixel *src) { 
    	int ii, jj;
    	pixel_sum sum;
    	pixel current_pixel;
    	initialize_pixel_sum(&sum);
    	//在for循环条件内，通过sum()与min()确定需要处理的像素点个数
    	for(ii = max(i-1, 0); ii <= min(i+1, dim-1); ii++)
    		for(jj = max(j-1, 0); jj <= min(j+1, dim-1); jj++)
    			//每加一个像素点，计数器的值加一，保存在src中
    			accumulate_sum(&sum, src[RIDX(ii, jj, dim)]);
    	//调用函数计算除法，这里很明显是变量除变量的形式
    	assign_sum_to_pixel(&current_pixel, sum);
    	//返回一个像素点
    	return current_pixel;
    }

在naive\_smooth()函数中，按顺序对src中每个像素点调用avg()函数，将返回值保存在dst的对应位置。在avg()函数中，ii与jj选择像素点，通过accumulate\_sum()函数累加，通过assign\_sum\_to\_pixel()函数得到平均值，最后将结果current\_pixel返回。可以看到这里存在过多的函数调用，如在每次for循环内都调用一次min()或max()函数，因此可以预料到效率很低。

#### 版本一：消除不必要的函数调用并独立计算不同位置的像素点 ####

考虑到虽然不同位置的像素点需要取相邻的不同数目的像素点的平均值，但数目只有4、6、9。  
![在这里插入图片描述][20191108191348348.png]  
结合上图，分析可知：对于四个顶点，我们需要取相邻四个像素点的平均值；对于除顶点外的四条边上的像素点，我们需要取相邻六个像素点的平均值；对于其他像素点，我们需要取相邻九个像素点的平均值。

我们按照行访问顺序，针对不同的求平均值的情况分开处理，即独立计算不同位置的像素点，从而将所有除法运算由除变量改为除常量。在此基础上，我们还可以尽可能消除函数调用。如下图所示：

![在这里插入图片描述][20191108191412883.png]  
核心代码如下：

void smooth1(int dim, pixel *src, pixel *dst) { 
    	//消除过多的函数调用，独立计算不同位置的像素点，将所有除法运算由除变量改为除常量
    	int i=1,j=0;
    	//处理左上角顶点
    	dst[0].red=(src[0].red+src[1].red+src[dim].red+src[dim+1].red)/4;
    	dst[0].green=(src[0].green+src[1].green+src[dim].green+src[dim+1].green)/4;
    	dst[0].blue=(src[0].blue+src[1].blue+src[dim].blue+src[dim+1].blue)/4;
    	//处理第一行其他非右上角顶点
    	for(j=1; j<dim-1; j++) { 
    		dst[j].red=(src[j-1].red+src[j].red+src[j+1].red+src[dim+j-1].red+src[dim+j].red+src[dim+j+1].red)/6;
    		dst[j].green=(src[j-1].green+src[j].green+src[j+1].green+src[dim+j-1].green+src[dim+j].green+src[dim+j+1].green)/6;
    		dst[j].blue=(src[j-1].blue+src[j].blue+src[j+1].blue+src[dim+j-1].blue+src[dim+j].blue+src[dim+j+1].blue)/6;
    	}
    	//处理右上角顶点
    	dst[j].red=(src[j].red+src[j-1].red+src[dim+j].red+src[dim+j-1].red)/4;
    	dst[j].green=(src[j].green+src[j-1].green+src[dim+j].green+src[dim+j-1].green)/4;
    	dst[j].blue=(src[j].blue+src[j-1].blue+src[dim+j].blue+src[dim+j-1].blue)/4;
    	//处理1至dim-2行
    	for(; i<dim-1; i++) { 
    		//处理每一行的第一个像素点
    		dst[i*dim].red=(src[(i-1)*dim].red+src[(i-1)*dim+1].red+src[i*dim].red+src[i*dim+1].red+src[(i+1)*dim].red+src[(i+1)*dim+1].red)/6;
    		dst[i*dim].green=(src[(i-1)*dim].green+src[(i-1)*dim+1].green+src[i*dim].green+src[i*dim+1].green+src[(i+1)*dim].green+src[(i+1)*dim+1].green)/6;
    		dst[i*dim].blue=(src[(i-1)*dim].blue+src[(i-1)*dim+1].blue+src[i*dim].blue+src[i*dim+1].blue+src[(i+1)*dim].blue+src[(i+1)*dim+1].blue)/6;
    		//处理每一行第二个至第dim-1个像素点
    		for(j=1; j<dim-1; j++) { 
    			dst[i*dim+j].red=(src[(i-1)*dim+j-1].red+src[(i-1)*dim+j].red+src[(i-1)*dim+j+1].red+src[i*dim+j-1].red+src[i*dim+j].red+src[i*dim+j+1].red+src[(i+1)*dim+j-1].red+src[(i+1)*dim+j].red+src[(i+1)*dim+j+1].red)/9;
    			dst[i*dim+j].green=(src[(i-1)*dim+j-1].green+src[(i-1)*dim+j].green+src[(i-1)*dim+j+1].green+src[i*dim+j-1].green+src[i*dim+j].green+src[i*dim+j+1].green+src[(i+1)*dim+j-1].green+src[(i+1)*dim+j].green+src[(i+1)*dim+j+1].green)/9;
    			dst[i*dim+j].blue=(src[(i-1)*dim+j-1].blue+src[(i-1)*dim+j].blue+src[(i-1)*dim+j+1].blue+src[i*dim+j-1].blue+src[i*dim+j].blue+src[i*dim+j+1].blue+src[(i+1)*dim+j-1].blue+src[(i+1)*dim+j].blue+src[(i+1)*dim+j+1].blue)/9;
    		}
    		//处理每一行最后一个像素点
    		dst[i*dim+j].red=(src[(i-1)*dim+j-1].red+src[(i-1)*dim+j].red+src[i*dim+j-1].red+src[i*dim+j].red+src[(i+1)*dim+j-1].red+src[(i+1)*dim+j].red)/6;
    		dst[i*dim+j].green=(src[(i-1)*dim+j-1].green+src[(i-1)*dim+j].green+src[i*dim+j-1].green+src[i*dim+j].green+src[(i+1)*dim+j-1].green+src[(i+1)*dim+j].green)/6;
    		dst[i*dim+j].blue=(src[(i-1)*dim+j-1].blue+src[(i-1)*dim+j].blue+src[i*dim+j-1].blue+src[i*dim+j].blue+src[(i+1)*dim+j-1].blue+src[(i+1)*dim+j].blue)/6;
    	}
    	//处理左下角像素点
    	dst[i*dim].red=(src[(i-1)*dim].red+src[(i-1)*dim+1].red+src[i*dim].red+src[i*dim+1].red)/4;
    	dst[i*dim].green=(src[(i-1)*dim].green+src[(i-1)*dim+1].green+src[i*dim].green+src[i*dim+1].green)/4;
    	dst[i*dim].blue=(src[(i-1)*dim].blue+src[(i-1)*dim+1].blue+src[i*dim].blue+src[i*dim+1].blue)/4;
    	//处理最后一行非左下角、非右下角的像素点
    	for(j=1; j<dim-1; j++) { 
    		dst[i*dim+j].red=(src[(i-1)*dim+j-1].red+src[(i-1)*dim+j].red+src[(i-1)*dim+j+1].red+src[i*dim+j-1].red+src[i*dim+j].red+src[i*dim+j+1].red)/6;
    		dst[i*dim+j].green=(src[(i-1)*dim+j-1].green+src[(i-1)*dim+j].green+src[(i-1)*dim+j+1].green+src[i*dim+j-1].green+src[i*dim+j].green+src[i*dim+j+1].green)/6;
    		dst[i*dim+j].blue=(src[(i-1)*dim+j-1].blue+src[(i-1)*dim+j].blue+src[(i-1)*dim+j+1].blue+src[i*dim+j-1].blue+src[i*dim+j].blue+src[i*dim+j+1].blue)/6;
    	}
    	//处理右下角像素点
    	dst[i*dim+j].red=(src[(i-1)*dim+j-1].red+src[(i-1)*dim+j].red+src[i*dim+j-1].red+src[i*dim+j].red)/4;
    	dst[i*dim+j].green=(src[(i-1)*dim+j-1].green+src[(i-1)*dim+j].green+src[i*dim+j-1].green+src[i*dim+j].green)/4;
    	dst[i*dim+j].blue=(src[(i-1)*dim+j-1].blue+src[(i-1)*dim+j].blue+src[i*dim+j-1].blue+src[i*dim+j].blue)/4;	
    }

#### 版本二：纵向的动态规划 ####

继续分析，可以发现上面的程序性能仍然存在问题。虽然在前一个版本中，我尽可能地消除了函数调用，将待平均像素点数目判断由max()、min()、计数器的方法改为代码直接指定的方法，但出现了程序运行过程中比较多的重复计算量。如下图所示，蓝色部分为重复计算区域：  
![在这里插入图片描述][2019110819153691.png]  
我基于动态规划的思想，将每一个像素点的计算转换为一个块(2x2或2x3或3x2或3x3)内的各个像素点取平均值，并将每一块纵向分开为2或3个纵向块，用动规数组记录每一列(2个或3个像素点)的R、G、B之和。相邻的两个纵向块之间存在递推关系，通式可以表达为：

> dp\[i\]\[j\]=dp\[i-1\]\[j\]-src\[(i-1)\*dim+j\]+src\[(i+2)\*dim+j\]

核心代码为：

void smooth2(int dim, pixel *src, pixel *dst) { 
    	//使用数组存储中间结果，动规
    	int i,j;
    	int r2[2][dim],g2[2][dim],b2[2][dim];//从上到下2个
    	int r3[dim][dim],g3[dim][dim],b3[dim][dim];//从上到下3个
    	for(j=0; j<dim; j++) { 
    		//第j列一开始的大小为2的子块
    		r2[0][j]=src[j].red;
    		g2[0][j]=src[j].green;
    		b2[0][j]=src[j].blue;
    		r2[0][j]+=src[dim+j].red;
    		g2[0][j]+=src[dim+j].green;
    		b2[0][j]+=src[dim+j].blue;
    		//第j列一开始的大小为3的子块
    		r3[0][j]=r2[0][j]+src[(dim<<1)+j].red;
    		g3[0][j]=g2[0][j]+src[(dim<<1)+j].green;
    		b3[0][j]=b2[0][j]+src[(dim<<1)+j].blue;
    		//递推得到其他子块
    		for(i=1; i<dim-2; i++) { 
    			r3[i][j]=r3[i-1][j]-src[(i-1)*dim+j].red+src[(i+2)*dim+j].red;
    			g3[i][j]=g3[i-1][j]-src[(i-1)*dim+j].green+src[(i+2)*dim+j].green;
    			b3[i][j]=b3[i-1][j]-src[(i-1)*dim+j].blue+src[(i+2)*dim+j].blue;
    		}
    		//最后一个长度为2的子块
    		r2[1][j]=r3[dim-3][j]-src[(dim-3)*dim+j].red;
    		g2[1][j]=g3[dim-3][j]-src[(dim-3)*dim+j].green;
    		b2[1][j]=b3[dim-3][j]-src[(dim-3)*dim+j].blue;
    	}
    	//处理左上角顶点
    	dst[0].red=(r2[0][0]+r2[0][1])/4;
    	dst[0].green=(g2[0][0]+g2[0][1])/4;
    	dst[0].blue=(b2[0][0]+b2[0][1])/4;
    	//处理第一行其他非右上角顶点
    	for(j=1; j<dim-1; j++) { 
    		dst[j].red=(r2[0][j-1]+r2[0][j]+r2[0][j+1])/6;
    		dst[j].green=(g2[0][j-1]+g2[0][j]+g2[0][j+1])/6;
    		dst[j].blue=(b2[0][j-1]+b2[0][j]+b2[0][j+1])/6;
    	}
    	//处理右上角顶点
    	dst[j].red=(r2[0][j-1]+r2[0][j])/4;
    	dst[j].green=(g2[0][j-1]+g2[0][j])/4;
    	dst[j].blue=(b2[0][j-1]+b2[0][j])/4;
    	//处理1至dim-2行
    	for(i=1; i<dim-1; i++) { 
    		//处理每一行的第一个像素点
    		dst[i*dim].red=(r3[i-1][0]+r3[i-1][1])/6;
    		dst[i*dim].green=(g3[i-1][0]+g3[i-1][1])/6;
    		dst[i*dim].blue=(b3[i-1][0]+b3[i-1][1])/6;
    		//处理每一行第二个至第dim-1个像素点
    		for(j=1; j<dim-1; j++) { 
    			dst[i*dim+j].red=(r3[i-1][j-1]+r3[i-1][j]+r3[i-1][j+1])/9;
    			dst[i*dim+j].green=(g3[i-1][j-1]+g3[i-1][j]+g3[i-1][j+1])/9;
    			dst[i*dim+j].blue=(b3[i-1][j-1]+b3[i-1][j]+b3[i-1][j+1])/9;
    		}
    		//处理每一行最后一个像素点
    		dst[i*dim+j].red=(r3[i-1][j-1]+r3[i-1][j])/6;
    		dst[i*dim+j].green=(g3[i-1][j-1]+g3[i-1][j])/6;
    		dst[i*dim+j].blue=(b3[i-1][j-1]+b3[i-1][j])/6;
    	}
    	//处理左下角像素点
    	dst[i*dim].red=(r2[1][0]+r2[1][1])/4;
    	dst[i*dim].green=(g2[1][0]+g2[1][1])/4;
    	dst[i*dim].blue=(b2[1][0]+b2[1][1])/4;
    	//处理最后一行非左下角、非右下角的像素点
    	for(j=1; j<dim-1; j++) { 
    		dst[i*dim+j].red=(r2[1][j-1]+r2[1][j]+r2[1][j+1])/6;
    		dst[i*dim+j].green=(g2[1][j-1]+g2[1][j]+g2[1][j+1])/6;
    		dst[i*dim+j].blue=(b2[1][j-1]+b2[1][j]+b2[1][j+1])/6;	
    	}
    	//处理右下角像素点
    	dst[i*dim+j].red=(r2[1][j-1]+r2[1][j])/4;
    	dst[i*dim+j].green=(g2[1][j-1]+g2[1][j])/4;
    	dst[i*dim+j].blue=(b2[1][j-1]+b2[1][j])/4;	
    }

这样处理虽然以“用空间换时间”的方式减少了总计算量，但不难看出由于递推关系为纵向，因此读运算的空间局部性较差，产生了大量的不命中。此外，二维数组的选择似乎也不够合理。因此，可以将递推关系改为横向，再次尝试。我同时想到了通过指针尽可能小范围移动的方法，继续尝试第三个版本。

#### 版本三：使用三个指针 ####

基于版本一的行优先读写顺序，考虑到对于任何像素点，待求平均的像素点所构成的块大小都不会超过三行，每行都不会超过三个。这启发我可以通过三个指针，每个指针控制行相邻的两个或三个像素点的读运算。核心代码为：

void smooth3(int dim, pixel *src, pixel *dst) { 
    	//使用指针，尽量少移动
        int i,j;
    	//每一个指针对应一行
        pixel *pixelA,*pixelB,*pixelC;
        int size = dim-1;
        //处理第一行第一个像素点
        pixelB = src;
        pixelC = pixelB + dim;
        dst->red = (pixelB->red + (pixelB+1)->red + pixelC->red + (pixelC+1)->red)>>2;
        dst->green = (pixelB->green + (pixelB+1)->green + pixelC->green + (pixelC+1)->green)>>2;
        dst->blue = (pixelB->blue + (pixelB+1)->blue + pixelC->blue + (pixelC+1)->blue)>>2;
        pixelB++;
        pixelC++;
        dst++;
        //处理第一行中间的dim-2个像素点
        for(i = 1; i < size; i++)
        { 
            dst->red = (pixelB->red + (pixelB-1)->red + (pixelB+1)->red + pixelC->red + (pixelC-1)->red + (pixelC+1)->red)/6;
            dst->green = (pixelB->green + (pixelB-1)->green + (pixelB+1)->green + pixelC->green + (pixelC-1)->green + (pixelC+1)->green)/6;
            dst->blue = (pixelB->blue + (pixelB-1)->blue + (pixelB+1)->blue + pixelC->blue + (pixelC-1)->blue + (pixelC+1)->blue)/6;
            pixelB++;
            pixelC++;
            dst++;
        }
        //处理第一行最后一个像素点
        dst->red = (pixelC->red + (pixelC-1)->red + pixelB->red + (pixelB-1)->red)>>2;
        dst->green = (pixelC->green + (pixelC-1)->green + pixelB->green + (pixelB-1)->green)>>2;
        dst->blue = (pixelC->blue + (pixelC-1)->blue + pixelB->blue + (pixelB-1)->blue)>>2;
        dst++;
    	//开始处理中间的dim-2行
        pixelA = src;
        pixelB = pixelA + dim;
        pixelC = pixelB + dim;
        for(i = 1; i < size; i++)
        { 
            //对于每一行的第一个像素点
            dst->red = (pixelA->red + (pixelA+1)->red + pixelB->red + (pixelB+1)->red + pixelC->red + (pixelC+1)->red)/6;
            dst->green = (pixelA->green + (pixelA+1)->green + pixelB->green + (pixelB+1)->green + pixelC->green + (pixelC+1)->green)/6;
            dst->blue = (pixelA->blue + (pixelA+1)->blue + pixelB->blue + (pixelB+1)->blue + pixelC->blue+ (pixelC+1)->blue)/6;
            dst++;
            pixelA++;
            pixelB++;
            pixelC++;
            //对于每一行中间的dim-2个像素点
            for(j = 1; j < dim-1; j++)
            { 
                dst->red = (pixelA->red + (pixelA-1)->red + (pixelA+1)->red + pixelB->red + (pixelB-1)->red + (pixelB+1)->red + pixelC->red + (pixelC-1)->red + (pixelC+1)->red)/9;
                dst->green = (pixelA->green + (pixelA-1)->green + (pixelA+1)->green + pixelB->green + (pixelB-1)->green + (pixelB+1)->green + pixelC->green + (pixelC-1)->green + (pixelC+1)->green)/9;
                dst->blue = (pixelA->blue + (pixelA-1)->blue + (pixelA+1)->blue + pixelB->blue + (pixelB-1)->blue + (pixelB+1)->blue + pixelC->blue + (pixelC-1)->blue + (pixelC+1)->blue)/9;
                pixelA++;
                pixelB++;
                pixelC++;
                dst++;
            }
            //对于每一行最后一个像素点
            dst->red = (pixelA->red + (pixelA-1)->red + pixelB->red + (pixelB-1)->red + pixelC->red + (pixelC-1)->red)/6;
            dst->green = (pixelA->green + (pixelA-1)->green + pixelB->green + (pixelB-1)->green + pixelC->green + (pixelC-1)->green)/6;
            dst->blue = (pixelA->blue + (pixelA-1)->blue + pixelB->blue + (pixelB-1)->blue + pixelC->blue+ (pixelC-1)->blue)/6;
            pixelA++;
            pixelB++;
            pixelC++;
            dst++;
        }
        //处理最后一行第一个像素点
        dst->red = (pixelA->red + (pixelA+1)->red + pixelB->red + (pixelB+1)->red)>>2;
        dst->green = (pixelA->green + (pixelA+1)->green + pixelB->green + (pixelB+1)->green)>>2;
        dst->blue = (pixelA->blue + (pixelA+1)->blue + pixelB->blue + (pixelB+1)->blue)>>2;
        dst++;
        pixelA++;
        pixelB++;
        //处理最后一行中间dim-2个像素点
        for(i = 1; i < size; i++)
        { 
            dst->red = (pixelA->red + (pixelA-1)->red + (pixelA+1)->red + pixelB->red + (pixelB-1)->red + (pixelB+1)->red)/6;
            dst->green = (pixelA->green + (pixelA-1)->green + (pixelA+1)->green + pixelB->green + (pixelB-1)->green + (pixelB+1)->green)/6;
            dst->blue = (pixelA->blue + (pixelA-1)->blue + (pixelA+1)->blue + pixelB->blue + (pixelB-1)->blue + (pixelB+1)->blue)/6;
            pixelA++;
            pixelB++;
            dst++;
        }
        //处理最后一行最后一个像素点
        dst->red = (pixelA->red + (pixelA-1)->red + pixelB->red + (pixelB-1)->red)>>2;
        dst->green = (pixelA->green + (pixelA-1)->green + pixelB->green + (pixelB-1)->green)>>2;
        dst->blue = (pixelA->blue + (pixelA-1)->blue + pixelB->blue + (pixelB-1)->blue)>>2;
    }

#### 版本四：结合上述三个版本 ####

版本一与版本二给了我启发：版本一将处理方式不同的位置分别讨论，但大量的重复计算限制了性能的进一步提升；版本二采用动态规划的思想，但不合理的子问题(纵向三个像素点的R、G、B之和)与二维数组的选择不够合理，导致性能提升并不理想；版本三使用指针的思想同样值得推广。

结合版本一、版本二与版本三的优缺点，便有了版本四。版本四每次使用了六个临时变量存储结果，1~6分别为(i,j)、(i,j+1)、(i,j+2)、(i+1,j)、(i+1,j+1)、(i+1,j+2)所对应的向下三个像素点的R或G或B之和。核心代码如下：

void smooth(int dim, pixel *src, pixel *dst) { 
    	int i,j,dest;
    	//首先处理四个顶点
    	//左上角顶点
    	dst[0].red = (src[0].red+src[1].red+src[dim].red+src[dim+1].red)>>2;
    	dst[0].blue = (src[0].blue+src[1].blue+src[dim].blue+src[dim+1].blue)>>2;
    	dst[0].green = (src[0].green+src[1].green+src[dim].green+src[dim+1].green)>>2;
    	//右上角顶点
    	i=dim-1;
    	j=dim*2-1;
    	dst[i].red = (src[i].red+src[i-1].red+src[j].red+src[j-1].red)>>2;
    	dst[i].blue = (src[i].blue+src[i-1].blue+src[j].blue+src[j-1].blue)>>2;
    	dst[i].green = (src[i].green+src[i-1].green+src[j].green+src[j-1].green)>>2;
    	//左上角顶点
    	i=dim*(dim-1);
    	j=dim*(dim-2);
    	dst[i].red = (src[i].red+src[i+1].red+src[j].red+src[j+1].red)>>2;
    	dst[i].blue = (src[i].blue+src[i+1].blue+src[j].blue+src[j+1].blue)>>2;
    	dst[i].green = (src[i].green+src[i+1].green+src[j].green+src[j+1].green)>>2;
    	//右上角顶点
    	i=dim*dim-1;
    	j=dim*(dim-1)-1;
    	dst[i].red = (src[i].red+src[i-1].red+src[j].red+src[j-1].red)>>2;
    	dst[i].blue = (src[i].blue+src[i-1].blue+src[j].blue+src[j-1].blue)>>2;
    	dst[i].green = (src[i].green+src[i-1].green+src[j].green+src[j-1].green)>>2;
    	//接下来处理四条边
    	//上边
    	dest = dim-1;
    	i=dim+1;
    	for (j = 1; j < dest; j++) { 
    		dst[j].red = (src[j-1].red+src[j].red+src[j+1].red+src[i-1].red+src[i].red
    		              +src[i+1].red)/6;
    		dst[j].green = (src[j-1].green+src[j].green+src[j+1].green+src[i-1].green+src[i].green
    		                +src[i+1].green)/6;
    		dst[j].blue = (src[j-1].blue+src[j].blue+src[j+1].blue+src[i-1].blue+src[i].blue
    		               +src[i+1].blue)/6;
    		i++;
    	}
    	//下边
    	dest = dim*dim-1;
    	for (j = dim*(dim-1)+1; j < dest; j++) { 
    		i=j-dim;
    		dst[j].red = (src[j-1].red+src[j].red+src[j+1].red+src[i-1].red+src[i].red
    		              +src[i+1].red)/6;
    		dst[j].green = (src[j-1].green+src[j].green+src[j+1].green+src[i-1].green+src[i].green
    		                +src[i+1].green)/6;
    		dst[j].blue = (src[j-1].blue+src[j].blue+src[j+1].blue+src[i-1].blue+src[i].blue
    		               +src[i+1].blue)/6;
    	}
    	//左边
    	dest = dim*dim-dim;
    	for (j = dim; j < dest; j+=dim) { 
    		dst[j].red = (src[j].red+src[j+1].red+src[j-dim].red+src[j-dim+1].red+src[j+dim].red+src[j+1+dim].red)/6;
    		dst[j].green = (src[j].green+src[j+1].green+src[j-dim].green+src[j-dim+1].green+src[j+dim].green+src[j+1+dim].green)/6;
    		dst[j].blue = (src[j].blue+src[j+1].blue+src[j-dim].blue+src[j-dim+1].blue+src[j+dim].blue+src[j+1+dim].blue)/6;
    	}
    	//右边
    	dest=dim*dim-1;
    	for (j = dim+dim-1; j < dest; j+=dim) { 
    		dst[j].red = (src[j].red+src[j-1].red+src[j-dim].red+src[j-dim-1].red+src[j+dim].red+src[j-1+dim].red)/6;
    		dst[j].green = (src[j].green+src[j-1].green+src[j-dim].green+src[j-1+dim].green+src[j+dim].green+src[j-dim-1].green)/6;
    		dst[j].blue = (src[j].blue+src[j-1].blue+src[j-dim].blue+src[j-dim-1].blue+src[j+dim].blue+src[j-1+dim].blue)/6;
    	}
    
    	//处理中间的(dim-1)*(dim-1)个像素点
    	pixel *pixelA = &src[0]; 
    	pixel *pixelB = &src[dim];
    	pixel *pixelC = &src[dim+dim];
    	pixel *pixelD = &src[dim+dim+dim];
    
    	//6个临时变量，存储3*2范围内的值
    	int sum0_red, sum0_green, sum0_blue;
    	int sum1_red, sum1_green, sum1_blue;
    	int sum2_red, sum2_green, sum2_blue;
    	int sum3_red, sum3_green, sum3_blue;
    	int sum4_red, sum4_green, sum4_blue;
    	int sum5_red, sum5_green, sum5_blue; 
    
    	//index_为index的下面一个
    	int index = dim+1;
    	int index_ = index+dim;
    	//对于1~dim-2行
    	//循环展开:2，每次两行，index为本行，index_为下一行
    	for (i = 1; i < dim - 2; i += 2) { 
    		sum0_red = pixelB->red;
    		sum0_blue = pixelB->blue;
    		sum0_green = pixelB->green;
    		sum0_red += pixelC->red;
    		sum0_blue += pixelC->blue;
    		sum0_green += pixelC->green;
    		sum3_red = sum0_red+pixelD->red;
    		sum3_green = sum0_green+pixelD->green;
    		sum3_blue = sum0_blue+pixelD->blue;
    		sum0_red += pixelA->red;
    		sum0_blue += pixelA->blue;
    		sum0_green += pixelA->green;
    		//右移，此时sum0=A+B+C,sum3=B+C+D;
    		pixelA++;
    		pixelB++;
    		pixelC++;
    		pixelD++;
    
    		sum1_red = pixelB->red;
    		sum1_blue = pixelB->blue;
    		sum1_green = pixelB->green;
    		sum1_red += pixelC->red;
    		sum1_blue += pixelC->blue;
    		sum1_green += pixelC->green;
    		sum4_red = sum1_red+pixelD->red;
    		sum4_green = sum1_green+pixelD->green;
    		sum4_blue = sum1_blue+pixelD->blue;
    		sum1_red += pixelA->red;
    		sum1_blue += pixelA->blue;
    		sum1_green += pixelA->green;
    		//此时sum1=A+B+C,sum4=B+C+D;
    		pixelA++;
    		pixelB++;
    		pixelC++;
    		pixelD++;
    
    		sum2_red = pixelB->red;
    		sum2_blue = pixelB->blue;
    		sum2_green = pixelB->green;
    		sum2_red += pixelC->red;
    		sum2_blue += pixelC->blue;
    		sum2_green += pixelC->green;
    		sum5_red = sum2_red+pixelD->red;
    		sum5_green = sum2_green+pixelD->green;
    		sum5_blue = sum2_blue+pixelD->blue;
    		sum2_red += pixelA->red;
    		sum2_blue += pixelA->blue;
    		sum2_green += pixelA->green;
    		//此时sum2=A+B+C,sum5=B+C+D;
    		pixelA++;
    		pixelB++;
    		pixelC++;
    		pixelD++;
    
    		dst[index].red = ((sum0_red+sum1_red+sum2_red)/9);
    		dst[index].blue = ((sum0_blue+sum1_blue+sum2_blue)/9);
    		dst[index].green = ((sum0_green+sum1_green+sum2_green)/9);
    		index++;
    
    		dst[index_].red = ((sum3_red+sum4_red+sum5_red)/9);
    		dst[index_].blue = ((sum3_blue+sum4_blue+sum5_blue)/9);
    		dst[index_].green = ((sum3_green+sum4_green+sum5_green)/9);
    		index_++;
    		//右推
    		sum0_red = sum1_red;
    		sum1_red = sum2_red;
    		sum0_green = sum1_green;
    		sum1_green = sum2_green;
    		sum0_blue = sum1_blue;
    		sum1_blue = sum2_blue;
    		sum3_red = sum4_red;
    		sum4_red = sum5_red;
    		sum3_green = sum4_green;
    		sum4_green = sum5_green;
    		sum3_blue = sum4_blue;
    		sum4_blue = sum5_blue;
    		
    		//设置j<dim-4以防止越界，但有可能没处理完
    		//循环展开:4，每一次：更新值+指针右移+赋值+临时变量右推
    		for (j = 2; j < dim-4; j += 4) { 
    			//第一次
    			sum2_red = pixelB->red;
    			sum2_blue = pixelB->blue;
    			sum2_green = pixelB->green;
    			sum2_red += pixelC->red;
    			sum2_blue += pixelC->blue;
    			sum2_green += pixelC->green;
    			sum5_red = sum2_red+pixelD->red;
    			sum5_green = sum2_green+pixelD->green;
    			sum5_blue = sum2_blue+pixelD->blue;
    			sum2_red += pixelA->red;
    			sum2_blue += pixelA->blue;
    			sum2_green += pixelA->green;
    			pixelA++;
    			pixelB++;
    			pixelC++;
    			pixelD++;
    
    			dst[index].red = ((sum0_red+sum1_red+sum2_red)/9);
    			dst[index].blue = ((sum0_blue+sum1_blue+sum2_blue)/9);
    			dst[index].green = ((sum0_green+sum1_green+sum2_green)/9);
    			index++;
    
    			dst[index_].red = ((sum3_red+sum4_red+sum5_red)/9);
    			dst[index_].blue = ((sum3_blue+sum4_blue+sum5_blue)/9);
    			dst[index_].green = ((sum3_green+sum4_green+sum5_green)/9);
    			index_++;
    
    			sum0_red = sum1_red;
    			sum1_red = sum2_red;
    			sum0_green = sum1_green;
    			sum1_green = sum2_green;
    			sum0_blue = sum1_blue;
    			sum1_blue = sum2_blue;
    			sum3_red = sum4_red;
    			sum4_red = sum5_red;
    			sum3_green = sum4_green;
    			sum4_green = sum5_green;
    			sum3_blue = sum4_blue;
    			sum4_blue = sum5_blue;
    
    			//第二次
    			sum2_red = pixelB->red;
    			sum2_blue = pixelB->blue;
    			sum2_green = pixelB->green;
    			sum2_red += pixelC->red;
    			sum2_blue += pixelC->blue;
    			sum2_green += pixelC->green;
    			sum5_red = sum2_red+pixelD->red;
    			sum5_green = sum2_green+pixelD->green;
    			sum5_blue = sum2_blue+pixelD->blue;
    			sum2_red += pixelA->red;
    			sum2_blue += pixelA->blue;
    			sum2_green += pixelA->green;
    			pixelA++;
    			pixelB++;
    			pixelC++;
    			pixelD++;
    
    			dst[index].red = ((sum0_red+sum1_red+sum2_red)/9);
    			dst[index].blue = ((sum0_blue+sum1_blue+sum2_blue)/9);
    			dst[index].green = ((sum0_green+sum1_green+sum2_green)/9);
    			index++;
    
    			dst[index_].red = ((sum3_red+sum4_red+sum5_red)/9);
    			dst[index_].blue = ((sum3_blue+sum4_blue+sum5_blue)/9);
    			dst[index_].green = ((sum3_green+sum4_green+sum5_green)/9);
    			index_++;
    
    			sum0_red = sum1_red;
    			sum1_red = sum2_red;
    			sum0_green = sum1_green;
    			sum1_green = sum2_green;
    			sum0_blue = sum1_blue;
    			sum1_blue = sum2_blue;
    			sum3_red = sum4_red;
    			sum4_red = sum5_red;
    			sum3_green = sum4_green;
    			sum4_green = sum5_green;
    			sum3_blue = sum4_blue;
    			sum4_blue = sum5_blue;
    
    			//第三次
    			sum2_red = pixelB->red;
    			sum2_blue = pixelB->blue;
    			sum2_green = pixelB->green;
    			sum2_red += pixelC->red;
    			sum2_blue += pixelC->blue;
    			sum2_green += pixelC->green;
    			sum5_red = sum2_red+pixelD->red;
    			sum5_green = sum2_green+pixelD->green;
    			sum5_blue = sum2_blue+pixelD->blue;
    			sum2_red += pixelA->red;
    			sum2_blue += pixelA->blue;
    			sum2_green += pixelA->green;
    			pixelA++;
    			pixelB++;
    			pixelC++;
    			pixelD++;
    
    			dst[index].red = ((sum0_red+sum1_red+sum2_red)/9);
    			dst[index].blue = ((sum0_blue+sum1_blue+sum2_blue)/9);
    			dst[index].green = ((sum0_green+sum1_green+sum2_green)/9);
    			index++;
    
    			dst[index_].red = ((sum3_red+sum4_red+sum5_red)/9);
    			dst[index_].blue = ((sum3_blue+sum4_blue+sum5_blue)/9);
    			dst[index_].green = ((sum3_green+sum4_green+sum5_green)/9);
    			index_++;
    
    			sum0_red = sum1_red;
    			sum1_red = sum2_red;
    			sum0_green = sum1_green;
    			sum1_green = sum2_green;
    			sum0_blue = sum1_blue;
    			sum1_blue = sum2_blue;
    			sum3_red = sum4_red;
    			sum4_red = sum5_red;
    			sum3_green = sum4_green;
    			sum4_green = sum5_green;
    			sum3_blue = sum4_blue;
    			sum4_blue = sum5_blue;
    
    			//第四次
    			sum2_red = pixelB->red;
    			sum2_blue = pixelB->blue;
    			sum2_green = pixelB->green;
    			sum2_red += pixelC->red;
    			sum2_blue += pixelC->blue;
    			sum2_green += pixelC->green;
    			sum5_red = sum2_red+pixelD->red;
    			sum5_green = sum2_green+pixelD->green;
    			sum5_blue = sum2_blue+pixelD->blue;
    			sum2_red += pixelA->red;
    			sum2_blue += pixelA->blue;
    			sum2_green += pixelA->green;
    			pixelA++;
    			pixelB++;
    			pixelC++;
    			pixelD++;
    
    			dst[index].red = ((sum0_red+sum1_red+sum2_red)/9);
    			dst[index].blue = ((sum0_blue+sum1_blue+sum2_blue)/9);
    			dst[index].green = ((sum0_green+sum1_green+sum2_green)/9);
    			index++;
    
    			dst[index_].red = ((sum3_red+sum4_red+sum5_red)/9);
    			dst[index_].blue = ((sum3_blue+sum4_blue+sum5_blue)/9);
    			dst[index_].green = ((sum3_green+sum4_green+sum5_green)/9);
    			index_++;
    
    			sum0_red = sum1_red;
    			sum1_red = sum2_red;
    			sum0_green = sum1_green;
    			sum1_green = sum2_green;
    			sum0_blue = sum1_blue;
    			sum1_blue = sum2_blue;
    			sum3_red = sum4_red;
    			sum4_red = sum5_red;
    			sum3_green = sum4_green;
    			sum4_green = sum5_green;
    			sum3_blue = sum4_blue;
    			sum4_blue = sum5_blue;
    
    		}
    		//处理这一行没处理完的像素点
    		for (; j < dim-1; j++) { 
    			sum2_red = pixelB->red;
    			sum2_blue = pixelB->blue;
    			sum2_green = pixelB->green;
    			sum2_red += pixelC->red;
    			sum2_blue += pixelC->blue;
    			sum2_green += pixelC->green;
    			sum5_red = sum2_red+pixelD->red;
    			sum5_green = sum2_green+pixelD->green;
    			sum5_blue = sum2_blue+pixelD->blue;
    			sum2_red += pixelA->red;
    			sum2_blue += pixelA->blue;
    			sum2_green += pixelA->green;
    			pixelA++;
    			pixelB++;
    			pixelC++;
    			pixelD++;
    
    			dst[index].red = ((sum0_red+sum1_red+sum2_red)/9);
    			dst[index].blue = ((sum0_blue+sum1_blue+sum2_blue)/9);
    			dst[index].green = ((sum0_green+sum1_green+sum2_green)/9);
    			index++;
    
    			dst[index_].red = ((sum3_red+sum4_red+sum5_red)/9);
    			dst[index_].blue = ((sum3_blue+sum4_blue+sum5_blue)/9);
    			dst[index_].green = ((sum3_green+sum4_green+sum5_green)/9);
    			index_++;
    
    			sum0_red = sum1_red;
    			sum1_red = sum2_red;
    			sum0_green = sum1_green;
    			sum1_green = sum2_green;
    			sum0_blue = sum1_blue;
    			sum1_blue = sum2_blue;
    			sum3_red = sum4_red;
    			sum4_red = sum5_red;
    			sum3_green = sum4_green;
    			sum4_green = sum5_green;
    			sum3_blue = sum4_blue;
    			sum4_blue = sum5_blue;
    		}
    
    		//改变指针，指向下一行
    		pixelA += dim;
    		pixelB += dim;
    		pixelC += dim;
    		pixelD += dim;
    		index += dim+2;
    		index_ += dim+2;
    	}
    }

## 五、遇到的问题及解决方法 ##

1、 未进入perfLab文件夹导致无法make  
![在这里插入图片描述][20191108192221129.png]  
解决方法：导致该问题的原因是没有在指定的文件夹下执行make，解决方法为cd进入perfLab文件夹，再执行make。

2、 代码出现细节上的错误  
在写版本二时未仔细检查，评分时出现：  
![在这里插入图片描述][2019110819224865.png]  
考虑到版本二中使用了动态规划数组，结合报错信息，推测大概率是数组访问越界。经检查，出错原因为r2、g2、b2定义为int\[2\]\[dim\]，数组第一行对应dst第一行，数组第二行对应dst最后一行，在使用时却视为了int\[dim\]\[dim\]，直接使用了r2\[i\]\[j\]，导致出现段错误。这提醒了我，对于一些符号的定义一定要明确，避免出现前后含义不一致的情况。

写在最后：  
**如果觉得这篇博客帮到了你，请给博主点一个大大的赞！**

[20191108185645990.png]: https://img-blog.csdnimg.cn/20191108185645990.png
[20191108185704381.png]: https://img-blog.csdnimg.cn/20191108185704381.png
[2019110423484818.png]: https://img-blog.csdnimg.cn/2019110423484818.png
[20191104235005672.png]: https://img-blog.csdnimg.cn/20191104235005672.png
[20191105003124534.png]: https://img-blog.csdnimg.cn/20191105003124534.png
[20191105003059869.png]: https://img-blog.csdnimg.cn/20191105003059869.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191108190205594.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw,size_16,color_FFFFFF,t_70
[20191108191348348.png]: https://img-blog.csdnimg.cn/20191108191348348.png
[20191108191412883.png]: https://img-blog.csdnimg.cn/20191108191412883.png
[2019110819153691.png]: https://img-blog.csdnimg.cn/2019110819153691.png
[20191108192221129.png]: https://img-blog.csdnimg.cn/20191108192221129.png
[2019110819224865.png]: https://img-blog.csdnimg.cn/2019110819224865.png