《计算机系统结构课后习题答案(1).pdf》由会员分享，可在线阅读，更多相关《计算机系统结构课后习题答案(1).pdf（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 第一章计算机系统结构的基本概念1.有一个计算机系统可按功能分成4 级，每级的指令互不相同，每一级的指令都比其下一级的指令在效能上强M倍，即第 i 级的一条指令能完成第i-1级的 M条指令的计算量。现若需第i 级的 N 条指令解释第 i+1级的一条指令，而有一段第 1 级的程序需要运行Ks，问在第 2、3 和 4 级上一段等效程序各需要运行多长时间？答：第 2 级上等效程序需运行：(N/M)*Ks。第 3 级上等效程序需运行：(N/M)*(N/M)*Ks。第 4 级上等效程序需运行：(N/M)*(N/M)*(N/M)*Ks。note:由题意可知：第i 级的一条指令能完成第i-1级的 M条指令
2、的计算量。而现在第i 级有 N条指令解释第 i+1级的一条指令，那么，我们就可以用N/M 来表示 N/M 表示第 i+1级需(N/M)条指令来完成第i 级的计算量。所以，当有一段第 1 级的程序需要运行Ks 时，在第 2 级就需要(N/M)Ks，以此类推2.硬件和软件在什么意义上是等效的？在什么意义上又是不等效的？试举例说明。答：软件和硬件在逻辑功能上是等效的，原理上，软件的功能可用硬件或固件完成，硬件的功能也可用软件模拟完成。但是实现的性能价格比，实现的难易程序不同。在 DOS操作系统时代，汉字系统是一个重要问题，早期的汉字系统的字库和处理程序都固化在汉卡（硬件）上，而随着 CPU、硬盘、内
3、存技术的不断发展，UCDOS把汉字系统的所有组成部份做成一个软件。3.试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系与影响。答：计算机系统结构、计算机组成、计算机实现互不相同，但又相互影响。（1）计算机的系统结构相同，但可采用不同的组成。如IBM370 系列有 115、125、135、158、168 等由低档到高档的多种型号机器。从汇编语言、机器语言程序设计者看到的概念性结构相同，均是由中央处理机/主存，通道、设备控制器，外设4 级构成。其中，中央处理机都有相同的机器指令和汇编指令系统，只是指令的分析、执行在低档机上采用顺序进行，在高档机上采用重叠、流水或其它并行处理方式。（
4、2）相同的组成可有多种不同的实现。如主存器件可用双极型的，也可用MOS型的；可用 VLSI 单片，也可用多片小规模集成电路组搭。（3）计算机的系统结构不同，会使采用的组成技术不同，反之组成也会影响结构。如为实现A:=B+CD:=E*F,可采用面向寄存器的系统结构，也可采用面向主存的三地址寻址方式的系统结构。要提高运行速度，可让相加与相乘并行，为此这两种结构在组成上都要求设置独立的加法器和乘法器。但对面向寄存器的系统结构还要求寄存器能同时被访问，而对面向主存的三地址寻址方式的系统结构并无此要求，倒是要求能同时形成多个访存操作数地址和能同时访存。又如微程序控制是组成影响结构的典型。通过改变控制存储
5、器中的微程序，就可改变系统的机器指令，改变结构。如果没有组成技术的进步，结构的进展是不可能的。综上所述，系统结构的设计必须结合应用考虑，为软件和算法的实现提供更多更好的支持，同时要考虑可能采用和准备采用的组成技术。应避免过多地或不合理地限制各种组成、实现技术的采用和发展，尽量做到既能方便地在低档机上用简单便宜的组成实现，又能在高档机上用复杂较贵的组成实现，这样，结构才有生命力；组成设计上2 面决定于结构，下面受限于实现技术。然而，它可与实现折衷权衡。例如，为达到速度要求，可用简单的组成但却是复杂的实现技术，也可用复杂的组成但却是一般速度的实现技术。前者要求高性能的器件，后者可能造成组成设计复杂
6、化和更多地采用专用芯片。组成和实现的权衡取决于性能价格比等因素；结构、组成和实现所包含的具体内容随不同时期及不同的计算机系统会有差异。软件的硬化和硬件的软件都反映了这一事实。VLSI 的发展更使结构组成和实现融为一体，难以分开。4.什么是透明性概念？对计算机系统结构，下列哪些是透明的？哪些是不透明的？存储器的模 m 交叉存取；浮点数据表示；I/O系统是采用通道方式还是外围处理机方式；数据总线宽度；字符行运算指令；阵列运算部件；通道是采用结合型还是独立型；PDP-11 系列的单总线结构；访问方式保护；程序性中断；串行、重叠还是流水控制方式；堆栈指令；存储器最小编址单位；Cache 存储器。答：透
7、明指的是客观存在的事物或属性从某个角度看不到。透明的有：存储器的模m交叉存取；数据总线宽度；阵列运算部件；通道是采用结合型还是独立型；PDP-11 系列的单总线结构串行、重叠还是流水控制方式；Cache 存储器。不透明的有：浮点数据表示；I/O系统是采用通道方式还是外围处理机方式；字符行运算指令；访问方式保护；程序性中断；堆栈指令；存储器最小编址单位。5.从机器（汇编）语言程序员看，以下哪些是透明的？指令地址寄存器；指令缓冲器；时标发生器；条件寄存器；乘法器；主存地址寄存器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器。答：透明的有：指令缓冲器、时标发生器、乘法器、先进先出链、移位器
8、、主存地址寄存器。6.下列哪些对系统程序员是透明的？哪些对应用程序员是透明的？系列机各档不同的数据通路宽度；虚拟存储器；Cache 存储器；程序状态字；“启动 I/O”指令；“执行”指令；指令缓冲寄存器。答：对系统程序员透明的有：系列机各档不同的数据通路宽度；Cache 存储器；指令缓冲寄存器；对应用程序员透明的有：系列机各档不同的数据通路宽度；Cache 存储器；指令缓冲寄存器；虚拟存储器；程序状态字；“启动 I/O”指令。note:系列机各档不同的数据通路宽度、Cache 存贮器、指令缓冲寄存器属于计算机组成，对系统和程序员和应用程序员都是透明的。虚拟存贮器、程序状态字、“启动 I/O”指
9、令，对系统程序员是不透明的，而对应用程序员却是透明的。“执行”指令则对系统程序员和应用程序员都是不透明的。7.想在系列机中发展一种新型号机器，你认为下列哪些设想是可以考虑的，哪些则不行的？为什么？（1）新增加字符数据类型和若干条字符处理指令，以支持事务处理程序的编译。（2）为增强中断处理功能，将中断分级由原来的4 级增加到 5 级，并重新调整中断响应的优先次序。3（3）在 CPU和主存之间增设 Cache 存储器，以克服因主存访问速率过低而造成的系统性能瓶颈。（4）为解决计算误差较大，将机器中浮点数的下溢处理方法由原来的恒置“1”法，改为用 ROM存取下溢处理结果的查表舍入法。（5）为增加寻址
10、灵活性和减少平均指令字长，将原等长操作码指令改为有3 类不同码长的扩展操作码；将源操作数寻址方式由操作码指明改成如VAX-11 那种设寻址方式位字段指明。（6）将 CPU与主存间的数据通路宽度由16 位扩展成 32 位，以加快主机内部信息的传送。（7）为减少公用总路线的使用冲突，将单总线改为双总线。（8）把原 0 号通用寄存器改作堆栈指示器。答：可以考虑的有：1,3,4,6,7。不可以考虑的有：2,5,8。原则是看改进后能否保持软件的可移植性。P.S.为了能使软件长期稳定，就要在相当长的时期里保证系统结构基本不变，因此在确定系列结构时要非常慎重。其中最主要是确定好系列机的指令系统、数据表示及概
11、念性结构。既要考虑满足应用的各种需要和发展，又要考虑能方便地采用从低速到高速的各种组成的实现技术，即使用复杂、昂贵的组成实现时，也还能充分发挥该实现方法所带来的好处。8.并行处理计算机除分布处理、MPP和机群系统外，有哪4 种基本结构？列举它们各自要解决的主要问题。答：除了分布处理，MPP 和机群系统外，并行处理计算机按其基本结构特征可分为流水线计算机，阵列处理机，多处理机和数据流计算机四种不同的结构。流水线计算机主要通过时间重叠，让多个部件在时间上交划重叠地并行招待运算和处理，以实现时间上的并行。它主要应解决：拥塞控制，冲突防止，流水线调度等问题。阵列处理机主要通过资源重复实现空间上的并行。
12、它主要应解决：处理单元灵活、规律的互连模式和互连网络设计，数据在存储器中的分布算法等问题。多处理机主要通过资源共享，让一组计算机在统一的操作系统全盘控制下，实现软件和硬件各级上的相互作用，达到时间和空间上的异步并行。它主要应解决：处理机间互连等硬件结构，进程间的同上步和通讯，多处理机调度等问题。数据流计算机设有共享变量的概念，指令执行顺序只受指令中数据的相关性制约。数据是以表示某一操作数或参数已准备就绪的数据令牌直接在指令之间传递。它主要应解决：研究合适的硬件组织和结构，高效执行的数据流语言等问题。9.计算机系统的 3T 性能目标是什么？答：计算机系统的3T 性能目标是 1TFLOPS 计算能
13、力，1TBYTE 主存容量和 1TBYTES 的 I/O带宽。4 第二章数据表示与指令系统1.数据结构和机器的数据表示之间是什么关系？确定和引入数据表示的基本原则是什么？答：数据表示是能由硬件直接识别和引用的数据类型。数据结构反映各种数据元素或信息单元之间的结构关系。数据结构要通过软件映象变换成机器所具有的各种数据表示实现，所以数据表示是数据结构的组成元素。不同的数据表示可为数据结构的实现提供不同的支持，表现在实现效率和方便性不同。数据表示和数据结构是软件、硬件的交界面。除基本数据表示不可少外，高级数据表示的引入遵循以下原则：（1）看系统的效率有否提高，是否养活了实现时间和存储空间。（2）看引
14、入这种数据表示后，其通用性和利用率是否高。2.标志符数据表示与描述符数据表示有何区别？描述符数据表示与向量数据表示对向量数据结构所提供的支持有什么不同？答：标志符数据表示与描述符数据表示的差别是标志符与每个数据相连，合存于同一存储单元，描述单个数据的类型特性;描述符是与数据分开存放，用于描述向量、数组等成块数据的特征。描述符数据表示为向量、数组的的实现提供了支持，有利于简化高级语言程序编译中的代码生成，可以比变址法更快地形成数据元素的地址。但描述符数据表示并不支持向量、数组数据结构的高效实现。而在有向量、数组数据表示的向量处理机上，硬件上设置有丰富的赂量或阵列运算指令，配有流水或阵列方式处理的
15、高速运算器，不仅能快速形成向量、数组的元素地址，更重要的是便于实现把向量各元素成块预取到中央处理机，用一条向量、数组指令流水或同时对整个向量、数组高速处理如让硬件越界判断与元素运算并行。这些比起用与向量、阵列无关的机器语言和数据表示串行实现要高效的多。3.堆栈型机器与通用寄存器型机器的主要区别是什么？堆栈型机器系统结构为程序调用哪些操作提供了支持？答：通用寄存器型机器对堆栈数据结构实现的支持是较差的。表现在：(1)堆栈操作的指令少，功能单一；(2)堆栈在存储器内，访问堆栈速度低；(3)堆栈通常只用于保存于程序调用时的返回地址，少量用堆栈实现程序间的参数传递。而堆栈型机器则不同，表现在：(1)有
16、高速寄存器组成的硬件堆栈，并与主存中堆栈区在逻辑上组成整体，使堆栈的访问速度是寄存器的，容量是主存的；(2)丰富的堆栈指令可对堆栈中的数据进行各种运算和处理；(3)有力地支持高级语言的编译；(4)有力地支持子程序的嵌套和递归调用。堆栈型机器系统结构有力地支持子程序的嵌套和递归调用。在程序调用时将返回地址、条件码、关键寄存器的内容等全部压入堆栈，待子程序返回时，再从堆栈中弹出。4.设某机阶值 6 位、尾数 48 位，阶符和数符不在其内，当尾数分别以2、8、16 为基时，在非负阶、正尾数、规格化数情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示的规格化
17、数的总个数。解：依题意知：p=6 m=48 rm=2,8,16，m=m/log2(rm)，列下表：5 p=6,m=48,rm=2(m=48)p=6,m=48,rm=8(m=16)p=6,m=48,rm=16(m=12)最小阶(非负阶，最小为 0)000最大阶(2p-1)26-126-126-1最小尾数值(rm(-1)1/21/81/16最大尾数值(1-rm(-m)1-2(-48)1-8(-16)，即(1-2(-48)1-16(-12)，即(1-2(-48)可表示的最小值1/21/81/16可表示的最大值263*(1-2(-48)863*(1-8(-16)1663*(1-16(-12)阶的个数(
18、2p)262626可表示的尾数的个数248*(2-1)/2816*(8-1)/81612*(16-1)/16可表示的规格化数的个数26*248*(2-1)/226*816*(8-1)/826*1612*(16-1)/16note:可表示的最小值=rm(最小阶)*最小尾数值=rm0*rm(-1)=rm(-1);可表示的最大值=rm(最大阶)*最大尾数值=rm(2p-1)*(1-rm(-m);可表示的尾数的个数=rmm*(rm-1)/rm;可表示的规格化数的个数=阶的个数*尾数的个数=2p*rmm*(rm-1)/rm。5.（1）浮点数系统使用的阶基rp=2,阶值位数 p=2,尾数基值 rm=10，
19、以 rm 为基的尾数位数 m=1,按照使用的倍数来说，等价于m=4,试计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数。（2）对于 rp=2,p=2,rm=4,m=2,重复以上计算。解：依题意列下表：p=2,rm=10,m=1p=2,rm=4,m=2最小尾数值10-1=0.14-1=0.25最大尾数值1-10-1=0.91-4-2=15/16最大阶值2p-1=33可表示的最小值0.10.25可表示的最大值103*0.9=90043*15/16=60可表示数的个数3648题中“按照使用的倍数来说，等价于m=4,”这个 m=4,因为 23
20、10=fbyte 通道极限流量应大于或等于设备对通道要求的流量fbyte。如果字节多路通道上所挂设备台数为m,设备的速率为 fi，为了不丢失信息，应满足：1/(TS+TD)=m*fi fi也就是设备发出字节传送请求间隔时间(500 s)的倒数，所以：m=4。4.某虚拟存储器共8 个页面，每页 1024 个字，实际主存为4096 个字，采用页表法进行地址映象。映象表的内容如下表所示。虚页号01234567实页号31232100装入位11001010注：我把虚页号加上了。(1)列出会发生页面失效的全部虚页号；(2)按以下虚地址计算主存实地址：0，3728，1023，1024，2055，7800，4
21、096，6800。解:(1)会发生页面失效的全部虚页号为：2,3,5,7。17 (2)虚地址虚页号页内位移装入位实页号页内位移实地址0001303072327836560页面失效页面失效无102301023131023409510241011010242055270页面失效页面失效无780076320页面失效页面失效无40964012020486800665610656656剖析：(1)根据页表法列出表2，当装入位为 0 时，即为页面失效，再找出相对应的虚页号即可。(2)虚页号=虚地址/页面大小页内位移量=虚地址虚页号*页面大小实地址实页号*页面大小页内位移量由于可以用替换算法解决页面失效的问
22、题，所以，发生页面失效的虚页2,3,5,7仍然可以有相应的实地址，但这样要在页表中建立新的虚实地址对应关系，新的虚实地址对应关系和原来的对应关系相同的可能性就很小了。5、一个段页式虚拟存储器。虚地址有2 位段号、2 位页号、11 位页内位移（按字编址），主存容量为 32K 字。每段可有访问方式保护，其页表和保护位如下表所示。段号0123访问方式只读可读/执行可读/写/执行可读/写虚页 0 所在位置实页 9在辅存上页表不在主存内实页 14虚页 1 所在位置实页 3实页 0页表不在主存内实页 1虚页 2 所在位置在辅存上实页 15页表不在主存内实页 6虚页 3 所在位置实页 12实页 8页表不在主
23、存内在辅存上(1)此地址空间中共有多少个虚页？(2)当程序中遇到下列情况时方式段页页内位移取数取数取数0 1 3 1 1 3 1 10 2047 18 存数存数存数转移至此取数取数转移至此0 2 1 1 0 2 31 1 0 3 2 0 04 2 14 100 50 5 60写出由虚地址计算出实地址。说明哪个会发生段失效、页面或保护失效失效。解答:(1)该地址空间中共有16 个虚页。(2)程序中遇到上表中各情况时，是否会发生段失效、页失效或保护失效及相应的主存实地址的情况如下表所示：方式段 页页内位移段失效页失效实页号实地址保护失效取数取数取数存数存数存数转移至此取数取数转移至此0 1 3 0
24、 2 1 1 0 2 31 1 3 1 1 0 3 2 0 01 10 2047 4 2 14 100 50 5 60无无无无有无无无有无无无有无/有无有/无3 0 无3 无无8 无无146145 10 无6184 无无16484 无无28732无无/有/无/有剖析：(1)虚地址中段号有2 位，页号有 2 位，也就是每个程序最多只能有22=4个段，每个段至多只能有22=4页，所以该地址空间中共有4*4=16个虚页。(2)先从题意得知：实地址：15 位，其中实页号4 位，页内位移 11 位页大小为 2K 字（由页内位移得知）6.设某程序包含5 个虚页，其页地址为4，5，3，2，5，1，3，2，2
25、，5，1，3。当使用 LRU 算法替换时，为获得最高命中率，至少应分配给该程序几个实页？其可能的最高命中率为多少？19 7.采用页式管理的虚拟存储器，分时运行两道程序。其中，程序X 为 DO 50 I=1,3 B(I)=A(I)-C(I)IF(B(I)LE0)GOTO 40 D(I)=2*C(I)-A(I)IF(D(I)EQ 0)GOTO 50 40 E(I)=0 50 CONTINUE Data:A=(-4,+2,0)C=(-3,0,+1)每 个 数 组 分 别 放 在 不 同 的 页 面 中;而 程 序Y在 运 行 过 程 中，其 数 组 将 依 次 用 到 程 序 空 间 的 第3,5,
26、4,2,5,3,1,3,2,5,1,3,1,5,2页。如果采用LRU 算法，实存却只有8 页位置可供存放数组之用。试问为这两首程序的数组分别分配多少个实页最为合适？为什么？解答：分别分配给程序X 和 Y 的数组 4 个实页最为合适。根据题意，程序 X 依次调用数组 A,C,B,B,E,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 的页地址流进行堆栈处理的过程可知，分配
27、给程序X 的数组 5 个实页最为合适;分析使用 LRU算法对程序 Y 的页地址流进行堆栈处理的过程可知，分配给程序Y 的数组 4 个实页最为合适。但实存只有 8 页位置可供存放数组之用，所以，分别分配给程序X 和 Y 的数组 4 个实页。note:分时运行在微观上是串行的，就是说，分时运行时把时间划分为若干时间片，每个程序轮流占用时间片;在宏观上是并行的，就是说，每个程序在一个时间片内并不能运行完。总的来看，是同时运行的，所以两个程序分配的实页和不能大于8。20 我不了解 FORTRAN，找朋友把上面的源代码转成C了：main()int A=-4,2,0;int C=-3,0,1;for(i=
28、0,i0)Ei=0;8.设一个按位编址的虚拟存储器，它应可对应1K 个任务，但在一段较长时间内，一般只有4 个任务在使用，故用容量为 4 行的相联寄存器组硬件来缩短被变换的虚地址中的用户位位数；每个任务的程序空间最大可达4096 页，每页为 512 个字节，实主存容量为220 位；设快表用按地址访问存储器构成，行数为32，快表的地址是经散列形成；为减少散列冲突，配有两套独立相等比较电路。请设计该地址变换机构，内容包括：(1)画出其虚、实地址经快表变换之逻辑结构示意图；(2)相联寄存器组中每个寄存器的相联比较位数；(3)相联寄存器组中每个寄存器的总位数；(4)散列变换硬件的输入位数和输出位数；(
29、5)每个相等比较器的位数；(6)快表的总容量（以位为单位）。解:(1)依题意得知：虚地址为 34 位，其中用户号为 10 位（对应 1K 的任务）、虚页号 12 位（每个任务 4096 页）、页内位移 12 位（每页 512 字节，512 字节=512*8=1024*4=212）实地址为 20 位，其中实页号 8 位，页内位移 12 位（与虚页页内位移对应）相联寄存器的作用：把 10 位的用户号转换为2 位的 ID（因为一般只有 4 个任务在使用），并把 ID 与虚地址的虚页号合并到快表中查实页号。快表的作用：相当于页表，即虚页号对实页号的对应关系。但又有所简化（原因是如果用用户号和虚页号与实
30、页号对应，前者就有22 位，现改进后虚页号只有14 位了）21 (2)相联寄存器组中每个寄存器的相联比较位数为10（与虚地址中的用户号宽度对应）(3)相联寄存器组中每个寄存器的总数为12（用户号宽度+ID 宽度）(4)散列变换硬件的输入位数为14 位（虚页号宽度+相联寄存器中 ID 的宽度），输出位数为 8 位（与主存中的实页号宽度对应）(5)每个相等比较器的位数=ID+用户虚页号 nv=2+12=14(位)。(6)快表的总容量：32 行*（14(输入位数)+8（输出位数）*2=32*22*2 9.考虑一个 920 个字的程序，其访问虚存的地址流为20，22，208，214，146，618，3
31、70，490，492，868，916，728。(1)若页面大小为 200 字，主存容量为400 字，采用 FIFO 替换算法，请按访存的各个时刻，写出其虚页地址流，计算主存的命中率；(2)若页面大小为 100 字，再做一遍；(3)若页面大小为 400 字，再做一遍；(4)由(1)、(2)、(3)的结果可得出什么结论？(5)若把主存容量增加到800 字，按第(1)小题再做一遍，又可得出什么结论？解：(1)主存容量 400 字，页面大小 200 字，所以主存实页数为2；把地址流转换为页地址流，以第一个虚地址流转换为页地址流为例说明：求模公式为：INT（地址/页面大小），就是把地址整除于页面大小，得
32、INT（20/200）=0，下同，所以页地址流为：0,0,1,1,0,3,1,2,2,4,4,3 按 FIFO 算法得出替换过程为：0（调入），0（命中），1（调入），1（命中），0（命中），3（替换 0，0 比 1先入队，所以被替换，下同），1（命中），2（替换 1），2（命中），4（替换 3），4（命中），3（替换 2），所以总共命中 6 次。故命中率 H=6/12=50%(2)方法同（1）H=25%22 (3)H=50%(4)由以上结论可得，FIFO 算法的条件下，当页面大小发生变化时，其命中率变化是：一开始随页面大小增大命中率（第一步与第二步比较），但当页面大小增到一定时，命中率不再增
33、加（第一步与第三步比较）。(5)命中率为 58%，结论是如果分配给主存容量增加时可以搞高命中率。10.在一个页式二级虚拟存储器中，采用FIFO 算法进行页面替换，发现命中率H 太低，因此有下列建议：(1)增大辅存容量;(2)增大主存容量(页数);(3)FIFO改为 LRU;(4)FIFO改为 LRU，并增大主存容量(页数);(5)FIFO改为 LRU，并增大页面大小。试分析上述各建议对命中率的影响情况。解答：(1)增大辅存容量，对命中率H无影响。(2)增大主存容量(页数)，可普遍提高命中率。(3)FIFO改为 LRU，一般可提高命中率。(4)FIFO改为 LRU，并增大主存容量(页数)，一般可
34、使命中率有较大提高。(5)FIFO改为 LRU，并增大页面大小，如果原来页面很小，则会使命中率显著上升，如果原来页面很大，则会使命中率下降。11.采用组相联映象的Cache 存储器，Cache 为 1KB，要求 Cache 的每一块在一个主存周期内能从主存取得。主存模 4 交叉，每个分体宽为32 位，总容量为 256KB。用按地址访问存储器构成相联目录表实现主存地址到Cache地址的变换，并约定用4 个外相等比较电路。请设计此相联目录表，求出该表之行数、总位数及每个比较电路的位数。解答：设 Cache 地址中的组内块号为s，相联目录表的行数是2(13-s)，总位数是(8+2s)*2(15-s)
35、，每个比较电路的位数为8+s。剖析：在一个主存周期内主存能访问到的字节数为mW=4*32/8=16(Byte)。要求 Cache 的每一块在一个主存周期内能从主存取得，所以，Cache 中每块的块内字数不能大于16Bytes。为了加速调块，一般让每块的大小等于在一个主存周期内主存能访问到的字数，即16Bytes。设 Cache 地址中的组内块号为s，相联目录表的行数=Cache 地址内的组数 Q=Cache 容量/(每组块数*每块大小)=1KB/(S*4*32)=213/(2s*27)=2(6-s)。主存块数/Cache块数=256=2*8，所以，主存地址中的区号nd=8。每个比较电路的位数=
36、nd+s=nd+s=8+s。相 联 目 录 表 的 总 位 数=表 中 子 目 录 表 的 个 数*每 个 子 目 录 表 的 位 数*相 联 目 录 表 的 行 数=4*(nd+s+s)*Q=4*(8+2s)*2(6-s)=(8+2s)*2(8-s)。note：若认为相等比较电路的个数=组内块数，则相联目录表的行数=24，每个比较电路的位数=10，相联目录表的23 总位数=12*26。12.有一个 Cache 存储器。主存共分8 个块(07),Cache为 4 个块(03),采用组相联映象，组内块数为2 块，替换算法为近期最少使用算法(LRU)。(1)画出主存、Cache 地址的各字段对应关
37、系(标出位数)图;(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 地址的各字段的位数及其对应关系如下图所示 (2)主存块、Cache 块的映象对应关系如下图所示24(3)Cache中各块随时间的使用状况如下图所示。图中标*号的是候选替换块的块号，H：命中;R：替换;L：失效。(4)发生
38、块失效又发生块争用的时刻有6、7、9、10、11、12、14、15。(5)Cache的块命中率 Hc=3/15=0.2。剖析：由于主存块、Cache 块之间存在上述的映象对应关系，主存的第0、1、4、5 块只能映象装入或替换物理 Cache 的第 0、1 块;主存的第 2、3、6、7 块只能映象装入或替换物理Cache 的第 2、3 块。13.采用组相联映象，LRU替换算法的 Cache 存储器，发现等效访问速度不高，为此建议：(1)增大主存容量;(2)增大 Cache 的块数(块的大小不变);(3)增大组相联组的大小(块的大小不变);(4)增大块的大小(组的大小和 Cache 总容量不变);
39、(5)提高 Cache 本身器件的访问速度。解答：(1)增大主存容量对 Cache 的访问时间 ta 基本不影响，从而对Cache 的等效访问速度基本不影响。(2)增大 Cache 的块数(块的大小不变)一般将使 Cache 的命中率 Hc 上升，从而使 ta 下降，从而提高 Cache的等效访问速度。(3)增大组相联组的大小(块的大小不变)一般将使 Cache 的命中率 Hc 上升，从而使 ta 下降，从而提高 Cache的等效访问速度。(4)增大块的大小(组的大小和 Cache 总容量不变)一般将使 ta 下降，从而提高Cache 的等效访问速度。(5)提高 Cache 本身器件的访问速度
40、一般将缩短ta，从而提高 Cache 的等效访问速度。14.你对 Cache 存储器的速度不满，于是申请到一批有限的经费，为能发挥其最大经济效益，有人建议你再买一些同样速度的 Cache 片子以扩充其容量;而另有人建议你干脆去买更高速的Cache 片子将现有的低速Cache 片子全部换掉。你认为哪种建议可取？你如何做决定？为什么？解答：Cache本身的速度与容量都会影响Cache 存储器的等效访问速度。如果对 Cache 存储器的等效访问速度不满，需要改进的话，就要作具体分析，看看现在Cache 存储器的等效访问速度是否已接近于Cache 本身的速度。如果差得较远，说明Cache 的命中率低，
41、应从提高Cache 命中率着手，包括调整组的大小、块的大小、替换算法以及增大 Cache 容量等。如果 Cache 存储器的等效访问速度已经非常接近于Cache 本身的速度还不能满足需要，就应25 该更换更高速的 Cache 片子。26 第五章重叠、流水和向量处理机1.假设指令的解释分取指、分析与执行3 步，每步的时间相应为t 取指、t 分析、t 执行,(1)分别计算下列几种情况下，执行完100 条指令所需时间的一般关系式：a.顺序方式;b.仅“执行 k”与“取指 k+1”重叠;c.仅“执行 k”、“分析 k+1”、“取指 k+2”重叠;(2)分别在 t 取指=t 分析=2、t 执行=1 及
42、t 取指=t 执行=5、t 分析=2 两种情况下，计算出上述各结果。解：(1)执行完 100 条指令所需时间：a.100*(t取指+t 分析+t 执行);b.t取指+100*t分析+99*max(t取指+t 执行)+t执行;c.t取指+max(t取指+t 分析)+98*max(t取指+t 分析+t 执行)+max(t分析+t 执行)+t执行。(2)在 t 取指=t 分析=2、t 执行=1 的情况下，执行完100 条指令所需时间：a.500 b.401 c.203 在 t 取指=t 执行=5、t 分析=2 的情况下，执行完100 条指令所需时间：a.1200 b.705 c.510 2.流水线有
43、 4 个功能部件组成，每个功能部件的延迟时间为t，当输入 10 个数据后间歇 5t 又输入 10 个数据，如此周期性地工作，求此时流水线的吞吐率，并画出时空图。解：TP=10/14t=5/7t 时空图：3.有一个浮点乘流水线如图5.35(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A*B*C*D的时空图以及输入端的变化，并求出该流水线的吞吐率和效率;当流水线改为图5.35(b)形式实现同一计27 算时，求该流水线的效率及吞吐率。图 5.35(a)图 5.35(b)解：按图 5.35(a)组织的流水线时，TP=3/13 t;=3/11。实现 A*B*C*D的时空图如图 05
44、04 所示：图 0504 按图 5.35(a)组织的流水线时，TP=3/13 t;=3/11。实现 A*B*C*D的时空图如图 0504 所示：图 0505 28 剖析：为了减少运算过程中的操作数相关，A*B*C*D应改为(A*B)*(C*D)进行运算。4.一个 4 段的双输入端规格化浮点加法流水线，每段经过时间10ns,输出可直接返回输入或将结果暂存于相应缓冲器中，问最少需经多少时间能求(10)(i=1)Ai，并画出时空图。答:时空图如下：求(10)(i=1)Ai需要的最知时间是 170ns。剖 析：为 了 避 免 先 写 后 读 相 关，使 流 水 线 性 能 尽 可 能 高，需 将(10
45、)(i=1)Ai调 整 成(A1+A2)+(A3+A4)+(A9+A10)+(A5+A6)+(A7+A8)。5.为提高流水线效率可采用哪两种主要途径来克服速度瓶颈？现有3 段流水线，各段经过时间依次为t、3t、t，(1)分别计算在连续输入3 条指令时和 30 条指令时的吞吐率和效率。(2)按两种途径之一改进，画出你的流水线结构示意图，同时计算连续输入3 条指令和 30 条指令时的吞吐率。(3)通过对(1)、(2)两小题的计算比较可得出什么结论？解答:为提高流水线效率可采用瓶颈希再细分和瓶颈段并联两种主要途径来克服速度瓶颈。29 (1)连续输入 3 条指令时的吞吐率TP3=3/11 t;效率3=
46、5/11。连续输入 30 条指令时的吞吐率TP30=15/46t;效率3=25/46。(2)改进后的流水线结构示意图大体如图5.35(a)和图 5.35(b)。连续输入 3 条指令时的吞吐率TP3=3/7 t;效率3=3/7。连续输入 30 条指令时的吞吐率TP30=15/17t;效率3=15/17。(3)只有当连续输入流水线的指令足够多时，流水线的实际吞吐率和效率才会提高。6.有一个双输入端的加-乘双功能静态流水线，由经过时间为t、2t、2t,t 的 1、2、3、4 四个子过程构成。加按 1-2-4连接，乘按 1-3-4连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行A*(B
47、+C*(D+E*F)+G*H的运算，请调整计算顺序画出能获得尽量高的吞吐率的流水时空图，标出流水线入、出端数的变化情况，求出完成全部运算的时间及此期间流水线的效率。如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程3 不能再细分，只能用并联方法改进，问流水线的效率为多少？解:根据题意，画出流水线吞吐率尽可能高的时空图如图0507：图 0507 在此期间的流水线效率=(6*4 t+3*4t)/4*24t=3/8 如果将瓶颈子过程2 和 3 均细分成两个子过程，则时空图如图0508 所示：图 0508 由图可见，完成全部运算最少需要18t。若子过程 3 不能再细分，只能用并联方法
48、改进，则则时空图如图0509 所示：图 0509 30 这种情况下，流水线效率=(24 t+12 t)/6*18t=1/3 剖析：因为是双功能静态流水线，为了能有高的吞吐率，应减少流水线的功能切换次数。因此，应将算法调整成先作一连串的乘，然后再切换成一连串的加。原式展开成A*B+A*C*D+A*C*E*F+G*H，先进行乘法流水，为了减少因先写后读相关而等待的时间，应尽量安排对计算式子项数最多的乘法先进行操作，即先计算A*C*E*F，再计算A*C*D，.7.现有长度为 8 的向量 A 和 B，请分别画出下列 4 种结构的处理器上求点积A*B 的时空图，并求完成全部结果的最少时钟拍数。设处理器中
49、每个部件的输出均可直接送到任何部件的输入或存入缓冲器中去，其间的传送延时不计，指令和源操作数均能连续提供。(1)处理器有一个乘法部件和一个加法部件，不能同时工作，部件内也只能以顺序方式工作，完成一次加法或乘法均需 5 拍;(2)与(1)基本相同，只是乘法部件和加法部件可并行;(3)处理器有一个乘、加法双功能静态流水线，乘、加法均由5 个流水段构成，各段经过时间要1 拍;(4)处理器有乘、加法两条流水线，可同时工作，各由5 段构成，每段经过时间为1 拍。解答：(1)在这种结构的处理器上求点积A*B 的时空图如图 0510 所示：图 0510 完成全部运算最少需要75 拍。(2)在这种结构的处理器
50、上求点积A*B 的时空图如图 0511 所示：图 0511 31 完成全部运算最少需要45 拍。(3)在这种结构的处理器上求点积A*B 的时空图如图 0512 所示：图 0512 完成全部运算最少需要30 拍。(4)在这种结构的处理器上求点积A*B 的时空图如图 0513 所示：图 0513 完成全部运算最少需要 26 拍。剖析：向量 A*B 的点积为 A*B=(8)(i=1)ai*bi=a1*b1+a2*b2+a3*b3+a4*b4+a5*b*+a6*b*+a7*b7+a8*b8,共需 8 次乘法和 7 次加法。8.试总结 IBM 360/91解决流水线控制的一般方法、途径和特点。在流水线中