计算机系统结构课后习题答案

MPP ：即大规模并行处理，按照当前的标准，具有几百台～几千台处理机的任何机器都是大规模并行处理系统。

8.2 一个具有32台处理机的系统，对远程存储器访问时间是2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本地处理机挂起。处理机的时钟周期时间是10ns，假设指令基本的CPI为1.0（设所有访存均命中Cache）。对于下述两种情况：

（1） 没有远程访问；

（2） 0.5%的指令需要远程访问。 试问前者比后者快多少？

解：已知远程访问率 p = 0.5%，远程访问时间 t = 2000ns，时钟周期 T = 10ns 远程访问开销 C = t/T = 2000ns/10ns = 200（时钟周期数） 有 0.5%远程访问的机器的实际 CPI2 为： CPI2 = CPI1 + p×C = 1.0 + 0.5%×200 = 2.0 只有局部访问的机器的基本 CPI1 = 1.0 CPI2/ CPI1 = 2.0/1.0 = 2（倍）

因此，没有远程访问状态下的机器速度是有0.5% 远程访问的机器速度的2 倍。

8.3 什么是多处理机的一致性？给出解决一致性的监听协议和目录协议的工作原理。

答：（1） 对多个处理器维护一致性的协议称为Cache一致性协议。

（2）目录协议的工作原理：采用一个集中的数据结构——目录。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。目录协议根据该项目中的信息以及当前要进行的访问操作，依次对相应的Cache发送控制消息，并完成对目录项信息的修改。此外，还要向请求处理器发送响应信息。

（3）监听协议的工作原理：每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。

8.4 在标准的栅栏同步中，设单个处理器的通过时间（包括更新计数和释放锁）为C，求N个处理器一起进行一次同步所需要的时间。

解：我们忽略读写锁的时间。N个处理器中的每一个都需要C个时钟周期来锁住与栅栏相关的计数器，修改它的值，然后释放锁。考虑最坏情况，所有N个处理器都要对计数器加锁并修改它的值，由于锁只能顺序访问计数器，在同一时间，只能有一个处理器修改计数器的数据。所以，总共要花NC个时钟周期使得所有的处理器都到达数据栅栏。

8.6 采用排队锁和fetch-and-increment重新实现栅栏同步，并将它们分别与采用旋转锁实现的栅栏同步进行性能比较。

解：fetch-and-increment(count)；

if (count=total){

count=0； release=1； }

//进程全部到达 //重置计数器 //释放进程

else{

spin(release=1)； }

//还有进程未到达 //等待信号

当有N个处理器时，上述代码执行fetch-and-increment操作N次，当访问释放操作的时候，有N个Cache未命中。当最后一个处理器到达栅栏条件后，release被置为“1”，此时有N-1个Cache未命中（对于最后一个到达栅栏的处理器，当它读release的时候，将在主存中命中）。所以，共有3N-1次总线传输操作。如果有10个处理器，则共有29次总线传输操作，总共需要2900个时钟周期。

8.7 有些机器实现了专门的锁广播一致性协议，实现上可能使用不同的总线。假设使用写广播协议，重新给出例8.3旋转锁的时间计算。

解：当实现了专门的锁广播一致性协议后，每当一把锁被释放的时候，和锁相关的值将被广播到所有处理器，这意味着在处理器对锁变量进行读操作的时候，未命中的情况永远不会发生。

假定每个Cache都有一个数据块保留锁变量的初值。通过下表可以知道，10次上锁/释放锁的平均时间是550个时钟周期，总时间是5500个时钟周期。 事件 所有处理器都读（命中）锁 释放锁的处理器进行写（不命中）广播 读（命中）锁（处理器认为锁是空闲的） 一个处理器进行写交换广播，同时还有9个写广播 一个处理器得到并释放锁的总时间 持续时间 0 100 0 1000 1100

第9章 机群

9.1 解释下列术语

机群：是一种价格低廉、易于构建、可扩放性极强的并行计算机系统。它由多台同构或异构的独立计算机通过高性能网络或局域网互连在一起，协同完成特定的并行计算任务。从用户的角度来看，机群就是一个单一、集中的计算资源。

单一系统映象：包含四重含义。（1）单一系统。尽管系统中有多个处理器，用户仍然把整个机群视为一个单一的计算系统来使用。（2）单一控制。逻辑上，最终用户或系统用户使用的服务都来自机群中唯一一个位置。（3）对称性。用户可以从任一个结点上获得机群服务，也就是说，对于所有结点和所有用户，除了那些具有特定访问权限的服务与功能外，所有机群服务与功能都是对称的。（4）位置透明。用户不必了解真正提供服务的物理设备的具体位置。

高可用性机群：当系统中某些结点出现故障的情况下，仍能继续对外提供服务。它采用冗余机制，当系统中某个结点由于软、硬件故障而失效时，该结点上的任务将在最短的时间内被迁移到机群内另一个具有相同功能与结构的结点上继续执行。

