目录

第一章 概论

第二章 数据表示、寻址方式与指令系统

第三章 存储、中断、总线与I/O系统

第四章 存储体系

第五章 标量处理机

第六章 向量处理机

第七章 多处理机

第八章 数据流计算机和规约机

---

第一章 概论

• 从使用语言的角度，一台由软、硬件组成的通用计算机系统可以被看成是按功能划分的多层机器级组成的层次结构。

• 层次结构由高到低依次为应用语言机器级、高级语言机器级、汇编语言机器级、操作系统机器级、传统机器语言机器级和微程序机器级。

• 从计算机的层次结构角度来看，系统结构是对计算机系统中各级界面的定义及其上下功能的分配。

• 计算机系统结构也称计算机系统的体系结构，它只是系统结构中的一部分，指的是传统机器语言机器级的系统结构。其界面之上包括操作系统级、汇编语言级、高级语言级和应用语言级中所有软件的功能，该界面之下包括所有硬件和固件的功能。

• 计算机组成是计算机系统结构的逻辑实现，计算机实现是计算机组成的物理实现。

2、计算机系统软、硬件取舍的基本原则

• 原则1：应考虑在现有硬、器件条件下，系统的性价比，主要从实现费用，速度和其他性能要求来综合考虑。

• 原则2：要考虑到准备采用和可能采用的组成技术，使之尽可能不要过多或不合理地限制各种组成、实现技术的采用。

• 原则3：不能仅从“硬”的角度考虑如何便于应用组成技术的成果和便于发挥器件技术的进展，还应从“软”的角度把如何为编译和操作系统的实现以及为高级语言程序的设计提供更多、更好的硬件支持放在首位

• 实现软件移植的技术主要有如下几种：1.统一高级语言 2.采用系列机 3.模拟和仿真

【简答题】实现软件移植的技术途径及其适用环境。

• 【参考答案】：（1）统一高级语言；适用于结构完全相同以至完全不同的机器之间的高级语言程序应用软件的移植。（2）采用系列机；适用于结构相同或相近的机器之间的汇编语言应用软件和部分系统软件的移植。（3）模拟与仿真；适用于结构不同的机器之间的机器语言程序的移植

• 仿真是用微程序解释，其解释程序存储于控制存储器中；而模拟是用机器语言程序解释，其解释程序存储于主存中。

• 非用户片也称为通用片，其功能是由器件厂家生产时固定的，器件的用户只能使用，不能改变器件内部功能。

• 并行性是贯穿于计算机信息加工的各个参骤和阶段的、从这个角度来看，并行性等级（由低-高）又分为：①存储器操作并行 ②处理器操作步骤并行 ③处理器操作并行④指令、任务、作业并行

• 简答：并行性的不同等级以不同角度，并行性有不同的等级。1）计算机系统执行程序的角度来看，并行性等级由低到高可分为四级。

• 分别是：①指令内部－一条指令内部各个微操作之间的并行执行。②指令之间－多条指令的并行执行。③任务或进程之间－多个任务或程序段的并行执行。④作业或程序之间－多个作业或多道程序的并行执行。

• 单选：并行性的不同等级从计算机系统中处理数据的角度来看、并行性等级从低到高可以分为四级。

• 分别是：①位串字串－同时只对一个字的一位进行处理，这通常是指传统的串行单处理机，没有并行性。②位并字串－同时对一个字的全部位进行处理，这通常是指传统的并行单处理机，开始出现并行性。③位片串字并－同时对许多字的同一位（称位片）进行处理、开始进入并行处理领域。④全并行－同时对许多字的全部或部分位组进行处理。

• 并行性开发的途径（1）并行性开发的途径有：时间重叠、资源重复、资源共享。

• ①时间重叠是在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，加快硬件周转来赢得速度。②资源重复是在并行概念中引入空间因素，资源来提高可靠性或性能。双工系统是通过使用两台相同的计算机完成同一任务来提高可靠性的。③资源共享是用软件方法，让多个用户按一定时间顺序轮流使用同一套资源来提高资源利用率，相应地也就提高了系统的性能。

• 填空：一般用耦合度反映多机系统中各机器之间物理连接的紧密度和交叉作用能力的强弱，有最低耦合、松散耦合和紧密耦合之分。

• 弗林提出按指令流和数据流的多倍性对计算机系统分类。

---

