计算机系统结构总复习习题课件

《计算机系统结构总复习习题课件》由会员分享，可在线阅读，更多相关《计算机系统结构总复习习题课件（148页珍藏版）》请在金锄头文库上搜索。

1、计算机系统结构总复习2001.9.11计算机系统结构总复习习题课件第一章第一章 基本概念（基本概念（P1P1） 本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。 定量知识：对计算机性能进行定量评价的几个重要公式。2计算机系统结构总复习习题课件本章重点本章重点 本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下：(1) Amdahl定律；(2) 平均周期数CPI公式，程序执行时间Te公式；(3) 每秒百万指令数MIPS公式，每秒百万浮点数MFLOPS公式。2001.9.13计算机系统结构总复习习题课件

2、1.定量知识3个性能公式1.1 AmdahlAmdahl定律定律（加快经常性事件原理，P9）其中：Sn 全局加速比； To 原执行时间（old）； Tn 新执行时间（new）； Se 被改进部分的局部加速比； Fe 被改进部分原执行时间占原来总时间的百分比。4计算机系统结构总复习习题课件Amdahl定律的推导5计算机系统结构总复习习题课件Amdahl定律的图形 从图1.2可以看出，增大Se和Fe对Sn都有提升作用；但当Fe固定时，一味增大Se对Sn的作用会越来越不显著。6计算机系统结构总复习习题课件作作1.12假定利用增加向量模块来提高计算机的运假定利用增加向量模块来提高计算机的运算速度。计算

3、机处理向量的速度比其通常的运算算速度。计算机处理向量的速度比其通常的运算要快要快20倍，将可用向量处理部分所花费的时间占倍，将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。总时间的百分比称为可向量化百分比。（1）求出加速比）求出加速比S和向量化百分比之间的关系式和向量化百分比之间的关系式作作1.13（2）当要得到加速比为当要得到加速比为2时的可向量化百时的可向量化百分比分比F为多少？为多少？作作1.14（3）为了获得在向量模式所得到的最大加为了获得在向量模式所得到的最大加速比的一半，可向量化百分比速比的一半，可向量化百分比F为多少？为多少？计算机系统结构总复习习题课件(2)

4、由（1）式有解（1）：由Amdahl定律知(1)计算机系统结构总复习习题课件(3) 由题意可知计算机系统结构总复习习题课件作作1.17假假设设高高速速缓缓存存Cache工工作作速速度度为为主主存存的的5倍倍，且且Cache被被访访问问命命中中的的概概率率为为90，则则采采用用Cache后后，能使整个存储系统获得多高的加速比？能使整个存储系统获得多高的加速比？解：解：fe=0.9，re=5计算机系统结构总复习习题课件题题1.1 某计算机系统同时采用两种措施改进性能，某计算机系统同时采用两种措施改进性能，使得两个功能部件的性能分别提高到原来的使得两个功能部件的性能分别提高到原来的re1倍和倍和re

5、2 ，这两个部件在运行时使用的时间比例，这两个部件在运行时使用的时间比例分别为分别为fe1和和fe2 。试分析系统性能提高的总体加。试分析系统性能提高的总体加速比。速比。解解:计算机系统结构总复习习题课件1.2 CPI与程序执行时间Te（P11）CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，易知计算机系统结构总复习习题课件1.3 每秒百万指令数MIPS与每秒百万浮点数MFLOPS（P11）例题：P10，例1.1例1.5。 P33，题12 ，题13 ，题14 。13计算机系统结构总复习习题课件例例1.191.19 用用

6、一一台台4OMHz4OMHz处处理理机机执执行行标标准准测测试试程程序序，它它含含的的混混合合指指令令数数和和相相应应所所需需的的时时钟钟周周期期数数如如下：下：指令类型指令类型 指令条数 时钟周期数时钟周期数整数运算整数运算 4500045000 1数据传送数据传送 32000 232000 2浮点运算浮点运算 15000 215000 2控制传送控制传送 8000 28000 2求有效求有效CPICPI、MIPSMIPS速率和程序的执行时间。速率和程序的执行时间。计算机系统结构总复习习题课件解：依题意可知 IN=105条，n=4计算机系统结构总复习习题课件作作1.201.20 某工作站采用

7、时钟频率为某工作站采用时钟频率为15MHz15MHz、处理速率为、处理速率为10MIPS10MIPS的处理机来执行一个巳知混合程序。假定每次的处理机来执行一个巳知混合程序。假定每次存储器存取为存储器存取为1 1周期延迟、试问：周期延迟、试问： (1)(1)此计算机的有效此计算机的有效CPICPI是多少是多少? ? (2) (2) 假定将处理机的时钟提高到假定将处理机的时钟提高到30MHz30MHz，但存储器子，但存储器子 系统速率不变。这样，每次存储器存取需要两个时钟系统速率不变。这样，每次存储器存取需要两个时钟 周期。如果周期。如果3030指令每条只需要一次存储存取，而另指令每条只需要一次存

8、储存取，而另 外外5 5每条需要两次存储存取，还假定已知混合程序每条需要两次存储存取，还假定已知混合程序 的指令数不变，并与原工作站兼容，试求改进后的处的指令数不变，并与原工作站兼容，试求改进后的处 理机性能。理机性能。 解解(1)计算机系统结构总复习习题课件(2)依题意可知：依题意可知：30%的指令需要一次存储存取，则的指令需要一次存储存取，则这些指令在处理器提高时钟频率之后需要增加这些指令在处理器提高时钟频率之后需要增加1个时个时钟周期；另外钟周期；另外5%的指令需要增加的指令需要增加2个时钟周期。个时钟周期。改进后性能提高情况可用改进后性能提高情况可用CPU时间之比表示：时间之比表示：计

9、算机系统结构总复习习题课件题题1.3某向量计算机系统中，标量指令的平均某向量计算机系统中，标量指令的平均CPI是是1，向量运算指令的平均，向量运算指令的平均CPI是是64，系统加快，系统加快向量部件的速度后使向量运算速度提高到原来向量部件的速度后使向量运算速度提高到原来的的2倍，某一测试程序执行时的向量运算指令数倍，某一测试程序执行时的向量运算指令数量占全部指令数的量占全部指令数的10，问计算机系统运行这，问计算机系统运行这个测试程序的整体性能比原来提高多少？个测试程序的整体性能比原来提高多少？解：解：计算机系统结构总复习习题课件作作1.121.12 假设在一台假设在一台40MHz40MHz处

10、理机上运行处理机上运行200 000200 000条条指令的目标代码，程序主要由四种指令组成。根据指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：需的指令数如下： 指令类型指令类型CPI指令混合百分比算术和逻辑运算算术和逻辑运算160%CacheCache命中的加载命中的加载/ /存储存储218%转移转移412%CacheCache失效时访问主存失效时访问主存810%(1)(1)计算在单处理机上用上述踪数据运行程序的平均计算在单处理机上用上述踪数据运行程序的平均CPICPI(2)(2)根据根据(

11、1)(1)所得所得CPICPI，计算相应的，计算相应的MIPS MIPS 速率和程序的执行时间速率和程序的执行时间计算机系统结构总复习习题课件解：依题意可知 IN=2105条，n=4，计算机系统结构总复习习题课件第二章第二章 指令系统（指令系统（P36P36） 本章介绍指令系统设计中2个最基本的内容：数据表示、操作码优化。本章重点本章重点 (1) Huffman编码方法；(2) 等长扩展编码方法（15/15/15法，8/64/512法）；(3) 编码方法性能指标（平均码长L，信息冗余量R）。21计算机系统结构总复习习题课件2.1 Huffman压缩编码（P91）(1)Huffman压缩概念（最

12、佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分配，可使平均码长达到最低。(2) Huffman编码方法 这种编码方法由两个过程组成。频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树 Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根

13、结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就较少，符合Huffman压缩原则。 上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。2001.9.122计算机系统结构总复习习题课件 平均码长平均码长：各事件编码长度的数学期望。 信息冗余量信息冗余量：它表明消息编码中“无用成分”所占的百分比。23计算机系统结构总复习习题课件2.2 扩展编码方法（扩展编码方法（等长扩展法，P94-95）用码长表示：例如4-8-12法。这并不能说明具体编码方法，例如下面两种编码方法都是4-8-12法。用码点数表示：例

14、如15/15/15法，8/64/512法15/15/15法，每一种码长都有4位可编码位（前头可以有相同的扩展标识前缀），可产生16个码点（即编码组合），但是至多只能使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是“非前缀原则”。8/64/512法，每一种码长按4位分段，每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。24计算机系统结构总复习习题课件10000001110.090.300.60

15、1.000.1510.0610.030.030.040.050.150.300.40 I7I6I5I4I3I2I1I7I6I5I4I3I2I1例例例例2.12.12.12.1 某指令系统各指令使用频度如下：某指令系统各指令使用频度如下：某指令系统各指令使用频度如下：某指令系统各指令使用频度如下：I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.

16、4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 1.Huffman 1.Huffman 1.Huffman 1.Huffman编码编码编码编码计算机系统结构总复习习题课件由此可得到哈夫曼编码如下：由此可得到哈夫曼编码如下： I1: 0 I2: 10 I3: 110 I4: 11100 I1: 0 I2: 10 I3: 110 I4: 11100 I5: 11101 I6: 11110 I7: 11111 I5: 11101 I6: 11110 I7: 11111 平均码长平均码长L L=0.4*1+0.3*2+0.

