Cache综合应用案例 某计算机的主存地址空间大小为256 MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64 B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示： 程序A： int a[256][256]; …… int.

Presentation on theme: "Cache综合应用案例 某计算机的主存地址空间大小为256 MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64 B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示： 程序A： int a[256][256]; …… int."— Presentation transcript:

1 Cache综合应用案例 某计算机的主存地址空间大小为256 MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64 B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示： 程序A： int a[256][256]; …… int sum_array1 ( ) { int i, j, sum = 0; for ( i = 0; i < 256; i++) for (j = 0; j < 256; j++) sum += a[i] [j]； return sum； } 程序B： int a[256][256]; …… int sum_array2 ( ) { int i, j, sum = 0; for ( j = 0; j < 256; j++) for ( i = 0; i < 256; i++) sum += a[i] [j]； return sum； }

2 假定int类型数据用32位补码表示，程序编译时i, j, sum均分配在寄存器中，数组a按行优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
（1）若不考虑用于Cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少？ （2）数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）？ （3）程序A和B的数据访问命中率各是多少？哪个程序的执行时间更短？

3 [答案] （1）数据Cache的总容量为：4256位（532字节）。 （2）数组a在主存的存放位置及其与Cache之间的映射为： a[0][31]所在主存块映射到Cache第6行， a[1][1] 所在主存块映射到Cache第5行。 （3）编译时i, j, sum均分配在寄存器中，故数据访问命中率仅考虑数组a的情况。 ①程序A的数据访问命中率为93.75%； ②程序B的数据访问命中率为0。 程序A的执行比程序B快得多。

4 [解析] （1）主存容量256MB，按字节寻址的地址位数应为28位，数据Cache分为8行（用3位地址），每行64B（用6位地址），因此Cache中每个字块的Tag字段的位数应是28-9=19位，还要使用一个有效位，二者合计为20位；因此数据Cache的总容量应为：64B×8+(20/8×8)B = 532B。 （2）数组a在主存的存放位置及其与Cache之间的映射关系如下图所示。 数组a 按行优先方式存放，其起始地址：a[0][0]=320=140H，int类型数据用32位补码表示，每个数占4个字节单元，数组中,a[i][j]在内存的地址：a[i][j]= a[0][0] +(256i+j)×4 = 140H+(256i+j)×4 则a[0] [31]所在的主存对应的地址：a[0][31]=140H+31×4=1BCH a[1] [1]所在的主存对应的地址： A[1][1]=140H+（256+1）×4= 140H =140H+400H+4H=544H 主存地址空间大小为256MB=228，每个Cache行大小为64Ｂ，8行 数组A[0][31]所在的主存块对应的Cache行号是： （（320+31×4）/ 64） mod 8 = 6。或 1BCH= … B 数组A[1][1]所在主存块对应的Cache行号： (( ×4+ 1×4) / 64) mod 8 = 5。或 544H= … B 所以　a[0][31]所在主存块映射到Cache第6行，a[1][1]所在主存块映射到Cache第5行。

5 数组a在主存的存放位置及其与Cache之间的映射关系
主存地址 19位 3位 6位 主存区号 Cache 行号 行内 地址 Tag Cache地址 一个Cache行 有效位 V Tag Cache 行号 行内 地址 1位 位 3位 6位

6 （3）编译时i, j, sum均分配在寄存器中，故数据访问命中率仅考虑数组a的情况。
①这个程序的特点是数组中的每一个int 类型的数据只被使用一次。数组A按行优先存放，因为 64B×8=128×4B，数据Cache正好放下数组半行中的全部数据，即数据的存储顺序与使用次序有更高的吻合度，每个字块存16个int类型的数据，访问每个字块中头一个字不会命中，但接下来的15个字都会命中，访问全部字块都符合这一规律，命中率是15/16，即程序A的数据访问命中率为93.75%； ②而程序B是按照数组的列执行外层循环，在内层循环过程中，将连续访问不同行的同一列的数据，不同行的同一列数据使用的是同一个Cache单元，每次都不会命中，命中率是0，程序执行特别慢。 根据上述计算出的命中率，得出程序B每次取数都要访问主存，所以程序A的执行比程序B快得多。