计组实验报告.doc

课程实验报告
课 程 名 称: 计算机组成与结构
实验项目名称: perflab-handout
专 业 班 级: 计科1403
姓 名:
学 号:
指 导 教 师: 黄丽达
完 成 时 间: 2016 年 5 月 28 日
信息科学与工程学院
实验题目:perflab-handout
实验目得:本次实验得核心任务就是要求修改kernel、c文件,并可以在使用driver进行评测时获得更好得加速比。kernel、c文件中主要有两个需要进行优化得函数:rotate与smooth,并分别给出了naive_rotate与naive_smooth两个函数得基本实现作为baseline作为您改进后得程序得比较对象。本次实验,要求针对每个函数、每个人均至少写出3种优化版本、并根据driver报告得结果进行性能分析。
实验环境:联想ThinkPad E545,Ubuntu14(32位)gdb工具
实验内容及操作步骤:
rotate原始代码分析:
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)];
}
首先要理解RIDX得意思,在头文件defs、h中宏定义了#defineRIDX(i,j,n) ((i)*(n)+(j),意思就是一个n*n得二维数组得第i行,第j列。所以这段代码得就是把一幅画进行逆时针方向旋转90°该函数将所有得像素进行了行列调位、导致整幅图画进行了逆时针90°旋转。
分析代码性能不好得因素:
原代码由于使用了两重for循环,而且每一重for循环得循环次数为dim次,循环次数过多导致程序得性能非常差,优化方法一就是减少循环次数,采用循环展开可以减少循环得次数达到优化效果。
优化1:
void rotate(int dim, pixel *src, pixel *dst)
{
int i, j;
for (i = 0; i < dim-1; i=i+2)
for (j = 0; j < dim; j++)
{
dst[RIDX(dim-1-j, i, dim)] =src[RIDX(i,j,dim)];
dst[RIDX(dim-1-j,i+1,dim)] = src[RIDX(i+1,j,dim)];
}

for (; i < dim; i++)
{
dst[RIDX(dim-1-j, i, dim)] =src[RIDX(i,j,dim)];
}
}
运行结果截图:

从上述截图可以瞧出,当将循环展开成每次做两个像素点得旋转时,程序得性能明显提高,原来代码得加速比就是1、3,优化后性能就是原始代码得两倍,所以循环展开可以提高程序得性能。
优化2:
循环分块与写优先操作结合可以提高性能,原代码因为循环步长太长,以至于cache得命中率非常低,所以总体运算效率不高。因此,我考虑到cache得大小,应在存储得时候进行32个像素依次存储(列存储)。(32个像素排列就是为了充分利用一级缓存(32KB), 采用分块策略, 每一个块大小为32)这样可以做到cache友好、可以大幅度提高效率,同时写优先操作(写地址连续)比原代码得读优先操作(读地址连续)性能会更好。
void rotate(int dim, pixel *src, pixel *dst)
{
int i, j, i1, j1, im, jm;
int block=32;//blocking the Matrix
for(i=0; i<dim; i+=block)
for(j=0; j<dim; j+=block)
{
//block*block mini matrix
im = i+block;
for(i1=i; i1<i+block; i1++) {
jm = j+block;
for(j1=j; j1<j+block; j1++)
dst[RIDX(i1, j1, dim)] = src[RIDX(j1, dim-i1-1, dim)];
}
}
}

从上述截图可以瞧出,当将循环步长分成最大为32,优先dest得写操作时,程序得性能明显提高,原来代码得加速比就是1、3,优化后性能就是原始代码得三倍多,所以循环分块与写优先操作结合可以提高性能。
优化3:
循环展开类循环分块结合,通过减少每次迭代计算元素得数量,减少循环得迭代次数,同时分块可以逐点赋值—>逐行(列)赋值 充分利用块空间,防止前面开辟得块还没有完全利用就被后来得覆盖,提高cache命中率 。
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++;
*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;
dst-=31+dim;
}
dst+=dst_base+dim;
dst+=32;
src+=(dim<<5)-dim;
}
}