17、15*3+0.05*5+0.04*5=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5 = 2.20 +0.03*5+0.03*5 = 2.20位位 信息冗余量信息冗余量R=(2.20-2.17)/2.20=1.36%R=(2.20-2.17)/2.20=1.36% 指令长度个数指令长度个数=4=4计算机系统结构总复习习题课件2.2.扩展哈夫曼编码扩展哈夫曼编码I1, I2, I3 I1, I2, I3 用两位用两位: 00, 01, 10: 00, 01, 10I4, I5, I6, I7 I4, I5, I6, I7 用四位用四位: 1100,

18、 1101, 1110, : 1100, 1101, 1110, 11111111L L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4 = 2.30 = 2.30位位信息冗余量信息冗余量=(2.302.20)/2.30=0.0565=5.65%=(2.302.20)/2.30=0.0565=5.65%计算机系统结构总复习习题课件41 1 1 151 1 1 1 10.03I741 1 1 051 1 1 1 00.03I641 1 0 151 1 1 0 10.04I541 1

19、 0 051 1 1 0 00.05I421 031 1 00.15I320 1 2 1 00.30I220 0100.40I1OP长度长度lihuffman扩展编扩展编码码OP长长度度li操作码操作码OP使用哈夫曼使用哈夫曼编码编码 频频 度度（Pi） 指指 令令操作码的扩展（等长扩展）操作码的扩展（等长扩展）平均码长： 2. 2 2.3计算机系统结构总复习习题课件例例2.22.2 指令系统共有指令系统共有4242种指令，前种指令，前1515种使用频率平均种使用频率平均为为0.050.05，中间，中间1313种使用频率平均为种使用频率平均为0.0150.015，最后，最后1414种种使用频率

20、平均为使用频率平均为0.0040.004。如何编码？。如何编码？00000000 ： 1515种种111011101111 00001111 0000 ： ： 1515种种1111 11101111 11101111 1111 00001111 1111 0000 ： ： ： 1515种种1111 1111 11101111 1111 1110解：解：因频率分布有三种，故因频率分布有三种，故码长可有三种；码长可有三种； 因每段指令数基本相同，因每段指令数基本相同，故可采用故可采用等长扩展等长扩展(4-8-12(4-8-12位位) )， 保留特征码的每段指令保留特征码的每段指令数相同数相同(15

21、-15-15)(15-15-15)方法。结方法。结果如图所示；果如图所示； 结果：采用结果：采用15-15-1515-15-15扩展方法，最后一种编码用于扩展方法，最后一种编码用于扩展，每段扩展，每段0000000011101110用于编码，用于编码，11111111用于扩展。用于扩展。计算机系统结构总复习习题课件例例2.32.3 指令系统共有指令系统共有7474种指令，前种指令，前4 4种使用频率平均种使用频率平均为为0.120.12，中间，中间1515种使用频率平均为种使用频率平均为0.020.02，最后，最后5555种使种使用频率平均为用频率平均为0.0040.004。如何编码？。如何编

22、码？解：解：同上例方法，同上例方法，码长可有三种；码长可有三种； 因每段指令数成比例因每段指令数成比例(1(1：4)4)，故可采用，故可采用等长等长扩展方法扩展方法(3-6-9(3-6-9位位) )扩展扩展，保留标志位方法，结果保留标志位方法，结果如图所示；如图所示； 结果：采用结果：采用4-16-64扩展方法，编码第一位用于扩展，扩展方法，编码第一位用于扩展，每段每段0XX用于编码，用于编码，1XX用于扩展。用于扩展。0xx 40xx 4种种1xx 0xx 161xx 0xx 16种种1xx 1xx 0xx 641xx 1xx 0xx 64种种 4-16-64 4-16-64平均码长平均码长

23、 =0.12*4*3+0.02*15*6+0.004*55*9=5.22=0.12*4*3+0.02*15*6+0.004*55*9=5.22；计算机系统结构总复习习题课件例例2.4 2.4 指令系统共有指令系统共有7878种指令，前种指令，前1010种使用频率平种使用频率平均为均为0.0490.049，中间，中间1818种使用频率平均为种使用频率平均为0.020.02，最后，最后5050种使用频率平均为种使用频率平均为0.0030.003。如何编码？。如何编码？ 解：解：同上例方法，码长可有三种；因每段指令数比同上例方法，码长可有三种；因每段指令数比例为例为1 1：2 2：5 5，故不可采用

24、等长扩展，采用不等长编，故不可采用等长扩展，采用不等长编码码( 4-6-10( 4-6-10位位) )较能减少平均码长。较能减少平均码长。00000000 ： 1010种种100110011010 001010 00 ： ： 2020种种1110 111110 111111 00 00001111 00 0000 ： ： ： 6464种种1111 11 11111111 11 1111 第一种采用第一种采用4 4位编码中前位编码中前1010种种(00001001)(00001001)； 第二种采用第一种频率编第二种采用第一种频率编码中的后码中的后5 5种编码种编码(10101110)(1010

25、1110)与扩展的与扩展的2 2位共位共2020种编码；种编码； 第三种采用第一种频率编第三种采用第一种频率编码中的最后一种码中的最后一种(1111)(1111)与扩与扩展的展的6 6位共位共6464种编码。种编码。计算机系统结构总复习习题课件作作2.52.5 某模型机有某模型机有9 9条指令，其使用频率为：条指令，其使用频率为：ADDADD（加）（加）30%30%SUBSUB（减）（减）24%24%JOMJOM（按负转移）（按负转移）6%6% STOSTO（存）（存）7%7%JMPJMP（转移）（转移）7%7% SHRSHR（右移）（右移）2%2%CILCIL（循环左移）（循环左移）3%3%

26、 CLACLA（清加）（清加）20%20%STPSTP（停机）（停机）1%1% 要求有两种指令字长，都按双操作数指令格式编要求有两种指令字长，都按双操作数指令格式编, ,采用扩展操作码，并限制只能有两种操作码码长。设采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存为该机有若干个通用寄存器，主存为1616位宽，按字节编位宽，按字节编址，采用整数边界存贮，任何指令都在一个主存周期址，采用整数边界存贮，任何指令都在一个主存周期中取得，短指令为寄存器寄存器型，长指令为寄存中取得，短指令为寄存器寄存器型，长指令为寄存器主存型，主存地址应能变址寻址。器主存型，主存地址应能变址寻址

27、。计算机系统结构总复习习题课件解：解：(1)Huffman树的形式如图所示。树的形式如图所示。0.010.020.03010.030.06010.060.12010.070.070.14010.260100.300.200.240.44010.5610011计算机系统结构总复习习题课件由上图可得到的由上图可得到的Huffman编码为：编码为：ADD(ADD(加加) 30% 01) 30% 01 SUB( SUB(减减) 24% 11) 24% 11 CLA( CLA(清加清加) 20% 10) 20% 10 JOM( JOM(按负转移按负转移) 6% 0001) 6% 0001 STO( ST

28、O(存存) 7% 0011 ) 7% 0011 JMP( JMP(转移转移) 7% 0010) 7% 0010 CIL( CIL(循环左移循环左移) 3% 00001 ) 3% 00001 SHR( SHR(右移右移) 2% 000001 ) 2% 000001 STP( STP(停机停机) 1% 000000) 1% 000000因此，操作码的平均码长为：因此，操作码的平均码长为：计算机系统结构总复习习题课件(2)采用采用2-5扩展的操作码编码为：扩展的操作码编码为： ADD(ADD(加加) 30% 00) 30% 00 SUB( SUB(减减) 24% 01) 24% 01 CLA( CL

29、A(清加清加) 20% 10) 20% 10 JOM( JOM(按负转移按负转移) 6% 11000) 6% 11000 STO( STO(存存) 7% 11001 ) 7% 11001 JMP( JMP(转移转移) 7% 11010) 7% 11010 SHR( SHR(右移右移) 2% 11011 ) 2% 11011 CIL( CIL(循环左移循环左移) 3% 11100) 3% 11100 STP( STP(停机停机) 1% 11101) 1% 11101因此，操作码的平均码长为：因此，操作码的平均码长为：计算机系统结构总复习习题课件(3)该机允许使用的可编址的通用寄存器个数为该机允许

30、使用的可编址的通用寄存器个数为23=8个个(4)短指令为寄存器短指令为寄存器-寄存器型，格式如下：寄存器型，格式如下：OP(2位位)R1(3位位)R2(3位位)OP(5位位)R1(3位位)X(2位位)相对位移相对位移d(6位位)(5)访主存操作数地址寻址的最大相对位移量为访主存操作数地址寻址的最大相对位移量为64个字节个字节(-32+31个字节个字节)长指令为寄存器长指令为寄存器-主存型，格式如下：主存型，格式如下：计算机系统结构总复习习题课件作作2.152.15 某处理机的指令字长为某处理机的指令字长为1616位，有双地址位，有双地址指令、单地址指令和零地址指令三类，并假设每指令、单地址指令

31、和零地址指令三类，并假设每个地址字段的长度为个地址字段的长度为1616位。位。（1 1）如果双地址指令有）如果双地址指令有1515条，单地址和零地址条，单地址和零地址指令的条数基本相同，问单地址指令和零地址指指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。令各有多少条？并且为这三类指令分配操作码。（2 2）如果三类指令的比例为）如果三类指令的比例为1 1：9 9：9 9，问双地址，问双地址指令、单地址指令和零地址指令各有多少条？并指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。且为这三类指令分配操作码。计算机系统结构总复习习题课件解解：（