负载均衡机群：机群能够根据系统中各个结点的负载情况实时地进行任务分配。它专门

设置了一个重要的监控结点，负责监控其余每个工作结点的负载和状态，并根据监控结果将任务分派到不同的结点上。

高性能计算机群：通过高速的商用互连网络，将数十台乃至上千台PC机或工作站连接在一起，可以提供接近甚至超过传统并行计算机系统的计算能力，但其价格却仅是具有相同计算能力的传统并行计算机系统的几十分之一。

Beowulf机群：使用普通的硬件加上Linux操作系统、再加上GNU开发环境以及PVM/MPI共享库所构建的机群。它一方面集中了那些相对较小的机器的计算能力，能够以很高的性能价格比提供与大型机相当的性能，另一方面也保证了软件环境的稳定性。

9.2 机群系统有什么特点？

答：（1）系统开发周期短。由于机群系统大多采用商品化的PC机、工作站作为结点，并通过商用网络连接在一起，系统开发的重点在于通信子系统和并行编程环境上，这大大节省了研制时间。

（2）可靠性高。机群中的每个结点都是独立的PC机或工作站，某个结点的失效并不会影响其它结点的正常工作，而且它的任务还可以传递给其它结点完成，从而有效地避免由于单结点失效引起的系统可靠性降低的问题。

（3）可扩放性强。机群的计算能力随着结点数量的增加而增大。这主要是得益于机群结构的灵活性，由于结点之间以松耦合方式连接，机群的结点数量可以增加到成百上千。另外，机群系统的硬件容易扩充和替换，可以灵活配置。

（4）性能价格比高。由于生产批量小，传统并行计算机系统的价格均比较昂贵，往往要几百万到上千万美元。而机群的结点和网络都是商品化的计算机产品，能够大批量生产，成本相对较低，因而机群系统的性能价格比更好。与相同性能的传统并行计算机系统相比，机群的价格要低1～2个数量级。

（5） 用户编程方便。机群系统中，程序的并行化只是在原有的C、C++或Fortran串行程序中插入相应的通信原语，对原有串行程序的改动有限。用户仍然使用熟悉的编程环境，无需适用新的环境。

9.3 说明IBM SP2的体系结构特点。

答：SP2机群是异步的MIMD，具有分布式存储器系统结构。它的每个结点都是一台RS/6000工作站，带有自己的存储器和本地磁盘。结点中采用的处理器是一台6流出的超标量处理机，每个时钟周期可以执行6条指令。

SP2的结点数可以从2个到512个不等，每个结点配有一套完整的AIX操作系统（IBM的UNIX），结点间的互连网络接口是松散耦合的，通过结点本身的I/O微通道（MCC）接到网络上。

SP2的结点都有1个指令Cache，1个数据Cache，1个分支指令和转移控制部件，2个整数部件和2个浮点部件，但它们在存储器容量、数据宽度和I/O总线插槽个数上有所不同。

系统采用标准的工作站部件，仅在标准技术不能满足性能要求时才使用专用软件和硬件。

SP2的I/O系统基本上是围绕着HPS建立的，并可以用一个LAN网关同SP2系统外的其他计算机连接。

SP2中设置了一个专门的系统控制台用以管理整个系统，系统管理人员可以通过这个系统控制台从单一地点对整个系统进行管理。

第1章 计算机系统结构的基本概念

1.1 解释下列术语 层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。这些层次依次为：微程序机器级，传统机器语言机器级，汇编语言机器级，高级语言机器级，应用语言机器级等。

虚拟机：用软件实现的机器。

翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。

解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。

计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。

在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。

计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。

计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。

系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。

Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。

程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。包括时间局部性和空间局部性。

CPI：每条指令执行的平均时钟周期数。

测试程序套件：由各种不同的真实应用程序构成的一组测试程序，用来测试计算机在各个方面的处理性能。

存储程序计算机：冯·诺依曼结构计算机。其基本点是指令驱动。程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作。

系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。

软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。

向上（下）兼容：按某档计算机编制的程序，不加修改就能运行于比它高（低）档的计算机。

向后（前）兼容：按某个时期投入市场的某种型号计算机编制的程序，不加修改地就能运行于在它之后（前）投入市场的计算机。

兼容机：由不同公司厂家生产的具有相同系统结构的计算机。

模拟：用软件的方法在一台现有的计算机（称为宿主机）上实现另一台计算机（称为虚拟机）的指令系统。

仿真：用一台现有计算机（称为宿主机）上的微程序去解释实现另一台计算机（称为目标机）的指令系统。

并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠，就存在并行性。它包括同时性与并发性两种含义。

时间重叠：在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。

资源重复：在并行性概念中引入空间因素，以数量取胜。通过重复设置硬件资源，大幅度地提高计算机系统的性能。

资源共享：这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备。

