计算机系统结构

4.1解释下列术语 指令级并行：简称ILP。是指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。

指令调度：通过在编译时让编译器重新组织指令顺序或通过硬件在执行时调整指令顺序来消除冲突。

指令的动态调度：是指在保持数据流和异常行为的情况下，通过硬件对指令执行顺序进行重新安排，以提高流水线的利用率且减少停顿现象。是由硬件在程序实际运行时实施的。

指令的静态调度：是指依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化的。

保留站：在采用Tomasulo算法的MIPS处理器浮点部件中，在运算部件的入口设置的用来保存一条已经流出并等待到本功能部件执行的指令（相关信息）。

4.2 简述Tomasulo算法的基本思想。

答：核心思想是：① 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减小到最少；② 通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现，它保存等待流出和正在流出指令所需要的操作数。

基本思想：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。

第5章 存储层次

5.1解释下列术语

失效开销：CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。

强制性失效：当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。

容量失效：如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。

冲突失效：在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。

2：1Cache经验规则：大小为N的直接映象Cache的失效率约等于大小为N /2的两路组相联Cache的实效率。

第 11 页 共 17 页

计算机系统结构

Victim Cache：位于Cache和存储器之间的又一级Cache，容量小，采用全相联策略。用于存放由于失效而被丢弃（替换）的那些块。每当失效发生时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需块。

非阻塞Cache：Cache在等待预取数据返回时，还能继续提供指令和数据。

请求字优先：调块时，首先向存储器请求CPU所要的请求字。请求字一旦到达，就立即送往CPU，让CPU继续执行，同时从存储器调入该块的其余部分。

5.4降低Cache失效率有哪几种方法？简述其基本思想。 答：常用的降低Cache失效率的方法有下面几种：

（1） 增加Cache块大小。增加块大小利用了程序的空间局部性。 （2） 增加Cache的容量。 （3） 提高相联度，降低冲突失效。 （4） 伪相联Cache，降低冲突失效。当对伪相联Cache进行访问时，首先是按与直接映象相同的方式进行访问。如果命中，则从相应的块中取出所访问的数据，送给CPU，访问结束。如果不命中，就将索引字段的最高位取反，然后按照新索引去寻找“伪相联组”中的对应块。如果这一块的标识匹配，则称发生了“伪命中”。否则，就访问下一级存储器。

（5） 硬件预取技术。在处理器提出访问请求前预取指令和数据。 （6） 由编译器控制的预取，硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。

（7） 编译器优化，通过对软件的优化来降低失效率。 （8） “牺牲”Cache。在Cache和其下一级存储器的数据通路之间增设一个全相联的小Cache，存放因冲突而被替换出去的那些块。每当发生不命中时，在访问下一级存储器之前，先检查“牺牲”Cache中是否含有所需的块。如果有，就将该块与Cache中某个块做交换，把所需的块从“牺牲”Cache 调入Cache。

5.5简述减小Cache失效开销的几种方法。

答：让读失效优先于写、写缓冲合并、请求字处理技术、非阻塞Cache或非锁定Cache技术、采用二级Cache。

5.6 通过编译器对程序优化来改进Cache性能的方法有哪几种？简述其基本思想。 答：（1）数组合并。通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干个数组的同一维，这些访问可能会相互干扰，导致冲突失效，可以将这些相互独立的数组合并成一个复合数组，使得一个Cache块中能包含全部所需元素。（2）内外循环交换。循环嵌套时，程序没有按数据在存储器中的顺序访问。只要简单地交换内外循环，就能使程序按数据在存储器中的存储顺序进行访问。（3）循环融合。有些程序含有几部分独立的程序段，它们用相同的循环访问同样的数组，对相同的数据作不同的运算。通过将它们融合成一个单一循环，能使读入Cache的数据被替换出去之前得到反复的使用。（4）分块。通过改进时间局部性来减少失效。分块不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。

5.10 假设对指令Cache的访问占全部访问的75%；而对数据Cache的访问占全部访问

第 12 页 共 17 页

计算机系统结构