32、1 1）双地址指令）双地址指令1515条，地址码：条，地址码： 0000000011101110单地址指令单地址指令2 26 61 16363条，地址码：条，地址码：1111 0000001111 000000 1111 111110 1111 111110零地址指令零地址指令6464条，地址码：条，地址码： 1111 111111 0000001111 111111 000000 1111 111111 111111 1111 111111 111111（2 2）双地址指令）双地址指令1414条，地址码：条，地址码：0000000011011101单地址指令单地址指令2 26 6222 21

33、26126条，条， 1110 0000001110 000000 1110 111110 1110 111110 零地址指令零地址指令128128条，地址码：条，地址码：1111 111110 0000001111 111110 000000 1111 111111 111111 1111 111111 111111计算机系统结构总复习习题课件 2.2.2 操作数优化寻址方式比较（P95） 指令中操作数占用的位数由操作数的个数与寻址方式决定。 按操作数的个数划分，有零操作数指令、一操作数指令、二操作数指令、三操作数指令共四种形式。应该按机器用途来选择（P99，表2.20）。 缩短操作数长度的常

34、用方法是间址和变址（P99页末）。2001.9.139计算机系统结构总复习习题课件第三章第三章 存储系统（存储系统（P130P130） 长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上CPU的发展，容量不能满足软件尺寸扩大。 本章学习两种提高主存系统性能/价格比的结构化方法：并行存储器与存储层次技术。后者为主。2001.9.140计算机系统结构总复习习题课件例例3.1假设高速缓存假设高速缓存Cache工作速度为主存工作速度为主存的的5倍，且倍，且Cache被访问命中的概率为被访问命中的概率为90，则采用则采用Cache后，能使整个存储系统获得多后，能使整个存储系统获得多高的加速

35、比？高的加速比？解：解：计算机系统结构总复习习题课件l例例3.2假设高速缓存假设高速缓存Cache的访问周期为的访问周期为50ns，主存的访问周期为，主存的访问周期为400ns，且，且Cache被访问命中的概率为被访问命中的概率为95，则采用，则采用Cache后，后，能使整个存储系统等效的访问周期为多少能使整个存储系统等效的访问周期为多少？获得多高的加速比？获得多高的加速比？解：解：计算机系统结构总复习习题课件存储层次的管理方式(P148) 根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。(1)段式管理段式管理(P

36、148)。段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。 每段使用独立的逻辑地址空间，即都从0开始计算地址。 段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。 段式管理方法的虚实变换算法是查段表(P150)。2001.9.143计算机系统结构总复习习题课件(2)页式管理页式管理(P151)。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。 我们把用户文件划分得到的一个长度单位称为“虚页虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小

37、划分得到的一个长度单位称为“实页实页”。 页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。 页式管理方法的虚实变换算法是查页表(P152)。(3)段段页页式式管管理理(P153)。它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P154)。 段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。 由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理，为了叙述简单，下面的分析还是以页式管理为模型。2001.9.1

38、44计算机系统结构总复习习题课件3.3 地址映象与变换(P174)基本术语：基本术语： 逻逻辑辑地地址址（又称为相相对对地地址址、虚虚地地址址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间逻辑地址空间、虚空间虚空间或虚存虚存。 物物理理地地址址（又称为绝绝对对地地址址、实实地地址址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间物理地址空间、实空间实空间或实存实存。 从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。 地址映

39、象地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。 地址变换地址变换（又叫虚实变换虚实变换）指逻辑地址到物理地址的变换过程或者算法。 页失效页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。 实页争用实页争用又叫实页冲突实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。2001.9.145计算机系统结构总复习习题课件相联目录表技术1.1.页表占用空间过大问题页表占用空间过大问题 页表必须存放在实存M1里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在M2。 页表占用空间 = 页表行数 每行宽度 其中，页

40、表行数 = 虚存容量 / 页面大小 以PC机为例，页表行数 60G / 4K = 236 / 212 = 224 1600万！按每行宽度6字节估算约需96MB。 减少页表空间的思路分减少行数和减少行宽两类。2.相联目录表方法（P158） 仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。3.快慢表方法（P159）4.通过地址映象减少行宽 如下文所示2001.9.146计算机系统结构总复习习题课件4种常见的地址映象方式3.3.1 全相联(P174) 全全相相联联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实

41、页。这种关系可用下页示意图(a)、(b)表示。 全相联的虚实变换信息完全来自于变换表，查表过程如图(c)所示。 全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入/调出的操作开销也最少，有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。 由于页表必须常驻在实存中，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象方式一般用于主存-辅存层次。2001.9.147计算机系统结构总复习习题课件全相联的地址映象方式与地址变换原理示意图(a

42、)(b)2001.9.148计算机系统结构总复习习题课件全相联的地址映象方式与地址变换原理示意图(c)2001.9.149计算机系统结构总复习习题课件3.3.2 直接相联(P176) 直直接接相相联联是一种最强的约束关系，它规定每个虚页只对应唯一的实页。为了便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现起来非常简单，因为在二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位，如下页示意图(c)所示。 例3.3 已知虚页号 = 7，实页总数 = 4，用直接相联求实页号。解： 可用十进制形式求：7 mod 4 = 3； 也可用二进制形式求：由于n =

43、4，所以log2n = 2，取7的二进制形式111B的最低2位，得11B，即3。 直接相联映象方式不需要借助页表来进行虚实变换，显然大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率大大下降。 这种映象方式主要用于一些对实存价格非常敏感的Cache-主存层次。2001.9.150计算机系统结构总复习习题课件直接相联的地址映象方式与地址变换原理2001.9.151计算机系统结构总复习习题课件3.3.3 组相联(P178) 组相联映

44、象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。具体做法是先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合，对应的虚实组之间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。 由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”。如图(c)所示。 采用组相联映象方式时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低；另一

45、方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。 这种映象方式性价比较好，在Cache-主存层次中被普遍使用。2001.9.152计算机系统结构总复习习题课件组相联的地址映象方式与地址变换原理(a)(b)2001.9.153计算机系统结构总复习习题课件组相联的地址映象方式与地址变换原理(c)2001.9.154计算机系统结构总复习习题课件3.3.4 段相

46、联(P184) 段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图(a)、(b)所示（设实段数为2）。 段相联的虚实变换与组相联类似，不过可以通过计算来确定的部分不是在段外，而是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为“段号查表、段内复制”。如图 (c)所示。 段相联映象方式的虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以

47、虚段号比实段号位数多，也就意味着“多少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。2001.9.155计算机系统结构总复习习题课件段相联的地址映象方式与地址变换原理(a)(b)2001.9.156计算机系统结构总复习习题课件段相联的地址映象方式与地址变换原理(c)2001.9.157计算机系统结构总复习习题课件多用户虚地址格式 在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从CPU发出的虚地址还需要在前面拼接上一个“当前用户号”字段，形成“多用户虚地址”，如下图所示(参见

48、P154)。 在虚实变换时，上面所说的各种查表操作之前还得先去查一个“段表基址寄存器组”或“页表基址寄存器组”的小表格(P150，P152)，确定现在该查哪一张段表或页表。这个小表格建立在CPU里，读写时间很短。2001.9.158计算机系统结构总复习习题课件3.4 替换算法(P164) 上面所讲的地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。 不命中时需要增加的操作就是首先调出一页，调出之后再调入称为 “替换”。 替换算法要解决的是选择调出对象的问题。 替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用

49、）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。2001.9.159计算机系统结构总复习习题课件3.4.1 几种常用的替换算法(P164)(1)随机算法RAND 在比较范围内任取一页作为淘汰页；(2)先进先出算法FIFO 在比较范围内选取调入最早的一页作为淘汰页；(3)最不经常使用算法LFU 在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；(4)最不接近使用算法LRU 在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；(5)最优替换算法OPT 在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页。2001.9.160计算机系统结构总复习习题课件

50、实例：实存状况图(P166图3.32)例如 LRU 算法（其中*号表示被选中的淘汰页）：61计算机系统结构总复习习题课件例例3.3设某用户虚存共有设某用户虚存共有8页页,主存有主存有4页页,每页大每页大小为小为1KB.试根据页表计算出虚地址试根据页表计算出虚地址1023和和6800的主存实地址。的主存实地址。提示：注意页表中虚、 实页对应关系页表虚页号虚页号实页号实页号装入位装入位031111220330421510601700计算机系统结构总复习习题课件每页首地址=页号 X 每页大小第0页01023第1页10242047第2页20483071第3页30724095第4页40965119第5页

51、51206143第6页61447167第7页7168-8191解：解：页号与地址对应关系页号与地址对应关系虚地址虚地址1023，虚页号为，虚页号为0，页内位移，页内位移为为1023；根据虚页号查页表得知实页；根据虚页号查页表得知实页号为号为3，且装入位为，且装入位为1。主存实地址主存实地址PA=3072+1023=4095虚地址虚地址6800，虚页号为，虚页号为6，页内位移，页内位移为为656；根据虚页号查页表得知实页；根据虚页号查页表得知实页号为号为0，且装入位为，且装入位为1。主存实地址主存实地址PA=0+656=656虚页号虚地址虚页号虚地址/1024计算机系统结构总复习习题课件例例3.