耦合度：反映多机系统中各计算机之间物理连接的紧密程度和交互作用能力的强弱。

紧密耦合系统：又称直接耦合系统。在这种系统中，计算机之间的物理连接的频带较高，一般是通过总线或高速开关互连，可以共享主存。

松散耦合系统：又称间接耦合系统，一般是通过通道或通信线路实现计算机之间的互连，可以共享外存设备（磁盘、磁带等）。计算机之间的相互作用是在文件或数据集一级上进行。

异构型多处理机系统：由多个不同类型、至少担负不同功能的处理机组成，它们按照作业要求的顺序，利用时间重叠原理，依次对它们的多个任务进行加工，各自完成规定的功能动作。

同构型多处理机系统：由多个同类型或至少担负同等功能的处理机组成，它们同时处理同一作业中能并行执行的多个任务。

1.2 试用实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系。 答：如在设计主存系统时，确定主存容量、编址方式、寻址范围等属于计算机系统结构。确定主存周期、逻辑上是否采用并行主存、逻辑设计等属于计算机组成。选择存储芯片类型、微组装技术、线路设计等属于计算机实现。

计算机组成是计算机系统结构的逻辑实现。计算机实现是计算机组成的物理实现。一种体系结构可以有多种组成。一种组成可以有多种实现。

1.3 计算机系统结构的Flynn分类法是按什么来分类的？共分为哪几类？ 答：Flynn分类法是按照指令流和数据流的多倍性进行分类。把计算机系统的结构分为： （1） 单指令流单数据流SISD （2） 单指令流多数据流SIMD （3） 多指令流单数据流MISD （4） 多指令流多数据流MIMD

1.4 计算机系统设计中经常使用的4个定量原理是什么？并说出它们的含义。 答：（1）以经常性事件为重点。在计算机系统的设计中，对经常发生的情况，赋予它优先的处理权和资源使用权，以得到更多的总体上的改进。（2）Amdahl定律。加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中所占的重要性。（3）CPU性能公式。执行一个程序所需的CPU时间 = IC ×CPI ×时钟周期时间。（4）程序的局部性原理。程序在执行时所访问地址的分布不是随机的，而是相对地簇聚。

1.5 分别从执行程序的角度和处理数据的角度来看，计算机系统中并行性等级从低到高可分为哪几级？

答：从处理数据的角度来看，并行性等级从低到高可分为：

（1）字串位串：每次只对一个字的一位进行处理。这是最基本的串行处理方式，不存在并行性；

（2）字串位并：同时对一个字的全部位进行处理，不同字之间是串行的。已开始出现并行性；

（3）字并位串：同时对许多字的同一位（称为位片）进行处理。这种方式具有较高的并行性；

（4）全并行：同时对许多字的全部位或部分位进行处理。这是最高一级的并行。 从执行程序的角度来看，并行性等级从低到高可分为： （1）指令内部并行：单条指令中各微操作之间的并行； （2）指令级并行：并行执行两条或两条以上的指令；

（3）线程级并行：并行执行两个或两个以上的线程，通常是以一个进程内派生的多个线程为调度单位；

（4）任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段），以子程序或进程为调度单元；

（5）作业或程序级并行：并行执行两个或两个以上的作业或程序。

1.6 某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：

指令类型 整数 指令执行数量 45000 平均时钟周期数 1 数据传送 浮点 分支 75000 8000 1500 2 4 2 求该计算机的有效CPI、MIPS和程序执行时间。 解：（1）CPI ＝(45000×1＋75000×2＋8000×4＋1500×2) / 129500＝1.776 （2）MIPS速率＝f/ CPI ＝400/1.776 ＝225.225MIPS

（3）程序执行时间= (45000×1＋75000×2＋8000×4＋1500×2)／400=575s

1.7 将计算机系统中某一功能的处理速度加快10倍，但该功能的处理时间仅为整个系统运行时间的40%，则采用此增强功能方法后，能使整个系统的性能提高多少？

解 由题可知： 可改进比例 = 40% = 0.4 部件加速比 = 10 根据Amdahl定律可知：

1系统加速比??1.5625

0.4?1?0.4??10采用此增强功能方法后，能使整个系统的性能提高到原来的1.5625倍。

1.8 计算机系统中有三个部件可以改进，这三个部件的部件加速比为：

部件加速比1=30； 部件加速比2=20； 部件加速比3=10

（1） 如果部件1和部件2的可改进比例均为30%，那么当部件3的可改进比例为多少时，系统加速比才可以达到10？

（2） 如果三个部件的可改进比例分别为30%、30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？

解：（1）在多个部件可改进情况下，Amdahl定理的扩展：

Sn?1F(1??Fi)??iSi

已知S1＝30，S2＝20，S3＝10，Sn＝10，F1＝0.3，F2＝0.3，得：

10?1

1（-0.3?0.3?F3）?（0.3/30?0.3/20?F3/10）得F3＝0.36，即部件3的可改进比例为36%。

