【正确答案】正确答案：二维数组a的所有元素在内存中的存放顺序是按行优先方式存放的，即从数组的首地址开始，先顺序存放第一行的256个元素，再存放第二行的256个元素，依此类推。 数组每个数据32位，即4个字节，一个cache行64字节，故可以存放16个数据。 (1)若不考虑用于cache一致性维护和替换算法的控制位，则数据Cache的总容量是多少? 通常所说的cache容量均指数据区容量，按此理解，数据cache的总容量是8×64=512B。 也有个别文献将cache的控制位也计入cache总容量，此时还应加入标记和有效位的空间： 标记位数=主存地址位数－cache地址位数=28－9=19 (2)数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是： a[0][31]主存起始地址：320+31×4=444， 块号=444／64=6，cache行号6rood8=6 a[1][1]主存起始地址：320+(256+1)×4=1348， 块号=1348／64=21，cache行号21mod8=5 (3)程序A和B的数据访问命中率计算： 设处理机为32位，即每次访存读取4个字节。 本题给出的两个程序实现数组求和功能，即计算256行、256列的二维数组a[256][256]的所有元素之和。 程序A逐行访问数组，故数据的访问次序与存放次序相同。程序B逐列访问数组，故连续两次访存内存地址的间隔为256。由于cache的容量相对较小，不足以调人数组的所有元素。故在按行访问时，大部分访存可以命中cache，只有cache每行从主存调入的第一次访问不命中：但按列访问量，每个cache行在调入后一次也未被访问即被调出。 程序A： 解法1：第一次访存不命中，直接访问主存并将当前页调入cache，此后15次访存都访问当前页，故全部命中cache；第17次访存的数据不在当前页，故不命中，直接访问主存并将该页调入cache，但此后的15次访存又都访问当前页，故全部命中cache；依此类推，命中率是15／16=93．75％ 解法2：总访存次数=数组元素个数=256×256×4=2 ¹⁶ ；每次对加载到cache某行中的第一个数据的访问都不命中cache，故未命中次数=占用内存块数=2 ¹⁶ ×4／64=2 ¹² ；故命中率=(2 ¹⁶ －2 ¹² )／2 ¹⁶ =93．75％。 程序B： 数组每行256个数据，占用256×4=1024个地址，共需1024／64=16个cache页，cache共8页。程序的访问次序是a[0，0]、a[1，0]、a[2，0]、a[3，0]……，cache的8行被依次加载的数据为：a[0，0]～a[0，15]、a[1，0]～a[1，15]、a[2，0]～a[7，0]～a[7，15]，当访问a[8，0]时，a[0，0]～a[0，15]被换出，以此类推，每次访存均不命中，故命中率是0。 比较后可知，程序A的执行时间更短。