实验答案托管在我的GitHub上
由于Cache Lab的Part B的64 × 64的矩阵一直拿不到满分，索性放在了一边，先从老的Performance Lab开始做起。
实验简介
Performance Lab - Code Optimization是有关性能优化的实验，对应于书本的第5章：优化程序性能和第6章：存储器层次结构。主要提供了利用书本所学的知识优化代码的机会。
本实验主要分为两个部分，每个部分分别对于一个简单的图像处理函数进行优化。第一个部分所优化的函数旋转(rotate)对于缓存更加敏感，而第二个部分所优化的函数平滑(smooth)则属于计算密集型函数。对它们优化的侧重是有所不同的。
本实验的具体介绍见实验讲义。
实验介绍
在本实验中，我们将实现两个图像处理函数——旋转和平滑。
我们将一张图片抽象地表示为一个二维矩阵M，M(i, j)代表了M中第i行第j列的像素的值，该像素值被定义为红色、绿色、蓝色（RGB）的值的三元组。在本实验中，我们只考虑正方形的图片。下标遵循C语言风格，从0到N-1。
旋转操作被定义为将图片逆时针旋转90°，旋转可以分为两步实现——
- 将矩阵转置，即将M(i, j)变为M(j, i)
- 将矩阵的第i行和第N - i - 1交换
平滑操作被定义为将每一个像素点的值换位周围像素点（以该像素点为中心的最多3*3的正方形）的平均值。
实验要求
在本实验中像素（pixel）是一个定义如下的结构体：1
2
3
4
5
6The core data structure deals with image representation. A pixel is a struct as shown below:
typedef struct {
unsigned short red; /* R value */
unsigned short green; /* G value */
unsigned short blue; /* B value */
} pixel;
此外，为了简化起见，还定义了如下的宏：1
旋转操作的朴素版本如下：1
2
3
4
5
6
7void 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;
}
平滑操作的朴素版本如下（辅助函数未列出）：1
2
3
4
5
6
7void 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;
}
为了简化起见，你可以假设所有的矩阵的边长都是32的倍数，并且在进行正确性测试的时候，只会测试5个值。
具体的注册函数和自动跑分机制请参阅实验讲义。
实验思路
旋转操作：旋转操作不涉及复杂的计算，经过测试将代码移动所带来的性能提升微乎其微。主要应当采用分块的手段提高代码的空间局部性的利用率。
平滑操作（平滑操作参考了别人的思路）：平滑操作是计算密集型函数，经过测试，通过减少过程调用以及代码移动带来的有限的性能提升。
观察原始代码可以发现分支预测的惩罚是巨大的（因为循环只会执行3次，会带来大量的预测不命中）。我们可以考虑将红、绿、蓝三色的值的计算分开地并行处理，并且依次处理四个角、四条边、和剩余的像素点。以提升局部性的利用率并且降低分支预测不命中所带来的惩罚。
实验答案
旋转操作：1
2
3
4
5
6
7
8
9
10
11
12
13void block_rotate(int dim, pixel * src, pixel * dst) {
int i, j, k, l;
int cst0 = dim - 1;
for (i = 0 ; i < dim ; i += 8) {
for (j = 0 ; j < dim ; j += 8) {
for (k = i ; k < i + 8 ; k++) {
for (l = j ; l < j + 8 ; l++) {
dst[RIDX(cst0 - l, k, dim)] = src[RIDX(k, l, dim)];
}
}
}
}
}
平滑操作：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
45
46
47
48
49
50void optimized_smooth(int dim, pixel * src, pixel * dst) {
int i, j;
int tmp;
dst[0].red = (src[0].red + src[1].red + src[dim].red + src[dim + 1].red) >> 2;
dst[0].green = (src[0].green + src[1].green + src[dim].green + src[dim + 1].green) >> 2;
dst[0].blue = (src[0].blue + src[1].blue + src[dim].blue + src[dim + 1].blue) >> 2;
i = dim - 1;
dst[i].red = (src[i].red + src[i - 1].red + src[i + dim].red + src[i + dim -1].red) >> 2;
dst[i].green = (src[i].green + src[i - 1].green + src[i + dim].green + src[i + dim -1].green) >> 2;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + dim].blue + src[i + dim -1].blue) >> 2;
i = i * dim;
dst[i].red = (src[i].red + src[i + 1].red + src[i - dim].red + src[i - dim + 1].red) >> 2;
dst[i].green = (src[i].green + src[i + 1].green + src[i - dim].green + src[i - dim + 1].green) >> 2;
dst[i].blue = (src[i].blue + src[i + 1].blue + src[i - dim].blue + src[i - dim + 1].blue) >> 2;
i = i + dim - 1;
dst[i].red = (src[i].red + src[i - 1].red + src[i - dim].red + src[i - dim - 1].red) >> 2;
dst[i].green = (src[i].green + src[i - 1].green + src[i - dim].green + src[i - dim - 1].green) >> 2;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i - dim].blue + src[i - dim - 1].blue) >> 2;
for (i = 1 ; i < dim - 1 ; i++) {
dst[i].red = (src[i].red + src[i - 1].red + src[i + 1].red + src[i + dim].red + src[i + dim - 1].red + src[i + dim + 1].red) / 6;
dst[i].green = (src[i].green + src[i - 1].green + src[i + 1].green + src[i + dim].green + src[i + dim - 1].green + src[i + dim + 1].green) / 6;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + 1].blue + src[i + dim].blue + src[i + dim - 1].blue + src[i + dim + 1].blue) / 6;
}
for (i = dim * (dim - 1) + 1 ; i < dim * dim - 1 ; i++) {
dst[i].red = (src[i].red + src[i - 1].red + src[i + 1].red + src[i - dim].red + src[i - dim - 1].red + src[i - dim + 1].red) / 6;
dst[i].green = (src[i].green + src[i - 1].green + src[i + 1].green + src[i - dim].green + src[i - dim - 1].green + src[i - dim + 1].green) / 6;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + 1].blue+ src[i - dim].blue + src[i - dim - 1].blue+ src[i - dim + 1].blue) / 6;
}
for (j = dim ; j < dim * (dim - 1) ; 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 + dim + 1].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 + 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 + dim + 1].blue) / 6;
}
for (j = 2 * dim - 1 ; j < dim * dim - 1 ; 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 + dim - 1].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 + 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 + dim - 1].blue) / 6;
}
for (i = 1 ; i < dim - 1 ; i++) {
for (j = 1 ; j < dim - 1 ; j++) {
tmp = i * dim + j;
dst[tmp].red = (src[tmp].red + src[tmp - 1].red + src[tmp + 1].red + src[tmp - dim].red + src[tmp - dim - 1].red + src[tmp - dim + 1].red + src[tmp + dim].red + src[tmp + dim - 1].red + src[tmp + dim + 1].red) / 9;
dst[tmp].green = (src[tmp].green + src[tmp - 1].green + src[tmp + 1].green + src[tmp - dim].green + src[tmp - dim - 1].green + src[tmp - dim + 1].green + src[tmp + dim].green + src[tmp + dim - 1].green + src[tmp + dim + 1].green) / 9;
dst[tmp].blue = (src[tmp].blue + src[tmp - 1].blue + src[tmp + 1].blue + src[tmp - dim].blue + src[tmp - dim - 1].blue + src[tmp - dim + 1].blue + src[tmp + dim].blue + src[tmp + dim - 1].blue + src[tmp + dim + 1].blue) / 9;
}
}
}
实验总结
实验的第一部分对于缓存的要求不是很高，简单的分块可以带来很大的性能提升。
实验的第二部分实际上我是卡了比较久的，在发现减少过程调用和代码移动性能提升有限后我就卡住了，因为我发现似乎无法进行循环展开。实际上还是太生疏了，没有想到要分析性能瓶颈，最后参考了别人的答案，实际上看到了别人答案的一瞬间就豁然开朗了，但是在这之前完全没有想到会是分支预测的问题。还需要多加练习。