52、4虚存虚存32页页,主存主存16页页,每页为每页为1KB。某时刻已。某时刻已调入主存的实页与虚页对应如下调入主存的实页与虚页对应如下:虚页号虚页号0128实页号实页号51047求虚地址求虚地址0A5CH和和1A5CH对应的实地址。对应的实地址。0001001001011100主存实地址查页表（已装入）直接直接dp125CH0000101001011100 单用户的虚地址PD0A5CH解：解：计算机系统结构总复习习题课件0001101001011100 查页表（未装入）单用户的虚地址页面失效，无对应的主存实地址。PD直接直接1A5CH解：解：用户的虚页并未装入主存中，当执行该虚页用户的虚页并未装

53、入主存中，当执行该虚页程序时，找不到对应的实页。程序时，找不到对应的实页。计算机系统结构总复习习题课件例3.5 虚拟存储器举例IBM370/168相等比较位数？相等比较位数？相等寄存器位数？相等寄存器位数？快表行数？快表行数？快表每行的位数？快表每行的位数？用户数？用户数？每个用户虚页数？每个用户虚页数？每页大小？每页大小？如何减少散列冲突如何减少散列冲突？快表为何采用两组快表为何采用两组？相等比较的作用？相等比较的作用？224212=4K212=4KB15位30位64行24+24位9位计算机系统结构总复习习题课件假若一计算机的主存储器按假若一计算机的主存储器按64块组织，块大小块组织，块大小

54、为为8个字，高速缓存有个字，高速缓存有8块。试按下述要求画图块。试按下述要求画图回答问题。回答问题。（1）画出全相联映像示意图、指定标记字段）画出全相联映像示意图、指定标记字段和主存地址格式。和主存地址格式。（2）画出直接映像示意图、指定标记字段和）画出直接映像示意图、指定标记字段和主存地址格式。主存地址格式。（3）画出）画出2路组相联映像示意图、指定标记字段路组相联映像示意图、指定标记字段和主存地址格式。和主存地址格式。例例3.6计算机系统结构总复习习题课件b0b1b7 解解：（1）全相联映像）全相联映像标记标记6位的高速缓存位的高速缓存B7B8B9 B1B0B56B57B63 主存储器主存

55、储器（块号）标记（块号）标记（6位）字（位）字（3位）位）行号（行号（3位）位）字（字（3位）位）主存地址主存地址缓存地址缓存地址 标记标记计算机系统结构总复习习题课件b0b1b7 （2）直接映像）直接映像标记标记3位的高速缓存位的高速缓存主存储器主存储器行号行号L字字w主存地址主存地址缓存地址缓存地址 标记标记 B7B8B9 B1B0B56B57B63 区区0区区7区号区号E（标记）（标记）块号块号B字字W3位3位3位3位3位计算机系统结构总复习习题课件（3）2路组相联映像路组相联映像标记标记4位的高速缓存位的高速缓存主存储器主存储器主存地址主存地址缓存地址缓存地址 B3B4B5B2B1B0

56、B60B61B63 B62区区0区区15区号区号E（标记）（标记）组号组号G字字W4位2位3位1位3位b0b1b7b2b3b4b5b60组组1组组2组组3组组组号组号g行号行号L字字w2位计算机系统结构总复习习题课件例例3.7有有1K个任务，短期内只有个任务，短期内只有4个用户，个用户，每个用户程序空间可达每个用户程序空间可达4096页，每页页，每页512B，主存地址长度为主存地址长度为20位，虚实地址经快表变换，位，虚实地址经快表变换，问相关设计：问相关设计： (1) (1) 实页位数实页位数 ？（2 2）每个相联寄存器的相联比较位数）每个相联寄存器的相联比较位数 （3 3）每个相联寄存器的

57、总位数）每个相联寄存器的总位数 （4 4）散列变换硬件的输入和输出位数）散列变换硬件的输入和输出位数 （5 5）每个相等比较器的位数为）每个相等比较器的位数为 （6 6）快表的总容量）快表的总容量 计算机系统结构总复习习题课件l3.7解：解：（1）可有可有1K个任务，短期内只有个任务，短期内只有4个用户，个用户，指示用户号的地址字段指示用户号的地址字段U=10位；位；ID=2位；位；又又每个用户程序空间可达每个用户程序空间可达4096页，页，P=12, 每页每页512B，512*8= 4096 512*8= 4096 位位 D=( (9+3) )=12位；位；又又主存地址长度为主存地址长度为2

58、0位，位， 实页号实页号p=20-12=8p=20-12=8位位（2 2）每个相联寄存器的相联比较位数为）每个相联寄存器的相联比较位数为U=10U=10位；位；（3 3）每个相联寄存器的总位数为）每个相联寄存器的总位数为U+ID=12U+ID=12位；位；（4 4）散列变换硬件的输入和输出位数为）散列变换硬件的输入和输出位数为1414位和位和4 4位位（5 5）每个相等比较器的位数为）每个相等比较器的位数为P+ID=12+2=14P+ID=12+2=14位；位；（6 6）快表的总容量为）快表的总容量为16(12+2+8)2=70416(12+2+8)2=704（位）（位）计算机系统结构总复习习

59、题课件用户号用户号U虚页号虚页号P页内位移页内位移D多用户的虚地址多用户的虚地址34位实页实页p页内位移页内位移d主存实地址20位8位12位12位12位10位散列变换散列变换相等？相等？14位4位16行直接P+IDP+IDppU1U2U3U300011011虚实地址经快表变换的逻辑示意图虚实地址经快表变换的逻辑示意图计算机系统结构总复习习题课件题题3.8对于下述访存字节地址序列：对于下述访存字节地址序列：1,14,50,89,20,17,19,56,19,11,14,43,15,16,9,17标出每次访存后的标出每次访存后的cache存储空间的分配情存储空间的分配情况和命中情况。假定况和命中情

60、况。假定cache是是2路组相联的，路组相联的，采用采用FIFO替换策略，每块是替换策略，每块是4个个32位的字。位的字。Cache的容量是的容量是16字，初始字，初始cache为空。为空。计算机系统结构总复习习题课件主存地址主存地址cache地址地址区号区号组号组号块号块号字字W1位1位2位1位2位组号组号块号块号字字w1位解：解：B3B4B2B1B0B7B5B6主存储器主存储器 组0组1区0区13位B4B7B5B6区7 计算机系统结构总复习习题课件时间时间 t 12345678910111213141516字地址流字地址流（2路组相联路组相联FIFO）调调进进调调进进调调进进替替换换替替换

61、换替替换换替替换换命命中中命中命中1次次组0组1替替换换替替换换替替换换1114 1450195689 89 89 8920*50*17171911175617 1719191450142014 14*89*89114508920171956191114431516917替替换换1756*43171614*191411*19174317*151943*161519 916 1519* 9151 1*调调进进替替换换替替换换替替换换计算机系统结构总复习习题课件3.2.2 性能指标（P132-P134） (1) 容量：S=S2 （理论上） (2) 单价：（美分/bit）2001.9.177计算机系

62、统结构总复习习题课件(3) 速度：表现访问速度的参数很多 命中率：反映被访问数据事先已在M1的发生概率 等效访问时间：命中时的访问时间为T1，不命中时的访问时间为T2，等效访问时间则是它们的概率均值2001.9.178计算机系统结构总复习习题课件 访问效率：这是一个相对值，便于不同系统之间的比较。访问效率e受H和r的影响（参见右图）：79计算机系统结构总复习习题课件 Cache预取技术对命中率的提高作用（P134）： 这里所说的“预取”技术，并不是根据对程序执行的未来趋势进行猜测以提前调入数据，而仅仅是在发生不命中情况时把调入1个数据字改为调入1个数据块的策略。根据程序的局部化原理，在当前使用

63、数据周围的其它数据未来被使用的几率大于远处数据，所以该数据块中被提前调入的邻近数据很可能成为未来的命中点，从而提高命中率。 采用这种预取技术后新的命中率为其中：H 原命中率（即按照不命中时取入1字的策略）； H 新命中率（即按照不命中时取入1块的策略）； n 每块数据平均被访问次数。2001.9.180计算机系统结构总复习习题课件 按照定义，原不命中率 ，新不命中率 ，并且有 。由于预取使得每块数据中的不命中次数由n次降低到1次，所以有 。此式可改写为 ，整理得 。H的推导：2001.9.181计算机系统结构总复习习题课件 加速比（P193） Cache-主存层次的主要作用是提高访问速度，系统

64、的等效速度应高于主存（即M2）的原有速度，两个速度之比称为加速比。 增加中间层对e的影响2001.9.182计算机系统结构总复习习题课件3.9在一个在一个Cache存储系统中，存储系统中，Cache的访问周期为的访问周期为10ns，主存储器的访问周期为，主存储器的访问周期为60ns，每个数据在，每个数据在Cache中平均重复使用中平均重复使用4次。当块大小为次。当块大小为1个字节时，个字节时，存储系统的访问效率只有存储系统的访问效率只有0.5，现在要通过增加块大，现在要通过增加块大小，使存储系统的访问效率达到小，使存储系统的访问效率达到0.94。（1）当存储系统的访问效率为）当存储系统的访问效

