Performance-lab是利用书中的知识,对图像处理中的rotate和smooth操作函数进行优化。这个实验也没有一个标准的答案,这里就根据自己的理解和网上查到的知识进行一下优化。
lab的具体内容可以在官网中下载,所有的lab代码在GitHub上。
1 Rotate
我们首先查看原naive_rotate函数如下,其实进行的就是逆时针90°的旋转
1 |
|
1.1 调换i,j的顺序
在原来的naive_rotate的src是按照行访问,dst是按照列访问,我们将其改成src按列访问,dst按行访问,如下:
1 | void rotate(int dim, pixel *src, pixel *dst) |
其运行的结果如下所示,可以看到有很大的提升,原因在于之前每次内循环都得计算依次dim-1-j
,而现在每次外循环才计算一次dim-1-i,大大减小了计算量。
1 | $ ./driver |
1.2 循环展开
循环展开可以避免频繁地测试循环条件从而加快执行速度:
- writeup中图片尺寸是32的倍数,所以我们可以进行32路展开;
- 根据空间局部性原则,使内部循环步长短于外部循环;
所以我们给出以下代码:执行结果如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45void rotate(int dim, pixel *src, pixel *dst)
{
int i,j;
dst+=(dim*dim-dim);
for(i=0;i<dim;i+=32){
for(j=0;j<dim;j++){
dst[0]=src[0];
dst[1]=src[dim];
dst[2]=src[2*dim];
dst[3]=src[3*dim];
dst[4]=src[4*dim];
dst[5]=src[5*dim];
dst[6]=src[6*dim];
dst[7]=src[7*dim];
dst[8]=src[8*dim];
dst[9]=src[9*dim];
dst[10]=src[10*dim];
dst[11]=src[11*dim];
dst[12]=src[12*dim];
dst[13]=src[13*dim];
dst[14]=src[14*dim];
dst[15]=src[15*dim];
dst[16]=src[16*dim];
dst[17]=src[17*dim];
dst[18]=src[18*dim];
dst[19]=src[19*dim];
dst[20]=src[20*dim];
dst[21]=src[21*dim];
dst[22]=src[22*dim];
dst[23]=src[23*dim];
dst[24]=src[24*dim];
dst[25]=src[25*dim];
dst[26]=src[26*dim];
dst[27]=src[27*dim];
dst[28]=src[28*dim];
dst[29]=src[29*dim];
dst[30]=src[30*dim];
dst[31]=src[31*dim];
src++;
dst-=dim;
}
src+=31*dim;
dst+=dim*dim+32;
}
}1
2
3
4
5
6
7
8
9
10
11
12$ ./driver
Rotate: Version = naive_rotate: Naive baseline implementation:
Dim 64 128 256 512 1024 Mean
Your CPEs 2.8 4.1 5.3 8.9 10.9
Baseline CPEs 14.7 40.1 46.4 65.9 94.5
Speedup 5.3 9.9 8.8 7.4 8.7 7.8
Rotate: Version = rotate: Current working version:
Dim 64 128 256 512 1024 Mean
Your CPEs 2.3 2.3 2.4 2.4 4.8
Baseline CPEs 14.7 40.1 46.4 65.9 94.5
Speedup 6.4 17.1 19.0 28.0 19.6 16.3
1.3 矩阵分块
矩阵分块也可以认为是循环展开的一种,我们以32为矩阵分块的单位,代码如下:
1 | void rotate(int dim, pixel *src, pixel *dst) |
执行结果如下,可以发现,这种方式和前一种有着差不多的优化速度,且代码可读性更佳。
1 | $ ./driver |
2 Smooth
这题采用分类讨论和减少函数调用的方式去做,如下代码所示:
1 | void smooth(int dim, pixel *src, pixel *dst) |
运行结果如下:
1 | $ ./driver |
小结
书本上的知识还是很难应用到实际中,而且许多函数修改完以后可读性变差,所以这里做这个实验的感觉并没有前几个实验做得那么爽快。