（2）设系统改进前的执行时间为T，则3个部件改进前的执行时间为：（0.3+0.3+0.2）T = 0.8T，不可改进部分的执行时间为0.2T。

已知3个部件改进后的加速比分别为S1＝30，S2＝20，S3＝10，因此3个部件改进后的执行时间为：

"Tn?0.3T0.3T0.2T???0.045T 302010 改进后整个系统的执行时间为：Tn = 0.045T+0.2T = 0.245T

那么系统中不可改进部分的执行时间在总执行时间中占的比例是：

0.2T?0.82

0.245T

1.9 假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示： 操作类型 程序中的数量 改进前的执行时间 改进后的执行时间 操作1 操作2 操作3 操作4 （百万条指令） 10 30 35 15 （周期） 2 20 10 4 （周期） 1 15 3 1 （1）改进后，各类操作的加速比分别是多少？

（2）各类操作单独改进后，程序获得的加速比分别是多少？ （3）4类操作均改进后，整个程序的加速比是多少？ 解：根据Amdahl定律Sn? 操作类型 操作1 操作2 操作3 操作4 各类操作的指令条数在程序中所占的比例Fi 11.1% 33.3% 38.9% 16.7% 各类操作的加速比Si 2 1.33 3.33 4 各类操作单独改进后，程序获得的加速比 1.06 1.09 1.37 1.14 1Fe(1?Fe)?Se可得

4类操作均改进后，整个程序的加速比：

1Sn??2.16

Fi(1??Fi)??Si

3.19 某向量处理机有16个向量寄存器，其中V0~V5中分别放有向量A、B、C、D、E、F，向量长度均为8，向量各元素均为浮点数；处理部件采用两条单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似于CARY-1的链接技术，先计算（A+B）*C，在流水线不停流的情况下，接着计算（D+E）*F。

（1） 求此链接流水线的通过时间？（设寄存器入、出各需1拍） （2） 假如每拍时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件的实

际吞吐率为多少MFLOPS？

解：（1）我们在这里假设A＋B的中间结果放在V6中，（A＋B）×C地最后结果放在V7中，D＋E地中间结果放在V8中，（D＋E）×F的最后结果放在V9中。具体实现参考下图：

V0AV1BV6V2CV7向量加向量乘V3DV4EV8V5FV9 通过时间应该为前者（（A＋B）×C）通过的时间：

T通过= (1+2+1)+(1+3+1) =9（拍）

（2）在做完（A＋B）×C之后，作（C＋D）×E就不需要通过时间了。 V6←A＋B

V7←V6×C V8←D＋E

V9←V8×F

T?T通过＋（8－1）?8?24（拍）?1200(ns)TP?32?26.67MFLOPST

7章 互连网络

7.1 解释以下术语 线路交换：在线路交换中，源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。

分组交换：把信息分割成许多组（又称为包），将它们分别送入互连网络。这些数据包可以通过不同的路径传送，到目的结点后再拼合出原来的数据，结点之间不存在固定连接的物理通路。

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

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

互连网络：一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。在拓扑上，互连网络是输入结点到输出结点之间的一组互连或映象。

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

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

结点度：指互连网络中结点所连接的边数（通道数）。

等分带宽：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。

对称网络：从任意结点来看，网络的结构都是相同的。

7.2 试比较可用于动态互连的总线、交叉开关和多级互连网络的硬件复杂度和带宽。 答：总线互连的复杂性最低，成本也是最低。其缺点是每台处理机可用的带宽较窄。 交叉开关是最昂贵的，因为其硬件复杂性以n2上升，所以其成本最高。但是交叉开关的带宽和寻径性能最好。当网络的规模较小时，它是一种理想的选择。

多级互连网络的复杂度和带宽介于总线和交叉开关之间，是一种折中方案。其主要优点是采用模块化结构，可扩展性较好。不过，其时延随网络级数的增加而上升。另外，由于其硬件复杂度比总线高很多，其成本也不低。

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=2n 个输入端的Omega网络，采用单元控制。 （1）N个输入总共应有多少种不同的排列？

（2）该Omega网络通过一次可以实现的置换总共可有多少种是不同的？ （3）若N=8，计算一次通过能实现的置换数占全部排列的百分比。

解：（1）N个输入的不同排列数为N！。

（2）N个输入端、输出端的Omega网络有n＝log2N级开关级，每级开关级有N/2个2×2的4功能开关，总共有（N/2）log2N个开关。置换连接是指网络的输入端与输出端的一对一连接，故只考虑2×2开关的2个功能状态，即直送与交叉。网络采用单元控制，因此，每个开关都根据连接要求处于2个功能状态中的一种状态，所以，由（N/2）log2N个开关组成的Omega网络的开关状态的种树为：

（N/2）log2N2?NN/2