第二章 数据表示、寻址方式与指令系统

• 数据表示指的是能由计算机硬件识别和引用的数据类型，表现在它有对这种类型的数据进行操作的指令和运算部件。

• 数据结构是要通过软件映像，变换成计算机中所具有的数据表示来实现的。不同的数据表示可为数据结构的实现提供不同的支持，表现为实现效率和方便性的不同。数据结构和数据表示是软、硬件的交界面。

• 填空：高级数据表示的形式如下：①自定义数据表示；②向量、数组数据表示；③堆栈数据表示据表示；

• 解答：标志符数据表示的主要优点是：1）简化了指令系统和程序设计。2）简化了编译程序。3）便于实现一致性校验。4）能由硬件自动变换数据类型。5）支持数据库系统的实现与数据类型无关的要求，使程序不用修改即可处理多种不同类型的数据。6）为软件调试和应用软件开发提供了支持。

• 浮点数尾数的下溢处理方法（1）截断法；（2）舍入法；（3）恒置“1”法；（4）查表舍入法；

【简单应用题】设某计算机阶值p=4位、尾数m=15位，阶符和数符不在其内，当尾数以rm=8为基时，在非负阶、正尾数、规格化情况下，试计算：（1）最小阶值；（2）最大阶值；（3）阶的个数；（4）最小尾数值；（5）最大尾数值；（6）可表示的最小值；（7）可表示的最大值；（8）可表示数的个数。

【参考答案】：解：

• 填空：寻址方式的三种面向多数计算机都将主存、寄存器、堆栈分类编址，分别有面向主存、面向寄存器和面向堆栈的寻址方式。面向主存的寻址主要访问主存，少量访问寄存器。面向寄存器的寻址主要访问寄存器，少量访问主存和堆栈。面向堆栈的寻址主要访问堆栈，少量访问主存或寄存器。

• 程序在主存中的定位技术（1）静态再定位（2）动态再定位（3）虚实地址映像表

• 【填空题】静态再定位就是在目的程序装入主存、逻辑地址时，由装入程序用软件方法把目的程序的变换成物理地址，执行程序时，物理地址不再改变。

• 简答：指令系统的设计包括指令功能和指令格式的设计，在设计新的指令系统时，一般要按以下步骤反复多次地进行，直至指令系统的效率到很高为止。这些步骤依次为：

• 1）根据应用，初拟出指令的分类和具体的指令。2）试编出用该指令系统设计的各种高级语言的编译程序。3）对各种算法编写大量的测试程序并进行模拟测试，看指令系统的操作码和寻式效能是否都比较高。4）将程序中高频出现的指令串复合改成一条强功能新指令，即改用硬件方式实现。

简答：编译程序设计者要求指令系统应设计具有；

1）规整性。对相似的操作做相同的规定。2）对称性。对称性操作的定义相同，便于编译。3）独立性和全能性。有多种程序选择实现同一种功能，应限定只能有一种选择方式。4）正交性。指令中各个不同含义的字段，如操作类型、数据类编码时应互不相关，相互独立。5）可组合性。让指令系统中所有操作对各种寻址方式和数据类型都能适用。6）可扩充性。要留有一定数量的冗余操作码，以便以后扩充指令。

• 简答：哈夫曼压缩概念的基本思想是：当各种事件发生的概率不均等时，对发生概率最高的事件用最短的位数来表示，而对出现概率较低的事件允许用较长的位数来表示，就会使表示的平均位数缩短。

• 指令系统的设计包括指令功能和指令格式的设计。

• 简答：CISC存在如下问题：（1）指令系统庞大，一般指令在200条以上，许多指令的功能异常复杂，需要有多种寻址方式、指令格式和指令长度。（2）许多指令的操作繁杂、执行速度很低、甚至不如用几条简单、基本的指令组合实现。（3）由于指令系统庞大、使高级语言编详程序选择目标指令的范围太大，因此，难以优化生成高效机器语言程序、编译程序段太长、太复杂。（4）由于指令系统庞大、各种指令的使用额度都不会太高、且差别很大，其中相当一部分指令的利用率很低。

• 简答：采用RISC技术的好处主要有以下几个方面：（1）降低设计成本、提高系统的可靠性。（2）可直接支持高级语言的实现，简化编译程序的设计，指令总数的减少、缩小了编译过程中对功能类似的机器指令进行选择的范围，减轻了对各种寻址方式的选择、分析和变换的负担，不用进行指令格式的变换，易于更换或取消指令。

