计算机体系结构概述

1.1计算机系统的多级层次结构

1.从使用语言的角度，可以将系统看成是按功能划分的多个机器级组成的层次结构，由高到低分别为应用语言机器级、高级语言机器级、汇编语言机器级、 操作系统机器级、传统机器语言机器级和微程序机器级。

2.各机器级的实现方法：翻译（变换成低一级等效程序）或解释（仿真高级机器级语句或指令） 3.通过多层次结构的观点可以得出，软件的功能可以由硬件实现，硬件的功能也可用软件模拟实现。

1.2计算机系统结构、组成与实现

1. 透明：客观存在的事物或属性从某个角度看不到的。

2. 计算机系统结构指的是传统机器级的系统结构；它是软、硬件之间的功能分配以及对传

统机器级界面的确定，提供机器语言、汇编语言程序设计者或编译程序生成系统为使其设计或生成的程序能在机器上正确运行应看到和遵循的计算机属性。数据表示、寻址方式、寄存器组织、指令系统、存储系统组织、中断系统、管态目态定义与转换、IO结构、保护方式和机构。

2. 计算机组成：是计算机系统结构的逻辑实现，包括机器级内的数据流和控制流的组成及逻辑设计

等。它着眼于机器级内的各事件的排序方式与控制机构、各部件的功能及各部件间的联系。近40年里，计算机组成设计主要围绕提高速度，着重从提高操作的并行度、重叠度、以及功能的分散和设置专用功能部件来设计的。

(1)数据通路宽度；(2)专用部件的设置；(3)各种操作对部件的共享程度；(4)功能部件的并行度；(5)控制机构的组成方式；(6)缓冲和排队技术； (7)预估、预判技术； (8)可靠性技术。

3.计算机实现：指的是计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，器件、模块、插件、底板的划分与连接，专用器件的设计，微组装技术，信号传输，电源、冷却及整机装配技术等。它着眼于器件技术和微组装技术，其中，器件技术在实现技术中起着主导作用。

4. 计算机系统结构、组成、实现三者互不相同，但又相互影响。

①相同结构(如指令系统相同)的计算机，可以因速度不同而采用不同的组成；相同组成可有多种不同的实现方法。②系统结构不同会使可能采用的组成技术不同。反过来，组成也会影响结构。③组成设计上面决定于结构，下面受限于实现技术，它们是可以与实现折衷权衡的。组成和实现的权衡取决于器件的来源、厂家的技术特长和性能价格比能否优化。

1.3软硬件取舍与计算机系统设计思路

1. 软硬件实现的优缺点：解题速度、程序存储空间、硬件成本、硬件利用率、计算机系统的灵活性和适应性。

2. 软、硬件取舍的基本原则

确定软、硬件功能分配比例的第一个基本原则是应考虑在现有硬、器件(主要是逻辑器件和存储器件)条件下，系统要有高的性能价格比，主要从实现费用、速度和其他性能要求来综合考虑。

确定软、硬件功能分配的第二个基本原则是，要考虑到准备采用和可能采用的组成技术，使它尽可能的不要过多或不合理的限制各种组成、实现技术的采用。

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

3. 计算机系统的设计思路

＠\"由上往下\"设计思路：从考虑如何满足应用要求，定好面对使用者那级机器应有什么基本功能和特性，逐级往下设计，每级都考虑怎样优化上一级实现，这样设计的计算机系统对于设计时面向的应用必然是很好的。缺点①是应用的改变会带来系统效率的急剧下降；②适用于专用机设计，不适用于通用机的设计。

＠\"由下往上\"设计思路：不管应用的要求，只根据已有器件和硬件的状况，先设计微程序机器级，先设计出微程序机器级（如果采用微程序控制）及传统机器级，然后再为不同应用配多种操作系统和编译软件，使应用人员可根据所提供的语言种类、数据形式，采用合适的算法来满足相应的应用。这是常用的通用机设计思路缺点是①造成软硬件脱节，软件设计复杂；

＠\"由中间开始\"设计思路：\"中间\"指的是层次结构中的软硬交界面，目前多数是传统及其级与操作系统机器级之间。既考虑能拿到的硬、器件，又要考虑硬件对操作系统、编译系统的实现提供什么支持，然后由中间点分别往上、往下进行软件和硬件的设计。优点在于：针对上述两种方法的缺陷，软件和硬件并行设计，可缩短系统设计周期，设计过程中可交流协调，是一种交互式的、较好的设计方法。

1.4结构设计要解决好软件的可移植性 1.实现软件移植的好处和技术

软件的可移植性：指的是软件不修改或只经少量修改就可由一台机器移到另一台机器上运行，同一软件可应用于不同的环境。这样，实践证明是可靠的软件就能长期使用，不会因机器更新去重新编写，既大大减少了编制软件的工作量，又能迅速用上新的硬件技术，更新系统，让新系统立即发挥效能。

实现软件移植的几个基本技术：统一高级语言、采用系列机、模拟和仿真。 2. 统一高级语言

统一高级语言：实现软件移植的一种技术是统一高级语言，设计出一种完全通用的高级语言，为所有程序员所使用。这样，结构相同以至完全不同的机器之间都能实现高级语言程序的软件移植。

第一，不同的用途要求语言的语法、语义结构不同。 第二，人们对语言的基本结构看法不一。 第三，即使同一种高级语言在不同厂家的机器上也不能完全通用。第四，受习惯势力阻挠，人们不愿抛弃惯用的语言，因为熟悉、有经验，也不愿抛弃长期积累的、用原有语言编写并已被实践证明是正确的软件。

对策：统一高级语言可以解决结构相同或完全不同的机器间的软件移植，从长远看是方向但目前难以解决，只能作相对统一。

3.采用系列机

＠系列机设计是从中间向两边设计相呼应。在软、硬件界面上设定好一种系统结构(系列机中称系列结构)，其后，软件设计者按此设计软件，硬件设计者根据机器速度、性能、价格的不同，选择不同器件、硬件和组成、实现技术，研制并提供不同档次的机器。

＠采用系列机：在结构相同或相似的机器之间实现软件移植

＠优点：①解决了软件环境要求稳定，软件可不断积累、丰富、提高。②能不断采用新的器件和硬件技术，使之性能不断提高。缺点：因要保持向后兼容性，器件越来越复杂，最终系统结构受到发展限制。

＠系列机软件兼容的最基本的要求和特征是系列机软件必须保证向后兼容，力争向上兼容。 对策：系列机是普遍采用的好办法，但只能实现同一系列内软件兼容，同时软件兼容又会阻碍系统结构突破性的发展；适当的时候推出新的系列结构。

4.模拟和仿真

模拟和仿真是不同系统结构的机器之间的机器语言软件移植方法。这种用机器语言程序解释实现软件移植的方法称为模拟。缺点：运行速度显著降低，实时性差，模拟程序编制复杂和费时。用微程序直接解释另一种机器指令系统的方法就称为仿真。缺点：微程序机器结构深深依赖于传统机器级的结构，当两种机器结构差别大时就很难仿真。

两者区别：在于解释用的语言。仿真是用微程序解释，其解释程序存在控制存储器中；模拟是用机器语言解释，其解释程序存在主存中。

对策：模拟灵活，可实现不同系统间的软件移植，但结构差异较大时，效率、速度会急剧下降；仿真速度较快，但不灵活，只能在差别不大的系统之间使用。因此，在不同系列机器间的软件移植时，将模拟和仿真两种技术结合起来使用。

1.5应用与器件的发展对系统结构的影响

1. 应用的发展对系统结构的影响

计算机工业在处理性能和价格的关系上大致也是这两种趋势：维持价格提高性能；维持性能降低价格。 从系统结构的观点看：①低档(型)机上引用甚至照搬高档(型)机的结构和组成。②巨、大型机一般采取维持价格、提高性能或提高价格、提高性能来研究和采用新的结构及组成。③为保持小、微型机的便宜价格，从结构和组成上采用为不同用途提供相应选购件或扩展部件的做法是可取的。

2. 器件的发展对系统结构的影响

器件的发展历程：从电子管、晶体管、小规模集成电路、大规模集成电路迅速发展到超大规模集成电路，并使用或开始使用砷化镓器件、高密度组装技术和光电子集成技术。在此期间，器件的使用方法发生了由非用户片，发展到现场片和用户片，它影响着结构和组成技术的发展。已从非用户片发展到现场片与用户片。

一般同一系列内各档机器可分别用通用片、现场片或用户片实现。就是同一型号机器也先用通用片或现场片来实现，等机器成熟取得用户信任后，再改用半用户片或全用户片实现。至于高速机器一般一开始就用门阵列片或用户片，只有这样，才能发挥出单元电路的高速性。

①器件的发展改变了计算机系统设计的传统方法。过去逻辑设计主要是以节省功耗、降低成本、提高速度为目的，而对VLSI来说，如何能缩短设计周期、提高系统效能及能用上批量生产的通用的VLIS片子为目的。②器件的发展推动结构和组成的发展。促使计算机性能价格比的提高；加速了结构的“下移”；促进了算法、语言和软件的发展。

1.6系统结构中的并行性发展和计算机系统的分类 1.并行性含义：

1）并行性：指有同时进行运算或操作的特性。开发并行性的目的是为了能并行处理，以提高计算机解题的效率。并行性包括同时性（二个或多个事件在同一时刻发生）和并发性（两个或多个事件在同一时间间隔内发生）

2）并行性等级

＠执行程序的等级划分：（由低到高）指令内部、指令之间、任务或进程之间、作业或程序之间 ＠处理数据的等级划分：（由低到高）位串字串、位并字串、位片串字并、全并行

＠信息加工的等级划分：（由低到高）存储器操作并行、处理器操作并行、处理器操作并行、指令、任务、作业并行。

3）并行性开发的途径

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

＠资源重复：是在并行概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。 ＠资源共享：是用软件的方法让多个用户按一定时间顺序轮流使用同一套资源来提高其利用率，相应也就提高了系统的性能。

4

在1960年以前，并行性发展主要表现为算术运算的位并行及运算与输入/输出操作的并行。 1960～1970年的这段时间内，出现了多道程序分时系统、多功能部件、流水线单处理机等。 1970～1980年，VLSI的普遍应用加快了并行处理系统结构的发展，出现了大型和巨型的向量机、阵列机、相联处理等多种并行处理系统结构。

1980～1990年，在系统结构上创新和突破影响较大的有精简指令系统计算机(RISC)，指令级并行的超标量处理机、超流水线处理机、超长指令字(VLIW)计算机，多微处理机系统，数据流计算机和智能计算机。

1990年以来，计算机发展进入新的多计算机和智能计算机时代。机器最主要的特点是进行大规模并行处理(MPP)，采用VLSI硅片、砷化镓、高密度组装和光电子技术。多处理机包括多向量机及机群系统、多计算机系统将是今后并行处理计算机发展的主流。

3T性能目标：科学计算中的重大挑战性课题往往要求计算机系统能有1TFLOPS的计算能力、1TB的主存容量、1TB/s的I/O带宽，称之为3T性能目标。

2并行处理系统的结构与多机系统的耦合度

1）并行处理计算机的结构：并行处理机按其基本结构特性，可以分为：流水线计算机、阵列处理机、多处理机（分布处理、机群系统和MPP）和数据流计算机四种不同结构。

2）多机系统的耦合度：多机系统包含多处理机系统和多计算机系统。多处理机系统：是由多台处理机组成的单一系统。多计算机系统：则是由多台独立的计算机组成的系统。

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

3. 计算机系统的分类（弗林分类法）

按指令流和数据流的多倍性对计算机分类分为：SISD（单处理器的计算机、流水线单处理机）、SIMD（阵列处理机、相联处理机）、MISD（脉动阵列流水机）、MIMD（多处理机和多计算机系统）四大类

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

2.1数据表示

1. 数据表示与数据结构的关系

数据表示指的是能由机器硬件直接识别和引用（处理）的数据类型；数据表示是硬件设计的基础，表现在它具有对这种数据类型进行操作的指令和运算部件。数据结构反映应用中要用到的各种数据元素之间的结构关系，是软硬功能分配中软的方面。数据结构是通过软件映象变换成机器所具有的各种数据表示实现，数据表示是数据结构的组 成元素。

2. 高级数据表示 1) 自定义数据表示

为了缩短高级语言与机器语言的语义差距引出来的，它有标志符数据表示和数据描述符数据表示 2）带标志符的数据表示

让数据类型直接与数据本身联系在一起，运算符不反映数据类型，是通用的。将数据类型和数据本身联系在一起，机器语言中的操作码和高级语言的运算符一样能够通用于各种数据类型的操作称这种数据表示为标志符数据表示。标志符应由编译程序建立，对高级语言程序透明，以减轻应用程序员的负担。

优点：简化了指令系统和程序设计；简化了编译程序；便于实现一致性校验；能由硬件自动完成数据类型的变换；支持了数据库系统的实现与数据类型无关的要求；为软件调试和应用软件开发提供了支持。

缺点：每个数据字因增设标志符，会使程序所占用的主存空间增加；采用标志符会降低指令的执行速度。

3）数据描述符

主要用于描述向量、数组、记录等成块数据。数据描述符和标志符的差别：标志符是和每个数据相连的，合存在一个存贮单元中，描述单个数据的类型特征；描述符是和数据分开存放的，专门用来描述所要访问的整块数据特征。

优点：描述相同类型的数据块时，占用空间比标志符少，比标志符的效率要高；为向量、数组实现提供了支持，有利于简化高级语言编译中的代码生成可以比变址法更快形成元素地址。

缺点：由于没有相应的向量、数组运算类指令的高速运算硬件，数据描述符并不能支持向量、数组的高效实现。

4）向量数据表示

为向量、数组数据结构的实现和快速运算提供更好的硬件支持的方法是增设向量、数组数据表示，组成向量机，如STAR-100和CRAY-1等。有向量数据表示的处理机就是向量处理机，如向量流水机、阵列机、相联处理机等。

引入向量、数组数据表示不只是能快速形成元素的地址，更主要的是便于实现把向量各元素成块预取到中央处理机，并用一条向量、数组指令流水或同时对整个向量、数组高速处理，用硬件判断下标是否越界，并让越界判断和元素运算并行。高速巨型机都设置有向量数据表示；现在向量、数据表示已下移到了通用机和系列机上。

5）堆栈数据表示

堆栈数据结构在编译和子程序调用中很有用，为高效实现，不少机器都设有堆栈数据表示。 堆栈机器特点：①有高速寄存器组成的硬件堆栈，并与主存中的堆栈区在逻辑上构成整体，使堆栈的访问速度是寄存器的，容量是主存的。②有丰富的堆栈操作指令且功能很强，直接可对堆栈中的数据进行各种运算和处理。③有力地支持了高级语言程序的编译。④有力地支持了子程序的嵌套和递归调用。

6）引入数据表示的原则

＠一是看系统的效率是否提高，即是否减少了实现时间和存储时间。 ＠二是看引入这种数据表示后，其通用性和利用率是否高。

数据表示的确定：①一般计算机选用常用的数据表示；②对较高级的数据表示要有针对性的选取； 3. 浮点数尾数基值大小和下溢处理方法的选择 1) 浮点数尾数基值大小

当机器字长相同时，用浮点数表示实数比用定点数表示有更大的可表示数范围。

当总的机器字长定好后，浮点数表示中p和m的位数主要是根据数的表示范围和精度来定。浮点数阶值的位数p主要影响两个可表示区的大小，即可表示数的范围大小，而尾数的位数m主要影响在可表示

区中能表示值的精度。当阶值位数p、m一定时，尾数采用什么进制也还会影响到数的可表示范围、精度及数在数轴上分布的离散程度。

非负阶、正尾数，且都是规格化数的情况：

可表示最小尾数值：rm可表示最大阶值： 2

p

-1

可表示最大尾数值：1-rm

-m‘

-1 可表示最小值：rm-1

可表示尾数的个数：

可表示最大值：可表示阶的个数：2

p

可表示数的个数：2

p

·

尾数基值取大，会扩大浮点数的范围、增加可表示数的个数、减少移位的次数、降低右移造成的精度损失、提高运算速度，这些都是好的；但会降低数据的表示精度、数值的分布变稀，这些都是不好的。因此

选取根据应用需要来综合平衡：一般在大、中型机上，

宜取大，这样可使数的表示范围大、个数

多、运算速度快，因浮点数尾数位数相对多得多，所以精度实际比小、微型机的高得多；而小、微型机由于可表示数范围不要求太大，速度也不要求太高，尾数字长较短，所以更注重于可表示精度，宜使小些。

2) 下溢处理方法的选择

下面以二进制数0.0111为例，机器字长为2。大家还要看看各种方法的误差问题 1）截断法：0.01,去掉你的尾巴

2）舍入法：0.10，小数点第三位为1进1，为0舍去 3）恒置1法：0.01

4）查表舍入法：用2^K的ROM存放下溢处理表，地址值由尾数的K-1位和弃掉最高位组成，ROM对应的内容就是下溢处理结果。

产生误差值最大的是恒置1法，最小的舍入法；平均误差最大的是截断法，最小的是查表舍入法；下溢处理不需要附加时间，速度最快的是截断法和恒置1法，最省硬件的是截断法和恒置1法，最慢的是舍入法，最费硬件的是查表舍入法。

基本思想：ROM查表舍入法是将K位数据下溢处理成K-1位的结果，ROM表存储容量为2k个单元，每个单元字长为K-1位。待处理的K位数据作为地址，按此地址读出表中对应单元中所存放的K-1位内容就是该数经下溢处理后的结果。ROM表的安排原则：Ⅰ）当k位尾数为非全1时，按舍入法取值；Ⅱ）当k位尾数为全1时，按截断法取值。

2.2寻址方式

1）寻址方式：指令寻找操作数或信息的方式，有面向寄存器、面向堆栈、面向主存三种方式。 2）寻址方式在指令中的两种指名方式

取得

3）程序在主存中的定位技术

静态再定位是目的程序装入主存时，通过调用装入程序，把目的程序的逻辑地址用软的方法逐一修改成物理地址。不利于多道程序运行、程序的可重入、故障排除、重叠流水技术使用。

动态再定位的一种方法是设置基址寄存器和地址加法器硬件，在程序装入主存时，只将装入主存的起始地址存入该道程序的基址寄存器中，指令的地址字段不做修改。程序在执行过程中，不断将逻辑地址经地址加法器加上基址寄存器中的基址，形成物理地址访存。

基址寻址与变址寻址的区别：基址寻址是对逻辑地址空间到物理地址空间变换的支持，以利于实现程序的动态在定为。变址寻址是对向量、数组等数据块的运算支持，以利于实现程序的循环。

4）信息按整数边界存放

主存内一般同时存有多种长度的信息，为了让任何所需的信息都只用一个存储周期访问到，就要求信息在主存中存放的地址必须是该信息宽度的整数倍。P61.7

2.3指令格式的优化设计

指令格式的优化来说，就是指如何用最短的位数来表示指令的操作信息和地址信息，使程序中指令的平均字长最短。

1）指令操作码的优化

研究操作码的优化表示，主要是为了缩短指令字长，减少程序总位数及增加指令字能表示的操作信息和地址信息。

哈夫曼编码的基本思想。

①操作码等长编码 操作码用定长码表示需要②哈夫曼编码

步骤：1）将所有指令的使用频率由小到大排序； 2）每次选择基中最小的二个频度合并成一个频度，并插入余下未参与结合的频度值中；3）重复步骤2直至结合完毕形成根结点 4）每个结点向下延伸的二个分支左标\"1\"，右标\"0\"（相反也行）5）从根结点开始沿线到达各指令所经的代码序列就构成了该频度指令的哈夫曼编码。

哈夫曼编码的平均码长公式

哈夫曼编码并不是惟一的，但只要采用全哈夫曼编码，操作码的平均码长肯定是惟一的，而且是可用二进制位编码平均码长最短的编码。全哈夫曼编码是最优化的编码。但这种编码的码长种类太多。

③扩展操作码编码

用有限的几种码长对操作码给行编码，即让平均码长接近哈夫曼编码，又能让计算机方便地进行处理。

扩展码的扩展的方法：早期一般采用等长扩展，如15/15/15法和8/64/512法，但现在不再强调等长扩展了。

2）指令格式优化的措施

(即3)位

在操作码优化的基础上，再在地址码和寻址方式采取相关措施，就可以减少程序的总位数，使指令字格式达到优化。

①采用扩展操作码，并根据指令的频度pi的分布状况选择合适的编码方式，以缩短操作码的平均码

②采用诸如基址、变址、相对、寄存器、寄存器间接、段式存放、隐式指明等多种寻址方式，以缩短地址码的长度，并在有限的地址长度内提供更多的地址信息；

③采用0、1、2、3等多种地址制，以增强指令的功能，这样，从宏观上就越能缩短程序的长度，并加快程序的执行速度；

④在同种地址制内再采用多种地址形式，如寄存器-寄存器、寄存器-主存、主存-主存等，让每种地

⑤在维持指令字在存储器中按整数边2.4按CISC方向发展和改进指令系统 1.CISC改进思路

如何进一步增强原有指令的功能以及设置更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬化。它可从面向目标程序、面向高级语言、面向操作系统三个方面的优化实现来考虑。

1） 面向目标程序的优化实现改进

目标是：提高包括系统软件和应用软件在内的各种机器语言目标程序的实现效率。该方法既能减少目标程序占用的存储空间，缩短指令的执行时间，提高程序的运行速度，使实现更加方便。

途径是：第一种思路是通过对大量已有机器的机器语言程序及其执行情况进行统计各种指令和指令串的使用频度来加以分析和改进。对高频指令可增强其功能，加快其执行速度，缩短其指令字长；而对使用频度很低的指令可考虑将其功能合并到某些高频的指令中去，或在今后设计新系列机时，将其取消。对高频的指令串可增设新指令取代。

第二种思路是增设强功能复合指令来取代原先是由常用宏指令或子程序实现的功能，由微程序解释实现，不仅大大提高了运算速度，减少了程序调用的额外开销，也减少了子程序所占的主存空间。用新指令替代常用指令串的办法实质上是尽量减少程序中不执行数据变换的非功能型指令的使用，让真正执行数据变换的功能型指令所占的比例提高。