一种网络开关状态实现Omega网络的一种无冲突的置换连接，所以，一次使用Omega网络可以实现的无冲突的置换连接有NN/2种。

（3）若N=8，则一次通过能实现的置换数占全部排列的百分比为：

NN/2844096???10.16% N!8!40320

7.8 用一个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网络开关状态图如下所示。

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

7.9试证明多级Omega网络采用不同大小构造块构造时所具有的下列特性：

（1） 一个k×k开关模块的合法状态（连接）数目等于kk。

（2） 试计算用2×2开关模块构造的64个输入端的Omega网络一次通过所能实现置

换的百分比。

（3） 采用8×8开关模块构造64个输入端的Omega网络，重复（2）。

（4） 采用8×8开关模块构造512个输入端的Omega网络，重复（2）。 解：（1）一个k×k开关的合法状态或合法连接有：① 一个输入端连接一个输出端，即一对一的置换连接；② 一个输入端连接多个或全部输出端，即一对多的选播连接或一对全体的广播连接。

两个或两个以上的输入端连接一个输出端是非法连接。因此，某个输出端可被连接到任意一个输入端的连接有k种，无论这个输出端是被置换连接还是被播送连接。

k个输出端被连接到输入端的合法连接的数量为：

k×k×?×k＝kk k个 （2）用k×k开关模块构造N个输入端的Omega网络时，开关级数为n＝logkN，每级

开关模块数为N/k，网络的开关模块总数为（N/k）logkN。

一个k×k开关一对一连接的合法状态只有k种，所有开关都是一对一连接的合法状态才能实现一种一次使用网络的无冲突置换连接。因此，由（N/k）logkN个k×k开关组成的Omega网络一次使用的无冲突置换连接函数为：

kNlogkNkN?(klogkN)k?NNk

网络可以实现的置换连接数即为N个输出端的不同排序的排序数，即为N！，所以，Omega网使用一次实现的无冲突置换连接数占可以实现的置换连接数的比例为：

NNk/N!

若采用2×2开关模块构造的64个输入端的Omega网络，即有k=2，N=64，则Omega网使用一次实现置换连接的比例为：

6432?4.95?10-32 64！（3）若采用8×8开关模块构造64个输入端的Omega网络，即有k=8，N=64，则Omega

网使用一次实现置换连接的比例为：

648?3.85?10-16 64！（4）若采用8×8开关模块构造512个输入端的Omega网络，即有k=8，N=512，则

Omega网使用一次实现置换连接的比例为：

51264/512！

第8章 多处理机

8.1 解释以下术语

集中式共享多处理机：也称为对称式共享存储器多处理SMP。它一般由几十个处理器构成，各处理器共享一个集中式的物理存储器，这个主存相对于各处理器的关系是对称的，

分布式共享多处理机：它的共享存储器分布在各台处理机中，每台处理机都带有自己的本地存储器，组成一个“处理机-存储器”单元。但是这些分布在各台处理机中的实际存储器又合在一起统一编址， 在逻辑上组成一个共享存储器。这些处理机存储器单元通过互连网络连接在一起 ，每台处理机除了能访问本地存储器外，还能通过互连网络直接访问在其他处理机存储器单元中的 “远程存储器”。

通信延迟：通信延迟＝发送开销＋跨越时间＋传输时间＋接收开销。

计算/通信比：反映并行程序性能的一个重要的度量。在并行计算中，每次数据通信要进行的计算与通信开销的比值。

多Cache一致性：多处理机中，当共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储器块的副本，要保证多个副本数据是一致的。

监听协议：每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。

目录协议：用一种专用的存储器所记录的数据结构。它记录着可以进入Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。

写作废协议：在处理器对某个数据项进行写入之前，它拥有对该数据项的唯一的访问权。

写更新协议：当一个处理器对某数据项进行写入时，它把该新数据广播给所有其它Cache。这些Cache用该新数据对其中的副本进行更新。

栅栏同步：栅栏强制所有到达该栅栏的进程进行等待。直到全部的进程到达栅栏，然后释放全部进程，从而形成同步。

旋转锁：处理机环绕一个锁不停地旋转而请求获得该锁。

同时多线程：是一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技术，它是多线程技术的一种改进。

细粒度多线程技术：是一种实现多线程的技术。它在每条指令之间都能进行线程的切换，从而使得多个线程可以交替执行。通常以时间片轮转的方法实现这样的交替执行，在轮转的过程中跳过处于停顿的线程。

粗粒度多线程技术：是一种实现多线程的技术。只有线程发生较长时间的停顿时才切换到其他线程。

SMP：对称式共享存储器多处理

以把功能部件链接起来进行流水处理，以达到加快执行的目的。

分段开采：当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。

半性能向量长度：向量处理机的性能为其最大性能R?的一半时所需的向量长度。

向量长度临界值：向量流水方式的处理速度优于标量串行方式的处理速度时所需的向量长度的最小值。