简答：设计RISC应遵循的一般原则包括：（1）确定指令系统时，只选择使用频度很高的那些指令，再增加少量能有效支持操作系统、高级语言实现及其他功能的指令，大大减少指令系统，一般使之不超过100条。（2）减少指令系统所用寻址方式种类，一般不超过两种。简化指令的格式限制在两种之内，并让全部指令都是相同长度。（3）让所有指令都在一个机器周期内完成。（4）扩大通用寄存器数，一般不少于32个，尽量减少访存，所有指令只有存、取指令访存，其他指令一律只对寄存器操作。（5）为提高指令执行速度，大多数指令都用硬件控制实现，少数指令才用微程序实现。（6）通过精简指令和优化设计编译程序，简单、有效地支持高级语言的实现。

---

第三章 存储、中断、总线与I/O系统

• 对存储系统的基本要求是大容量、高速度和低价格。

• 选择：存储器容量SM=W*l*m。其中，W为存储体的字长（单位是位或字节）；l为存储体的字数；m为并行工作的存储体数。

• 单体的Bm=W/TM，m个存储体并行的最大频宽Bm=W*m/TM。

• 填空：能并行读出多个CPU字的单体多字和多体单字、多体多字的交叉访问主存系统被称为并行主存系统。

• 解答：1、CPU中止正在执行的程序，转去处理随机提出的请求，待处理完后，再回到原先被打断的程序继续恢复执行的过程称为中断。

2、响应和处理各种中断的软、硬件总体称为中断系统。3、在计算机中，中断可分为内部中断、外部中断和软件中断三类。

①内部中断由CPU内的异常引起。②外部中断由中断信号引起；软件中断由自陷指令引起，用于供操作系统服务。③外部中断又分为可屏蔽中断和不可屏蔽中断。

• 中断的分类、分级、响应：

• 1、引起中断的各种事件称为中断源。2、中断源向中断系统发出请求中断的申请，称为中断请求。同时可能有多个中断请求，中断系统需按事先确定的中断响应优先次序，对优先级高的中断请求予以响应。3、程序性中断是包括指令和数据的格式错、程序执行中出现异常以及程序的事件记录、监督程序对事件的检测引起的中断等。4、外部中断来自计算机外部，它包括各种定时器中断、外部信号中断及中断键中断。各种定时器中断用以计时、计费、控制等；外部信号中断主要用于与其他计算机和系统的联系；中断键则用于操作员对计算机的干预。这些外部中断又可分为两类：一类是若未被响应，则继续保留；另一类是如不响应，则不再保留。5、中断的响应次序是在同时发生多个不同中断类的中断请求时，中断响应硬件中排队器所决定的响应次序（中断响应的次序用排队器硬件实现，次序是由高到低固定的）。

• 简答：中断系统的功能包括中断请求的保存和清除、优先级的确定、中断断点及现场的保存、对中断请求的分析和处理以及中断返回等。中断系统主要是要有高的中断响应速度，即从发出中断请求到进入中断处理程序的中断响应时间要短；其次是中断处理的灵活性。因此，中断系统的软、硬件功能分配实质上是中断处理程序软件和中断响应硬件的功能分配。

• 简答：总线的相关概念。总线是用于互连计算机、CPU、存储器、I/O接口及外围设备、远程通信设备间信息传送通路的集合。总线与其相配合的附属控制电路统称为总线系统。按信息传送功能、性能的不同，有数据线，地址线，命令，时序和中断信号等控制／状态线，电源线，地线及备用线等。

1. 总线按在系统中的位置分芯片级、板级和系统级等3级。
2. 就总线允许信息传送的方向来说，可以有单向传输和双向传输两种
3. 总线按用法可分为专用和非专用两类。
4. 总线标准一般包括机械、功能、电气及过程4个方面的标准
5. 总线的通信技术信息在总线上的传送方法基本上可分为同步和异步两种。

1.同步通信部件间的信息传送由定宽、定距的系统时钟同步。信息的传送速率高，受总线长度的影响小，时钟在总线上的时滞可能会造成同步误差，时钟线上的干扰信号易引起误同步。

2.异步通信由于I/O总线一般是为有不同速度的许多I/O设备所共享，因此宜于采用异步通信。异步通信又分单向源控制和请求／回答双向控制两种。