2）面向高级语言的优化实现改进

目标：就是尽可能缩短高级语言和机器语言的语义差距，支持高级语言编译，缩短编译程序长度和编译时间。

途径：第一种改进思路是通过对源程序中各种高级语言语句的使用频度进行统计来分析改进。对高频语句增设与之语义差距小的新指令。

第二种重要的思路是如何面向编译，优化代码的生成来改进，增强系统结构的规整性和对称性来改进指。

第三种思路是设法改进指令系统，使它与各种语言间的语义差距都有同等的缩小。 第四种思路，让机器具有分别面向各种高级语言的多种指令系统、多种系统结构，并动态的切换，发展自适应系统。

第五种思路，发展高级语言计算机(或称高级语言机器). 3）面向操作系统的优化实现改进

目标：就是如何缩短操作系统与计算机系统结构之间的语义差距，进一步减少运行操作系统的时间和节省操作系统软件所占用的存储空间。

途径：第一种思路同样是通过对操作系统中常用指令和指令串的使用频度进行统计分析来改进。但这种改进的效果很有限。

第二种思路是考虑如何增设专用于操作系统的新指令。

第三个思路是把操作系统中频繁使用的，对速度影响大的机构型软件子程序硬化或固化，改为直接用硬件或微程序解释实现。

第四个思路是：发展让操作系统由专门的处理机来执行的功能分布处理系统结构。 2.5按RISC方向发展与改进指令系统 1. CISC结构的问题

①指令系统庞大，一般在200条指令以上。延长了设计周期，增大了设计成本，增大设计出错的机会，降低了系统的可靠性。②许多指令的操作繁杂，执行速度很低。③指令系统庞大，使高级语言编译程序选择目标指令的范围太大，难以优化生成高效机器语言程序，编译程序也太长、太复杂。④指令系统庞大，各种指令的使用频度都不会太高，80%的指令使用频度低，降低了系统的性能价格比。

2.设计RISC机器一般原则

(1)确定指令系统时，精简指令条数，只选择使用频度很高的那些指令，使之一般不超过100(2)减少指令系统所用寻址方式种类，一般不超过两种。简化指令的格式限制在两种之内，并让全部指令都是相同长度。

(3)让所有指令都在一个机器周期内完成。 (4)(5)

(6)通过精简指令和优

3. 设计RISC结构采用的基本技术 (1)按设计RISC的一般原则来设计。 (2)逻辑实现采用硬联和微程序相结合。

(3)在CPU中设置大量工作寄存器并采用重叠寄存器窗口。 (4)指令用流水和延迟转移。

(5)采用高速缓冲存储器Cache,设置指令Cache和数据Cache分别存放指令和数据。

(6)优化设计编译系统。

4. 采用RISC结构后可以带来如下好处： (1)简化指令系统设计，适合VLSI实现。 (2)提高机器的执行速度和效率。

(3)降低了设计成本，提高了系统的可靠性。

(4)可直接支持高级语言的实现，简化编译程序的设计。 5. RISC存在某些问题及发展趋势

(1)由于指令少，使原在CISC上由单一指令完成的某些复杂功能现在要用多条RISC指令才能完成，加重了汇编语言程序设计的负担，增加了机器语言程序的长度，占用存储空间多，加大了指令的信息流量。(2)对浮点运算执行和虚拟存储器的支持虽有很大加强，但仍显得不足。(3)RISC机器的编译程序比CISC的难写。

今后计算机发展趋势：使得在设计CPU时，向着RISC和CISC结合，取长补短的方向发展。

第3章 总线、中断和输入输出系统

3.1输入输出系统的基本概念 1.I/O系统的组成

输入输出系统包括输入输出设备、设备控制器及与输入输出操作有关的软、硬件。 2.I/O系统的面向操作系统的设计

目前，大多数计算机系统上，用户程序的输入输出不能由用户自己安排，通过高级语言的I/O读写语句到编译程序、操作系统软件和I/O总线、设备控制器、设备硬件等共同完成。I/O功能只反映在高级语言与操作系统的界面上，应用程序员不必具体安排程序是怎样完成输入输出的。因此，大多数计算机的I/O系统的设计应是面向操作系统，考虑怎样在操作系统与I/O系统之间进行合理的软、硬件功能的分配。输入输出系统硬件的功能对应用程序员来说是透明的。

3. I/O系统的发展

I/O系统的发展经历了3个阶段（3种I/O方式）：程序控制I/O方式（全软的、程序查询的、中断驱动）、直接存储器访问方式（DMA）、及I/O处理机方式。对于I/O处理机方式又分为：通道方式（CH）和外围处理机方式（PPU）。

3.2总线设计 1.总线分类

1）单向传输和双向传输：（允许信息传送方向） 2）专用总线和非专用总线（用法）

＠专用总线：优点是多个部件同时收发，不争用总线，系统流量高，控制简单，可靠性高，但线路复杂。 ＠非专用总线：多种功能或多个部件分时共享，同是只有一对部件可使用总线进行通讯。优点是总线数

少，接口标准化，模块性强，可扩充能力强，缺点是系统流量小，出现争用总线的情况，可能导致系统瘫痪.

2.总线的控制方式

1）串行链接：所有部件经公共\"总线请求\"向控制器发出使用申请；\"总线请求\"信号串行通过每个部件，发送结束后去除\"总线忙\"，由部件物理位置决定其使用总线优先级。优点是控制简单。缺点是优先级不灵活，信号失效敏感。

2）集中式查询：所有部件经公共\"总线请求\"向控制器发出使用申请；总线定时查询计数并寻找发送部件。优点是优先级灵活，可靠性高，缺点是控制线数多，控制复杂。

3）集中式独立请求方式：每个部件各自一对\"请求\"和\"准许\"线；控制器根据某种算法确定使用总线部件。优点是总线分配速度快，优先级灵活。缺点是控制线数多，控制复杂。

3.总线的通讯技术：同步通讯和异步通讯，异步通讯又分为单向控制和请求/回答双向控制两种方式。 4、数据宽度与总线线数

＠数据宽度：是I/O设备取得I/O总线后所传送的数据总量。有单字、定长块、可变长块、单字加定长块和单字加可变长块等。数据宽度是指I/O设备取得I/O总线后一次所传送的数据总量，分类也是按这标准进行划分的。

＠总线线数：在满足性能前提下，总线线数可通过线的组合、编码及并/串-串/并转换来减少，但一般会降低总线的流量。

3.3中断系统 1.中断的分类和分级 1）基本概念

＠中断源：引起中断的各种事件

＠中断请求：中断源向中断系统发出请求中断的申请

＠中断响应的过程：CPU中断现行程序的运行，转去对该请求进行预处理，调出有关中断的处理服务程序，准备运行。 2）中断的分类：

＠为什么要分类：不少中断源性质相近，为了简化中断处理程序入口地址形成硬件，将它们归为几类，每类给定一个中断服务程序入口，再由软件分支转入相应的中断处理部分。

＠一般分为：机器校验，管理程序调用，程序性，外部，输入输出和重新启动6类。

＠多个中断请求的同时出现就要对中断进行分级（中断响应的优先次序）：依次为：机器校验、程序性和管理程序调用、外部中断和I/O中断、重新启动。

2.通过中断屏蔽位改变中断响应次序的方法 1)中断响应的优先次序和中断处理次序

＠中断响应次序是由硬件中中断排队器所决定的中断响应次序，是定死的。

＠中断的处理要由中断处理程序来完成，而中断处理程序在执行前或执行中是可以被中断的，所以中断处理次序和中断响应的优先次序可以不同，中断级屏蔽位寄存器用以决定某级中断请求能否进入中断响应排队器。课本P71页范例.

3.中断系统的软硬件功能分配

＠中断系统的功能包括：中断请求的保存、优先级的确定（硬件）、中断现场的保存、对中断请求的分析（硬件）和处理、中断返回等。

3.4通道处理机

1.通道处理机进行输入输出的过程

在多用户环境下，应用程序进行一次输入输出，只能在目态程序中安排要求输入/输出的访管指令，并带上设备号、设备与主存交换的字节数、与主存交换信息的起始地址等参数。

CPU执行到访管指令时，按其入口地址，将管理程序调出来执行。此管理程序任务是根据提供的参数编制通道程序。

编制好的通道程序存在主存对应该通道的通道缓冲区中，就置好相应通道地址字。之后，管理程序就执行“启动I/O”指令，进入通道开始选择设备期。

在通道开始选择设备期内，CPU先选择指定的通道、子通道、备控制器和设备，向设备发启动命令。设备启动成功后，CPU退出管态，继续运行目态程序。而通道进入通道数据传送期。

被启动的通道开始执行存放于通道缓冲区内通道程序组织I/O操作，直至通道程序执行完无链通道指令后，传送完成，转入通道数据传送结束期，向CPU发出I/O中断请求。CPU响应此中断请求后，第二次转管态，调出相应管理程序对中断请求进行处理。之后，再返回目态，继续目态程序的运行。

这样，每完成一次输入/输出只需两次进管，大大减少了对目态程序的干扰，显著提高了CPU运算和外设操作及多台设备可以并行工作。

2.通道的分类

根据通道数据传送期中信息传送方式的不同，分字节多路、选择和数组多路三类通道。

字节多路通道适用于连接大量的像光电机等字符类低速设备（如键盘、鼠标、打印机）。通道“数据宽度”为单字节，以字节交叉方式轮流为多台低速设备服务，使效率提高。

数组多路通道适合于连接多台像磁盘等高速设备。“数据宽度”为定长块，传送完K个字节数据后就重新选择下个设备。采用成组交叉方式轮流为多台磁盘设备服务。

选择通道适合于连接优先级高的磁盘等高速设备（如高速磁盘等），让它独占通道，只能执行一道通道程序。“数据宽度”为可变长块，一次对N个字节全部传送完。

3. 通道流量的分析

通道流量：通道在数据传送期内，单位时间内传送的字节数。

假设设计通道选择一次设备的时间TS和传送一个字节的时间TD，数组多路通道每选择一台设备传送“定长块”K个字节，选择通道每选择一台设备传送“可变长块”N个字节。

字节多路通道极限流量 数组多路通道极限流量

选择通道通道极限流量

当挂上设备后，设备要求通道的实际最大流量：

字节多路通道 数组多路通道 选择通道通道

所挂设备在满负荷的最坏情况下都不丢失信息，必须满足设备要求通道的实际最大流量不超过通道的

极限流量，因此，上述三类通道应分别满足、、

如果I/O系统有m个通道，其中1至m1为字节多路，m1+1至m2为数组多路，m2+1至m为选择，则I

/O系统的极限流量为:

第4章 存储体系

4.1 存储体系的概念与并行主存系统 1.发展存储体系的必要性

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

最大频宽Bm是存储器连续访问时的频宽。单体的Bm=W/TA。m个存储体并行的最大频宽Bm=W×m/TA。由于存储器不一定能满负荷工作，因此，实际频宽往往低于最大频宽。

为弥补CPU与存储器在速度上的差距一条途径是发展存储系统，在组成上引入并行和重叠技术，构成并行主存系统，在保持每位价格基本不变的情况下，能使主存的频宽得到较大的提高；但靠这种并行主存的方法来提高频宽是有限的。

为弥补CPU与存储器在速度上的差距另一条途径是从系统结构上改进，发展存储体系；使所有信息以各种方式分布于不同的存储器上。例如，至少应有主存和辅存。

2.并行主存系统

能并行读出CPU字的单体多字和多体单字、多体多字的交叉访问主存系统。

单体单字存储器：Bm=W/Tm 单体多字存储器：Bm=mW/Tm 多体多字交叉访问存储器：Bm=mW/Tm 3. 并行主存系统频宽的分析

提高模m值是能提高并行主存系统的最大频宽的直接方法，但主存实际频宽并不是随m值增大而线性提高。原因在于以下两点：一是系统效率的问题。二是在工程实现上由于模m越高，存储器数据总线越长，总线上并联的负载越重，有时还不得不增加门的级数，这些都会使传输延迟增加。平均频宽是

其中m是分体个数，

4.存储体系的概念

是转移概率。

1）存储体系：让构成存储系统的n种不同的存储器(M1～Mn)之间，配上辅助软、硬件或辅助硬件，使之从应用程序员来看，它们在逻辑上是一个整体。让存储层次的等效访问速度是接近于M1的，容量是Mn的，每位价格是接近于Mn的。典型的两级存储体系是虚拟存储器和Cache存储器。

虚拟存储器：是从主存容量满足不了要求提出来的。从应用程序员来看，主、辅存就构成了一个完整的整体，速度接近于主存的，容量是辅存的，每位价格接近于的辅存。

Cache存储器：在CPU和主存之间增设高速、小容量、每位价格较高的Cache，用辅助硬件将Cache和主存构成整体。从CPU看，有接近于Cache的速度、主存的容量，接近于主存的每位价格。

2）存储体系透明性

虚拟存储器和Cache存储器对应用程序员来说都是透明的。虚拟存储器由辅助软件和硬件来完成，对系统程序员是不透明的，Cache存储器是由硬件来构成的对系统程序员来说也是透明的。

3）存储体系构成依据是程序的局部性

程序局部性包括时间上的局部性和空间上的局部性。前者指的是在最近的未来要用到的信息很可能是现在正在使用的信息，这是因为程序存在循环。后者指的是在最近的未来要用到的信息很可能与现在正在使用的信息在程序空间上是邻近的，这是因为指令通常是顺序存放、顺序执行，数据通常是以向量、阵列、树形、表格等形式簇聚地存放的。

4）存储体系的性能参数

为评价存储层次性能，引入存储层次的每位价格c、命中率H和等效访问时间TA。

存储层次的每位价格

使SM1 <命中率H定义为CPU产生的逻辑地址能在M1中访问到(命中到)的概率。

存储层次的等效访问时间希望TA越接近于TA1，即存储层次访问效率

越接近于1越好。

在主、辅存之间增加一级电子磁盘，使级间r值不会过大，有利于降低对H的要求，以获得同样的e。所以要想使存储层次的访问效率e趋于1，就要在选择具有高命中率的算法、相邻二级的容量差和速度差及增加的辅助软、硬件的代价等因素间综合权衡，进行优化设计。

4.2虚拟存储器

根据所用的映像算法，将虚拟存储器管理方式分成段式、页式和段页式3种 （一）页式虚拟存储器管理方式

1）思想：逻辑空间分页，物理空间分同样大小的页，二者对应。 2）页表：主存起点，装入位，访问方式，专用位 3）地址变换过程（P92图4.13）

＠根据虚地址中的用户标志在页表基址寄存器找到程序页表的始点； ＠根据程序页表的始表和虚地址中的用户虚页号找到页表的对应行； ＠把页表对应行的实页号和虚地址的页内位移装入到主存地址寄存器 ＠根据主存寄存器的值访问主存。

4）优缺点：优点是映象表硬件较少，地址转换速度快，调入操作简单，页内零头浪费少。缺点是不易修改、保护，不易实现其用段的管理。

（二）页式虚拟存储器构成 1.地址的映像和变换 1）地址的映像和变换

虚地址Ns：用户标志U、用户虚页号Nv'及页内地址Nr； 实地址np：实页号nv、页内位移nr；

地址映象和变换：因为Nv>>nv，所以如何把多用户虚地址Ns变换成主存地址np；

2）全相联映象：让每道程序的任何虚页可以映象装入任何实页位置。它用页表作为地址映象表，故称之为页表法。

3）相联目录表法：由于页表中绝大部份行中的实页号及其它字段无用，降低了页表的空间利用率，所以把页表压缩成只存放已装入主存的那些虚页与实页位置的对应关系，简称目录表法。

4）外页表与内页表：用类似于页表的方式为每道程序设置一个存放用户虚页号与辅存实地址映象关系的表称为外页表；而页表则称为内页表。内页表的地址映象和变换是由硬件完成的，外页表由于辅存访问速度比较慢，所以用软件实现以节省硬件成本。[例]P123习题8

2.页面替换算法

1）替换算法：虚存的空间要比主存的空间大得多，当出现页面失效而主页页已满的情况下，必须强制主存中腾出某页让给辅存调来的新页，调出主存中的哪页的方法即为替换算法。替换算法的确定主要看主存是否有高的命中率。

2）RAND、FIFO、LRU及OPT算法

RAND算法：用软硬件的随面数产生主存中要被替换页的页号。

FIFO算法：选择最早装入主存的页作为被替换的页。这种算法实现方便，但不一定正确反映出程序的局部性。

LRU算法：选择近期最少访问的页作为被替换页。实现的方法是通过主存页面表来反映

OPT算法：根据未来实际使用情况将未来的近期里不用的页替换出去。这种算法是用来评价期它替换算法好坏的标准。不可能实现。

3）页地址模拟流 [例]P123习题4.9 [例]P122 习题4.6

4）堆栈型替换算法：设A是长度为L的任意一个页地址流,t为已处理过t-1个页面的时间点,n为分配给该地址流的主存页数，Bt(n)表示在t时间点、在n页主存中的页面集合，Lt表示到t时间点已遇到过的地址流中相异页的页数。如果替换算法满足：

n＜Lt时，Bt(n)

Bt(n+1)

n≥Lt时，Bt(n)=Bt(n+1)

则属堆栈型的替换算法。

LRU和OPT算法是堆栈型替换算法，FIFO算法不是堆栈型替换算法； 堆栈型算法的特性：命中率随主页数增加只有可能提高，至少不会降低。

5）PFF算法：由LRU算法加以改进，原理是由操作系统动态调节分配给各道程序的实页数。 3.虚拟存储器工作全过程 4.页式虚拟存储器实现中的问题 1）页面失效的处理

页面失效产生原因：页面的划分只是对程序和主存空间进行机械等分，造成指令或操作数横跨在两页上存储；

页面失效的处理不能按一般的中断对待，应看做是一种故障，必须立即响应和处理。解决的方法：后援寄存器法；

P122 习题4.4

2）提高虚拟存储器等效访问速度的措施

影响虚拟存储器等效访问的瓶颈：页表大并放在主存中；

解决方法：小机器用快速随机存储器或寄存器组来存放页表；大机器是靠硬件上增设快表来解决；

快表和慢表、散列、散列冲突

请大家结合习题P122页习题4.8和课本P107页的图4.27理解一下，这题我们在前面作过。 3）影响主存命中率和CPU效率的某些因素

页面大小Sp与主存命中率H的关系：随着Sp的逐渐增大，H先增大到最大值后又减小 分配给某道程序的容量S1与H的关系：随着S1逐渐增大，H先增加到最大值后趋向平缓（堆栈型算法。）。

请大家结合P122习题4.6和4.9理解一下 （二）段式管理

1）思想：逻辑空间分段，物理空间分区，段对应区。 2）段表：段名，地址，装入位，段长，访问方法。 3）地址变换过程：（请与课本P90图4。11对照） 由虚地址中的程序号指明哪个基址寄存器

根据基址寄存器的值和虚地址中的段号在该程序的段表找到相应的记录 根据段表的记录和虚地址中的偏移量在实主存空间找到物理地址

4）优缺点：优点是能使大程序分块编制、程序共用主存内的程序和数据、容易以段为单位实现存储保护；缺点是段表长增加辅助硬件开销和降低查表速度、造成大的段间零头浪费。

（三）段页式管理

1）思想：逻辑地址分段、段内分页；物理地址分块，块大小与页相同，逻辑页对应物理块

2）段表和页表：（与上面大致相同） 3）地址变换过程：（P93图。14）

根据虚地址用户标志U在段表基址寄存器中查到该程序的段表记录；

根据段表基址寄存器段表记录中的段表起点和虚地址中的段号找到多用户段表中对应的页表记录； 根据多用户段表中页表记录的页表起点和虚地址中的页号找到多用户页表中的对应记录； 根据多用户页表中对应记录的实页号和虚地址中的页内位移形成主存地址装入主存地址寄存器。 [例]P122习题4.5 4.3高速缓冲存储器 1.基本结构

将Cache和主存等分成大小相同的块，每当给出一个主存字地址进行访存时，都必须通过主存—Cache地址映像变换机构判定该访问字所在的块是否已在Cache中。如果在Cache中，主存地址经地址映像机构变换成Cache地址去访问Cache，Cache与处理机之间进行单字信息传送；如果不在Cache中，产生Cache块失效，这时将从访存的通路中把包含该字的一块信息通过多字宽通路调入Cache，同时，将被访问的字直接从单字通路送往处理机。如果Cache已装不进了，发生块冲突，就要按所选的替换块将该块替换进Cache，并修改地址映像表中的地址映像关系及Cache各块的使用状态标志等信息。

1）Cache的原理和虚拟存储器在原理上是类似的，所以虚拟存储器中使用的地址映象、变换及替换算法基本上也适用于Cache存储器，但由于对Cache的速度要求高，所以在构成、实现以及透明性等问题有其特点。

Cache—主存之间的地址映像和变换，以及替换、调度算法全得用专门的硬件来实现。这样，Cache存储器不仅对应用程序员是透明的，而且对系统程序员也是透明的。

Cache一旦发生失效，程序不能换道的，CPU只能停等着从主存中将所需的块调入物理Cache。 Cache存储器地址映像规则一般使用组相联或直接映像，不采用全相联映像。

处理机和Cache、主存的联系不同于虚拟存储器和主存、辅存之间的联系；主存和处理机之间设有直接通路，同时，Cache与处理机之间也设有直接通路。这样，发生块失效时，不是采用程序换道的方式，而是让Cache调块与处理机访主存重叠进行，这就是通过直接通路实现读直达；同样，也可以实现CPU直接写入主存的写直达。

2）为了更好地发挥Cache的高速性，用了以下方法：

流水进行查表变换和访Cache工作（流水概念下章介绍，现在的理解就是这两个步骤一起进行）； Cache的物理位置尽量靠近处理机或就放在处理机（我们现在微机的CPU中也有哦）； 让Cache调块与处理机访问主存字重叠进行； Cache访问主存的优先级尽量高 2.地址映像和变换 1）全相联映象和变换

