《计算机组织与系统结构第四章习题答案.docx》由会员分享，可在线阅读，更多相关《计算机组织与系统结构第四章习题答案.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 4 章 习 题 答 案3. 某机主存空间大小为64KB，按字节编址。要求：1假设用1K4位的SRAM芯片构成该主存储器，须要多少个芯片？2主存地址共多少位？几位用于选片？几位用于片内选址？3画出该存储器的逻辑框图。参考答案：164KB / 1K4位 = 642 = 128片。2因为是按字节编址，所以主存地址共16位，6位选片，10位片内选址。3明显，位方向上扩展了2倍，字方向扩展了64倍。以下图中片选信号CS为高电平有效。4. 用64K1位的DRAM芯片构成256K8位的存储器。要求：1 计算所需芯片数，并画出该存储器的逻辑框图。2 假设采纳异步刷新方式，每单元刷新间隔不超过2ms，那么产
2、生刷新信号的间隔是多少时间？假设采纳集中刷新方式，那么存储器刷新一遍最少用多少读写周期？参考答案：1256KB / 64K1位 = 48 = 32片。存储器逻辑框图见下页图中片选信号CS为高电平有效。2因为每个单元的刷新间隔为2ms，所以，采纳异步刷新时，在2ms内每行必需被刷新一次，且仅被刷新一次。因为DRAM芯片存储阵列为64K=256256，所以一共有256行。因此，存储器限制器必需每隔产生一次刷新信号。采纳集中刷新方式时，整个存储器刷新一遍须要256个存储读写周期，在这个过程中，存储器不能进展读写操作。 5. 用8K8位的EPROM芯片组成32K16位的只读存储器，试问：1数据存放器最
3、少应有多少位？ 2 地址存放器最少应有多少位？3 共需多少个EPROM芯片？ 4 画出该只读存储器的逻辑框图。参考答案：1数据存放器最少有16位。 2地址存放器最少有：15位假设按16位的字编址；16位假设按字节编址。3共须要 32K16位 / 8K8位= 42 = 8片。4该只读存储器的逻辑框图如下假定按字编址，图中片选信号CS为高电平有效。 6. 某计算机中已配有0000H7FFFH的ROM区域，现在再用8K4位的RAM芯片形成32K8位的存储区域，CPU地址总线为A0-A15，数据总线为D0-D7，限制信号为R/W#读/写, MREQ#访存。要求说明地址译码方案，并画出ROM芯片, RA
4、M芯片及CPU之间的连接图。假定上述其他条件不变，只是CPU地址线改为24根，地址范围000000H007FFFH为ROM区，剩下的全部地址空间都用8K4位的RAM芯片配置，那么须要多少个这样的RAM芯片？参考答案：CPU地址线共16位，故存储器地址空间为0000HFFFFH，其中，8000HFFFFH为RAM区，共215=32K个单元，其空间大小为32KB，故需8K4位的芯片数为32KB/8K4位= 42 = 8片。因为ROM区在0000H7FFFH，RAM区在8000HFFFFH，所以可通过最高位地址A15来区分，当A15为0时选中ROM芯片；为1时选中RAM芯片，此时，依据A14和A13
5、进展译码，得到4个译码信号，分别用于4组字扩展芯片的片选信号。图略，可参照图4.15假设CPU地址线为24位，ROM区为000000H007FFFH，那么ROM区大小为32KB，总大小为16MB=214KB=51232KB，所以RAM区大小为51132KB，共需运用RAM芯片数为51132KB/8K4位=51142个芯片。7. 假定一个存储器系统支持4体穿插存取，某程序执行过程中访问地址序列为3, 9, 17, 2, 51, 37, 13, 4, 8, 41, 67, 10，那么哪些地址访问会发生体冲突？参考答案：对于4体穿插访问的存储系统，每个存储模块的地址分布为：Bank0: 0, 4,
6、8, 12, 16 Bank1: 1, 5, 9, 13, 17 37 41Bank2: 2, 6, 10, 14, 18 Bank3: 3, 7, 11, 15, 195167假如给定的访存地址在相邻的4次访问中出现在同一个Bank内，就会发生访存冲突。所以，17和9, 37和17, 13和37, 8和4发生冲突。8. 现代计算机中，SRAM一般用于实现快速小容量的cache，而DRAM用于实现慢速大容量的主存。以前超级计算机通常不供应cache，而是用SRAM来实现主存如，Cray巨型机，请问：假如不考虑本钱，你还这样设计高性能计算机吗？为什么？参考答案：不这样做的理由主要有以下两个方面：
7、 主存越大越好，主存大，缺页率降低，因而削减了访问磁盘所需的时间。明显用DRAM芯片比用SRAM芯片构成的主存容量大的多。 程序访问的局部性特点使得cache的命中率很高，因而，即使主存没有用快速的SRAM芯片而是用DRAM芯片，也不会影响到访问速度。9. 分别给出具有以下要求的程序或程序段的例如： 1对于数据的访问，几乎没有时间局部性和空间局部性。2对于数据的访问，有很好的时间局部性，但几乎没有空间局部性。3对于数据的访问，有很好的空间局部性，但几乎没有时间局部性。4对于数据的访问，空间局部性和时间局部性都好。参考答案略： 可以给出很多类似的例如。例如，对于按行优先存放在内存的多维数组，假如
8、按列优先访问数组元素，那么空间局部性就差，假如在一个循环体中某个数组元素只被访问一次，那么时间局部性就差。10. 假定某机主存空间大小1GB，按字节编址。cache的数据区即不包括标记, 有效位等存储区有64KB，块大小为128字节，采纳干脆映射和全写write-through方式。请问：1主存地址如何划分？要求说明每个字段的含义, 位数和在主存地址中的位置。2cache的总容量为多少位？ 参考答案：1主存空间大小为1GB，按字节编址，说明主存地址为30位。cache共有64KB/128B=512行，因此，行索引行号为9位；块大小128字节，说明块内地址为7位。因此，30位主存地址中，高14位
9、为标记Tag；中间9位为行索引；低7位为块内地址。2因为采纳干脆映射，所以cache中无需替换算法所需限制位，全写方式下也无需修改dirty位，而标记位和有效位总是必需有的，所以，cache总容量为512(1288+14+1)K位。11. 假定某计算机的cache共16行，开场为空，块大小为1个字，采纳干脆映射方式。CPU执行某程序时，依次访问以下地址序列：2，3，11，16，21，13，64，48，19，11，3，22，4，27，6和11。要求：1说明每次访问是命中还是缺失，试计算访问上述地址序列的命中率。2假设cache数据区容量不变，而块大小改为4个字，那么上述地址序列的命中状况又如何？
10、参考答案（1） cache采纳干脆映射方式，其数据区容量为16行1字/行=16字；主存被划分成1字/块，所以，主存块号 = 字号。因此，映射公式为：cache行号 = 主存块号 mod 16 = 字号 mod 16。开场cache为空，所以第一次都是miss，以下是映射关系字号-cache行号和命中状况。2-2: miss，3-3: miss，11-11: miss，16-0: miss, 21-5: miss，13-13: miss，64-0: miss, replace，48-0: miss, replace，19-3: miss, replace，11-11: hit, 3-3: mis
11、s, replace，22-6: miss，4-4: miss，27-11: miss, replace，6-6: miss, replace，11-11: miss, replace。 只有一次命中！2cache采纳干脆映射方式，数据区容量不变，为16个字，每块大小为4个字，所以，cache共有4行；主存被划分为4个字/块，所以，主存块号 = 字号/4。因此，映射公式为：cache行号 = 主存块号 mod 4 = 字号/4 mod 4。以下是映射关系字号-主存块号-cache行号和命中状况。2-0-0: miss，3-0-0: hit，11-2-2: miss，16-4-0: miss,
12、replace，21-5-1, 13-3-3: miss，64-16-0, 48-12-0, 19-4-0: miss, replace，11-2-2: hit，3-0-0: miss, replace，22-5-1: hit，4-1-1: miss, replace，27-6-2: miss, replace，6-1-1: hit，11-2-2: miss, replace。 命中4次。 由此可见，块变大后，能有效利用访问的空间局部性，从而使命中率提高！12. 假定数组元素在主存按从左到右的下标依次存放。试变更以下函数中循环的依次，使得其数组元素的访问及排列依次一样，并说明为什么修改后的程序
13、比原来的程序执行时间短。int sum_array ( int aNNN)int i, j, k, sum=0;for (i=0; i N; i+) for (j=0; j N; j+) for (k=0; k N; k+) sum+=akij;return sum;参考答案：int sum_array ( int aNNN)int i, j, k, sum=0;for (k=0; k N; k+) for (i=0; i N; i+) for (j=0; j N; j+) sum+=akij;return sum;修改后程序的数组元素的访问及排列依次一样，使得空间局部性比原程序好，故执行时间
14、更短。13. 分析比拟以下三个函数的空间局部性，并指出哪个最好，哪个最差？ # define N 1000typedef struct int vel3;int acc3; point;point pN;void clear3(point *p, int n)int i, j;for (j=0; j3; j+) for (i=0; in; i+)pi.velj = 0;for (i=0; in; i+)pi.accj = 0;# define N 1000typedef struct int vel3;int acc3; point;point pN;void clear1(point *p,
15、 int n)int i, j;for (i = 0; i n; i+) for (j = 0; j3; j+) pi.velj = 0;for (j = 0; i3; j+) pi.accj = 0;# define N 1000typedef struct int vel3;int acc3; point;point pN;void clear2(point *p, int n)int i, j;for (i=0; in; i+) for (j=0; j3; j+) pi.velj = 0; pi.accj = 0;参考答案： 对于函数clear1，其数组访问依次及在内存的存放依次完全一样
16、，因此，空间局部性最好。对于函数clear2，其数组访问依次在每个数组元素内跳越式访问，相邻两次访问的单元最大相差3个int型变量假定sizeof(int)=4，那么相当于12B，因此空间局部性比clear1差。假设主存块大小比12B小的话，那么大大影响命中率。对于函数clear3，其数组访问依次及在内存的存放依次不一样，相邻两次访问的单元都相差6个int型变量假定sizeof(int)=4，那么相当于24B因此，空间局部性比clear2还差。假设主存块大小比24B小的话，那么大大影响命中率。14. 以下是计算两个向量点积的程序段：float dotproduct (float x8, flo
17、at y8)float sum = 0.0;int i,;for (i = 0; i 8; i+) sum += xi * yi;return sum;要求：1试分析该段代码中数组x和y的时间局部性和空间局部性，并推断命中率的上下。2假定该段程序运行的计算机的数据cache采纳干脆映射方式，其数据区容量为32字节，每个主存块大小为16字节。假定编译程序将变量sum和i安排给存放器，数组x存放在00000040H开场的32字节的连续存储区中，数组y紧跟在x后进展存放。试计算该程序数据访问的命中率，要求说明每次访问的cache命中状况。3将上述2中的数据cache改用2-路组相联映射方式，块大小改
18、为8字节，其他条件不变，那么该程序数据访问的命中率是多少？4在上述2中条件不变的状况下，假如将数组x定义为float12，那么数据访问的命中率是多少？参考答案：1数组x和y都按存放依次访问，不考虑映射的状况下，空间局部性都较好，但都只被访问一次，故没有时间局部性。命中率的上下及块大小, 映射方式等都有关，所以，无法推断命中率的上下。2cache采纳干脆映射方式，块大小为16字节，数据区大小为32字节，故cache共有2行。数组x的8个元素共32B分别存放在主存40H开场的32个单元中，共有2个主存块，其中x0 x3在第4块，x4 x7在第5块中；数组y的8个元素共32B分别在主存第6块和第7块
19、中。所以，x0 x3和y0 y3都映射到cache第0行；x4 x7和y4 y7都映射到cache第1行。cache第0-3次循环第4-7次循环第0行x0-3，y0-3第1行x4-7，y4-7每调入一块，装入4个数组元素，因为xi和yi总是映射到同一行，相互淘汰对方，故每次都不命中，命中率为0.3改用2路组相联，块大小为8B，那么cache共有4行，每组两行，共两组。数组x有4个主存块，x0 x1, x2 x3，x4 x5，x6 x7分别在第811块中；数组y有4个主存块，y0 y1, y2 y3，y4 y5，y6 y7分别在第1215块中；cache第0行第1行第0组x0-1,x4-5y0-
20、1,y4-5第1组x2-3,x6-7y2-3,y6-7每调入一块，装入两个数组元素，第二个数组元素的访问总是命中，故命中率为50%。4假设2中条件不变，数组x定义了12个元素，共有48B，使得y从第7块开场，因而，xi和yi就不会映射到同一个cache行中，即：x0 x3在第4块，x4 x7在第5块，x8 x11在第6块中，y0 y3在第7块，y4 x7在第8块。cache第0-3次循环第4-7次循环第0行x0-3y4-7第1行y0-3x4-7每调入一块，装入4个数组元素，第一个元素不命中，后面3个总命中，故命中率为75%。15. 以下是对矩阵进展转置的程序段：typedef int arra
21、y44;void transpose(array dst,array src)inti, j; for (i = 0; i 4; i+)for (j = 0; j 4; j+)dstji = srcij;假设该段程序运行的计算机中sizeof(int)=4，且只有一级cache，其中L1 data cache的数据区大小为32B，采纳干脆映射, 写回方式，块大小为16B，初始为空。数组dst从地址0000C000H开场存放，数组src从地址0000C040H开场存放。填写下表，说明数组元素srcrowcol和dstrowcol映射到cache的哪一行，其访问是命中hit还是失效miss。假设L
22、1 data cache的数据区容量改为128B时，重新填写表中内容。src数组dst数组32Bcol=0col=1col=2col=3col=0col=1col=2col=3row=00/miss0/miss0/hit0/miss0/miss0/miss0/miss0/missrow=11/miss1/hit1/miss1/hit1/miss1/miss1/miss1/missrow=20/miss0/miss0/hit0/miss0/miss0/miss0/miss0/missrow=31/miss1/hit1/miss1/hit1/miss1/miss1/miss1/misssrc数组d
23、st数组128Bcol=0col=1col=2col=3col=0col=1col=2col=3row=04/miss4/hit4/hit4/ hit0/miss0/hit 0/hit 0/hit row=15/ miss5/hit5/hit5/hit1/miss1/hit1/hit1/hitrow=26/ miss6/hit6/hit6/hit2/miss2/hit2/hit2/hitrow=37/ miss7/hit7/hit7/hit3/miss3/hit3/hit3/hit参考答案：从程序来看，数组访问过程如下：src0 0, dst0 0, src0 1, dst1 0, src0
24、2, dst2 0, src0 3, dst3 0src1 0, dst0 1, src1 1, dst1 1, src1 2, dst2 1, src1 3, dst3 1src2 0, dst0 2, src2 1, dst1 2, src2 2, dst2 2, src2 3, dst3 2src3 0, dst0 3, src3 1, dst1 3, src3 2, dst2 3, src3 3, dst3 3因为块大小为16B，每个数组元素有4个字节，所以4个数组元素占一个主存块，因此每次总是调入4个数组元素到cache的一行。当数据区容量为32B时，L1 data cache中共有
25、2行。数组元素dst0i, dst2i , src0i, src2i (i=03)都映射到cache第0行，数组元素dst1i, dst3i , src1i, src3i (i=03)都映射到cache第1行。因此，从上述访问过程来看，src00所在的一个主存块即存放src0i (i=03)四个数组元素刚调入cache后，dst00所在主存块又把src00替换掉了。当数据区容量为128B时，L1 data cache中共有8行。数组元素dst0i, dst1i , dst2i, dst3i, src0i, src1i, src2i, src3i (i=03) 分别映射到cache第0, 1,
26、2, 3, 4, 5, 6, 7行。因此，不会发生数组元素的替换。每次总是第一个数组元素不命中，后面三个数组元素都命中。16. 通过对方格中每个点设置相应的CMYK值就可以将方格图上相应的颜色。以下三个程序段都可实现对一个88的方格中图上黄色的功能。struct pt_color int c;int m;int y;int k;struct pt_color square88;int i, j;for (i = 0; i 8; i+) for (j = 0; j 8; j+) squareij.c = 0;squareij.m = 0;squareij.y = 1;squareij.k = 0
27、;struct pt_color int c;int m;int y;int k;struct pt_color quare88;int i, j;for (i = 0; i 8; i+) for (j = 0; j 8; j+) square j i.c = 0;square j i.m = 0;square j i.y = 1;square j i.k = 0;struct pt_color int c;int m;int y;int k;struct pt_color square88;int i, j;for (i = 0; i 8; i+)for (j = 0; j 8; j+)sq
28、uareij.y = 1;for (i = 0; i 8; i+)for (j = 0; j 8x 且 x y，明显，满意该条件的x和y有很多，例如，x=4，y=3, x=5，y=4等等。对于以下的访问地址序列：0，1，4，8，cache1缺失4次，而cache2缺失3次；对于以下的访问地址序列：0，2，4，8，12，cache1缺失5次，而cache2缺失4次；对于以下的访问地址序列：0，3，4，8，12，16，20，cache1缺失7次，而cache2缺失6次；如此等等，可以找出很多。20. 提高关联度通常会降低缺失率，但并不总是这样。请给出一个地址访问序列，使得采纳LRU替换算法的2-路
29、组相联映射cache比具有同样大小的干脆映射cache的缺失率更高。参考答案：2-路组相联cache的组数是干脆映射cache的行数的一半，所以，可以找到一个地址序列A, B, C，使得：A映射到某一个cache行，B和C同时映射到另一个cache行，并且A, B, C映射到同一个cache组。这样，假如访存的地址序列为A, B, C, A, B, C, A, B, C ，那么对于干脆映射cache，其命中状况为：miss/miss/miss /hit/miss/miss /hit/miss/miss/ 命中率可达33.3%。对于组相联cache，因为A, B, C映射到同一个组，每组只有2行
30、，采纳LRU替换算法，所以，每个地址处的数据刚调出cache就又被访问到，每次都是miss，命中率为0。例如：假定干脆映射cache为4行1字/行，同样大小的2-路组相联cache为2组2行/组1字/行当访问序列为：0, 2, 4, 0, 2, 4, 0, 2, 4, 局部块大小为3时，那么出现上述状况。当访问的局部块大于组的大小时，可能会发生“颠簸现象：刚被替换出去的数据又被访问，导致缺失率为100%！21. 假定有三个处理器，分别带有以下不同的cache：cache1：采纳干脆映射方式，块大小为1个字，指令和数据的缺失率分别为4%和6%； cache2：采纳干脆映射方式，块大小为4个字，指
31、令和数据的缺失率分别为2%和4%；cache3：采纳2-路组相联映射方式，块大小为4个字，指令和数据的缺失率分别为2%和3%。在这些处理器上运行一样的程序，其中有一半是访存指令。假设缺失损失为块大小+6个时钟周期，处理器1和处理器2的时钟周期都为420ps，带有cache3的处理器3的时钟周期为450ps。请问：哪个处理器因cache缺失而引起的额外开销最大？哪个处理器执行速度最快？参考答案：假设所运行的程序共执行N条指令，每条访存指令仅读写一次内存数据，那么在该程序执行过程中各处理器因cache缺失而引起的额外开销和执行时间计算如下。对于处理器1：额外开销为：N(4% + 6%50%)(1+
32、6) = 0.49 N个时钟周期执行程序所需时间为：(N +0.49N)420ps = 1045.8N ps对于处理器2：额外开销为：N(2%+4%50%)(4+6) = 个时钟周期执行程序所需时间为：(N+0.40N)420ps=1008N ps对于处理器3：额外开销为：N(2%+3%50%)(4+6) = 个时钟周期执行程序所需时间为：(N+0.35N)450ps=N ps由此可见，处理器1的cache缺失引起的额外开销最大，处理器2的执行速度最快。22. 假定某处理器带有一个数据区容量为256B的cache，其块大小为32B。以下C语言程序段运行在该处理器上，sizeof(int) =
33、4，编译器将变量i, j, c, s都安排在通用存放器中，因此，只要考虑数组元素的访存状况。假设cache采纳干脆映射方式，那么当s=64和s=63时，缺失率分别为多少？假设cache采纳2-路组相联映射方式，那么当s=64和s=63时，缺失率又分别为多少？ int i, j, c, s, a128; for ( i = 0; i 10000; i+ )for ( j = 0; j 128; j=j+s ) c = aj;参考答案：块大小为32B，cache容量为256B = 8行8字/行 4B/字，仅考虑数组访问状况。1) 干脆映射，s=64: 访存依次为a0, a64 , a0, a64, , 共循环10000次。这两个元素被映射到同一个cache行中，每次都会发生冲突，因此缺失率为100%。2) 干脆映射，s=63: 访存依次为a0, a63, a126, a0, a63, a126, 共循环10000次。这三