计算机系统结构课后习题

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

1、课后习题第一章计算机系统结构的基本概念1 . 有- - 个计算机系统可按功能分成4级，每级的指令互不相同，每一级的指令都比其下一级的指令在效能上强M倍，即第i级的一条指令能完成第i - 1级的M条指令的计算量。现若需第i级的N条指令解释第i + 1级的一条指令，而有一段第1级的程序需要运行K s ,问在第2、3和4级上一段等效程序各需要运行多长时间？答 ： 第2级上等效程序需运行： (N/*K s。第3级上等效程序需运行：(N/M) * (N/M) *Ks。第 4 级上等效程序需运行：(N/ * (N/M) * (N/M) *Ks。note: 由题意可知：第i级的一条指令能完成第i - 1级的

2、M条指令的计算量。而现在第i级有N条指令解释第i + 1级的一条指令，那么，我们就可以用N /M来表示N /M表示第i + 1级需(N/M )条指令来完成第i级的计算量。所以，当有一段第1级的程序需要运行K s时，在第2级就需要(N/M) K s ,以此类推2 . 硬件和软件在什么意义上是等效的？在什么意义上又是不等效的？试举例说明。答： 软件和硬件在逻辑功能上是等效的，原理上，软件的功能可用硬件或固件完成， 硬件的功能也可用软件模拟完成。但是实现的性能价格比，实现的难易程序不同。在D O S操作系统时代，汉字系统是一个重要问题，早期的汉字系统的字库和处理程序都固化在汉卡( 硬件) 上，而随着

3、CPU、硬盘、内存技术的不断发展，UCDOS把汉字系统的所有组成部份做成一个软件。3 . 试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系与影响。答： 计算机系统结构、计算机组成、计算机实现互不相同，但又相互影响。( 1 )计算机的系统结构相同， 但可采用不同的组成。 如1BM370系列有115、125、135、158、1 6 8等由低档到高档的多种型号机器。从汇编语言、机器语言程序设计者看到的概念性结构相同，均是由中央处理机/ 主存，通道、设备控制器，外 设4级构成。其中，中央处理机都有相同的机器指令和汇编指令系统，只是指令的分析、执行在低档机上采用顺序进行，在高档机上采用重

4、叠、流水或其它并行处理方式。(2)相同的组成可有多种不同的实现。如主存器件可用双极型的，也可用MOS型的；可用VLS工单片，也可用多片小规模集成电路组搭。(3)计算机的系统结构不同，会使采用的组成技术不同，反之组成也会影响结构。如为实 现A:=B+CD:=E*F,可采用面向寄存器的系统结构，也可采用面向主存的三地址寻址方式的系统结构。要提高运行速度，可让相加与相乘并行，为此这两种结构在组成上都要求设置独立的加法器和乘法器。但对面向寄存器的系统结构还要求寄存器能同时被访问，而对面向主存的三地址寻址方式的系统结构并无此要求，倒是要求能同时形成多个访存操作数地址和能同时访存。又如微程序控制是组成影响

5、结构的典型。通过改变控制存储器中的微程序，就可改变系统的机器指令，改变结构。如果没有组成技术的进步，结构的进展是不可能的。综上所述， 系统结构的设计必须结合应用考虑， 为软件和算法的实现提供更多更好的支持,同时要考虑可能采用和准备采用的组成技术。应避免过多地或不合理地限制各种组成、实现技术的采用和发展，尽量做到既能方便地在低档机上用简单便宜的组成实现，又能在高档机上用复杂较贵的组成实现，这样，结构才有生命力；组成设计上面决定于结构，下面受限于实现技术。然而，它可与实现折衷权衡。例如，为达到速度要求，可用简单的组成但却是复杂的实现技术，也可用复杂的组成但却是一般速度的实现技术。前者要求高性能的器

6、件，后者可能造成组成设计复杂化和更多地采用专用芯片。组成和实现的权衡取决于性能价格比等因素；结构、组成和实现所包含的具体内容随不同时期及不同的计算机系统会有差异。 软件的硬化和硬件的软件都反映了这一事实。VLSI的发展更使结构组成和实现融为一体，难以分开。4. 什么是透明性概念？对计算机系统结构，下列哪些是透明的？哪些是不透明的？存储器的模m交叉存取；浮点数据表示；工/ 。系统是采用通道方式还是外围处理机方式；数据总线宽度；字符行运算指令；阵列运算部件；通道是采用结合型还是独立型；PDP-11系列的单总线结构；访问方式保护；程序性中断；串行、重叠还是流水控制方式；堆栈指令；存储器最小编址单位；

7、Cache存储器。答： 透明指的是客观存在的事物或属性从某个角度看不到。透明的有：存储器的模m交叉存取；数据总线宽度；阵列运算部件；通道是采用结合型还是独立型；PDP-11系列的单总线结构串行、重叠还是流水控制方式；Cache存储器。不透明的有：浮点数据表示；I/O系统是采用通道方式还是外围处理机方式；字符行运算指令；访问方式保护；程序性中断； ；堆栈指令；存储器最小编址单位。5 . 从 机 器 （ 汇编）语言程序员看，以下哪些是透明的？指令地址寄存器；指令缓冲器；时标发生器；条件寄存器；乘法器；主存地址寄存器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器。答： 透明的有：指令缓冲器

8、、时标发生器、乘法器、先进先出链、移位器、主存地址寄存器。6 . 下列哪些对系统程序员是透明的？哪些对应用程序员是透明的？系列机各档不同的数据通路宽度； 虚拟存储器；Cache存储器； 程序状态字； 启动I/O”指令; 执行 指令；指令缓冲寄存器。答： 对系统程序员透明的有：系列机各档不同的数据通路宽度；Cache存储器；指令缓冲寄存器；对应用程序员透明的有：系列机各档不同的数据通路宽度；Cache存储器；指令缓冲寄存器；虚拟存储器；程序状态字； 启动工/ 。 ” 指令。n o t e :系列机各档不同的数据通路宽度、Cache存贮器、指令缓冲寄存器属于计算机组成，对系统和程序员和应用程序员都

9、是透明的。虚拟存贮器、程序状态字、 启动工/ 。 ” 指令，对系统程序员是不透明的，而对应用程序员却是透明的。 执行指令则对系统程序员和应用程序员都是不透明的。7 . 想在系列机中发展一种新型号机器，你认为下列哪些设想是可以考虑的，哪些则不行的？为什么？新增加字符数据类型和若干条字符处理指令，以支持事务处理程序的编译。（ 2 ）为增强中断处理功能，将中断分级由原来的4 级增加到5 级，并重新调整中断响应的优先次序。（ 3 ）在 CPU和主存之间增设C ach e存储器，以克服因主存访问速率过低而造成的系统性能瓶颈。（ 4 ）为解决计算误差较大，将机器中浮点数的下溢处理方法由原来的恒置1 法，改

10、为用R OM存取下溢处理结果的查表舍入法。（ 5 ）为增加寻址灵活性和减少平均指令字长，将原等长操作码指令改为有3 类不同码长的扩展操作码；将源操作数寻址方式由操作码指明改成如VAX-11那种设寻址方式位字段指明。（ 6 ）将 CPU与主存间的数据通路宽度由1 6 位扩展成3 2 位，以加快主机内部信息的传送。（ 7 ）为减少公用总路线的使用冲突，将单总线改为双总线。（ 8）把 原 0 号通用寄存器改作堆栈指示器。答：可以考虑的有：1 ,3 , 4, 6, 7 o 不可以考虑的有：2 ,5 ,8 。原则是看改进后能否保持软件的可移植性。P .S .为了能使软件长期稳定，就要在相当长的时期里保证

11、系统结构基本不变，因此在确定系列结构时要非常慎重。其中最主要是确定好系列机的指令系统、数据表示及概念性结构。既要考虑满足应用的各种需要和发展，又要考虑能方便地采用从低速到高速的各种组成的实现技术，即使用复杂、昂贵的组成实现时，也还能充分发挥该实现方法所带来的好处。8 . 并行处理计算机除分布处理、MPP和机群系统外，有 哪 4 种基本结构？列举它们各自要解决的主要问题。答： 除了分布处理，MPP和机群系统外，并行处理计算机按其基本结构特征可分为流水线计算机，阵列处理机，多处理机和数据流计算机四种不同的结构。流水线计算机主要通过时间重叠，让多个部件在时间上交划重叠地并行招待运算和处理，以实现时间

12、上的并行。它主要应解决：拥塞控制，冲突防止，流水线调度等问题。阵列处理机主要通过资源重复实现空间上的并行。它主要应解决：处理单元灵活、 规律的互连模式和互连网络设计，数据在存储器中的分布算法等问题。多处理机主要通过资源共享，让一组计算机在统一的操作系统全盘控制下，实现软件和硬件各级上的相互作用，达到时间和空间上的异 步并行。它主要应解决：处理机间互连等硬件结构，进程间的同上步和通讯，多处理机调度等问题。数据流计算机设有共享变量的概念，指令执行顺序只受指令中数据的相关性制约。数据是以表示某一操作数或参数已准备就绪的数据令牌直接在指令之间传递。它主要应解决：研究合适的硬件组织和结构，高效执行的数据

13、流语言等问题。9 .计算机系统的3 T性能目标是什么？答： 计算机系统的3 T性 能 目 标 是1T FL 0PS计 算 能 力 ，1TBYTE主 存 容 量 和1TBYTES的I / O带宽课 后 习 题 第 二 章 数 据 表 示 与 指 令 系 统1 . 数据结构和机器的数据表示之间是什么关系？确定和引入数据表示的基本原则是什么？答： 数据表示是能由硬件直接识别和引用的数据类型。数据结构反映各种数据元素或信息单元之间的结构关系。数据结构要通过软件映象变换成机器所具有的各种数据表示实现， 所以数据表示是数据结构的组成元素。不同的数据表示可为数据结构的实现提供不同的支持，表现在实现效率和方便

14、性不同。数据表示和数据结构是软件、硬件的交界面。除基本数据表示不可少外，高级数据表示的引入遵循以下原则：（ 1 ）看系统的效率有否提高，是否养活了实现时间和存储空间。（ 2 ）看引入这种数据表示后，其通用性和利用率是否高。2 . 标志符数据表示与描述符数据表示有何区别？描述符数据表示与向量数据表示对向量数据结构所提供的支持有什么不同？答：标志符数据表示与描述符数据表示的差别是标志符与每个数据相连, 合存于同一存储单元,描述单个数据的类型特性； 描述符是与数据分开存放，用于描述向量、数组等成块数据的特征。描述符数据表示为向量、数组的的实现提供了支持，有利于简化高级语言程序编译中的代码生成，可以比

15、变址法更快地形成数据元素的地址。但描述符数据表示并不支持向量、数组数据结构的高效实现。而在有向量、数组数据表示的向量处理机上，硬件上设置有丰富的赂量或阵列运算指令，配有流水或阵列方式处理的高速运算器，不仅能快速形成向量、数组的元素地址，更重要的是便于实现把向量各元素成块预取到中央处理机，用一条向量、数组指令流水或同时对整个向量、数组高速处理. 如让硬件越界判断与元素运算并行。这些比起用与向量、阵列无关的机器语言和数据表示串行实现要高效的多。3. 堆栈型机器与通用寄存器型机器的主要区别是什么？堆栈型机器系统结构为程序调用的哪些操作提供了支持？答：通用寄存器型机器对堆栈数据结构实现的支持是较差的。

16、表现在：（ 1 ）堆栈操作的指令少，功能单一；（ 2 ）堆栈在存储器内，访问堆栈速度低；（ 3 ）堆栈通常只用于保存于程序调用时的返回地址，少量用堆栈实现程序间的参数传递。而堆栈型机器则不同，表现在：（ 1 ）有高速寄存器组成的硬件堆栈，并与主存中堆栈区在逻辑上组成整体，使堆栈的访问速度是寄存器的，容量是主存的；（ 2）丰富的堆栈指令可对堆栈中的数据进行各种运算和处理；（ 3 ）有力地支持高级语言的编译；（ 4 ）有力地支持子程序的嵌套和递归调用。堆栈型机器系统结构有力地支持子程序的嵌套和递归调用。在程序调用时将返回地址、条件码、关键寄存器的内容等全部压入堆栈，待子程序返回时，再从堆栈中弹出。

17、4. 设某机阶值6位、尾 数48位，阶符和数符不在其内，当尾数分别以2、8、1 6为基时，在非负阶、正尾数、规格化数情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示的规格化数的总个数。解： 依题意知：p = 6 m = 4 8 r m = 2 , 8 , 16 , m 1 = m / l o g 2 （ r m ） ,列下表:p = 6 , m = 4 8 , r m = 2 （ m，=4 8 ）p = 6 , m = 4 8 , r m = 8 （ m，= 16 ） p = 6 , m = 4 8 , r m = 16 （ m，= 12 ）最小阶

18、（ 非负阶， 最小为0）000最大阶（ 2 - P - 1）2 6 - l26-l2 * 6 - 1n o t e :司. 表示的最小值二皿人( 最小阶) * 最小尾数值= r m/ x0 * r m/ ( - 1) = r mA ( -1) ;最小尾数值( r m - ( -1) )1/ 21/ 81/ 16最大尾数值( 1 -r n T ( -m，) )1-2( -48 )1_8 (_16 ) ,即( 1-2 ( -48 ) )1_16 (_12)9 即( 1-27 -48 ) )可表示的最小值1/ 21/ 81/ 16可表示的最大值2* 6 3 * ( 1-2* ( -48 ) )8 *

19、 6 3 * ( 1-8 7 -16 ) )16 6 3 * ( 1-16 -( -12) )阶的个数( 2 p )262飞26可表示的尾数的个数2. 48 * ( 2T ) / 28 16 * ( 8 -1) / 816 12* ( 16 -1) / 16可表示的规格化数的个数26 * 2-48 * ( 2-1) / 22* 6 * 8 16 * ( 8 -1) / 82 飞 * 16 12* ( 16 -1) / 16可表示的最大值=1 ! 1人( 最大阶) * 最大尾数值=r m八( 2Ap -l ) * ( l -r mA ( -m1 ) ) ;可表示的尾数的个数=r mAm， * (

20、 r m -1) / r m ;可表示的规格化数的个数=阶的个数* 尾数的个数=2八p * r m ， * ( r m -1) / r m。5 . ( 1)浮点数系统使用的阶基r p =2,阶值位数p =2,尾数基值r m =10,以r m为基的尾数位数按照使用的倍数来说，等价于m = 4 ,试计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数。( 2 )对 于r p =2, p =2, r m =4 , m =2,重复以上计算。解依题意列下表：p =2, r m =10, m，=1p =2, r m =4, m ， =2最小尾数值0-

21、1=0. 11=0. 25最大尾数值1-10-1=0. 91-4=2=15 / 16最大阶值2p -l =33可表示的最小值0. 10. 25可表示的最大值10* 3 * 0. 9 =9 004 3 * 15 / 16 =6 0可表示数的个数3 648题中按照使用的倍数来说，等价于m =4,这个m =4,因为2人3103 - 4-2的例子寺返回勺现场23 23 22223 . 若机器共有5级中断， 中断响应优先次序为1-2-3- 4 -5 ,现要求其实际的中断处理次求序1 *4 5-2 3 o(1)设计各级中断处理程序的中断级屏蔽位( 令、 1”对应于开放，、 0”对应于屏蔽) ；(2)若在运

22、行用户程序时，同时出现第4, 2级中断请求，而在处理第2级中断未完成时，又同时出现第1, 3, 5级中断请求，请画出此程序运行过程示意图。答：(1)中断级屏蔽位设置如下图:中断处理程序级别中断级屏蔽位1级2级3级4级5级第1级11111第2级01100第3级00100第4级01111第5级01101（ 2）中断过程示意图：如图2、4中断同时出现，进行排队器。首先响应第2级中断请求， 屏蔽字为01100,表明其对第4级中断请求开放， 所以转去响应第4级中断请求并进行处理。响应4 ,中断4运行结束，回2。1、3、5进入排队器。第2级中断请求的处理请求被中断， 转去响应 第1级中断请求并进行处理。响

23、应第5级中断请求并进行处理。继续响应并处理第2级中断处理请求， 结束后返回用户程序。最后处理第3级中断请求。中断 用反 中断处理程序请 录 程 序 12 3 44. 简述字节多路，数组多路和选择通道的数据传送方式。答 ： 字节多路通道适用于连接大量的像光电机等字符类低速设备。这些设备传送一个字符（ 字节） 的时间很短，但字符（ 字节） 间的等待时间很长。通道 数据宽度为单字节，以字节交叉方式轮流为多台设备服务，使效率提高。字节多路通道可有多个子通道，同时执行多个通道程序。数组多路通道适合于连接多台象磁盘等高速设备。这些设备的传送速率很高，但传送开始前的寻址辅助操作时间很长。通道 数据宽度” 为

24、定长块，多台设备以成组交叉方式工作，以充分利用并尽可能重叠各台高速设备的辅助操作时间。传送完K个字节数据，就重新选择下个设备。数组多路通道可有多个子通道，同时执行多个通道程序。选择通道适合于连接象磁盘等优先级高的高速设备，让它独占通道，只能执行一道通道程序。 通道 数据宽度为可变长块， - 次将N个字节全部传送完， 在数据传送期只选择一次设备。5. 如果通道在数据传送期中，选择设备需9 .8 . ，传送一个字节数据需0.2R S。某低速设备每 隔500R S发出一个字节数据传送请求，问至多可接几台这种低速设备？ 对于如下A F 6种高速设备， 一次通讯传送的字节数不少于1024个字节，问哪些设

25、备可以挂在此通道上？ 哪些则不能？ 其中A-F设备每发出一个字节数据传送请求的时间间隔分别为( 单位为RS) :表 3-51设备ABCDEF发申请间隔( u S)_ _ _ _ _ _0 . 20 . 2 50 . 50 . 1 90 . 40 . 2 1答：( 1)至多可连接50台低速的外设。剖析：根据题意可知：低速设备应挂接在字节多路通道上，字节多路通道的通道极限流量为：fmax.byte=l/(TS+TD)=fbyte通道极限流量应大于或等于设备对通道要求的流量fbyteo如果字节多路通道上所挂设备台数为m,设备的速率为fi,为了不丢失信息，应满足：1/(TS+TD)=m*fifi也就是

26、设备发出字节传送请求间隔时间(500R S)的倒数，所以：m80%, H (1 0 5 -5 /4 ) / (10A5 -l) (.这样的命中率很难达到。为了降低对H 的要求，可以选择高命中率的算法，可以减少相邻两级的访问速度差和容量差( 这样做不利于降低存储器的平均每位价格) ，可在主、辅存储器间加一层电子磁盘，使存储体系中相邻两级的访问时间比不太大。2、程序存放在模3 2 单字交叉存储器中，设访存申请队的转移概率人为25% ,求每个存储周期能访问到的平均字数。当模数为1 6呢？由此你可得到什么结论？ 解：B= 1-(1-X )-m / 入解： 由人=0.25,m =32 求得：B=4-4*

27、 (3/4) A32同理，m=16 时， B=4-4* (3 /4 )- 16可得出，在入= 0 .2 5时，m =32的平均访问字数大于m =16时的平均访问字数。3、设主存每个分体的存取周期为2 p s ,宽度为4个字节。采用模m多分体交叉存取，但实际频宽只能达到最大频宽的0 .6倍。现要求主存实际频宽为4M B/S,问主存模数m应取多少方能使两者速度基本适配？其中m取2的塞。解：m=4剖析： 根据题意，模m多分体交叉的最大频宽为：分体数* 单体频宽=m*分体的宽度/ 分体的存取周期=111*48/2口s ,所以有 0 . 6*m *4/2=4。4 . 某虚拟存储器共8个页面，每页1 0

28、2 4个字，实际主存为4 0 9 6个字，采用页表法进行地址映象。映象表的内容如下表所示。虚页号01234567实页号31232100装入位11001010注：我把虚页号加上了。(1 )列出会发生页面失效的全部虚页号；(2 )按以下虚地址计算主存实地址：0, 3728, 1023, 1024, 2055, 7800, 4096, 6800。解：(1 )会发生页面失效的全部虚页号为：2 ,3 , 5, 7o(2)虚地址虚页号页内位移装入位实页号页内位移实地址0001303072327836560页面失效页面失效无102301023131023409510241011010242055270页面失

29、效页面失效无780076320页面失效页面失效无40964012020486800665610656656剖析：(1 )根据页表法列出表2,当装入位为0时 、 即为页面失效，再找出相对应的虚页号即可。(2 )虚页号= 虚地址/ 页面大小页内位移量= 虚地址一虚页号* 页面大小实地址= 实页号* 页面大小十页内位移量由于可以用替换算法解决页面失效的问题，所以，发生页面失效的虚页2 , 3 , 5 , 7仍然可以有相应的实地址，但这样要在页表中建立新的虚实地址对应关系，新的虚实地址对应关系和原来的对应关系相同的可能性就很小了。5、一个段页式虚拟存储器。虚地址有2位段号、2位页号、1 1位页内位移(

30、按字编址)，主存容量为3 2 K字。每段可有访问方式保护，其页表和保护位如下表所示。(1 )此地址空间中共有多少个虚页？段号0123访问方式只读可读/ 执行可读/ 写/ 执行可读/ 写虚页0 所在位置实页9在辅存上页表不在主存内实页14虚页1所在位置实页3实页0页表不在主存内实页1虚页2 所在位置在辅存上实页15页表不在主存内实页6虚页3 所在位置实页12实页8页表不在主存内在辅存上(2 )当程序中遇到下列情况时写出由虚地址计算出实地址。说明哪个会发生段失效、页面或保护失效失效。方式段页页内位移取数011取数1110取数332047存数014存数212存数1014转移至此13100取数0250

31、取数205转移至此3060解答：(1 )该地址空间中共有1 6个虚页。(2 )程序中遇到上表中各情况时，是否会发生段失效、页失效或保护失效及相应的主存实地址的情况如下表所示：方式段页页内位移段失效页失效实页号实地址保护失效取数011无无36145无取数1110无无010无取数332047无有无无/存数014无无36184有存数212有/无无/存数1014无有无无/转移至此13100无无816484无取数0250无有无无/取数205有/无无/转移至此3060无无1428732有剖析:(1 )虚地址中段号有2 位，页号有2 位 ，也就是每个程序最多只能有2人 2 = 4 个段,每个段至多只能有2-

32、 2 = 4 页，所以该地址空间中共有4*4 = 1 6 个虚页。(2 )先从题意得知：实地址：1 5 位，其中实页号4 位 ，页内位移1 1 位页大小为2K字(由页内位移得知)6 . 设某程序包含5 个虚页，其页地址为4, 5, 3, 2, 5, 1, 3, 2, 2, 5, 1, 3 。当使用LR U算法替换时一 ， 为获得最高命中率， 至少应分配给该程序几个实页？其可能的最高命中率为多少？325135325145325443222513332511132555132堆栈页地址流 453 2513225S(1)SS(3)S(4)S(5)S(6)n=1n=2n=3n=4 H数 n=5 H使用

33、LRU算法对页地址流进行堆栈处理7 . 采用页式管理的虚拟存储器，分时运行两道程序。其中，程 序 X 为D O 5 0 1 = 1 , 3B (I )= A (I )- C (I )I F (B (I ) L E 0 )G 0 T 0 4 0D (I )= 2 * C (I )- A (I )I F (D (I ) E Q O )G O T O 5 04 0 E (I )= 05 0 C O N T I N U ED at a: A = (- 4 , + 2 , 0 )C = (- 3 , 0 , + l )每个数组分别放在不同的页面中； 而程序丫在运行过程中，其数组将依次用到程序空间的第3,

34、 5, 4,2,5,3, 1,3,2,5, 1,3, 1,5,2页。如果采用LRU算法，实存却只有8 页位置可供存放数组之用。试问为这两首程序的数组分别分配多少个实页最为合适？为什么？解答： 分别分配给程序X 和丫的数组4 个实页最为合适。根据题意，程 序 X 依次调用数组A,C,B,B,C,A,D,D,E, A,C,B,B,E中的数据。设程序X 中的数组A, B, C, D, E 分别存放于程序空间的第1,2,3, 4,5页，则程序的页地址流为：1, 3, 2, 2, 5, 1 3, 2, 2, 3, 1 4, 4, 5 1, 3 2, 2, 5。分析使用LRU算法对程序X 的页地址流进行堆

35、栈处理的过程可知， 分配给程序X 的数组5个实页最为合适； 分析使用LRU算法对程序Y 的页地址流进行堆栈处理的过程可知，分配给程序丫的数组4 个实页最为合适。但实存只有8 页位置可供存放数组之用，所以，分别分配给程序X 和丫的数组4 个实页。note :分时运行在微观上是串行的，就是说，分时运行时把时间划分为若干时间片，每个程序轮流占用时间片； 在宏观上是并行的， 就是说， 每个程序在一个时间片内并不能运行完。 总的来看,是同时运行的，所以两个程序分配的实页和不能大于8。我不了解FORTRAN,找朋友把上面的源代码转成C 了：m a i n ( )i n t A = - 4 , 2 , 0

36、;int C = -3,0, 1） ;for （ i=0, 100）Ei=0;） ；） ；）8 . 设一个按位编址的虚拟存储器，它应可对应1 K个任务，但在一段较长时间内，一般只有4个任务在使用， 故用容量为4行的相联寄存器组硬件来缩短被变换的虚地址中的用户位位数； 每个任务的程序空间最大可达4 0 9 6页，每页为5 1 2个字节，实主存容量为2- 2 0位；设快表用按地址访问存储器构成,行数为3 2 ,快表的地址是经散列形成；为减少散列冲突，配有两套独立相等比较电路。请设计该地址变换机构，内容包括：（ 1 ）画出其虚、实地址经快表变换之逻辑结构示意图；（ 2 ）相联寄存器组中每个寄存器的相

37、联比较位数；（ 3 ）相联寄存器组中每个寄存器的总位数；（ 4 ）散列变换硬件的输入位数和输出位数；（ 5 ）每个相等比较器的位数；（ 6 ）快表的总容量（ 以位为单位）。解：（ 1 ）依题意得知： 虚地址为3 4位， 其中用户号为1 0位 （ 对应1 K的任务） 、 虚页号1 2位 （ 每个任务4 0 9 6页）、页内位移1 2位 （ 每页5 1 2字节，5 1 2字节= 5 1 2 * 8 = 1 0 2 4 * 4 = 2 - 1 2 ）实地址为2 0位，其中实页号8位，页内位移1 2位 （ 与虚页页内位移对应）相联寄存器的作用：把1 0位的用户号转换为2位的工D （ 因为一般只有4个任

38、务在使用），并把I D与虚地址的虚页号合并到快表中查实页号。快表的作用：相当于页表，即虚页号对实页号的对应关系。但又有所简化（ 原因是如果用用户号和虚页号与实页号对应，前者就有2 2 位，现改进后虚页号只有1 4 位了）快表（ 按地址访问）虚拟存储器快表示意图相联比较U1 （ 1晦 ）00U201u310U411（ 2 ） 相联寄存器组中每个寄存器的相联比较位数为10 （ 与虚地址中的用户号宽度对应）（ 3） 相联寄存器组中每个寄存器的总数为12 （ 用户号宽度+1D宽度）（ 4） 散列变换硬件的输入位数为1 4 位 （ 虚页号宽度+ 相联寄存器中工D 的宽度），输出位数为8位 （ 与主存中的

39、实页号宽度对应）（ 5 ） 每个相等比较器的位数=1D+用户虚页号nv= 2 + 12 = 14 （ 位） 。（ 6） 快表的总容量：3 2 行* （ 1 4 （ 输入位数） +8 （ 输出位数）*2=32*22*29 . 考虑一个9 2 0 个字的程序，其访问虚存的地址流为20, 22, 208, 214, 146, 618, 370, 490,492, 868, 916, 728=（ 1） 若页面大小为2 0 0 字，主存容量为4 0 0 字，采 用 F IF O 替换算法，请按访存的各个时刻，写出其虚页地址流，计算主存的命中率；（ 2 ） 若页面大小为1 0 0 字，再做一遍；（ 3 ）

40、 若页面大小为4 0 0字，再做一遍；（ 4 ） 由 （ 1 ） 、 （ 2 ） 、 （ 3 ） 的结果可得出什么结论？（ 5 ） 若把主存容量增加到8 0 0 字，按第（ 1 ） 小题再做一遍，又可得出什么结论？解：（ 1 ） 主存容量4 0 0 字，页面大小2 0 0 字，所以主存实页数为2 ；把地址流转换为页地址流，以第一个虚地址流转换为页地址流为例说明：求模公式为：INT （ 地址/ 页 面 大 小 ），就是把地址整除于页面大小，得 I N T （ 2 0 / 2 0 0 ） = 0 ,下 同 ，所以页地址流为：0 , 0 , 1 , 1 , 0 , 3 , 1 , 2 , 2 , 4

41、 , 4 , 3按 F I F O 算法得出替换过程为：0 （ 调入），0 （ 命中），1 （ 调入），1 （ 命中），0 （ 命中），3（ 替 换 0 , 0比 1先入队，所以被替换，下同），1 （ 命中），2 （ 替 换 1 ） , 2 （ 命中），4 （ 替 换 3 ）,4 （ 命中），3 （ 替 换 2 ）,所以总共命中6次。故命中率H = 6 / 1 2 = 5 0 %（ 2 ） 方 法 同 （ 1 ） H = 2 5 %（ 3 ） H = 5 0 %（ 4 ） 由以上结论可得，F I F O 算法的条件下，当页面大小发生变化时，其命中率变化是：一开始随页面大小增大命中率（ 第一步与

42、第二步比较），但当页面大小增到一定时，命中率不再增加（ 第一步与第三步比较）。（ 5 ） 命中率为5 8 % , 结论是如果分配给主存容量增加时可以搞高命中率。10.在一个页式二级虚拟存储器中，采 用 F I F O 算法进行页面替换，发现命中率H太低，因此有下列建议：（ 1 ） 增大辅存容量；（ 2 ） 增大主存容量（ 页数） ;(3 ) F I F O 改为 L R U ;(4) FIFO改为LRU,并增大主存容量(页数)；(5) FIFO改为LRU,并增大页面大小。试分析上述各建议对命中率的影响情况。解答：(1)增大辅存容量，对命中率H无影响。(2)增大主存容量(页数)，可普遍提高命中率

43、。(3)F1F。改为LRU, 一般可提高命中率。(4)F1F。改为LRU,并增大主存容量(页数)，一般可使命中率有较大提高。(5)F1FO改为LRU,并增大页面大小，如果原来页面很小，则会使命中率显著上升，如果原来页面很大，则会使命中率下降。11 . 采用组相联映象的Cache存储器，Cache为1KB,要 求Cache的每一块在一个主存周期内能从主存取得。主存模4交叉，每个分体宽为32位 ，总容量为256KB。用按地址访问存储器构成相联目录表实现主存地址到Cache地址的变换，并约定用4个外相等比较电路。请设计此相联目录表，求出该表之行数、总位数及每个比较电路的位数。解 答 ：设Cache地

44、 址 中 的 组 内 块 号 为s ,相 联 目 录 表 的 行 数 是2入(13-s),总 位 数 是(8 + 2s) *2人(15-s),每个比较电路的位数为8 + s。剖析： 在一个主存周期内主存能访问到的字节数为mW=4*32/8=16 (Byte)。要 求Cache的每一块在一个主存周期内能从主存取得，所以，Cache中每块的块内字数不能大于16Bytes。为了加速调块,一般让每块的大小等于在一个主存周期内主存能访问到的字数，即16Bytes。设Cache地址中的组内块号为s,相联目录表的行数=Cache地址内的组数Q=Cache容量/ (每组块数* 每块大小)=1KB/ (S*4*

45、32)=2A13/ (2入s*2入7)=2入(6-s)。主存块数/Cache块数=256=2*8,所 以 ，主 存 地 址 中 的 区 号nd=8。每个比较电路的位数=nd+s1=nd+s=8+so相 联 目 录 表 的 总 位 数 = 表 中 子 目 录 表 的 个 数 * 每 个 子 目 录 表 的 位 数 * 相 联 目 录 表 的 行 数=4*(nd+sf+s)*Q=4*(8+2s)*2人(6-s)= (8+2s)*2A(8-s)on o te ：若认为相等比较电路的个数= 组内块数，则相联目录表的行数=2-4,每个比较电路的位数=10,相联目录表的总位数=12 *2A6o12 . 有

46、一个Cache存储器。主存共分8个 块（ 07） , Cache为4个 块（ 03）， 采用组相联映象，组内块数 为2块，替换算法为近期最少使用算法（ LRU） o（ 1）画出主存、Cache地址的各字段对应关系（ 标出位数） 图；（ 2）画出主存、Cache空间块的映象对应关系示意图；（ 3）对于如下主存块地址流：1,2,4,1,3,7,0,1,2,5,4,6,4,7,2,如主存中内容一开始未装入Cache中，请列出Cache中各块随时间的使用状况；（ 4 ）对于（ 3）, 指出块失效又发生块争用的时刻；（ 5）对于（ 3）， 求出此期间Cache的命中率。解答：（ 1）主存地址、Cache

47、地址的各字段的位数及其对应关系如下图所示Cache块号neb 主存地址nm区号nd（ 1位）组号q（ 1位）组 内 块 号 位 ）块内地址nmr- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 相联查找直接查找主存块号nmb W W Cache地址nc组号q（ 1位）组内块号s1（ 1位）块内地址nmr主存地址和Cache地址的对应关系（ 2）主存块、Cache块的映象对应关系如下图所示组 间 直 接 财 主 存 块 号0组一1组 。 组 一1组 -组内各块之间全相联映象岖1区主存块和Cach e块的对应关系(3

48、) Cache中各块随时间的使用状况如下图所示。图中标* 号的是候选替换块的块号，H：命中；R：替换；L：失效。tine t主 存 块 地 址 流12 3 4 5 68 9 10 11 12 13 14 15Cachet夬命中情况Cache的使用情况7 2(4)发生块失效又发生块争用的时刻有6、7、9、10、11、12、14、15o(5) Cache 的块命中率 Hc=3/15 = 0.2。剖析： 由于主存块、Cache块之间存在上述的映象对应关系，主存的第0、1、 4、5块只能映象装入或替换物理Cache的 第0、1块； 主存的第2、3、6、7块只能映象装入或替换物理Cache的 第2、3块

49、。13 . 采用组相联映象，LRU替换算法的Cache存储器，发现等效访问速度不高，为此建议：(1)增大主存容量；(2)增 大Cache的块数(块的大小不变);(3)增大组相联组的大小(块的大小不变)；(4)增大块的大小(组的大小和Cache总容量不变);(5)提 高Cache本身器件的访问速度。解答：(1)增大主存容量对Cache的访问时间ta基本不影响，从而对Cache的等效访问速度基本不影响。(2)增 大Cache的块数(块的大小不变)一般将使Cache的命中率He上升，从而使ta下降，从而提高Cache的等效访问速度。(3)增大组相联组的大小(块的大小不变)一般将使Cache的命中率H

50、e上升，从而使ta下降，从而提高Cache的等效访问速度。(4 )增大块的大小(组的大小和Cache总容量不变)一般将使ta下降， 从而提高Cache的等效访问速度。(5)提 高Cache本身器件的访问速度一般将缩短ta,从而提高Cache的等效访问速度。14 . 你 对Cache存储器的速度不满，于是申请到一批有限的经费，为能发挥其最大经济效益，有人建议你再买一些同样速度的Cache片子以扩充其容量； 而另有人建议你干脆去买更高速的Cache片子将现有的低速Cache片子全部换掉。你认为哪种建议可取？你如何做决定？为什么？解答：Cache本身的速度与容量都会影响Cache存储器的等效访问速度

51、。如 果 对Cache存储器的等效访问速度不满，需要改进的话，就要作具体分析，看看现在Cache存储器的等效访问速度是否已接近 于Cache本身的速度。如果差得较远，说 明Cache的命中率低，应从提高Cache命中率着手，包括调整组的大小、块的大小、替换算法以及增大Cache容量等。如 果Cache存储器的等效访问速度已经非常接近于Cache本身的速度还不能满足需要，就应该更换更高速的Cache片子。课后习题第 五 章 重 叠 、流水和向量处理机1 . 假设指令的解释分取指、分析与执行3 步，每步的时间相应为t 取指、t 分析、t 执行，（ 1） 分别计算下列几种情况下，执 行 完 100条

52、指令所需时间的一般关系式：a .顺序方式；b .仅 执行k 与 取指k+1” 重叠；c .仅 执行k 、 分 析 k+1、 取 指 k+2” 重叠;（ 2） 分别在t 取指= t 分析=2、t 执行= 1 及 t 取指= t 执行=5、t 分析= 2 两种情况下，计算出上述各结果。解：（1） 执行完 100条指令所需时间：a . 100* （ t 取指+ t 分析+ t 执行） ；b . t 取指+ 1 0 0 *t分析+99*max （ t 取指+ t 执行） + t 执行；c . t 取指+max （ t 取指+ t 分析） +98*max （ t 取指+ t 分析+ t 执行） +max

53、 （ t 分析+ t 执行） + t 执行。（ 2） 在 t 取指= t 分析=2、t 执行= 1 的情况下，执 行 完 100条指令所需时间：a . 500b.401c . 203在 t 取指= t 执行=5、t 分析= 2 的情况下，执 行 完 100条指令所需时间：a .1200b.705c.5102 . 流水线有4 个功能部件组成，每 个 功 能 部 件 的 延 迟 时 间 为 当 输 入 1 0 个数据后间歇5A t 又输入 1 0 个数据，如此周期性地工作，求此时流水线的吞吐率，并画出时空图。解:TP = 10/14At = 5 /7A t时空图：3 . 有一个浮点乘流水线如图5

54、. 3 5 ( a ) 所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出 实 现 A * B * C * D 的时空图以及输入端的变化，并求出该流水线的吞吐率和效率； 当流水线改为图5 . 3 5 ( b ) 形式实现同一计算时，求该流水线的效率及吞吐率。图 5 . 3 5 ( a ) t 3 Z操作数： | 阶 加 卜 T 尾 乘 T 规 格 化 一 积(a)图 5 . 3 5 ( b )(b)解：按 图 5 . 3 5 ( a ) 组织的流水线时，T P = 3 / 1 3 A t ; r ) = 3 / llo实现A * B * C * D 的时空图如图0 5 0 4 所示：图

55、 0 5 0 4按图5 .3 5 (a )组织的流水线时,T P = 3 /1 3 A t； r= 3 /llo实现A*B*C*D的时空图如图0 5 0 4所示:图 0505剖析：为了减少运算过程中的操作数相关，A*B*C*D应改为（ （ A*B） * （ C*D） ）进行运算。4 . 一个4段的双输入端规格化浮点加法流水线，每段经过时间1 0 n s ,输出可直接返回输入或将结果暂存于相应缓冲器中，问最少需经多少时间能求（ 10） 2 （ i = l ） A i ,并画出时空图。答： 时空图如下:蛤 中 A1+A2 A5M6 ft5-ft8fflltnA “ A rm。A3*AU A7+A8

56、 ft1A4求(10) X (i= l) A i需要的最知时间是170nso剖析： 为了避免先写后读相关，使流水线性能尽可能高，需将(10) N (i = l ) A i调整成( ( ( (A1+A2)+ (A3+A4) + (A9+A10) + ( (A5+A6)+ (A7+A8) )。5. 为提高流水线效率可采用哪两种主要途径来克服速度瓶颈？现有3段流水线，各段经过时间依次为A t、3A t A t,(1 )分别计算在连续输入3条指令时和3 0条指令时的吞吐率和效率。(2 )按两种途径之一改进，画出你的流水线结构示意图，同时计算连续输入3条指令和3 0条指令时的吞吐率。(3 )通过对(1

57、)、(2 )两小题的计算比较可得出什么结论？解答：为提高流水线效率可采用瓶颈希再细分和瓶颈段并联两种主要途径来克服速度瓶颈。(1 )连续输入3条指令时的吞吐率TP3 = 3 / l l Z t ;效率0 3 = 5 /1 1。连续输入3 0条指令时的吞吐率TP30 = 1 5 /4 6 4 t;效率3 = 2 5 /4 6。(2 ) 改进后的流水线结构示意图大体如图5 . 3 5 (a ) 和 图 5 . 3 5 (b ) 连续输入3条指令时的吞吐率T P 3 = 3 / 7 Z t ; 效 率 r 3 = 3 / 7 。连续输入3 0 条指令时的吞吐率T P 3 0 = 1 5 / 1 7

58、A t ; 效 率 3 = 1 5 / 1 7 。(3 ) 只有当连续输入流水线的指令足够多时，流水线的实际吞吐率和效率才会提高。6 . 有一个双输入端的加- 乘双功能静态流水线，由 经 过 时 间 为 2 A t 的 1 、2 、3 、4四个子过程构成。加 按 1 - 2 - 4 连接，乘 按 1 - 3 - 4连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。 现要执行A * (B + C * (D + E * F ) ) + G * H 的运算， 请调整计算顺序画出能获得尽量高的吞吐率的流水时空图，标出流水线入、出端数的变化情况，求出完成全部运算的时间及此期间流水线的效率。如对流水

59、线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程3不能再细分，只能用并联方法改进，问流水线的效率为多少？解 ：根据题意，画出流水线吞吐率尽可能高的时空图如图0 5 0 7 ：图 0 5 0 7在此期间的流水线效率q = (6 * 4 A t + 3 * 4 A t ) / 4 * 2 4 A t = 3 / 8如果将瓶颈子过程2和 3均细分成两个子过程，则时空图如图0 5 0 8 所示:图 0508由图可见，完成全部运算最少需要 At 。若子过程3 不能再细分，只能用并联方法改进，则则时空图如图0 5 0 9 所示:图 0509时间( * ： )A E A G AC ACC F B

60、 H D EFAB ACEFACD GHACEF+GHAB+ACD输出AC EF AB GH flCD ACEFAB+ACDACEF+GH这种情况下，流水线效率n= (24Z t + 12Zxt) /6*18Z t = l/3剖析： 因为是双功能静态流水线，为了能有高的吞吐率，应减少流水线的功能切换次数。因此,应将算法调整成先作一连串的乘，然后再切换成一连串的加。原式展开成A*B+A*C*D+A*C*E*F+G*H,先进行乘法流水，为了减少因先写后读相关而等待的时间，应尽量安排对计算式子项数最多的乘法先进行操作，即先计算A *C *E *F,再计算A*C*D, . . .7 . 现有长度为8

61、的向量A 和 B , 请分别画出下列4 种结构的处理器上求点积A*B的时空图，并求完成全部结果的最少时钟拍数。 设处理器中每个部件的输出均可直接送到任何部件的输入或存入缓冲器中去，其间的传送延时不计，指令和源操作数均能连续提供。(1 )处理器有一个乘法部件和一个加法部件，不能同时工作，部件内也只能以顺序方式工作，完成一次加法或乘法均需5 拍;(2 ) 与 ( 1)基本相同，只是乘法部件和加法部件可并行;(3)处理器有一个乘、加法双功能静态流水线，乘、加法均由5 个流水段构成，各段经过时间要1拍;(4)处理器有乘、加法两条流水线，可同时工作，各 由 5 段构成，每段经过时间为1 拍。解答:(1)

62、在这种结构的处理器上求点积A *B 的时空图如图0510所示:图 0510部件完成全部运算最少需要7 5 拍。(2)在这种结构的处理器上求点积A *B 的时空图如图0511所示:图 0511部件完成全部运算最少需要4 5 拍。(3)在这种结构的处理器上求点积A *B 的时空图如图0512所示:图 0512完成全部运算最少需要3 0 拍。(4)在这种结构的处理器上求点积A *B 的时空图如图0513所示： 图0513完成全部运算最少需要26拍。剖析： 向量A*B的点积为A*B= (8) (i=l) ai*bi= al*bl + a2*b2 + a3*b3 + a4*b4 + a5*b* + a6

63、*b* + a7*b7 + a8*b8,共需 8次乘法和7 次加法。8 . 试总结IBM 360/91解决流水线控制的一般方法、途径和特点。在流水线中设置相关直接通路解决局部相关；用猜测法解决全局相关；设置 向后8 条 检查，加快短循环程序的处理；对流水线的中断处理用 不精确断点法” 。9 . 在一个5 段的流水线处理机上需经9拍才能完成一个任务，其预约表为：totlt2t3t4t5t6t7t8S1VVs2VVs 3VVVs 4VVs 5VV分别写出延迟禁止表F 、冲突向量C ； 画出流水线状态转移图； 求出最小平均延迟及流水线的最大吞吐率及其高度方案。按此流水高度方案输入6个任务，求实际吞吐

64、率。解： 根据预约表，延迟禁止表F = 1 , 3 , 4, 8 ）冲突向量为C : 1 0 0 0 1 1 0 1状态转移图如图0 5 1 4 所示图 0 5 1 4各种方案的平均延迟表:调度方案(2, 5 )(2, 7 )5| ( 5 , 6 )( 6 )( 6 , 7 )( 7 )平均延迟3 . 54. 555 . 566 . 57最小延迟为3 . 5 拍，其调度方案为（ 2 , 5 ）。按调度方案（ 2 , 5 ）输 入 6个任务时的时空图如图0 5 1 5 所示:图 0 5 1 5实际吞吐率TP=6/25 ( 任务/ 拍) 。剖析：求延迟禁止表F=1, 3, 4, 8 ) ,第一行间

65、隔8 ,第二行间隔1 ,第三行间隔1, 3, 4,然后间隔都为1，合并。求冲突向量，写一个8位两进制数，根据禁止表倒着写。由于初始冲突向量的C 2 ,c 5 ,c 6 ,c 7为0 ,所以第二个任务可以距第一个任务2, 5, 6或7拍流入流水线。10 . 求向量口= 人* (B+C),各向量元素均为N ,参照CRAY 1方式分解为3条向量指令：1: V 3 -存储器 访存取A送入V 3寄存器组2： V2 K )3： V4D当采用下列3种方式工作时需多少拍才能得到全部结果？(1) 1、2、3、串行执行；(2) 1和2并行执行完后，再执行3;(3 )采用链接技术。解： (1 )每条指令所需拍数为:

66、指令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 ）指令1和2并行执行：1 （ 启动访存，送浮加部件）+6 （ 访存，浮加）+1 （ 存V3,存 V2）+N-1=7+N1, 2 并行：7+N+8+N=15+2N（ 3 ） l+6+l+l+7+l+N -l=16+N1 1 .设向量长度为6 4 ,以CR AY-1机

67、上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值1 4拍； 从存储器读数6拍，打入寄存器及启动功能部件各1拍。问下列各指令组内的哪些指令可以链接？哪些指令不能链接？不能链接的原因是什么？分别计算出各指令组全部完成所需的拍数。(1)(2)(3)(4)V 0 -存储器V1-V2+V3V4*-V5*V6V2-VO*V1V3- 存储器V4-V2+V3VO-存储器V2-VO*V1V3-V2+V0V5-V3+V4V 0 -存储器V l-l/V OV3-V1*V2V5-V3+V4解：（ 1 ） 3条向量指令之间既没有发生源V i冲突，也没有V i的先写后读相关，又不存在功能部 件 的 使

68、 用 冲 突 ， 所 以 这3条 向 量 指 令 可 以 同 时 并 行 流 水 。m ax（ l + 6 （访存）+1 + 6 4 -1 ） , （ 1 + 6 （ 浮加）+1 + 6 4 -1 ） , （ 1+ （ 7 浮乘）+1 + 6 4 -1 ） = 72 拍。 所以向量指令组全部完成需要72 （ 拍） 。（ 2 ） 3条向量指令之间没有功能部件的使用冲突，但是在第1、2两条向量指令与第3条向量指令之间有V 2及V 3的先写后读相关。只要让第1条向量指令较第2条向量指令提前1拍启动，则第1 ,2两条向量指令的第1个结果元素就可以被同时链接到第3条向量指令中。max （ 1+（ 7 浮

69、乘）+1 + 64-1） , （ 1 + 6 （ 访存）+1 + 64-1） + （ 1 + 6 （ 浮 力 口 ）+1 + 64-1） =8 0 （ 拍） 。（ 3）第1条向量指令与第2条向量指令之间有V 0的先写后读相关，两者可以链接。第3条向量指令与第2条向量指令之间有源向量寄存器V 0的冲突，它们之间只能串行。第3条向量指令与第4条向量指令之间有加法功能部件的使用冲突，它们之间也只能串行。（1 + 6 （访存）+1 + 1+ （ 7 浮乘）+1 + 64-1） + （ 1 + 6 （ 访存）+1 + 64-1） （ 1 + 6 （ 浮加）+1 + 64-1） =222 （ 拍） 。（

70、4） 4条向量指令均依次有V i的先写后读相关， 但无源V i冲突， 也无功能部件的使用冲突，所以，这4条向量指令可以全部链接在一直，进行流水。（1 + 6 （访存）+1） + （ 1 + 14（求倒数）+1） + （ 1+ （ 7 浮乘）+1） + （ 1 + 6 （浮加）+1） +64-1=104 拍。12. 设指令由取指、分析、执行三个子部件组成。每个子部件经过时间为 , 连续执行1 2条指令。请分别画出在常规标量流水处理机及度m均为4的超标量处理机、超长指令字处理机、超流水线处理机上工作的时空图，分别计算它们相对常规标量流水处理机的加速比Sp。解： 常规标量处理机的时空图：度m为4的超

71、标量处理机的时空图:其相对于常规标量流水处理机的加速比S p = 1 4 A t/5 A t= 2 .8度 m 为 4 的超长指令字处理机的时空图：其相对于常规标量流水处理机的加速比S p = 1 4 A t/5 A t= 2 .8度 m 为 4 的超流水线处理机的时空图:其相对于常规标量流水处理机的加速比S p = 1 4 A t/5 .7 5 A t = 5 6 /2 3 2 . 8课后习题第 六 章 阵 列 处 理 机1 . 画出1 6 台处理器仿工LLIAC IV 的模式进行互连的互连结构图，列 出 PEO分别只经- - 步、二步和三步传送能将信息传送到的各处理器号。答： 6 台处理器

72、仿ILLIAC IV 处理单元的互连结构如图所示：图中第个PU中包含PE、PEM和MLUoPEO(PUO)经一步可将信息传送至 PU1、PU4、PU12、PU15。PEO (PU0)至少需经二步才能将信息传送至PU2、PU3、PU5、PU8、PU1K PU13、PU14oPEO (PU0)至少需经三步步才能将信息传送至PU6、PU7、PU9、PUlOo2. 编号为0、1、. . . 、15的 16个处理器,(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Shuffle (Shuffle)时，第 13号处理器各连至哪一个处理器？解答：( 1)5号处理器(2)5号处理器(

73、3) 12号处理器(4)11号处理器(5)7号处理器剖析：由题意知，有 16个处理器，即仿ILLIAC IV处理单元的互连结构用单级互连网互连。当互连函数分别为N=16z n=log2(N)=log2(16)=4。Cube3(13)=Cube3(1101)=0101=5PM2 + 3（ 13） = （ 13 + 2人3） modi 6=5PM2-0（ 13） = （ 13-2八0） modi 6=12Shuffle（ 13） =Shuffie （ 1101） =1011 = 11Shuffle（ Shuffle） =Shuffie（ 11） =Shuffie（ 1011） =0111=73 .

74、 编号分别为0、1、2.F的16个处理器之间要求按下列配对通信：（ B、1） , （ 8、2） , （ 7、D） , （ 6、C） , （ E、4） , （ A、0） , （ 9、3） , （ 5、F） 0试选择所用互连网络类型、控制方式，并画出该互连网络的拓补结构和各级交换开关状态图。解答：采 用4级立方体网络，级控制。该互连网络的入端出端123456789ABDF026789ABDF级 023级号CubeOCubelCube2Cube3开关状态直连交换直连交换多级互连网络拓补结构和各级交换开关状态图如下图所示:剖 析 ：从处理器号的配对传送关系可以转成处理器二进制编号的配对传送关系:(B,

75、 1)(1011,0001)(8,2)(1000,0010)(7,D)(0111,1101)( 6 ,0 (0110, 1100)( E , 4 ) ( 1 1 1 0 , 0 1 0 0 )( A , 0 ) ( 1 0 1 0 , 0 0 0 0 )( 9 , 3 ) ( 1 0 0 1 , 0 0 1 1 )( 5 , F ) ( 0 1 0 1 , 1 1 1 1 )不难得出其一般规律是：二进制编号为P 3 P 2 P 1 P 0 的处理器与( P 3 ) P 2 ( P l ) P 0 的处理器配对交换数据。由于实现的都是交换函数的功能，采用成本最低的级控制多级立方体互联网络就可以实

76、现。N = 1 6 的多级立方体网络，由 n = l o g2 ( 1 6 ) = 4 组成。每一级均使用N/ 2 = 8个二功能交换开关。多级网络各级的级号由入端到出端依次为0 、1 、2 、3 . 第 i级的每个交换单元的配对用的是C u bei ( P 3 . . . P i . . . P 0 ) = P 3 . . . P i ) . . . P 0 函数。根据本题的要求，应当让第1 、3级的各交换单元处于 交换 状态，第 0 、2级的各交换单元处于 直连 状态。4 . 画出编号为0 、1 、. . . 、F共 1 6 个处理器之间实现多级立方体互连的互连网络，采用级控制信号为 1

77、1 0 0 ( 从右至左分别控制第0级至第3级 ) 时，9号处理器连向哪个处理器？解答：多级立方体互连网络的图和第3题的图基本一致，不同之处在于，第 0 、1级的开关状态为直连，第 2 、3级的开关状态为交换。9号处理器在经过0级 和 1级交换开关后，连向哪第1 0 个处理器； 在经过2级交换开关后，连向第4个处理器； 在经过3级交换开关后，连 向 第 9个处理器。5 . 对于采用级控制的三级立方体网络，当 第 i级 ( 0 = i tin e程序在多处理机上运行的资源时间图(3 )在 有2台处理机制多处理机系统上运行的资源时间图如下图所示。假设标号为5 0和6 0的两个并发进程中，标号为5

78、0的进程最后完成。time处理机I120 J01N4 30 JOIN 60 J0IN2_ _ _ _I I_ I I I_I II ICPU1 FORK4O 10 JOIN 40 JOIN4 ； 5B J0IN2 7 0I 1 1 1 1 1 1 1 1 1 1 1F0RK3 0 F0RK6 0 GOTO7 0F0RK20- A程序在多处理机上运行的资源时间图剖析： GOTO 70语句的问题关键是70语句是在50语句还是60语句所在CPU上执行的。也就是说50语 句 和60语句谁先执行完。7、若有如下程序：V = U/ BW = A * UX = W -VY = W * UZ = X / Y试

79、用FORK、JOIN语句改写成可在多处理机上并行执行的程序。假设现有两台处理机，且除法速度最慢，力 口 、减法速度最快，请画出该程序运行时的资源时间图。解答：用FORK、J。 工N语句改写成可在多处理机上并行执行的程序如下：SI U= A + BF ORK S3S2 V = U/ BJOIN 2G OTO S4 S3 W = A * UJOIN 2S4 FORK S5S4 X=W-VJOIN 2GOTO S6S5 Y=W*UJOIN 2S6 Z=X/Y该程序在有2 台处理机的多处理机系统上运行时的资源时间图如下所示:处理机,S3 JI0N2 S5 JI0N2 S6CPU2_ I I _ I I

80、 _ LI _ II * I /S1 I S2 G O T O S S” JI0N2CPU1_I I _ I I I I _ I 1+ F0RKS3 / JI0N 2 F0RKS5 - Atin e程序在多处理机上运行的资源时间图8 . 分别确定下列各计算机系统中, 计算点积S= (8) Z ( i=l) ai*bi所需的时间( 尽可能给出时空图示意) ：(1)通用PE的串行SISD系统；(2)具有一个加法器和乘法器的多功能并行流水SISD系统； 有 8 个处理器的SIMD系统；(4)有 8 个处理器的MIMD系统。设访存取指和取数的时间可以忽略不计； 加与乘分别需要2 拍和4 拍； 在 SI

81、MD和MIMD系统中处理器( 机) 之间每进行一次数据传送的时间为1拍， 而在SISD的串行或流水系统中都可忽略； 在 SIMD系统中PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在M1MD中每个PE都可以和其它PE有直接的通路。解答： ( 1)利用通用PE的串行S1SD系统计算点积所需时间为46拍，时空图如下图所示：部件八a1*b1a2 M12*a3 M） 3+a4*b4*a5*b5+a6*b6+a7*b7+a8Mb8+4 2time （ 拍）(2)利用具有一个加法器和乘法器的多功能并行流水S1SD系统计算点积所需时间为15拍，时空b 1 b 2 b 3 b b

82、5 b 6 b 7 b 8图如下图所示:(3)利用有8个处理器的S1MD系统计算点积所需时间为14拍，时空图如下图所示:time（ 拍）（ 4 ）利 用 有8 个处理器的M工 MD系统计算点积所需时间为1 4 拍，时空图如下图所示:处理机CPU1CPU2CPU3CPU4CPU5CPU6CPU7CPU8time （ 拍）9 . 设程序有T 个任务，在 A、B 两台处理机组成的多处理机上运行。每个任务在A 处理机上执行的时间为 E , 在 B 处理机上执行的时间为2 E ,不考虑机间通讯时间，问如何分配任务，可使系统总执行时间最短？总执行时间最短为多少？解： 设 为A 处理机分配工个任务，为 B

83、处理机分配T -工个任务， 则系统总执行时间最短为IE=2 (T -I) E o 解得：I= 2 T /3 o 所以，总执行时间最短为2T E /3。10 . 简述多处理机操作系统3 种不同类型的构形， 列出每种构形有优点和缺点以及设计中的问题.答 ：类型构型优点缺点适用场合主从型管理程序只在一台指定的处理上运行硬件结构简单,控制简单对主机的可靠性要求高，灵活性差工作负荷固定，从处理机的能力明显低于主处理机各自独立型控制功能分散到多台处理机，共同完成对整个系统的控制。每台处理机都有一个独立的管理程序( 操作系统的内核) 在运行。 要求管理程序必须是可再入的。适应分布处理的模块化结构,对主机依赖

84、性小，可靠性高,系统效率较高尽管每台处理机都有专用表格，但一些共享表格会增加共享冲突，加大了开销。实现复杂，输入输出结构变换需要人为干预，处理机间负荷的平衡比较困难松耦合多处理机系统浮动型管理程序在处理机间浮动集中了主从型和各自独立型的优点， 且灵活性高设计最困难紧耦合多处理机系统，同构多处理机系统课后习题第八章其它计算机结构1、简述脉动阵列结构的特点。答：（ 1）结构简单，规整，模块化强，可扩充性好;（ 2）处理单元间数据通信距离短，规则，使数据流和控制流的设计，同步控制均简单规整；（ 3）脉动阵列机中各处理单元同时运算，并行性极高，可通过流水获得很高的吞吐率；（ 4）输入数据被多个处理单元

85、重复使用，减轻阵列与外界I/O通信量，降低系统对主存和工/ 。系统频宽的要求。（ 5）脉动阵列结构的构形与特定任务和算法密切相关，具有专用性，限制了应用范围。2、什么叫控制驱动、数据驱动、需求驱动？答：控制流驱动： 即指令的执行是在PC （ 程序计数器） 的控制下，按照事先指定的序列进行的， 指令的执行顺序隐含在控制流中。数据流驱动： 即指令的执行是按照数据相关和资源可用性确定的序列进行的，指令的执行基本上是无序的。只要一条指令所需的操作数全部就绪， 就可以被激发并执行。需求驱动： 即指令的执行是按照数据需求确定的序列进行的。3、什么叫大规模并行处理机MPP?什么叫机群系统？答：MPP是大规模

86、并行处理机，指用数百万个高性能，低成本的RISC微处理器通过互联网络互连，组成 的SIMD或MIMD系统。机群系统是将多个高性能工作站或高档微型计算机使用高速通信网络加以互连组成系统。4、用结构有向图形式画出求解x=square root （ a+b） *d/e-e/d的数据流程序图，当a=4、b=8时，表示出该数据流程序图的执行过程。迭代结构的数据流程序图。7 、静态和动态数据流机的主要区别在哪里？答： （ 1 ）静态数据流机的数据令牌无标号。动态数据流机的数据令牌有标号；（ 2 ）静态数据流任意给定时刻当结点操作时每条弧上只能有一个数据令牌、动态数据流机中，任何一条弧上可出现多个不带目标号

87、的数据令牌；（ 3 ）静态数据流机中必须设控制令牌以满足要求，动态数据流机中不必须投控制令牌，因为令牌有识别时间、先后关系的标号；（ 4 ）静态数据流机不支持递归的并发激活，只支持一般循环，动态数据流机支持递归的并发激活；（ 5 ）静态数据流机不需硬件完成标记的匹配，动态数据流机需要硬件将标记附加在数据令牌上，并完成对标记的匹配工作。8 . 为进行智能信息处理， 智能计算机就具有哪些功能， 从系统结构上怎样来支持这些功能的实现？答 ：智能机是具有智能的高性能计算机. 它是一个知识信息的处理系统. 智能机能不断地学习，积累， 完善知识， 利用知识进行推理， 判断和求解问题. 它有大容量的知识库， 有高度并行处理，多重处理和分布处理能力的多个处理机， 是一种结构动态可变， 易于扩充的开放式系统， 提供有良好的人-机界面和多种智能接口.智能机中3 个重要的组成部分是知识库机， 推理机和智能接口处理机.