65、率为0.5时，计算命中率和时，计算命中率和等效访问周期。等效访问周期。（2）为了使存储系统的访问效率达到）为了使存储系统的访问效率达到0.94，命中率，命中率和等效访问周期应该提高到多少？和等效访问周期应该提高到多少？（3）为了使存储系统的访问效率从）为了使存储系统的访问效率从0.5提高到提高到0.94，块的大小至少增加到几个字？块的大小至少增加到几个字？计算机系统结构总复习习题课件解解:（1）当存储系统的访问效率为）当存储系统的访问效率为0.5时，由表达式时，由表达式可求出命中率为等效访问周期为或由得计算机系统结构总复习习题课件（2）当存储系统的访问效率提高到）当存储系统的访问效率提高到0.

66、94时，命中率时，命中率应该提高到应该提高到H2等效访问周期应提高为或由得计算机系统结构总复习习题课件（3）为了使存储系统的访问效率由0.5提高到0.94，块大小应为B个字。则有在上式中代入相关参数，可求出其中n为Cache的块大小与数据重复使用次数的乘积，H1是原来的命中率，H是块大小增加后的命中率。计算机系统结构总复习习题课件3.5 虚拟存储器与Cache的特点(P146，P172) 虚拟存储器与Cache的主要区别(P173表3.4) Cache的主要组成与工作流程(P173图3.38)2001.9.187计算机系统结构总复习习题课件本章小结(1) 并行存储系统原理；(2) 存储层次的原

67、理及5项性能指标；(3) 存储层次的3种管理方式；(4) 4种地址映象与地址变换方式；(5) 5种替换算法；(6) 堆栈型替换算法；(7) 主存-辅存层次与Cache-主存层次的特点；88计算机系统结构总复习习题课件第四章第四章输入输出系统（输入输出系统（P208） 输输入入输输出出系系统统是计算机系统中实现各种输入输出任务的资源总称。它包括各种输入输出设备、相关的管理软件等等。由于输入输出设备的特殊工作性质使其数据吞吐率通常远低于主机，设计输入输出系统就是要建立数据交换的最佳方案，使双方都能高效率地工作。 本章重点是中断优先级管理、通道流量设计。2001.9.189计算机系统结构总复习习题课

68、件4.1 基本输入输出方式(P212)4.1.1 程序控制I/O方式4.1.2 中断I/O方式4.1.3 DMA方式4.1.4 通道方式4.1.5 I/O处理机方式2001.9.190计算机系统结构总复习习题课件4.2 中断优先级管理(P219) 中断是为实时任务优先获得处理机资源而采用的一种调度技术，当系统中存在多个中断源时必须根据实时性强弱设定优先顺序，这也被称为中断的分级。为了兼顾中断响应的时效与配置的灵活，通常采用两套机制结合组成中断优先序管理体系。 (1)硬件响应优先序：未被屏蔽的几个中断源同时提出申请时，CPU选择服务对象的顺序。它由硬件电路实现，用户不能修改。如P226图4.11

69、所示。 (2)软件服务优先序：在各中断服务程序开头，用软件设置自己的中断屏蔽字（在主程序中也设置）。以此改变实际服务顺序(P230)。 例如某个硬件响应优先级高的中断源，其中断服务程序执行中屏蔽了自身，而开放了某个硬件响应优先级比它低的中断源，后者就可以在前者刚开放中断时就打断它，从而在实际上先得到服务。 中断服务过程示意图如P231图4.14所示。 由于常规用户主程序对处理机的需求紧迫性最低，所以它的中断屏蔽字是“全部开放”。 (3)实例分析：屏蔽字表、中断服务过程图。 例4.1（P230倒数第8行开始）2001.9.191计算机系统结构总复习习题课件4.3 通道处理机(P233)(1)定义

70、： 通道处理机（简称通道）是隶属于主处理机的输入输出专用协处理机。(2)特点： 有一套输入输出功能很强的专用指令系统； 与主处理机共享主存，存放相应的程序和数据； 一个通道可以连接多台外部设备； 主处理机可用启动I/O指令来启动一个通道； 当通道访存与主处理机冲突时，存控部件赋予通道较高的优先权； 通道程序执行完毕自动转入休眠状态，同时向主处理机发出一个特定的中断申请，通知该事件。(3)地位： 从属于主处理机。92计算机系统结构总复习习题课件 字节多路通道：以字节为单位交叉为多台设备传输。子通道的概念。 选择通道：完成一台设备的全部传输再去为另一台设备服务。 数组多路通道：以数组为单位交叉为多

71、台设备传输。(5)通道传输过程的时间分配 (P241，其中P是设备台数)： 字节多路通道： ，其中n是单台设备的数据传输量； 选择通道： 数组多路通道： ，其中k是块尺寸， 。(4)分类(P238)：93计算机系统结构总复习习题课件(6)通道流量分析(P243)： 通道最大能力流量：94计算机系统结构总复习习题课件 通道实际最大负荷流量： 通道正常工作条件：95计算机系统结构总复习习题课件 实例分析：通道时间关系图 例4.2（P243倒数第2行开始）96计算机系统结构总复习习题课件(1)(1)在上表中填出设备相应二次请求传送字节的间隔在上表中填出设备相应二次请求传送字节的间隔时间。时间。(2)

72、(2)当所有设备同时要传送数据时，求其对通道要求当所有设备同时要传送数据时，求其对通道要求的总流量的总流量f fbytebyte设备号号1 12 23 34 45 56 6传送速率送速率(B/ms)(B/ms)505050504040252525251010二次二次请求的求的间隔隔时间(S)(S)例例4.1 4.1 某字节交叉多路通道连接某字节交叉多路通道连接6 6台设备，其数据台设备，其数据传送速率如下表所示。传送速率如下表所示。计算机系统结构总复习习题课件(3)(3)让通道以极限流量让通道以极限流量f fmax.bytemax.byte=f=fbytebyte的工作周期工的工作周期工作，通

73、道的工作周期作，通道的工作周期( (即即TS+TDTS+TD的时间间隔的时间间隔) )是是多少？多少？(4)(4)让通道中所挂设备速率越高的数据传送请求被让通道中所挂设备速率越高的数据传送请求被响应的优先级越高。画出响应的优先级越高。画出6 6台设备同时发送请台设备同时发送请求到下次同时发送请求期间里，通道响应和求到下次同时发送请求期间里，通道响应和处理完各设备请求时刻的示意图。哪个设备处理完各设备请求时刻的示意图。哪个设备丢失了信息？提出一种不丢失信息的解决办丢失了信息？提出一种不丢失信息的解决办法法。计算机系统结构总复习习题课件设备号号1 12 23 34 45 56 6传送速率送速率(B

74、/ms)(B/ms)505050504040252525251010二次二次请求的求的间隔隔时间(S)(S)220 02020252540404040100100解解：(1)(1)(2) (2) 总容量总容量(3)(3) 传送周期传送周期 T TS S+T+TD D=1ms/200B=5S=1ms/200B=5S1234566号设备丢失了一次数据号设备丢失了一次数据20us计算机系统结构总复习习题课件方法方法1：增加通道的最大流量增加通道的最大流量，保证连接在通道，保证连接在通道上的所有设备的数据传送请求能够及时得到通道上的所有设备的数据传送请求能够及时得到通道的响应的响应方法方法2：动态改变

75、设备的优先级动态改变设备的优先级方法方法3：增加一定数量的数据缓冲器增加一定数量的数据缓冲器，特别是对，特别是对优先级比较低的设备优先级比较低的设备计算机系统结构总复习习题课件例例4.2印字机各占一个子通道，印字机各占一个子通道，0号打印机、号打印机、1号打印号打印机和机和0号光电输入机合用一个子通道。假定数据传送号光电输入机合用一个子通道。假定数据传送期内高速印字机每隔期内高速印字机每隔25us发一个请求，低速打印机每发一个请求，低速打印机每隔隔150us发一个字节请求，光电输入机每隔发一个字节请求，光电输入机每隔800us发一发一个字节请求，则这个字节请求，则这5台设备要求通道的实际流量为

76、多台设备要求通道的实际流量为多少？少？字节多路通道字节多路通道0子通道子通道2子通道子通道1子通道子通道0号高速号高速印字机印字机1号高速号高速印字机印字机0号打号打印机印机1号打号打印机印机0号光电号光电输入机输入机计算机系统结构总复习习题课件解：解：5台设备要求通道的数据流量为：台设备要求通道的数据流量为：可将该通道设计成可将该通道设计成0.1MB/s，即所设计的工作周期为：，即所设计的工作周期为：这样各设备的请求就能及时得到响应和处理，不这样各设备的请求就能及时得到响应和处理，不会丢失信息。会丢失信息。计算机系统结构总复习习题课件0号印字机号印字机通道工作周期通道工作周期0us50us1

77、00us150us1号印字机号印字机0号打印机号打印机1号打印机号打印机0号光电机号光电机表示设备提出申请的时刻表示设备提出申请的时刻表示通道处理完设备申请的时刻表示通道处理完设备申请的时刻优先级次序：优先级次序：0号印字机、号印字机、1号印字机、号印字机、0号打印机、号打印机、1号打印机、号打印机、0号光电机号光电机计算机系统结构总复习习题课件例例4.3 4.3 设通道在数据传送期中，选择设备需设通道在数据传送期中，选择设备需4.9S4.9S，传送一个字节数据需，传送一个字节数据需0.lS0.lS。 （1 1）其低速设备每隔）其低速设备每隔250S250S发出一个字节数据发出一个字节数据传送