3.2 指令的执行可采用顺序执行、重叠执行和流水线三种方式，它们的主要区别是什么？各有何优缺点。

答：（1）指令的顺序执行是指指令与指令之间顺序串行。即上一条指令全部执行完后，才能开始执行下一条指令。

优点：控制简单，节省设备。缺点：执行指令的速度慢，功能部件的利用率低。

（2）指令的重叠指令是在相邻的指令之间，让第k条指令与取第k+l条指令同时进行。重叠执行不能加快单条指令的执行速度，但在硬件增加不多的情况下，可以加快相邻两条指令以及整段程序的执行速度。与顺序方式相比，功能部件的利用率提高了，控制变复杂了。

（3）指令的流水执行是把一个指令的执行过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，每个子过程与其它的子过程并行进行。依靠提高吞吐率来提高系统性能。流水线中各段的时间应尽可能相等

3.3 简述先行控制的基本思想。 答：先行控制技术是把缓冲技术和预处理技术相结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲器，用以平滑它们的工作。预处理技术是指预取指令、对指令进行加工以及预取操作数等。

采用先行控制方式的处理机内部设置多个缓冲站，用于平滑主存、指令分析部件、运算器三者之间的工作。这样不仅使它们都能独立地工作，充分忙碌而不用相互等待，而且使指令分析部件和运算器分别能快速地取得指令和操作数，大幅度地提高指令的执行速度和部件的效率。这些缓冲站都按先进先出的方式工作，而且都是由一组若干个能快速访问的存储单元和相关的控制逻辑组成。

采用先行控制技术可以实现多条指令的重叠解释执行。

3.4 设一条指令的执行过程分成取指令、分析指令和执行指令三个阶段，每个阶段所需的时间分别为△t、△t和2△t 。分别求出下列各种情况下，连续执行N条指令所需的时间。

（1）顺序执行方式；

（2）只有“取指令”与“执行指令”重叠； （3）“取指令”、“分析指令”与“执行指令”重叠。 解：（1）每条指令的执行时间为：△t＋△t＋2△t＝4△t

连续执行N条指令所需的时间为：4N△t

（2）连续执行N条指令所需的时间为：4△t＋3（N-1）△t＝（3N＋1）△t （3）连续执行N条指令所需的时间为：4△t＋2（N-1）△t＝（2N＋2）△t

3.5 简述流水线技术的特点。 答：流水技术有以下特点： （1） 流水线把一个处理过程分解为若干个子过程，每个子过程由一个专门的功能部件来实现。因此，流水线实际上是把一个大的处理功能部件分解为多个独立的功能部件，并依靠它们的并行工作来提高吞吐率。

（2） 流水线中各段的时间应尽可能相等，否则将引起流水线堵塞和断流。 （3） 流水线每一个功能部件的前面都要有一个缓冲寄存器，称为流水寄存器。

（4） 流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。

（5） 流水线需要有通过时间和排空时间。在这两个时间段中，流水线都不是满负荷工作。

3.6 解决流水线瓶颈问题有哪两种常用方法？ 答：细分瓶颈段与重复设置瓶颈段

3.7 减少流水线分支延迟的静态方法有哪些？ 答：（1）预测分支失败：沿失败的分支继续处理指令，就好象什么都没发生似的。当确定分支是失败时，说明预测正确，流水线正常流动；当确定分支是成功时，流水线就把在分支指令之后取出的指令转化为空操作，并按分支目标地址重新取指令执行。

（2）预测分支成功：当流水线ID段检测到分支指令后，一旦计算出了分支目标地址，就开始从该目标地址取指令执行。

（3）延迟分支：主要思想是从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成。不管分支是否成功，都要按顺序执行延迟槽中的指令。

3种方法的共同特点：它们对分支的处理方法在程序的执行过程中始终是不变的。它们要么总是预测分支成功，要么总是预测分支失败。

3.8 简述延迟分支方法中的三种调度策略的优缺点。 调度策略 从前调度 从目标处调度 对调度的要求 分支必须不依赖于被调度的指令 对流水线性能改善的影响 总是可以有效提高流水线性能 如果分支转移失败，必须保证被调度的指令对程分支转移成功时，可以提高流水线性能。序的执行没有影响，可能需要复制被调度指令 但由于复制指令，可能加大程序空间 如果分支转移成功，必须保证被调度的指令对程分支转移失败时，可以提高流水线性能 序的执行没有影响 从失败处调度

3.9列举出下面循环中的所有相关，包括输出相关、反相关、真相关。

for (i=2; i<100; i=i+1) a[i]=b[i]+a[i] ;/* s1 */ c[i+1]=a[i]+d[i] ; /* s2 */ a[i-1]=2*b[i] ; /* s3 */ b[i+1]=2*b[i]

解：展开循环两次：

a[i] = b[i] + a[i]

;/* s4 */ ; /* s1 */

