福建农林大学计算机系统结构期末复习资料(更新版).pdf
《福建农林大学计算机系统结构期末复习资料(更新版).pdf》由会员分享,可在线阅读,更多相关《福建农林大学计算机系统结构期末复习资料(更新版).pdf(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、福建农林大学计算机系统结构共 18 页第 1 页计算机系统结构期末复习资料计算机系统结构期末复习资料计算机系统结构期末复习资料计算机系统结构期末复习资料应用题应用题应用题应用题【题型 1】经统计,某机器 14 条指令的使用频度分别为:0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14,0.11,0.03。分别求出用等长码、Huffman 码、只有两种码长的扩展操作码 3 种编码方式的操作码平均码长。解答14 条指令的等长操作码的平均码长是14log2位,即 4 位。哈夫曼编码可先用哈夫曼算法构造哈夫曼树,本题的哈夫曼树如图 1
2、 所示。在图 1 中,叶子上用圆括号所括起来的数字表示该频度指令所用的二进位编码的码位数,所以哈夫曼编码的操作码平均码长为38.3141=iiilp位。采用只有两种码长的扩展操作码,可根据 14 条指令所给出的使用频度值分成两群,让使用频度较高的 6 种指令用 3 位操作码编码表示,留下两个 3 位码作为长码的扩展标志,扩展出 2 位,共有 8 条使用低频的指令的操作码,这样,操作码的平均码长为=+=1414.320.0580.03iiilp位【题型 2.1】设中断级屏蔽位“1”对应于开放,“0”对应于屏蔽,各级中断处理程序的中断级屏蔽位设置福建农林大学计算机系统结构共 18 页第 2 页如表
3、所示。表 1 中断级屏蔽位设置中断处理程序级别中断级屏蔽位第 1 级第 2 级第 3 级第 4 级第 1 级0000第 2 级1011第 3 级1000第 4 级1010(1)当中断响应应优先次序4321时,其中断处理次序是什么?(2)如果所有的中断处理都各需 3 个单位时间,中断响应和中断返回时间相对中断处理时间少得多。当机器正在运行用户程序时,同时发生第 2、3 级中断请求,过两个单位时间后,又同时发生第 1、4 级中断请求,试画出程序运行过程示意图。分析为了领会中断响应排队器对中断响应的优先次序是用硬件固定的,以及通过由操作系统给各中断级服务程序现行程序状态字中的中断级屏蔽位设置不同的状
4、态,可以改变中断处理(完)的次序这两个要点,图1 给出了一个中断响应硬件部分的简单逻辑原理示意图。图中略去了某些实现上的具体细节,因为这些已不是本课程要讨论的内容。中断级屏蔽位是程序状态字中的一个组成部分。程序状态字是将散布于系统各部分,反映程序工作时某些关键性硬件的状态,组合在一起所构成的字,有的计算机也称其为处理器状态字或程序换道区。每类程序均在主存中指定一个区域来放置其程序状态字。运行一个程序或进程时,就会将其程序状态字从主存指定单元或区域取出送到分散于系统各部分的寄存器或计数器中,建立起运行此程序或进程的环境。一个程序或进程在退出运行时,也会将反映该程序状态的这些寄存器或计数器内容组拼
5、成程序状态字,存回该程序或进程在主存中的指定单元或区域里因此,程序或进程的切换,只需要通过硬件启动的交换新旧程序状态字的内容即可快速完成。例如在 IBM 370 系列机上,程序状态字为 64 位,等于它的长字,交换程序状态字只需硬件启动经写长字和读长宇二次访存即可完成。尽管中断请求是随机发出的,为了便于精确保存中断的断点以及在中断处理完后又能返回到原中断处,中断响应排队器总是在每条指令执行到最后一个机器周期的最后一个时钟周期时,对目前到达中断响福建农林大学计算机系统结构共 18 页第 3 页应排队器入口的所有中断请求排一次队,择优进行响应。在中断响应排队器相应的输出端产生出响应信号,此信号经中
6、断级服务程序入口地址形成硬件,生成该级中断服务程序的程序状态字在内存区中所存放的地址。同时,经中断响应控制信号启动,进行新旧程序状态字的交换,完成程序的切换被中断的程序的断点地址(即程序计数器的内容),由硬件自动压入返回地址堆栈,予以保存。系统切换到新的程序或进程后,继续运行下去,如果新的程序或进程是一个中断服务程序,在运行结束,执行到中断返回指令时,就会从堆栈中弹出所保存的返回地址再次交换程序状态字,系统又重新返回到原先被中断的程序,恢复运行。当然,低级的中断服务程序在处理过程中又遇到了比其更高级的中断请求时,应允许其被中断,以实现多级中断的嵌套。利用返回地址堆栈的后进先出工作方式,就可以完
7、成中断嵌套时的正确返回。可以看出,只要某道程序运行时,由操作系统在现行程序的程序状态字中,根据对各中断级的中断请求是否屏蔽,设置好中断级屏蔽位的状态,就可以控制这些级别的中断请求是否进入中断响应排队器去参加排队。只有能进入中断响应排队器的中断级请求,才有机会得到响应,从而就可改变中断实际处理完的次序。应当注意的是,用户程序是不能屏蔽任何中断的。因此,用户程序的现行程序状态字中,对各级中断级的屏蔽位,均应让其处于“开放”状态。根据本题所给出的各级中断处理程序对中断级屏蔽位设置的状况,很容易得出其中断处理(完)的次序应当是 1342。因为正处理 l 级的中断处理程序时,现行程序状态字中的中断级屏蔽
8、位为 0000,在其执行期间,任何新的同级和低级的中断请求都不可能进入中断响应排队器进行排队,所以,1 级中断处理程序一定会先处理完。当执行 3 级中断服务程序时,由于现行程序状态字中的中断级屏蔽位为 1000,即对 l 级中断请求是“开放”的,而对其它各级中断请求则处于“屏蔽”状态,所以,只要此时发生 1 级中断请求,它就能进入中断响应排队器去排队。从而在中断请求排队的微操作发出时,就可打断 3 级中断服务程序的执行,交换程序状态字。转去执行 1 级中断处理程序,使之被优先处理完。而在执行 3 级中断服务程序时,由于现行程序状态字对 2、3、4 级的中断请求处于被“屏蔽”的状态,所以,它们都
9、不能打断正在执行的 3 级中断处理程序。其它的情况也就可以依此类推得到。解答(1)中断处理(完)的次序为2431。(2)CPU 运行程序的过程示意图如下图所示。在该图中,粗短线部分代表进行交换程序状态字的时间,t为 1 个单位时间。【题型 2.2】若机器共有 5 级中断,中断响应优先次序为 l2345,现要求其实际的中断处理次序为 l4523。(1)设计各级中断处理程序的中断级屏蔽位(令“1”对应于屏蔽,“0”对应于开放);(2)若在运行用户程序时,同时出现第 4、2 级中断请求,而在处理第 2 级中断未完成时,又同时出现第 l、3、5 级中断请求,请画出此程序运行过程示意图。分析根据题意,中
10、断级屏蔽位“l”对应于屏蔽,“0”对应于开放,实际上就是在图 31 中,控制各级中断请求进入中断响应排队器入口端的与门控制端是接在各中断级屏蔽位触发器的“0”输出端而已,并无实质上的不同。此外,正在处理某级中断服务程序时,与其同级的新的中断请求是不能被响应的,应福建农林大学计算机系统结构共 18 页第 4 页KTnTP=当予以屏蔽,这是因为两者既然是属于同一优先级的,则先来的中断请求理所应当先得到响应并被处理完。所以,根据所要求的中断处;理(完)的次序,各级中断处理程序现行状态字中各中断级屏蔽位的状态就很容易被设置出来。解答(1)各级中断处理程序中的中断级屏蔽位的设置,如表 2 所示。表 2
11、中断级屏蔽位的设置中断处理程序级别中断级屏蔽位51111101000100111501100(2)由已知条件可得程序运行过程的示意图如图 3.3 所示。图中,粗短线表示交换程序状态宇的时间。【题型 3】吞吐率衡量流水线性能的主要指标有吞吐率、加速比和效率。解决流水线瓶颈问题的常用方法:细分瓶颈段、重复设置瓶颈段。最大吞吐率 Tpmax:指流水线达到稳定状态后可获得的吞吐率。实际吞吐率 Tp:是指单位时间内能处理的任务数或输出结果的数量,它总是小于最大吞吐率。因为流水线有建立阶段和排空阶段,以及其他因素会影响流水线的连续流动。(1)吞吐率 Tp:流水线单位时间里能流出的任务数或结果数。各段时间均
12、相等的流水线:实际吞吐率:tnknTP+=)1(福建农林大学计算机系统结构共 18 页第 5 页最大吞吐率:各段时间不完全相等的流水线:实际吞吐率:最大吞吐率:(2)效率:流水线中的设备实际使用时间与整个运行时间的比值,即流水线设备的利用率。各段时间均相等的流水线:E=TPt各段时间不完全相等的流水线:流水线中经过时间最长的子过程称为瓶颈子过程。例如,有一个 4 段的指令流水线如图 2 所示,其中,1、3、4 段的经过时间均为0t,只有 2 段的经过时间为03t,因此瓶颈在 2 段,使整个流水线最大吞吐率只有)3/(10t,其时-空图如图 3 所示。即使流水线每隔0t流入一条指令,也会因来不及
13、处理被堆积于 2 段,致使流水线仍只能以03t才流出一条指令。为了提高流水线的最大吞吐率,首先要找出瓶颈,然后设法消除此瓶颈。消除瓶颈的一种办法是将瓶颈子过程再细分。例如将 2 段再细分成 21、22、23 三个字段,如图 4 所示。让各子段经过时间都减少到0t,这样,最大吞吐率就可提高到0/1t。图 5 是将瓶颈子过程再细分后的时-空图。然而,并不是所有的子过程都能再细分的。假如 2 段已经不能再细分了,则可以通过重复设置多套(如此例用 3 套)瓶颈段并联,让它们交叉并行,如图 6 所示。每隔0t轮流给其中一个瓶颈段分配任务,使它们仍可每隔0t解释完一条指令,时-空图见图 7 所示。这种办法
14、需要解决好在各并行子过程之间的任务分配和同步控制,比瓶颈()ttnknTPn=+=11limmax=+=kikitttntnTP121),max()1(),max(121maxktttTP=+=kikikiitttntktnE1211),max()1(福建农林大学计算机系统结构共 18 页第 6 页子过程再细分控制要复杂、设备量要多。以上讲的都是流水线连续流动时能达到的最大吞吐量。由于流水开始时总要有一段建立时间,加上各种原因使流水线不能连续流动,经常是流一段时间,停一段时间,因此流水线的实际吞吐率pT总比最大吞吐率maxpT要小。【例题】为提高流水线效率可采用哪两种主要途径来克服速度瓶颈?现
15、有 3 段流水线,各段经过时间依次为t、3t、t,(1)分别计算在连续输入 3 条指令时和 30 条指令时的吞吐率和效率。(2)按两种途径之一改进,画出你的流水线结构示意图,同时计算连续输入 3 条指令和 30 条指令时的吞吐率。(3)通过对(1)、(2)两小题的计算比较可得出什么结论?解答:提高流水线效率,消除速度瓶颈主要有将瓶颈段再细分以及重复设置多个瓶颈段并联工作,给其轮流分配任务的两种途径。(1)在 3 段流水线,各段经过时间依次是t,t3,t的情况下,连续流入 3 条指令时,将ttttttttmnj=3,3,3,2321代入,可得吞吐率pT和效率为:ttntnTmijip=+=113
16、)1(1福建农林大学计算机系统结构共 18 页第 7 页而连续流入 30 条指令时,只需将上式之 n 改为 30,其他参数不变,得(2)若采取将 2 段细分成 3 个字段,每个字段均为t,构成的流水线结构如下图所示。连续流入 3 条指令时,将tmnji=,5,3代入,得连续流入 30 条指令时,将30=n代入,其它参数不变,有若采取将 3 个 2 段并联构成的流水线,其构成如下图所示。连续流入 3 条指令及流入 30 条指令时的吞吐率pT和效率所计算的结果分别与子过程细分的相同。115)1(11=+=mijimiitntmtnttntnTmijip=+=4615)1(14625)1(11=+=
17、mijimiitntmtntttTijip=+=73)13(3517375351=ttiitttTijip=+=1715)130(30511715345530=tt福建农林大学计算机系统结构共 18 页第 8 页(3)将(1)题中 n=3 和 n=30 的计算结果进行比较可以看出,只有当连续流入流水线的指令越多时,流水线的实际吞吐率和效率才会提高。将(1)、(2)题的计算结果进行比较,同样可以看出,无论采用平瓶颈子过程再细分,还是将多个瓶颈子过程并联来消除流水线瓶颈,都只有在连续流入流水线的指令数越多时,才能使实际吞吐率和效率得到显著的提高。若连续流入流水线的指令数太少,消除流水线瓶颈虽可以提
18、高流水线的实际吞吐率pT,而效率却可能下降。【题型 4.1】在一个 4 段的流水线处理机上需经 7 拍才能完成一个任务,其预约表如下表所示。分别写出延迟禁止表 F、冲突向量 C;画出流水线状态转移图;求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案,输入 6 个任务,求实际的吞吐率。段时间12345671S2S3S4S解答:此例可得延迟禁止表 F=2,4,6。初始冲突向量 C=(101010)。状态转移图如图所示。各种周期性调度方案及其相应的平均延迟如下表所示:调度方案平均延迟/拍(1,7)4(3,5)4(5,3)4(5)5由表可知,最小平均延迟为 4 拍。此时流水线的最
19、大吞吐率 Tpmax=1/4(任务/拍)。最佳调度方案宜选其中按(1,7)周期性调度的方案。按(1,7)调度方案输入 6 个任务,全部完成的时间为1+7+1+7+1+7=24(拍),实际吞吐率 Tp=6/24(任务/拍)。若按(3,5)调度方案输入 6 个任务,全部完成的时间为 3+5+3+5+3+7=26(拍),实际吞吐率 Tp=6/26(任务/拍)。若按(5,3)调度方案输入 6 个任务,全部完成的时间为 5+3+5+3+5+7=28(拍),实际吞吐率 Tp=6/28(任务/拍)。【题型 4.2】在一个 5 段的流水线处理机上需经 9 拍才能完成一个任务,其预约表如表下表所示。表 9 拍才
20、能完成一个任务的预约表时间时间段段t t t t0 0 0 0t t t t1 1 1 1t t t t2 2 2 2t t t t3 3 3 3t t t t4 4 4 4t t t t5 5 5 5t t t t6 6 6 6t t t t7 7 7 7t t t t8 8 8 8S S S S1 1 1 1S S S S2 2 2 2S S S S3 3 3 3S S S S4 4 4 4S S S S5 5 5 5福建农林大学计算机系统结构共 18 页第 9 页分别写出延迟禁止表 F、冲突向量 C;画出流水线状态转移图;求出最小平均延迟及流水线的最大吞吐率及其调用方案。按此流水调度方案
21、输入 6 个任务,求实际吞吐率。解答 对预约表中各个行中打“”的拍数求出差值,并将这些差值汇集在一起,就可得到延迟禁止表F=1,3,4,8由延迟禁止表 F 可转换得初始冲突向量 C=(10001101)。根据初始冲突向量可画出状态转移图如下图所示。流水线状态转移图为:各种周期性调度方案及其相应的平均延迟如下表所示:调度方案平均延迟/拍调度方案平均延迟/拍(2,5)3.5(6,7)6.5(2,7)4.5(7)7(5)5(5,2)3.5(6,5)5.5(6)6由上表可知,最小平均延迟为 3.5 拍。此时流水线的最大吞吐率 Tpmax=1/3.5(任务/拍)。最佳调度方案宜选其中按(2,5)周期性调
22、度的方案。按(2,5)调度方案输入 6 个任务的时空图为:11111 1111 1122 22222222233333 33 333344 444 4444 4455 5555555 5566666666666时 间空 间(段 号)s1 s2 s3 s4s50123 45 67891 01 11 21 31 41 51 61 7 1 81 92 02 12 2 2 3 2 42 5/t全部完成的时间为 25(拍),实际吞吐率 Tp=6/25(拍/任务)。【题型 4.2】求向量)(CBAD+=,各向量元素均为 N,参照 CRAY1 方式分解为 3 条向量指令:1:3V存储器访存取 A 送入3V寄
23、存器组2:2V0V1VKCB+3:4V2V3VDAK当采用下列 3 种方式工作时,各需多少拍才能得到全部结果?(1)1、2、3、串行执行;(2)1 和 2 并行执行完后,再执行 3;(3)采用链接技术。解答:(1)每条指令所需拍数为:福建农林大学计算机系统结构共 18 页第 10 页指令 1:1(启动访存)+6(访存)+1(存 V3)+N-1(第一个分量后每隔 1 拍出一个结果)=7+N(拍)指令 2:1(送浮加部件)+6(浮加)+1(存 V2)+N-1=7+N(拍)指令 3:1(送浮乘部件)+7(浮乘)+1(存 V4)+N-1=8+N(拍)串行:7+N+7+N+8+N=22+3N(拍)(2)
24、指令 1 和 2 并行执行:1(启动访存,送浮加部件)+6(访存,浮加)+1(存 V3,存 V2)+N-1=7+N(拍),1,2 并行:7+N+8+N=15+2N(拍)(3)1+6+1+1+7+1+N-1=16+N(拍)【题型 4.3】设向量长度为 64,以 CRAY-1 机上所用浮点功能部件的执行时间分别为:相加 6 拍,相乘 7拍,求倒数近似值 14 拍;从存储器读数 6 拍,打入寄存器及启动功能部件各 1 拍。问下列各指令组内的哪些指令可以链接?哪些指令不能链接?不能链接的原因是什么?分别计算出各指令组全部完成所需的拍数。(1)(2)(3)(4)0V存储器1V2V+3V4V5V6V2V0
25、V1V3V存储器4V2V+3V0V存储器2V0V1V3V2V+0V5V3V+4V0V存储器1V1/0V3V1V2V5V3V+4V解答:(1)3 条向量指令之间既没有发生源iV冲突,也没有iV的先写后读相关,又不存在功能部件的使用冲突,所以这 3 条向量指令可以同时并行流水。max(1+6(访存)+1+64-1),(1+6(浮加)+1+64-1),(1+(7浮乘)+1+64-1)=72 拍。所以向量指令组全部完成需要 72(拍)。(2)3 条向量指令之间没有功能部件的使用冲突,但是在第 1、2 两条向量指令与第 3 条向量指令之间有 V2及 V3 的先写后读相关。只要让第 1 条向量指令较第 2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 福建 农林 大学 计算机系统 结构 期末 复习资料 新版
限制150内