本次试验是CSAPP的第5个试验，这次试验次要是让咱们相熟如何优化程序，如何写出更具备效率的代码。通过这次试验，咱们能够更好的了解计算机的工作原理，在当前编写代码时，具备能联合软硬件思考的能力。
@[toc]
试验简介
本次试验次要解决优化内存密集型代码。图像处理提供了许多能够从优化中受害的性能示例。在本试验中，咱们将思考两种图像处理操作：旋转，可将图像逆时针旋转90o，平滑，能够“平滑”或“含糊”图片。
在本试验中，咱们将思考将图像示意为二维矩阵M，其中${M_{i,j}}$示意M的第（i，j）个像素的值，像素值是红色，绿色和蓝色（RGB）值的三倍。咱们只会思考方形图像。令N示意图像的行（或列）数。行和列以C款式编号，从0到N − 1。
给定这种示意模式，旋转操作能够非常简单地实现为以下两个矩阵运算：
转置：对于每对（i，j），${M_{i,j}}$和${M_{j,i}}$是调换的
替换行：第i行与第N-1 − i行替换。
具体如下图所示
<img src="https://gitee.com/dongxingbo/Picture/raw/master//Blog/2020/%E5%8D%81%E4%BA%8C%E6%9C%88//PerformanceLab_%E5%9B%BE%E7%89%87%E6%97%8B%E8%BD%AC90%E7%A4%BA%E6%84%8F%E5%9B%BE.png" alt="image-20201203203611824" style="zoom:80%;" />
通过用四周所有像素的平均值替换每个像素值（在以该像素为核心的最大3×3窗口）中替换每个像素值来实现平滑操作。如下图所示。像素的值$M2[1][1]$ 和$M2[N - 1][N - 1]$如下所示：
$M2[1][1] = \frac{{\sum\nolimits_{i = 0}^2 {\sum\nolimits_{j = 0}^2 {M1[i][j]} } }}{9}$
$M2[N - 1][N - 1] = \frac{{\sum\nolimits_{i = N - 2}^{N - 1} {\sum\nolimits_{j = N - 2}^{N - 1} {M1[i][j]} } }}{4}$
<img src="https://gitee.com/dongxingbo/Picture/raw/master//Blog/2020/%E5%8D%81%E4%BA%8C%E6%9C%88//PerformanceLab_%E5%B9%B3%E6%BB%91%E5%9B%BE%E5%83%8F%E5%9B%BE%E7%A4%BA.png" alt="image-20201203204903889" style="zoom:80%;" />
本次试验中，咱们须要批改惟一文件是kernels.c。driver.c程序是一个驱动程序，可让对咱们批改的程序进行评分。应用命令make driver生成驱动程序代码并应用./driver命令运行它。
数据结构体
图像的外围数据是用构造体示意的。像素是一个构造，如下所示：
typedef struct { unsigned short red; /* R value */ unsigned short green; /* G value */ unsigned short blue; /* B value */} pixel;能够看出，RGB值具备16位示意模式（“ 16位色彩”）。图像I示意为一维像素阵列，其中第（i，j）个像素为I [RIDX（i，j，n）]。这里n是图像矩阵的维数， RIDX是定义如下的宏：
#define RIDX(i,j,n) ((i)*(n)+(j))无关此代码，请参见文件defs.h。
旋转Rotate
以下C函数计算将源图像src旋转90°的后果，并将后果存储在指标图像dst中。dim是图像的尺寸。
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;}下面的代码扫描源图像矩阵的行，而后复制到指标图像矩阵的列中。咱们的工作是应用代码移动，循环展开和阻塞等技术重写此代码，以使其尽可能快地运行。(无关此代码，请参见文件kernels.c。)
平滑Smooth
平滑性能将源图像src作为输出，并在指标图像dst中返回平滑后果。这是实现的一部分：
void naive_smooth(int dim, pixel *src, pixel *dst) { int i, j; for(i=0; i < dim; i++) for(j=0; j < dim; j++) dst[RIDX(i,j,dim)] = avg(dim, i, j, src); /* Smooth the (i,j)th pixel */ return;}函数avg返回第（i，j）个像素四周所有像素的平均值。咱们的工作是优化平滑（和avg）以尽可能快地运行。 （留神：函数avg是一个部分函数，能够齐全解脱它而以其余形式实现平滑)。(这段代码（以及avg的实现）位于kernels.c文件中。)
评估指标
咱们的次要性能指标是CPE。如果某个函数须要C个周期来运行大小为N×N的图像，则CPE值为$C/{N^2}$。
版本治理
咱们能够编写旋转和平滑例程的许多版本。为了帮忙您比拟编写的所有不同版本的性能，咱们提供了一种“注册”性能的形式。
例如，咱们提供给您的文件kernels.c蕴含以下性能：
void register_rotate_functions() { add_rotate_function(&rotate, rotate_descr);}此函数蕴含一个或多个调用以增加旋转函数。在下面的示例中，增加旋转函数将函数旋转与字符串旋转阐明一起注册，该字符串是函数性能的ASCII形容。请参阅文件kernels.c以理解如何创立字符串形容。该字符串的长度最多为256个字符。
驱动
将编写的源代码将与咱们提供给驱动程序二进制文件的指标代码链接。要创立此二进制文件，您将须要执行以下命令
unix> make driver每次更改kernels.c中的代码时，都须要从新制作驱动程序。要测试您的实现，而后能够运行以下命令：
unix> ./driver该驱动程序能够在四种不同的模式下运行：
默认模式，在其中运行施行的所有版本。
Autograder模式，其中仅运行rotation（）和smooth（）函数。这是当咱们应用驱动程序对您的切纸进行评分时将运行的模式。
文件模式，其中仅运行输出文件中提到的版本。
转储模式，其中每个版本的单行形容转储到文本文件中。而后，您能够编辑该文本文件，以仅应用文件模式保留要测试的版本。您能够指定是在转储文件之后退出还是要运行您的实现。
如果不带任何参数运行，驱动程序将运行所有版本（默认模式）。其余模式和选项能够通过驱动程序的命令行参数来指定，如下所示：
-g：仅运行rotate（）和smooth（）函数（主动分级模式）。
-f <funcfile> :仅执行在<funcfile>中指定的那些版本（文件模式）。
-d <dumpfile> :将所有版本的名称转储到名为<dumpfile>的转储文件中，将一行转储到版本（转储模式）。
-q :将版本名称转储到转储文件后退出。与-d一起应用。例如，要在打印转储文件后立刻退出，请键入./driver -qd dumpfile。
-h：打印命令行用法。
优化程序的办法
emsp; 回顾下罕用的优化程序的办法，总结如下：
(1)高级设计
为遇到的问题抉择适当的算法和数据结构。要特地警惕，防止应用那些会渐进地产生蹩脚性能的算法或编码技术。
(2)根本编码准则
防止限度优化的因素，这样编译器就能产生高效的代码。
打消间断的函数调用。在可能时，将计算移到循环外。思考有选择地斗争程序的模块性以取得更大的效率。
打消不必要的内存援用。引入长期变量来保留两头后果。只有在最初的值计算出来时，才将后果寄存到数组或全局变量中。
(3)低级优化
结构化代码以利用硬件性能。
开展循环，升高开销，并且使得进一步的优化成为可能。
通过应用例如多个累积变量和从新联合等技术，找到办法进步指令级并行。
用功能性的格调重写条件操作，使得编译采纳条件数据传送。
(4)使用性能剖析工具
当解决大型程序时，将注意力集中在最耗时的局部变得很重要。代码分析程序和相干的工具能帮忙咱们系统地评估和改良程序性能。咱们形容了 GPROF，一个规范的Unix分析工具。还有更加简单欠缺的分析程序可用，例如 Intel的VTUNE程序开发零碎，还有 Linux零碎基本上都有的 VALGRIND。这些工具能够在过程级合成执行工夫，预计程序每个基本块（ basic block）的性能。（基本块是外部没有管制转移的指令序列，因而基本块总是整个被执行的。)
Optimizing Rotate
在这一部分中，咱们将优化旋转以实现尽可能低的CPE。您应该编译驱动程序，而后应用适当的参数运行它以测试您的实现。例如，运行提供的原始版本（用于旋转）的驱动程序将生成如下所示的输入：
函数源码如下：
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;}其中，defs.h中RIDX定义为：#define RIDX(i,j,n) ((i)*(n)+(j))上面详细分析下程序。
i = 0 j = 0 dest[20] = src[0] i = 1 j = 0 dest[21] = src[5]i = 0 j = 1 dest[15] = src[1] i = 1 j = 1 dest[16] = src[6]i = 0 j = 2 dest[10] = src[2] i = 1 j = 2 dest[11] = src[7]i = 0 j = 3 dest[5] = src[3] i = 1 j = 3 dest[6] = src[8]i = 0 j = 4 dest[0] = src[4] i = 1 j = 4 dest[1] = src[9]具体如下图所示：
这段代码的作用就是将dim * dim大小的方块中所有的像素进行行列调位、导致整幅图画进行了90度旋转。察看源代码咱们发现，程序进行了嵌套循环，随着dim的减少，循环的复杂度越来越大，而且每循环一次，dim-1-j就要计算一次，因而，咱们思考进行分块优化。
优化版本一：分块 8 * 8
对于循环分块，这里的分块指的是一个利用级的数据组块，而不是高速缓存中的块，这样构造程序，能将一个片加载到L1高速缓存中去，并在这个片中进行所须要的所有读和写，而后丢掉这个片，加载下一个片，以此类推。
/*分块：8 * 8*/char rotate_descr[] = "rotate1: Current working version";void rotate(int dim, pixel *src, pixel *dst) { int i,j,i1,j1; for(i=0; i < dim; i+=8) for(j=0; j < dim; j+=8) for(i1=i; i1 < i+8; i1++) for(j1=j; j1 < j+8; j1++) dst[RIDX(dim-1-j1,i1,dim)] = src[RIDX(i1,j1,dim)];}优化后的版本测试如下所示：
右上图能够看到，得分有了显著的晋升，Dim规模较小时，晋升并不显著，在Dim为1024*1024时，由原来的17.1升高到了6.0.阐明咱们的办法还是无效的，然而最初的总得得分只有9.3分，成果不是很好。
优化版本二：分块 32 * 32
char rotate_descr[] = "rotate2: Current working version";void rotate(int dim, pixel *src, pixel *dst) { int i,j,i1,j1; for(i=0; i < dim; i+=32) for(j=0; j < dim; j+=32) for(i1=i; i1 < i+32; i1++) for(j1=j; j1 < j+32; j1++) dst[RIDX(dim-1-j1,i1,dim)] = src[RIDX(i1,j1,dim)];}本次持续采纳的是分块策略，分为了32块，然而由下图的得分能够看到，性能根本有晋升，所以，须要换个思路了。
优化版本三：循环展开，32路并行
在版本二的根底上，咱们进行循环展开，32路并行，并应用指针代替RIDX进行数组拜访，这里就义了程序的尺寸来换取速度优化。
char rotate_descr[] = "rotate3: Current working version";void rotate(int dim, pixel *src, pixel *dst) { int i,j; int dst_base = (dim-1)*dim; dst +=dst_base; for(i = 0;i < dim;i += 32){ for(j = 0;j < dim;j++){ *dst = *src; src +=dim; dst++; //31组 *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src +=dim; dst++; *dst = *src; src++; src -= (dim<<5)-dim; //src -=31*dim; dst -=31+dim; } dst +=dst_base + dim; dst +=32; src +=(dim<<5)-dim; //src +=31*dim; }}咱们在版本二的根底上，将原来的程序的内循环展开成32个并行，每一次同时解决32个像素点，行将循环次数缩小了32倍，大大减速了程序。分数由版本二的10.3分涨到了15.3分。特地是在哦1024 * 1024时，由15.1间接降到了5.0，性能晋升还是很显著的。
Optimizing Smooth
在这一部分中，您将优化平滑度以实现尽可能低的CPE。例如，运行提供的奢侈版本（为了平滑）的驱动程序将生成如下所示的输入：
unix> ./driverSmooth: Version = naive_smooth: Naive baseline implementation:Dim 32 64 128 256 512 MeanYour CPEs 695.8 698.5 703.8 720.3 722.7Baseline CPEs 695.0 698.0 702.0 717.0 722.0Speedup 1.0 1.0 1.0 1.0 1.0 1.0 void naive_smooth(int dim, pixel *src, pixel *dst) { int i, j; for(i=0; i < dim; i++) for(j=0; j < dim; j++) dst[RIDX(i,j,dim)] = avg(dim, i, j, src); /* Smooth the (i,j)th pixel */ return;}这个函数的作用是平滑图像，在smooth函数中因为要求四周点的平均值，所以会频繁的调用avg函数，而且avg函数还是一个2层for循环，所以咱们能够思考循环展开或者打消函数调用等办法，缩小avg函数调用和循环。
Smooth函数解决分为4块，一为主体外部，由9点求平均值；二为4个顶点，由4点求平均值；三为四条边界，由6点求平均值。从图片的顶部开始解决，再上边界，程序解决下来，其中在解决左边界时，for循环解决一行主体局部。
未经优化的函数性能如下，得分为12.2分。
优化版本一：打消函数调用
void smooth(int dim, pixel *src, pixel *dst){pixel_sum rowsum[530][530]; int i, j, snum; for(i=0; i<dim; i++) { rowsum[i][0].red = (src[RIDX(i, 0, dim)].red+src[RIDX(i, 1, dim)].red); rowsum[i][0].blue = (src[RIDX(i, 0, dim)].blue+src[RIDX(i, 1, dim)].blue); rowsum[i][0].green = (src[RIDX(i, 0, dim)].green+src[RIDX(i, 1, dim)].green); rowsum[i][0].num = 2; for(j=1; j<dim-1; j++) { rowsum[i][j].red = (src[RIDX(i, j-1, dim)].red+src[RIDX(i, j, dim)].red+src[RIDX(i, j+1, dim)].red); rowsum[i][j].blue = (src[RIDX(i, j-1, dim)].blue+src[RIDX(i, j, dim)].blue+src[RIDX(i, j+1, dim)].blue); rowsum[i][j].green = (src[RIDX(i, j-1, dim)].green+src[RIDX(i, j, dim)].green+src[RIDX(i, j+1, dim)].green); rowsum[i][j].num = 3; } rowsum[i][dim-1].red = (src[RIDX(i, dim-2, dim)].red+src[RIDX(i, dim-1, dim)].red); rowsum[i][dim-1].blue = (src[RIDX(i, dim-2, dim)].blue+src[RIDX(i, dim-1, dim)].blue); rowsum[i][dim-1].green = (src[RIDX(i, dim-2, dim)].green+src[RIDX(i, dim-1, dim)].green); rowsum[i][dim-1].num = 2; } for(j=0; j<dim; j++) { snum = rowsum[0][j].num+rowsum[1][j].num; dst[RIDX(0, j, dim)].red = (unsigned short)((rowsum[0][j].red+rowsum[1][j].red)/snum); dst[RIDX(0, j, dim)].blue = (unsigned short)((rowsum[0][j].blue+rowsum[1][j].blue)/snum); dst[RIDX(0, j, dim)].green = (unsigned short)((rowsum[0][j].green+rowsum[1][j].green)/snum); for(i=1; i<dim-1; i++) { snum = rowsum[i-1][j].num+rowsum[i][j].num+rowsum[i+1][j].num; dst[RIDX(i, j, dim)].red = (unsigned short)((rowsum[i-1][j].red+rowsum[i][j].red+rowsum[i+1][j].red)/snum); dst[RIDX(i, j, dim)].blue = (unsigned short)((rowsum[i-1][j].blue+rowsum[i][j].blue+rowsum[i+1][j].blue)/snum); dst[RIDX(i, j, dim)].green = (unsigned short)((rowsum[i-1][j].green+rowsum[i][j].green+rowsum[i+1][j].green)/snum); } snum = rowsum[dim-1][j].num+rowsum[dim-2][j].num; dst[RIDX(dim-1, j, dim)].red = (unsigned short)((rowsum[dim-2][j].red+rowsum[dim-1][j].red)/snum); dst[RIDX(dim-1, j, dim)].blue = (unsigned short)((rowsum[dim-2][j].blue+rowsum[dim-1][j].blue)/snum); dst[RIDX(dim-1, j, dim)].green = (unsigned short)((rowsum[dim-2][j].green+rowsum[dim-1][j].green)/snum); }}在以上的优化中，咱们勾销了对avg函数的间接调用，而是间接对像素点的fgb色彩别离求均值，并且将反复利用的数据存储在了数组之中，因而，速度比之前有所晋升，然而晋升并不高，由12.2晋升到15.4。
优化版本二：离开探讨，分块求均匀
void smooth(int dim, pixel *src, pixel *dst){ int i,j; int dim0=dim; int dim1=dim-1; int dim2=dim-2; pixel *P1, *P2, *P3; pixel *dst1; P1=src; P2=P1+dim0; //左上角像素解决 dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2; dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2; dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2; dst++; //上边界解决 for(i=1;i<dim1;i++) { dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red)/6; dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green)/6; dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue)/6; dst++; P1++; P2++; } //右上角像素解决 dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2; dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2; dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2; dst++; P1=src; P2=P1+dim0; P3=P2+dim0; //左边界解决 for(i=1;i<dim1;i++) { dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red+P3->red+(P3+1)->red)/6; dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green+P3->green+(P3+ 1)->green)/6; dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue+P3->blue+(P3+1)->blue)/6; dst++; dst1=dst+1; //两头主体局部解决 for(j=1;j<dim2;j+=2) { //同时解决两个像素 dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red+P3->red+(P3+1)->red+(P3+2)->red)/9; dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green+P3->green+(P3+1)->green+(P3+2)->green)/9; dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue+P3->blue+(P3+1)->blue+(P3+2)->blue)/9; dst1->red=((P1+3)->red+(P1+1)->red+(P1+2)->red+(P2+3)->red+(P2+1)->red+(P2+2)->red+(P3+3)->red+(P3+1)->red+(P3+2)->red)/9; dst1->green=((P1+3)->green+(P1+1)->green+(P1+2)->green+(P2+3)->green+(P2+1)->green+(P2+2)->green+(P3+3)->green+(P3+1)->green+(P3+2)->green)/9; dst1->blue=((P1+3)->blue+(P1+1)->blue+(P1+2)->blue+(P2+3)->blue+(P2+1)->blue+(P2+2)->blue+(P3+3)->blue+(P3+1)->blue+(P3+2)->blue)/9; dst+=2; dst1+=2; P1+=2; P2+=2; P3+=2; } for(;j<dim1;j++) { dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red+P3->red+(P3+1)->red+(P3+2)->red)/9; dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green+P3->green+(P3+1)->green+(P3+2)->green)/9; dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue+P3->blue+(P3+1)->blue+(P3+2)->blue)/9; dst++; P1++; P2++; P3++; } //右侧边界解决 dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red+P3->red+(P3+1)->red)/6; dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green+P3->green+(P3+1)->green)/6; dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue+P3->blue+(P3+1)->blue)/6; dst++; P1+=2; P2+=2; P3+=2; } //右下角解决 dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2; dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2; dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2; dst++; //下边界解决 for(i=1;i<dim1;i++) { dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red)/6; dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green)/6; dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue)/6; dst++; P1++; P2++; } //右下角像素解决 dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2; dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2; dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2; }在这个版本中，咱们在版本一的根底上持续优化。将Smooth函数分为外部-顶点-边界的四局部，一为主体外部，由9点求平均值；二为4个顶点，由4点求平均值；三为四条边界，由6点求平均值。从图片的顶部开始解决，再上边界，程序解决下来，其中在解决左边界时，for循环解决一行主体局部，就是以上的代码。
下图为测试后果，由版本一的分15.4分晋升到了44.1分，性能晋升显著！
总结
本次试验的趣味性不如前几个试验，难度也没有前几个试验的大。在理论优化程序时，咱们不能一味的为了速度而开展程序，或者打消函数援用，以程序的体积和可读性去换取性能的晋升是十分不划算的。在保障可读性的前提下尽可能去晋升程序的性能。
如遇到排版错乱的问题，能够通过以下链接拜访我的CSDN。
**CSDN:[CSDN搜寻“嵌入式与Linux那些事”]