映像规则：是主存中任意一块都可映像装入到Cache中任意一块位置(如图4.31)。 主存-Cache地址的变换：都采用目录表硬件方式实现。 地址变换过程：（如图4.31）给出主存地址

访存时，将其主存块号

与目录表中所有各项的

形成Cache

字段同时相联比较。若有相同的，就将对应行的Cache块号地址

取出，拼接上块内地址

,访Cache；若没有相同的，表示该主存块未装入Cache，发生Cache优点：块冲突概率最低，Cache的空间利用率最高。 缺点：要构成容量为2）直接映像

项的相联存储器，代价太大，且Cache容量很大时，查表速度很难提高。

映像规则：它把主存空间按Cache大小等分成区，每区内的各块只能按位置一一对应到Cache的相应块位置上。主存第i块只能惟一映像到第

变换过程：处理机给出主存地址时取

块位置上。

对应部分作为Cache地址访问Cache，同

访主存时，截取与

部分作为地址访问区号标志表存储器，读出原先所存区号与主存地址对应的区号部分相比较。若

比较相等时，表示Cache命中，让Cache的访问继续进行，并中止访主存；若比较不等，表示Cache块失效，此时让Cache的访问中止，而让主存的访问继续进行，并由硬件自动将主存中该块调入Cache。

表存储器：存放Cache每一块位置目前是被主存中哪个区的块所占用的区号。

优点：所需硬件省，只需容量较小的按地址访问的区号标志表存储器和少量的比较电路，成本很低。

直接映像的缺点：Cache的块冲突概率很高。只要有两个或两个以上经常使用的块恰好被映像到Cache同一块位置上，就会使Cache命中率急剧下降。

3）组相联映像及其变换

将Cache空间和主存空间都分成组，每组为S块(整个Cache是一区。主存分成与Cache同样大小的

)。Cache共有

个块，分成Q组(

)，

个区，其地址按区号、组号、组内块号、块内地

址分成对应的4个字段。主存地址的组号、组内块号分别用q、s′字段表示，它们的宽度和位置与Cache地址的q、s是一致的。组相联映像指的是各组之间是直接映像，而组内各块之间是全相联映像。

当组相联映象的S大到等于CACHE的块数时（即CACHE所有块为一组时）就成了全相联映象，当S小到1时就变成了直接映象。

优缺点：是界于全相联映像与直接映像之间的，Cache块冲突概率要比直接映像的低得多。成本比全相联映象多得多，性能接近于全相联映象。

组相联的地址变换原理：（如图4.36）先由q在找，若在上q和

组中选出一组，对该组再用nd+s′进行相联查

行中查不到相符的，表示主存该块不在Cache中；如果查到有相符的，则将表中相应的s拼就是Cache地址

。

[例]P124习题4.12 3. 替换算法的实现

Cache存储器块替换多采用LRU算法，具体的硬件实现方法可以有堆栈法和比较法两类。堆栈法用到相联访问功能的寄存器组设备量大，价格较贵，所以更多的是采用比较对法。

1）堆栈法

思想：设置一个容量等于Cache 总块数的堆栈，每次访问与堆栈内各块号比较，相符将此块号取出重新压栈，没有则将新访问块号压入栈顶，栈底出栈（全相联映象） 优缺点：成本高，用于组相联且组内块数少的LRU算法场合。

2）比较对法

思想：让各块成对组合，用一个触发器的状态表示该比较对内两块访问的远近次序，再经门电路就可找到LRU块。

优缺点：比较对触发器的个数会随块数的增多以极快的速度增加，实现困难，用于块数少的场合。

4. Cache存储器的透明性及性能分析 1）Cache存储器的透明性分析

解决问题：Cache和主存对应单元内容不一致； 解决方法：写回法和写直达法 2）Cache的取算法 恒取法和不命中预取法

2） 影响Cache存储器性能的因素

＠命中率是与块大小、块总数、采用组相联的组大小、替换算法和地址流的簇聚性有关。 ＠块大，不命中率总是下降趋势； ＠组大，不命中率总是下降趋势；

＠只要命中率有限，等效访问速度能提高的最大值也是有限。 Cache存储器的等效访问速度与命中率的关系。 设储周期：

为Cache的访问时间，

为主存周期，

为访Cache的命中率，则Cache存储器的等效存

其等效访问速度提高的倍数为：

[例]P124习题4.13

第5章 重叠、流水和向量流水处理机

5.1重叠方式

1.指令的顺序方式与重叠方式的解释

顺序解释：指的是各条指令之间顺序串行(执行完一条指令后才取下条指令)地进行，每条指令内部的各个微操作也顺序串行地进行。优点：控制简单，转入下条指令的时间易于控制。缺点：上一步操作未完成，下一步操作便不能开始，速度上不去，机器各部件的利用率低。

重叠解释：在解释第k条指令的操作完成之前，就开始解释第k+1条指令。重叠解释虽不能加快一条指令的解释，却能加快相邻两条以至整段程序的解释。

2.重叠方式对计算机组成的要求

为解决“取指k+1”与“分析k”在时间上重叠，可能产生访存冲突。可采用办法：第一种办法是让操作数和指令分别存放于两个独立编址且可同时访问的存储器中；第二种办法是仍维持指令和操作数混存，但采用多体交叉主存结构；第三种办法是增设采用先进先出方式工作的指令缓冲寄存器(简称指缓)。

为了实现 “执行k”与“分析k+1”重叠，还需要解决好几个问题：①硬件上还应有独立的指令分析部件和指令执行部件。②还需在硬件上解决控制上的同步问题，保证任何时候都只是“执行k”与“分析k+1”重叠。③还需要解决好控制上的转移问题。④控制上还要解决好邻近指令之间有可能出现的某种关联问题。

3.一次重叠方式的相关控制

·\"相关\"：邻近指令之间出现关联，为了防出错让它们不能同时解释的现象；数相关：该例子是在第k、k+1条指令的数据地址之间有了关联，称为发生了“数相关”。数相关不只是会发生在主存空间，还会发生在通用寄存器空间。指令相关：如果采用机器指令可修改的办法经第k条指令的执行来形成第k+1条指令的现象。

1）指令相关

指令相关的处理：禁止指令修改，还可另设置一条执行指令来解决程序设计灵活性。 2）主存空间数相关的处理：推后读

推后读是指若出现相邻两条指令之间出现对主存同一单元要求先写后读的关联 3)通用寄存器组相关的处理

通用寄存器组数相关的处理方法：推后\"分析k+1\"和设置\"相关专用通路\"，前面降低速度为代价，后者增加硬件成本为代价。

设置\"相关专用通路\"是指第K条指令的运算结果直接通有硬件专用通道回送到寄存器。

通用寄存器组基址值或变址值相关的处理：方法同上类拟，只不推后分析的推后时间不同及设置\"相关专用通路\"回写是到访存操作数地址形成机构。

5.2流水方式 1.流水是重叠的延伸

一次重叠:“分析k+1”与“执行k”的一次重叠是把指令的解释过程分解成“分析”与“执行”两个子过程，在独立的分析部件和执行部件上时间重叠地进行。指令由串行解释到一次重叠解释，机器的最大吞吐率提高了一倍。

流水：分为更多的m个子过程，可同时解释m条指令即让相邻的m条指令的解释在时间上重叠。如能把一条指令的解释分解成时间相等的m个子过程，则每隔Δt=T/m就可以处理一条指令。机器的最大吞吐率提高了m倍。

2.流水线的分类

⑴.依据向下扩展和向上扩展的思路，可分类出在计算机系统不同等级上使用的流水线。 向下扩展：指把子过程进一步地细分，让每个子过程经过的时间都同等程度地减少，吞吐率就会进一步提高。

向上扩展：流水的向上扩展可理解为在多个处理机之间流水，流水按处理的级别可分为部件级、处理机级和系统级。

⑵.从流水具有功能的多少来看，可以分为单功能流水线和多功能流水线。

⑶.按多功能流水线的各段能否允许同时用于多种不同功能连接流水，可把流水线分为静态流水线和动态流水线。

⑷从机器所具有的数据表示可以把流水线处理机分为标量流水机和向量流水机。

⑸.从流水线中各功能段之间是否有反馈回路，可把流水线分为线性流水和非线性流水。 3.流水线处理机的主要性能 1）吞吐率Tp和加速比Sp

吞吐率：流水线单位时间里能流出的任务数或结果数。最大吞吐率：

瓶颈子过程：流水线中经过时间最长的子过程；消除瓶颈：一种办法是将瓶颈子过程再细分。二种办法重复设置多套(如用三套)瓶颈段并联，让它们交叉并行。

实际吞吐率：设一m段流水线的各段经过时间均为Δt0，则第1条指令从流入到流出需要T0=mΔt0

的流水建立时间，之后每隔Δt0就可以流出一条指令。这样，完成n个任务的解释共需时间T=m·Δt0+(n-1)Δt0。在这段时间里，流水线的实际吞吐率：

加速比：如果用加速比Sp表示流水方式相对于非流水顺序方式速度提高的比值，那么非流水顺序方

式连续完成n个任务需要n×m×Δt0的时间，因此，流水方式工作的加速比：

2）效率

流水线的效率：是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。如果是线性流水线，且各段经过时间相同， 则在T时间里，流水线各段的效率都相同，均为η0，即

与吞吐率关系：η=TP·△t0

P5.3习题5.3类似题目：习题2、4、5、6类型 4. 流水线机器的相关处理

流水机器的相关由全局性相关和局部性相关两类。

全局性相关：转移指令与其后的指令之间存在关联，使之不能同时解释，还会使指令缓冲器所预取的指令全部作废，重新花较长的时间再去访存取指令。其造成的对流水机器的吞吐率和效率下降的影响要比指令相关、主存操作数相关和通用寄存器组相关及基址值或变址值相关严重的多，所以称为全局性相关。

局部性相关：是指指令相关、主存操作数相关和通用寄存器组相关及基址值或变址值相关，影响的是相关的两条或几条指令，最多影响流水线某些段工作的推后，不会改动指缓中预取到的指令，影响是局部的所以称为局部性相关。

1）局部性相关的处理

同步流动方式：一种是让任务(指令)流出流水线的顺序保持与流入流水线的顺序一致，称为顺序流动方式或同步流动方式。采用顺序流动方式的好处是控制比较简单，ASC机就采用这种方式。

异步流动方式：另一种是让流出流水线的任务(指令)顺序可以和流入流水线的顺序不同，称为异步流动方式。

异步流动方式带来的新的相关：\"写-写\"相关、\"先读后写\"相关、\"先写后读\"相关； 解决方法：推后后续指令和设置相关直接通路； 2）全局性相关的处理

猜测法：根据历史猜测出现概率大的分支装入指缓； 加快和提前形成条件码：不等指令执行完成提前形成条件码；

采取延迟转移：用软件方法将转移指令与其前面不相关的指令交换位置；

加快短循环程序的处理：将长度小于指缓的循环程序一次性放入指缓，并暂停预联指令或者循环出口端条件转移指令恒猜循环分支。

5.流水机器的中断处理

问题：在执行指令i时有中断，断点本应在指令i执行结束，指令i+1尚未开始执行的地方，但流水机器是同时解释多条指令， 指令i+1、 i+2…可能已进入流水线被部分解释。 对于异步流动流水线，这些指令中有些可能流到了指令i的前面去了。

解决办法：①采用“不精确断点”法。②采用“精确断点”法。 [例]P158习题8 6.流水线的调度

非线性流水线会出现多个任务争用同一功能段的使用冲突现象。预约表及流水线调度过程。解题步骤： ①根据预约表写出延迟禁止表F；②由延迟禁止表形成冲突向量C；③由所有的向量图画出状态图；④由状态图形成最佳调度方案。[例]P158习题5 .9。

5.3向量的流水处理与向量流水处理机 1.向量的流水处理

横向（水平）处理方式：逐个求结果向量的各个元素会引起流水线功能段的频繁切换以及发生大量的先写后读的操作数相关，不适合流水处理。

纵向（垂直）处理方式：避免了功能段的频繁切换以及发生大量的先写后读的操作数相关，适合流水处理。

分组纵横处理方式：可以减轻对向量长度N的限制，以便用面向寄存器-寄存器型的结构流水。 CRAY-1,将长向量按向量寄存器组中寄存器的个数分组，组内按纵向方处理，组间采用软件的方法编制向量循环程序来横向处理。

2.向量流水处理机（以CRAY-1为例）

1）组成：P150

2）流水线单功能部件：P151 3）向量寄存器：P151

4）Vi冲突：并行工作的各向量指令的源向量或结果向量使用相同的Vi；

5）功能部件冲突：同一功能部件被要求并行工作的多条向量指令所使用； 6）四个向量指令（P152图5。29）

7）通过链接技术实现向量指令之间大部分时间并行（以D=A*（B+C）为例）

掌握根据P152三条向量指令画出图P153图5.30的方法，注意两个条件，一是向量长度限制，二是Vi冲突的解决方法。

[例]P158习题5.10

5.4指令级高度并行的超级处理机

超标量处理机（资源重复）：配置多套部件，按组（一组m条指令）执行指令；

超长指令字（VLIW）处理机：编译程序找出指令间潜在并行性，将多个能并行执行的指令或无关操作先行压缩组合在一起，形成一条多个操作段的超长指令。

超流水线处理机（时间并行性）：在公共硬件上采用较短时钟周期，深度流水来提高速度，提高每个部件的利用率。

第6章 阵列处理机

阵列处理机（并行处理机）：将大量重复设置的处理单元PE按一定的方式互联成阵列，在单一控制部件CU控制下对各自所分配的不同数据并行执行同一指令规定的操作，是操作级并行的SIMD计算机。主要用于大量向量、数组要求高速运算场合。

6.1阵列处理机原理 1.阵列处理机基本构型

由于存储器的组成方式不同，阵列处理机有两种不同的基本构型：分布式存储器的阵列处理机和集中式共享存储器的阵列处理机。

1）分布式存储器的阵列处理机

控制部件CU:整个系统在CU控制下运行用户程序和部分系统程序的。所有指令都在控制部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件CU自己执行.

各处理单元:有局部存储器PEM存放被分布的数据。把适合并行处理的向量类指令“播送”给各个PE，控制那些活跃的PE并行执行。

互连网络(ICN):运算中，PE间可通过互连网络(ICN)来交换数据。互连网络的连通路径选择也由控制部件统一控制。

管理处理机SC:是一种通用机，用于管理系统资源，完成系统维护、输入/输出、用户程序的汇编及向量化编译、作业调度、存储分配、设备管理、文件管理等操作的功能。

阵列处理机是SIMD的主流。典型机器有ILLIACⅣ、MPP、DAP、CM-2、MP-1、DAP600系列等。 2）集中式共享存储器的阵列处理机

系统存储器是由K个存储分体集中组成，经互连网络ICN为全部N个处理单元所共享。

不同点;①互联网络所起作用不同；②信息在存储器中分布的要求不同。相同点：CU和SC功能相同。 互连网络的作用：用于在处理单元与存储器分体之间进行转接构成数据通路，希望各处理单元能高速灵活地动态与不同的存储分体相连，使尽可能多的PE能无冲突地访问共享的主存模块。

采用这种构形的典型机器有BSP。 2.阵列处理机的特点

①阵列处理机提高速度是利用资源重复，利用并行性中的同时性； ②处理单元同等地担负起各种运算，其设备利用率可能不那么高； ③速度提高在硬件价格大幅度下降情况下，潜力巨大； ④互连网络对系统性能影响显著；

⑤互连网络使阵列处理机比固定结构的单功能流水线灵活； ⑥阵列处理机结构和所采用并行算法紧密联系； ⑦阵列处理机还必须提高标量处理速度。 6.2 阵列处理机的并行算法 1.ILLIACⅣ的处理单元阵列结构

ILLIACⅣ是采用分布存储器构形。其中，PUi为处理部件，包含64位的算术处理单元PEi、所带的局部存储器PEMi和存储逻辑部件MLU。64个处理部件PU0～PU63排列成8×8的方阵，任何一个PUi只与其上、下、左、右4个近邻PUi-8、PUi+8、PUi-1和PUi+1直接相连。上下同一列两端的PU连成环，左右每一行右端的PU与下一行左端的PU相连，最下面一行右端的PU与最上面一行左端的PU相连，从而形成一个闭合的螺线形状，所以称其为闭合螺线阵列。普遍来讲，中，任意两个处理单元之间的最短距离不超过

步。

个处理单元组成的阵列

ILLIACⅣ的处理单元是累加器型运算器，把累加寄存器RGA中的数据和存储器中来的数据进行运算，结果保留在累加寄存器RGA中。每个处理单元内有一个数据传送寄存器RGR收发数据，实现数据在处理单元之间的传送，并有一个屏蔽触发器，用来控制让该PUi是否被屏蔽掉，使之不参与向量指令的操作。

6.3 SIMD计算机的互连网络 1.互连网络的设计目标与互连函数

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

2)问题：在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结

①操作方式：有同步、异步及同步与异步组合三种。现有的阵列处理机均采用同步操作方式，让所有PE

②控制策略：可以有集中或分布两种控制策略。多数现有的SIMD互连网络采用集中控制的策略。

③交换方法：主要有线路交换、包交换及线路与包交换组合三种。线路交换是在源和目的间建立实际的连接通路，一般适合于大批数据传输。包交换是将数据置于包内传送，不用建立实际的连接通路，对短数据信息传送特别有效。SIMD互连网络多采用硬连的线路交换，包交换则多用于多处理机和计算机网络中。

④网络的拓扑结构：有静态和动态两种。在静态拓扑结构中，两个PE之间的链是固定的，总线不能重新配置成与其他PE相连。而动态拓扑结构中，两个PE之间的链通过置定网络的开关单元状态可以重新配置。动态网络有单级和多级两类。

3) 互连函数：互联网络的连接规律可以用互联函数来表示，它反映了对于所有的入端0、1、…、j、…、N-1，同时存在入端j连至出端f(j)的函数对应关系。

2.基本的单级互连网络

基本的单级互连网络有立方体、PM2I、混洗交换网络3种。 1）立方体单级网络

连接规律：是在一个N维的立方体中所有各顶点之间边的连接规律；N个结点的立方体单级网络共有n=log2N种互连函数，即

单级立方体网络的最大距离为n，即反复使用单级网络，最多经n次传送就可以实现任意一对入、出端间的连接。

2）PM2I单级网络

PM2I单级网络是“加减2i”单级网络的简称。能实现与j号处理单元直接相连的是号为j±2i的处理单

元，即 式中，0≤j≤N-1,0≤i≤n-1,。它共有2n个互连函

数。由于PM2+(n-1)=PM2-(n-1),因此PM2I互连网络只有2n-1种互连函数是不同的。

PM2I单级网络最大距离为上取整[n/2]，最多只要两次使用，即可实现任意一对入、出端号之间的联接。

3）混洗交换单级网络

混洗交换单级网络包含两个互连函数，一个是全混，另一个是交换。N维全混互连函数表示为 ：

，式中,

为入端编号的二进

制码。由于单纯的全混互连网络不能实现二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数。这就是全混交换单级网络，

数据传送最多只需n次交换和n-1次混洗传送即可，其最大距离为2n-1。 3.基本的多级互连网络

最基本的多级互连网络就是由3种单级互连网络相对应组成的多级立方体互连网络、多级混洗交换网络、多级PM2I网络以及全排列网络。不同的多级互联网络，在所用的交换开关、拓扑结构和控制方式上各有不同。

1）多级立方体网络

多级立方体网络有STARAN网络、间接二进制n方体网络等。特点：交换开关用二功能，拓扑结构用立方体，控制方式可以有级控制、部分级控制和单元控制。

采用级控制方式的多级立方体网络称交换网络，它只能实现交换函数的功能。

采用部分级控制方式的多级立方体网络称移数网络；采用单元控制方式的多级立方体网络称间接二进制n方体网络。

2）多级混洗交换网络

多级混洗交换网络（omega网络），特点：交换开关用四功能的，拓扑结构为混洗，控制方式为单元控制。

3）多级PM2I网络

多级PM2I网络（数据变换网络），N个端子经n级连接，从入端到出端的级编号依次为n-1、n-2、。。。、1、0.每一级均把前后两列各N个单元以PM2I的拓扑互连。每一级控制信号有平控H、下控D和上控U信号分别控制这三类连接线。

若采用单元控制方式则称为强化数据变换网络ADM. 可以实现omega网络的全部连接，而且其组合数还要更多。

小结：这几种多级网络，灵活性由低到高的次序是：级控制立方体、部分级控制立方体、间接二进制n方体、omega、ADM,而复杂性和成本的次序也相应增高。

4）全排列网络

互连网络是从N个入端到N个出端的一到一的映射，即对N个端的重新排列。互连网络的功能是用新排列来置换N个入端原有的排列。

阻塞式网络：前几种基本多级网络都能实现任意一个入端与任意一个出端间的连接，但要同时实现两对或多对入、出端间的连接时，都有可能发生争用数据传送路径的冲突。

非阻塞式网络（全排列网络）：前几种基本多级网络都能实现任意一个入端与任意一个出端间的连接，能同时实现两对或多对入、出端间的连接时，没有发生争用数据传送路径的冲突网络。非阻塞式网络连接灵活，但连线多、控制复杂、成本高。

N个端的全部排列有N!种。可是，用单元控制的个开关，n级互连网络共用为2种排列。

级间接二进制n方体网络，每级有N/2

个二功能的交换开关，这样，全部开关处于不同状态的总数

即NN/2种。当N为大于2的整数时，总有NN/2＜N!，就是说它无法实现所有N!

实现的方法：一种方法根据循环多级互连网络的实现思路。只要对这个多级互连网络通行两次，此时全部开关的总状态数有NN/2·NN/2= NN种，足以满足N!种不同排列的开关状态要求。第二种方法将级的N个入端和N个出端的互连网络和它的逆网络连在一起，这样可以省去中间完全重复的一级，得到总级数为

级的全排列网络。

6.4并行存储器的无冲突访问