• 数据通路宽度是数据总线的物理宽度，即一个时钟周期所传送的信息量。

• 数据宽度有单字、定长块、可变长块、单字加定长块和单字加可变长块等之分。

• 总线的控制方式分集中式控制、分布式控制，其中集中式控制主要有串行链接、定时查询和独立请求3种不同的方式。

• 填空选择：I/O系统相关概念①I/O（输入／输出）系统包括输入／输出设备、设备控制器及与输入／输出操作有关的软、硬件。②输入／输出系统的发展经历了3个阶段，相对应于3种方式，即程序控制I/O（包括全软件的、程序查询的、中断驱动的）、直接存储器访问及I/O处理机方式。③对于I/O处理机方式，又有通道方式和外围处理机方式之分。④输入／输出设备分外存和传输设备两大类。外存有磁盘、磁带、光盘等。传输设备有键盘、鼠标。

• 通道处理机的工作原理和流量设计。根据通道数据传送期中信息传送方式的不同，可分为字节多路、数组多路和选择3类通道。①字节多路通道适用于连接大量的像光电机等字符类低速设备。它们传送一个字符（字节）的时间很短，但字符（字节）间的等待时间很长。因此，通道数据宽度为单字节，以字节交叉方式轮流为多台低速设备服务，使效率提高。②数组多路通道适合于连接多台磁盘等高速设备。这些设备的传送速率很高，但传送开始前的寻址辅助操作时间很长。③选择通道适合于连接优先级高的磁盘等高速设备，让它独占通道，只能执行一道通道程序。数据传送以不定长块方式进行，相当于数据宽度为可变长块，一次对N个字节全部传送完。所以，在数据传送期内只选择一次设备。

• 应用计算：通道处理机的工作原理和流量设计

• 通道流量是通道在数据传送期内，单位时间内传送的字节数。它能达到的最大流量称通道极限流量。通道的极限流量与其工作方式、数据传送期内选择一次设备的时间TS、和传送一个字节的时间TD的长短有关。字节多路通道每选择一台设备只传送一个字节，其通道极限流量：fmax.byte=1/（Ts+TD）

• 数组多路通道 每选择一台设备可传送完K个字节。如果要传送N个字节，就得分N/K次传送才行，每次传送都要选一次设备，通道极限流量：fmax.block=K/（Ts+KTD）=

• 选择通道每选择一台设备就把N个字节全部传送完，通道极限流量fmax.select=N/（Ts+NTD）=

---

第四章 存储体系

• 基本的二级存储体系是虚拟存储器和Cache存储器，这是存储体系的两个不同的分支。

• 虚拟存储器是因主存容量满足不了要求而提出来的。

• 在主存和辅存之间，增设辅助的软、硬件设备，让它们构成一个整体，所以也称为主存一辅存存储层次。从CPU上看，速度是接近主存的，容量是辅存的。

• 因主存速度满足不了要求而引出了Cache存储器。

• 根据存储映像算法的不同，其中主要有段式、页式和段页式3种。

• 页式存储是把主存空间和程序空间都机械地等分成固定大小的页

• 段页式的主要问题是地址变换过程至少需要查表两次，即查段表和页表。

• 简答：提高页表的空间的利用率的方法有：一种解决办法是将页表中装入位为“0”的行用实页号n，字段存放该程序此虚页在辅存中的实地址，以便调页时实现用户虚页号到辅存实地址的变换。另一种方法是把页表压缩成只存放已装入主存的那些虚页与实页位置（nv）的对应关系，该表最多为2nv行。我们称它为相联目录表法，简称目录表法。该表采用按内容访问的相联存储器构成。

• 选择：页面置换算法：随机算法、先进先出算法FIFO、近期最少使用LRU（近期最久未用过OPT 是理想算法用于评价其他算法的好坏）算法等。

综合应用题：页面置换算法：

【综合应用题】在一个采用组相联映象的Cache系统中，主存由0～15共16块组成， Cache分为2组，每组2块，每块大小为16个存储字。在某个程序执行时，访存的主存块地址流为：6、2、4、1、4，6、3、0、4，5、7、3。

（1）写出主存块地址和 Cache块地址的格式，并指出各字段的长度。

（2）采用LRU 替换算法时，画出 Cache内各块实际替换过程图，并计算Cache命中率。

