计算机系统结构 习题课及答案全套ppt课件.ppt

习题课,目录,1计算机系统结构的基本概念,2指令系统,3存储系统,返回总目录,4输入输出系统,5标量处理机,7互连网络,基本要求：）计算机系统结构的基本概念，定量原理，指令的格式设计，CISC与RISC，虚拟存储页面替换算法，Cache映象，通道流量分析，数据相关，线性与非线性流水线技术及性能分析，互连网络基本概念；学习重点：）定量原理，指令格式设计，RISC，页面替换算法，Cache映象，流水线性能分析；,1计算机系统结构的基本概念,1.1名词解释,返回目录,1. 计算机体系结构的定义：程序员所看到的计算机的属性，即概念性结构与功能特性。 Amdahl提出的体系结构：是指传统机器级的体系结构。即一般所说的机器语言程序员所看到的传统机器级所具有的属性。 2. 透明性 在计算机技术中，对这种本来是存在的 事物或属性，但从某种角度看又好象不存在。,大概率事件优先原则：即对于大概率事件（最常见事件），赋予它优先的处理权和资源使用权，以获得全局的最优结果。Amdahl定律：加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中所占的重要性。程序的局部性原理：程序在执行时所访问地址的分布不是随机的，而是相对地簇聚；这种簇聚包括指令和数据两部分。程序局部性包括程序的时间局部性和空间局部性。时间局部性：程序即将用到的信息很可能就是目前正在使用的信息空间局部性：程序即将用到的信息很可能与目前正在使用的信息相邻或临近。,1计算机系统结构的基本概念,1.1名词解释,系统加速比：系统改进前与改进后总执行时间之比CPI：指令周期数（Cycles of Instruction)并行性：在同一时刻或同一时间间隔内完成两种或两种以上的性质相同或不同的工作。翻译：先把N1级程序全部变换成N级程序之后，再去执行N级程序，在执行过程中，N1级程序不再被访问（基于层次结构）解释：每当一条N1级指令被译码后，就直接去执行一串等效的N级指令，然后再去取下一条N1级指令，依此重复进行。,1计算机系统结构的基本概念,1.1名词解释,例：设某程序中FP操作占20%，其平均CPI=4.0, FPSQR操作的比例占4%，其平均CPI=20.0, 其它指令平均CPI=1.20，现采用两种方法进行优化: a. 将FP操作的CPI减为2;b. 将FPSQR操作的CPI减少为12;问1：哪一种方法更优?问2：若同时采用a、b方法，系统的加速比为多少？,1计算机系统结构的基本概念,1.2,问1解：比较2方案的CPI即可 CPIa =（1-20%-4%）CPI其他+（20%CPIFP ） +（4%CPIFPSQR） = 76%1.20 + 20% 2+ 4% 20 =2.11CPIb =（1-20%-4%）CPI其他+（20%CPIFP ） +（4%CPIFPSQR） = 76% 1.20 + 20% 4 +4% 12 =2.3 所以，采用方法a更优。,1计算机系统结构的基本概念,1.2,问2解： 加速比：,1计算机系统结构的基本概念,1.2,例：假设我们考虑条件分支指令的两种不同设计方法如下：,(1) CPUA：通过比较指令设置条件码，然后测试条件码进行分支 CPUB：在分支指令中包括比较过程,在两种CPU中，条件分支指令都占用2个时钟周期而所有其它指令占用1个时钟周期，对于CPUA，执行的指令中分支指令占20%；由于每个分支指令之前都需要有比较指令，因此比较指令也占20%。由于CPUB在分支时需要比较，因此假设它的时钟周期时间是CPUA的1.25倍。问1：哪一个CPU更快？,1计算机系统结构的基本概念,1.3,我们不考虑所有系统问题，所以可用CPU性能公式。占用2个时钟周期的分支指令占总指令的20%，剩下的指令占用1个时钟周期。所以 CPIA = 20% 2 + 80% 1 = 1.2则CPU性能为： 总CPU时间A = ICA 1.2 时钟周期A,解1：,1计算机系统结构的基本概念,1.3,根据假设，有： 时钟周期B = 1.25 时钟周期A在CPUB中没有独立的比较指令，所以CPUB的程序量为CPUA的80%，分支指令的比例为： 20%/80% = 25%这些分支指令占用2个时钟周期，而剩下的75%的指令占用1个时钟周期，因此： CPIB = 0.25 2 + 0.75 1 = 1.25因为CPUB不执行比较，故： ICB = 0.8 ICA,解1：,1计算机系统结构的基本概念,1.3,因此CPUB性能为： 总CPU时间B = ICB CPIB 时钟周期B = 0.8 ICA 1.25 (1.25 时钟周期A) = 1.25 ICA 时钟周期A在这些假设之下，尽管CPUB执行指令条数较少，CPUA因为有着更短的时钟周期，所以比CPUB快。,解1：,1计算机系统结构的基本概念,1.3,例：我们分析一个用于Web服务器系统的处理器的性能。假定采用某增强方式使新的CPU处理Web服务器应用程序的运行速度是原来处理器中的10倍，同时假定此CPU有40%的时间用于计算，另外60%的时间用于I/O操作。那么增强性能后总的加速比是多少？ 解：增强比例 = 0.4 增强加速比 = 10,1计算机系统结构的基本概念,1.4,例：设某计算机系统执行程序中，可向量化部分最大可达70%。一种实现方法是采用陈列多处理机即硬件方式实现，使60%的向量化指令执行速度加快到原来的10倍，另一种方法是采用优化编译系统的方法实现，使向量化程序可达70%，且速度可增加3倍。请比较这两种方案哪种更优。解：通过计算加速比知，硬件方案较优！,1计算机系统结构的基本概念,1.5,Assume a simple load/store machine with the following instruction frequency:,conditional branches currently use simple test against 0Should we add complex comparison/branch combination (BEQ Rn,Rm,LOC orBNE Rn,Rm,LOC) -25% of branches can use the complex scheme and save(节省了） the preceding ALU instruction -The CPU cycle time(CCT) of the machine has to be 10% longer -Will this increase CPU performance?,1计算机系统结构的基本概念,1.6,1计算机系统结构的基本概念,1.6,使用40MHz时钟速率的处理机执行一个测试程序，它的主要指令类型所执行的指令数及所需的时钟周期数如下，试计算执行此程序的有效CPI，MIPS速率及总的CPU时间。（p33习题1.19),1计算机系统结构的基本概念,1.7 p33习题1.19,总时钟周期数=45000*1+32000*2+15000*2+8000*2=155000总指令数=45000+32000+15000+8000=100000CPI=总时钟周期数/总指令数=1.55总CPU执行时间=155000/40* 10-6=0.003875sMIPS=总指令数*10-6/总时间=0.1/0.003875=25.8,1计算机系统结构的基本概念,1.7 p33习题1.19,1计算机系统结构的基本概念,1.8 p33习题1.20,某工作站采用时钟频率为15MHz，处理速率为10MIPS的处理机来执行一个已知混合程序。假定每次存储器存取为1周期延迟，试问：（1）此计算机的有效CPI是多少？（2）时钟提高到30MHz，但存储器子系统速率不变。这样，每次存储器存取需要2个时钟周期。如果30%指令每条只需要1次存储存取，而另外5%每条需要2次存储存取，还假定已知混合程序的指令数不变，并与原工作站兼容，试求改进后的处理机性能。,1计算机系统结构的基本概念,1.8 p33习题1.20,解：（1）设该程序执行时间为t，则CPI=总时钟周期数/总指令数=(t*15M)/(t*10M) = 1.5（2） 公式： CPUtime=IC*CPI*CCT 即有： CPUtime=指令数指令周期数cpu周期时间,1计算机系统结构的基本概念,1.8 p33习题1.20,1计算机系统结构的基本概念,1.9 p34习题1.21,解：,2指令系统,2.1名词解释,CISC:复杂指令集计算机（Complex Instruction Set Computer）。强化指令功能，设置一些功能复杂的指令，把一些原来由软件实现的、常用的功能改用硬件的指令系统来实现，基于这种指令集结构而设计实现的计算机系统称为CISC计算机。RISC:精简指令集计算机（Reduced Instruction Set Computer）。尽量简化指令功能，只保留那些功能简单，能在一个周期内执行完成的指令，较复杂的功能用一段子程序来实现，这种计算机系统称为RISC计算机。,返回目录,2指令系统,2.2简答,RISC的关键技术有哪些？延时转移技术指令取消技术重叠寄存器窗口技术指令流调整技术硬件为主，固件为辅,2指令系统,2.3,例: 某计算机有10条指令，它们的使用频率分别为 0.30, 0.20, 0.16, 0.09, 0.08, 0.07, 0.04, 0.03, 0.02, 0.01(1) 用霍夫曼编码对它们的操作码进行编码，并计算平均代码长度。(2) 用扩展霍夫曼编码法对操作码进行编码，限两种操作码长度，并计算平均代码长度。,2指令系统,2.3,答：(1) 霍夫曼树如下：,2指令系统,2.3,霍夫曼编码的结果以及各编码的长度如下所示：0.30 0.20 0.16 0.09 0.08 0.07 0.04 0.03 0.02 0.0111 01 101 001 1001 1000 0001 00001 000001 000002 2 3 3 4 4 4 5 6 6平均代码长度为(0.30+0.20)2 + (0.16+0.09)3 + (0.08+0.07+0.04)4 + 0.035 + (0.02+0.01)6 = 1 + 0.75 + 0.76 + 0.15 + 0.18 = 2.84,2指令系统,2.3,(2) 用扩展霍夫曼编码法对操作码进行编码，限两种操作码长度，采用长度为2和长度为4两种编码： 0.30 0.20 0.16 0.09 0.08 0.07 0.04 0.03 0.02 0.01 00 01 1000 1001 1010 1011 1100 1101 1110 1111平均代码长度为 (0.30+0.20)2 + (1-0.30-0.20)4 = 3.0,2指令系统,2.4P127页习题2.13,解：,2指令系统,2.4P127页习题2.13,解：,2指令系统,2.4P127页习题2.13,解：,2指令系统,2.5P127页习题2.14,2指令系统,2.5P127页习题2.14,解:（1）应采用Huffman编码，构造Huffman树如下：,2指令系统,2.5P127页习题2.14,2指令系统,2.5P127页习题2.14,2指令系统,2.5P127页习题2.14,2指令系统,2.6P128页习题2.15,2指令系统,2.6P128页习题2.15,解:（1）首先，我们可以根据指令地址的数量来决定各种指令在指令空间上的分布：,2指令系统,2.6P128页习题2.15,2指令系统,2.6P128页习题2.15,2指令系统,2.7P129页习题2.20,解：,START: MOVE AS, R1 MOVE NUM, R2LOOP: MOVE (R1), AD-AS(R1) INC R1 DEC R2 BGT LOOP HALTNUM: N,HALT指令共取100次，但前99次都被取消。,2指令系统,2.7P129页习题2.20,解：(1),START: MOVE AS, R1 MOVE NUM, R2 MOVE (R1), AD-AS(R1)LOOP: INC R1 DEC R2 BGT LOOP _ _ MOVE (R1), AD-AS(R1) _ _ HALTNUM: N,MOVE指令共取100次，但前99次都被正常执行，只有最后1次被取消。,2指令系统,2.7P129页习题2.20,解：(2),因为采用指令取消技术前，取消指令次数为99次，而在采用指令取消技术后，取消指令次数为1次，所以节省的指令周期数为：99198,2指令系统,2.7P129页习题2.20,START: MOVE AS, R1 MOVE NUM, R2 MOVE (R1), AD-AS(R1) INC R1LOOP: DEC R2 BGT LOOP _ _ _ MOVE (R1), AD-AS(R1) _ _ _ INC R1 _ _ _ HALTNUM: N,解：(3),3存储系统,3.1名词解释,返回目录,存储系统:由多个不同性能的存储器组成的有机的一体化的存储体。LRU:近期最少使用算法(Least Recently Used Algorithm)。一种页面替换算法，这种算法选择近期最少访问的页面作为被替换的页面。LFU：最久没用使用的算法LFU（Least Frequently Used Algorithm）。一种页面替换算法，这种算法把近期最久没有访问过的页面作为被替换的页面。,3存储系统,3.1名词解释,“颠簸”现象(thrashing)：下次就要使用的页面本次被替换出去，这种现象称为。全相联映象：主存中的任一块可以被放置到Cache中的任意一个位置。直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。 组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。,3存储系统,3.1名词解释,写直达法：执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。写回法：执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。按写分配(写时取)：写失效时，先把所写单元所在的块调入Cache，再行写入.不按写分配(绕写法)：写失效时，直接写入下一级存储器而不调块。,3存储系统,3.2简答,常用的页面替换算法有哪些？随机算法RAND算法(random Algorithm)FIFO算法（first in first out Algorithm)近期最少使用LRU算法(Least Recently Used Algorithm)最久没用使用的算法LFU（Least Frequently Used Algorithm）最优替换算法，即OPT算法（Optional Replacement algorithm）,3存储系统,3.2简答,虚拟存储器中，影响主存命中率的主要因素有？程序在执行过程中的页地址流的分布情况；所采用的页面替换算法；页面的大小主存容量页面调度算法,3存储系统,3.2简答,简要介绍Cache与主存的三种地址映象方式，并举例加以说明？(略),3存储系统,3.3P205页习题3.14,解：(1),3存储系统,3.3P205页习题3.14,解：(1),3存储系统,3.3P205页习题3.14,解：(1),3存储系统,3.3P205页习题3.14,解：(2),FIFO页面替换算法的页命中率：3/12LFU页面替换算法的页命中率：5/12OPT页面替换算法的页命中率：6/12,3存储系统,3.4P205页习题3.15,解：(1),可能的最高页命中率出现在:页地址流中每一种都可以单独占一个页面时，因为对于各种页地址流，都是第一次“调入”，其后各次都是“命中”。在此例中，需5个页面。因此：可能的最高页命中率（页地址流个数页地址流种数）/页地址流个数（125）/12= 7/12,3存储系统,解：(1),或通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“”表示命中。,Hmax=7/1258.3%,3.4P205页习题3.15,3存储系统,解：(2),至少分配4个页面才能获得最高的命中率7/12 .,3.4P205页习题3.15,3存储系统,解：(3),访问存储单元的命中率命中次数/总访问次数(121024-5)/(121024)12283/1228899.96% 分析：页“不命中”时，仅第1次不命中，其它1023次都是命中的。而在页“命中”时，1024次都是命中的。所以总访问次数为12*1024，不命中次数为5,3.4P205页习题3.15,3存储系统,3.4P205页习题3.19,解：（1）主存地址,6 5 4 3 0,5 4 3 0,解：（2）缓存地址,3存储系统,3.4P205页习题3.19,解：（3）主存与Cache的块映象关系,Cache,主存,3存储系统,3.4P205页习题3.19,解：（3）主存与Cache的块映象关系,3存储系统,3.4P205页习题3.19,解：（4）通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。,3存储系统,3.4P205页习题3.19,解：（5）采用LFU替换算法，命中率为4/12,3存储系统,3.4P205页习题3.19,解：（6）采用FIFO替换算法，命中率为3/12,3存储系统,3.4P205页习题3.19,解：（7）1采用LFU替换算法(全相联)，命中率3/12,3存储系统,3.4P205页习题3.19,解：（7）2采用FIFO替换算法(全相联)，命中率4/12,3存储系统,3.4P205页习题3.19,解：（8）,访问存储单元的命中率命中次数/总访问次数(1216-8)/(1216)184/19295.8% 分析：页“不命中”时，仅第1次不命中，其它15次都是命中的。而在页“命中”时，16次都是命中的。所以总访问次数为12*16，不命中次数为8,4输入输出系统,4.1名词解释,通道处理机：一种能够执行有限输入输出指令，并且能够被多台外围设备共享的小型DMA专用处理机。,4输入输出系统,4.2简答,通道的分类？,4输入输出系统,4.3P251页习题4.7,解：,（1）字节多路通道的实际工作流量为：fBYTE=100+33.3+33.3+20+10=196.6(KB/s)（2）在设计最大通道流量时，应留有一定的余量，对于字节多路通道，通道的最大流量应略大于所有连接在这个通道上的设备的流量之和。因此设计：a) 通道的最大流量fMAXBYTE=200(KB/s)b) 通道的工作周期T1/200 000=5us/byte,4输入输出系统,4.3P251页习题4.7,（3）由于通道工作在最大流量，故工作周期为5us,由时间关系图可知，通道处理完各台设备的第一次数据服务请求的时刻如下：D1：5usD2：10usD3：20usD4：30usD5：90us通道分时为各台设备服务的时间关系图（略）,解：,4输入输出系统,4.4P252页习题4.8,解：,（1）字节多路通道的实际工作流量为：fBYTE=1/10+1/75+1/15+1/50=200(KB/s)通道的工作周期为：T1/200 000=5us/byte,4输入输出系统,4.4P252页习题4.8,解：,（2）Ts+Td=5us，通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。,4输入输出系统,4.4P252页习题4.8,解：,（3）5，160，20，40；（4）D2丢失第一次请求的数据； （5）可用以下三种方法解决：（见P245）增加通道的最大流量，保证连接在通道上的所有设备的数据传送请求能够及时得到通道的响应。动态改变设备的优先级。增加一定数量的数据缓冲器，特别是对优先级比较低的设备。如例中，为D5增加一数据缓冲器，则其第一次数据传送请求可以在第85微秒处得到通道的响应，第二次在145微秒处响应。所有设备的数据都不会丢失。,5标量处理机,5.1名词解释,流水线技术：指将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。静态流水线：在同一时刻，流水线的各段只能按同一种功能的连接方式工作。动态流水线：在同一时刻，流水线的各段可以按不同功能的连接方式工作。,5标量处理机,5.1名词解释,吞吐率：吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。通过时间：第1个任务从进入流水线到流出流水线的时间称为通过时间。排空时间：最后1个任务从进入流水线到流出流水线的时间称为排空时间。,5.2简答,5标量处理机,衡量流水线性能的主要指标有哪些？吞吐率、加速比和效率。,吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。,加速比是指流水线的速度与等功能非流水线的速度之比。,效率是指流水线的设备利用率。,5.2简答,5标量处理机,流水线各段执行时间不相等时，消除瓶颈的方法？数据相关有哪几类？,细分瓶颈段 重复设置瓶颈段,写后读 读后写 写写,5.3例5.1,5标量处理机,例5.1 在静态流水线上计算 求：吞吐率，加速比，效率。,5.3例5.1,5标量处理机,用教材P283图5.32所示的TI-ASC计算机的多功能静态流水线计算.,5.3例5.1,5标量处理机,解：(1) 确定适合于流水处理的计算过程,(2) 画时空图,(3) 计算性能 吞吐率 TP7(20t) 加速比 S(34t)(20t)1.7 效率 E(4436)(820)0.21,5.3例5.1,5标量处理机,5.3例5.1,5标量处理机,5.3例5.1,5标量处理机,5.4例5.2,5标量处理机,例5.2 在用一条4段浮点加法器流水线计算8个浮点浮点数的和：ZABCDEFGH 求：吞吐率，加速比，效率。,5.4例5.2,5标量处理机,5.4例5.2,5标量处理机,5.5,5标量处理机,5.5,5标量处理机,5.5,5标量处理机,5.5,5标量处理机,5.6,5标量处理机,一个流水线由四段组成，其中每当流经第三段时，总要在该段循环一次才能流到第四段。如果每段经过一次的时间都是t，问：当在流水线的输入端每t时间输入任务时，该流水线会发生什么情况？此流水线的最大吞吐率为多少？如果每2t输入一个任务，连续处理10个任务的实际吞吐率和效率是多少？当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务 时，其吞吐率提高多少？,题：,5.6,5标量处理机,解：,（1）会发生流水线阻塞情况。,5.6,5标量处理机,解：,5.6,5标量处理机,解：,5.6,5标量处理机,解：,5.6,5标量处理机,解：,（3）重复设置部件,5.6,5标量处理机,解：,吞吐率提高倍数,1.64,5.7P342页习题5.3,5标量处理机,题：,5.7P342页习题5.3,5标量处理机,解：,（1）顺序执行方式：,5.7P342页习题5.3,5标量处理机,解：,（2）仅“取指令”和“执行”重叠：,5.7P342页习题5.3,5标量处理机,解：,（2）仅“取指令”和“执行”重叠：,5.8P343页习题5.7,5标量处理机,题：,5.8P343页习题5.7,5标量处理机,解：,5.8P343页习题5.7,5标量处理机,解：（下面图片中的所有11均改为7）,5.9P343页习题5.8,5标量处理机,题：,5.9P343页习题5.8,5标量处理机,解：,5.9P343页习题5.8,5标量处理机,解：,5.9P343页习题5.8,5标量处理机,解：,5.9P343页习题5.8,5标量处理机,解：,5.10P343页习题5.9,5标量处理机,解：,为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。记c1=A1B1，c6=A6B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。,5.10P343页习题5.9,5标量处理机,解：,5.10P343页习题5.9,5标量处理机,解：,5.10P343页习题5.9,5标量处理机,解：,根据时空图得：TP = 11/(22t) = 1/(2t)S = (64t + 54t)/(22t) = 2E = (64t + 54t)/(622t) = 1/3,5.11,5标量处理机,题：,有一条流水线如下所示。求:1）连续输入10条指令,该流水线的实际吞吐率和效率;2）该流水线的瓶颈在哪一段？请采取三种不同的措施消除此“瓶颈”。对于你所给出的新流水线，计算连续输入10条指令时，其实际吞吐率和效率。,5.11,5标量处理机,解：（1）,5.11,5标量处理机,解：（2）瓶颈在3、4段,措施1：变成八级流水线（细分）,5.11,5标量处理机,解：（2）瓶颈在3、4段,措施2：变成两级流水线（合并）,5.11,5标量处理机,解：（2）瓶颈在3、4段,措施3：重复设置硬件,5.11,5标量处理机,解：（2）瓶颈在3、4段,措施3：重复设置硬件,5.11,5标量处理机,解：（2）瓶颈在3、4段,措施3：重复设置硬件,5.12,5标量处理机,题：,如果流水线有m段，各段的处理时间分别是ti（i=1，2，m），现在有n个任务需要完成，且每个任务均需流水线各段实现，请计算：（1）流水线完成这n个任务所需要的时间；（2）和非流水线实现相比，这n个任务流水实现 的加速比是多少？加速比的峰值是多少？,5.12,5标量处理机,解：（1）,5.12,5标量处理机,解：（2）,祝大家考出好成绩！,QQ:30047495手机:13187323020E-mail:xiangdeshenghn165办公地点:计算机学院网络工程系（信息楼三楼）祝同学们学业大成！有问题或建议请与本人直接联系！,