《《计算机系统结构》总复习-习题.ppt》由会员分享，可在线阅读，更多相关《《计算机系统结构》总复习-习题.ppt（103页珍藏版）》请在三一办公上搜索。
1、1,计算机系统结构,总复习,2,第一章 基本概念（P1）,本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。定量知识：对计算机性能进行定量评价的几个重要公式。,3,本章重点,本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下：(1)Amdahl定律；(2)平均周期数CPI公式，程序执行时间Te公式；(3)每秒百万指令数MIPS公式，每秒百万浮点数MFLOPS公式。,4,1.定量知识3个性能公式,1.1 Amdahl定律（加快经常性事件原理，P9）,其中：Sn 全局加速比；To 原执行时间（old）；T
2、n 新执行时间（new）；Se 被改进部分的局部加速比；Fe 被改进部分原执行时间占原来总时间的百分比。,5,Amdahl定律的推导,6,Amdahl定律的图形,从图1.2可以看出，增大Se和Fe对Sn都有提升作用；但当Fe固定时，一味增大Se对Sn的作用会越来越不显著。,7,作1.12 假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍，将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。（1）求出加速比S和向量化百分比之间的关系式作1.13（2）当要得到加速比为2时的可向量化百分比F为多少？作1.14（3）为了获得在向量模式所得到的最大加
3、速比的一半，可向量化百分比F为多少？,8,(2)由（1）式有,解（1）：由Amdahl定律知,(1),9,(3)由题意可知,10,作1.17 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90，则采用Cache后，能使整个存储系统获得多高的加速比？,解：fe=0.9，re=5,11,1.2 CPI与程序执行时间Te（P11）,CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，易知,12,1.3 每秒百万指令数MIPS与每秒百万浮点数MFLOPS（P11）,例题：P10，例1.1例1.5。P33
4、，题12，题13，题14。,13,例1.19 用一台4OMHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型 指令条数 时钟周期数整数运算 45000 1数据传送 32000 2浮点运算 15000 2控制传送 8000 2求有效CPI、MIPS速率和程序的执行时间。,14,解：依题意可知 IN=105条，n=4,15,作1.20 某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个巳知混合程序。假定每次存储器存取为1周期延迟、试问：(1)此计算机的有效CPI是多少?(2)假定将处理机的时钟提高到30MHz，但存储器子 系统速率不变。这样，每
5、次存储器存取需要两个时钟 周期。如果30指令每条只需要一次存储存取，而另 外5每条需要两次存储存取，还假定已知混合程序 的指令数不变，并与原工作站兼容，试求改进后的处 理机性能。,解(1),16,(2)依题意可知：30%的指令需要一次存储存取，则这些指令在处理器提高时钟频率之后需要增加1个时钟周期；另外5%的指令需要增加2个时钟周期。,改进后性能提高情况可用CPU时间之比表示：,17,作1.21 假设在一台40MHz处理机上运行200 000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：,(1)计算在单处理机上用上述踪数据运行程序的平
6、均CPI(2)根据(1)所得CPI，计算相应的MIPS 速率和程序的执行时间,18,解：依题意可知 IN=2105条，n=4，,19,第二章 指令系统（P36）,本章介绍指令系统设计中2个最基本的内容：数据表示、操作码优化。,本章重点,(1)Huffman编码方法；(2)等长扩展编码方法（15/15/15法，8/64/512法）；(3)编码方法性能指标（平均码长L，信息冗余量R）。,20,2.1 Huffman压缩编码（P91）,(1)Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分配，可使平均
7、码长达到最低。(2)Huffman编码方法 这种编码方法由两个过程组成。频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树 Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就较少，符合Hu
8、ffman压缩原则。上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。,21,平均码长：各事件编码长度的数学期望。,信息冗余量：它表明消息编码中“无用成分”所占的百分比。,22,2.2 扩展编码方法（等长扩展法，P94-95）,用码长表示：例如4-8-12法。这并不能说明具体编码方法，例如下面两种编码方法都是4-8-12法。用码点数表示：例如15/15/15法，8/64/512法15/15/15法，每一种码长都有4位可编码位（前头可以有相同的扩展标识前缀），可产生16个码点（即编码组合），但是至多只能使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识
9、前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是“非前缀原则”。8/64/512法，每一种码长按4位分段，每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。,23,1,0,0,0,0,0,0,1,1,1,0.09,0.15,1,0.06,1,0.03,0.03,0.04,0.05,0.15,0.30,0.40,I7 I6 I5 I4 I3 I2 I1,例2.1 某指令系统各指令使用频度如下：I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.
10、05 0.04 0.03 0.03 1.Huffman编码,24,由此可得到哈夫曼编码如下：I1:0 I2:10 I3:110 I4:11100 I5:11101 I6:11110 I7:11111 平均码长L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5+0.03*5+0.03*5=2.20位 信息冗余量R=(2.20-2.17)/2.20=1.36%指令长度个数=4,25,2.扩展哈夫曼编码I1,I2,I3 用两位:00,01,10I4,I5,I6,I7 用四位:1100,1101,1110,1111L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+
11、0.03)*4=2.30位信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%,26,操作码的扩展（等长扩展）,平均码长：2.2 2.3,27,作 2.13 采用最优Huffman编码法（信息熵）的操作码最短平均长度为：,28,29,例2.2 指令系统共有42种指令，前15种使用频率平均为0.05，中间13种使用频率平均为0.015，最后14种使用频率平均为0.004。如何编码？,解：因频率分布有三种，故码长可有三种；,因每段指令数基本相同，故可采用等长扩展(4-8-12位)，保留特征码的每段指令数相同(15-15-15)方法。结果如图所示；,结果：采用15-15-15扩展方
12、法，最后一种编码用于扩展，每段00001110用于编码，1111用于扩展。,30,例2.3 某模型机有9条指令，其使用频率为：ADD（加）30%SUB（减）24%JOM（按负转移）6%STO（存）7%JMP（转移）7%SHR（右移）2%CIL（循环左移）3%CLA（清加）20%STP（停机）1%要求有两种指令字长，都按双操作数指令格式编,采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存为16位宽，按字节编址，采用整数边界存贮，任何指令都在一个主存周期中取得，短指令为寄存器寄存器型，长指令为寄存器主存型，主存地址应能变址寻址。,31,解：(1)Huffman树的形式如图
13、所示。,0.01,0.02,0.03,0,1,0.03,0.06,0,1,0.06,0.12,0,1,0.07,0.07,0.14,0,1,0.26,0,1,0,0.30,0.20,0.24,0.44,0,1,0.56,1,0,0,1,1,32,由上图可得到的Huffman编码为：ADD(加)30%01 SUB(减)24%11 CLA(清加)20%10 JOM(按负转移)6%0001 STO(存)7%0011 JMP(转移)7%0010 CIL(循环左移)3%00001 SHR(右移)2%000001 STP(停机)1%000000因此，操作码的平均码长为：,33,(2)采用2-5扩展的操作码
14、编码为：ADD(加)30%00 SUB(减)24%01 CLA(清加)20%10 JOM(按负转移)6%11000 STO(存)7%11001 JMP(转移)7%11010 SHR(右移)2%11011 CIL(循环左移)3%11100 STP(停机)1%11101因此，操作码的平均码长为：,34,(3)该机允许使用的可编址的通用寄存器个数为23=8个(4)短指令为寄存器-寄存器型，格式如下：,OP(2位),R1(3位),R2(3位),OP(5位),R1(3位),X(2位),相对位移d(6位),(5)访主存操作数地址寻址的最大相对位移量为64个字节(-32+31个字节),长指令为寄存器-主存型
15、，格式如下：,35,作2.14 一台模型机共有7条指令，各指令的使用频度分别是35、25、20、10、5、3、2，有8个通用数据寄存器，2个变址寄存器。(1)要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。(2)设计8位字长的寄存器寄存器型指令3条，16位字长的寄存器存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出各字段的长度和操作码的编码。,36,答:(1)要使得到的操作码长度最短，应采用Huffman编码，Huffman树构造如下,37,由此可以得到7条指令的编码分别如下：,这样，Huffman编码法得到的操作码的平均长度为：l=
16、2(0.35+0.25+0.20)+30.10+4 0.05+5(0.03+0.02)=1.6+0.3+0.2+0.25=2.35,指令号出现的频率编码135%00225%01320%10410%11055%111063%1111072%11111,38,39,作2.14(改）一台模拟机共有7条指令，各指令的使用频度分别为35%，25%，20%，10%，5%，3%，2%。该模拟机有8位和16位两种指令长，采用2-4扩展操作码，8位字长指令为寄存器-寄存器（R-R）二地址类型，16位字长指令为寄存器-存贮器（R-M）二地址变址寻址（-128变址范围127）类型。(1)计算操作码的平均码长(2)该
17、机允许使用多少个可编址的通用寄存器，多少个变址寄存器？设计该机的两种指令格式，标出各字段位数并给出操作码编码。,40,扩展码有2种方案（下图）00 00013条 01 2条10 10001100 100111014条 10105条1110 10111111 1100(3-7型）（2-8 型）简版,41,2-4扩展码有2种方案（上图）前一种方案里短指令占的比例较大，应该选用它。平均码长/L=(0.35+0.25+0.20)2+(0.1+0.05+0.03+0.02)4=2.4 用R代表寄存器编号，A代表变址偏移量。题目未指明R-R型R-M型谁是短码，所以先列出2种方案：,42,8 位:操作码 2
18、,寄存器（8-2)/2=3（右边为 操作码4 位）16位：操作码 2,寄存器 3，变址寻址（-128变址范围127）：27=128，符号1位，共 8位，变址器：16-4-3-8=1,43,2.2.2 操作数优化寻址方式比较（P95）,指令中操作数占用的位数由操作数的个数与寻址方式决定。按操作数的个数划分，有零操作数指令、一操作数指令、二操作数指令、三操作数指令共四种形式。应该按机器用途来选择（P99，表2.20）。缩短操作数长度的常用方法是间址和变址（P99页末）。,44,作2.15 某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令三类，并假设每个地址字段的长度为6位。（1）如
19、果双地址指令有15条，单地址和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。（2）如果三类指令的比例为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。,45,46,解：,（1）双地址指令15条，地址码：00001110 单地址指令26163条，地址码：1111 000000 1111 111110零地址指令64条，地址码：1111 111111 000000 1111 111111 111111,47,48,第三章 存储系统（P130）,长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上CPU的发
20、展，容量不能满足软件尺寸扩大。本章学习两种提高主存系统性能/价格比的结构化方法：并行存储器与存储层次技术。后者为主。,49,例3.1 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90，则采用Cache后，能使整个存储系统获得多高的加速比？解：,50,例3.2 假设高速缓存Cache的访问周期为50ns，主存的访问周期为400ns，且Cache被访问命中的概率为95，则采用Cache后，能使整个存储系统等效的访问周期为多少？获得多高的加速比？解：,51,第四章 输入输出系统（P208）,输入输出系统是计算机系统中实现各种输入输出任务的资源总称。它包括各种输入输出设备
21、、相关的管理软件等等。由于输入输出设备的特殊工作性质使其数据吞吐率通常远低于主机，设计输入输出系统就是要建立数据交换的最佳方案，使双方都能高效率地工作。本章重点是中断优先级管理、通道流量设计。,52,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处理机方式,53,4.2 中断优先级管理(P219),中断是为实时任务优先获得处理机资源而采用的一种调度技术，当系统中存在多个中断源时必须根据实时性强弱设定优先顺序，这也被称为中断的分级。为了兼顾中断响应的时效与配置的灵活，通常采用两套机制结合组
22、成中断优先序管理体系。(1)硬件响应优先序：未被屏蔽的几个中断源同时提出申请时，CPU选择服务对象的顺序。它由硬件电路实现，用户不能修改。如P226图4.11所示。(2)软件服务优先序：在各中断服务程序开头，用软件设置自己的中断屏蔽字（在主程序中也设置）。以此改变实际服务顺序(P230)。例如某个硬件响应优先级高的中断源，其中断服务程序执行中屏蔽了自身，而开放了某个硬件响应优先级比它低的中断源，后者就可以在前者刚开放中断时就打断它，从而在实际上先得到服务。中断服务过程示意图如P231图4.14所示。由于常规用户主程序对处理机的需求紧迫性最低，所以它的中断屏蔽字是“全部开放”。(3)实例分析：屏
23、蔽字表、中断服务过程图。例4.1（P230倒数第8行开始）,54,作业4.5 已知中断服务请求次序为 1-2-3-4，现改为3-2-4-1，（1）设计中断屏蔽码（2）处理机运行主程序时，同时D1和D2q请求中断，而在运行中断源D2时，D3和D4又同时请求，请画出程序运行过程示意图解：(1)中断屏蔽字表如下图；(令1对应屏蔽，0对应开放),55,(2)中断过程示意图如下图。,例 4.1 设中断级屏蔽位为“0”对应于开放，1对应于屏蔽，各级中断处理程序的中断级屏蔽位设置如下：(1)当中断响应的优先次序为1、2、3、4，其中断处理次序是什么？(2)所有的中断处理各需要3个单位时间，当正在运行用户程序
24、时，同时出现第2、3级中断请求，过2个单位时间，又同时出现第1、4级中断请求，请画出程序运行过程示意图。,【解答】(1)当中断响应的优先次序为1、2、3、4，其中断处理次序是1、3、4、2。,(2)运行过程示意图如下：,58,4.3 通道处理机(P233),(1)定义：通道处理机（简称通道）是隶属于主处理机的输入输出专用协处理机。(2)特点：有一套输入输出功能很强的专用指令系统；与主处理机共享主存，存放相应的程序和数据；一个通道可以连接多台外部设备；主处理机可用启动I/O指令来启动一个通道；当通道访存与主处理机冲突时，存控部件赋予通道较高的优先权；通道程序执行完毕自动转入休眠状态，同时向主处理
25、机发出一个特定的中断申请，通知该事件。(3)地位：从属于主处理机。,59,字节多路通道：以字节为单位交叉为多台设备传输。子通道的概念。选择通道：完成一台设备的全部传输再去为另一台设备服务。数组多路通道：以数组为单位交叉为多台设备传输。(5)通道传输过程的时间分配(P241，其中P是设备台数)：字节多路通道：，其中n是单台设备的数据传输量；选择通道：数组多路通道：，其中k是块尺寸，。,(4)分类(P238)：,60,(6)通道流量分析(P243)：,通道最大能力流量：,61,通道实际最大负荷流量：,通道正常工作条件：,62,实例分析：,通道时间关系图P243 例 4.1 倒数第2行开始,63,(
26、1)在上表中填出设备相应二次请求传送字节的间隔时间。(2)当所有设备同时要传送数据时，求其对通道要求的总流量fbyte,例4.1 某字节交叉多路通道连接6台设备，其数据传送速率如下表所示。,64,(3)让通道以极限流量fmax.byte=fbyte的工作周期工作，通道的工作周期(即TS+TD的时间间隔)是多少？(4)让通道中所挂设备速率越高的数据传送请求被响应的优先级越高。画出6台设备同时发送请求到下次同时发送请求期间里，通道响应和处理完各设备请求时刻的示意图。哪个设备丢失了信息？提出一种不丢失信息的解决办法。,65,解：(1),(2)总容量(3)传送周期 TS+TD=1ms/200B=5S,
27、1,2,3,4,5,6,6号设备丢失了一次数据,20us,66,方法1：增加通道的最大流量，保证连接在通道上的所有设备的数据传送请求能够及时得到通道的响应方法2：动态改变设备的优先级方法3：增加一定数量的数据缓冲器，特别是对优先级比较低的设备,67,例4.2 印字机各占一个子通道，0号打印机、1号打印机和0号光电输入机合用一个子通道。假定数据传送期内高速印字机每隔25us发一个请求，低速打印机每隔150us发一个字节请求，光电输入机每隔800us发一个字节请求，则这5台设备要求通道的实际流量为多少？,字节多路通道,0子通道,2子通道,1子通道,0号高速印字机,1号高速印字机,0号打印机,1号打
28、印机,0号光电输入机,68,解：5台设备要求通道的数据流量为：,可将该通道设计成0.1MB/s，即所设计的工作周期为：,这样各设备的请求就能及时得到响应和处理，不会丢失信息。,69,0号印字机,通道工作周期,0us 50us 100us 150us,1号印字机,0号打印机,1号打印机,0号光电机,表示设备提出申请的时刻 表示通道处理完设备申请的时刻优先级次序：0号印字机、1号印字机、0号打印机、1号打印机、0号光电机,70,例4.3 设通道在数据传送期中，选择设备需4.9S，传送一个字节数据需0.lS。（1）其低速设备每隔250S发出一个字节数据传送请求，问最多可接多少台这种设备？（2）若有A
29、E共5种高速设备，要求字节传送的间隔时间如下表所示，其时间单位为S。若一次通信传送的字节数不少于1024个字节，问哪些设备可挂在此通道上？哪些则不能？,71,其中，n1024，应使select i maxselect由此可得出通道工作周期为：T0.1048(us)所以，只有A、C、D、E可挂在此通道上，B则不行。,解：(1)低速设备应接字节多路通道,n 250/5=50台，所以，n50台，即最多可接50台这种设备,(2)根据题意，此通道为选择通道,72,本章小结,(1)5种I/O方式；(2)中断优先级管理（屏蔽字表、中断服务过程图）；(3)3种通道处理机的特点；(4)3种通道最大能力流量；(5
30、)3种通道实际最大负荷流量；(6)通道正常工作条件；(7)通道时间关系图（字节多路通道）；习题：P250，题5，题8。,73,第五章 标量流水线技术(P253),本章学习标量计算机上使用的流水加速技术。主要内容有流水技术的分类、流水线性能指标计算、非线性流水线的调度算法。标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。标量计算机上使用的流水加速技术属于指令级并行技术。每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果5个子过
31、程，也可以分得更细或更粗一些。划分的原则是各部分时间长度大致相等、并使用CPU中不同的部件，这样才有利于多任务重叠处理。,74,5.2 流水处理与逻辑相关的概念,CPU中的各个部件按流水处理顺序连接起来，就称为一条流水线。5.2.1 流水线工作原理 处理机解释程序的方式有顺序方式、重叠方式、流水方式等。顺序方式是解释完一条指令再开始解释下一条(P254)；流水方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目(P277)；重叠方式是一种简单的流水方式，它把指令分成2个子过程，每条指令只与下一条指令相重叠(P255)。,75,流水线结构
32、图(P278),流水线工作时空图(P278P279),76,77,5.2.2 逻辑相关(P263-276),相关的定义：(P263倒数第4段)一条指令必须等待前一条指令解释完成才能开始解释。相关的分类及其对策1.全局性相关/局部性相关(P312、P269/P263、P303)；2.指令相关/数相关(P264/P263)；3.主存数相关/寄存器数相关(P265/P266)；4.数值相关/变址值相关(P266/P268)。,78,5.3 流水技术的分类(P280),线性/非线性(P280)：部件级/处理机级/处理机间级（宏流水线）(P281)：单功能/多功能(P282)：静态/动态(P283)：标
33、量/向量(P285)：同步/异步(P285)：顺序/乱序(P285、P304)：,79,5.4.1 吞吐率TP(P285)吞吐率（TP ThroughPut）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。，其中k表示流水线划分的段数。当满足 条件时，有。,5.4 线性流水线性能分析(P285),80,其中,5.4.2 加速比(P288),81,段效率：，各段平均效率：其中 表示第i段设备量占整条流水线全部设备量的百分比。当满足 条件时，有：,5.4.3 效率（设备利用率，P289）,82,1,2,3,4,t t 3t t,例5.1 带有瓶颈部件的4功能段流水线,t1=t2
34、=t4=t,t3=3t,4个任务、10个任务时TP，E、SP。,（1）分析法:各段时间不等,83,S,T,S1,S2,S3,S4,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t12,t13,t14,t15,1,2,3,4,t11,1,2,3,4,1,2,3,4,1,2,3,4,输出,（2）时空图法,84,例5.2 以浮点加法运算为例（四段流水线）各段时间相等，求吞吐率、效率。求Z=A+B+C+D+E+F+G+H，TP、E、Sp(注意有相关),解:,流水线的效率不高，原因在于存在着数据相关,有空闲功能段。,85,例5.3 ASC计算机多功能算术运算流水线各段时间相等，6次浮点加
35、、5次定点乘的吞吐率，效率，加速比 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/19t E=(6*6+5*4)t/(19*8t)=36.8%Sp=(6*6+5*4)t/19t=56/19=2.94,1,2,3,4,5,8,6,7,1,2,3,4,5,6,时间,浮加,定点乘,一,二,三,四,五,一,二,三,四,五,一,二,三,四,五,一,二,三,四,五,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,86,作业5.7 p343 一条线性流水线有4个功能段
36、组成，每个功能段的延迟时间都相等，都为t。开始5个t，每间隔一个t向流水线输入一个任务，然后停顿2个t，如此重复。求流水线的实际吞吐率、加速比和效率。,解答流水线的时空图如下：,87,我们可以看出，在（11n+1）t的时间内，可以输出5n个结果，如果指令的序列足够长（n），并且指令间不存在相关，那么，吞吐率可以认为满足：加速比为：从上面的时空图很容易看出，效率为：,88,作业 5.8 用一条5个功能段的浮点加法器流水线计算 每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、
37、加速比和效率。解答首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：,89,I1：R1A1+A2I2：R2A3+A4I3：R3A5+A6I4：R4A7+A8I5：R5A9+A10I6：R6R1+R2I7：R7R3+R4I8：R8R5+R6I9：FR7+R8 这并不是唯一可能的计算
38、方法。假设功能段的延迟为t。时空图如下，图中的数字是指令号。,90,3,2,1,4,1,1,1,1,2,2,2,2,3,3,3,3,4,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,9,21t,部件m,1,5,4,3,2,R1=A1+A2,R2=A3+A4,R3=A5+A6,R4=A7+A8,R5=A9+A10,R6=R1+R2,R7=R3+R4,R8=R5+R6,F=R7+R8,R1,R3,R5,R6,R7,R8,F,R2,R4,91,整个计算过程需要21t，所以吞吐率为：加速比为：效率为：,92,作业 5.9(类似题5.8)一条
39、线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算：画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。,93,解：为了取得较高的速度，我们需要一次将乘法作完，设源操作数存放在寄存器A、B中，中间结果存放在寄存器R中，最后结果存放在寄存器F中，则执行的指令序列如下所示：I1：R1A1*B1I2：R2A2*B2I3：R3A3*B3I4：R4A4*B4I5：R5A5*B5I6：R6A6*B6I7：R7R1+R
40、2I8：R8R3+R4I9：R9R5+R6I10：R10R7+R8I11：FR9+R10,这并不是唯一可能的计算方法。假设功能段的延迟为t。时空图（不完全）如下，图中的数字是指令号。,94,1,2,22t,部件m,1,5,4,3,2,R1=A1*B1,R2=A2*B2,R3=A3*B3,R4=A4*B4,R5=A5*B5,R6=A6*B6,R7=R1+R2,R8=R3+R4,F=R9+R10,R1,R10,R6,R7,R8,F,6,1,1,1,3,3,2,2,2,3,4,3,4,4,4,5,6,5,5,5,6,6,6,7,8,7,7,7,8,8,8,9,R9=R5+R6,R10=R7+R8,9
41、,9,9,10,10,11,10,10,11,11,11,乘法,加法,95,整个计算过程需要22t，所以吞吐率为：加速比为：效率为：,96,例5.4 有一个浮点乘流水线如下图(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A*B*C*D的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为下图(b)形式实现同一计算时，求该流水线的效率及吞吐率。,阶加,尾乘,规格化,t,3t,t,积,操作数,图(a),阶加,尾乘1,尾乘2,尾乘3,规格化,积,t,3t,t,3t,3t,图(b),97,分析为了减少运算过程中的操作数相关，A*B*C*D应改为采用(A*B)*(C*
42、D)的算法步骤进行运算。解按图(a)组织，实现A*B*C*D的时空关系如下图(A)所示。,时间,部件,输入,输出,AB,CD,A*B,C*D,A*BC*D,A*B*C*D,13,规格化尾乘阶加,图(A),吞吐率TP=3/(13t)效率E=(35t)/(313t)=5/13=38.5%,98,时间,部件,输入,输出,AB,CD,A*B,C*D,A*BC*D,A*B*C*D,规格化尾乘3尾乘2尾乘1阶加,图(B),11,流水线按图(b)组织时，实现A*B*C*D的时空关系如图(B)吞吐率TP=3/(11t)效率E=(35t)/(511t)=3/11=27.3%,99,本章小结,(1)流水处理与相关
43、的概念；(2)时空图画法及其应用；(3)7种流水线分类方法；(4)3个流水线性能指标；(5)2种“瓶颈”解决方法；,100,第七章 互连网络1.设16个处理机的编号分别为0、1、15，采用单级互连网络。互连函数分别为：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal第12号处理机分别与哪一个处理机相连？,101,解：(12)10下=(1100)2下1100最高位取反得0100，4号处理机(12+8)MOD 16=4，4号处理机12 1=11，11号处理机1100循环左移1位得到1001,9号处理机1100的最高最低位交换0101,5号处理机1100的位序反过来为0011,3号处理机,102,作业 7.3 已知输入端编号13=1101B。(1)Cube3(1101B)=0101B=5(2)PM2+3(13)=(13+23)mod 16=21 mod 16=5(3)PM2+0(13)=(13-20)mod 16=12(4)Shuffle(1101B)=1011B=11(5)Shuffle(Shuffle(1101B)=Shuffle(1011B)=0111B=7,103,再见,