• 填空：Cache的地址映像方式包括全相联映像、直接映像和组相连映像。

• 三级存储体系：①物理地址，②虚地址，③全Cache。

---

第五章 标量处理机

• 顺序执行，解释一条机器指令的微操作可归并成取指令、分析和执行三部分。

• 简答：实现指令的重叠解释必须在计算机组成上满足以下几点要求：

1）要解决访主存的冲突。2）要解决“分析”与“执行”操作的并行。3）要解决“分析”与“执行”操作控制上的同步。4）要解决指令间各种相关的处理。

• 简答：“一次重叠”的定义：任何时候都只是“执行k”与“分析k+1”重叠。就是说，即使“分析k+1”比“执行k”提前结束，“执行k”也不紧接在“分析k+1”之后与“执行”重叠进行；同样，即使“执行k”比“分析k+1”提前结束，“分析k+2”也不紧接在“执行k”之后与“分析k+1”重叠进行，称这种指令分析部件和指令执行部件在任何时候都只有相邻的两条指令在重叠解释的方式为“一次重叠”。

• “一次重叠”的好处是节省硬件，计算机内指令分析部件和指令执行部件均只需一套，也简化了控制。设计时应适当安排好微操作，使“分析”和“执行”的时间尽量等长，重叠方式才能有较高的效率。

• 指令相关是因为机器指令允许修改而引出的。如果规定在程序运行过程中不准修改指令，指令相关就不可能发生。

• 流水的最大吞吐率是指流水线满负荷每隔Δt流出一个结果时所达到的吞吐率。实际吞吐率总是低于其最大吞吐率。

• 填空：2、流水的分类流水的分类从不同的角度对流水可进行不同的分类。具体如下：①流水按处理的级别可分为部件级、处理机级和系统级。②从流水线具有功能的多少，可以分为单功能流水线和多功能流水线③按多功能流水线的各段能否允许同时用于多种不同功能连接流水，可把流水线分为静态流水线和动态流水线。④从计算机所具有的数据表示角度，可以把流水线处理机分为标量流水机和向量流水机。⑤从流水线中各功能段之间是否有反馈回路的角度，可以把流水线分为线性流水线和非线性流水线。

• 计算：1、流水线的性能与计算标量流水处理机的性能主要是吞吐率Tp、加速比Sp和效率η。其中吞吐率是流水线单位时间里能流出的任务数或结果数。

• 简答、标量流水机对局部性相关的处理一般采用总线式分布方式控制管理，包括①相关的判断主要是靠分布于各寄存器的“忙位”标志来管理；②在分散于各流水线的人、出端处设置若干保存站来缓存信息；③用站号控制公共数据总线的连接作相关专用通路，使之可为多个子过程的相关所共用；④一旦发生相关，用更换站号来推后和控制相关专用通路的连接；⑤采用多条流水线，每条流水线入端有多组保存站，以便发生相关后，可以采用异步的流动方式；

• 自从20世纪80年代RISC兴起之后，出现了提高指令级并行的高性能超级处理机，让单处理机在每个时钟周期里可解释多条指令。代表性的例子是超标量处理机、超长指令字处理机、超流水线处理机和超标量超流水线处理机。

• 【简答题】简述超标量处理机与超流水处理的区别。【参考答案】：（1）超标量处理机是利用资源重复，设置多个执行部件寄存器堆端口。（2）超流水处理机是着重开发时间并行，在公共的硬件上采用较短的时钟周期，深度流水来提高速度，需使用高速的时钟机制来实现。

---

第六章 向量处理机

1、向量处理机相关概念 ①向量处理机是有向量数据表示的处理机，分向量流水处理机和阵列处理机两类。向量流水处理机是以时间重叠途径开发的，而阵列处理机是以资源重复途径开发的。②所谓Vi冲突，指的是并行工作的各向量指令的源向量或结果向量使用了相同的Vi 。③CRAY-1向量处理的一个显著特点是只要不出现功能部件使用冲突和源向量寄存器使用冲突，通过链接机构可使有数据相关的向量指令仍能大部分时间并行执行。④链接技术是提高计算机整体运算速度的一个非常重要的措施。

（1）阵列处理机的构形阵列处理机有两种构形，差别主要在于存储器的组成方式和互连网络的作用不同。