78、请求，问最多可接多少台这种设备？传送请求，问最多可接多少台这种设备？ （2 2）若有）若有A AE E共共5 5种高速设备，要求字节传送种高速设备，要求字节传送的间隔时间如下表所示，其时间单位为的间隔时间如下表所示，其时间单位为SS。若。若一次通信传送的字节数不少于一次通信传送的字节数不少于10241024个字节，问哪个字节，问哪些设备可挂在此通道上？哪些则不能？些设备可挂在此通道上？哪些则不能？设备A AB BC CD DE E时间间隔隔(S)(S)0.130.130.10.10.110.110.20.20.30.3计算机系统结构总复习习题课件其中，其中，n1024，应使，应使 select

79、 i max select由此可得出通道工作周期为：由此可得出通道工作周期为：T0.1048(us)所以，只有所以，只有A、C、D、E可挂在此通道上，可挂在此通道上，B则不行。则不行。解：解：解：解：(1)(1)(1)(1)低速设备应接字节多路通道低速设备应接字节多路通道低速设备应接字节多路通道低速设备应接字节多路通道 n250/5=50250/5=50250/5=50250/5=50台，所以，台，所以，台，所以，台，所以，n50n50n50n50台，即最多可接台，即最多可接台，即最多可接台，即最多可接50505050台台台台这种设备这种设备这种设备这种设备 (2)(2)(2)(2)根据题意，

80、此通道为选择通道根据题意，此通道为选择通道根据题意，此通道为选择通道根据题意，此通道为选择通道计算机系统结构总复习习题课件本章小结(1) 5种I/O方式；(2) 中断优先级管理（屏蔽字表、中断服务过程图）；(3) 3种通道处理机的特点；(4) 3种通道最大能力流量；(5) 3种通道实际最大负荷流量；(6) 通道正常工作条件；(7) 通道时间关系图（字节多路通道）；习题：P250，题5，题8。2001.9.1106计算机系统结构总复习习题课件第五章第五章 标量流水线技术标量流水线技术( (P253)P253) 本章学习标量计算机上使用的流水加速技术。主要内容有流水技术的分类、流水线性能指标计算、

81、非线性流水线的调度算法。 标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。 流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。 标量计算机上使用的流水加速技术属于指令级并行技术。 每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果5个子过程，也可以分得更细或更粗一些。划分的原则是各部分时间长度大致相等、并使用CPU中不同的部件，这样才有利于多任务重叠处理。107计算机系统结构总复习习题课件5.2流水处理与逻辑相关的概念流水处理与逻辑相关的概念CPU中的各个部件按流水处理顺序

82、连接起来，就称为一条流水线。5.2.1 流水线工作原理 处理机解释程序的方式有顺序方式顺序方式、重叠方式重叠方式、流水方式流水方式等。顺序方式顺序方式是解释完一条指令再开始解释下一条(P254)；流水方式流水方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目(P277)；重叠方式重叠方式是一种简单的流水方式，它把指令分成2个子过程，每条指令只与下一条指令相重叠(P255)。108计算机系统结构总复习习题课件 流水线结构图(P278) 流水线工作时空图(P278P279)109计算机系统结构总复习习题课件110计算机系统结构总复习习题课

83、件5.2.2逻辑相关逻辑相关(P263-276) 相关的定义：(P263倒数第4段) 一条指令必须等待前一条指令解释完成才能开始解释。 相关的分类及其对策1. 全局性相关/局部性相关(P312、P269/P263、P303)；2. 指令相关/数相关(P264/P263)；3. 主存数相关/寄存器数相关(P265/P266)；4. 数值相关/变址值相关(P266/P268)。111计算机系统结构总复习习题课件5.3 5.3 流水技术的分类流水技术的分类( (P280)P280) 线性/非线性(P280)： 部件级/处理机级/处理机间级（宏流水线） (P281)： 单功能/多功能(P282)： 静

84、态/动态(P283)： 标量/向量(P285)： 同步/异步(P285)： 顺序/乱序(P285、P304)：2001.9.1112计算机系统结构总复习习题课件 5.4.1 吞吐率TP(P285) 吞吐率（TP ThroughPut）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。 ，其中k表示流水线划分的段数。 当满足 条件时，有 。5.4 5.4 线性流水线性能分析线性流水线性能分析( (P285)P285)113计算机系统结构总复习习题课件其中5.4.2 5.4.2 加速比加速比( (P288)P288)114计算机系统结构总复习习题课件段效率：，各段平均效率：其中

85、表示第i段设备量占整条流水线全部设备量的百分比。当满足 条件时，有：5.4.3 5.4.3 效率（设备利用率，效率（设备利用率，P289P289）2001.9.1115计算机系统结构总复习习题课件1234 t t3 t t例例5.1带有瓶颈部件的带有瓶颈部件的4功能段流水线功能段流水线,tt1 1=t=t2 2=t=t4 4=t, =t, tt3 3=3t,4=3t,4个任务、个任务、1010个任务时个任务时TPTP，E E、S SP P 。（1）分析法）分析法:各段时间不等各段时间不等TP=TP=ntti i+(n-1)+(n-1)tmaxtmaxi=1m计算机系统结构总复习习题课件STS1

86、S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412341234输出输出=Sp=n*tti imi=1tti i+ +(n-1)(n-1)* *ttj jmI=14*6tt15tt=242415=1.6E=E=n n个任务实际占用的时个任务实际占用的时- -空区空区M M各段总的时各段总的时- -空区空区（2）时空图法）时空图法计算机系统结构总复习习题课件例例5.2以浮点加法运算为例（四段流水线）各段时间相等，以浮点加法运算为例（四段流水线）各段时间相等，求吞吐率、效率。求吞吐率、效率。求求Z=A+B+C+D+E+F+G+H，TP、E、Sp(

87、注意有相关注意有相关)Z=A+B+C+D+E+F+G+H1234567TP=7/15ttE E=7*4/(15*4)=7/1546%Sp=4*7/15=28/15=1.87解解:流水线的效率不高，原因在于存在着数据相关流水线的效率不高，原因在于存在着数据相关, ,有空闲功能段。有空闲功能段。时间时间空间空间1111222233334444555566667777 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15计算机系统结构总复习习题课件例例5.3ASC计算机多功能算术运算流水线各段时间相等，计算机多功能算术运算流水线各段时间相等，6次浮点次浮点加、加、5次定点乘的吞吐率

88、，效率，加速比次定点乘的吞吐率，效率，加速比m=8，n=11分析：分析：T加加=6+(6-1)*1=11(t)T乘乘=4+(5-1)*1=8(t)则则 TP=（6+5）/(11+8)t=11/19tE=(6*6+5*4)t/(19*8t)=36.8%Sp=(6*6+5*4)t/19t=56/19=2.94123456123456123456123456123458671234561 23456时间时间浮加浮加定点乘定点乘一一二二三三 四四 五五一一二二三三 四四 五五一一二二三三 四四五五一一二二三三 四四五五 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

89、 18 19计算机系统结构总复习习题课件题题5.1 5.1 一一条条线线性性流流水水线线有有4 4个个功功能能段段组组成成，每每个个功功能能段段的的延延迟迟时时间间都都相相等等，都都为为tt。开开始始5 5个个tt，每每间间隔隔一一个个tt向向流流水水线线输输入入一一个个任任务务，然然后后停停顿顿2 2个个tt，如如此此重重复复。求求流流水线的实际吞吐率、加速比和效率。水线的实际吞吐率、加速比和效率。解答解答流水线的时空图如下：流水线的时空图如下：计算机系统结构总复习习题课件我我们们可可以以看看出出，在在（11n+111n+1）tt的的时时间间内内，可可以以输输出出5n5n个个结结果果，如如果

90、果指指令令的的序序列列足足够够长长（nn），并并且且指指令令间间不不存存在相关，那么，吞吐率可以认为满足：在相关，那么，吞吐率可以认为满足：加速比为：加速比为：从上面的时空图很容易看出，效率为：从上面的时空图很容易看出，效率为：计算机系统结构总复习习题课件例例5.45.4 用一条用一条5 5个功能段的浮点加法器流水线计算个功能段的浮点加法器流水线计算 每每个个功功能能段段的的延延迟迟时时间间均均相相等等，流流水水线线的的输输出出端端和和输输入入端端之之间间有有直直接接数数据据通通路路，而而且且设设置置有有足足够够的的缓缓冲冲寄寄存存器器。要要求求用用尽尽可可能能短短的的时时间间完完成成计计算算

91、，画画出出流流水水线线时时空空图图，并并计计算算流流水水线线的的实实际吞吐率、加速比和效率。际吞吐率、加速比和效率。 解解答答 首首先先需需要要考考虑虑的的是是，1010个个数数的的的的和和最最少少需需要要做做几几次次加加法法。我我们们可可以以发发现现，加加法法的的次次数数是是不不能能减减少少的的：9 9次次；于于是是我我们们要要尽尽可可能能快快的的完完成成任任务务，就就只只有有考考虑虑如如何何让让流流水水线线尽尽可可能能充满，这这需需要要消消除除前前后后指指令令之之间间的的相相关关。由由于于加加法法满满足足交交换换率率和和结结合合率率，我我们们可可以以调调整整运运算算次次序序如如以以下下的的

