计算机系统结构(02325)

系统结构是对计算机系统中各级界面的定义以及其上下的功能分配。每级都有其自己的系统结构。计算机系统结构也称计算机系统的体系结构，它只是系统结构中的一部分，指的是传统机器语言级的系统结构。计算机系统结构研究的是软、硬件之间的功能分配以及对传统机器级界面的确定。为机器语言、汇编语言程序设计者或编译程序生成系统设计或生成的程序能在机器上正确运行提供应看到和遵循的计算机属性。

计算机结构的属性包括：

3、计算机组成

计算机组成：指的是计算机系统结构的逻辑实现，包括机器级内部的数据流和控制流的组成以及逻辑设计等。计算机组成要解决的问题：在希望达到的性能和价格情况下，如何更好、更合理地把各种设备和部件组织成计算机，实现所确定的系统结构。计算机组成设计主要是围绕提高速度，着重提高操作的并行度、重叠度，以及功能的分散和设置专用功能部件来进行的。

4、计算机实现

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

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

指令系统的确定属于计算机系统结构。
指令的实现，如取指令、指令操作码译码、计算机操作数地址，取数、运算、送结果等的操作安排和排序属于计算机组成。
实现这些指令功能的具体电路、器件的设计及装配技术属于计算机实现。

5、软、硬件取舍的基本原则

软、硬件的功能分配时计算机系统结构的主要任务，而软件和硬件在逻辑功能上又是等效的。从原理上讲，软件的功能可以用硬件或固件完成，硬件的功能也可以通过软件模拟完成，只是它们在性能、价格、实现的难以程度上是不一样的。一般来说：提高硬件功能的比例可以提高解题速度，减少程序所需的存储空间，但会增加硬件成本，降低硬件利用率和计算机系统的灵活性及适应性；提高软件功能的比例可降低硬件成本，提高系统的灵活性、适应性，但解题速度会下降，软件设计费用和所需的存储器用量增加。

软、硬件取舍的原则：

原则1：应考虑在现有的硬、器件（主要是逻辑器件和存储器件）的条件下，系统要有高的性能价格比，主要从实现费用、速度和其他性能要求来综合考虑。
原则2：要考虑到准备采用和可能采用的组成技术，使之尽可能不要过多或不合理的限制各种组成、实现技术的应用。
原则3：不能仅从“硬”的角度考虑如何便于应用组成技术的成果和便于发挥器件技术的发展，还应从“软”的角度把如何编译和操作系统的实现以及高级语言程序的设计提高更多、更好的硬件支持放在首位。

考虑如何使软件和硬件功能的分配更合理：

硬件实现优点：速度较快，性能好；缺点：不灵活，适应性差。
软件实现优点：设计容易，修改容易，有灵活的适应性；缺点：速度，性能低。

6、计算机系统的定量原理

哈夫曼压缩原理：尽可能加速处理高概率的事件远比加速处理概率很低的事件对性能的提高要显著。例如，CPU在运算中发生溢出的概率很低，为此，设计时可以考虑加快不溢出时的运算速度，而对溢出时的速度不予考虑。
Amdahl(阿姆达尔)定律：定义系统性能的加速比：加快某部件执行速度所获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比。
程序访问的局部性定律：程序访问的局部性包括时间上和空间上的两个局部性。时间上的局部性：现在在使用的信息可能不久还要使用；空间上的局部性：最近的将来要用到的信息很可能于现在正在使用的信息在程序位置上是临近的。

7、计算机系统的设计方法

“由上往下”设计，也称“由顶向低”设计：先考虑如何满足应用的需求，定好面向应用的那个虚拟机器级的特性和工作环境，如要用到的基本命令、指令等，再逐级地向下设计，每设计下一级都要考虑对上一级是优化的。（面向应用高效，无法适用于通用件的设计，串行设计，周期长）
“由下往上”设计，也称“由底向顶”设计：它是先不管应用要求，只根据目前能用的器件，参照、吸收已有各种机器的特点，将微程序机器级（如果采用微程序控制）和传统机器级研制出来。然后，加配适用于不同应用领域的多种操作系统和编译系统软件，如多种分时操作系统和多种高级语言的编译程序，传统称为配软件，使应用人员可以根据不同的语言类型、数据形式，采用合适的系统软件和算法来满足应用的需要。(串行设计，周期长)
“从中间开始”设计：选择从层次结构的主要软、硬件界面开始设计，即在传统机器语言机器级于操作系统机器级之间进行合理的软、硬件功能分配。这是通用机一般采用的方法。它可以克服“由上往下”和“由下往上”两种设计方法中，软、硬件设计分离和脱节的致命缺点。（并行设计，缩短周期）。软件人员依次设计操作系统级、汇编语言级、高级语言级和应用语言级;硬件人员依次设计传统机器语言机器级、微程序机器级和数字逻辑级。

8、计算机设计的步骤

需求分析：度系统的应用环境、所用语言的种类特性、进行技术经济分析和市场分析等。
根据需求分析写出需求说明书。
进行概念设计：对机器级界面，如数据表示、指令系统、寻址方式等进行细致的定义和设计，同时提供几种方案，以便选择和比较。
通过模拟、测试，反复对所设计的系统进行优化和性能评价。

9、软件、应用、器件的发展对系统结构的影响

软件发展对系统结构的影响：软件相对于硬件来说，成本越来越高；产量和可靠性的提高越来越困难；软件生产效率低；软件排错比编写难。因此，程序设计者一般不愿意，也不应该在短时间里按新的系统结构、新的指令系统去重新设计软件。
应用的发展对系统结构的影响：不同的应用对应计算机系统结构的设计提出了不同的要求。用户角度：机器的应用范围越宽越好，希望在一台机器上能同时支持科学计算、事务处理和实时控制等，应用目的的发生改变时不必重新购置机器；应用需求时促进计算机系统结构发展的最根本动力。
器件的发展对系统结构的影响：电子管(1945-1954)->晶体管(1955-1964)->小规模集成电路(LSI:1965-1974)->大规模集成电路(VLSI:1974-1990)->微处理器(1990-2000)。器件的发展改变了逻辑设计的传统方法。过去，逻辑设计主要是逻辑化简，节省门的个数、门电路的输入端及门电路的级数，以节省功耗、降低成本、提高速度。但对于VLSI来说，这样做反而使设计收起延长，组成实现不规整，故障诊断困难，机器产量低，这些都将使成本反而增大。计算机的设计也从过去只进行全硬的逻辑设计发展到现在所用的软硬结合方式进行计算机辅助设计和辅助制造。

10、实现软件的移植技术

软件的可移植性：软件在不修改或只经少量修改就可由一台机器迁移到另一台机器上运行，同一软件可应用于不同环境。

统一高级语言：高级语言是面向题目和算法的，与机器的具体结构关系不大。统一高级语言可以解决结构相同或完全不同的机器间的软件移植，但目前难以解决，只能做得相对统一。
采用系列机：由同一厂家生产的具体相同系统结构，但具体不同组成和实现的一系列不同型号的机器。系列机是当前普遍采用的方法，但只能实现同一系统内的软件兼容，虽然允许发展、变化，但兼容的约束反过来会阻碍系统结构取得突破性的进展。
模拟：B机器的每条机器指令用A机器的一段机器语言程序解释，如同A机器上也有B机器的指令系统一样，这种用机器语言程序解释实现软件移植的方法称为模拟；模拟方式灵活可实现不同系统间的软件移植，但结构差异太大时，效率、速度会急剧下降。
仿真：用微程序直接解释另一种机器指令系统的方法就称为仿真。仿真方式在速度上损失小，但不灵活，只能在差别不大的系统之间使用，否则效率也会过低且难以仿真，需与模拟结合才行。