从上述截图可以瞧出,当将循环展开32次,同时进行类分块时,程序得性能明显提高,原来代码得加速比就是1、8,优化后性能就是原始代码得四倍多,所以循环展开类循环分块结合可以大大提高程序性能。
smooth原始代码分析:
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);
}
这段代码得就是把一幅画复制一份赝品,赝品得某点得像素为对应原画得周围像素得平均值(如果该像素点在四个顶点,则赝品得该点像素等于原画包括该点得周围四个点得像素平均,如果该像素点为四条边界上得像素点,则赝品得该点像素点等于原画包括该点得周围六个点得像素平均值,如果该像素点为中间点,则该点像素为原画得周围九个点得平均值)。
分析代码性能不好得因素:
这段代码频繁地调用avg函数,并且avg函数中也频繁调用initialize_pixel_sum 、accumulate_sum、assign_sum_to_pixel这几个函数,且又含有2层for循环,而我们应该减少函数调用得时间开销。所以,需要改写代码,不调用avg函数。
优化1:
不调用avg函数,把avg函数写进smooth函数主体中,通过减少函数调用来达到优化程序得目得。
void smooth(int dim, pixel *src, pixel *dst)
{
int i, j;
for (i = 0; i < dim; i++)
{
for (j = 0; j < dim; j++)
{
int ii, jj;
pixel_sum sum;
pixel current_pixel;
sum、red= sum、green = sum、blue = 0;
sum、num= 0;
for(ii= max(i-1, 0); ii <= min(i+1, dim-1); ii++)
{
for(jj = max(j-1, 0); jj <=min(j+1, dim-1); jj++)
{
pixel p=src[RIDX(ii, jj, dim)];
sum、red += (int) p、red;
sum、green+= (int) p、green;
sum、blue+= (int) p、blue;
sum、num++;
}
}
current_pixel、red = (unsigned short)(sum、red/sum、num);
current_pixel、green = (unsigned short)(sum、green/sum、num);
current_pixel、blue= (unsigned short) (sum、blue/sum、num);
dst[RIDX(i, j, dim)] = current_pixel;
}
}
}