阵列处理机：为了存储器频宽要与多个处理单元的速率匹配，要求存储器采用多体并行组成；还要保证对数组访问的模式，存储器都能实现无冲突地访问工作。

对数组访问的模式：可能要访问数组的行、列、主对角线、次对角线的全部元素或其中某个子方阵。 1）一维数组的存储访问分析

问题：若遇到按2变址，访问奇数或偶数下标的元素时，则因访存冲突会使存储器的实际频宽降低一半。

解决办法：并行存储的分体数m应取成质(素)数，才能较好地避免存储器访问的冲突。只要变址跳距与m互质，存储器访问就总能无冲突地进行。

2）多维数组（二维数组）存储访问分析

①解决办法一：为了能使行或列的各元素都能并行访问，采取将数据在存储器中错位存放。但是该方案可造成主对角线上各元素的并行访问冲突，致使实际频宽下降一半，次对角线上各元素的访问则都发生冲突，使实际频宽降低成与串行一样。

②解决办法二：能满足上述这些要求的一种存储方案是使并行存储器分体数m大于每次要访问的向量或数组元素的个数n(n在阵列处理机上就是处理单元数)，且等于质数，同时在多维数组的行、列等方向上采取不同的错开距离。

同一列两个相邻元素地址错开的距离为

,同一行两个相邻元素地址错开的距离为

,

,当m取成

(P为正整数)时，实现无冲突访问的充分条件是让=1。对于这种无冲突访问的存储

方案，要求n×n二维数组A中的任意一个元素Aab应放在下列地址处：

③解决办法三：有n个处理单元的并行处理机，为了能并行访问n个元素，且适应任意规模的数组，可以先将多维数组或者非n×n方阵的二维数组按行或列的顺序变换为一维数组，形成一个一维线性地址空间，地址用a表示。然后，将地址a所对应的元素存放在体号地址n］下取整的单元中，就可以满足无冲突访问的要求。

BSP计算机就是采用类似这种映像规则存放的。它共有16个处理单元，选取的并行存储器分体数m为17。

,体内地址为i=INT［a/

第7章 多处理机

多处理机：是指有两台以上的处理机，共享I/O子系统，机间经共享主存或高速通信网络通信，在操作系统控制下，协同求解大而复杂问题的计算机系统。有同构型、异构型和分布型三种。

两个目的：①通过多台处理机对多个作业、任务进行并行执行来提高求解大而复杂问题的速度。②使用冗余的多个处理机，通过重新组织来提高系统的可靠性、适应性和可用性。

7.1多处理机的特点及主要技术问题

1.多处理机的基本特点：多处理机是属于多指令流多数据流(MIMD)的系统。多处理机则实现的是更高一级的作业或任务间的并行，是开发并行性中的并发性。结构上多个处理机用多个指令部件分别控制,通过机间互连网络通讯;算法上不只限于处理向量数组,还要实现更多通用算法中的并行;系统管理上要更多地依靠软件手段,有效解决资源分配和管理,特别是任务分配,处理机调度,进程的同步和通讯等问题.

2.多处理机与阵列处理机的差别

①结构灵活性。多处理机制结构灵活性高于并行处理机。

②程序并行性。并行处理机是操作级并行，并行性仅存在于指令内部，识别比较容易，由程序员掌握程序并行性的开发;多处理是指令、任务、作业并行，并行性主要存在于指令外部，另外还存在于指令内部，识别比较困难，必须利用多种途径开发程序的并行性。

③并行任务派生。并行处理机工作能否并行工作由指令决定，多处理机必须有专门指令指明程序能否并行执行，派生的任务数是动态变化的。

④进程同步。并行处理机的进程同步是自然的，而多处理机不一定必须采取同步措施。 ⑤资源分配和任务调度。多处理机的资源分配和任务调度比并行处理机复杂得多。 ⒊多处理机存在如下主要技术问题

①硬件结构上，如何解决好处理机、存储器模块及I/O子系统间的互连； ②如何最大限度的开发系统的并行性，以实现多处理机各级的全面并行； ③如何选择任务和子任务的大小，即任务的粒度，使并行度高，辅助开销小； ④如何协调好多处理机中各并行执行的任务和进程间的同步问题；

⑤如何将任务分配到多处理机上，解决好处理机调度、任务调度和资源分配，防止死锁； ⑥一旦某个处理机发生故障，如何对系统进行组织，不使其瘫痪；

⑦多处理机机数增多后，如何能给编程者提供良好的编程环境，减轻程序的复杂性。 7.2多处理机的硬件结构 1 紧耦合和松耦合

1）紧耦合多处理机是通过共享主存实现处理机间通信的；为减少访主存冲突，主存采用模m多体交叉存取；存储器模块数m应等于或略大于处理机数p。要解决好数据在各存储器模块中的分配和定位。各处理机可自带小容量局部存储器和再自带高速缓冲存储器Cache，可以减少处理机-存储器互连网络的使用冲突。

系统由P台处理机、m个存储器模块和d个I/O通道组成。通过处理机—存储器互连网络（PMIN）、I/O—处理机互连网络（IOPIN）和中断信号互连网络（ISIN）进行互连。

处理机-存储器互连网络：实现各处理机与各存储器模块的连接，存储器模块数m应等于或略大于处理机数p。

I/O-处理机互连网络：它来实现处理机和连接外设的I/O通道经通信。

中断信号互连网络：由一台处理机向另一台处理机发出中断信号来实现处理机间的进程同步。 紧耦合多处理机常用于并行执行作业中的多个任务，以提高系统的速度性能；即各处理机一般常采用同构对称型（即系统是多个同类型至少功能相同的处理机组成）的紧耦合多处理机。

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

非层次松耦合多处理机：典型的经消息传送系统互连的松耦合非层次型多处理机。该系统有N个计算机模块。每个计算机模块中有处理器CPU、Cache、局部存储器LM和一组I/O设备。还有一个通道和仲裁开关CAS与消息传送系统MTS接口，对两个或多个计算机模块同时请求访问MTS的某个物理段时进行仲裁。

是层次型总线式多处理机。

层次型松耦合多处理机：卡内基-梅隆大学设计的松耦合多处理机2. 机间互连形式

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

总线形式：处理机与外部存储器模块通过总线相连。结构简单、成本低、扩展性好；但总线失效敏感，存在总线争用。适合处理机较少、系统信息流量少、机数可扩充情况。

环形互连：各处理机点点相加成环。结构简单、成本低、不争用总线；但信息传输有延迟。适合处理机较少、使用高宽带的光纤通信、系统流量高、机数可扩充的情况。

交叉开关：用纵横开关阵列将存储器模块、I/O通道相连。不争用开关；但开关阵列复杂，设备量较大。适合处理机数较多（但不超过16）、系统流量大、处理机数可扩充的情况。

多端口存储器：将交叉开关移到存储器接口中。不争用总线，但存储器接口复杂，较难控制。适合处理机数少、不能扩充（一般是2台），系统流量高的情况。

开关枢纽结构：把交叉开关设置在各处理机或接口内部。所有开关枢纽数量少，可用较短路径与处理机连接；但开关枢纽较复杂。适合处理机数多、可扩充、分布结构情况。

7.3多处理机的并行性

多处理机并行性既存在于指令内部，也存在于指令外部；多处理机低层次的并行可通过向量化来实现，如利用面向SIMD的并行算法解决向量数组的并行运算。系统高层次的任务和作业的并行性主要靠算法、编译、语言及操作系统来开发。

1并行算法

并行算法的研究思路：将大的程序分解成可由足够多的并行处理的过程(进程、任务、程序段)。每个过程被看成是一个结点，将过程之间的关联关系用结点组成的树来描述。这样，程序内各过程之间的关系就可被当成是一种算术表达式中各项之间的运算，表达式中的每一项都可看成是一个程序段的运行结果。因此，研究程序段之间的并行问题就可设想成是对算术表达式如何并行运算的问题。

并行算法的性能：用P表示可并行处理的处理机机数；用TP表示P台处理机运算的级数即树高；加速比SP表示单处理机顺序运算的级数T1与P台处理机并行运算的级数TP之比； EP表示P台处理机的设备利用率(效率)，EP= SP/P。SP≥1时，会使EP ≤1，即运算的加速总是伴随着效率的下降。

串行处理机习惯采用循环和迭代算法

多处理机并行算法实现（1）：应尽可能增大树中每一层的结点数，即增大树的广度，使各处理机可并行的过程数尽可能增大，以降低树的高度。当最大限度降低了树的高度之后，就应再缩小树的广度，使之在达到一定的加速比SP 之后如何减少机数P来减少多处理机效率的降低。

具体实现：先从算术表达式的最直接形式出发，利用交换律把相同的运算集中在一起。然后再利用结合律和分配律把参加这些运算的操作数配对，尽可能并行运算，从而组成树高为最小的子树。最后再把这些子树结合起来。

2. 程序并行

①数据相关（先写后读）：如果Pi的左部变量在Pj的右部变量集内，且Pj必须取出Pi运算的结果来作为操作数，就称Pj“数据相关”于Pi 。不能并行和交换串行，只在特殊情况下可以交换串行。

②数据反相关（先读后写）：如果Pj 的左部变量在Pi 的右部变量集内，且当Pi 未取用其变量的值之前，是不允被Pj 所改变的，就称Pi “数据反相关”于Pj。可以并行执行，但必须保证其写入共享主存时的先读后写次序，不能交换串行。

③数据输出相关（写-写）：如果Pi 的左部变量也是Pj 的左部变量，且Pj 存入其算得的值必须在P

i

存入之后，则称Pj “数据输出相关”于Pi 。可以并行执行，但同样需保证其写入的先后次序，不能交

换串行。

若同时有先写后读和先读后写两种相关，以交换数据为目的时，则必须并行执行，且要求读写完全同步，不许顺序串行和交换串行；若没有任何相关，或仅有源数据相同时， 可以并行、 顺序串行和交换串行。

3 并行程序设计语言

基本要求：能使程序员在其程序中灵活方便的表示出各类并行性，能在各种并行/向量计算机系统中高效地实现。

并行进程的特点：这些进程在时间重叠地执行，一个进程未结束，另一个进程就开始。 并行任务的派生：使一个任务在执行的同时，派生出可与它并行执行的其它一个或多个任务，分配给不同的处理机完成。

并行任务的汇合：被派生的任务，可以相同的，也可以是不同的，执行时间可以相同，也可以不同，等它们全部完成后，再汇合起来进行后续的单任务或新的并行任务。

FORK语句：执行一个FORK m语句时，派生出标号为m开始的新进程， 具体来说，就是准备好这个新进程启动和继续执行所必需的有关信息；如果是共享主存，则应为它产生存贮器指针、映象函数和访问权数据；将空闲的处理机分配给被FORK语句派生的新进程，如果没有可用的空闲处理机，则应让它们排队等待； 继续在原分配给它的处理机上执行FORK

JOIN语句：JOIN语句附有一个计数器，其初始值置为0。每当执行JOIN n语句时，计数器的值加 1，并与n比较。若比较相等，表明这是执行中的第n个并发进程经过JOIN语句，于是允许该进程通过JOIN语句， 将计数器清0，在其所在的处理机上继续执行后续语句。若比较结果，计数器的值仍小于n， 则表明此进程不是并发进程中的最后一个，可让现在执行JOIN语句的这个进程先结束，把它所占用的处理机释放出来，分配给正在排队等待的其他任务。如没有排队等待的任务，则让该处理机空闲。

4．多处理机的性能

任务粒度的大小，会显著影响多处理机的性能和效率；任务粒度过小，辅助开销大，系统效率

低；粒度过大，并行度低，性能不会很高。因此，要合理选择任务粒度的大小，并使其尽可能的均匀，还要采取措施减少辅助开销，以保证系统性能随处理机数目的增大有较大的提高。

衡量任务粒度大小的一个依据是程序用于有效计算的执行时间E与处理机间的通信等辅助开销时间C的比值。只有E/C的值较大时， 开发并行性才能得到好处。

任务粒度还与系统的应用有关。图像及多目标跟踪因为机间通信开销少，宜于细粒度处理。要求冗长计算才能得到结果的题目，宜于粗粒度处理.

7.4多处理机的操作系统

多处理机操作系统有主从型、各自独立型及浮动型三种类型。

类型 构型 优点 缺点 适用工作负主从型 管理程序只在一台指定的处理上运行 硬件结构简单，控制简单 对主机的可靠性要求高，灵活性差 从处理明显低控制功能分散到多台处理机，共同完成对整适应分布处理的模块尽管每台处理机都有专用表格，但一些共享个系统的控制。每台处理机都有一个独立的化结构，对主机依赖性表格会增加共享冲突，加大了开销。实现复松耦合各自独立型 管理程序(操作系统的内核)在运行。要求管小，可靠性高，系统效杂，输入输出结构变换需要人为干预，处理系统 理程序必须是可再入的。 率较高 集中了主从型和各自浮动型 管理程序在处理机间浮动 独立型的优点，且灵活性高 设计最困难 机间负荷的平衡比较困难 紧耦合系统，理机第8章 其它计算机结构

8.1脉动阵列处理机

8.1.1脉动阵列结构的原理

脉动阵列结构是由一组处理单元PE构成的阵列。每个PE的内部结构相同，一般由一个加法/逻辑运算部件或加法/乘法运算部件再加上若干个锁存器构成，可完成少数基本的算术逻辑运算操作。阵列内所有处理单元的数据锁存器都受同一个时钟控制。运算时数据在阵列结构的各个处理单元间沿各自的方向同步向前推进，阵列内部的各个单元只接收前一组处理单元传来的数据，并向后一组处理单元发送数据。只有位于阵列边缘的处理单元，才与存储器或I/O端口进行数据通信。

根据具体计算的问题不同，脉动阵列可以有一维线形、二维矩形/六边形/二叉树形/三角形等阵列互连构形。

脉动阵列结构具有如下一些特点： ①结构简单、规整，模

②PE间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均简单规整。

③脉动阵列中所有PE能同时运算，具有极高的计算并行性，可通过流水获得很高的运算效率和吞吐率。

④输入数据被多个处理单元重复使用，减轻阵列与外界I/O通信量，降低系统对主存和I/O系统频宽的要求。

⑤脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI是不利的。

8.1.2通用脉动阵列结构

发展通用脉动阵列结构的途径主要有三种。

①通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序重新配置阵列的结构。

②用软件把不同的算法映像到固定的阵列结构上。这一方法依赖于面向并行运算所采用的程序语言、操作系统、编译程序和软件开发工具的设计。

③探寻与问题大小无关的脉动处理方法，以及VLSI运算系统的分割矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相应的设置方案。

8.2大规模并行处理机MPP与机群系统

8.2.1 大规模并行处理机MPP

发展背景：由于VLSI和微处理技术的发展，以及高科技应用领域对计算机和通信网络在计算、处

理和通信性能上不断提出更高的要求(极大的处理数据量、异常复杂的运算、很不规则的数据结构、极高的处理速度),使发展大规模的并行处理成了20世纪80年代中期计算机发展的热点。

大规模并行处理机：通过新的计算方法、存储技术、处理手段和结构组织方式，将数百至数千个高性能、低成本的RISC微处理器用专门的互连网络互连，组成大规模并行处理机MPP。这种处理机可进行中粒度和细粒度大规模并行处理，构成SIMD或MIMD系统。

优点：它具有性能价格比高和可扩展性好的优点。 8.2.2

机群系统是将多个高性能的工作站或高档微型计算机，使用高速的通信网络加以互连组成的系统。

实现对中、粗粒度并行进程的高效并行处理。机群系统中的主机和网络可以是同构的，也可以是异构的。主机间的通信主要采用消息传递。从结构和结点间的通信来看，是一种分布式存储方式，而从用户来看，表示出的是一个完整的并行系统。

机群系统如下几个明显的优点： ①系统有高的性能价格比。 ②系统的开发周期短。 ③系统的可扩展性好。

④系统的资源利用率高。 ⑤用户投资风险小。 ⑥用户编程方便。

8.3 数据流计算机

8.3.1数据驱动的概念

计数器控制驱动的控制流方式：它是VonNeumann型计算机的基本特点；在程序计数器集中控制下，顺次地执行指令，是以控制流方式工作。

特点：通过访问共享存储单元让数据在指令之间传递；指令执行的顺序性隐含于控制流中，但却可以显示使用专门的控制操作符来实现并行处理；指令执行的顺序受程序计数器控制，即是受控制令牌所支配。

数据驱动的数据流方式：只要一条或一组指令所要求的操作数全部准备就绪，就可立即激发相应的指令或指令组执行；执行结果的输出将送往等待这一数据的下一条或下一组指令。指令的执行基本上是无序的，完全受数据流的驱动，与指令在程序中出现的先后顺序无关。

特点：没有通常的共享变量的概念，即没有共享存储数据的概念；指令执行顺序只受指令中数据相关性的制约；数据是以数据令牌方式直接在指令之间传递的。

需求驱动的数据流方式：数据驱动计算，其操作是按输入数据可用性决定的次序进行；需求驱动计算，其操作则按数据需求所决定的次序进行。前者只要所要求的输入数据全部就绪，即可驱动操作执行，是一种提前求值的策略；而后者则是按需求值，只有当某一函数需要用到某一自变量时，才驱动对该自变量的求值操作，是一种滞后求值的策略。

从语义上讲，数据流是基于异步性和函数性的一种计算模型。 8.1.2数据流程序图和语言⒈数据流程序图

有向图来表示指令级的数据流程序，它可看成是数据流机器的机器语言。它有多个结点，并用一些弧把它们连接而成。每一个结点用圆圈或三角形或其他特殊符号表示，认为是一种处理部件，结点内的符号或字母表示一种操作。弧代表数据令牌在结点间的流向。

为了满足数据流机程序设计的需要，还需进一步引入许多常用的其它结点。这些结点可分别表示

利用上述这些结点，可以画出一些常见程序结构的数据流程序图。 P223 8.4解：

⒉.活动模片表示法

活动模片表示法：数据流实际上可以被看成是一组活动模片组成的集合体。每一个活动模片相应于数据流程序图中一个或多个操作结点，且由4个域组成。它们是一个操作码域，两个操作数域和一个目的域。

目前数据流控制机制的高级语言主要有单赋值语言和函数程序设计语言。另外，逻辑程序设计语言PROLOG这样一类的描述式语言，也可作为数据流机的高级语言。

8.3.3数据流计算机的结构

（1）静态数据流机的数据令牌无标号。动态数据流机的数据令牌有标号；

（2）静态数据流任意给定时刻当结点操作时每条弧上只能有一个数据令牌、动态数据流机中，任何一条弧上可出现多个不带目标号的数据令牌；

（3）静态数据流机中必须设控制令牌以满足要求，动态数据流机中不必须投控制令牌，因为令牌有识别时间、先后关系的标号；

（4）静态数据流机不支持递归的并发激活，只支持一般循环，动态数据流机支持递归的并发激活； （5）静态数据流机不需硬件完成标记的匹配，动态数据流机需要硬件将标记附加在数据令牌上，并完成对标记的匹配工作。

8.3.4数据流机器存在的问题

数据流计算机在提高并行处理效能上有着非常显著的长处，但也存在一些问题。

(1)数据流机是操作级上并行，但如果题目本身数据相关性很强，会使效率比传统的VonNeumann型机的还要低。

(2)数据流机中给数据建立、识别、处理标记，花费较多的辅助开销和存储空间。 (3)数据流机不保存数组。

(4)数据流语言的变量代表数值而不是存储单元位置，使程序员无法控制存储分配。 (5)数据流机互连网络设计困难，输入/输出系统仍不够完善。 (6)数据流机没有程序计数器，给诊断和维护带来了困难。

8.4 归约机

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

函数式语言：是由所有函数表达式的集合、所有目标(也是表达式)的集合及所有由函数表达式到目标的函数集合三部分组成的。

归约：如果给出了一个属函数表达式集合中的复杂函数的表达式，利用提供的函数集合中的子函数经过有限次归约代换之后，总可以得到所希望的结果，即由常量构成的目标。函数表达式的每一次归约，就是一次函数的应用，或是一个子表达式(子函数式)的代换(还原)。

归约机：针对函数程序设计语言的特点和问题来设计支持函数式程序运行的新计算机（归约机）。函数式程序本质上是属于解释执行方式，从函数式程序的归约来看，机器内部通常采用链表的存储结构，且依赖于动态存储分配，存储空间的大小无法预测，需要频繁地进行空白单元的回收，使空间、时间开销都较大，频繁的函数应用和参数传递，加上自变量动态取值，同样的计算往往要重复多次。

(1)归约机应当是面向函数式语言，或以函数式语言为机器语言的非Neumann型机器。

(2)具有大容量物理存储器和虚拟存储器，具备高效的动态存储分配和管理的软、硬件支持，满足归约机对动态存储分配及所需存储空间大的要求。

(3)处理部分应当是一种有多个处理器或多个处理机并行的结构形式，以发挥函数式程序并行处理的特长。

(4)采用适合函数式程序运行的多处理器互连的结构，最好采用树形的互连结构或多层次复合的互连结构形式。

(5)为减少进程调度及进程间通信开销，尽量把运行进程的结点机安排成紧靠该进程所需用的数据，并使运行时需相互通信的进程所占用的处理机也靠近，让各处理机的负荷平衡。

根据机器内部对函数表达式所用存储方式的不同，将归约方式分成串归约和图归约两类。 根据机器所用归约方式的不同，相应就有串归约机和图归约机两类。1979年，美国的Mago教授提出的细胞归约机FFP就是一种串归约机。墨西哥国立大学的Guzman等人提出的并行LISP机，就是图归约机。

8.5 智能机

智能机是具有智能的高性能计算机.它是一个知识信息的处理系统.智能机能不断地学习,积累,完善知识,利用知识进行推理,判断和求解问题的能力.它具有大容量的知识库；具有高度并行处理,多重处理和分布处理能力的多个处理机,是一种结构动态可变,易于扩充的开放式系统；提供有良好的人-机界面和多种智能接口。智能机中3个重要的组成部分是知识库机,推理机和智能接口处理机.

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