仿真和模拟的区别：

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

仿真和模拟的选择：

不同系列间的软件移植一般都是仿真和模拟并行。宜用仿真：频繁使用的易于仿真的机器指令易用仿真，以提高速度。宜用模拟：很少使用的、难以仿真的指令及I/O操作宜用模拟。

11、系统结构中的并行概念与开发

并行性包括同时性和并发性二重含义。同时性：两个或多个事件在同一个时刻发生。并发性：两个或多个事件在同一时间间隔内发生。

开发并行性的目的是为了能并行处理，以提高计算机解题的效率。

并行性开发的途径：

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

12、并行性的等级

从计算机系统执行程序的角度来看，并行性等级由低到高可以分为四级：

指令内部：一条指令内部各个微操作之间的并行执行。
指令之间：多条指令的并行执行。
任务或进程之间：多个任务和进程的并行执行。
作业或程序之间：多个作业或程序的并行执行。

从计算机系统中处理数据的角度来看，并行性等级从低到高可以分为四级：

位串字串：同时只对一个字的一位进行处理，这通常是指传统的串行单处理机，没有并行性。
位并字串：同时对一个字的全部位进行处理，这通常是指传统的并行单处理机，开始出现并行性。
位片串字并：同时对许多字的同一位(称为片)进行处理，开始进入并行处理领域。
全并行：同时对许多字的全部或部分位组进行处理。

并行性是贯穿于计算机信息加工的各个步骤和阶段的，从这个角度看，并行性等级可以分为：

存储器操作并行：可用单体单字、多体单字或多体多字方式在一个存储周期内访问多个字，进而采用按内容访问方式在一个存储周期内用位片串字并或全并行方式实现对存储器中大量字的高速并行比较、检索、更新、变化等操作。（相连处理机）
处理器操作步骤并行：指令的取指、分析、执行，浮点加法的求阶差、对阶、尾加、舍入、规格化等操作，执行步骤在时间上重叠流水地进行。（流水线处理机）
处理器操作并行：通过重复设置大量处理单元，让它们在同一控制器控制下按同一指令要求对向量、数组中各元素同时操作。（阵列处理机）
指令、任务、作业并行：这是较高级的并行。指令级以上的并行是多个处理机同时对多个条指令和相关的多数据组进行处理，操作级并行是对同一条指令及其相关的数据组进行处理。前者属于多指令流数据流计算机，后者属于单指令流多数据流计算机。

13、计算机分类（弗林分类法）

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

SISD(单指令流单数据流)系统：是传统的单处理器计算机，指令部件每次只对一条指令译码，只对一个操作部件分配数据，均属于SISD系统。
SIMD(单指令流多数据流)系统：单条指令流控制多个处理单元同时执行，每个处理单元包括处理器和相关数据存储，一条指令事实上控制了不同的处理器对不同的数据进行操作。
MISD(多指令流单数据流)系统：一个数据流被传送给一组处理器，通过这一组处理器的不同指令操作最终得到处理结果。
MIMD(多指令流多数据流)系统：多个处理器对各自不同的数据集同时进行不同的指令流。

14、数据表示与数据结构

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

数据结构：反映了应用中要用到的各种数据元素或信息单元之间的结构关系。数据结构是要通过软件映像，变换成计算机中所具有的数据表示来实现的。

高级数据表示：

自定义数据表示：标志符数据表示、数据描述符
向量、数组数据表示：
堆栈数据表示：

标志符数据表示：在处理运算符和数据类型的关系上，高级语言和机器语言差别很大，为缩短高级语言与机器语言的这种语义差距，让计算机中每一个数据都带类型标志位，这种数据表示称为标志符数据表示。标志符数据表示的主要优化：简化了指令系统和程序设计；简化了编译程序；便于实现一致性校验；能有硬件自动变换数据类型；支持数据库系统的实现与数据类型无关的要求，是程序不用修改即可处理多种不同类型的数据；为软件调试和应用软件开发提供了支持。

数据描述符：数据描述符和标志符的差别：标志符是和数据相连的，合存在一个存储单元总，表示单个数据的类型特征；数据描述符则是与数据分开存放的，用于描述所要访问的数据是整块的还是单个的，访问该数据块或数据元素所需要的地址以及其他信息等。数据描述符的作用：对向量、数组、记录等数据，由于元素属性相同，为进一步减少标志符所占的存储空间。

向量、数组数据表示：为向量、数组数据结构的实现和快速运算提供更好的硬件支持的方法是增设向量、数组数据表示，组成向量机。

堆栈数据表示：堆栈数据结构在编译和子程序调用中很有用。有堆栈数据白送的计算机称为堆栈计算机。堆栈计算机表现于：由高速寄存器组成的硬件堆栈，并附加控制电路，让它与主存总的堆栈区在逻辑上构成整体，使堆栈的访问速度是寄存器的，容量是主存的；有丰富的堆栈操作指令且功能很强，可直接对堆栈中的数据进行各种运算和处理；有力地支持了高级语言程序的编译；有力支持了子程序的嵌套和递归调用。

15、引入数据表示的原则

原则1：看系统的效率是否有显著提高，包括实现时间和存储空间是否显著减少。实现时间是否减少又主要看在主存和处理机之间传送的信息量是否减少。传送的信息量越少，实现的时间就越少。
原则2：看引入这种数据表示后，其通用性和利用率是否提高。如果只是对某种数据结构的实现效率很高，而对其他数据结构的实现效率很低，或者引入这种数据表示在应用中很少用到，那么为此所消耗的硬件过多却并未在性能上得到好处，必然导致性能价格的下降，特别是一些复杂的数据表示。

16、浮点数尾数下溢的处理方法

截断法：将尾数超出计算机字长的部分截去。优点：实现最简单，不增加硬件，不需要处理时间；缺点：由于误差大，平均误差大且无法调节，因而很少使用。
舍入法：在计算机运算的规定字长之外增设一位附加位，存放溢出部分的最高位，每当进行尾数下溢处理时，将附加位加1。优点：实现简单，增加的硬件很少，最大误差小，平均误差接近于零；缺点：处理速度慢，需要花费在数的附加位加1及因此产生进位的时间。
恒置“1”法：将计算机运算的规定字长的最低位恒置为“1”。优点：实现最简单，不需要增加硬件和处理时间，平均误差趋于0。缺点：最大误差最大，比截断法的还要大。
查表舍入表：用ROM或PLA存放下溢处理表，k位地址使用尾数最低的k-1位和准备舍掉的最高位状态，读出的内容就是对应的k-1位的下溢处理结果。优点：ROM查表舍入法速度较快，平均误差可调节为0，是较好的方法。缺点：硬件量大，不过随着器件价格的下降和集成度的改进，使用将会增多。

17、程序在主存中的定位技术

当程序装入主存是，就需要进行逻辑地址空间到物理地址空间的变换，即进行程序定位。逻辑地址：程序员在编程用的地址。物理地址：程序在主存中的实际地址。

静态再定位：在目的程序装入主存时，由装入程序用软件方法把目的程序的逻辑地址变换成物理地址，程序执行时，物理地址不再改变，称这种定位技术为静态再定位。
动态再定位：执行每条指令时才形成主存物理地址的方法称为动态再定位。指令不修改，通过基址寻址法来解决。
虚拟地址映射表：采用虚拟存储器增加了映像表硬件后，使程序空间可以超过实际主存空间。