1、互连网的设计目标SIMD系统的互连网络的设计目标是：结构不要过分复杂，以降低成本；互连要灵活，以满足算法和应用的需要；处理单元间信息交换所需的传送步数要尽可能少，以提高速度性能；能用规整单一的基本构件组合而成，或者经多次通过或者经多级连接来实现复杂的互连，使模块性好，以便于用VLSI实现并满足系统的可扩充性。

• 简答：在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结构做出抉择。操作方式有同步、异步及同步与异步组合3种。现有的阵列处理机根据其SIMD性质，均采用同步操作方式，让所有PE按时钟同步操作。异步或组合操作方式一般多用于多处理机。交换方法主要有线路交换、包交换及线路与包交换组合3种。网络的拓扑结构指的是互连网络入、出端可以连接的模式，有静态和动态两种。

• 基本的单击互连网络有：立方体单级网络、PM2I单级网络、混洗交换单级网络、蝶形单级网络。

1、脉动阵列流水处理机概念。脉动阵列结构是由一组处理单元（PE）构成的阵列。每个PE的内部结构相同，一般由一个加法／逻辑运算部件或加法／乘法运算部件再加上若干锁存器构成，可完成少数基本的算术逻辑运算操作。阵列内所有处理单元的数据锁存器都受同一个时钟控制。运算时数据在阵列结构的各个处理单元间沿各自的方向同步向前推进，形象的称其为脉动阵列结构。

2、脉动阵列结构具有如下特点：（1）结构简单、规整，模块化强，可扩充性好，非常适合用超大规模集成电路实现。（2）PE间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均简单规整。（3）脉动阵列中所有PE能同时运算，具有极高的计算并行性，可通过流水获得很高的运算效率和吞吐率。输入数据能被多个处理单元重复使用，大大减轻了阵列与外界的I/O通信量，降低了对系统主存和I/O系统频宽的要求。（4）脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI是不利的。

• 简答：发展通用脉动阵列构的途径主要有3种：（1）通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序重新配置阵列的结构。（2）用软件把不同的算法映像到固定的阵列结构上，该方法依赖于面向并行运算所采用的程序语言，操作系统，编详程序和软件开发工具的设计。（3）探寻与问题大小无关的脉动处理方法，以及VLSI运算系统的分割矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相应的设置方案。

---

第七章 多处理机

• 由于应用的目的和结构不同，多处理机可以有同构型、异构型和分布型3种。

• 简答：多处理机与阵列处理机的对比：多处理机是属于多指令流多数据流的系统。它与单指令流多数据流的阵列处理机相比，有很大的差别。其差别主要来源于并行性的等级不同，阵列处理机主要是针对向量、数组处理，实现向量指令操作级的并行，是开发并行性中的同时性。多处理机实现的则是更高一级的作业或任务间的并行，是开发并行性中的并发性。因此，在硬件结构上，它的多个处理机要用多个指令部件分别控制，通过共享主存或机间互联网络实现异步通信；在算法上，不限于向量、数组处理，还要挖掘和实现更多通用算法中隐含的并行性；在系统管理上，要更多的依靠操作系统等软件手段，有效地解决资源分析和管理，特别是任务分配、处理机调度、进程的同步和通信等问题。

1、多处理机有紧耦合和松耦合两种不同的构形。

（1）紧耦合多处理机。紧耦合多处理机是通过共享主存来实现处理机间通信的，其通信速率受限于主存频宽。各处理机与主存经互联网络连接，处理机数受限于互联网络带宽及各处理机访主存冲突的概率。

（2）松耦合多处理机。松耦合多处理机中，每台处理机都有一个容量较大的局部存储器，用于存储经常用的指令和数据，以减少紧耦合系统中存在的访主存冲突。不同处理机间或者通过通道互联实现通信，以共享某些外围设备；或者通过消息传送系统（MTS）来交换信息，这时各台处理机可带有自己的外围设备。消息传送系统常采用分时总线或环形、星型、树形等拓扑结构。松耦合多处理机较适合做粗粒度的并行计算。

2、多处理机的互连一般采用总线、环形互连、交叉开关、多端口存储器或蠕虫穿洞寻径网络等几种形式。

3、为解决多个处理机同时访问公用总线的冲突，研制了静态优先级、固定时间片、动态优先级、先来先服务等多种总线仲裁算法。