1.1计算机系统的多级层次结构

1.从使用语言的角度，可以将系统看成是按功能划分的多个机器级组成的层次结构，由高到低分别为应用语言机器级、高级语言机器级、汇编语言机器级、 操作系统机器级、传统机器语言机器级和微程序机器级。

2.各机器级的实现方法：翻译（变换成低一级等效程序）或解释（仿真高级机器级语句或指令） 3.通过多层次结构的观点可以得出，软件的功能可以由硬件实现，硬件的功能也可用软件模拟实现。

1.2计算机系统结构、组成与实现

1. 透明：客观存在的事物或属性从某个角度看不到的。

2. 计算机系统结构指的是传统机器级的系统结构；它是软、硬件之间的功能分配以及对传

统机器级界面的确定，提供机器语言、汇编语言程序设计者或编译程序生成系统为使其设计或生成的程序能在机器上正确运行应看到和遵循的计算机属性。数据表示、寻址方式、寄存器组织、指令系统、存储系统组织、中断系统、管态目态定义与转换、IO结构、保护方式和机构。

2. 计算机组成：是计算机系统结构的逻辑实现，包括机器级内的数据流和控制流的组成及逻辑设计

等。它着眼于机器级内的各事件的排序方式与控制机构、各部件的功能及各部件间的联系。近40年里，计算机组成设计主要围绕提高速度，着重从提高操作的并行度、重叠度、以及功能的分散和设置专用功能部件来设计的。

(1)数据通路宽度；(2)专用部件的设置；(3)各种操作对部件的共享程度；(4)功能部件的并行度；(5)控制机构的组成方式；(6)缓冲和排队技术； (7)预估、预判技术； (8)可靠性技术。

3.计算机实现：指的是计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，器件、模块、插件、底板的划分与连接，专用器件的设计，微组装技术，信号传输，电源、冷却及整机装配技术等。它着眼于器件技术和微组装技术，其中，器件技术在实现技术中起着主导作用。

4. 计算机系统结构、组成、实现三者互不相同，但又相互影响。

①相同结构(如指令系统相同)的计算机，可以因速度不同而采用不同的组成；相同组成可有多种不同的实现方法。②系统结构不同会使可能采用的组成技术不同。反过来，组成也会影响结构。③组成设计上面决定于结构，下面受限于实现技术，它们是可以与实现折衷权衡的。组成和实现的权衡取决于器件的来源、厂家的技术特长和性能价格比能否优化。

1.3软硬件取舍与计算机系统设计思路

1. 软硬件实现的优缺点：解题速度、程序存储空间、硬件成本、硬件利用率、计算机系统的灵活性和适应性。

2. 软、硬件取舍的基本原则

确定软、硬件功能分配比例的第一个基本原则是应考虑在现有硬、器件(主要是逻辑器件和存储器件)条件下，系统要有高的性能价格比，主要从实现费用、速度和其他性能要求来综合考虑。

确定软、硬件功能分配的第二个基本原则是，要考虑到准备采用和可能采用的组成技术，使它尽可能的不要过多或不合理的限制各种组成、实现技术的采用。

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

3. 计算机系统的设计思路

＠\"由上往下\"设计思路：从考虑如何满足应用要求，定好面对使用者那级机器应有什么基本功能和特性，逐级往下设计，每级都考虑怎样优化上一级实现，这样设计的计算机系统对于设计时面向的应用必然是很好的。缺点①是应用的改变会带来系统效率的急剧下降；②适用于专用机设计，不适用于通用机的设计。

＠\"由下往上\"设计思路：不管应用的要求，只根据已有器件和硬件的状况，先设计微程序机器级，先设计出微程序机器级（如果采用微程序控制）及传统机器级，然后再为不同应用配多种操作系统和编译软件，使应用人员可根据所提供的语言种类、数据形式，采用合适的算法来满足相应的应用。这是常用的通用机设计思路缺点是①造成软硬件脱节，软件设计复杂；

＠\"由中间开始\"设计思路：\"中间\"指的是层次结构中的软硬交界面，目前多数是传统及其级与操作系统机器级之间。既考虑能拿到的硬、器件，又要考虑硬件对操作系统、编译系统的实现提供什么支持，然后由中间点分别往上、往下进行软件和硬件的设计。优点在于：针对上述两种方法的缺陷，软件和硬件并行设计，可缩短系统设计周期，设计过程中可交流协调，是一种交互式的、较好的设计方法。

1.4结构设计要解决好软件的可移植性 1.实现软件移植的好处和技术

软件的可移植性：指的是软件不修改或只经少量修改就可由一台机器移到另一台机器上运行，同一软件可应用于不同的环境。这样，实践证明是可靠的软件就能长期使用，不会因机器更新去重新编写，既大大减少了编制软件的工作量，又能迅速用上新的硬件技术，更新系统，让新系统立即发挥效能。

实现软件移植的几个基本技术：统一高级语言、采用系列机、模拟和仿真。 2. 统一高级语言

统一高级语言：实现软件移植的一种技术是统一高级语言，设计出一种完全通用的高级语言，为所有程序员所使用。这样，结构相同以至完全不同的机器之间都能实现高级语言程序的软件移植。

第一，不同的用途要求语言的语法、语义结构不同。 第二，人们对语言的基本结构看法不一。 第三，即使同一种高级语言在不同厂家的机器上也不能完全通用。第四，受习惯势力阻挠，人们不愿抛弃惯用的语言，因为熟悉、有经验，也不愿抛弃长期积累的、用原有语言编写并已被实践证明是正确的软件。

对策：统一高级语言可以解决结构相同或完全不同的机器间的软件移植，从长远看是方向但目前难以解决，只能作相对统一。

3.采用系列机

＠系列机设计是从中间向两边设计相呼应。在软、硬件界面上设定好一种系统结构(系列机中称系列结构)，其后，软件设计者按此设计软件，硬件设计者根据机器速度、性能、价格的不同，选择不同器件、硬件和组成、实现技术，研制并提供不同档次的机器。

＠采用系列机：在结构相同或相似的机器之间实现软件移植

＠优点：①解决了软件环境要求稳定，软件可不断积累、丰富、提高。②能不断采用新的器件和硬件技术，使之性能不断提高。缺点：因要保持向后兼容性，器件越来越复杂，最终系统结构受到发展限制。

＠系列机软件兼容的最基本的要求和特征是系列机软件必须保证向后兼容，力争向上兼容。 对策：系列机是普遍采用的好办法，但只能实现同一系列内软件兼容，同时软件兼容又会阻碍系统结构突破性的发展；适当的时候推出新的系列结构。

4.模拟和仿真

模拟和仿真是不同系统结构的机器之间的机器语言软件移植方法。这种用机器语言程序解释实现软件移植的方法称为模拟。缺点：运行速度显著降低，实时性差，模拟程序编制复杂和费时。用微程序直接解释另一种机器指令系统的方法就称为仿真。缺点：微程序机器结构深深依赖于传统机器级的结构，当两种机器结构差别大时就很难仿真。

两者区别：在于解释用的语言。仿真是用微程序解释，其解释程序存在控制存储器中；模拟是用机器语言解释，其解释程序存在主存中。

对策：模拟灵活，可实现不同系统间的软件移植，但结构差异较大时，效率、速度会急剧下降；仿真速度较快，但不灵活，只能在差别不大的系统之间使用。因此，在不同系列机器间的软件移植时，将模拟和仿真两种技术结合起来使用。

1.5应用与器件的发展对系统结构的影响

1. 应用的发展对系统结构的影响

计算机工业在处理性能和价格的关系上大致也是这两种趋势：维持价格提高性能；维持性能降低价格。 从系统结构的观点看：①低档(型)机上引用甚至照搬高档(型)机的结构和组成。②巨、大型机一般采取维持价格、提高性能或提高价格、提高性能来研究和采用新的结构及组成。③为保持小、微型机的便宜价格，从结构和组成上采用为不同用途提供相应选购件或扩展部件的做法是可取的。

2. 器件的发展对系统结构的影响

器件的发展历程：从电子管、晶体管、小规模集成电路、大规模集成电路迅速发展到超大规模集成电路，并使用或开始使用砷化镓器件、高密度组装技术和光电子集成技术。在此期间，器件的使用方法发生了由非用户片，发展到现场片和用户片，它影响着结构和组成技术的发展。已从非用户片发展到现场片与用户片。

一般同一系列内各档机器可分别用通用片、现场片或用户片实现。就是同一型号机器也先用通用片或现场片来实现，等机器成熟取得用户信任后，再改用半用户片或全用户片实现。至于高速机器一般一开始就用门阵列片或用户片，只有这样，才能发挥出单元电路的高速性。

①器件的发展改变了计算机系统设计的传统方法。过去逻辑设计主要是以节省功耗、降低成本、提高速度为目的，而对VLSI来说，如何能缩短设计周期、提高系统效能及能用上批量生产的通用的VLIS片子为目的。②器件的发展推动结构和组成的发展。促使计算机性能价格比的提高；加速了结构的“下移”；促进了算法、语言和软件的发展。

1.6系统结构中的并行性发展和计算机系统的分类 1.并行性含义：

1）并行性：指有同时进行运算或操作的特性。开发并行性的目的是为了能并行处理，以提高计算机解题的效率。并行性包括同时性（二个或多个事件在同一时刻发生）和并发性（两个或多个事件在同一时间间隔内发生）

2）并行性等级

＠执行程序的等级划分：（由低到高）指令内部、指令之间、任务或进程之间、作业或程序之间 ＠处理数据的等级划分：（由低到高）位串字串、位并字串、位片串字并、全并行

＠信息加工的等级划分：（由低到高）存储器操作并行、处理器操作并行、处理器操作并行、指令、任务、作业并行。

3）并行性开发的途径

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

＠资源重复：是在并行概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。 ＠资源共享：是用软件的方法让多个用户按一定时间顺序轮流使用同一套资源来提高其利用率，相应也就提高了系统的性能。

4

在1960年以前，并行性发展主要表现为算术运算的位并行及运算与输入/输出操作的并行。 1960～1970年的这段时间内，出现了多道程序分时系统、多功能部件、流水线单处理机等。 1970～1980年，VLSI的普遍应用加快了并行处理系统结构的发展，出现了大型和巨型的向量机、阵列机、相联处理等多种并行处理系统结构。

1980～1990年，在系统结构上创新和突破影响较大的有精简指令系统计算机(RISC)，指令级并行的超标量处理机、超流水线处理机、超长指令字(VLIW)计算机，多微处理机系统，数据流计算机和智能计算机。

1990年以来，计算机发展进入新的多计算机和智能计算机时代。机器最主要的特点是进行大规模并行处理(MPP)，采用VLSI硅片、砷化镓、高密度组装和光电子技术。多处理机包括多向量机及机群系统、多计算机系统将是今后并行处理计算机发展的主流。

3T性能目标：科学计算中的重大挑战性课题往往要求计算机系统能有1TFLOPS的计算能力、1TB的主存容量、1TB/s的I/O带宽，称之为3T性能目标。

2并行处理系统的结构与多机系统的耦合度

1）并行处理计算机的结构：并行处理机按其基本结构特性，可以分为：流水线计算机、阵列处理机、多处理机（分布处理、机群系统和MPP）和数据流计算机四种不同结构。

2）多机系统的耦合度：多机系统包含多处理机系统和多计算机系统。多处理机系统：是由多台处理机组成的单一系统。多计算机系统：则是由多台独立的计算机组成的系统。

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

3. 计算机系统的分类（弗林分类法）

按指令流和数据流的多倍性对计算机分类分为：SISD（单处理器的计算机、流水线单处理机）、SIMD（阵列处理机、相联处理机）、MISD（脉动阵列流水机）、MIMD（多处理机和多计算机系统）四大类

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

2.1数据表示

1. 数据表示与数据结构的关系

数据表示指的是能由机器硬件直接识别和引用（处理）的数据类型；数据表示是硬件设计的基础，表现在它具有对这种数据类型进行操作的指令和运算部件。数据结构反映应用中要用到的各种数据元素之间的结构关系，是软硬功能分配中软的方面。数据结构是通过软件映象变换成机器所具有的各种数据表示实现，数据表示是数据结构的组 成元素。

2. 高级数据表示 1) 自定义数据表示

为了缩短高级语言与机器语言的语义差距引出来的，它有标志符数据表示和数据描述符数据表示 2）带标志符的数据表示

让数据类型直接与数据本身联系在一起，运算符不反映数据类型，是通用的。将数据类型和数据本身联系在一起，机器语言中的操作码和高级语言的运算符一样能够通用于各种数据类型的操作称这种数据表示为标志符数据表示。标志符应由编译程序建立，对高级语言程序透明，以减轻应用程序员的负担。

优点：简化了指令系统和程序设计；简化了编译程序；便于实现一致性校验；能由硬件自动完成数据类型的变换；支持了数据库系统的实现与数据类型无关的要求；为软件调试和应用软件开发提供了支持。

缺点：每个数据字因增设标志符，会使程序所占用的主存空间增加；采用标志符会降低指令的执行速度。

3）数据描述符

主要用于描述向量、数组、记录等成块数据。数据描述符和标志符的差别：标志符是和每个数据相连的，合存在一个存贮单元中，描述单个数据的类型特征；描述符是和数据分开存放的，专门用来描述所要访问的整块数据特征。

优点：描述相同类型的数据块时，占用空间比标志符少，比标志符的效率要高；为向量、数组实现提供了支持，有利于简化高级语言编译中的代码生成可以比变址法更快形成元素地址。

缺点：由于没有相应的向量、数组运算类指令的高速运算硬件，数据描述符并不能支持向量、数组的高效实现。

4）向量数据表示

为向量、数组数据结构的实现和快速运算提供更好的硬件支持的方法是增设向量、数组数据表示，组成向量机，如STAR-100和CRAY-1等。有向量数据表示的处理机就是向量处理机，如向量流水机、阵列机、相联处理机等。

引入向量、数组数据表示不只是能快速形成元素的地址，更主要的是便于实现把向量各元素成块预取到中央处理机，并用一条向量、数组指令流水或同时对整个向量、数组高速处理，用硬件判断下标是否越界，并让越界判断和元素运算并行。高速巨型机都设置有向量数据表示；现在向量、数据表示已下移到了通用机和系列机上。

5）堆栈数据表示

堆栈数据结构在编译和子程序调用中很有用，为高效实现，不少机器都设有堆栈数据表示。 堆栈机器特点：①有高速寄存器组成的硬件堆栈，并与主存中的堆栈区在逻辑上构成整体，使堆栈的访问速度是寄存器的，容量是主存的。②有丰富的堆栈操作指令且功能很强，直接可对堆栈中的数据进行各种运算和处理。③有力地支持了高级语言程序的编译。④有力地支持了子程序的嵌套和递归调用。

6）引入数据表示的原则

＠一是看系统的效率是否提高，即是否减少了实现时间和存储时间。 ＠二是看引入这种数据表示后，其通用性和利用率是否高。

数据表示的确定：①一般计算机选用常用的数据表示；②对较高级的数据表示要有针对性的选取； 3. 浮点数尾数基值大小和下溢处理方法的选择 1) 浮点数尾数基值大小

当机器字长相同时，用浮点数表示实数比用定点数表示有更大的可表示数范围。

当总的机器字长定好后，浮点数表示中p和m的位数主要是根据数的表示范围和精度来定。浮点数阶值的位数p主要影响两个可表示区的大小，即可表示数的范围大小，而尾数的位数m主要影响在可表示区中能表示值的精度。当阶值位数p、m一定时，尾数采用什么进制也还会影响到数的可表示范围、精度及数在数轴上分布的离散程度。

非负阶、正尾数，且都是规格化数的情况：

可表示最小尾数值：rm可表示最大阶值： 2

p

-1

可表示最大尾数值：1-rm

-m‘

-1 可表示最小值：rm-1

可表示尾数的个数：

可表示最大值：可表示阶的个数：2

p

可表示数的个数：2

p

·

尾数基值取大，会扩大浮点数的范围、增加可表示数的个数、减少移位的次数、降低右移造成的精度损失、提高运算速度，这些都是好的；但会降低数据的表示精度、数值的分布变稀，这些都是不好的。因此

选取根据应用需要来综合平衡：一般在大、中型机上，

宜取大，这样可使数的表示范围大、个数

多、运算速度快，因浮点数尾数位数相对多得多，所以精度实际比小、微型机的高得多；而小、微型机由于可表示数范围不要求太大，速度也不要求太高，尾数字长较短，所以更注重于可表示精度，宜使小些。

2) 下溢处理方法的选择

下面以二进制数0.0111为例，机器字长为2。大家还要看看各种方法的误差问题 1）截断法：0.01,去掉你的尾巴

2）舍入法：0.10，小数点第三位为1进1，为0舍去 3）恒置1法：0.01

4）查表舍入法：用2^K的ROM存放下溢处理表，地址值由尾数的K-1位和弃掉最高位组成，ROM对应的内容就是下溢处理结果。

产生误差值最大的是恒置1法，最小的舍入法；平均误差最大的是截断法，最小的是查表舍入法；下溢处理不需要附加时间，速度最快的是截断法和恒置1法，最省硬件的是截断法和恒置1法，最慢的是舍入法，最费硬件的是查表舍入法。

基本思想：ROM查表舍入法是将K位数据下溢处理成K-1位的结果，ROM表存储容量为2k个单元，每个单元字长为K-1位。待处理的K位数据作为地址，按此地址读出表中对应单元中所存放的K-1位内容就是该数经下溢处理后的结果。ROM表的安排原则：Ⅰ）当k位尾数为非全1时，按舍入法取值；Ⅱ）当k位尾数为全1时，按截断法取值。

2.2寻址方式

1）寻址方式：指令寻找操作数或信息的方式，有面向寄存器、面向堆栈、面向主存三种方式。 2）寻址方式在指令中的两种指名方式 3）程序在主存中的定位技术

静态再定位是目的程序装入主存时，通过调用装入程序，把目的程序的逻辑地址用软的方法逐一修改成物理地址。不利于多道程序运行、程序的可重入、故障排除、重叠流水技术使用。

动态再定位的一种方法是设置基址寄存器和地址加法器硬件，在程序装入主存时，只将装入主存的起始地址存入该道程序的基址寄存器中，指令的地址字段不做修改。程序在执行过程中，不断将逻辑地址经地址加法器加上基址寄存器中的基址，形成物理地址访存。

基址寻址与变址寻址的区别：基址寻址是对逻辑地址空间到物理地址空间变换的支持，以利于实现程序的动态在定为。变址寻址是对向量、数组等数据块的运算支持，以利于实现程序的循环。

4）信息按整数边界存放

取得

主存内一般同时存有多种长度的信息，为了让任何所需的信息都只用一个存储周期访问到，就要求信息在主存中存放的地址必须是该信息宽度的整数倍。P61.7

2.3指令格式的优化设计

指令格式的优化来说，就是指如何用最短的位数来表示指令的操作信息和地址信息，使程序中指令的平均字长最短。

1）指令操作码的优化

研究操作码的优化表示，主要是为了缩短指令字长，减少程序总位数及增加指令字能表示的操作信息和地址信息。

哈夫曼编码的基本思想。

①操作码等长编码 操作码用定长码表示需要②哈夫曼编码

步骤：1）将所有指令的使用频率由小到大排序； 2）每次选择基中最小的二个频度合并成一个频度，并插入余下未参与结合的频度值中；3）重复步骤2直至结合完毕形成根结点 4）每个结点向下延伸的二个分支左标\"1\"，右标\"0\"（相反也行）5）从根结点开始沿线到达各指令所经的代码序列就构成了该频度指令的哈夫曼编码。

哈夫曼编码的平均码长公式

哈夫曼编码并不是惟一的，但只要采用全哈夫曼编码，操作码的平均码长肯定是惟一的，而且是可用二进制位编码平均码长最短的编码。全哈夫曼编码是最优化的编码。但这种编码的码长种类太多。

③扩展操作码编码

用有限的几种码长对操作码给行编码，即让平均码长接近哈夫曼编码，又能让计算机方便地进行处理。

扩展码的扩展的方法：早期一般采用等长扩展，如15/15/15法和8/64/512法，但现在不再强调等长扩展了。

2）指令格式优化的措施

在操作码优化的基础上，再在地址码和寻址方式采取相关措施，就可以减少程序的总位数，使指令字格式达到优化。

①采用扩展操作码，并根据指令的频度pi的分布状况选择合适的编码方式，以缩短操作码的平均码

(即3)位

②采用诸如基址、变址、相对、寄存器、寄存器间接、段式存放、隐式指明等多种寻址方式，以缩短地址码的长度，并在有限的地址长度内提供更多的地址信息；

③采用0、1、2、3等多种地址制，以增强指令的功能，这样，从宏观上就越能缩短程序的长度，并加快程序的执行速度；

④在同种地址制内再采用多种地址形式，如寄存器-寄存器、寄存器-主存、主存-主存等，让每种地

2.4按CISC方向发展和改进指令系统 1.CISC改进思路

如何进一步增强原有指令的功能以及设置更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬化。它可从面向目标程序、面向高级语言、面向操作系统三个方面的优化实现来考虑。

1） 面向目标程序的优化实现改进

目标是：提高包括系统软件和应用软件在内的各种机器语言目标程序的实现效率。该方法既能减少目标程序占用的存储空间，缩短指令的执行时间，提高程序的运行速度，使实现更加方便。

途径是：第一种思路是通过对大量已有机器的机器语言程序及其执行情况进行统计各种指令和指令串的使用频度来加以分析和改进。对高频指令可增强其功能，加快其执行速度，缩短其指令字长；而对使用频度很低的指令可考虑将其功能合并到某些高频的指令中去，或在今后设计新系列机时，将其取消。对高频的指令串可增设新指令取代。

第二种思路是增设强功能复合指令来取代原先是由常用宏指令或子程序实现的功能，由微程序解释实现，不仅大大提高了运算速度，减少了程序调用的额外开销，也减少了子程序所占的主存空间。用新指令替代常用指令串的办法实质上是尽量减少程序中不执行数据变换的非功能型指令的使用，让真正执行数据变换的功能型指令所占的比例提高。