92、指指令令序序列列，我我们们把把中中间间结结果果寄寄存存器器称称为为R R，源源操操作作数数寄寄存存器器称称为为A A，最最后后结结果果寄寄存存器器称称为为F F，并并假设源操作数已经在寄存器中，则指令如下：假设源操作数已经在寄存器中，则指令如下：计算机系统结构总复习习题课件I1：R1A1+A2I2：R2A3+A4I3：R3A5+A6I4：R4A7+A8I5：R5A9+A10I6：R6R1+R2I7：R7R3+R4I8：R8R5+R6I9：FR7+R8 这并不是唯一可能的计算方法。假设功能段的延迟这并不是唯一可能的计算方法。假设功能段的延迟为为tt。时空图如下，图中的数字是指令号。时空图如下，图

93、中的数字是指令号。计算机系统结构总复习习题课件 32 1 4 1 1 1 1 2 2 2 2 3 3 3 34 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 921t部件m15432R1=A1+A2R2=A3+A4R3=A5+A6R4=A7+A8R5=A9+A10R6=R1+R2R7=R3+R4R8=R5+R6F=R7+R8R1R3R5R6R7R8FR2R4计算机系统结构总复习习题课件整个计算过程需要整个计算过程需要21t21t，所以吞吐率为：，所以吞吐率为：加速比为：加速比为：效率为：效率为：计算机系统结构总复习习题课件 作作5.

94、55.5 流水线由流水线由4 4个功能部件组成，每个功能部个功能部件组成，每个功能部件的延迟时间为件的延迟时间为t t。当输入。当输入1010个数据后，间歇个数据后，间歇5t 5t ，又输入，又输入1010个数据，如此周期性地工作，个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。求此时流水线的吞吐率，并画出其时空图。 分析分析 所谓输入所谓输入1010个数据后，间歇个数据后，间歇5t5t，又，又输入输入1010个数据的含义应当是以输入时间为基准，个数据的含义应当是以输入时间为基准，即从第即从第1010个数据输入时算起，隔个数据输入时算起，隔5t5t后又开始后又开始输入新的一轮数

95、据。输入新的一轮数据。计算机系统结构总复习习题课件1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 101 21时间(t)部件5t 解答解答 按题意可得按题意可得4 4个功能部件流水时的时空关系如下图所示个功能部件流水时的时空关系如下图所示所以，按周期性工作时的流水线平均吞吐率为所以，按周期性工作时的流水线平均吞吐率为T Tp p=10/(14t)=5/(7t)=10/(14t)=5/(7t)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 164321计算机系统

96、结构总复习习题课件 作作5.65.6 有一个浮点乘流水线如下图有一个浮点乘流水线如下图(a)(a)所示，其乘积可所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实直接返回输入端或暂存于相应缓冲寄存器中，画出实现现A*B*C*DA*B*C*D的时空图以及输入端的变化，并求出该流水的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为下图线的吞吐率和效率；当流水线改为下图(b)(b)形式实现同形式实现同一计算时，求该流水线的效率及吞吐率。一计算时，求该流水线的效率及吞吐率。阶加尾乘规格化t3tt积操作数图(a)阶加尾乘1尾乘2尾乘3规格化积t3tt3t3t图(b)计算机系统

97、结构总复习习题课件 分析分析 为了减少运算过程中的操作数相关，为了减少运算过程中的操作数相关，A*B*C*DA*B*C*D应改为采用应改为采用(A*B)*(C*D) (A*B)*(C*D) 的算法步骤进行运算。的算法步骤进行运算。 解解 按图按图(a)(a)组织，实现组织，实现A*B*C*DA*B*C*D的时空关系如下图的时空关系如下图(A)(A)所示。所示。时间部件输入输出ABCDA*BC*DA*BC*DA*B*C*D13规格化尾乘阶加图(A)吞吐率吞吐率TP=3/(13t)TP=3/(13t)效率效率E=(35t)/(313t)=5/13=38.5%E=(35t)/(313t)=5/13=

98、38.5%计算机系统结构总复习习题课件时间部件输入输出ABCDA*BC*DA*BC*DA*B*C*D规格化尾乘3尾乘2尾乘1阶加图(B)11流水线按图流水线按图(b)(b)组织时，实现组织时，实现A*B*C*DA*B*C*D的时空关系如图的时空关系如图(B)(B)吞吐率吞吐率TP=3/(11t)TP=3/(11t)效率效率E =(35t)/(511t)=3/11=27.3%E =(35t)/(511t)=3/11=27.3%计算机系统结构总复习习题课件例例5.55.5 ( (类类似似题题5.8) 5.8) 一一条条线线性性静静态态多多功功能能流流水水线线由由6 6个个功功能能段段组组成成，加加

99、法法操操作作使使用用其其中中的的1 1、2 2、3 3、6 6功功能能段段，乘乘法法操操作作使使用用其其中中的的1 1、4 4、5 5、6 6功功能能段段，每每个个功功能能段段的的延延迟迟时时间间均均相相等等。流流水水线线的的输输入入端端与与输输出出端端之之间间有有直直接接数数据据通通路路，而而且且设设置有足够的缓冲寄存器。现在用这条流水线计算：置有足够的缓冲寄存器。现在用这条流水线计算：画画出出流流水水线线时时空空图图，并并计计算算流流水水线线的的实实际际吞吞吐吐率率、加加速速比比和和效率。效率。计算机系统结构总复习习题课件解解：为为了了取取得得较较高高的的速速度度，我我们们需需要要一一次次

100、将将乘乘法法作作完完，设设源源操操作作数数存存放放在在寄寄存存器器A A、B B中中，中中间间结结果果存存放放在在寄寄存存器器R R中中，最最后后结结果存放在寄存器果存放在寄存器F F中，则执行的指令序列如下所示：中，则执行的指令序列如下所示：I1I1：R1A1*B1R1A1*B1I2I2：R2A2*B2R2A2*B2I3I3：R3A3*B3R3A3*B3I4I4：R4A4*B4R4A4*B4I5I5：R5A5*B5R5A5*B5I6I6：R6A6*B6R6A6*B6I7I7：R7R1+R2R7R1+R2I8I8：R8R3+R4R8R3+R4I9I9：R9R5+R6R9R5+R6I10I10：

101、R10R7+R8R10R7+R8I11I11：FR9+R10FR9+R10这并不是唯一可能的计算方这并不是唯一可能的计算方法。假设功能段的延迟为法。假设功能段的延迟为tt。时空图（不完全）如。时空图（不完全）如下，图中的数字是指令号。下，图中的数字是指令号。计算机系统结构总复习习题课件1 222t部件m15432R1=A1*B1R2=A2*B2R3=A3*B3R4=A4*B4R5=A5*B5R6=A6*B6R7=R1+R2R8=R3+R4F=R9+R10R1R10R6R7R8F6111332223 434445 6555 6667 87778889R9=R5+R6R10=R7+R8999101

102、0111010111111乘法加法计算机系统结构总复习习题课件作作5.45.4 在一台单流水线多操作部件的处理机上执行下面的程在一台单流水线多操作部件的处理机上执行下面的程序，取指令、指令译码各需要序，取指令、指令译码各需要1 1个时钟周期，个时钟周期，MOVE,ADDTMOVE,ADDT和和MULMUL操作各需要操作各需要2 2个、个、3 3个和个和4 4个时钟周期。每个操作都在第一个时钟周期。每个操作都在第一个时钟周期从寄存器中读取操作数，在最后个时钟周期从寄存器中读取操作数，在最后1 1个时钟周期把个时钟周期把运算结果写到通用寄存器中。运算结果写到通用寄存器中。K：MOVER1,R0;R

103、1R0K+2：ADDR0,R2,R3;R0 (R2)+(R3)K+1：MULR0,R2,R1;R0 (R1)(R2)（1）就程序本身而言，可能有哪几种相关？）就程序本身而言，可能有哪几种相关？（2）在程序实际执行过程中，有哪几种相关会引起流水）在程序实际执行过程中，有哪几种相关会引起流水线的停顿线的停顿?（3）画出指令执行过程的流水线时空图，并计算机执行）画出指令执行过程的流水线时空图，并计算机执行晚这晚这3条指令共使用了多少个时钟周期？条指令共使用了多少个时钟周期？计算机系统结构总复习习题课件K、K+1存在写读相关，读写相关；存在写读相关，读写相关；K+1、K+2存在写写相关。存在写写相关。

104、K：MOVER1,R0;R1R0K+2：ADDR0,R2,R3;R0 (R2)+(R3)K+1：MULR0,R2,R1;R0 (R1)(R2)解解（1）（2）K、K+1的写读相关，会引起流水线的停顿；的写读相关，会引起流水线的停顿；K+1、K+2的写写相关会引起流水线的停顿。的写写相关会引起流水线的停顿。计算机系统结构总复习习题课件IF1ID1RR1 EXE1IF2MD1RR2ID2MD2 MD3IF3ID3WR3RR3FA1I1I2I3时钟周期1 2 3 4 5 6 7 8 9 10（3）WAW WAW(RAW)(RAW)WAW共使用共使用11个个时钟周期时钟周期K：MOVER1,R0;R1

105、R0K+2：ADDR0,R2,R3;R0 (R2)+(R3)K+1：MULR0,R2,R1;R0 (R1)(R2)WR1WR2FA2计算机系统结构总复习习题课件作作5.135.13 一台非流水处理机一台非流水处理机A A的工作时钟频率为的工作时钟频率为25MHz25MHz，它的，它的平均平均CPICPI为为4 4。处理器。处理器B B是是A A的改进型，它有的改进型，它有1 1条条5 5段的线性指段的线性指令流水线。由于锁定电路延迟及时钟扭斜效应，它的工作令流水线。由于锁定电路延迟及时钟扭斜效应，它的工作时钟频率仅为时钟频率仅为20MHz,20MHz,问：问：（1 1）若在）若在A A和和B