18、指令系统设计的原则及一般步骤

指令系统的设计包括指令的功能（操作类型、寻址方式和具体操作内容）和指令格式的设计。编译程序设计者要求指令系统应设计具有：

规整性：对相似的操作做相同的规定。
对称性：例如：有A-B->A，同时应有A-B->B；
独立性和全能性：如果有多种程序选择实现同一种功能，为减少编译时哪种实现好的分析，应限定操作只能有一种选择方式。
正交性：指令中各个不同含义的字段，如操作类型、数据类型、寻址方式等，在编码时应互不相关，相互独立。
可组合性：让指令系统中所有操作对各种寻址方式和数据类型都能适用。
可扩充性：要留有一定数量的冗余操作码，以便以后扩充新指令。

设计新指令的一般步骤：

根据应用，初拟出指令的分类和具体的指令；
试编出该指令系统设计的各种高级语言的编译程序；
对各种算法编写大量的测试程序并进行模拟测试，看指令系统的操作码和寻址方式效能释放都比较高
将程序中高频出现的指令串合改成一条强功能的新指令，即改用硬件方式实现；将频度很低的指令的操作改成用基本的指令组成的指令串来完成，即用软件的方式实现。

19、存储系统的基本要求

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

系统对存储器性能的要求：

存储器速度能和CPU匹配
容量上能放下所有系统软件及多个用户软件
存储器的价格只能占整个计算机硬件价格中一个较小而合理的比例

为了弥补CPU与存储器在速度上的差距：

途径1：在组成上引入并行和重叠技术，构成并行主存系统，在保持每位价格基本不变的情况下，使主存的频宽得到较大的提高。
途径2：从系统上改进，发展存储体系

20、并行主存系统

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

单体单字存储器：一个字长为W位的单体主存，一次可访问一个存储器字。

单体多字存储器：主存在一个存储周期内疚可以读出4个CPU字，相当于CPU从主存中获得信息的最大速率提高为原来的4倍。

多体单字：

多体多字：

21、中断系统

CPU正在执行的程序，转去处理随机提出的请求，待处理完，再回到原先被打断的程序继续恢复执行的过程称为中断。相应和处理各种中断的软、硬件总体称为中断系统。

中断分为：内部中断、外部中断和软件中断。内部中断由CPU内的异常引起；外部中断由中断信号引起，分为可屏蔽中断和不可屏蔽中断；软件中断由软件自陷指令引起，拥有共操作系统服务。

异常：由执行现行指令引起的暂停事件，如运算结果溢出、页面失效等属于异常，一般不能屏蔽，应予以相应和处理。

中断：专指那些与当前进程运行无关的请求暂停的事件，如机器故障中断请求、外设中断请求、定时器中断请求等。中断可以被屏蔽，未被相应的中断源保留在中断字寄存器中，直至屏蔽解除后仍可得到相应和处理。

中断系统的功能：中断请求的保存和清除、优先级的确定、中断断点及现场的保存、对中断请求的分析和处理以及中断返回等。

22、总线系统

总线是用于互联计算机、CPU、存储器、I/O接口及外围设备、远程通信设备间信息传送通路的集合。总线与其相配合的附属控制电路统称为总线系统。

总线的分类：

按总线允许信息传送的方向分为：单向传输和双向传输两种。双向传输有半双向传输和全双向传输的不同。半双向传输可沿相反方向传送，但同时只能向一个方向传送。全双向传输允许同时向两个方向传送，全双向传输的速度快，造价高，结构复杂。
总线按用法可分：专用和非专用两类。专用总线，只连接一对物理部件；非专用总线，可以被多种功能或多个部件分时共享，同一时间只有一对部件可使用总线进行通信。

专用总线的优缺点：

优点：多个部件可以同时收/发信息，不争用总线，系统流量高；通信时不用指明源和目的，控制简单；系统可靠，任何总数的失效只会使连接该总线的两个部件不能直接通信，但它们仍可通过其他部件间接通信。
缺点：总线数多，成本高；专用总线的时间利用率低；专用总线不利于系统模块化，增加一个部件要增加许多新的接口和连线。

非专用总线的优缺点：

优点：总线数少，造价低；总线接口标准化、模块性强；可扩充能力强，部件的增加不会使电缆、接口和驱动电路激增；易用多重总线来提高总线的带宽和可靠性，使故障弱化。
缺点：系统流量小，经常会出现争用总线的情况，使未获得总线使用权的部件不得不等待而降低效率。如果处理不当，总线有可能成为系统速度性能的瓶颈，对单总线结构尤其如此；共享总线失效会导致系统瘫痪。

总线的控制方式

非专用总线上所挂多个设备或部件如果同时请求使用总线，就得由总线控制机构按某种优先次序裁决，保证只有一个高优先级的申请者首先取得对总线的使用权。总线的控制方式有：集中式控制和分布式总线控制。

集中式控制：总线控制机构基本集中在一起，无论是在连接到总线的一个部件中，还是在单独的硬件中，都称为集中式控制。集中式总线控制有串行链接、定时查询和独立请求3种方式。

分布式总线控制：总线控制逻辑分散连到总线的各个部件式，就称为分布式总线控制。

总线的通信技术

当获得了总线的使用权后，还必须给出通信的是“源”还是“目的”部件，以及传送信息的类型和方向等信息，之后才能开始真正的数据信息的传送。总线的通信技术有同步通信和异步通信两种。

异步通信：部件间的信息传送有定宽、定距的系统时标同步。优点是：信息的传送速率高，受总线长度的影响小。缺点是：时钟在总线上的时滞可能会造成同步误差，时钟线上的干扰信号容易引起误同步，总线操作都必须以同样的时钟频率进行。

异步通信：采用应答方式，没有公共时钟标准。异步通信分为：单向源控制和请求/回答双向控制两种。

23、I/O系统

I/O系统包括：输入/输出设备、设备控制器、与输入/输出操作相关的软、硬件。

输入/输出系统发展的3个阶段：程序控制I/O、直接存储器访问（DMA）及 I/O处理机。

I/O处理机方式包括：通道方式和外围处理机方式。

通道处理机输入/输出的主要过程：

进入管态：CPU相应此中断请求后，转向该管理程序入口，进入管态。
编制通道程序：管理程序根据广义指令中所提供的参数编制通道程序。
选择通道和设备：
执行通道程序：
CPU处理中断：
再返回目态，继续目态程序的运行。

24、虚拟存储器的管理方式

虚拟存储器通过增设地址映像表机构来实现程序在主存中的定位。将程序分割成若干段或页，用相应的映像表指明该程序的某段或某页是否已装入主存。若已装入，同时指明其在主存中的起始地址；若未装入，就去辅存中调段或调页，装入主存后在映像表中建立好程序空间与实存空间的地址映像关系。程序执行时通过查映像表将程序地址变换成主存地址再访问主存。根据存储映像算法的不同，虚拟存储器的管理方式主要有段式、页式和段页式三种。

1）段式管理：将主存按段分配的存储管理方式称为段式管理。程序都有模块性：一个复杂的大程序总可以分解成多个在逻辑上相对独立的模块，这些模块可以是主程序、子程序或过程，也可以是数据块。每个模块都是一个单独段，都以该段的起点为0相对编址。当某个段有辅存调入主存时，只要系统赋予该段一个基址（即该段存放在主存中的起始地址），就可以有基址和单元在段内的相对位移形成在主存中的实际地址。