4、环形互连的缺点：由于环形互连是点点连接，不是总线连接，其物理参数容易得到控制，非常适合于有高通信带宽的光纤通信。光纤通信是很难用在总线式互连系统上的。环形互连的缺点是信息在每个接口处都会有一个单位的传输延迟，当互连的处理机机数增加时，环中的信息传输延迟将增大。令牌环可看成是一种周期短、延迟长的流水线。

• 互联网信息浏览的概念。WWW应用的基础元素是网页（Page）。网页的编写使用的是超文本标记语言（HTML），而网页中的信息在互联网中的传输是通过超文本传输协议（HTTP）来实现的。互联网中的每一个网页，都有一个唯一的标识来指示，称为统一资源定位器（URL）。

• 【简答题】简述紧耦合多处理机中解决多Cache一致性的办法。

• 【参考答案】：（1）对于进程迁移引起的多Cache之间的不一致性问题，可以通过禁止进程迁移的办法予以解决，也可以在进程挂起时，靠硬件方法将Cache中该进程改写过的信息块强制写回主存相应位置办法来解决。（2）以硬件为基础实现多Cache的一致性。以硬件为基础实现多Cache的一致性的办法有多种。最普遍采用的办法叫做监视Cache协议法，即各个处理机中的Cache 控制器随时都在监视着其他Cache的行动。（3）以软件为基础实现多Cache的一致性。

• 填空：按运算基本对象，并行算法可分为数值型和非数值型两类。基于代数运算，如矩阵运算、多项式求值、线性方程组求解等并行算法称为数值型并行算法。基于关系运算，如选择、排序、查找、字符处理的并行主要是对符号操作的，称为非数值型并行算法。按并行进程间的操作顺序不同，并行算法又分为同步型、异步型和独立型3种。根据各处理机任务的大小（即任务粒度）不同，并行算法又分为细粒度、中粒度、粗粒度3种。

• 程序并行性的分析如下：（1）数据相关。（2）数据反相关。（3）数据输出相关。

• 【综合应用题】由霍纳法则给定的表达式为E= （a+h）+b（（c+ g）+def ） 利用减少树高的办法来加速运算，要求：

（1）画出树形流程图。（2）确定Tp 加速比Sp，效率Ep的值。

• 并行语言与并行编译①并行算法需要用并行程序来实现。为了加强程序并行性的识别能力，就要使用并行程序设计语言。②并行程序设计语言的基本要求是：能使程序员在其程序中灵活、方便地表示出各类并行性，能在各种并行／向量计算机系统中高效地实现。③并行进程的特点是这些进程在时间上重叠地执行，一个进程未结束，另一个进程就已开始。④并行任务的派生是使一个任务在执行的同时，派生出可与它并行执行的其他一个或多个任务，分配给不同的处理机完成。

• 主从型操作系统

①优点：主从型操作系统的结构比较简单；整个管理程序只在一个处理机上运行，一般都不必是可再入的；只有一个处理机访问执行表，不存在系统管理控制表格的访问冲突和阻塞，简化了管理控制的实现。因此，实现起来简单、经济、方便。是目前大多数多处理机操作系统所采用的方式。

②缺点：对主处理机的可靠性要求很高，整个系统显得不够灵活，如果负荷过重，也会影响整个系统的性能。

③适用场合：主从型操作系统适用于工作负荷固定，从处理机能力明显低手主处理机，或由功能相差很大的处理机组成的异构型多处理机。

• 各自独立型操作系统

①优点：很适应分布处理的模块化结构特点，减少对大型控制专用处理机的需求；某个处理机发生故障，不会引起整个系统的瘫痪，有较高的可靠性；每台处理机都有其专用控制表格，使访问系统表格的冲突较少，也不会有许多公用的执行表，同时控制进程和用户进程一起进行调度，能取得较高的系统效率。

②缺点：实现复杂。尽管每台处理机都有自己的专业控制表格，但仍有一些共享表格，会增加共享表格的访问冲突，导致进程调度的复杂性和开销的加大，某台处理机一且发生故障，要想恢复和重新执行未完成的工作比较困难。每台处理机都有自己专用的输入／输出设备和文件，使整个系统的输入／输出结构变换需要操作员干预。各处理机负荷的平衡比较困难，各台处理机需有局部存储器存放管理程序副本，降低了存储器的利用率。

③适用场合：各自独立型操作系统适用于松耦合多处理机。