2）面向高级语言的优化实现改进

目标：就是尽可能缩短高级语言和机器语言的语义差距，支持高级语言编译，缩短编译程序长度和编译时间。

途径：第一种改进思路是通过对源程序中各种高级语言语句的使用频度进行统计来分析改进。对高频语句增设与之语义差距小的新指令。

第二种重要的思路是如何面向编译，优化代码的生成来改进，增强系统结构的规整性和对称性来改进指。

第三种思路是设法改进指令系统，使它与各种语言间的语义差距都有同等的缩小。 第四种思路，让机器具有分别面向各种高级语言的多种指令系统、多种系统结构，并动态的切换，发展自适应系统。

第五种思路，发展高级语言计算机(或称高级语言机器). 3）面向操作系统的优化实现改进

目标：就是如何缩短操作系统与计算机系统结构之间的语义差距，进一步减少运行操作系统的时间和节省操作系统软件所占用的存储空间。

途径：第一种思路同样是通过对操作系统中常用指令和指令串的使用频度进行统计分析来改进。但这种改进的效果很有限。

第二种思路是考虑如何增设专用于操作系统的新指令。

第三个思路是把操作系统中频繁使用的，对速度影响大的机构型软件子程序硬化或固化，改为直接用硬件或微程序解释实现。

第四个思路是：发展让操作系统由专门的处理机来执行的功能分布处理系统结构。 2.5按RISC方向发展与改进指令系统 1. CISC结构的问题

①指令系统庞大，一般在200条指令以上。延长了设计周期，增大了设计成本，增大设计出错的机会，降低了系统的可靠性。②许多指令的操作繁杂，执行速度很低。③指令系统庞大，使高级语言编译程序选择目标指令的范围太大，难以优化生成高效机器语言程序，编译程序也太长、太复杂。④指令系统庞大，各种指令的使用频度都不会太高，80%的指令使用频度低，降低了系统的性能价格比。

2.设计RISC机器一般原则

(1)确定指令系统时，精简指令条数，只选择使用频度很高的那些指令，使之一般不超过100(2)减少指令系统所用寻址方式种类，一般不超过两种。简化指令的格式限制在两种之内，并让全部指令都是相同长度。

(3)让所有指令都在一个机器周期内完成。 (4)扩大通用寄存器数，尽量减少访(5)(6)

3. 设计RISC结构采用的基本技术 (1)按设计RISC的一般原则来设计。 (2)逻辑实现采用硬联和微程序相结合。

(3)在CPU中设置大量工作寄存器并采用重叠寄存器窗口。 (4)指令用流水和延迟转移。

(5)采用高速缓冲存储器Cache,设置指令Cache和数据Cache分别存放指令和数据。 (6)优化设计编译系统。

4. 采用RISC结构后可以带来如下好处： (1)简化指令系统设计，适合VLSI实现。 (2)提高机器的执行速度和效率。

(3)降低了设计成本，提高了系统的可靠性。

(4)可直接支持高级语言的实现，简化编译程序的设计。 5. RISC存在某些问题及发展趋势

(1)由于指令少，使原在CISC上由单一指令完成的某些复杂功能现在要用多条RISC指令才能完成，加重了汇编语言程序设计的负担，增加了机器语言程序的长度，占用存储空间多，加大了指令的信息流量。(2)对浮点运算执行和虚拟存储器的支持虽有很大加强，但仍显得不足。(3)RISC机器的编译程序比CISC的难写。

今后计算机发展趋势：使得在设计CPU时，向着RISC和CISC结合，取长补短的方向发展。

第3章 总线、中断和输入输出系统

3.1输入输出系统的基本概念 1.I/O系统的组成

输入输出系统包括输入输出设备、设备控制器及与输入输出操作有关的软、硬件。 2.I/O系统的面向操作系统的设计

目前，大多数计算机系统上，用户程序的输入输出不能由用户自己安排，通过高级语言的I/O读写语句到编译程序、操作系统软件和I/O总线、设备控制器、设备硬件等共同完成。I/O功能只反映在高级语言与操作系统的界面上，应用程序员不必具体安排程序是怎样完成输入输出的。因此，大多数计算机的I/O系统的设计应是面向操作系统，考虑怎样在操作系统与I/O系统之间进行合理的软、硬件功能的分配。输入输出系统硬件的功能对应用程序员来说是透明的。

3. I/O系统的发展

I/O系统的发展经历了3个阶段（3种I/O方式）：程序控制I/O方式（全软的、程序查询的、中断驱动）、直接存储器访问方式（DMA）、及I/O处理机方式。对于I/O处理机方式又分为：通道方式（CH）和外围处理机方式（PPU）。

3.2总线设计 1.总线分类

1）单向传输和双向传输：（允许信息传送方向） 2）专用总线和非专用总线（用法）

＠专用总线：优点是多个部件同时收发，不争用总线，系统流量高，控制简单，可靠性高，但线路复杂。 ＠非专用总线：多种功能或多个部件分时共享，同是只有一对部件可使用总线进行通讯。优点是总线数少，接口标准化，模块性强，可扩充能力强，缺点是系统流量小，出现争用总线的情况，可能导致系统瘫痪.

2.总线的控制方式

1）串行链接：所有部件经公共\"总线请求\"向控制器发出使用申请；\"总线请求\"信号串行通过每个部件，发送结束后去除\"总线忙\"，由部件物理位置决定其使用总线优先级。优点是控制简单。缺点是优先级不灵活，信号失效敏感。

2）集中式查询：所有部件经公共\"总线请求\"向控制器发出使用申请；总线定时查询计数并寻找发送部件。优点是优先级灵活，可靠性高，缺点是控制线数多，控制复杂。

3）集中式独立请求方式：每个部件各自一对\"请求\"和\"准许\"线；控制器根据某种算法确定使用总线部件。优点是总线分配速度快，优先级灵活。缺点是控制线数多，控制复杂。

3.总线的通讯技术：同步通讯和异步通讯，异步通讯又分为单向控制和请求/回答双向控制两种方式。 4、数据宽度与总线线数

＠数据宽度：是I/O设备取得I/O总线后所传送的数据总量。有单字、定长块、可变长块、单字加定长块和单字加可变长块等。数据宽度是指I/O设备取得I/O总线后一次所传送的数据总量，分类也是按这标准进行划分的。

＠总线线数：在满足性能前提下，总线线数可通过线的组合、编码及并/串-串/并转换来减少，但一般会降低总线的流量。

3.3中断系统 1.中断的分类和分级 1）基本概念

＠中断源：引起中断的各种事件

＠中断请求：中断源向中断系统发出请求中断的申请

＠中断响应的过程：CPU中断现行程序的运行，转去对该请求进行预处理，调出有关中断的处理服务程序，准备运行。 2）中断的分类：

＠为什么要分类：不少中断源性质相近，为了简化中断处理程序入口地址形成硬件，将它们归为几类，每类给定一个中断服务程序入口，再由软件分支转入相应的中断处理部分。

＠一般分为：机器校验，管理程序调用，程序性，外部，输入输出和重新启动6类。

＠多个中断请求的同时出现就要对中断进行分级（中断响应的优先次序）：依次为：机器校验、程序性和管理程序调用、外部中断和I/O中断、重新启动。

2.通过中断屏蔽位改变中断响应次序的方法 1)中断响应的优先次序和中断处理次序

＠中断响应次序是由硬件中中断排队器所决定的中断响应次序，是定死的。

＠中断的处理要由中断处理程序来完成，而中断处理程序在执行前或执行中是可以被中断的，所以中断处理次序和中断响应的优先次序可以不同，中断级屏蔽位寄存器用以决定某级中断请求能否进入中断响应排队器。课本P71页范例.

3.中断系统的软硬件功能分配

＠中断系统的功能包括：中断请求的保存、优先级的确定（硬件）、中断现场的保存、对中断请求的分析（硬件）和处理、中断返回等。

3.4通道处理机

1.通道处理机进行输入输出的过程

在多用户环境下，应用程序进行一次输入输出，只能在目态程序中安排要求输入/输出的访管指令，并带上设备号、设备与主存交换的字节数、与主存交换信息的起始地址等参数。

CPU执行到访管指令时，按其入口地址，将管理程序调出来执行。此管理程序任务是根据提供的参数编制通道程序。

编制好的通道程序存在主存对应该通道的通道缓冲区中，就置好相应通道地址字。之后，管理程序就执行“启动I/O”指令，进入通道开始选择设备期。

在通道开始选择设备期内，CPU先选择指定的通道、子通道、备控制器和设备，向设备发启动命令。设备启动成功后，CPU退出管态，继续运行目态程序。而通道进入通道数据传送期。

被启动的通道开始执行存放于通道缓冲区内通道程序组织I/O操作，直至通道程序执行完无链通道指令后，传送完成，转入通道数据传送结束期，向CPU发出I/O中断请求。CPU响应此中断请求后，第二次转管态，调出相应管理程序对中断请求进行处理。之后，再返回目态，继续目态程序的运行。

这样，每完成一次输入/输出只需两次进管，大大减少了对目态程序的干扰，显著提高了CPU运算和外设操作及多台设备可以并行工作。

2.通道的分类

根据通道数据传送期中信息传送方式的不同，分字节多路、选择和数组多路三类通道。

字节多路通道适用于连接大量的像光电机等字符类低速设备（如键盘、鼠标、打印机）。通道“数据宽度”为单字节，以字节交叉方式轮流为多台低速设备服务，使效率提高。

数组多路通道适合于连接多台像磁盘等高速设备。“数据宽度”为定长块，传送完K个字节数据后就重新选择下个设备。采用成组交叉方式轮流为多台磁盘设备服务。

选择通道适合于连接优先级高的磁盘等高速设备（如高速磁盘等），让它独占通道，只能执行一道通道程序。“数据宽度”为可变长块，一次对N个字节全部传送完。

3. 通道流量的分析

通道流量：通道在数据传送期内，单位时间内传送的字节数。

假设设计通道选择一次设备的时间TS和传送一个字节的时间TD，数组多路通道每选择一台设备传送“定长块”K个字节，选择通道每选择一台设备传送“可变长块”N个字节。

字节多路通道极限流量 数组多路通道极限流量

选择通道通道极限流量

当挂上设备后，设备要求通道的实际最大流量：

字节多路通道 数组多路通道 选择通道通道

所挂设备在满负荷的最坏情况下都不丢失信息，必须满足设备要求通道的实际最大流量不超过通道的

极限流量，因此，上述三类通道应分别满足、、

如果I/O系统有m个通道，其中1至m1为字节多路，m1+1至m2为数组多路，m2+1至m为选择，则I

/O系统的极限流量为:

第4章 存储体系

4.1 存储体系的概念与并行主存系统 1.发展存储体系的必要性

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

最大频宽Bm是存储器连续访问时的频宽。单体的Bm=W/TA。m个存储体并行的最大频宽Bm=W×m/TA。由于存储器不一定能满负荷工作，因此，实际频宽往往低于最大频宽。

为弥补CPU与存储器在速度上的差距一条途径是发展存储系统，在组成上引入并行和重叠技术，构成并行主存系统，在保持每位价格基本不变的情况下，能使主存的频宽得到较大的提高；但靠这种并行主存的方法来提高频宽是有限的。

为弥补CPU与存储器在速度上的差距另一条途径是从系统结构上改进，发展存储体系；使所有信息以各种方式分布于不同的存储器上。例如，至少应有主存和辅存。

2.并行主存系统

能并行读出CPU字的单体多字和多体单字、多体多字的交叉访问主存系统。

单体单字存储器：Bm=W/Tm 单体多字存储器：Bm=mW/Tm 多体多字交叉访问存储器：Bm=mW/Tm 3. 并行主存系统频宽的分析

提高模m值是能提高并行主存系统的最大频宽的直接方法，但主存实际频宽并不是随m值增大而线性提高。原因在于以下两点：一是系统效率的问题。二是在工程实现上由于模m越高，存储器数据总线越长，总线上并联的负载越重，有时还不得不增加门的级数，这些都会使传输延迟增加。平均频宽是

其中m是分体个数，

4.存储体系的概念

是转移概率。

1）存储体系：让构成存储系统的n种不同的存储器(M1～Mn)之间，配上辅助软、硬件或辅助硬件，使之从应用程序员来看，它们在逻辑上是一个整体。让存储层次的等效访问速度是接近于M1的，容量是Mn的，每位价格是接近于Mn的。典型的两级存储体系是虚拟存储器和Cache存储器。

虚拟存储器：是从主存容量满足不了要求提出来的。从应用程序员来看，主、辅存就构成了一个完整的整体，速度接近于主存的，容量是辅存的，每位价格接近于的辅存。

Cache存储器：在CPU和主存之间增设高速、小容量、每位价格较高的Cache，用辅助硬件将Cache和主存构成整体。从CPU看，有接近于Cache的速度、主存的容量，接近于主存的每位价格。

2）存储体系透明性

虚拟存储器和Cache存储器对应用程序员来说都是透明的。虚拟存储器由辅助软件和硬件来完成，对系统程序员是不透明的，Cache存储器是由硬件来构成的对系统程序员来说也是透明的。

3）存储体系构成依据是程序的局部性

程序局部性包括时间上的局部性和空间上的局部性。前者指的是在最近的未来要用到的信息很可能是现在正在使用的信息，这是因为程序存在循环。后者指的是在最近的未来要用到的信息很可能与现在正在使用的信息在程序空间上是邻近的，这是因为指令通常是顺序存放、顺序执行，数据通常是以向量、阵列、树形、表格等形式簇聚地存放的。

4）存储体系的性能参数

为评价存储层次性能，引入存储层次的每位价格c、命中率H和等效访问时间TA。

存储层次的每位价格

使SM1 <命中率H定义为CPU产生的逻辑地址能在M1中访问到(命中到)的概率。存储层次的等效访问时间

希望TA越接近于TA1，即存储层次访问效率

越接近于1越好。

在主、辅存之间增加一级电子磁盘，使级间r值不会过大，有利于降低对H的要求，以获得同样的e。所以要想使存储层次的访问效率e趋于1，就要在选择具有高命中率的算法、相邻二级的容量差和速度差及增加的辅助软、硬件的代价等因素间综合权衡，进行优化设计。

4.2虚拟存储器

根据所用的映像算法，将虚拟存储器管理方式分成段式、页式和段页式3种 （一）页式虚拟存储器管理方式

1）思想：逻辑空间分页，物理空间分同样大小的页，二者对应。

2）页表：主存起点，装入位，访问方式，专用位 3）地址变换过程（P92图4.13）

＠根据虚地址中的用户标志在页表基址寄存器找到程序页表的始点； ＠根据程序页表的始表和虚地址中的用户虚页号找到页表的对应行； ＠把页表对应行的实页号和虚地址的页内位移装入到主存地址寄存器 ＠根据主存寄存器的值访问主存。

4）优缺点：优点是映象表硬件较少，地址转换速度快，调入操作简单，页内零头浪费少。缺点是不易修改、保护，不易实现其用段的管理。

（二）页式虚拟存储器构成 1.地址的映像和变换 1）地址的映像和变换

虚地址Ns：用户标志U、用户虚页号Nv'及页内地址Nr； 实地址np：实页号nv、页内位移nr；

地址映象和变换：因为Nv>>nv，所以如何把多用户虚地址Ns变换成主存地址np；

2）全相联映象：让每道程序的任何虚页可以映象装入任何实页位置。它用页表作为地址映象表，故称之为页表法。

3）相联目录表法：由于页表中绝大部份行中的实页号及其它字段无用，降低了页表的空间利用率，所以把页表压缩成只存放已装入主存的那些虚页与实页位置的对应关系，简称目录表法。

4）外页表与内页表：用类似于页表的方式为每道程序设置一个存放用户虚页号与辅存实地址映象关系的表称为外页表；而页表则称为内页表。内页表的地址映象和变换是由硬件完成的，外页表由于辅存访问速度比较慢，所以用软件实现以节省硬件成本。[例]P123习题8

2.页面替换算法

1）替换算法：虚存的空间要比主存的空间大得多，当出现页面失效而主页页已满的情况下，必须强制主存中腾出某页让给辅存调来的新页，调出主存中的哪页的方法即为替换算法。替换算法的确定主要看主存是否有高的命中率。

2）RAND、FIFO、LRU及OPT算法

RAND算法：用软硬件的随面数产生主存中要被替换页的页号。

FIFO算法：选择最早装入主存的页作为被替换的页。这种算法实现方便，但不一定正确反映出程序的局部性。

LRU算法：选择近期最少访问的页作为被替换页。实现的方法是通过主存页面表来反映

OPT算法：根据未来实际使用情况将未来的近期里不用的页替换出去。这种算法是用来评价期它替换算法好坏的标准。不可能实现。

3）页地址模拟流

[例]P123习题4.9 [例]P122 习题4.6

4）堆栈型替换算法：设A是长度为L的任意一个页地址流,t为已处理过t-1个页面的时间点,n为分配给该地址流的主存页数，Bt(n)表示在t时间点、在n页主存中的页面集合，Lt表示到t时间点已遇到过的地址流中相异页的页数。如果替换算法满足：

n＜Lt时，Bt(n)

Bt(n+1)

n≥Lt时，Bt(n)=Bt(n+1)

则属堆栈型的替换算法。

LRU和OPT算法是堆栈型替换算法，FIFO算法不是堆栈型替换算法； 堆栈型算法的特性：命中率随主页数增加只有可能提高，至少不会降低。

5）PFF算法：由LRU算法加以改进，原理是由操作系统动态调节分配给各道程序的实页数。 3.虚拟存储器工作全过程 4.页式虚拟存储器实现中的问题 1）页面失效的处理

页面失效产生原因：页面的划分只是对程序和主存空间进行机械等分，造成指令或操作数横跨在两页上存储；

页面失效的处理不能按一般的中断对待，应看做是一种故障，必须立即响应和处理。解决的方法：后援寄存器法；

P122 习题4.4

2）提高虚拟存储器等效访问速度的措施

影响虚拟存储器等效访问的瓶颈：页表大并放在主存中；

解决方法：小机器用快速随机存储器或寄存器组来存放页表；大机器是靠硬件上增设快表来解决； 快表和慢表、散列、散列冲突

请大家结合习题P122页习题4.8和课本P107页的图4.27理解一下，这题我们在前面作过。 3）影响主存命中率和CPU效率的某些因素

页面大小Sp与主存命中率H的关系：随着Sp的逐渐增大，H先增大到最大值后又减小 分配给某道程序的容量S1与H的关系：随着S1逐渐增大，H先增加到最大值后趋向平缓（堆栈型算法。）。

请大家结合P122习题4.6和4.9理解一下 （二）段式管理

1）思想：逻辑空间分段，物理空间分区，段对应区。 2）段表：段名，地址，装入位，段长，访问方法。 3）地址变换过程：（请与课本P90图4。11对照）

由虚地址中的程序号指明哪个基址寄存器

根据基址寄存器的值和虚地址中的段号在该程序的段表找到相应的记录 根据段表的记录和虚地址中的偏移量在实主存空间找到物理地址

4）优缺点：优点是能使大程序分块编制、程序共用主存内的程序和数据、容易以段为单位实现存储保护；缺点是段表长增加辅助硬件开销和降低查表速度、造成大的段间零头浪费。

（三）段页式管理

1）思想：逻辑地址分段、段内分页；物理地址分块，块大小与页相同，逻辑页对应物理块

2）段表和页表：（与上面大致相同） 3）地址变换过程：（P93图。14）

根据虚地址用户标志U在段表基址寄存器中查到该程序的段表记录；

根据段表基址寄存器段表记录中的段表起点和虚地址中的段号找到多用户段表中对应的页表记录； 根据多用户段表中页表记录的页表起点和虚地址中的页号找到多用户页表中的对应记录； 根据多用户页表中对应记录的实页号和虚地址中的页内位移形成主存地址装入主存地址寄存器。 [例]P122习题4.5 4.3高速缓冲存储器 1.基本结构

将Cache和主存等分成大小相同的块，每当给出一个主存字地址进行访存时，都必须通过主存—Cache地址映像变换机构判定该访问字所在的块是否已在Cache中。如果在Cache中，主存地址经地址映像机构变换成Cache地址去访问Cache，Cache与处理机之间进行单字信息传送；如果不在Cache中，产生Cache块失效，这时将从访存的通路中把包含该字的一块信息通过多字宽通路调入Cache，同时，将被访问的字直接从单字通路送往处理机。如果Cache已装不进了，发生块冲突，就要按所选的替换块将该块替换进Cache，并修改地址映像表中的地址映像关系及Cache各块的使用状态标志等信息。

1）Cache的原理和虚拟存储器在原理上是类似的，所以虚拟存储器中使用的地址映象、变换及替换算法基本上也适用于Cache存储器，但由于对Cache的速度要求高，所以在构成、实现以及透明性等问题有其特点。

Cache—主存之间的地址映像和变换，以及替换、调度算法全得用专门的硬件来实现。这样，Cache存储器不仅对应用程序员是透明的，而且对系统程序员也是透明的。

Cache一旦发生失效，程序不能换道的，CPU只能停等着从主存中将所需的块调入物理Cache。 Cache存储器地址映像规则一般使用组相联或直接映像，不采用全相联映像。

处理机和Cache、主存的联系不同于虚拟存储器和主存、辅存之间的联系；主存和处理机之间设有直接通路，同时，Cache与处理机之间也设有直接通路。这样，发生块失效时，不是采用程序换道的方式，而是让Cache调块与处理机访主存重叠进行，这就是通过直接通路实现读直达；同样，也可以实现CPU直接写入主存的写直达。

2）为了更好地发挥Cache的高速性，用了以下方法：

流水进行查表变换和访Cache工作（流水概念下章介绍，现在的理解就是这两个步骤一起进行）； Cache的物理位置尽量靠近处理机或就放在处理机（我们现在微机的CPU中也有哦）； 让Cache调块与处理机访问主存字重叠进行； Cache访问主存的优先级尽量高 2.地址映像和变换 1）全相联映象和变换