段表：为了进行段式管理，每道程序在系统中都有一个段（映射）表来存放该道程序各段装入主存的状况信息。段表本身也是一个段，一般常驻主存中，也可以存在辅存中，需要时再调入主存。段表有段名（段号）、地址、装入位、段长和访问方式组成。

段名：用于存放段的名称，一般时有逻辑意义的，也可以转换成用段号指明。
地址：用于表示该段装入主存的起始（绝对）地址，当装入位为“0”时，则无效。
装入位：用来指示该段是否已经调入主存，“1”表示已装入，“0”表示未装入。
访问方式：用来标记该段允许的访问方式，如只读、可写、只能执行等，以提供段的访问方式保护。

分段管理优点：

分段方法能使大程序分模块编制，从而可使多个程序员并行编程，缩短编程时间，在执行或编译过程中对不断变化的可变长段也便于处理；
各个段的修改、增添并不影响其他各段的编制，各用户以段的连接形成的程序空间可以与主存的时间容量无关；
分段还便于几道程序共用主存内的程序和数据，不必再主存中重复存储，只需把它们按段存储，并在几道程序的段表中有公共段的名称及同样的基址即可；
由于各段使按其逻辑特点组合的，容易以段为单位实现存储保护。

段式管理的问题：

段式存储中各段装入主存的起点使随意的，段表中的地址字段很长，必须能表示出主存中任意一个绝对地址，加上各段长度随意，段长字段也很长。这既增加了辅助硬件的开销，降低了查表速度，也使主存管理麻烦。
段式管理和存储还会带来大的段间零头浪费。

2）页式管理：把主存空间和程序空间都机械地等分成固定大小的页（页面大小随计算机而异，一般再512B到几KB之间），按页顺序编号。这样，任一主存单元的地址Np就由实页号Nv和页内位移Nr两个字段组成。每个独立的程序也有自己的虚页号顺序。

页式管理的优点：页式对应用程序员完全透明，所需映像表硬件较少，地址变换的速度快，调入操作简单等方面都优于段式。

页式管理的不足：页式不能完全消除主存可用区的零头浪费，因为程序的大小不可能恰好就是页面大小的整数倍。产生的页内零头虽然无法利用，但其浪费比段式的要小得多，所以在主存空间利用率上，页式也是优于段式。

3）段页式管理：把实（主）存机械地等分成固定大小的页，程序按模块分段，每个段又分成与主存页面大小相同的页。每道程序通过一个段表和相应的一组页表进行定位。

在虚拟存储器中，每次访问一次主存都要进行一次程序地址向实（主）存地址的转换。段页式的主要问题式地址变换过程至少需要查表两次，即查段表和页表。因此，要想使虚拟存储器的速度接近于主存，必须在结构上采取措施，以便加快地址转换中查表的速度。

25、虚拟存储器的地址映射和变换

地址的映射：将每个虚存单元按某种规则（算法）装入（定位于）实主存，建立起多用户虚地址Ns于实（主）存地址Np之间的对应关系。

地址的变换：指程序按照这种映像关系装入实存后，在执行中，如何将多用户虚地址Ns变换成对应的实地址Np。

全相联映像：由于虚存空间远大于实存空间，页式虚拟存储器一般都采用让每道程序的任何虚页可以映像装入到任何实页位置的全相联映像，全相联映像的实页冲突概率低。它用页表作为地址映像表，故称之为页表法。

26、虚拟存储器的页面替换算法

页面替换算法要解决的问题：当处理机要用到的指令或数据不在主存时，会生产页面失效，这时需要去辅存中将含该指令或数据的一页调入主存。通常虚存空间比主存空间大得多，必然会出现主存已满又发生页面失效的情况，这时将辅存的一页调入主存会发生实页冲突，只有强制腾出主存中的某个页才能接纳由辅存中调来的新页。选择主存中哪个页作为被替换的页，就是替换算法要解决的问题。

替换算法正确的依据：是否有高命中率；算法是否便于实现；辅助软、硬件成本是否低。

页面替换算法：

随机算法(RAND)：用软的或硬的随机数产生主存中要被替换页的页号。这种算法简单，易于实现，但没有利用主存使用的“历史”信息，反映不了程序的局部性，使主存命中率很低，因此已不采用。
先进先出算法(FIFO)：选择最早装入主存的页作为被替换的页。这种算法实现方便，只要在操作系统为主存管理所设的主存页面表中给每个实页配一个计数器字段，每当一页转入主存时，让该页的计数器清零，其他已装入主存的那些页的计数器都加“1”。需要替换时，计数器最大的页的页号就是最先进入主存而现在准备替换的页号。先进先出算法虽然利用了主存使用的历史信息，但不一定能正确的反映程序的局部性，因此最先进入的页很可能时现在经常在用的页。
近期最少使用算法(LRU)：选择近期最少访问的页作为被替换页。优点：这种算法能比较正确地反映程序的局部性，一般来说，当前最少使用的页，未来也将很少被访问。不足：完全按此算法实现比较困难，需要为每个实页都分配一个字长很长的计数器。改进：对其进行变形，把近期久未访问的页作为被替换页，将”多“和”少“变成”有“和”无“，实现就方便多了。
优化替换算法(OPT)：近期最少使用和近期最久未用过两种算法都是LRU法，与FIFO法一样，都是根据页面使用的历史信息情况来预估未来的页面使用情况。如果能根据未来实际使用情况将未来近期里不用的页替换出去，一定会有最高的主存命中率，这种算法称为优化替换算法（Optimal,OPT）。优化替换算法是一种理想算法，可以被用来作为评价其他替换算法好坏的标准，看哪种替换算法的主存命中率最接近于优化替换算法的主存命中率。

替换算法一般是通过用典型的页地址流模拟其替换过程，再根据所得到的命中率的高低来评价其好坏，影响命中率的因素除替换算法外，还有地址流、页面大小和主存容量等。

27、虚拟存储器工作过程

在页式虚拟存储器中，每当用户用虚地址访问主存时，都必须查内页表，将多用户虚地址变换成主存的实地址。
在查内页表时，如果对应该虚页的装入位为”1“，就取出其主存页号Nv并接上业内位移Nr，形成主存实地址Np后访问主存。
如果对应该虚页的装入位为”0“时，表示该虚页未在主存中，就产生页面失效，程序换道经异常处理从辅存中调页。这时需查外页表，完成外部地址变换。
在查外页表时，若该虚页装入位为”0“，表示该虚页尚未装入辅存，产生辅存缺页故障，由海量存储器调入；
若查外页表时，改虚页装入位为”1“，就将多用户虚地址变换成辅助中的实块号，告诉I/O处理器到辅存中去调页，而后经I/O处理器送入主存。
一旦发生页面失效，还虚页确定调入页应进入主存中的哪一页位置，这就需要操作系统查主存页面表。
若占用位为”0“，表示主存未装满，因为是全相联映像，只需要找到任何占用位为”0“的一个位置即可。
若占用位全为”1“，表示主存已装满，就需要通过替换算法寻找替换页。

28、高速缓冲存储器

高速缓冲存储器：为了弥补主存速度的不足，在处理器和主存之间设置一个高速、小容量的Cache，构成Cache-主存存储层次，使之从CPU角度来看，速度接近于Cache，容量却是主存的。

Cache工作原理：

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

Cache的特点：

