深入理解计算机系统PerformanceLab实验报告

实验答案托管在我的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）是一个定义如下的结构体：

The 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	#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;
}

平滑操作的朴素版本如下（辅助函数未列出）：

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;
}

为了简化起见，你可以假设所有的矩阵的边长都是32的倍数，并且在进行正确性测试的时候，只会测试5个值。

具体的注册函数和自动跑分机制请参阅实验讲义。

实验思路

旋转操作：旋转操作不涉及复杂的计算，经过测试将代码移动所带来的性能提升微乎其微。主要应当采用分块的手段提高代码的空间局部性的利用率。

平滑操作（平滑操作参考了别人的思路）：平滑操作是计算密集型函数，经过测试，通过减少过程调用以及代码移动带来的有限的性能提升。
观察原始代码可以发现分支预测的惩罚是巨大的（因为循环只会执行3次，会带来大量的预测不命中）。我们可以考虑将红、绿、蓝三色的值的计算分开地并行处理，并且依次处理四个角、四条边、和剩余的像素点。以提升局部性的利用率并且降低分支预测不命中所带来的惩罚。

实验答案

旋转操作：

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

平滑操作：

void 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;
        }
    }
}

实验总结

实验的第一部分对于缓存的要求不是很高，简单的分块可以带来很大的性能提升。

实验的第二部分实际上我是卡了比较久的，在发现减少过程调用和代码移动性能提升有限后我就卡住了，因为我发现似乎无法进行循环展开。实际上还是太生疏了，没有想到要分析性能瓶颈，最后参考了别人的答案，实际上看到了别人答案的一瞬间就豁然开朗了，但是在这之前完全没有想到会是分支预测的问题。还需要多加练习。