c[i+1] = a[i] + d[i] a[i-1] = 2 * b[i] b[i+1] = 2 * b[i]

a[i+1] = b[i+1] + a[i+1] c[i+2] = a[i+1] + d[i+1] a[i] = 2 * b[i+1] b[i+2] = 2 * b[i+1] ; /* s2 */ ; /* s3 */ ; /* s4 */ ; /* s1? */ ; /* s2 ?*/ ; /* s3 ?*/ ; /* s4 ?*/

输出相关：无 反相关：无 真相关：S1&S2

由于循环引入的相关：S4&S4’（真相关）、S1’&S4（真相关）、S3’&S4（真相关）、S1&S3’（输出相关、反相关）、S2&S3’（反相关）。

3.10 简述三种向量处理方式，它们对向量处理机的结构要求有何不同？

答 (1)横向处理方式：若向量长度为N，则水平处理方式相当于执行N次循环。若使用流水线，在每次循环中可能出现数据相关和功能转换，不适合对向量进行流水处理。 (2)纵向处理方式：将整个向量按相同的运算处理完毕之后，再去执行其他运算。适合对向量进行流水处理，向量运算指令的源/目向量都放在存储器内，使得流水线运算部件的输入、输出端直接与存储器相联，构成M-M型的运算流水线。 (3)纵横处理方式：把长度为N的向量分为若干组，每组长度为n，组内按纵向方式处理，依次处理各组，组数为「N/n」，适合流水处理。可设长度为n的向量寄存器，使每组向量运算的源/目向量都在向量寄存器中，流水线的运算部件输入、输出端与向量寄存器相联，构成R-R型运算流水线。

3.11 可采用哪些方法来提高向量处理机的性能？ 答：可采用多种方法：

（1） 设置多个功能部件，使它们并行工作； （2） 采用链接技术，加快一串向量指令的执行； （3） 采用循环开采技术，加快循环的处理； （4） 采用多处理机系统，进一步提高性能。

3.12 有一指令流水线如下所示

入 1 2 3 4 出 50ns 50ns 100ns 200ns

（1） 求连续输入10条指令，该流水线的实际吞吐率和效率； （2） 该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给

出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？

解：（1）

Tpipeline???ti?(n?1)?tmaxi?1m?(50?50?100?200)?9?200 ?2200(ns)TP?nTpipeline?1(ns?1) 2204005??45.45% 411E?TP???ti?1mim?TP?（2）瓶颈在3、4段。

? 变成八级流水线（细分）

è?

150ns250ns3_150ns3_250ns4_150ns4_450ns3?4-1 3-1 1 2 3-2 4-3 4-4 4-2 Tpipeline???ti?(n?1)?tmaxi?1m?50?8?9?50?850(ns)TP?nTpipelinem

?185(ns?1)

E?TP???tii?1m?TP?40010??58.82% 817? 重复设置部件

TP?nTpipeline?185(ns?1)

E?400?10

850?8?10?58.82%

17段 4_4 4_3 4_2 4_1 3_2 3_1 2 211432 768 109 8 57 6 3 4 1 109 5 时间 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 850ns 3.13有一个流水线由4段组成，其中每当流经第3段时，总要在该段循环一次，然后才能流到第4段。如果每段经过一次所需要的时间都是?t，问：

（1） 当在流水线的输入端连续地每?t时间输入任务时，该流水线会发生什么情况？ （2） 此流水线的最大吞吐率为多少？如果每2?t输入一个任务，连续处理10个任务

时的实际吞吐率和效率是多少？ （3） 当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务时，其

吞吐率提高多少？

解：（1）会发生流水线阻塞情况。 第1个任务 第2个任务 第3个任务 第4个任务 S1 S2 S1 S3 S2 S1 S3 stall stall S4 S3 S2 S1 S3 stall stall S4 S3 S2 S3 stall S4 S3 S3 S4

（2）

段 4 2 6 7 3 4 5 8 9 10 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 2 5 1 2 3 4 6 7 8 9 10 时间 1 1 2 3 4 5 6 7 8 9 10 23 ? t 1

12?tTpipeline?23?tTPmax?Tp?nTpipeline?1023?t

?E?TP?5?t?50?54.35I2

（3）重复设置部件

Δt 3_1 1 2 4 3_2 Δt Δt Δt Δt

段 4 3_2 3_1 2 1 111 24 34 46 56 68 78 8 9 10 1 1 2 3 245 3 56 5 67 5 78 7 89 7 9 9 1010 9 10 23 34 时间 21014 ?t

TP?nTpipeline?10?5

14??t7??t57?t23?t吞吐率提高倍数＝

10＝1.64