速度快：访问Cache的时间一般是访问主存时间的1/10~1/4，只要Cache命中率足够高，就能接近于Cache的速度来访问大容量的主存。
容量小

29、高速缓冲存储器的地址映像与变换

地址的映像：将每个主存块按某种规则装入Cache中。

地址变换：每次访Cache时怎样将主存地址变换成Cache地址。

映像规则选择的依据：

所用的地址映像和变换硬件是否速度高、价格低和实现方便。
块冲突概率是否低。块冲突：指出现了主存块要进入Cache中的位置已被其他主存块所占用了。
Cache空间利用率是否高

地址映像和变换类型：

全相联映像和变换：主存中任意一块都可映像装入到Cache中任意一块位置。优点：块冲突概率低，只有当Cache全部装满才可能出现块冲突，所以Cache的空间利用率最高。缺点：要构成容量为项的相联存储器，其代价太大，而且Cache容量很大时，其查表速度很难提高。
直接映像及其变换：把主存空间按Cache大小等分成区，每区内的各块只能按一一对应到Cache的相对应块位置上，即主存第i块之恶能唯一映像到定i mod 块位置上。优点：成本低，节省所需硬件，只需要较小的按地址访问的区号标志表存储器和少量外比较电路；节省时间，访问Cache与访问区号表、比较区号是否相等的操作时同时进行的，当Cache命中时意味着省去了地址变换的时间。缺点：Cache的块冲突概率很高，只要有两个或两个以上经常使用的块恰好被映像到Cache同一块位置时，就会使Cache命中率急剧下降；即使此时Cache中有大量空闲块也无法利用。
组相联映像及变换：将Cache空间和主存空间都分成组，每组为S块，各组之间是直接映像，而组内各块之间是全相联映像。

30、三级存储体系

物理地址Cache：物理地址Cache是由”Cache-主存“和”主存-辅存“两个独立的存储层次组成。CPU用程序虚地址访存，经存储管理部件中的地址变换部件变换成主存物理地址访Cache，如果命中Cache，就访Cache；如果不命中，就将该主存物理地址的字和含该字的主存的一个块与Cache某相应块交换，而所访问的字直接与CPU交换。
虚地址Cache：虚地址Cache是将Cache-主存-辅存直接构成三级存储层次形式。CPU访存时，直接将虚地址送存储管理部件MMU和Cache，如果Cache命中，数据与指令直接与CPU传送；如果Cache不命中，由存储管理部件将虚地址变换成主存物理访问主存，将含该地址的数据块或指令块与Cache交换的同时，将单个指令和数据与CPU之间传送。
全Cache：全Cache是最近出现的组织形式，尚不成熟，尚未商品化。它没有主存，只用Cache与辅存中的一部分构成”Cache-辅存“存储体系。全Cache存储系统的等效访问时间要接近于Cache的，容量是虚地址空间的容量。

31、重叠方式

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

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

取指令：按指令计数器的内容访主存，取出该指令送到指令寄存器。
分析：对指令的操作码进行译码，按寻址方式和地址字段形成操作数真地址，并用此真地址去取操作数，为取下一条指令还要形成下一条指令的地址。
执行：是对操作数进行运算、处理，或存储运算结构。

加快标量处理机的机器语言的解释方法：

通过选用更高速的器件，采用更好的运算方法。
通过控制机构能同时解释两条、多条以至整段程序的方式，加快整个机器语言程序的解释。重叠和流水是其中常用的方式。

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

为了实现两条相邻指令在时间上重叠解释，首先需要付出空间代价，如增设数据总线、控制总线等；其次要处理号指令之间的关联，如转移的处理，指令相关等。

32、流式方式

一次重叠是把一条指令的解释分为两个子过程，即分析和执行。流水是重叠的引申，是把一条指令的解释分为更多的子过程，每个子过程可以与其他子过程同时进行。流水处理将”分析“子过程分为：取指令、指令译码、取操作数，并改进运算器的结构，以加快其“执行”子过程。

一次重叠可同时解释2条指令；流水处理可同时解释4条指令。

标量流水处理机的性能主要是吞吐量、加速比和效率：

吞吐率：流水线单位时间里能流出的任务数或结果数。
最大吞吐率：流水线达到满负荷状态后可获得的吞吐率。
加速比：流水方式相对非流水顺序方式速度提高的比值。
效率：流水线的效率是指流水线中设备的实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。

流水线中经过时间最长的子过程称为瓶颈子过程。为了提高流水线的最大吞吐率，首先要找出瓶颈，然后设法消除此瓶颈。消除瓶颈的办法：

将瓶颈子过程再细。
子过程不能再细分是，通过重复设置多套瓶颈段并联，让它们交叉并行。

影响吞吐率和效率提高的因素很多：

静态多功能流水线按某种功能流水时，总有一些基本概念用不到的段处于空闲；
流水建立时，本功能要用到的某些段也有部分处于空闲；
功能切换时，增加了前一功能流水的排空时间及后一功能流水的建立时间；
经常需要等待把上一步计算的结果输出回授到输入，才能开始下一步的计算。

标量流水线只有连续不断地流动，不出现断流，才能获得高效率。造成流水线断流的原因：

编译形成的目标程序不能发挥流水结构的作业
存储系统供不上连续流动所需的指令和操作数
出现了相关和中断。

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

先写后读相关：一般一个指令流水线中读的操作在前，写的操作在后。若是流入流水线的一段指令中，先流入的指令的写入结果的目的地址与后流入的指令的读取操作的源地址是同一个寄存器或者是存储单元的时候，可能会发生当后流入的指令达到读的操作的时候，先流入的指令还没有进行写操作。
写-写相关：如果前后两条指令的写操作的目的地址一样，如果先流入的还没有进行写操作，后流入的已经进行写操作，就会存在“写－写”相关。
先读后写相关：先流入的指令读取操作数的源地址和后流入的指令的写入结果的目的地址是同一个寄存器或者是存储单元，如果后流入的写操作先于先流入的指令读操作，就会发生“先读后写”相关。

全局性相关：转移指令和其后的指令之间存在关联，使之不能同时解释，其造成的对流水机器的吞吐率和效率下降的影响比局部性相关严重的多。如：一条指令是条件转移指令，有两个分支，应该执行哪个分支的指令，这就出现了全局性相关。全局性相关的处理方法：

使用猜测法：猜测其中一个分支继续流入，待条件码形成后再决定是否继续执行还是作废，按另一分支重新流入。
加快和提前形成条件码：尽快、尽早获得条件码，以便提前知道流向哪个分支，会有利于流水机器简化对条件转移的处理。
采取延迟转移：这是用软件方式进行静态指令调度的技术。不必增加硬件，在编译生成目标指令程序时，将转移指令与其前面不相关的一条或多条指令交换位置，让成功转移总是延时到这一条或多条指令执行之后再执行。这样，可使转移造成的流水性能损失减少到0。
加快断循环程序的处理

中断：中断会引起流水线断流，但出现概率比条件转移的概率要低很多，且又是随机发生的，所以，流水机器中断主要使如何处理号断点现场的保存和恢复，而不是如何缩短流水线的断流时间。流水机器的中断处理办法：

不精确断点法：无论指令i在流水线的哪一段发生中断，未进入流水线的后续指令不再进入，已在流水线的指令继续流完，然后才转入中断处理程序。这样，断点不一定使i,而可能是i+1,i+2…即断点是不精确的。当指令i在第1段响应中断时，断点才是精确的。
精确断点法：无论指令i是在流水线中哪一段响应中断，给中断处理程序的现场全都是对应i的，i之后流入流水线的指令的原有现场都能保存和恢复。

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