的25%。Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，32KB的指令Cache的失效率为0.39%，32KB的数据Cache的失效率为4.82%，64KB的混合Cache的失效率为1.35%。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？

解：（1）根据题意，约75%的访存为取指令。 因此，分离Cache的总体失效率为：（75%×0.15%）＋（25%×3.77%）＝1.055%； 容量为128KB的混合Cache的失效率略低一些，只有0.95%。 （2）平均访存时间公式可以分为指令访问和数据访问两部分：

平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间＋数据失效率×失效开销）

所以，两种结构的平均访存时间分别为：

分离Cache的平均访存时间＝75%×（1＋0.15%×50）＋25%×（1＋3.77%×50） ＝（75%×1.075）＋（25%×2.885）＝1.5275

混合Cache的平均访存时间＝75%×（1＋0.95%×50）＋25%×（1＋1＋0.95%×50） ＝（75%×1.475）＋（25%×2.475）＝1.725

因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构相关。

第6章输入输出系统

6.1 解释以下术语

可靠性：指系统从某个初始参考点开始一直连续提供服务的能力，它通常用平均无故障时间来衡量。

可用性：指系统正常工作的时间在连续两次正常服务间隔时间中所占的比率。

可信性：指服务的质量，即在多大程度上可以合理地认为服务是可靠的。

分离事务总线：将总线事务分成请求和应答两部分。在请求和应答之间的空闲时间内，总线可以供给其它的I/O使用。采用这种技术的总线称为分离事务总线。

通道：专门负责整个计算机系统输入/输出工作的专用处理机，能执行有限的一组输入输出指令。

6.2 假设一台计算机的I/O处理时间占10%，当其CPU性能改进为原来的100倍，而I/O性能仅改进为原来的2倍时，系统总体性能会有什么样的变化？

解：加速比?1?16.94

10%/2?90%/100

6.3 RAID有哪些分级？各有何特点？

第 13 页 共 17 页

计算机系统结构

答：(1)RAID0。亦称数据分块，即把数据分布在多个盘上，实际上是非冗余阵列，无冗余信息。(2)RAID1。亦称镜像盘，使用双备份磁盘。每当数据写入一个磁盘时，将该数据也写到另一个冗余盘，这样形成信息的两份复制品。如果一个磁盘失效，系统可以到镜像盘中获得所需要的信息。镜像是最昂贵的解决方法。特点是系统可靠性很高，但效率很低。(3)RAID2。位交叉式海明编码阵列。即数据以位或字节交叉的方式存于各盘，采用海明编码。原理上比较优越，但冗余信息的开销太大，因此未被广泛应用。(4)RAID3。位交叉奇偶校验盘阵列，是单盘容错并行传输的阵列。即数据以位或字节交叉的方式存于各盘，冗余的奇偶校验信息存储在一台专用盘上。(5)RAID4。专用奇偶校验独立存取盘阵列。即数据以块(块大小可变)交叉的方式存于各盘，冗余的奇偶校验信息存在一台专用盘上。(6)RAID5。块交叉分布式奇偶校验盘阵列，是旋转奇偶校验独立存取的阵列。即数据以块交叉的方式存于各盘，但无专用的校验盘，而是把冗余的奇偶校验信息均匀地分布在所有磁盘上。(7)RAID6。双维奇偶校验独立存取盘阵列。即数据以块(块大小可变)交叉的方式存于各盘，冗余的检、纠错信息均匀地分布在所有磁盘上。并且，每次写入数据都要访问一个数据盘和两个校验盘，可容忍双盘出错。

6.5计算机系统字长32位，包含两个选择通道和一个多路通道，每个选择通道上连接了两台磁盘机和两台磁带机，多路通道上连接了了两台行式打印机，两台读卡机，10台终端，假定各设备的传输率如下：

磁盘机：800KBps 磁带机：200KBps 行打机：6.6KBps 读卡机：1.2KBps 终 端：1KBps

计算该计算机系统的最大I/O数据传输率。