3.14 有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或 4?) ，画出其时空图，并计暂存于相应的流水寄存器中。现要在该流水线上计算 ( A B i i

i?1算其吞吐率、加速比和效率。

? 1 △t 加法 2△t △t △t 2 △t 3 乘法 4 5

解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1＋B1、A2＋B2、

A3＋B3和A4＋B4；再计算(A1＋B1) ×(A2＋B2)和(A3＋B3) ×(A4＋B4)；然后求总的结果。

其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。

段 5 4 3 2 1 A B C D A×B C×D A×B×C×D A=A1＋B1 B=A2＋B2 C=A3＋B3 D=A4＋B4 输0 1 2 3 入4 5 6 7 8 9 A1 A2 A3 A4 B1 B2 B3 B4 10 11 12 13 14 15 16 17 18 A×B A C B D C×D 时间

由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：

7 TP?

18?t如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t =29△t。所以加速比为：

2 9 ? t

S?18?t?1.61该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得： 4 ? 5 ? 3 ? 3E?

5?18?0.322

3.15 动态多功能流水线由6个功能段组成，如下图：

S1 S2 S3 加法 S4 乘法 S5 S6

其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算：

?xyzii?15ii

（1） 画出时空图； （2） 计算实际的吞吐率、加速比和效率。 解：机器一共要做10次乘法，4次加法。

3.16 在MIPS流水线上运行如下代码序列：

LOOP： LW R1，0（R2） DADDIU R1，R1，#1 SW R1， 0（R2） DADDIU R2，R2，#4 DSUB R4，R3，R2 BNEZ R4，LOOP

其中：R3的初值是R2+396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器文件“定向”。问：

（1） 在没有任何其它定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线

时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？ （2） 假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设

采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？ （3） 假设该流水线有正常的定向路径和一个单周期延迟分支，请对该循环中的指令进

行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。

解：

寄存器读写可以定向，无其他旁路硬件支持。排空流水线。

指令LW DADDIUSWDADDIUDSUBBNEZLW 1IF345678910111213141516171819202122IDEXMWBIFSSIDEXMWBIFSSIDEXMWBIFIDEXMWBIFSSIDEXMWBIFSSIDEXMWBIFSSIFIDEXMWB2

第i次迭代（i＝0..98）开始周期：1＋（i×17） 总的时钟周期数：（98×17）＋18＝1684

有正常定向路径，预测分支失败。

指令LWDADDIUSWDADDIUDSUBBNEZLW1IFIDIF23456EXMWBIDSEXMIFSIDEXIFIDIF7WBMEXIDIF8910111131415WBMEXIDIFWBMWBEXMWBmissmissIFIDEXMWB

第i次迭代（i＝0..98）开始周期：1＋（i×10） 总的时钟周期数：（98×10）＋11＝991

有正常定向路径。单周期延迟分支。

LOOP: LW R1，0(R2)

DADDIU R2，R2，#4 DADDIU R1，R1，#1 DSUB R4，R3，R2 BNEZ R4，LOOP SW R1，-4(R2)

第i次迭代（i ＝0..98）开始周期：1＋（i ×6 ） 总的时钟周期数：（98×6）＋10＝598

指令LW DADDIUDADDIUDSUBBNEZSWLW 1IFIDIF234EXMIDEXIFIDIF5WBMEXIDIF6WBMEXIDIF7891011WBMEXIDIFWBMWBEXMWBIDEXMWB

3.17 假设各种分支指令数占所有指令数的百分比如下：

条件分支 跳转和调用 20%（其中的60%是分支成功的） 5% 现有一条段数为4的流水线，无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第三个时钟周期结束时才能够被解析出来。第一个流水段是完全独立于指令类型的，即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是多少？

解：没有控制相关时流水线的平均CPI＝1 存在控制相关时：由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支 要到第3个时钟周期结束时才能被解析出来。所以：

（1）若使用排空流水线的策略，则对于条件分支，有两个额外的stall，对无条件分支，有一个额外的stall：

CPI = 1+20%*2+5%*1 = 1.45 加速比S=CPI/1 = 1.45

（2） 若使用预测分支成功策略，则对于不成功的条件分支，有两个额外的stall，对无条件分支和成功的条件分支，有一个额外的stall 1：

CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比S=CPI/1 = 1.33

（3）若使用预测分支失败策略，则对于成功的条件分支，有两个额外的stall；对无条件分支，有一个额外的stall；对不成功的条件分支，其目标地址已经由PC 值给出，不必等待，所以无延迟：

CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比S=CPI/1 = 1.29

3.18 在CRAY-1机器上，按照链接方式执行下述4条向量指令（括号中给出了相应功能部件的执行时间），如果向量寄存器和功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果？ V0←存储器 （从存储器中取数：7拍） V2←V0+V1 （向量加：3拍）

V3←V2

解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。

访存存储器V0V1V2V3V4V5向量加左移向量逻辑乘A3

T通过＝（7＋1）＋（1＋3＋1）＋（1＋4＋1）＋（1＋2＋1）＝23（拍）T总共?T通过＋（64－1）＝23＋63＝86（拍）

计算机系统结构课后习题答案