映像规则：是主存中任意一块都可映像装入到Cache中任意一块位置(如图4.31)。 主存-Cache地址的变换：都采用目录表硬件方式实现。 地址变换过程：（如图4.31）给出主存地址

访存时，将其主存块号

与目录表中所有各项的

形成Cache

字段同时相联比较。若有相同的，就将对应行的Cache块号地址

取出，拼接上块内地址

,访Cache；若没有相同的，表示该主存块未装入Cache，发生Cache优点：块冲突概率最低，Cache的空间利用率最高。 缺点：要构成容量为2）直接映像

项的相联存储器，代价太大，且Cache容量很大时，查表速度很难提高。

映像规则：它把主存空间按Cache大小等分成区，每区内的各块只能按位置一一对应到Cache的相应块位置上。主存第i块只能惟一映像到第

变换过程：处理机给出主存地址时取

块位置上。

对应部分作为Cache地址访问Cache，同

访主存时，截取与

部分作为地址访问区号标志表存储器，读出原先所存区号与主存地址对应的区号部分相比较。若

比较相等时，表示Cache命中，让Cache的访问继续进行，并中止访主存；若比较不等，表示Cache块失效，此时让Cache的访问中止，而让主存的访问继续进行，并由硬件自动将主存中该块调入Cache。

表存储器：存放Cache每一块位置目前是被主存中哪个区的块所占用的区号。

优点：所需硬件省，只需容量较小的按地址访问的区号标志表存储器和少量的比较电路，成本很低。

直接映像的缺点：Cache的块冲突概率很高。只要有两个或两个以上经常使用的块恰好被映像到Cache同一块位置上，就会使Cache命中率急剧下降。

3）组相联映像及其变换

将Cache空间和主存空间都分成组，每组为S块(整个Cache是一区。主存分成与Cache同样大小的

)。Cache共有

个块，分成Q组(

)，

个区，其地址按区号、组号、组内块号、块内地

址分成对应的4个字段。主存地址的组号、组内块号分别用q、s′字段表示，它们的宽度和位置与Cache地址的q、s是一致的。组相联映像指的是各组之间是直接映像，而组内各块之间是全相联映像。

当组相联映象的S大到等于CACHE的块数时（即CACHE所有块为一组时）就成了全相联映象，当S小到1时就变成了直接映象。

优缺点：是界于全相联映像与直接映像之间的，Cache块冲突概率要比直接映像的低得多。成本比全相联映象多得多，性能接近于全相联映象。

组相联的地址变换原理：（如图4.36）先由q在找，若在上q和

组中选出一组，对该组再用nd+s′进行相联查

行中查不到相符的，表示主存该块不在Cache中；如果查到有相符的，则将表中相应的s拼就是Cache地址

。

[例]P124习题4.12 3. 替换算法的实现

Cache存储器块替换多采用LRU算法，具体的硬件实现方法可以有堆栈法和比较法两类。堆栈法用到相联访问功能的寄存器组设备量大，价格较贵，所以更多的是采用比较对法。

1）堆栈法

思想：设置一个容量等于Cache 总块数的堆栈，每次访问与堆栈内各块号比较，相符将此块号取出重新压栈，没有则将新访问块号压入栈顶，栈底出栈（全相联映象） 优缺点：成本高，用于组相联且组内块数少的LRU算法场合。

2）比较对法

思想：让各块成对组合，用一个触发器的状态表示该比较对内两块访问的远近次序，再经门电路就可找到LRU块。

优缺点：比较对触发器的个数会随块数的增多以极快的速度增加，实现困难，用于块数少的场合。 4. Cache存储器的透明性及性能分析 1）Cache存储器的透明性分析

解决问题：Cache和主存对应单元内容不一致； 解决方法：写回法和写直达法 2）Cache的取算法 恒取法和不命中预取法

2） 影响Cache存储器性能的因素

＠命中率是与块大小、块总数、采用组相联的组大小、替换算法和地址流的簇聚性有关。 ＠块大，不命中率总是下降趋势； ＠组大，不命中率总是下降趋势；

＠只要命中率有限，等效访问速度能提高的最大值也是有限。

Cache存储器的等效访问速度与命中率的关系。 设储周期：

为Cache的访问时间，

为主存周期，

为访Cache的命中率，则Cache存储器的等效存

其等效访问速度提高的倍数为：

[例]P124习题4.13

第5章 重叠、流水和向量流水处理机

5.1重叠方式

1.指令的顺序方式与重叠方式的解释

顺序解释：指的是各条指令之间顺序串行(执行完一条指令后才取下条指令)地进行，每条指令内部的各个微操作也顺序串行地进行。优点：控制简单，转入下条指令的时间易于控制。缺点：上一步操作未完成，下一步操作便不能开始，速度上不去，机器各部件的利用率低。

重叠解释：在解释第k条指令的操作完成之前，就开始解释第k+1条指令。重叠解释虽不能加快一条指令的解释，却能加快相邻两条以至整段程序的解释。

2.重叠方式对计算机组成的要求

为解决“取指k+1”与“分析k”在时间上重叠，可能产生访存冲突。可采用办法：第一种办法是让操作数和指令分别存放于两个独立编址且可同时访问的存储器中；第二种办法是仍维持指令和操作数混存，但采用多体交叉主存结构；第三种办法是增设采用先进先出方式工作的指令缓冲寄存器(简称指缓)。

为了实现 “执行k”与“分析k+1”重叠，还需要解决好几个问题：①硬件上还应有独立的指令分析部件和指令执行部件。②还需在硬件上解决控制上的同步问题，保证任何时候都只是“执行k”与“分析k+1”重叠。③还需要解决好控制上的转移问题。④控制上还要解决好邻近指令之间有可能出现的某种关联问题。

3.一次重叠方式的相关控制

·\"相关\"：邻近指令之间出现关联，为了防出错让它们不能同时解释的现象；数相关：该例子是在第k、k+1条指令的数据地址之间有了关联，称为发生了“数相关”。数相关不只是会发生在主存空间，还会发生在通用寄存器空间。指令相关：如果采用机器指令可修改的办法经第k条指令的执行来形成第k+1条指令的现象。

1）指令相关

指令相关的处理：禁止指令修改，还可另设置一条执行指令来解决程序设计灵活性。 2）主存空间数相关的处理：推后读

推后读是指若出现相邻两条指令之间出现对主存同一单元要求先写后读的关联 3)通用寄存器组相关的处理

通用寄存器组数相关的处理方法：推后\"分析k+1\"和设置\"相关专用通路\"，前面降低速度为代价，后者增加硬件成本为代价。

设置\"相关专用通路\"是指第K条指令的运算结果直接通有硬件专用通道回送到寄存器。

通用寄存器组基址值或变址值相关的处理：方法同上类拟，只不推后分析的推后时间不同及设置\"相关专用通路\"回写是到访存操作数地址形成机构。

5.2流水方式 1.流水是重叠的延伸

一次重叠:“分析k+1”与“执行k”的一次重叠是把指令的解释过程分解成“分析”与“执行”两个子过程，在独立的分析部件和执行部件上时间重叠地进行。指令由串行解释到一次重叠解释，机器的最大吞吐率提高了一倍。

流水：分为更多的m个子过程，可同时解释m条指令即让相邻的m条指令的解释在时间上重叠。如能把一条指令的解释分解成时间相等的m个子过程，则每隔Δt=T/m就可以处理一条指令。机器的最大吞吐率提高了m倍。

2.流水线的分类

⑴.依据向下扩展和向上扩展的思路，可分类出在计算机系统不同等级上使用的流水线。 向下扩展：指把子过程进一步地细分，让每个子过程经过的时间都同等程度地减少，吞吐率就会进一步提高。

向上扩展：流水的向上扩展可理解为在多个处理机之间流水，流水按处理的级别可分为部件级、处理机级和系统级。

⑵.从流水具有功能的多少来看，可以分为单功能流水线和多功能流水线。

⑶.按多功能流水线的各段能否允许同时用于多种不同功能连接流水，可把流水线分为静态流水线和动态流水线。

⑷从机器所具有的数据表示可以把流水线处理机分为标量流水机和向量流水机。

⑸.从流水线中各功能段之间是否有反馈回路，可把流水线分为线性流水和非线性流水。 3.流水线处理机的主要性能 1）吞吐率Tp和加速比Sp

吞吐率：流水线单位时间里能流出的任务数或结果数。最大吞吐率：

瓶颈子过程：流水线中经过时间最长的子过程；消除瓶颈：一种办法是将瓶颈子过程再细分。二种办法重复设置多套(如用三套)瓶颈段并联，让它们交叉并行。

实际吞吐率：设一m段流水线的各段经过时间均为Δt0，则第1条指令从流入到流出需要T0=mΔt0

的流水建立时间，之后每隔Δt0就可以流出一条指令。这样，完成n个任务的解释共需时间T=m·Δt0+(n-1)Δt0。在这段时间里，流水线的实际吞吐率：

加速比：如果用加速比Sp表示流水方式相对于非流水顺序方式速度提高的比值，那么非流水顺序方

式连续完成n个任务需要n×m×Δt0的时间，因此，流水方式工作的加速比：

2）效率

流水线的效率：是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。如果是线性流水线，且各段经过时间相同， 则在T时间里，流水线各段的效率都相同，均为η0，即

与吞吐率关系：η=TP·△t0

P5.3习题5.3类似题目：习题2、4、5、6类型 4. 流水线机器的相关处理

流水机器的相关由全局性相关和局部性相关两类。

全局性相关：转移指令与其后的指令之间存在关联，使之不能同时解释，还会使指令缓冲器所预取的指令全部作废，重新花较长的时间再去访存取指令。其造成的对流水机器的吞吐率和效率下降的影响要比指令相关、主存操作数相关和通用寄存器组相关及基址值或变址值相关严重的多，所以称为全局性相关。

局部性相关：是指指令相关、主存操作数相关和通用寄存器组相关及基址值或变址值相关，影响的是相关的两条或几条指令，最多影响流水线某些段工作的推后，不会改动指缓中预取到的指令，影响是局部的所以称为局部性相关。

1）局部性相关的处理

同步流动方式：一种是让任务(指令)流出流水线的顺序保持与流入流水线的顺序一致，称为顺序流动方式或同步流动方式。采用顺序流动方式的好处是控制比较简单，ASC机就采用这种方式。

异步流动方式：另一种是让流出流水线的任务(指令)顺序可以和流入流水线的顺序不同，称为异步流动方式。

异步流动方式带来的新的相关：\"写-写\"相关、\"先读后写\"相关、\"先写后读\"相关； 解决方法：推后后续指令和设置相关直接通路； 2）全局性相关的处理

猜测法：根据历史猜测出现概率大的分支装入指缓； 加快和提前形成条件码：不等指令执行完成提前形成条件码；

采取延迟转移：用软件方法将转移指令与其前面不相关的指令交换位置；

加快短循环程序的处理：将长度小于指缓的循环程序一次性放入指缓，并暂停预联指令或者循环出口端条件转移指令恒猜循环分支。

5.流水机器的中断处理

问题：在执行指令i时有中断，断点本应在指令i执行结束，指令i+1尚未开始执行的地方，但流水机器是同时解释多条指令， 指令i+1、 i+2…可能已进入流水线被部分解释。 对于异步流动流水线，这些指令中有些可能流到了指令i的前面去了。

解决办法：①采用“不精确断点”法。②采用“精确断点”法。 [例]P158习题8 6.流水线的调度

非线性流水线会出现多个任务争用同一功能段的使用冲突现象。预约表及流水线调度过程。解题步骤： ①根据预约表写出延迟禁止表F；②由延迟禁止表形成冲突向量C；③由所有的向量图画出状态图；④由状态图形成最佳调度方案。[例]P158习题5 .9。

5.3向量的流水处理与向量流水处理机 1.向量的流水处理

横向（水平）处理方式：逐个求结果向量的各个元素会引起流水线功能段的频繁切换以及发生大量的先写后读的操作数相关，不适合流水处理。

纵向（垂直）处理方式：避免了功能段的频繁切换以及发生大量的先写后读的操作数相关，适合流水处理。

分组纵横处理方式：可以减轻对向量长度N的限制，以便用面向寄存器-寄存器型的结构流水。 CRAY-1,将长向量按向量寄存器组中寄存器的个数分组，组内按纵向方处理，组间采用软件的方法编制向量循环程序来横向处理。

2.向量流水处理机（以CRAY-1为例） 1）组成：P150

2）流水线单功能部件：P151 3）向量寄存器：P151

4）Vi冲突：并行工作的各向量指令的源向量或结果向量使用相同的Vi；

5）功能部件冲突：同一功能部件被要求并行工作的多条向量指令所使用； 6）四个向量指令（P152图5。29）

7）通过链接技术实现向量指令之间大部分时间并行（以D=A*（B+C）为例）

掌握根据P152三条向量指令画出图P153图5.30的方法，注意两个条件，一是向量长度限制，二是Vi冲突的解决方法。

[例]P158习题5.10

5.4指令级高度并行的超级处理机

超标量处理机（资源重复）：配置多套部件，按组（一组m条指令）执行指令；

超长指令字（VLIW）处理机：编译程序找出指令间潜在并行性，将多个能并行执行的指令或无关操作先行压缩组合在一起，形成一条多个操作段的超长指令。

超流水线处理机（时间并行性）：在公共硬件上采用较短时钟周期，深度流水来提高速度，提高每个部件的利用率。

第6章 阵列处理机

阵列处理机（并行处理机）：将大量重复设置的处理单元PE按一定的方式互联成阵列，在单一控制部件CU控制下对各自所分配的不同数据并行执行同一指令规定的操作，是操作级并行的SIMD计算机。主要用于大量向量、数组要求高速运算场合。

6.1阵列处理机原理 1.阵列处理机基本构型

由于存储器的组成方式不同，阵列处理机有两种不同的基本构型：分布式存储器的阵列处理机和集中式共享存储器的阵列处理机。

1）分布式存储器的阵列处理机

控制部件CU:整个系统在CU控制下运行用户程序和部分系统程序的。所有指令都在控制部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件CU自己执行.

各处理单元:有局部存储器PEM存放被分布的数据。把适合并行处理的向量类指令“播送”给各个PE，控制那些活跃的PE并行执行。

互连网络(ICN):运算中，PE间可通过互连网络(ICN)来交换数据。互连网络的连通路径选择也由控制部件统一控制。

管理处理机SC:是一种通用机，用于管理系统资源，完成系统维护、输入/输出、用户程序的汇编及向量化编译、作业调度、存储分配、设备管理、文件管理等操作的功能。

阵列处理机是SIMD的主流。典型机器有ILLIACⅣ、MPP、DAP、CM-2、MP-1、DAP600系列等。 2）集中式共享存储器的阵列处理机

系统存储器是由K个存储分体集中组成，经互连网络ICN为全部N个处理单元所共享。

不同点;①互联网络所起作用不同；②信息在存储器中分布的要求不同。相同点：CU和SC功能相同。 互连网络的作用：用于在处理单元与存储器分体之间进行转接构成数据通路，希望各处理单元能高速灵活地动态与不同的存储分体相连，使尽可能多的PE能无冲突地访问共享的主存模块。

采用这种构形的典型机器有BSP。 2.阵列处理机的特点

①阵列处理机提高速度是利用资源重复，利用并行性中的同时性； ②处理单元同等地担负起各种运算，其设备利用率可能不那么高； ③速度提高在硬件价格大幅度下降情况下，潜力巨大；

④互连网络对系统性能影响显著；

⑤互连网络使阵列处理机比固定结构的单功能流水线灵活； ⑥阵列处理机结构和所采用并行算法紧密联系； ⑦阵列处理机还必须提高标量处理速度。 6.2 阵列处理机的并行算法 1.ILLIACⅣ的处理单元阵列结构

ILLIACⅣ是采用分布存储器构形。其中，PUi为处理部件，包含64位的算术处理单元PEi、所带的局部存储器PEMi和存储逻辑部件MLU。64个处理部件PU0～PU63排列成8×8的方阵，任何一个PUi只与其上、下、左、右4个近邻PUi-8、PUi+8、PUi-1和PUi+1直接相连。上下同一列两端的PU连成环，左右每一行右端的PU与下一行左端的PU相连，最下面一行右端的PU与最上面一行左端的PU相连，从而形成一个闭合的螺线形状，所以称其为闭合螺线阵列。普遍来讲，中，任意两个处理单元之间的最短距离不超过

步。

个处理单元组成的阵列

ILLIACⅣ的处理单元是累加器型运算器，把累加寄存器RGA中的数据和存储器中来的数据进行运算，结果保留在累加寄存器RGA中。每个处理单元内有一个数据传送寄存器RGR收发数据，实现数据在处理单元之间的传送，并有一个屏蔽触发器，用来控制让该PUi是否被屏蔽掉，使之不参与向量指令的操作。

6.3 SIMD计算机的互连网络 1.互连网络的设计目标与互连函数

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

2)问题：在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结

①操作方式：有同步、异步及同步与异步组合三种。现有的阵列处理机均采用同步操作方式，让所有PE

②控制策略：可以有集中或分布两种控制策略。多数现有的SIMD互连网络采用集中控制的策略。

③交换方法：主要有线路交换、包交换及线路与包交换组合三种。线路交换是在源和目的间建立实际的连接通路，一般适合于大批数据传输。包交换是将数据置于包内传送，不用建立实际的连接通路，对短数据信息传送特别有效。SIMD互连网络多采用硬连的线路交换，包交换则多用于多处理机和计算机网络中。

④网络的拓扑结构：有静态和动态两种。在静态拓扑结构中，两个PE之间的链是固定的，总线不能重新配置成与其他PE相连。而动态拓扑结构中，两个PE之间的链通过置定网络的开关单元状态可以重新配置。动态网络有单级和多级两类。

3) 互连函数：互联网络的连接规律可以用互联函数来表示，它反映了对于所有的入端0、1、…、j、…、N-1，同时存在入端j连至出端f(j)的函数对应关系。

2.基本的单级互连网络

基本的单级互连网络有立方体、PM2I、混洗交换网络3种。 1）立方体单级网络

连接规律：是在一个N维的立方体中所有各顶点之间边的连接规律；N个结点的立方体单级网络共有n=log2N种互连函数，即

单级立方体网络的最大距离为n，即反复使用单级网络，最多经n次传送就可以实现任意一对入、出端间的连接。

2）PM2I单级网络

PM2I单级网络是“加减2i”单级网络的简称。能实现与j号处理单元直接相连的是号为j±2i的处理单

元，即 式中，0≤j≤N-1,0≤i≤n-1,。它共有2n个互连函

数。由于PM2+(n-1)=PM2-(n-1),因此PM2I互连网络只有2n-1种互连函数是不同的。

PM2I单级网络最大距离为上取整[n/2]，最多只要两次使用，即可实现任意一对入、出端号之间的联接。

3）混洗交换单级网络

混洗交换单级网络包含两个互连函数，一个是全混，另一个是交换。N维全混互连函数表示为 ：

，式中,

为入端编号的二进

制码。由于单纯的全混互连网络不能实现二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数。这就是全混交换单级网络，

数据传送最多只需n次交换和n-1次混洗传送即可，其最大距离为2n-1。 3.基本的多级互连网络

最基本的多级互连网络就是由3种单级互连网络相对应组成的多级立方体互连网络、多级混洗交换网络、多级PM2I网络以及全排列网络。不同的多级互联网络，在所用的交换开关、拓扑结构和控制方式上各有不同。

1）多级立方体网络

多级立方体网络有STARAN网络、间接二进制n方体网络等。特点：交换开关用二功能，拓扑结构用立方体，控制方式可以有级控制、部分级控制和单元控制。

采用级控制方式的多级立方体网络称交换网络，它只能实现交换函数的功能。

采用部分级控制方式的多级立方体网络称移数网络；采用单元控制方式的多级立方体网络称间接二进制n方体网络。

2）多级混洗交换网络

多级混洗交换网络（omega网络），特点：交换开关用四功能的，拓扑结构为混洗，控制方式为单元控制。

3）多级PM2I网络

多级PM2I网络（数据变换网络），N个端子经n级连接，从入端到出端的级编号依次为n-1、n-2、。。。、1、0.每一级均把前后两列各N个单元以PM2I的拓扑互连。每一级控制信号有平控H、下控D和上控U信号分别控制这三类连接线。

若采用单元控制方式则称为强化数据变换网络ADM. 可以实现omega网络的全部连接，而且其组合数还要更多。

小结：这几种多级网络，灵活性由低到高的次序是：级控制立方体、部分级控制立方体、间接二进制n方体、omega、ADM,而复杂性和成本的次序也相应增高。

4）全排列网络

互连网络是从N个入端到N个出端的一到一的映射，即对N个端的重新排列。互连网络的功能是用新排列来置换N个入端原有的排列。

阻塞式网络：前几种基本多级网络都能实现任意一个入端与任意一个出端间的连接，但要同时实现两对或多对入、出端间的连接时，都有可能发生争用数据传送路径的冲突。

非阻塞式网络（全排列网络）：前几种基本多级网络都能实现任意一个入端与任意一个出端间的连接，能同时实现两对或多对入、出端间的连接时，没有发生争用数据传送路径的冲突网络。非阻塞式网络连接灵活，但连线多、控制复杂、成本高。

N个端的全部排列有N!种。可是，用单元控制的个开关，n级互连网络共用为2种排列。

实现的方法：一种方法根据循环多级互连网络的实现思路。只要对这个多级互连网络通行两次，此时全部开关的总状态数有NN/2·NN/2= NN种，足以满足N!种不同排列的开关状态要求。第二种方法将级的N个入端和N个出端的互连网络和它的逆网络连在一起，这样可以省去中间完全重复的一级，得到总级数为

级的全排列网络。

级间接二进制n方体网络，每级有N/2

个二功能的交换开关，这样，全部开关处于不同状态的总数

即NN/2种。当N为大于2的整数时，总有NN/2＜N!，就是说它无法实现所有N!

6.4并行存储器的无冲突访问