• 浮动型操作系统是介于主从型和各自独立型操作系统之间的一种折中方式，其管理程序可以在处理器之间浮动。

• 多处理机的发展形式近十几年来，多处理机发展很快，有分布式共享存储器多处理机、对称多处理机、多向量多处理机，并行向量处理机、大规模并行处理机和机群系统等。

• 简答：机群系统是将多个高性能的工作站或高档微型计算机，使用高速的通信网络加以互连组成的系统。机群系统中的主机和网络可以是同构的，也可以是异构的。主机间的通信主要采用消息传递。从结构和结点间的通信来看，是一种分布式存储方式；从用户来看，表示的是一个完整的并行系统。

• 简答：机群系统比起传统的并行处理系统有如下明显的优点：（1）系统有高的性能价格比。（2）系统的开发周期短。（3）系统的可扩展性好。（4）系统的资源利用率高。（5）用户投资风险小。（6）用户编程方便。

---

第八章 数据流计算机和规约机

• 简答：控制流方式与数据流方式的比较如下：控制驱动的控制流方式的特点是：通过访问共享存储单元让数据在指令之间传递；指令执行的顺序性隐含于控制流中，但却可以显式地使用专门的控制操作符来实现并行处理：指令执行的顺序受程序计数器控制，也就是受控制令牌所支配的。数据驱动的数据流方式则不同，它没有通常的共享变量的概念，即没有共享存储数据的概念；指令执行顺序只受指令中数据相关性的制约；数据是以数据令牌方式直接在指令之间传递的。

• 数据流是基于异步性和函数性的一种计算模型。

• 这些结点可分别表示如下：（1）常数产生结点：没有输入端、只产生常数。激发后输出带常数的令牌。（2）算逻运算操作结点，主要包括常用的十、一、＊、／、乘方、开方等算术运算及非、与、或、异或、或非等布尔逻辑运算，激发后输出带相应操作结果的令牌。（3）复制操作结点：可以是数据的多个复制，也可以是控制量的多个复制（4）判定操作结点：对输人数据按某种关系进行判断和比较，激发后在输出控制端给出带逻辑值真（T）或假（F）的控制令牌。（5）控制类操作结点：控制类操作结点的激发条件需要加到布尔控制端，可以把控制类操作结点细分为常用的4种：T门控结点、F门控结点、开关门控结点和归并门控结点。 

• 简答：数据流计算机在提高并行处理效能上有着非常显著的特点，但也存在一些问题：（1）数据流计算机的主要目的是为了提高操作级并行的开发水平，但如果题目本身数据相关性很强，内涵并行性成分不多时，就会使效率反而比传统的 Von Neumann型机的还要低。（2）在数据流计算机中为给数据建立、识别、处理标记，需要花费较多的辅助开销和较大的存储空间，但如果不用标记，则无法递归并会降低并行能力。（3）数据流计算机不保存数组。（4）数据流语言的变量代表值，而不是存储单元位置，是程序员无法控制存储分配。（5）数据流计算机互联网设计困难，输入/输出系统仍不够完善。（6）数据流计算机没有程序计数器，给诊断和维护带来了困难。

• 归约机的结构：归约机和数据流计算机一样，都是基于数据流的计算模型，只是其采用的驱动方式不同。数据流计算机采用数据驱动，执行的操作序列取决于输入数据的可用性；归约机则是需求驱动，执行的操作序列取决于对数据的需求，对数据的需求又来源于函数式程序设计语言对表达式的归约。

• 归约机的特点如下：（1）归约机应当是面向函数式语言，或以函数式语言为机器语言的非Neumann 型机器，其内部结构应不同于Neumann型机器。（2）具有大容量物理存储器并采用大虚存容量的虚拟存储器，具有高效的动态存储分配和管理的软、硬件支持，满足归约机对动态存储分配及所需存储空间大的要求。（3）处理部分应当是一种有多个处理器或多个处理机并行的结构形式，以发挥函数式程序并行处理的特长。（4）采用适合于函数式程序运行的多处理器（机）互连的结构，最好采用树形方式的互连结构或多层次复合的互连结构形式。（5）为减少进程调度及进程间的通信开销，尽量把运行进程的结点机紧靠该进程所需用的数据安排，并使运行时需相互通信的进程所占用的处理机也靠近，让各处理机的负荷平衡。

• 根据计算机所用归约方式的不同，相应就有串归约机和图归约机两类。