超标量处理机：假设一条指令包含取指、译码、执行、存结果4个子过程，每个子过程经过时间为Δt。常规的标量流水线处理机是在每个Δt期间解释完一条指令，这种流水机的度m=1。超标量处理机：采用多指令流水线，每个Δt同时流出m条指令（称为度）。度为3的超标量处理机，每3条指令为一组。超标量流水线处理机非常适合于求解像稀疏向量或稀疏矩阵这类标量计算问题。
超长指令字处理机：超长指令字结构式将水平型微码和超标量处理两者结合。指令字长可达数百位，多个功能部件并发工作，共享大容量寄存器堆。优点：每条指令所需拍数比超标量处理机的少，指令译码容易，指令级并行性较高。不足：VLIW处理机能否成功，很大程度取决于代码压缩的效率，其结构的目标码于一般的计算机不兼容；指令字很长而操作段格式固定，经常使指令字中的许多字段没有操作，浪费存储空间。
超流水线处理机：超流水线处理机着重开发时间并行性，在公共的硬件上采用较短的时钟周期，深度流水来提高速度，需使用多相时钟，时钟频率高达100~500MHz。
超标量超流水线处理机：超标量超流水线处理机是超标量流水线和超流水线处理机的结合。

34、向量处理机

向量处理机是有向量数据表示的处理机，分向量流水处理机和阵列处理机两类：向量流水处理机是以时间重叠途径开发的；阵列处理机是以资源重复途径开发的。向量内部各元素（分量）很少相关，且一般又是执行同一种操作，容易发挥流水线的效能。可将向量数据表示和流水线结合构成向量流水处理机，以提高面向向量数组计算类应用的计算机的速度性能。

向量的流水处理：

横向（水平）处理方式：逐个求出结果向量的各个元素。如果在ASC多功能静态流水处理机上实现，加、乘相间的运算每次都得进行流水线功能的切换，流水线的吞吐率就会降低。横向（水平）处理方式，宜于在标量处理机上用循环程序实现。
纵向（垂直）处理方式：先对所有元素执行一种相同运算，再对所有元素执行另一种相同的运算。
分组纵横处理方式：若向量的长度N太长，超出了向量寄存器组种的寄存器个数，可以将该向量分割成若干组，使每组都能装得进向量寄存器组中。这样，每一组内均按纵向方式处理，而组和组之间则采用软件方法编制循环程序的方式依次循环处理。

向量横向处理时向量的处理方式，但不是向量的流水处理方式；而向量纵向处理和分组纵横处理既是向量的处理方式，也是向量的流水处理方式。

通过并行、链接提高性能：一般可采取让多个流水线功能部件并行，流水线链接，加快条件语句和稀疏矩阵处理，加快向量的归约操作等办法来提高向量流水处理的性能。前两者主要是加快相邻向量指令的执行，后两者主要是让循环向量化。

链接技术是提高计算机整体运行速度的一个非常重要的措施。

35、阵列处理机的构形和特点

阵列处理机有分布式存储器阵列处理机和集中式共享存储器阵列处理机两种构形，差别主要在于存储器的组成方式和互连网络的作用不同。

阵列处理机的特点：阵列处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列技术问题位背景发展起来的，这些计算问题利用多个处理单元对向量或数组包含的各个分量同时计算，从而易于获取很高的处理速度。

阵列处理机于流水线处理机相比：

阵列处理机利用的是资源重复，而不是时间重叠；利用的是并行性中的同时性，而不是并发性；
阵列处理机提高速度主要是高增大处理单元数，比起向量流水处理机主要靠缩短时钟周期来说，速度提高的潜力要大得多。
阵列处理机使用简单、规整的互连网络来确定处理单元间的连接。互连网络的结构形式限定了阵列处理机可用的解题算法，也会对系统多种性能指标产生显著影响，因此，互连网络的设计是重点。
阵列处理机在机间互连上比固定结构的单功能流水线灵活，使相当一部分专门问题上的工作性能比流水线处理机高得多，专用性强得多。

阵列处理机实质上是由专门应对数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列的控制及标量处理机和专门从事系统输入/输出及操作系统管理的处理机组成的一个异构型多处理机系统。

ILLIAC IV的并行算法举例：

矩阵加：阵列处理机解决矩阵加是最简单的一维情况。两个8×8的矩阵A、B相加，所得到的结果矩阵C也是一个8×8的矩阵。
矩阵乘：矩阵乘是二维数组运算，比矩阵加要复杂。
累加和：这是一个将N个数的顺序相加转为并行相加的问题。

36、SIMD计算机的互连网络

互连网络：是一种由开关元件按一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。在SIMD计算机中，处理单元和处理单元或存储分体之间要通过互连网络进行信息交换。

SIMD系统的互连网络设计目标：

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

互连网络应抉择的问题：

操作方式：操作方式有同步、异步、同步及异步组合3中方式。阵列处理机根据其SIMD性质，均采用同步操作方式，让所有PE按时钟同步操作。多处理机多采用异步或同步和异步组合方式。
控制策略：典型的互连网络由许多开关单元和互连线路组成的，互连通路的路径选择使通过置定开关单元的工作状态来控制的。控制策略由集中和分布两种。
交换方式：线路交换、包交换、线路域包交换组合。
拓扑结构：互连网络入、出段可用连接的模式，有静态和动态两种。动态网络主要有动态单机网络和动态多级网络两类。

38、基本的单极互连网络

立方体：立方体的每个顶点（网络的结点）代表一个处理单元，共有8个处理单元，用zyx三位二进制码编号。它所能实现的入、出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编号的某一位取反的其他3个处理单元上。如：010只能连到000、011、110。
PM2I：PM2I单级网络是“加减2i”单级网络的简称。能实现与j号处理单元直接相连的是号为j±2i的处理单元。
混洗交换：混洗交换单级网络包含两个互连函数：全混和交换。
蝶形单极网络：互连函数为：Butterfly（Pn-1Pn-2…P1P0）＝P0Pn-2…P1Pn-1；即将二进制地址的最高位和最低位相互交换位置。

39、基本的多级互连网络

多级立方体网络：
多级混洗交换网络——omega网络：
多级PM2I网络：
基准网络：
多级交叉网络：
多级蝶式网络：
全排列网络：

40、动脉阵列流水处理机

为了满足要求计算机量很大的信号/图像处理及科学计算的特定算法的需要，提出了脉动阵列结构的脉动阵列处理机的思想，它对特定问题具有极高的计算并行性，是一种解题速度很高的处理机。

脉动阵列处理机的特点：

结构简单、规整，模块化强，可扩充性好，非常合适用超大规模集成电路实现
PE间数据通信距离短、规则，是数据流和控制流的设计、同步控制等均简单规整
脉动阵列中所有PE能同时运算，具有极高的计算并行性，可通过流水获取很高的运算效率和吞吐率。
脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI是不利的。

不同的算法往往要求能有不同的阵列结构，以及大小不同的阵列，为了克服脉动阵列结构通用性差的弱点，今年来已研究和发展了一些可有效执行多种算法的较为通用的脉动阵列结构，发展通用脉动阵列结构的途径主要有3种：

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

41、多处理机

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

使用多处理机的目的：

通过多台处理机对多个作业、任务进行并行执行来提高解题速度，从而提高系统的整体性能
使用冗余的多个处理机通过重新组织来提高系统的可靠性、适应性和可用性。