解：本题要求计算通道的吞吐率，而且机器有一个多路通道，这就有两种可能：字节多路通道和数组多路通道。因为如果将多路通道组织成数组多路通道，某个时刻通道只能为一台设备传送数据，所以它的传输率是所有设备的传输率的最大值，而如果将它组织成字节多路通道，该通道的最大传输率就是所有设备的传输率之和。 所以在本题中，从性能上考虑，应组织成字节多路通道形式。 所以此类通道的最大传输率为：

（1）fBYTE＝∑fi＝f打印机传输率×2＋f读卡机传输率×2＋f终端传输率×10＝25.6KBps （i＝1..14） （2）两个选择通道连接的设备相同，所以只要计算其中一个通道的传输率既可。因为磁盘机的传输率大于磁带机。所以此类通道的传输率为：

max{800，200}＝800KBps

所以本系统的最大数据传输率为： f系统＝2×800＋25.6＝1625.6KBps。

6.6 简述通道完成一次数据传输的主要过程。

答：（1）在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，并启动通道。 (2) 通道处理机执行CPU为它组织的通道程序，完成指定的数据I/O工作。 (3) 通道程序结束后向CPU发中断请求。CPU响应这个中断请求后，第二次进入操作系统，调用管理程序对I/O中断请求进行处理。

第 14 页 共 17 页

计算机系统结构

第7章 互连网络

7.1 解释以下术语

静态互连网络：各结点之间有固定的连接通路、且在运行中不能改变的网络。

动态互连网络：由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。

互连函数：用变量x表示输入，用函数f(x)表示输出。则f(x)表示：在互连函数f的作用下，输入端x连接到输出端f(x)。它反映了网络输入端数组和输出端数组之间对应的置换关系或排列关系，所以互连函数有时也称为置换函数或排列函数。

网络直径：指互连网络中任意两个结点之间距离的最大值。

7.3 设E为交换函数，S为均匀洗牌函数，B为蝶式函数，PM2I为移数函数，函数的自变量是十进制数表示的处理机编号。现有32台处理机，其编号为0，1，2，…，31。

（1）分别计算下列互连函数

E2（12） S（8） B（9） PM2I+3（28） E0（S（4）） S（E0（18））

（2）用E0和S构成均匀洗牌交换网（每步只能使用E0和S一次），网络直径是多少？从5号处理机发送数据到7号处理机，最短路径要经过几步？请列出经过的处理机编号。

（3）采用移数网络构成互连网，网络直径是多少？结点度是多少？与2号处理机距离最远的是几号处理机？

解：（1）共有32个处理机，表示处理机号的二进制地址应为5位。

E2（12）＝E2（01100）＝01000（8） S（8）＝S（01000）＝10000（16） B（9）＝B（01001）＝11000（24） PM2I+3（28）＝28＋23 mod32 ＝4 E0（S（4））＝E0（S（00100））＝01001（9） S（E0（18））＝S（E0（10010））＝S（10011）＝00111（7）

（2）2n个结点的均匀洗牌交换网的网络直径为2n-1，32个结点的均匀洗牌交换网的网络直径为9。

从5号处理机发送数据到7号处理机，最短路径要经过6步：

00101→00100→01000→01001→10010→10011→00111

（3）网络直径是3，结点度是9，与2号处理机距离最远的是13、15、21、23号处理机。

7.7用一个N=8的三级Omega网络连接8个处理机（P0~P7），8个处理机的输出端分别依序连接Omega网络的8个输入端0~7，8个处理机的输入端分别依序连接Omega网络的8个输出端0~7。如果处理机P6要把数据播送给处理机P0~P4，处理机P3要把数据播送给处理机P5~P7，那么，Omega网络能否同时为它们的播送要求实现连接？画出实现播送的Omega网络的开关状态图。

解：Omega网络使用的2×2开关有4种状态：直送、交叉、上播、下播。置换连接只使用直送和交叉状态，播送连接还需要使用上播和下播状态。分别画出实现处理机P6和P3的播送连接要求使用的开关状态，如果没有开关状态和开关输出端争用冲突，就可以使用播送连接。实际上，它们的播送要求没有冲突，因此，可以同时实现，同时实现的Omega网

第 15 页 共 17 页