从上述运行截图可以瞧出,减少函数调用确实起到了优化代码得作用,但就是优化效果不明显,可能就是编译器在编译得时候做了优化得缘故所以人为得优化性能提升不多,但就是减少函数调用确实可以达到优化代码得效果。
优化2:
对图片进行分块处理,像素点分成图片四个角、图片四条边、图片内部三块分别进行处理。对角而言只需要4个像素点得均值,对于边而言为6个像素点均值,图片内部则需要9个像素点均值。
这样可以减少循环判断得次数,而且原代码得avg函数就是在一次循环中只进行一个像素点得累加,avg函数里用了两重循环,而函数主体有有两重循环,相当于原代码用了四重循环,所以性能很差,所以改进后不使用avg函数,并且通过分块,将每个分块周围得像素点一次性加起来而不就是一个循环累加一个像素点,达到大大减少循环调用得功能。
void smooth(int dim, pixel *src, pixel *dst)
{
int i,j,lastr,lastb,lastg;
int row = dim;
int curr;
//四个角处理
dst[0]、red=(src[0]、red+src[1]、red+src[dim]、red+src[dim+1]、red)>>2;//用">>"代替"/4"节省时间
dst[0]、blue=(src[0]、blue+src[1]、blue+src[dim]、blue+src[dim+1]、blue)>>2;
dst[0]、green=(src[0]、green+src[1]、green+src[dim]、green+src[dim+1]、green)>>2;
dst[dim-1]、red=(src[dim-1]、red+src[dim-2]、red+src[dim*2-2]、red+src[dim*2-1]、red)>>2;
dst[dim-1]、blue=(src[dim-1]、blue+src[dim-2]、blue+src[dim*2-2]、blue+src[dim*2-1]、blue)>>2;
dst[dim-1]、green=(src[dim-1]、green+src[dim-2]、green+src[dim*2-2]、green+src[dim*2-1]、green)>>2;
dst[(dim-1)*dim]、red=(src[(dim-1)*dim]、red+src[(dim-1)*dim+1]、red+src[(dim-2)*dim]、red+src[(dim-2)*dim+1]、red)>>2;
dst[(dim-1)*dim]、blue=(src[(dim-1)*dim]、blue+src[(dim-1)*dim+1]、blue+src[(dim-2)*dim]、blue+src[(dim-2)*dim+1]、blue)>>2;
dst[(dim-1)*dim]、green=(src[(dim-1)*dim]、green+src[(dim-1)*dim+1]、green+src[(dim-2)*dim]、green+src[(dim-2)*dim+1]、green)>>2;
dst[dim*dim-1]、red=(src[dim*dim-1]、red+src[dim*dim-2]、red+src[(dim-1)*dim-1]、red+src[(dim-1)*dim-2]、red)>>2;
dst[dim*dim-1]、blue=(src[dim*dim-1]、blue+src[dim*dim-2]、blue+src[(dim-1)*dim-1]、blue+src[(dim-1)*dim-2]、blue)>>2;
dst[dim*dim-1]、green=(src[dim*dim-1]、green+src[dim*dim-2]、green+src[(dim-1)*dim-1]、green+src[(dim-1)*dim-2]、green)>>2;
//四条边
for (j=1; j < dim-1; j++) {
dst[j]、red=(src[j]、red+src[j-1]、red+src[j+1]、red+src[j+dim]、red+src[j+1+dim]、red+src[j-1+dim]、red)/6;
dst[j]、green=(src[j]、green+src[j-1]、green+src[j+1]、green+src[j+dim]、green+src[j+1+dim]、green+src[j-1+dim]、green)/6;
dst[j]、blue=(src[j]、blue+src[j-1]、blue+src[j+1]、blue+src[j+dim]、blue+src[j+1+dim]、blue+src[j-1+dim]、blue)/6;
}
for (j=dim*(dim-1)+1; j < dim*dim-1; j++) {
dst[j]、red=(src[j]、red+src[j-1]、red+src[j+1]、red+src[j-dim]、red+src[j+1-dim]、red+src[j-1-dim]、red)/6;
dst[j]、green=(src[j]、green+src[j-1]、green+src[j+1]、green+src[j-dim]、green+src[j+1-dim]、green+src[j-1-dim]、green)/6;
dst[j]、blue=(src[j]、blue+src[j-1]、blue+src[j+1]、blue+src[j-dim]、blue+src[j+1-dim]、blue+src[j-1-dim]、blue)/6;
}
for (i=dim; i < dim*(dim-1); i+=dim) {
dst[i]、red=(src[i]、red+src[i-dim]、red+src[i+1]、red+src[i+dim]、red+src[i+1+dim]、red+src[i-dim+1]、red)/6;
dst[i]、green=(src[i]、green+src[i-dim]、green+src[i+1]、green+src[i+dim]、green+src[i+1+dim]、green+src[i-dim+1]、green)/6;
dst[i]、blue=(src[i]、blue+src[i-dim]、blue+src[i+1]、blue+src[i+dim]、blue+src[i+1+dim]、blue+src[i-dim+1]、blue)/6;
}
for (i=dim+dim-1; i < dim*dim-1; i+=dim) {
dst[i]、red=(src[i]、red+src[i-1]、red+src[i-dim]、red+src[i+dim]、red+src[i-dim-1]、red+src[i-1+dim]、red)/6;
dst[i]、green=(src[i]、green+src[i-1]、green+src[i-dim]、green+src[i+dim]、green+src[i-dim-1]、green+src[i-1+dim]、green)/6;
dst[i]、blue=(src[i]、blue+src[i-1]、blue+src[i-dim]、blue+src[i+dim]、blue+src[i-dim-1]、blue+src[i-1+dim]、blue)/6;
}
//图片内部 for(i=1;i<dim-1; i++){
lastr=src[row-dim]、red+src[row-dim+1]、red+src[row-dim+2]、red+src[row]、red+src[row+1]、red+src[row+2]、red+src[row+dim]、red+src[row+dim+1]、red+src[row+dim+2]、red;
lastb=src[row-dim]、blue+src[row-dim+1]、blue+src[row-dim+2]、blue+src[row]、blue+src[row+1]、blue+src[row+2]、blue+src[row+dim]、blue+src[row+dim+1]、blue+src[row+dim+2]、blue;
lastg=src[row-dim]、green+src[row-dim+1]、green+src[row-dim+2]、green+src[row]、green+src[row+1]、green+src[row+2]、green+src[row+dim]、green+src[row+dim+1]、green+src[row+dim+2]、green;
dst[row+1]、red=lastr/9;
dst[row+1]、blue=lastb/9;
dst[row+1]、green=lastg/9;
for(j=2;j<dim-1;j++){
curr=row+j;
lastr=lastr-src[curr-dim-2]、red+src[curr-dim+1]、red-src[curr-2]、red+src[curr+1]、red-src[curr+dim-2]、red+src[curr+dim+1]、red; lastb=lastb-src[curr-dim-2]、blue+src[curr-dim+1]、blue-src[curr-2]、blue+src[curr+1]、blue-src[curr+dim-2]、blue+src[curr+dim+1]、blue; lastg=lastg-src[curr-dim-2]、green+src[curr-dim+1]、green-src[curr-2]、green+src[curr+1]、green-src[curr+dim-2]、green+src[curr+dim+1]、green;
dst[curr]、red=lastr/9;
dst[curr]、blue=lastb/9;
dst[curr]、green=lastg/9;//内部其她点参考该行前一个点得像素值得到结果
}
row+=dim;
}
}
上述代码之所以使用lastr,lastb , lastg,就是因为像素点得与加起来对于原来得unsigned short类型会发生溢出,所以先定义几个int类型得变量保存像素与结果,将与平均后再赋值给每个像素点。

由运行截图可以瞧出,分块后程序性能大大提高,由原来得加速比为6、8提升到加速比为29、3,优化程度很高。这个方法不但就是进行了分块处理,同时也减少了循环得调用,优化结果非常可观。
优化3:
使用循环展开,减少循环次数达到优化效果。
void smooth(int dim, pixel *src, pixel *dst)
{
int i, j;
for (i = 0; i < dim; i++)
for (j = 0; j < dim-1; j+=2)
{
dst[RIDX(i, j, dim)] = avg(dim, i, j, src);
dst[RIDX(i, j+1, dim)] = avg(dim, i, j+1, src);
}
for (; j < dim; j++)
dst[RIDX(i, j, dim)] = avg(dim, i, j, src);
}

从运行截图上可以瞧出,减少循环次数,将循环展开,尽管跟原代码差别不就是很大,但就是还就是有了一些优化,尽管优化效果不够明显,但就是这个方法就是有效得。
实验结果及分析:
从上述运行结果对比来瞧,每个修改代码或多或少都得到了优化,各种方法得优化程度不一,有些方法优化效果非常显著,有些优化效果很小,但就是每一个修改得代码都达到了优化得目得,所以这次实验室成功得。

实
验成绩