106、B两个处理器上执行两个处理器上执行100100条指令的程序，则处条指令的程序，则处理器理器B B对对A A的加速比是多少？的加速比是多少？（2 2）在执行上述程时，计算）在执行上述程时，计算A A，B B处理器各自的处理器各自的MIPSMIPS速率是速率是多少？多少？解解:已知：已知：MIPSB=20计算机系统结构总复习习题课件题题5.25.2 某超标量流水线计算机每个时钟发射两条指令，其某超标量流水线计算机每个时钟发射两条指令，其4 4级指令流水线中包含级指令流水线中包含IF、ID、EXE、WB流水级，各个流水流水级，各个流水段都是花费一个时钟周期。段都是花费一个时钟周期。ALU指令在指令在

107、EXE流水段完成算术流水段完成算术运算，乘除指令比运算，乘除指令比ALU指令多花费指令多花费2个时钟周期，访存指令个时钟周期，访存指令在在EXE功能段完成访存操作。流水中无相关专用通路。指出功能段完成访存操作。流水中无相关专用通路。指出下列指令序列中的数据相关性，分别画出指令流水线在有序下列指令序列中的数据相关性，分别画出指令流水线在有序执行有序写回、无序执行无序写回情况下的时空图。执行有序写回、无序执行无序写回情况下的时空图。1：LOADR0,A;R0主存主存(A)单元单元2：ADDR1,R0;R1 (R1)+(R0)3:LOADR2,B;R2主存主存(B)单元单元4：MULR3,R4;R3

108、 (R3)+(R4)5：ANDR4,R5;R4 (R4)(R5)6：ADDR2,R5;R2 (R2)+(R5)解解（1）相关性分析相关性分析:1、2存在写读相关；存在写读相关；4、5存在读写存在读写相关；相关；3、6存在写读相关；存在写读相关；3、6存在写写相关。存在写写相关。计算机系统结构总复习习题课件IF1ID1 EXE1 WR1IF2顺序WR2EXE2ID2顺序(RAW)顺序 顺序顺序EXE1 MD2WR1IF2ID2EXE2ID1IF1WR2ID1 EXE1IF1WR1ID2MD1 MD2 MD3I1WR2IF2I2I3I4I5I6时钟周期1 2 3 4 5 6 7 8 9 10（2）

109、相关性分析相关性分析:按序发射按序完成之调度按序发射按序完成之调度1：LOADR0,A;R0主存主存(A)单元单元(1,2RAW)2：ADDR1,R0;R1 (R1)+(R0)3:LOADR2,B;R2主存主存(B)单元单元(3,6RAW,WW)4：MULR3,R4;R3 (R3)(R4)(4,5WAR)5：ANDR4,R5;R4 (R4)(R5)6：ADDR2,R5;R2 (R2)+(R5)顺序顺序顺序 顺序(RAW) (RAW) (RAW)(RAW)(RAW)(RAW)(RAW)主共使用主共使用11个时钟周期个时钟周期计算机系统结构总复习习题课件IF1ID1 EXE1 WR1IF2WR2E

110、XE2ID2RAMEXE2MD2MD1WR1IF2ID2EXE2ID1IF1WR2ID1 EXE1IF1WR1ID2I1WR2IF2I3I4I5I2I6时钟周期1 2 3 4 5 6 7 8 9 10（3）相关性分析相关性分析:无序发射无序完成之调度无序发射无序完成之调度1：LOADR0,A;R0主存主存(A)单元单元(1,2RAW)2：ADDR1,R0;R1 (R1)+(R0)3:LOADR2,B;R2主存主存(B)单元单元(3,6RAW),WW4：MULR3,R4;R3 (R3)(R4)(4,5WAR)5：ANDR4,R5;R4 (R4)(R5)6：ADDR2,R5;R2 (R2)+(R5

111、)(RAW)MD3主共使用主共使用7个时钟周期个时钟周期计算机系统结构总复习习题课件IF1ID1 EXE1 WR1IF2WR2EXE2ID2EXE2MD2MD1WR1IF2ID2EXE2ID1IF1WR2ID1 EXE1IF1WR1ID2I1WR2IF2I3I4I5I2I6时钟周期1 2 3 4 5 6 7 8 9 10（4）相关性分析相关性分析:无序发射无序完成之调度（设置专用数据通路）无序发射无序完成之调度（设置专用数据通路）1：LOADR0,A;R0主存主存(A)单元单元(1,2RAW)2：ADDR1,R0;R1 (R1)+(R0)3:LOADR2,B;R2主存主存(B)单元单元(3,6

112、RAW),WW4：MULR3,R4;R3 (R3)(R4)(4,5WAR)5：ANDR4,R5;R4 (R4)(R5)6：ADDR2,R5;R2 (R2)+(R5)MD3主共使用主共使用7个时钟周期个时钟周期计算机系统结构总复习习题课件作作5.17在在CRAY-1机上，设向量长度均为机上，设向量长度均为64，所有浮点功能，所有浮点功能部件的执行时间分别为：相加需部件的执行时间分别为：相加需6拍，相乘需拍，相乘需7拍，求倒数近拍，求倒数近似值需似值需14拍，从存储器读数据需拍，从存储器读数据需6拍，打入寄存器机启动功拍，打入寄存器机启动功能部件各需能部件各需1拍，问下列个指令组，组内的哪些指令可

113、以链拍，问下列个指令组，组内的哪些指令可以链接？，哪些指令不可以链接？不能链接的原因是什么？并分接？，哪些指令不可以链接？不能链接的原因是什么？并分别计算各指令组全部完成所需的拍数。别计算各指令组全部完成所需的拍数。（1 1） V0存储器存储器 （2） V2 V0 V1 V1 V2 V3V3存储器存储器 V4 V5V6V4 V2 V3（3） V0存储器存储器 （4） V2 存存储器器 V2 V0 V1V11/V0V3 V2 V0V3 V1 V2V5 V3 V4V5 V3 V4计算机系统结构总复习习题课件解：解：组（1 1）三条指令可并行）三条指令可并行执行。行。 T=1+7+1+64-1=72

114、(T=1+7+1+64-1=72(拍拍) )。组（2 2）前前二二条条指指令令可可并并行行执行行，前前两两条条与与第第三三条条指指令令可可链接接执行。行。 T=T=（1+7+1+1+6+11+7+1+1+6+1）+63=80+63=80（拍）。（拍）。组（组（3）前前3条指令可链接执行，后一条指令只能串行（加法条指令可链接执行，后一条指令只能串行（加法部件冲突）部件冲突）T=（8+9+8+63）+8+63=159（拍）。（拍）。组（组（4）前二条指令可并行前二条指令可并行执行，后两条可行，后两条可链接，接，这样前两前两条与后两条与后两条指令可链接执行。条指令可链接执行。T=（14）+（9）+(

115、8)+63=94（拍）。（拍）。计算机系统结构总复习习题课件题题5.3对于以下计算表达式对于以下计算表达式:I=A+B+C+DEF+G+H其中其中A,B,I都是寄存器名。都是寄存器名。（1）指出其中的并行性，即哪些操作可以并行执）指出其中的并行性，即哪些操作可以并行执行；行；（2）对于采用）对于采用5级指令流水线的计算机，试安排级指令流水线的计算机，试安排完成表达式计算的操作顺序，并写出指令序列，完成表达式计算的操作顺序，并写出指令序列，使得流水线的停顿时间最少；使得流水线的停顿时间最少；（3）对于一台）对于一台VLIW计算机，假定其有计算机，假定其有2个加法个加法部件和一个乘法部件，都能在一

116、个流水周期中完部件和一个乘法部件，都能在一个流水周期中完成计算，试将上述表达式用最少的超长指令序列成计算，试将上述表达式用最少的超长指令序列表示。表示。计算机系统结构总复习习题课件解（1）I=A+B+C+DEF+G+H可并行操作的运算为：可并行操作的运算为：A+B+C+G+HDEF（3） A+B，G+H，DE A+B+C，DEF A+B+C+G+H A+B+C+G+H+DEF计算机系统结构总复习习题课件IF2ID EXE1WRMEMWREXEIDMD1 MD2IF3IDIF6（2）2:R1E6:R0D *EWRMEMMD3 MEM3:R2GIF8ID EXE4WRMEMWREXEIDEXEIF

117、9IDIF1810:R7C9:R3 A+BWRMEMMEM8:R6FIF1IDEXEWRMEM1:R0DIF5ID EXE1WRMEMWREXEIDIF75:R4BMEM7:R5HIF4IDEXEWRMEM4:R3AEXEIDIF10WRMEMEXEIDIF14WRMEM12:R5D*E*FMD1 MD2IDIF12WRMD3 MEM11:R3G+HEXEIDIF11WRMEM14:R3A+B+C18:R3A+B+C+R5共用共用21个时钟周期，有个时钟周期，有4个个时钟周期的停顿时钟周期的停顿计算机系统结构总复习习题课件本章小结本章小结(1) 流水处理与相关的概念；(2) 时空图画法及其应用；(3) 7种流水线分类方法；(4) 3个流水线性能指标；(5) 2种“瓶颈”解决方法；2001.9.1147计算机系统结构总复习习题课件再见再见2001.9.1148计算机系统结构总复习习题课件