实验八 cache和程序访问的局部性

201411011120 高敏

一、实验目的

通过实际程序的执行结果,了解程序访问的局部性对带有 cache 的计算机系统性能的影响。 

二、实验要求

    在main函数中定义一个16*16二维整形数组，然后分别调用程序A和程序B对二维数组中的元素进行求和。在代码中增加计时函数，比较程序A和程序B执行时间是否有差异。

程序段 A

doublesum_array_rows(double a[16][16]){ 

double sum = 0;

for (int r = 0; r < 16; r++){

for (int c = 0; c < 16; c++){

sum += a[r][c];

}}

return sum;}

程序B

doublesum_array_cols(double a[16][16]){ 

double sum = 0;

for (int c = 0; c < 16; c++) {

for (int r = 0; r < 16; r++){

sum += a[r][c];

}}

return sum;}

三、实验报告

1、给出源程序(文本文件)和执行结果。 

程序A

int main(intargc, constchar * argv[]) {

double sum;

int count;

doubleTotal_time;

clock_t start, finish;

double a[16][16];

inti,j;

for(i=0;i<16;i++){

for(j=0;j<16;j++){

a[i][j]=1;

        }

    }

start = clock();

for(count=0;count<1000;count++)    sum=sum_array_rows(a);

finish = clock();

Total_time = (double)(finish-start) / CLOCKS_PER_SEC;

printf( "A=%f seconds\\n", Total_time);

return0;

}

运行结果

程序B：

int main(intargc, constchar * argv[]) {

double sum;

int count;

doubleTotal_time;

clock_t start, finish;

double a[16][16];

inti,j;

for(i=0;i<16;i++){

for(j=0;j<16;j++){

a[i][j]=1;

        }

    }

start = clock();

for(count=0;count<1000;count++)    sum=sum_array_cols(a);

finish = clock();

Total_time = (double)(finish-start) / CLOCKS_PER_SEC;

printf( "A=%f seconds\\n", Total_time);

return0;

}

运行结果

    执行时间有差异，计算二维数组和时，先算行的计算时间比先算列的时间更短。

2、对实验结果进行分析,说明局部数据块大小、数组访问顺序等和执行时间之间的关系。 

在局部数据块大小相同情况下，数组访问顺序按照行优先访问的顺序，执行时间更短。

因为计算机内存是一维的，数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。C语言中，数组按行优先顺序存储。

即将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。

二维数组Amn的按行优先存储的线性序列为：

a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn