;
}
修改后程序的数组元素的访问与排列顺序一致，使得空间局部性比原程序好，故执行时间更短。
13.分析比较以下三个函数的空间局部性，并指出哪个最好，哪个最差？
参考答案：
对于函数1，其数组访问顺序与在内存的存放顺序完全一致，因此，空间局部性最好。
对于函数2，其数组访问顺序在每个数组元素内跳越式访问，相邻两次访问的单元最大相差3个型变量（假定（）=4，则相当于12B），因此空间局部性比1差。
若主存块大小比12B小的话，则大大影响命中率。
对于函数3，其数组访问顺序与在内存的存放顺序不一致，相邻两次访问的单元都相差6个型变量（假定（）=4，则相当于24B）因此，空间局部性比2还差。
若主存块大小比24B小的话，则大大影响命中率。
14.以下是计算两个向量点积的程序段：
（x[8],y[8]）
{
=0.0;
i,;
（i=0;i<8;）x[i]*y[i];
;
}
要求：
（1）试分析该段代码中数组x和y的时间局部性和空间局部性，并推断命中率的高低。
（2）假定该段程序运行的计算机的数据采用直接映射方式，其数据区容量为32字节，每个主存块大小为16字节。
假定编译程序将变量和i分配给寄存器，数组x存放在00000040H开始的32字节的连续存储区中，数组y紧跟在x后进行存放。
试计算该程序数据访问的命中率，要求说明每次访问的命中情况。
（3）将上述
（2）中的数据改用2-路组相联映射方式，块大小改为8字节，其他条件不变，则该程序数据访问的命中率是多少？
（4）在上述
（2）中条件不变的情况下，如果将数组x定义为[12]，则数据访问的命中率是多少？
参考答案：
（1）数组x和y都按存放顺序访问，不考虑映射的情况下，空间局部性都较好，但都只被访问一次，故没有时间局部性。
命中率的高低与块大小、映射方式等都有关，所以，无法推断命中率的高低。
（2）采用直接映射方式，块大小为16字节，数据区大小为32字节，故共有2行。
数组x的8个元素（共32B）分别存放在主存40H开始的32个单元中，共有2个主存块，其中x[0]~x[3]在第4块，x[4]~x[7]在第5块中；数组y的8个元素（共32B）分别在主存第6块和第7块中。
所以，x[0]~x[3]和y[0]~y[3]都映射到第0行；
x[4]~x[7]和y[4]~y[7]都映射到第1行。
第0-3次循环
第4-7次循环
第0行
x[0-3]，y[0-3]
第1行
x[4-7]，y[4-7]
每调入一块，装入4个数组元素，因为x[i]和y[i]总是映射到同一行，相互淘汰对方，故每次都不命中，命中率为0.
（3）改用2路组相联，块大小为8B，则共有4行，每组两行，共两组。
数组x有4个主存块，x[0]~x[1]、x[2]~x[3]，x[4]~x[5]，x[6]~x[7]分别在第8~11块中；
数组y有4个主存块，y[0]~y[1]、y[2]~y[3]，y[4]~y[5]，y[6]~y[7]分别在第12~15块中；
第0行
第1行
第0组
x[0-1][4-5]
y[0-1][4-5]
第1组
x[2-3][6-7]
y[2-3][6-7]
每调入一块，装入两个数组元素，第二个数组元素的访问总是命中，故命中率为50%。
（4）若
（2）中条件不变，数组x定义了12个元素，共有48B，使得y从第7块开始，因而，x[i]和y[i]就不会映射到同一个行中，即：
x[0]~x[3]在第4块，x[4]~x[7]在第5块，x[8]~x[11]在第6块中，y[0]~y[3]在第7块，y[4]~x[7]在第8块。
第0-3次循环
第4-7次循环
第0行
x[0-3]
y[4-7]
第1行
y[0-3]
x[4-7]
每调入一块，装入4个数组元素，第一个元素不命中，后面3个总命中，故命中率为75%。
15.以下是对矩阵进行转置的程序段：
[4][4];
（,）
{
i,j;
（i=0;i<4;）
（j=0;j<4;）
[j][i]=[i][j];
}
假设该段程序运行的计算机中（）=4，且只有一级，其中L1的数据区大小为32B，采用直接映射、写回方式，块大小为16B，初始为空。
数组从地址0000C000H开始存放，数组从地址0000C040H开始存放。
填写下表，说明数组元素[][]和[][]映射到的哪一行，其访问是命中（）还是失效（）。
若L1的数据区容量改为128B时，重新填写表中内容。
数组
数组
32B
0
1
2
3
0
1
2
3
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
2
0
0
0
0
0
0
0
0
3
1
1
1
1
1
1
1
1
数组
数组
128B
0
1
2
3
0
1
2
3
0
4
4
4
4/
0
0
0
0
1
5/
5
5
5
1
1
1
1
2
6/
6
6
6
2
2
2
2
3
7/
7
7
7
3
3
3
3
参考答案：
从程序来看，数组访问过程如下：
[0][0]、[0][0]、[0][1]、[1][0]、[0][2]、[2][0]、[0][3]、[3][0]
[1][0]、[0][1]、[1][1]、[1][1]、[1][2]、[2][1]、[1][3]、[3][1]
[2][0]、[0][2]、[2][1]、[1][2]、[2][2]、[2][2]、[2][3]、[3][2]
[3][0]、[0][3]、[3][1]、[1][3]、[3][2]、[2][3]、[3][3]、[3][3]
因为块大小为16B，每个数组元素有4个字节，所以4个数组元素占一个主存块，因此每次总是调入4个数组元素到的一行。
当数据区容量为32B时，L1中共有2行。
数组元素[0][i]、[2][i]、[0][i]、[2][i]（0～3）都映射到第0行，数组元素[1][i]、[3][i]、[1][i]、[3][i]（0～3）都映射到第1行。
因此，从上述访问过程来看，[0][0]所在的一个主存块（即存放[0][i]（0～3）四个数组元素）刚调入后，[0][0]所在主存块又把[0][0]替换掉了。
……
当数据区容量为128B时，L1中共有8行。
数组元素[0][i]、[1][i]、[2][i]、[3][i]、[0][i]、[1][i]、[2][i]、[3][i]（0～3）分别映射到第0、1、2、3、4、5、6、7行。
因此，不会发生数组元素的替换。
每次总是第一个数组元素不命中，后面三个数组元素都命中。
16.通过对方格中每个点设置相应的值就可以将方格图上相应的颜色。
以下三个程序段都可实现对一个8×8的方格中图上黄色的功能。
程序段A程序段B程序段C
假设的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，（）=4。
编译时变量i和j分配在寄存器中，数组按行优先方式存放在000008C0H开始的连续区域中，主存地址为32位。
要求：
（1）对三个程序段A、B、C中数组访问的时间局部性和空间局部性进行分析比较。
（2）画出主存中的数组元素和中行的对应关系图。
（3）计算三个程序段A、B、C中的写操作次数、写不命中次数和写缺失率。
参考答案：
（1）对于时间局部性来说：
程序段A、B和C中，都是每个数组元素只被访问一次，所以都没有时间局部性；
对于空间局部性来说：
程序段A访问顺序和存放顺序一致，所以，空间局部性好；
程序段B访问顺序和存放顺序不一致，所以，空间局部性不好；
程序段C虽然访问顺序和存放顺序一致，但同一个主存块有两次访问，所以空间局部性不好；
（2）的行数为5123216；数组首地址为00000C80H，因为00000C80H正好是主存第1100100B（100）块的起始地址。
所以数组从主存第100块开始存放，一个数组元素占4×416B，所以每2个数组元素占用一个主存块。
8×8的数组共占用32个主存块，正好是数据区大小的2倍。
主存中的数组元素与行的映射关系图如下：
（3）对于程序段A：
每两个数组元素（共涉及8次写操作）装入到一个行中，总是第一次访问时未命中，后面7次都命中，所以，总的写操作次数为64×4=256次，写不命中次数为256×1/8=32次，因而写缺失率为12.5%。
对于程序段B：
每两个数组元素（共涉及8次写操作）装入到一个行中，但总是只有一个数组元素（涉及4次写操作）在被淘汰之前被访问，并且总是第一次不命中，后面3次命中。
即写不命中次数为256×1/4=64次，因而写缺失率为25%。
对于程序段C：
第一个循环共64次访问，每次装入两个数组元素，第一次不命中，第二次命中；第二个循环，共访问64×3次，每两个数组元素（共涉及6次写操作）装入到一个行中，并且总是第一次不命中，后面5次命中。
所以总的写不命中次数为32+（3×64）×1/6=64次，因而总缺失率为25%。
17.假设某计算机的主存地址空间大小为64，采用字节编址方式。
其数据区容量为4，采用4路组相联映射方式、替换和回写（）策略，块大小为64B。
请问：
（1）主存地址字段如何划分？
要求说明每个字段的含义、位数和在主存地址中的位置。
（2）该的总容量有多少位？
（3）若初始为空，依次从0号地址单元顺序访问到4344号单元，重复按此序列共访问16次。
若命中时间为1个时钟周期，缺失损失为10个时钟周期，则访存的平均时间为多少时钟周期？
参考答案：
（1）的划分为：
4=212B=24组×22行/组×26字节/行，所以，组号（组索引）占4位。
主存地址划分为三个字段：
高16位为标志字段、中间4位为组号、最低6位为块内地址。
即主存空间划分为：
64=226B=216组群×24块/组群×26字节/块
（2）共有64行，每行中有16位标志、1位有效位、1位修改（）位、2位位，以及数据64B。
故总容量为64×（16+1+1+2+64×8）=34048位。
（3）因为每块为64B，访问的单元范围为0～4344，共4345个单元，4345/64=67.89，所以访问的是主存前68块（第0～67块），也即的访问过程是对前68块连续访问16次，总访存次数为16×4345=69520。
共有16组，每组4行，采用算法的替换情况如下图所示：
根据图中所示可知，第一次循环的每一块只有第一次未命中，其余都命中；以后15次循环中，有20块的第一字未命中，其余都命中。
所以命中率p为（69520–68–15×20）/69520=99.47%
平均访存时间为：
+（1–p）×
=1+10×（1–p）=1+0.0053×10=1.053个时钟周期
18.假定某处理器可通过软件对高速缓存设置不同的写策略，那么，在下列两种情况下，应分别设置成什么写策略？
为什么？
（1）处理器主要运行包含大量存储器写操作的数据访问密集型应用。
（2）处理器运行程序的性质与
（1）相同，但安全性要求高，不允许有任何数据不一致的情况发生。
参考答案：
（1）采用策略较好，可减少访存次数。
（2）采用策略较好，能保证数据的一致性。
19.已知1采用直接映射方式，共16行，块大小为1个字，缺失损失为8个时钟周期；2也采用直接映射方式，共4行，块大小为4个字，缺失损失为11个时钟周期。
假定开始时为空，采用字编址方式。
要求找出一个访问地址序列，使得2具有更低的缺失率，但总的缺失损失反而比1大。
参考答案：
假设1和2的缺失次数分别为x和y，根据题意，x和y必须满足以下条件：
11×y>8×x且x>y，显然，满足该条件的x和y有许多，例如，4，3、5，4等等。
对于以下的访问地址序列：
0，1，4，8，1缺失4次，而2缺失3次；
对于以下的访问地址序列：
0，2，4，8，12，1缺失5次，而2缺失4次；
对于以下的访问地址序列：
0，3，4，8，12，16，20，1缺失7次，而2缺失6次；
如此等等，可以找出很多。
20.提高关联度通常会降低缺失率，但并不总是这样。
请给出一个地址访问序列，使得采用替换算法的2-路组相联映射比具有同样大小的直接映射的缺失率更高。
参考答案：
2-路组相联的组数是直接映射的行数的一半，所以，可以找到一个地址序列A、B、C，使得：
A映射到某一个行，B和C同时映射到另一个行，并且A、B、C映射到同一个组。
这样，如果访存的地址序列为A、B、C、A、B、C、A、B、C…，则对于直接映射，其命中情况为：
…命中率可达33.3%。
对于组相联，因为A、B、C映射到同一个组，每组只有2行，采用替换算法，所以，每个地址处的数据刚调出就又被访问到，每次都是，命中率为0。
例如：
假定直接映射为4行×1字/行，同样大小的2-路组相联为2组×2行/组×1字/行
当访问序列为：
0、2、4、0、2、4、0、2、4、…（局部块大小为3）时，则出现上述情况。
当访问的局部块大于组的大小时，可能会发生“颠簸”现象：
刚被替换出去的数据又被访问，导致缺失率为100%！
21.假定有三个处理器，分别带有以下不同的：
1：
采用直接映射方式，块大小为1个字，指令和数据的缺失率分别为4%和6%；
2：
采用直接映射方式，块大小为4个字，指令和数据的缺失率分别为2%和4%；
3：
采用2-路组相联映射方式，块大小为4个字，指令和数据的缺失率分别为2%和3%。
在这些处理器上运行相同的程序，该程序的为2.0，其中有一半是访存指令。
若缺失损失为（块大小+6）个时钟周期，处理器1和处理器2的时钟周期都为420，带有3的处理器3的时钟周期为450。
请问：
哪个处理器因缺失而引起的额外开销最大？
哪个处理器执行速度最快？
参考答案：
假设所运行的程序共执行N条指令，每条访存指令仅读写一次内存数据，则在该程序执行过程中各处理器因缺失而引起的额外开销和执行时间计算如下。
对于处理器1：
额外开销为：
N×（4%+6%×50%）×（1+6）=0.49N个时钟周期
执行程序所需时间为：
（N×2.0+0.49N）×420=1045.8N
对于处理器2：
额外开销为：
N×（24%×50%）×（4+6）=0.40N个时钟周期
执行程序所需时间为：
（N×2.0+0.40N）×4201008N
对于处理器3：
额外开销为：
N×（23%×50%）×（4+6）=0.35N个时钟周期
执行程序所需时间为：
（N×2.0+0.35N）×4501057.5N
由此可见，处理器1的缺失引起的额外开销最大，处理器2的执行速度最快。
22.假定某处理器带有一个数
升级会员 