阵列处理机：为了存储器频宽要与多个处理单元的速率匹配，要求存储器采用多体并行组成；还要保证对数组访问的模式，存储器都能实现无冲突地访问工作。

对数组访问的模式：可能要访问数组的行、列、主对角线、次对角线的全部元素或其中某个子方阵。 1）一维数组的存储访问分析

问题：若遇到按2变址，访问奇数或偶数下标的元素时，则因访存冲突会使存储器的实际频宽降低一半。

解决办法：并行存储的分体数m应取成质(素)数，才能较好地避免存储器访问的冲突。只要变址跳距与m互质，存储器访问就总能无冲突地进行。

2）多维数组（二维数组）存储访问分析

①解决办法一：为了能使行或列的各元素都能并行访问，采取将数据在存储器中错位存放。但是该方案可造成主对角线上各元素的并行访问冲突，致使实际频宽下降一半，次对角线上各元素的访问则都发生冲突，使实际频宽降低成与串行一样。

②解决办法二：能满足上述这些要求的一种存储方案是使并行存储器分体数m大于每次要访问的向量或数组元素的个数n(n在阵列处理机上就是处理单元数)，且等于质数，同时在多维数组的行、列等方向上采取不同的错开距离。

同一列两个相邻元素地址错开的距离为

,同一行两个相邻元素地址错开的距离为

,

,当m取成

(P为正整数)时，实现无冲突访问的充分条件是让=1。对于这种无冲突访问的存储

方案，要求n×n二维数组A中的任意一个元素Aab应放在下列地址处：

③解决办法三：有n个处理单元的并行处理机，为了能并行访问n个元素，且适应任意规模的数组，可以先将多维数组或者非n×n方阵的二维数组按行或列的顺序变换为一维数组，形成一个一维线性地址空间，地址用a表示。然后，将地址a所对应的元素存放在体号地址n］下取整的单元中，就可以满足无冲突访问的要求。

BSP计算机就是采用类似这种映像规则存放的。它共有16个处理单元，选取的并行存储器分体数m为17。

,体内地址为i=INT［a/

第7章 多处理机

多处理机：是指有两台以上的处理机，共享I/O子系统，机间经共享主存或高速通信网络通信，在操作系统控制下，协同求解大而复杂问题的计算机系统。有同构型、异构型和分布型三种。

两个目的：①通过多台处理机对多个作业、任务进行并行执行来提高求解大而复杂问题的速度。②使用冗余的多个处理机，通过重新组织来提高系统的可靠性、适应性和可用性。

7.1多处理机的特点及主要技术问题

1.多处理机的基本特点：多处理机是属于多指令流多数据流(MIMD)的系统。多处理机则实现的是更高一级的作业或任务间的并行，是开发并行性中的并发性。结构上多个处理机用多个指令部件分别控制,通过机间互连网络通讯;算法上不只限于处理向量数组,还要实现更多通用算法中的并行;系统管理上要更多地依靠软件手段,有效解决资源分配和管理,特别是任务分配,处理机调度,进程的同步和通讯等问题.

2.多处理机与阵列处理机的差别

①结构灵活性。多处理机制结构灵活性高于并行处理机。

②程序并行性。并行处理机是操作级并行，并行性仅存在于指令内部，识别比较容易，由程序员掌握程序并行性的开发;多处理是指令、任务、作业并行，并行性主要存在于指令外部，另外还存在于指令内部，识别比较困难，必须利用多种途径开发程序的并行性。

③并行任务派生。并行处理机工作能否并行工作由指令决定，多处理机必须有专门指令指明程序能否并行执行，派生的任务数是动态变化的。

④进程同步。并行处理机的进程同步是自然的，而多处理机不一定必须采取同步措施。 ⑤资源分配和任务调度。多处理机的资源分配和任务调度比并行处理机复杂得多。 ⒊多处理机存在如下主要技术问题

①硬件结构上，如何解决好处理机、存储器模块及I/O子系统间的互连； ②如何最大限度的开发系统的并行性，以实现多处理机各级的全面并行； ③如何选择任务和子任务的大小，即任务的粒度，使并行度高，辅助开销小； ④如何协调好多处理机中各并行执行的任务和进程间的同步问题；

⑤如何将任务分配到多处理机上，解决好处理机调度、任务调度和资源分配，防止死锁； ⑥一旦某个处理机发生故障，如何对系统进行组织，不使其瘫痪；

⑦多处理机机数增多后，如何能给编程者提供良好的编程环境，减轻程序的复杂性。 7.2多处理机的硬件结构 1 紧耦合和松耦合

1）紧耦合多处理机是通过共享主存实现处理机间通信的；为减少访主存冲突，主存采用模m多体交叉存取；存储器模块数m应等于或略大于处理机数p。要解决好数据在各存储器模块中的分配和定位。各处理机可自带小容量局部存储器和再自带高速缓冲存储器Cache，可以减少处理机-存储器互连网络的使用冲突。

系统由P台处理机、m个存储器模块和d个I/O通道组成。通过处理机—存储器互连网络（PMIN）、I/O—处理机互连网络（IOPIN）和中断信号互连网络（ISIN）进行互连。

处理机-存储器互连网络：实现各处理机与各存储器模块的连接，存储器模块数m应等于或略大于处理机数p。

I/O-处理机互连网络：它来实现处理机和连接外设的I/O通道经通信。

中断信号互连网络：由一台处理机向另一台处理机发出中断信号来实现处理机间的进程同步。

紧耦合多处理机常用于并行执行作业中的多个任务，以提高系统的速度性能；即各处理机一般常采用同构对称型（即系统是多个同类型至少功能相同的处理机组成）的紧耦合多处理机。

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

非层次松耦合多处理机：典型的经消息传送系统互连的松耦合非层次型多处理机。该系统有N个计算机模块。每个计算机模块中有处理器CPU、Cache、局部存储器LM和一组I/O设备。还有一个通道和仲裁开关CAS与消息传送系统MTS接口，对两个或多个计算机模块同时请求访问MTS的某个物理段时进行仲裁。

是层次型总线式多处理机。

层次型松耦合多处理机：卡内基-梅隆大学设计的松耦合多处理机2. 机间互连形式

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

总线形式：处理机与外部存储器模块通过总线相连。结构简单、成本低、扩展性好；但总线失效敏感，存在总线争用。适合处理机较少、系统信息流量少、机数可扩充情况。

环形互连：各处理机点点相加成环。结构简单、成本低、不争用总线；但信息传输有延迟。适合处理机较少、使用高宽带的光纤通信、系统流量高、机数可扩充的情况。

交叉开关：用纵横开关阵列将存储器模块、I/O通道相连。不争用开关；但开关阵列复杂，设备量较大。适合处理机数较多（但不超过16）、系统流量大、处理机数可扩充的情况。

多端口存储器：将交叉开关移到存储器接口中。不争用总线，但存储器接口复杂，较难控制。适合处理机数少、不能扩充（一般是2台），系统流量高的情况。

开关枢纽结构：把交叉开关设置在各处理机或接口内部。所有开关枢纽数量少，可用较短路径与处理机连接；但开关枢纽较复杂。适合处理机数多、可扩充、分布结构情况。

7.3多处理机的并行性

多处理机并行性既存在于指令内部，也存在于指令外部；多处理机低层次的并行可通过向量化来实现，如利用面向SIMD的并行算法解决向量数组的并行运算。系统高层次的任务和作业的并行性主要靠算法、编译、语言及操作系统来开发。

1并行算法

并行算法的研究思路：将大的程序分解成可由足够多的并行处理的过程(进程、任务、程序段)。每个过程被看成是一个结点，将过程之间的关联关系用结点组成的树来描述。这样，程序内各过程之间的

关系就可被当成是一种算术表达式中各项之间的运算，表达式中的每一项都可看成是一个程序段的运行结果。因此，研究程序段之间的并行问题就可设想成是对算术表达式如何并行运算的问题。

并行算法的性能：用P表示可并行处理的处理机机数；用TP表示P台处理机运算的级数即树高；加速比SP表示单处理机顺序运算的级数T1与P台处理机并行运算的级数TP之比； EP表示P台处理机的设备利用率(效率)，EP= SP/P。SP≥1时，会使EP ≤1，即运算的加速总是伴随着效率的下降。

串行处理机习惯采用循环和迭代算法

多处理机并行算法实现（1）：应尽可能增大树中每一层的结点数，即增大树的广度，使各处理机可并行的过程数尽可能增大，以降低树的高度。当最大限度降低了树的高度之后，就应再缩小树的广度，使之在达到一定的加速比SP 之后如何减少机数P来减少多处理机效率的降低。

具体实现：先从算术表达式的最直接形式出发，利用交换律把相同的运算集中在一起。然后再利用结合律和分配律把参加这些运算的操作数配对，尽可能并行运算，从而组成树高为最小的子树。最后再把这些子树结合起来。

2.

①数据相关（先写后读）：如果Pi的左部变量在Pj的右部变量集内，且Pj必须取出Pi运算的结果来作为操作数，就称Pj“数据相关”于Pi 。不能并行和交换串行，只在特殊情况下可以交换串行。

②数据反相关（先读后写）：如果Pj 的左部变量在Pi 的右部变量集内，且当Pi 未取用其变量的值之前，是不允被Pj 所改变的，就称Pi “数据反相关”于Pj。可以并行执行，但必须保证其写入共享主存时的先读后写次序，不能交换串行。

③数据输出相关（写-写）：如果Pi 的左部变量也是Pj 的左部变量，且Pj 存入其算得的值必须在P

i

存入之后，则称Pj “数据输出相关”于Pi 。可以并行执行，但同样需保证其写入的先后次序，不能交

换串行。

若同时有先写后读和先读后写两种相关，以交换数据为目的时，则必须并行执行，且要求读写完全同步，不许顺序串行和交换串行；若没有任何相关，或仅有源数据相同时， 可以并行、 顺序串行和交换串行。

3 并行程序设计语言

基本要求：能使程序员在其程序中灵活方便的表示出各类并行性，能在各种并行/向量计算机系统中高效地实现。

并行进程的特点：这些进程在时间重叠地执行，一个进程未结束，另一个进程就开始。 并行任务的派生：使一个任务在执行的同时，派生出可与它并行执行的其它一个或多个任务，分配给不同的处理机完成。

并行任务的汇合：被派生的任务，可以相同的，也可以是不同的，执行时间可以相同，也可以不同，等它们全部完成后，再汇合起来进行后续的单任务或新的并行任务。

FORK语句：执行一个FORK m语句时，派生出标号为m开始的新进程， 具体来说，就是准备好这个新进程启动和继续执行所必需的有关信息；如果是共享主存，则应为它产生存贮器指针、映象函数和访问权数据；将空闲的处理机分配给被FORK语句派生的新进程，如果没有可用的空闲处理机，则应让它们排队等待； 继续在原分配给它的处理机上执行FORK

JOIN语句：JOIN语句附有一个计数器，其初始值置为0。每当执行JOIN n语句时，计数器的值加 1，并与n比较。若比较相等，表明这是执行中的第n个并发进程经过JOIN语句，于是允许该进程通过JOIN语句， 将计数器清0，在其所在的处理机上继续执行后续语句。若比较结果，计数器的值仍小于n， 则表明此进程不是并发进程中的最后一个，可让现在执行JOIN语句的这个进程先结束，把它所占用的处理机释放出来，分配给正在排队等待的其他任务。如没有排队等待的任务，则让该处理机空闲。

4．多处理机的性能

任务粒度的大小，会显著影响多处理机的性能和效率；任务粒度过小，辅助开销大，系统效率

低；粒度过大，并行度低，性能不会很高。因此，要合理选择任务粒度的大小，并使其尽可能的均匀，还要采取措施减少辅助开销，以保证系统性能随处理机数目的增大有较大的提高。

衡量任务粒度大小的一个依据是程序用于有效计算的执行时间E与处理机间的通信等辅助开销时间C的比值。只有E/C的值较大时， 开发并行性才能得到好处。

任务粒度还与系统的应用有关。图像及多目标跟踪因为机间通信开销少，宜于细粒度处理。要求冗长计算才能得到结果的题目，宜于粗粒度处理.

7.4多处理机的操作系统

多处理机操作系统有主从型、各自独立型及浮动型三种类型。

类型 构型 优点 缺点 适用场合 工作负荷固定，主从型 管理程序只在一台指定的处理上运行 硬件结构简单，控制简单 对主机的可靠性要求高，灵活性差 从处理机的能力明显低于主处理机 控制功能分散到多台处理机，共同完成对整适应分布处理的模块尽管每台处理机都有专用表格，但一些共享个系统的控制。每台处理机都有一个独立的化结构，对主机依赖性表格会增加共享冲突，加大了开销。实现复松耦合多处理机各自独立型 管理程序(操作系统的内核)在运行。要求管小，可靠性高，系统效杂，输入输出结构变换需要人为干预，处理系统 理程序必须是可再入的。 率较高 集中了主从型和各自浮动型 管理程序在处理机间浮动 独立型的优点，且灵活性高 设计最困难 机间负荷的平衡比较困难 紧耦合多处理机系统，同构多处理机系统 第8章 其它计算机结构

8.1脉动阵列处理机

8.1.1脉动阵列结构的原理

脉动阵列结构是由一组处理单元PE构成的阵列。每个PE的内部结构相同，一般由一个加法/逻辑运算部件或加法/乘法运算部件再加上若干个锁存器构成，可完成少数基本的算术逻辑运算操作。阵列内所有处理单元的数据锁存器都受同一个时钟控制。运算时数据在阵列结构的各个处理单元间沿各自的方向同步向前推进，阵列内部的各个单元只接收前一组处理单元传来的数据，并向后一组处理单元发送数据。只有位于阵列边缘的处理单元，才与存储器或I/O端口进行数据通信。

根据具体计算的问题不同，脉动阵列可以有一维线形、二维矩形/六边形/二叉树形/三角形等阵列互连构形。

脉动阵列结构具有如下一些特点：

②PE间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均简单规整。

③脉动阵列中所有PE能同时运算，具有极高的计算并行性，可通过流水获得很高的运算效率和吞吐率。

④输入数据被多个处理单元重复使用，减轻阵列与外界I/O通信量，降低系统对主存和I/O系统频宽的要求。

⑤脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI是不利的。

8.1.2通用脉动阵列结构

发展通用脉动阵列结构的途径主要有三种。

①通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序重新配置阵列的结构。

②用软件把不同的算法映像到固定的阵列结构上。这一方法依赖于面向并行运算所采用的程序语言、操作系统、编译程序和软件开发工具的设计。

③探寻与问题大小无关的脉动处理方法，以及VLSI运算系统的分割矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相应的设置方案。

8.2大规模并行处理机MPP与机群系统

8.2.1 大规模并行处理机MPP

发展背景：由于VLSI和微处理技术的发展，以及高科技应用领域对计算机和通信网络在计算、处

理和通信性能上不断提出更高的要求(极大的处理数据量、异常复杂的运算、很不规则的数据结构、极高的处理速度),使发展大规模的并行处理成了20世纪80年代中期计算机发展的热点。

大规模并行处理机：通过新的计算方法、存储技术、处理手段和结构组织方式，将数百至数千个高性能、低成本的RISC微处理器用专门的互连网络互连，组成大规模并行处理机MPP。这种处理机可进行中粒度和细粒度大规模并行处理，构成SIMD或MIMD系统。

优点：它具有性能价格比高和可扩展性好的优点。

8.2.2

机群系统是将多个高性能的工作站或高档微型计算机，使用高速的通信网络加以互连组成的系统。

实现对中、粗粒度并行进程的高效并行处理。机群系统中的主机和网络可以是同构的，也可以是异构的。主机间的通信主要采用消息传递。从结构和结点间的通信来看，是一种分布式存储方式，而从用户来看，表示出的是一个完整的并行系统。

机群系统如下几个明显的优点： ①系统有高的性能价格比。 ②系统的开发周期短。 ③系统的可扩展性好。

④系统的资源利用率高。 ⑤用户投资风险小。 ⑥用户编程方便。

8.3 数据流计算机

8.3.1数据驱动的概念

计数器控制驱动的控制流方式：它是VonNeumann型计算机的基本特点；在程序计数器集中控制下，顺次地执行指令，是以控制流方式工作。

特点：通过访问共享存储单元让数据在指令之间传递；指令执行的顺序性隐含于控制流中，但却可以显示使用专门的控制操作符来实现并行处理；指令执行的顺序受程序计数器控制，即是受控制令牌所支配。

数据驱动的数据流方式：只要一条或一组指令所要求的操作数全部准备就绪，就可立即激发相应的指令或指令组执行；执行结果的输出将送往等待这一数据的下一条或下一组指令。指令的执行基本上是无序的，完全受数据流的驱动，与指令在程序中出现的先后顺序无关。

特点：没有通常的共享变量的概念，即没有共享存储数据的概念；指令执行顺序只受指令中数据相关性的制约；数据是以数据令牌方式直接在指令之间传递的。

需求驱动的数据流方式：数据驱动计算，其操作是按输入数据可用性决定的次序进行；需求驱动计算，其操作则按数据需求所决定的次序进行。前者只要所要求的输入数据全部就绪，即可驱动操作执行，是一种提前求值的策略；而后者则是按需求值，只有当某一函数需要用到某一自变量时，才驱动对该自变量的求值操作，是一种滞后求值的策略。

从语义上讲，数据流是基于异步性和函数性的一种计算模型。 8.1.2数据流程序图和语言⒈数据流程序图

有向图来表示指令级的数据流程序，它可看成是数据流机器的机器语言。它有多个结点，并用一些弧把它们连接而成。每一个结点用圆圈或三角形或其他特殊符号表示，认为是一种处理部件，结点内的符号或字母表示一种操作。弧代表数据令牌在结点间的流向。

为了满足数据流机程序设计的需要，还需进一步引入许多常用的其它结点。这些结点可分别表示

利用上述这些结点，可以画出一些常见程序结构的数据流程序图。 P223 8.4解：

⒉.活动模片表示法

活动模片表示法：数据流实际上可以被看成是一组活动模片组成的集合体。每一个活动模片相应于数据流程序图中一个或多个操作结点，且由4个域组成。它们是一个操作码域，两个操作数域和一个目的域。

目前数据流控制机制的高级语言主要有单赋值语言和函数程序设计语言。另外，逻辑程序设计语言PROLOG这样一类的描述式语言，也可作为数据流机的高级语言。

8.3.3数据流计算机的结构

（1）静态数据流机的数据令牌无标号。动态数据流机的数据令牌有标号；

（2）静态数据流任意给定时刻当结点操作时每条弧上只能有一个数据令牌、动态数据流机中，任何一条弧上可出现多个不带目标号的数据令牌；

（3）静态数据流机中必须设控制令牌以满足要求，动态数据流机中不必须投控制令牌，因为令牌有识别时间、先后关系的标号；

（4）静态数据流机不支持递归的并发激活，只支持一般循环，动态数据流机支持递归的并发激活； （5）静态数据流机不需硬件完成标记的匹配，动态数据流机需要硬件将标记附加在数据令牌上，并完成对标记的匹配工作。

8.3.4数据流机器存在的问题

数据流计算机在提高并行处理效能上有着非常显著的长处，但也存在一些问题。

(1)数据流机是操作级上并行，但如果题目本身数据相关性很强，会使效率比传统的VonNeumann型机的还要低。

(2)数据流机中给数据建立、识别、处理标记，花费较多的辅助开销和存储空间。 (3)数据流机不保存数组。

(4)数据流语言的变量代表数值而不是存储单元位置，使程序员无法控制存储分配。 (5)数据流机互连网络设计困难，输入/输出系统仍不够完善。 (6)数据流机没有程序计数器，给诊断和维护带来了困难。

8.4 归约机

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

函数式语言：是由所有函数表达式的集合、所有目标(也是表达式)的集合及所有由函数表达式到目标的函数集合三部分组成的。

归约：如果给出了一个属函数表达式集合中的复杂函数的表达式，利用提供的函数集合中的子函数经过有限次归约代换之后，总可以得到所希望的结果，即由常量构成的目标。函数表达式的每一次归约，就是一次函数的应用，或是一个子表达式(子函数式)的代换(还原)。

归约机：针对函数程序设计语言的特点和问题来设计支持函数式程序运行的新计算机（归约机）。函数式程序本质上是属于解释执行方式，从函数式程序的归约来看，机器内部通常采用链表的存储结构，且依赖于动态存储分配，存储空间的大小无法预测，需要频繁地进行空白单元的回收，使空间、时间开销都较大，频繁的函数应用和参数传递，加上自变量动态取值，同样的计算往往要重复多次。

(1)归约机应当是面向函数式语言，或以函数式语言为机器语言的非Neumann型机器。

(2)具有大容量物理存储器和虚拟存储器，具备高效的动态存储分配和管理的软、硬件支持，满足归约机对动态存储分配及所需存储空间大的要求。

(3)处理部分应当是一种有多个处理器或多个处理机并行的结构形式，以发挥函数式程序并行处理的特长。

(4)采用适合函数式程序运行的多处理器互连的结构，最好采用树形的互连结构或多层次复合的互连结构形式。

(5)为减少进程调度及进程间通信开销，尽量把运行进程的结点机安排成紧靠该进程所需用的数据，并使运行时需相互通信的进程所占用的处理机也靠近，让各处理机的负荷平衡。

根据机器内部对函数表达式所用存储方式的不同，将归约方式分成串归约和图归约两类。 根据机器所用归约方式的不同，相应就有串归约机和图归约机两类。1979年，美国的Mago教授提出的细胞归约机FFP就是一种串归约机。墨西哥国立大学的Guzman等人提出的并行LISP机，就是图归约机。

8.5 智能机

智能机是具有智能的高性能计算机.它是一个知识信息的处理系统.智能机能不断地学习,积累,完善知识,利用知识进行推理,判断和求解问题的能力.它具有大容量的知识库；具有高度并行处理,多重处理和分布处理能力的多个处理机,是一种结构动态可变,易于扩充的开放式系统；提供有良好的人-机界面和多种智能接口。智能机中3个重要的组成部分是知识库机,推理机和智能接口处理机.