Lec7 高速缓存习题

计算机系统院系 学号 姓名 授课教师 密封线一、 单项选择题（每小题1分，共20分）1. 位于存储器层次结构中的最顶部的是( A )。A. 寄存器 B. 主存 C. 磁盘 D. 高速缓存2. CPU一次访存时，访问了L1、L2、L3 Cache所用地址A1、A2、A3的关系（ B ）A.A1A2A3 B.A1=A2=A3 C.A1A2A3 D.A1=A28)字节，向量 v 的元素为 int，则对 v 的步长为 1 的应用的不命中率为_4/B_。 三、 判断对错（每小题1分，共10分，在题前打 X 符号）1. （ ）全相联Cache不会发生冲突不命中的情况。2. （ x ）直接映射Cache一定会发生冲突不命中的情况。四、简答题1. 简述程序的局部性原理，如何编写局部性好的程序？时间局部性空间局部性答：局部性原理: 1分 程序倾向于使用与最近使用过数据的地址接近或是相同的的数据和指令. 时间局部性: 最近引用的项很可能在不久的将来再次被引用，如代码和变量等；空间局部性: 与被引用项相邻的项有可能在不久的将来再次被引用。2分让通用或共享的功能或函数最常见情况运行得快：专注在核心函数和内循环.2分尽量减少每个循环内部的缓存不命中数量：反复引用变量是好的(时间局部性)寄存器-编译器；步长为1的 参考模式是好的(空间局部性)-缓存是连续块一旦从内存中读入数据对象，尽可能多的使用它，使得程序中时间局部性最大。2. 结合下面的程序段，解释局部性。int cal_array_sum(int *a,int n) int sum = 0;for (int i = 0; i n; i+) sum += ai;return sum;局部性原理（1分）: 程序倾向于使用与最近使用过数据的地址接近或是相同的 数据和指令.包括时间局部性和空间局部性。空间局部性（2分）：1、对数据的引用：顺序访问数组元素(步长为1的引用模式) 2、对指令的引用：顺序读取指令 时间局部性（2分）：1、对数据的引用：变量sum在每次循环迭代中被引用一次 2、对指令的引用：重复循环执行for循环体 五、系统分析题（每小题5分，共20分） 1. Intel I7 CPU的虚拟地址 48位，物理地址52位。其内部结构如下图所示，依据此结构， L1数据Cache共_64_组。 （所有缓存都是64 字节）用物理地址访问L1数据Cache时， Cache标记CT占_40_位六、综合设计题（每小题10分，共20分）1. 程序优化: 矩阵cn,n = an,n * bn,n ，采用 48题 I7 CPU。块64B。 for(int i=0;in;i+) for(int j=0;jn;j+) ci,j=0; for(int k=0; kn;k+)ci,j+=ai,k*bkj; 请针对该程序进行速度优化，写出优化后的程序，并说明优化的依据。1. Cache优化：尽量制造局部性调整循环顺序2. 编译优化：代码移动，移出循环3. CPU优化：循环展开for(int i=0;in;i+) for(int k=0;kn;k+) for(int j=0; jn;j+)ci,j += ai,k*bkj; for(int i=0;in;i+) for(int k=0;kn;k+) tmp = ai,k;for(int j=0; jn;j+)ci,j += tmp*bkj; for(int i=0;in;i+) for(int k=0;kn;k+) tmp = ai,k;for(int j=0; jn/2;j=j+2)ci,j += tmp*bkj; ci,j+1 += tmp*bkj+1; 从以下两方面给分：1、采用的方法：（1）调整循环变量次序（2）循环展开（3）局部变量累积等2、代码实现：基本正确（重在思路，不计较语法细节）3、论述分析清晰、有理1. 现代超标量CPU X86-64的Cache的参数s=5，E=1，b=5，若M=N=64, 请优化如下程序，并说明优化的方法（至少CPU与Cache各一种）。void trans(int M, int N, int AMN, int BNM) for (int i = 0; i M; i+) for (int j = 0; j N; j+) Bji =Aij; 1. Cache优化：分块矩阵（分块的大小） 32/4 = 8,块大小是8 for (int i = 0; i M/8; i=i+8) fo