多处理机属于多指令流多数据流（MIMD）系统，与单指令流多数据流的阵列处理机差别主要来源于并行性的等级不同，阵列处理机主要是针对向量、数组处理，实现向量指令操作级的并行，是开发并行性中的同时性；多处理机实现的则是更高一级的作业或任务间的并行，是开发并行性中的并发性。

对多处理机的要求：

在硬件结构上，它的多个处理机要用多个指令部件分别控制，通过共享主存或机间互连网络实现异步通信。
在算法上，不限于向量、数组处理，还要挖掘和实现更多通用算法中隐含的并发性。
在系统管理上，要更多地依靠操作系统等软件手段，有效地解决资源分析和管理，特别是任务分配、处理机调度、进程的同步和通信等问题。

多处理机的结构、机间互连、并行算法、并行语言、编译、操作系统等都将会直接影响到系统的性能和效率。

42、多处理机的硬件结构

紧耦合多处理机：紧耦合处理机是通过共享主存处理机间通信的，其通信速率受限于主存频宽。各处理机与主存经互连网络连接，处理机数受限于互连网络带宽及各处理机访主存冲突的概率。减少访主存冲突的方法：

主存采用模m多体交叉存取。模数m越大，发生冲突的概率越低，但要解决好数据在各存储器模块中的分配和定位。
各处理机可自带小容量局部存储器存放该处理机运行进程的核心代码和常用系统表格，以进一步减少访主存冲突。
处理机还可以自带高速缓冲存储器Cache，以减少访主存次数。

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

松耦合多处理机：松耦合多处理机中，每台处理机都有一个容量较大的局部存储器，用于存储经常用的指令和数据，以减少紧耦合系统中存在的访主存冲突。不同处理机间或者通过通道互连实现通信，以共享某些外围设备；或者通过消息传送系统来交换信息，这时各台处理机可带有自己的外围设备。

松耦合多处理机的特点：

消息传送系统经常采用分时总线或环形、星形、树形等拓扑结构。
松耦合多处理机较适合做粗粒度的并行计算。
处理的作业分割成若干相对对立的任务，在各个处理机上并行，而任务间的信息流量较小。
当各处理机任务间交互作用很少时，这种耦合度很松的系统是很有效的，可看成是一个分布系统。

松耦合多处理机可分为：非层次型和层次型两种构形。

43、多处理机机间互连形式

多处理机机间互连的形式是决定多处理机性能的一个重要因素。在满足高通信速率、低成本的条件下，互连还应灵活多样，以实现各种复杂的乃至不规则的互连而不发生冲突。

总线形式：多个处理机、存储器模块和外围设备通过接口与公用总线相连，采用分时或多路转接技术传送。单总线方式结构简单、成本低，系统增减模块方便。但对总线的失效敏感，处理机机数增加会增大总线冲突概率，使系统效率急剧下降。提高总线形式的系统效率方法：一是用优质高频同轴电缆来提高总线的传输速率，如进一步使用光纤通信；二是用多总线方式来减少访总线的冲突概率。为了解决多各处理机同时访问公用总线的冲突算法有：静态优先级、固定时间片、动态优先级、先来先服务等多种总线仲裁算法。
环形互连形式：为保持总线互连的优点（结构简单、造价低、可扩充性好），同时又能克服其不足（总线性能和可靠性受物理因素制约），可以考虑构造一种逻辑总线，让各台处理机之间点点相连成环状，称为环形互连。在这种多处理机上，信息的传递过程是由发送进程将信息送到环上，经环形网络不断向下一台处理机传递，直到此信息又回到发送者为止。环形互连形式适合于有高速通信的光纤通信。环形互连形式的缺点：信息在每个接口处都会有一个单位的传输延迟，当互连的处理机机数增加时，环中的信息传输延迟将增大。优点：即使网上处理机机数很多，通信负载很重，都不会出现像总线互连那样使系统带宽急剧下降的情况，系统的带宽仍保持一个高值。
交叉开关形式：但总线互连结构简单，但争用总线现象严重。交叉开关形式则不同于但总线。它用纵横开关阵列将横向的处理机P及I/O通道与纵向的存储器模块M连接起来。交叉开关形式互连网络不争用开关，可以大大展宽互连传输频带，提高系统效率，但整个交叉开关阵列非常复杂，硬件成本高。
多端口存储器形式：如果每个存储器模块有多个访问端口，将分布在交叉开关矩阵中控制、转移和优先级仲裁逻辑分别移到相对应存储器模块的接口中，就构成了多端口存储器形式的结构。多端口存储器形式的中心使多端口存储器模块。每个存储器模块的相应端口连接在一起，每一个端口负责处理一个处理机或I/O通道的访问请求。每个存储器模块按照对它的各个端口指定的优先级分解对它的访问冲突。多端口存储器形式端口数不宜太多，且一经做好就不容易改变，这对多处理机都是不利的。
蠕虫穿洞寻径网络：机间采用小容量缓冲存储器，用于消息分组寻径存储转发。在蠕虫网络中，将消息分组又分割成一系列更小的小组，同一分组中所有小组以异步流水方式按序不间断传送，并且同一分组中的所有小组，只有头部的小组知道其所在整个分组传送的目的地，用硬件方式进行传送的应答。
开关枢纽结构形式：参照多端口存储器的思想，把互连结构的开关设置在处理机或接口内部，组成分布式结构，称为开关枢纽结构形式。

理想的拓扑结构应该是：所用开关枢纽数量少，每个开会枢纽的端口数不多，能以较短的路径把数量很多的处理机连接起来，实现快速而灵活的通信；不改变模块本身的结构，就可以使系统规模得到任意扩充。

多处理机存储器的组织：多处理机的主存一般都是采用由多个模块构成的并行存储器。由M各存储器模块构成的并行存储器，存储单元的地址是按交叉方式编址的，这种地址交叉编址的方式主要由低位交叉和高位交叉两种。

44、紧耦合多处理机多Cache的一致性问题的产生

为了解决价格合理的大容量主存的访问速度低于处理机速度一个数量级的现实问题，系统在各处理机和主存之间，通常配置有一个高速缓冲存储器Cache。一致性问题产生的原因：

共享可写的数据：在多处理机中，由于每个处理机都有自己专用的Cache，当主存中同一个信息块在多个Cache中都有时，就会出现多个Cache之间的相应信息块的内容不一致的问题。
进程迁移：在多处理机上，为了提高系统的效率，有时还允许进程迁移，将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行。因为被迁移的进程中最近修改过的信息只保留在原处理机的Cache中，迁到新的处理机后，该进程就会使用主存中已过期的旧信息，使进程不能正确地得到恢复而出错。
I/O传输：当系统发绕过Cache的输入/输出操作时，也会导致多个Cache块之间及Cache与主存对应块的内容不一致。

45、紧耦合多处理机多Cache的一致性问题解决方法

解决进程迁移引起的多Cache不一致：

可以通过禁止进程迁移的方法予以解决；
也可以通过进程挂起时，靠硬件方法将Cache中该进程改写过的信息块强制写回主存相应位置的方法解决。

以硬件为基础实现多Cache的一致性：

监视Cache协议法：这是最普遍采用的方法（写作废法、写更新法），各个处理机中的Cache控制器随时都监视着其他Cache的行为。监视Cache协议方法实现简单，但只是适用于总线互连的多处理机。
目录法：目录法药建立一个目录表，目录表中的每一项记录一个数据块的使用情况，有了这个目录表后，一个处理机在写入自身Cache的同时，只需要有选择地通知其他存有此数据块的Cache将副本作废或更新即可。目录表的具体做法可分为：全映像目录表、有限目录表法和链式目录表法三种。

