提高程序局部性

介绍：

本次的任务：

密集型内存访问优化，跟图像处理有关。需要优化两个函数：

• rotate：将图像顺时针旋转90度
• smooth：平滑图像，更加准确地说是模糊化一个图像
  目的：尽可能地在 "模拟的L1 cache"（由助教提供，用于模拟计算机的cache）上提高这些函数的cache命中率。用二维数组M存储图像信息，Mi,j表示第（i,j）个像素。为了简化，本次实验只处理正方形的图像。下标以0开始，最大下标为N-1。每个像素点有4个byte，分别用于存储red，green，blue，alpha属性。（这些属性每个都是1个byte），如下图所示：
  typedef struct {
unsigned short red : 8;
unsigned short green : 8;
unsigned short blue : 8;
unsigned short alpha : 8;
} pixel;

逻辑：

文件用途：

cache.c：用于模仿cache
cache.h：...
defs.h：包含一些用到的变量和结构的定义
driver.c：测试两个函数的主程序
rotate.c：需要修改的文件1：rotate
smooth.c：需要修改的文件2：smooth

只要交rotate.c和smooth.c

实现细节：

数据呈现：

n * n的矩阵实际上是存放在一维矩阵中的，M（i,j） = Img[PIXEL(i，j，n)]，PIXEL(i,j,n) = （i*n+j）
通过宏定义COPY和SMOOTH间接调用cache模拟器（定义在defs.h中）

Cache结构：

模拟的Cache是一个16KB的直接映射缓存，具有32byte的cache line，好好看看笔记因此来决定如何最好地对这样一个结构的cache进行优化

Rotate：

src：源矩阵，dst：目标矩阵，dim：nn矩阵的那个n
void rotate_naive(int dim, pixel src, pixel* dst) ;
你的目的就是通过修改算法从而达到最大的cache命中率

Smooth：

参数：同理
实际的平滑操作由宏SMOOTH进行操作，首先获得目标像素的地址，然后获得源地址和它周围的八个像素。对于在边界的像素，直接使用宏COPY将其copy到目标像素，这样的话就不用单独处理这些没有8个周围像素的特殊情况了。代码首先处理掉图像的边缘部分，将它们直接复制到目标像素。然后以常规的方式对图像进行遍历，对遍历的每个像素进行平滑。与rotate函数相同，你需要做的也是通过改善程序局部性提高cache命中率。

评估方式：

你需要提交进行优化后的算法，可以通过cache模拟器检测其性能。有很多个测试案例，每个测试案例都会得到一个命中率（命中次数/cache访问总次数）

hit score通过取（命中率/之前的命中率）的几何平均值确定。几何平均值的计算如下，

hit score

假设：

为了使优化更加简单，可以假设图像的尺寸都是32的倍数：64,128,256,512,1024等

设置

版本：

rotate.c和smooth.c都只包含两个函数，其中有一个register函数，可以同时比较多个函数，在测试之前会被driver调用。这个函数一次或者多次调用add_rotate_function，add_rotate_function的作用是注册函数并未该函数添加描述。smooth.c同理

register_rotate_functions

测试：

打开项目-->生成-->执行，就会显示输出（检测你的算法的cache命中率的输入文件一直都是那些）

正确率：（必须和之前的功能一样，由驱动程序检查）
速度提升（不同的速度提升会有不同的分数，见pdf中的图

speed

提示：

• rotate函数侧重于空间局部性，因为每个像素只被使用一次，你应该专注于put into the cache by a previous pixel operation.（这句话不会翻译）
• smooth：受益于空间局部性，但也重用了已访问过的像素，因此，应该也要尝试提高时间局部性
• 尝试大量不同的函数，FIND_BEST_OF_MANY可以找出哪个函数的命中率最大
• 只是因为你的图像是方形的，并不意味着你必须处理方形图像

============我是分割线============
2018.7.29 修改

• put into the cache by a previous pixel operation.（如果之前的某个像素点被访问过，那么将它放入cache）