以软件为基础实现多Cache的一致性：软件为基础的做法都是靠软件来限制的，不把一些公用的可写数据存入Cache中。该方法的优点是可以降低硬件的复杂性，降低对互连网络通信量的要求，因而性价比较高；其缺点是软件的可靠性及编译程序的编写困难。比较适合用于多处理机数多的多处理机。

46、多处理机并行算法的定义和分类

定义：并行算法是指可同时执行的多个进程的集合，各进程可相互作用、协调和并发操作。

分类：

按运算基本对象：数值型和非数值型。数值型：基于代数运算，如：矩阵运算、多项式求值、线性方程组；非数值型：基于关系运算，如：选择、排序、查找、字符处理。
按并行进程间的操作顺序：同步型、异步型和独立型。同步型并行算法是指并行的各进程间由于相关，必须顺序等待；异步型并行算法是指并行的各进程间执行相互独立，不会因相关而等待，只是根据执行情况决定中止或继续；独立型并行算法是指并行的各进程间完全独立，进程之间不需要相互通信。
按各处理机计算任务的大小：细粒度、中粒度和粗粒度。细粒度并行算法一般指向量或循环级的并行；中粒度并行算法一般指较大的循环级并行，并确保这种并行的好处可以补偿因并行带来的额外开销；粗粒度并行算法一般是指子任务级的并行。

一般多程序多数据流的多处理机上运行的进程之间是异构性的，在单程序多数据流的多处理机上运行的多个并行进程则是同构性的。

47、多处理机的操作系统

包含并行性的程序在多处理机上运行时，需要有相应的控制机构来实现处理机的分配和进程调度、同步、通信，存储系统的管理，文件系统的管理及某处理机或设备故障时系统的重组，这主要是经多处理机操作系统用软件手段来实现的。

多处理机操作系统的基本特点：

应具有程序执行的并行性；
操作系统功能的分布性；
机间通信与同步性；
系统的容错。

多处理机操作系统可以分为：主从型、各自独立型和浮动型3类。

主从型操作系统：管理程序只在一个指定处理机（主处理机）上运行，该处理机可以是专门的执行管理功能的控制处理机，也可以是与其他从处理机相同的通用机，除执行管理功能外，也能做其他方面的应用。优点：主从型操作系统的结构比较简单；整个管理程序只在一个处理机上运行，除非某些需递归调用或多重调用的公用程序，一般都不必是可再用的；只有一个处理机访问执行表，不存在系统管理控制表格的访问冲突和阻塞，简化了管理控制的实现；实现起来简单、经济、方便，是目前大多数多处理机操作系统采用的方式。缺点：对主处理机的可靠性要求很高；一旦发生故障，很容易使整个系统瘫痪，这时必须由操作员干预才行；整个系统显得不够灵活，同时要求主处理机必须能快速执行其管理功能，提前等待请求，以便及时为从处理机分配任务，否则将使从处理机因长时间空闲而显著降低系统的效率。

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

各自独立型操作系统：各自独立型操作系统是将控制功能分散给多态处理机，共同完成对整个系统的控制工作。每台多处理机都有一个独立的管理程序（操作系统的内核）在运行，即每台处理机都有一个内核的副本，按自身的需要及分配给它的程序需要来执行各种管理功能。由于多台处理机执行管理程序，要求管理程序必须是可再入的，或对每台处理机提供专用的管理程序副本。优点：很适合分布处理的模块化结构特点，减少对大型控制专用处理机的需求；某个处理机发生故障，不会引起整个系统瘫痪，有较高的可靠性；每台处理机都有其专用控制表格，使访问系统表格的冲突较少，也不会有许多公用的执行表，同时控制进程和用户进程一起进行调度，能取得较高的系统效率。缺点：实现复杂；某台处理机一旦发生故障，要想恢复和重新执行未完成的工作比较困难；每台处理机都有自己专用的输入/输出设备和文件，使整个系统的输入/输出结构变换需要操作员干预；各处理机负荷的平衡比较困难；各台处理机需有局部存储器存放管理程序副本，降低了存储器的利用率。

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

浮动型操作系统：浮动型操作系统使介于主从型和各自独立型操作系统之间的一种折中方式，其管理程序可以在处理机之间浮动。优点：各类资源可以较好地做得符合平衡；它在硬件结构和可靠性上具有分布控制的优点，而在操作系统的复杂性和经济性则接近于主从型。缺点：浮动型操作系统设计最为困难。

浮动型操作系统适用于紧耦合多处理机，特别是公共主存和I/O子系统的多个相同处理机组成的同构多处理机。

48、多处理机的发展

分布式共享存储器多处理机：
对称多处理机：
多向量多处理机
并行向量处理机
大规模并行处理机
机群系统

49、传统冯*诺依曼型计算机

传统的Von Neumann(冯*诺依曼)型计算机采用控制驱动方式，在程序计数器集中控制下，顺序地执行指令，无论是流水线机、阵列机或多处理机，本质上仍是指令在计数器控制下顺序执行，这就很难最大限度地发掘出计算机的并行性。

虽然顺序程序可以通过一些派生（如FORK）、汇合(如JOIN)类的语句提高程序执行的并行度，但会增加操作控制的复杂性和程序执行的辅助开销，这在一定程度上又会抵消程序并行所带来的好处。开发并行性的另一种方式：改用数据驱动的数据流方式来工作。数据驱动的数据流方式指的是，只要一条或一组指令所要求的操作数全部准备就绪，就可以立即激发相应的指令或指令组执行，执行结果的输出将送往等待这一数据的下一条或下一组指令。

50、数据流计算机

数据流计算机属于非冯*诺依曼型计算机，使用数据流语言，基于数据驱动。数据驱动的数据流计算机特点：在这种计算机上不需要程序计数器；指令的执行基本上是无序的，完全受数据驱动，与指令在程序中出现的先后顺序无关，也就是说，部分有序的操作也不是由程序员指定的，而是受数据相关制约；程序设计者完全摆脱了检查和定义程序中所有可能存在的并行性这一繁重的工作；只要数据不相关和资源可以利用，就可以并行，因而最有利于计算机并行性的开发。

数据流计算机存在的问题：

数据流计算机的主要目的是为了提高操作级并行的开发水平，但如果题目本身数据相关性很强，内涵并行性成份不多时，就会使效率反而比传统的冯*诺依曼型机的还要低。
在数据流计算机中为给数据建立、识别、处理标记，需要花费较多的辅助开销和较大的存储空间。但如果不用标记，则无法递归并会降低并行管理。
数据流计算机不保存数组。在处理大型数组时，会因复制数组造成存储空间的大量浪费，增加额外数据传输开销。
数据流语言的变量代表数值，而不是存储单元位置，时程序员无法控制存储分配。
数据流计算机互连网络数据困难，输入/输出系统仍不够完善。
数据流计算机没有程序计数器，给诊断和维护带来了困难。

51、归约机

归约机属于非冯*诺依曼型计算机，数据流计算机采用数据驱动，执行的操作序列取决于数据的可用性，归约机则是需求驱动，执行的操作序列取决于对数据的需求，对数据的需求又来源于函数式程序设计语言对表达式的归约。

归约机结构的特点：

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

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/138136.html