爱华网标签：校园
分类：工作篇
并行计算机
随着计算机应用的不断深入和扩展，需要速度更快、性能更高的计算机系统。虽然超大规模集成电路技术的发展极大地提高了计算机器件的速度，从而使计算机系统的性能大幅度提高。但是，仍然满足不了当前对更高性能计算机系统的需要。人们基于并行处理的思想，开辟了并行处理和并行处理计算机的研究领域。本章对并行处理、并行计算及相关知识作概念性的介绍。
2.4.1并行处理
并行处理是信息处理的一种有效形式，主要是运用了“并行性”（Parallels）的概念。所谓并行性是指在同一时刻或在同一时间间隔内完成两种或两种以上性质相同或不相同的工作，并行性是指时间上的重叠。严格地说，并行性可分为同时性和并发性两种，同时性是指两个或多个事件在同一时刻发生，并发性则是两个或多个事件在同一时间间隔内发生。
提高计算机系统处理速度的重要措施是增加处理的并行性，其途径是采用“时间重叠” 和“资源重复”两种主要的方法。时间重叠是指多个处理过程在时间上互相错开，轮流重叠地使用同一套硬件设备的各个部分，以加速硬件周转，赢得时间，提高处理速度，如流水线计算机。资源重复是采用重复设置硬件设备的方法来提高计算机的处理速度，如多处理机系统。计算机系统结构向高性能发展的趋势是：一方面在单处理机内部广泛采用多种并行性技术，另一方面发展多处理机系统，而两方面互相结合运用。
目前，世界上已经开发了许多不同种类的并行计算机系统，可分别实现以下四个级别上的并行处理：
(1) 作业或程序级并行；
(2) 任务或过程级并行；
(3) 指令级并行；
(4) 指令内部级并行。
作业是用户提交给计算机执行的一个计算任务。它可能包含几个程序的顺序执行，也可能包含几个程序的并行执行。作业或程序级的并行是通过作业调度与分配算法实现的，这是由操作系统的功能实现的并行；而指令内部级并行常直接用硬件方法来实现。
计算机的基本工作过程是执行一串指令，对一组数据进行处理。通常，把计算机执行的指令序列称为“指令流”，指令流调用的数据序列称为“数据流”，把机器同时可处理的指令流或数据流的个数称为“多重性”。根据指令流和数据流的多重性可将计算机系统分为下列四类：
(1) 单指令流单数据流（SISD：Single Instruction Stream Single Data Stream）。这类计算机只有一个指令部件，一次只对一条指令译码，并且只对一个操作部件分配数据。目前多数串行计算机都属于SISD计算机系统。
(2) 单指令流多数据流（SIMD：Single Instruction Stream Multiple Data Stream）。这类计算机有多个处理单元，它们在同一个控制部件的管理下执行同一条指令，并向各个处理单元分配各自需要的不同数据。
(3) 多指令流单数据流（MISD：Multiple Instruction Stream Single Data Stream）。这类计算机包含多个处理单元，同时执行多条指令对同一数据及其中间结果进行不同的处理。至今尚未见过这类计算机。
(4) 多指令流多数据流（MIMD：Multiple Instruction Stream Multiple Data Stream）。这类计算机系统内有多个处理机，实际上是多个独立的SISD计算机的有机的集合，它们同时运行多个程序并对各自的数据进行处理。多处理机属于这类计算机系统。网络计算机系统可划归MIMD类型。
并行计算机体系结构
并行计算机的分类及基本结构(采用扩展的Flynn分类): 1.SIMD(单指令多数据流) SM--Vector Pipelined 向量流水计算机 DM--Processor Array SIMD阵列机 2.MIMD(多指令多数据流) SM--SMP(UMA) 对称式多处理机UMAUniform-memory-access VSM--cc-NUMA NonUniform-memory-access DM MPP大规模并行处理机 BeoWulf SMP cluster 其中,MIMD中的又分两类 共享存储型:具有统一的地址空间,任何一个处理器都可以直接访问到存储空间中的第一个存储单元. UMA 物理存储器被所有处理机均匀共享，所有处理机对所有存储字具有相同的存取时间. cc-NUMA 访问时间随存储字的位置不同而变化. COMA只用高速缓存的多处理机远程高速缓存访问则借助于分布高速缓存目录进行. 分布式存储型:不具有统一的地址空间,每个处理器只能访问部分存储资源.
《高性能计算之并行编程技术-MPI并行程序设计》
都志辉
李三立
陈渝刘鹏
第1章并行计算机
采用并行计算的优点：加快速度，节省投入，打破物理极限的约束。
按指令与数据划分：
SIMD单指令多数据并行计算机,MIMD多指令多数据并行计算机
SIMD计算机同时用相同的指令对不同的数据进行操作,数组或向量运算特别适合在SIMD并行计算机上执行.
MIMD计算机同时有多条指令对不同的数据进行操作.
SPMD(Single-Program Multuple-Data)单程序多数据并行计算机,MPMD(Multiple-Program Multiple-Data)多程序多数据并行计算机
一般地,SPMD并行计算机是由多个地位相同的计算机或处理器组成的;而MPMD并行计算机内计算机或处理器的地位
是不同的,根据分工的不同,它们擅长完成的工作也不同,因此可以根据需要将不同的程序(任务)放到MPMD并行计算机上执行,使得这些程序协调一致地完成给定的工作.
按存储方式划分：
共享内存和分布式内存是两种基本的并行计算机存储方式。除此之外，分布式共享内存也是一种越来越重要的并行计算机存储方式。
共享内存的并行计算机：各个处理单元通过对共享内存的访问来交换信息、协调各处理器对并行任务的处理。对这种共享内存的编程，实现起来相对简单，但共享内存往往成为性能特别是扩展性的重要瓶颈。
分布式内存的并行计算机：各个处理单元都拥有自己独立的局部存储器，由于不存在公共可用的存储单元，因此各个处理器之间通过消息传递来交换信息、协调和控制各个处理器的执行，这是本书介绍的消息传递并行编程模型所面对的并行计算机的存储方式。不难看出，通信对分布式内存并行计算机的性能有重要的影响，复杂的消息传递语句的编写成为在这种并行计算机上进行并行程序设计的难点所在。但是，对于这种类型的并行计算机，由
于它有很好的扩展性和很高的性能，它的应用非常广泛。
分布式共享内存的并行计算机：结合了前两者的特点，是当今新一代并行计算机的一种重要发展方向，对于目前越来越流行的机群计算（Cluster Computing）大多采用这种形式的结构。通过提高一个局部结点内的计算能力使它成为所谓的“超结点”不仅提高了整个系统的计算能力，而且可以提高系统的模块性和扩展性，有利于快速构造超大型的计算系统。
《高性能计算之并行编程技术-MPI并行程序设计》
都志辉
李三立
陈渝刘鹏
第2章并行编程模型与并行语言
并行编程模型：
数据并行编程模型：编程级别比较高，编程相对简单，但它仅适用于数据并行问题。
将相同的操作同时作用于不同的数据，因此适合在SIMD及SPMD并行计算机上运行，在向量机上通过数据并行求解问题的实践也说明数据并行是可以高效地解决一大类科学与工程计算问题的。
它提供给编程者一个全局的地址空间，一般这种形式的语言本身就提供并行执行的语义，因此对于编程者来说只需要简单地指明执行什么样的并行操作和并行操作的对象，就实现了数据并行的编程。比如对于数组运算，使得数组B和C的对应元素相加后送给A，则通过语句A=B+C（或其它的表达方式）就能够实现上述功能，使并行机对B C的对应元素并行相加，并将结果并行赋给A。因此数据并行的表达是相对简单和简洁的，它不需要编程者关心并行机是如何对该操作进行并行执行的。数据并行编程模型虽然可以解决一大类科学与工程计算问题，但是对于非数据并行类的问题，如果通过数据并行的方式来解决，一般难以取得较高的效率。数据并行不容易表达甚至无法表达其它形式的并行特征。数据并行发展到现在，高效的编译实现成为它面临的一个主要问题，有了高效的编译器，数据并行程序就可以在共享内存和分布式内存的并行机上都取得高效率，这样可以提高并行程序的开发效率，提高并行程序的可移植性，进一步推广并行程序设计。
消息传递编程模型：编程级别相对较低，但可以有更广泛的应用范围。
消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、控制执行。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并行机。消息传递为编程者提供了更灵活的控制手段和表达并行的方法，一些用数据并行方法很难表达的并行算法都可以用消息传递模型来实现。灵活性和控制手段的多样化是消息传递并行程序能提供高的执行效率的重要原因。
消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并行执行部分之间复杂的信息交换和协调控制的任务交给了编程者，这在一定程度上增加了编程者的负担。这也是消息传递编程模型编程级别低的主要原因。虽然如此，消息传递的基本通信模式是简单和清楚的，学习和掌握这些部分并不困难，因此目前大量的并行程序设计仍然是消息传递并行编程模式。
并行语言：
1 设计全新的并行语言
2 扩展原来的串行语言的语法成分，使它支持并行特征。需要重新开发编译器，使它能够支持扩充的并行部分。
3不改变串行语言，仅为串行语言提供可调用的并行库。原来的串行编译器也能够使用，不需要任何修改，编程者只需要在原来的串行程序中加入对并行库的调用，就可以实现并行程序设计。本书所介绍的MPI并行程序设计就属于这种方式。
第3章并行算法
并行算法分类：
根据运算的基本对象的不同：可以将并行算法分为数值并行算法（数值计算）和非数值并行算法（符号计算）。当然，这两种算法也不是截然分开的，比如在数值计算的过程中会用到查找、匹配等非数值计算的成分，当然非数值计算中也一般会用到数值计算的方法。
根据进程之间的依赖关系：可以分为同步并行算法（步调一致）、异步并行算法（步调、进展互不相同）和纯并行算法（各部分之间没有关系）。对于同步并行，任务的各部分是同步向前推进的，有一个全局的时钟来控制各部分的步伐。对于异步并行，各部分的步伐是互不相同的，它们根据计算过程的不同阶段决定等待、继续或终止。纯并行是最理想的情况，各部分之间可以尽可能快地向前推进，不需要任何同步或等待。
根据并行计算任务的大小：可以分为粗粒度并行、细粒度并行和中粒度并行。并行的粒度越小，就有可能开发更多的并行性，提高并行度，但是通信次数和通信量就增加很多。
并行算法的设计：
从本质上说，不同的并行算法是根据问题类别的不同和并行机体系结构的特点产生出来的。一个好的并行算法要既能很好地匹配并行计算机硬件体系结构的特点，又能反映问题内在并行性。
对于SIMD并行机一般适合同步并行算法；对于MIMD并行机则适合异步并行算法。
对于SPMD和MPMD这些，设计并行算法的思路比较不同。
应该设法加大计算时间相对于通信时间的比重，减少通信次数甚至以计算换通信。这是因为，对于机群系统，一次通信的开销要远远大于一次计算的开销。所以，并行的粒度不可以太小。如果能实现计算和通信的重叠，则会更大地提高整个程序的执行效率。
以同步和松同步为主，大粒度或中粒度的算法比较合适。
第4章 MPI简介
什么是MPI：
MPI是一个库，而不是一门语言。但是按照并行语言的分类，可以把FORTRAN+MPI或者C+MPI看作是一种在原来串行语言基础上扩展后得到的并行语言。MPI库可以被FORTRAN77/C/FORTRAN90/C++调用，从语法上说，它遵守所有对库函数/过程的调用规则，和一般的函数/过程没有什么区别。
MPI是一种标准或规范的代表，而不特指某一个对它的具体实现。迄今为止，所有的并行计算机制造商都提供对ＭＰＩ的支持，可以在网上免费得到ＭＰＩ在不同并行机上的实现。一个正确的ＭＰＩ程序，可以不加修改地再所有的并行机上运行。
ＭＰＩ是一种消息传递编程模型，并成为这种编程模型的代表和标准。
消息传递方式是广泛应用于多类并行机的一种模式,特别是那些分布存储并行机，尽管在具体的实现上有许多不同,但通过消息完成进程通信的基本概念是容易理解的。十多年来，这种模式在重要的计算应用中已取得了实质进步。有效和可移植地实现一个消息传递系统是可行的，因此，通过定义核心库程序的语法、语义，这将在大范围计算机上可有效实现将有益于广大用户。这是MPI产生的重要原因。
MPI的目的：较高的通信性能，较好的程序可移植性，强大的功能。
提供应用程序编程接口
提高通信效率，措施包括避免存储器到存储器的多次重复拷贝，允许计算和通信的重叠等
可在异构环境下提供实现
提供的接口可以方便C语言和Fortran77的调用
提供可靠的通信接口，即用户不必处理通信失败
定义的接口和现在已有接口，如PVM、NX、Express、p4等。差别不能太大。但是允许扩展以提供更大的灵活性
定义的接口能在基本的通信和系统软件无重大改变时，在许多并行计算机生产商的平台上实现。接口的语义是独立于语言的
接口设计应是线程安全的
MPI的产生：
MPI的语言绑定：
在MPI-1中明确提出了MPI和FORTRAN77与C语言的绑定，并且给出了通用接口和针对FORTRAN77与C的专用接口说明。
在MPI-2中除了和原来的FORTRAN77和C语言实现绑定之外，进一步与Fortran90和C++结合起来，提供了四种不同的接口，为编程者提供了更多选择的余地。但是MPI-2目前还没有完整的实现版本。
目前主要的MPI实现：
MPICH是一种最重要的MPI实现，它可以免费从http://www-unix.mcs.anl.gov/mpi/mpich取得。更为重要的是，MPICH是一个与MPI-1规范同步发展的版本，每当MPI推出新的版本就会有相应的MPICH的实现版本。目前MPICH的最新版本是MPICH-1.2.1。
CHIMP是Edinburgh开发的另一个免费MPI实现，是在EPCC（Edinburgh Parallel Computing Centre）的支持下进行的。从ftp://ftp.epcc.ed.ac.uk/pub/packages/chimp/release/可以免费下载该软件。
LAM(Local Area Multicomputer)也是免费的MPI实现，由Ohio State University开发。它目前的最新版本是LAM/MPI 6.3.2，可以从http://www.mpi.nd.edu/lam/download/下载。它主要用于异构的计算机网络计算系统。
http://blog.sina.com.cn/s/blog_7c8678bb0100tfrt.html
并行处理
并行处理（Parallel Processing）是计算机系统中能同时执行两个或更多个处理机的一种计算方法。处理机可同时工作于同一程序的不同方面。并行处理的主要目的是节省大型和复杂问题的解决时间。为使用并行处理，首先需要对程序进行并行化处理，也就是说将工作各部分分配到不同处理机中。而主要问题是并行是一个相互依靠性问题，而不能自动实现。此外，并行也不能保证加速。但是一个在 n 个处理机上执行的程序速度可能会是在单一处理机上执行的速度的 n 倍。
简介
只有部分应用程序在满足以下条件的情况下可利用并行处理：具有充足的能充分利用多处理机的应用程序；并行化目标应用程序或用户需进行新的编码来利用并行程序。
传统上，多处理机专为“并行计算机”所设计，沿着这样的思路，当前 Linux 支持 SMP 奔腾系统，在该系统中多处理机共享单个计算机中的单个存储器和总线接口。每个运行 Linux 的机器组都有可能通过网络互相连接形成并行处理群。第三种选择是使用 Linux 系统作为“主机”，提供专门的相关并行处理机（attached parallel processor）。第四种新选择是寄存器内 SIMD 并行，应用于多媒体扩展（MMX）。
并行处理所需要提供的典型硬件环境有：
单处理机上的单个区；
多处理机（SMP）中的单个区；
多区配置
一个处理机（MPP）中的各区；
多处理机（SMP 群）中的各区；
逻辑数据库区（在 AIX 第1版的 DB2 并行版 － DB2 PE 中也称之为多逻辑代码或 MLN）
在各种硬件环境下可能的并行类型如下：
硬件环境 I/O 并行查询内并行机制
内部分区并行性 Inter-Partition Parallelism
单区，单处理机是否否
单区，多处理机（SMP）是是否
多区，单处理机（MPP）是否是
多区，多处理机（SMP 群）是是是
逻辑数据库区是是是
到目前为止，并行计算机具有代表性的应用领域有：天气预报建摸、VLSI电路的计算机辅助设计、大型数据库管理、人工智能、犯罪控制和国防战略研究等，而且它的应用范围还在不断地扩大。并行处理技术主要是以算法为核心，并行语言为描述，软硬件作为实现工具的相互联系而又相互制约的一种结构技术。
并行算法的基本策略
在并行处理技术中所使用的算法主要遵循三种策略：
1．分而治之法：也就是把多个任务分解到多个处理器或多个计算机中，然后再按照一定的拓扑结构来进行求解。
2．重新排序法：分别采用静态或动态的指令词度方式。
3．显式／隐式并行性结合：显式指的是并行语言通过编译形成并行程序，隐式指的是串行语言通过编译形成并行程序，显式／隐式并行性结合的关键就在于并行编译，而并行编译涉及到语句、程序段、进程以及各级程序的并行性。
二、并行性描述定义
利用计算机语言进行并行性描述的时候主要有三种方案：
1．语言扩展方案：也就是利用各种语言的库函数来进行并行性功能的扩展。
2．编译制导法：也称为智能编译，它是隐式并行策略的体现，主要是由并行编译系统进行程序表示、控制流的分析、相关分析、优化分析和并行化划分，由相关分析得到方法库管理方案，由优化分析得到知识库管理方案，由并行化划分得到程序重构，从而形成并行程序。
3．新的语言结构法：这是显式并行策略的体现。也就是建立一种全新的并行语言的体系，而这种并行语言通过编译就能直接形成并行程序。
三、并行软件
并行软件可分成并行系统软件和并行应用软件两大类，并行系统软件主要指并行编译系统和并行操作系统，并行应用软件主要指各种软件工具和应用软件包。在软件中所牵涉到的程序的并行性主要是指程序的相关性和网络互连两方面。
1．程序的相关性：程序的相关性主要分为数据相关、控制相关和资源相关三类。
数据相关说明的是语句之间的有序关系，主要有流相关、反相关、输出相关、I／O相关和求知相关等，这种关系在程序运行前就可以通过分析程序确定下来。数据相关是一种偏序关系，程序中并不是每一对语句的成员都是相关联的。可以通过分析程序的数据相关，把程序中一些不存在相关性的指令并行地执行，以提高程序运行的速度。
控制相关指的是语句执行次序在运行前不能确定的情况。它一般是由转移指令引起的，只有在程序执行到一定的语句时才能判断出语句的相关性。控制相关常使正在开发的并行性中止，为了开发更多的并行性，必须用编译技术克服控制相关。
而资源相关则与系统进行的工作无关，而与并行事件利用整数部件、浮点部件、寄存器和存储区等共享资源时发生的冲突有关。软件的并行性主要是由程序的控制相关和数据相关性决定的。在并行性开发时往往把程序划分成许多的程序段——颗粒。颗粒的规模也称为粒度，它是衡量软件进程所含计算量的尺度，一般用细、中、粗来描述。划分的粒度越细，各子系统间的通信时延也越低，并行性就越高，但系统开销也越大。因此，我们在进行程序组合优化的时候应该选择适当的粒度，并且把通讯时延尽可能放在程序段中进行，还可以通过软硬件适配和编译优化的手段来提高程序的并行度。
2．网络互连：将计算机子系统互连在一起或构造多处理机或多计算机时可使用静态或动态拓扑结构的网络。静态网络由点一点直接相连而成，这种连接方式在程序执行过程中不会改变，常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定连接。动态网络是用开关通道实现的，它可动态地改变结构，使之与用户程序中的通信要求匹配。动态网络包括总线、交叉开关和多级网络，常用于共享存储型多处理机中。在网络上的消息传递主要通过寻径来实现。常见的寻径方式有存储转发寻径和虫蚀寻径等。在存储转发网络中以长度固定的包作为信息流的基本单位，每个结点有一个包缓冲区，包从源结点经过一系列中间结点到达目的结点。存储转发网络的时延与源和目的之间的距离(段数)成正比。而在新型的计算机系统中采用虫蚀寻径，把包进一步分成一些固定长度的片，与结点相连的硬件寻径器中有片缓冲区。消息从源传送到目的结点要经过一系列寻径器。同一个包中所有的片以流水方式顺序传送，不同的包可交替地传送，但不同包的片不能交叉，以免被送到错误的目的地。虫蚀寻径的时延几乎与源和目的之间的距离无关。在寻径中产生的死锁问题可以由虚拟通道来解决。虚拟通道是两个结点间的逻辑链，它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成。物理通道由所有的虚拟通道分时地共享。虚拟通道虽然可以避免死锁，但可能会使每个请求可用的有效通道频宽降低。因此，在确定虚拟通道数目时，需要对网络吞吐量和通信时延折衷考虑。
四、硬件技术在硬件技术方面主要从处理机、存储器和流水线三个方面来实现并行。
1．处理机：主要的处理机系列包括CISC、RISC、超标量、VL1W、超流水线、向量以及符号处理机。
传统的处理机属于复杂指令系统计算(CISC)结构。指令系统大，指令格式可变，通用寄存器个数较少，基本上使用合一的指令与数据高速缓存，时钟频率较低，CPI较高，大多数利用ROM 实现微码控制CPU，而当今的精简指令系统计算(RISC)处理机指令格式简单规范，面向寄存器堆，采用重叠寄存器窗口技术，具有多级Cache，多种流水线结构，强调编译优化技术，时钟频率快，CPI低，大多数用硬连线控制CPU。
CISC或RISC标量处理机都可以采用超标量或向量结构来改善性能。标量处理机在每个周期内只发射一条指令并要求周期只完成从流水线来的一条指令。而在超标量处理机中，使用了多指令流水线，每个周期要发射多条指令并产生多个结果。由于希望程序中有许多的指令级并行性，因此超标量处理机更要依靠优化编译器去开发并行性。
VL1W 结构是将水平微码和超标量处理这两种普遍采用的概念结合起来产生的。典型的超长指令字VL1W 机器指令字长度有数百位。在VLlW 处理机中，多个功能部件是并发工作的，所有的功能部件共享使用公用大型寄存器堆，由功能部件同时执行的各种操作是用VL1W 指令来同步的，每条指令可指定多个操作。VL1W 指令译码比超标量指令容易，但在开发不同数量的并行性时总是需要不同的指令系统。VL1W 主要是开发标量操作之间的并行性，它的成功与否很大程度取决于代码压缩的效率，其结构和任何传统的通用处理机完全不兼容。即使同一结构的不同实现也不大可能做到彼此二进制兼容。VL1W 的主要优点在于它的硬件结构和指令系统简单，在科学应用领域可以发挥良好作用，但在一般应用场合可能并不很好用。
向量处理机对数组执行向量指令，每条指令都包含一串重复的操作。它是专门设计用来完成向量运算的协处理机，通常用于多流水线超级计算机中。向量处理机可以利用循环级展开所得的并行性，它可以附属于任何标量处理机。专用的向量流水线可以在循环控制中消除某些软件开销，它的效果与优化编译器将顺序代码向量化的性能很有关系。从理论上说，向量机可以具有和超标量处理机同样的性能，因此可以说向量机的并行性与超标量机相同。
符号处理机是为AI应用而研制的，已用于定理证明、模式识别、专家系统、知识工程、文本检索、科学以及机器智能等许多应用领域。在这些应用中，数据和知识表达式、原语操作、算法特性、存储器、I／0和通信以及专用的结构特性与数值计算是不一样的，符号处理机也称为逻辑程序设计语言处理机、表处理语言处理机或符号变换器。符号处理并不和数值数据打交道，它处理的是逻辑程序、符号表、对象、剧本、黑板、产生式系统、语义网络、框架以及人工神经网络等问题。这些操作需要专门的指令系统，通常不使用浮点操作。
2．存储器：存储设备按容量和存取时间从低到高可分为寄存器、高速缓存、主存储器、磁盘设备和磁带机五个层次。较低层存储设备与较高层的相比，存取速度较快、容量较小，每字节成本较高、带宽较宽、传输单位较小。
存放在存储器层次结构中的信息满足三个重要特性：包含性、一致性和局部性。所谓包含性，指的是一个信息字的复制品可以在比它高的所有层中找到，而如果在高层中丢失了一个信息，则在比它低的所有层中此信息也将丢失。CPU 和高速缓存之间的信息传送是按字进行的，高速缓存和主存储器间用块作为数据传送的基本单位，主存和磁盘之间又是以页面为基本单位来传送信息的，而在磁盘和磁带机之间的数据传送则是按文件级处理的。所谓一致性要求的是同一个信息项与后继存储器层次上的副本是一致的。也就是说，如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改。为了尽量减少存储器层次结构的有效存取时间，通常把频繁使用的信息放在较低层次。维护存储器层次结构一致性一般有两种策略，一种是写直达策略，也就是如果，则立即在所有高层存储器中进行同样的修改；另一种是写回策略，也就是在较低层中对信息进行修改后并不立即在高层存储器中进行相应的修改，而是等到该信息将被替换或将从低层中消失时才在所有高层存储器中进行同样的修改。甚至可以将写直达和写回策略的优点结合起来，形成写一次协议来维护存储器的一致性。
存储器的层次结构是在一种程序行为——访问的局部性基础上开发出来的。主要有时间局部性、空间局部性和顺序局部性。时间局部性指的是最近的访问项很可能在不久的将来再次被访问。它往往会引起对最近使用区域的集中访问。空间局部性表示一种趋势，指的是一个进程访问的各项其地址彼此很近。顺序局部性指的是在典型程序中，除非是转移指令，一般指令都是顺序执行的。
在多处理机系统中一般使用共享存储器。对共享存储器的组织一般采用低位交叉、高位交叉、高低位交叉三种方法。低位交叉又称并发存取，它是把相邻的地址放在相邻的存储器模块中，在访问时不容易产生冲突，并行性较好，但可靠性容错能力和扩展性均较差。高位交叉又称允许同时存取，它是把相邻地址分配到同一个存储器模块中，可靠性、容错能力和扩展性均较强，但访问时易产生冲突，带宽较窄，并行性较差。高低位交叉存取又称C—s存取，它是结合了高位交叉和低位交叉两种方法的优点，既解决了冲突问题，又能有效地提高容错能力和并行性，最适合于向量处理机结构。
3．流水线：流水线技术主要有指令流水线技术和运算流水线技术两种。
指令流水线技术主要目的是要提高计算机的运行效率和吞吐率。它主要通过设置预取指令缓冲区、设置多功能部件、进行内部数据定向、采取适当的指令调度策略来实现。指令调度的策略主要有静态和动态两种，静态词度是基于软件的，主要由编译器完成，动态词度是基于硬件的，主要是通过硬件技术进行。
运算流水线主要有单功能流水线和多功能流水线两种。其中多功能流水线又可分为静态流水线和动态流水线。静态流水线技术只用来实现确定的功能，而动态流水线可以在不同时间重新组合，实现不同的功能，它除流线连接外，还允许前馈和反馈连接，因此也称为非线性流水线。这些前馈和反馈连接使得进入流水线的相继事件的词度变得很不简单。由于这些连接，流水线不一定从最后一段输出。根据不同的数据流动模式，人们可以用同一条流水线求得不同功能的值。
并行计算机发展简述
40 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。创建和使用并行计算机的主要原因是因为并行计算机是解决单处理器速度瓶颈的最好方法之一。
并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。
60 年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现，这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机（Mainframe）。IBM360 是这一时期的典型代表。
到了60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs 公司此时开始实施IlliacIV 计划，研制一台64 个CPU 的SIMD主机系统，它涉及到硬件技术、体系结构、I/O 设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小了的16CPU 系统终于在1975 年面世时，整个计算机界已经发生了巨大变化。
首先是存储系统概念的革新，提出虚拟存储和缓存的思想。IBM360/85 系统与360/91是属于同一系列的两个机型，360/91 的主频高于360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线；但是，360/85 的整体性能却高于360/91，唯一的原因就是前者采用了缓存技术，而后者则没有。
其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器被用作缓存，而CDC7600 则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到了计算机中。元器件技术的这两大革命性突破，使得IlliacIV 的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。
1976 年CRAY-1 问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15 年。CRAY-1 对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC 的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列全新技术手段的使用，使CRAY-1 的主频达到了80MHz。
微处理器随着机器的字长从4 位、8 位、16 位一直增加到32 位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基- 梅隆大学开始在当时流行的DECPDP11小型计算机的基础上研制成功一台由16 个PDP11/40 处理机通过交叉开关与16 个共享存储器模块相连接而成的共享存储多处理器系统C.mmp。
从80 年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP 方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了Cache 一致性问题的处理方案。从此，C.mmp 开创出的共享存储多处理器之路越走越宽；现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。
同一时期，基于消息传递机制的并行计算机也开始不断涌现。80 年代中期，加州理工成功地将64 个i8086/i8087 处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC 系列、INMOS Transputer 系列，Intel Paragon 以及IBM SP 的前身Vulcan 等基于消息传递机制的并行计算机。
80 年代末到90 年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC 微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性（Scalability）。90 年代初期，斯坦福大学提出了DASH 计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE 在此基础上提出了缓存一致性协议的标准。
90 年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5 除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息；CRAY T3D是一台NUMA 结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。
随着商品化微处理器、网络设备的发展，以及MPI/PVM 等并行编程标准的发布，机群架构的并行计算机出现。IBM SP2 系列机群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。
今天，越来越多的并行计算机系统采用商品化的微处理器加上商品化的互连网络构造，这种分布存储的并行计算机系统称为机群。国内几乎所有的高性能计算机厂商都生产这种具有极高性能价格比的高性能计算机，并行计算机就进入了一个新的时代，并行计算的应用达到了前所未有的广度和深度。
并行计算机随着微处理芯片的发展，已经进入了一个新时代。目前并行计算机的性能已经接近100TFLOPS，1000TFLOPS 的并行计算机正在规划之中。我国并行计算机的研制已经走在世界前列，正在研制生产100TFLOPS 的巨型计算机系统。2003年由联想公司生产的深腾6800 在2003 年11 月世界TOP500 排名中位列第14 名，2004 年曙光公司生产的曙光4000A 在2004 年6 月的世界TOP500 排名中位列第10 名，这是我国公开发布的高性能计算机在世界TOP500 中首次进入前十名，这标志着我国在并行计算机系统的研制和生产中已经赶上了国际先进水平，为提高我国的科学研究水平奠定了物质基础。
从TOP500 的前10 名来看，美国仍然是超级计算机的最大拥有者。按照世界TOP500 的统计数据来分析，美国在计算能力上占有近全世界的一半，在TOP500 中的所有计算机中拥有的数量超过50%。
1．计算机系统中提高并行性的技术途径有以下三种：
(1)时间重叠(time-interleaving)：在并行性概念中引入时间因素，即多个处理过程在
时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢
得速度。时间重叠原则上不要求重复的硬件设备。
(2)资源重复(resource-replication)：在并行性概念中引入空间因素，是根据“以数量
取胜”的原则，通过重复设置资源，尤其是硬件资源，大幅度提高计算机系统的性
能。随着硬件价格的降低，这种方式在单处理机中被广泛采用，而多处理机本身就是
资源重复的结果。
(3)资源共享(resource-sharing)：这是一种软件方法，它使多个任务按一定时间顺序轮
流使用同一套硬件设备。例如多道程序、分时系统就是遵循资源共享这一途径产生
的 。资源共享既降低了成本，又提高了计算机设备的利用率。
2．单机系统中并行性的发展
图1.4.2
(1)同构型（对称型）多处理机：由多个同类型，至少担负同等功能的处理机组成，同时
处理同一作业中能并行执行的多个任务。
(2)异构型（非对称型）多处理机：由多个不同类型，至少担负不同功能的处理机组成，
按照作业要求的顺序，利用时间重叠原理，依次对它们的多个任务进行加工，各自完
成规定的功能动作。
(3)分布处理系统：把若干台具有独立功能的处理机（或计算机）相互连接起来，在操作
系统的全盘控制下，统一协调地工作，而最少依赖集中的程序、数据或硬件。
http://sse.tongji.edu.cn/arch/arch_course/architecture/chapter1/lecture3/htm/lecture3_3.asp
多处理机
1．多处理机结构
⑴多处理机：具有多个处理机的计算机。
⑵结构：共享存储器结构、分布式存储器结构2种。
⑶共享存储器结构:多个处理单元通过网络（内部连接）共享集中的主存储器，主存储器由多个并行的存储体组成，而每个CU都有自己的控制单元（这是与并行处理机的不同点）。系统资源易管理、利用，程序员易编程；但是处理机数目少，不易扩充。
⑷分布式存储多处理机：每个处理机都有自己的控制器、自己的存储单元，CU及存储器等构成多个较为独立的部分，各个部分通过网络（内部连接）协调工作。其特点是结构灵活、易扩充，但是，任务传输以及任务分配算法复杂，通常要设计专有算法。
2．多处理机互连方式：
总线方式、交叉开关、多端口存储器方式、开关枢纽方式等。
3．多处理机的特点
⑴结构灵活
⑵程序并行：属于操作一级的并行。性能比指令级的并行高。
⑶进程同步：指令、任务、作业级别的并行处理，不需要同步控制（而并行处理机则要同步）。
⑷多处理机工作时，要根据任务的多少来调用资源，因此，所需要的资源变化复杂。
4．MMP与SMP
由于对计算机的速度、性能要求越来越高，近年来出现了超级并行计算机的体系结构，MMP、SMP就是其中的代表。
⑴MMP（大规模并行处理机）：采用几百到上万个基于RISC指令集的处理器，组成大型并行计算机系统。其运算速度达万亿次
（浮点加法）
⑵SMP（对称多处理机）：结构与MMP类似。不同的是SMP有一个统一的共享主存储空间，而MMP则是每个处理器都有自己的存储器。
5．超级大型并行计算机：
由于重大科学计算的运算需要，将出现超级并行机。此类计算机将具有3T性能。1T FLOPS的计算能力；1TB的主存储器；1TB/S的I/O带宽。
扩展阅读：
http://course.cug.edu.cn/cugThird/computer_system/xt-pages/6-3-1.htm
对称多处理机
概要
对称多处理机（SymmetricalMulti-Processing）又叫SMP，是指在一个计算机上汇集了一组处理器(多CPU)，各CPU之间共享内存子系统以及总线结构。它是相对非对称多处理技术而言的、应用十分广泛的并行技术。在这种架构中，一台电脑不再由单个CPU组成，而同时由多个处理器运行操作系统的单一复本，并共享内存和一台计算机的其他资源。虽然同时使用多个CPU，但是从管理的角度来看，它们的表现就像一台单机一样。系统将任务队列对称地分布于多个CPU之上，从而极大地提高了整个系统的数据处理能力。所有的处理器都可以平等地访问内存、I/O和外部中断。在对称多处理系统中，系统资源被系统中所有CPU共享，工作负载能够均匀地分配到所有可用处理器之上。从而提高整个系统的数据处理能力。
概述
AMDAthlon 64 X2平时所说的双CPU系统，实际上是对称多处理机系统中最常见的一种，通常称为2路对称多处理，它在普通的商业、家庭应用之中并没有太多实际用途，但在专业制作，如3DMaxStudio、Photoshop等软件应用中获得了非常良好的性能表现，是组建廉价工作站的良好伙伴。随着用户应用水平的提高，只使用单个的处理器确实已经很难满足实际应用的需求，因而各服务器厂商纷纷通过采用对称多处理系统来解决这一矛盾。在中国国内市场上这类机型的处理器一般以4个或8个为主，有少数是16个处理器。但是一般来讲，SMP结构的机器可扩展性较差，很难做到100个以上多处理器，常规的一般是8个到16个，不过这对于多数的用户来说已经够用了。这种机器的好处在于它的使用方式和微机或工作站的区别不大，编程的变化相对来说比较小，原来用微机工作站编写的程序如果要移植到SMP机器上使用，改动起来也相对比较容易。SMP结构的机型可用性比较差。因为4个或8个处理器共享一个操作系统和一个存储器，一旦操作系统出现了问题，整个机器就完全瘫痪掉了。而且由于这个机器的可扩展性较差，不容易保护用户的投资。但是这类机型技术比较成熟，相应的软件也比较多，因此现在中国国内市场上推出的并行机大量都是这一种。PC服务器中最常见的对称多处理系统通常采用2路、4路、6路或8路处理器。目前UNIX服务器可支持最多64个CPU的系统，如Sun公司的产品Enterprise10000。SMP系统中最关键的技术是如何更好地解决多个处理器的相互通讯和协调问题。
系统结构
PowerMac G4系统架构对称多处理机的系统结构，主要指处理器、存储器、输入输出(I/O)设备三者之间的连接，它对我们更好地理解多处理机操作系统是非常必要的。
多处理器与存储器之间的连接：
1、多端口存储器方式：这是最简单的连接。被共享的存储器有3块，每块都有4个端口，分别与4个处理器连接。因此，各处理器能并行访问不同的存储块，但对同一块的访问必须是顺序的。各存储块内的硬件逻辑自动控制其访问。优点是连接相当简单。由于存储器的端口不可能太多，这种方式限制了能够连接的处理器个数，适用于处理器数目较少的场合。
2、集中控制开关方式：集中控制开关方式能克服多端口方式的缺点。它的做法是，把各存储块内的硬件控制逻辑换成一个集中式开关，集中式开关给出处理器到存储块的访问路径。这种方式的优点是支持更多的处理器。缺点是开关单元比较复杂，降低了系统的可靠性。若有m个存储块，n个处理器，则连接路径数为m乘n。当处理器要访问某存储块时，经过集中式开关线路时应考虑不能有明显的延时。万一某一路径故障，有可能殃及其他路径。
3、局部存储器方式：多处理机竞争共享存储器时，因相互冲突而延迟，从而使各处理器访问主存的平均时间增加。如果一个存储块上连接的处理器不多，则引起冲突的概率当然就小。但我们又不愿意通过减少处理器数目来缩短访问主存的平均时间。这是一个两难问题。
一种解决办法是，在处理器和开关之间增加高速缓冲存储器(Cache)。把刚访问过的共享存储器的内容保留在Cache中，当处理器再度访问主存时，先查询Cache，如果要访问的数据已在Cache中，则不必访问主存。这样可以减少访问主存的次数但必须配置Cache置换算法并承担置换时间开销。另一种解决办法是，为每个处理器配备一个局部存储器，局部存储器的容量通常比Cache大，造价却比Cache小，所以受到欢迎。局部存储器Mi只属于Pi(i=1.…,n)，不能被其他处理器访问。任一处理器都只能访问共享存储器和私有的局部存储器，不能访问其他局部存储器，称为不对称性体系结构。局部存储器也由操作系统管理，使之起到一个高速缓冲存储器的作用。然而，把在一个处理器上运行的进程移到另一个处理器上运行的代价是非常高的。
4、分布式：变集中式开关为分布式开关是处理器与存储器连接的另一种设计思路。右图是分布式多处理器体系结构示意图。每个处理器都与一个局部存储器相连，但局部存储器不具有私有性，它能被各处理器访问。这样，所有处理器共享寻址空间。处理器Pi(i=1,…,n)对Mi的访问不经过开关切换线路，但对Mj(j≠i)的访问要经过开关切换。开关切换是这样实现的：局部开关把请求信号作为消息包packet()发给目的开关，途中各开关起转发作用。当目的开关得到消息后，就把自己的局部存储器中的数据作为一个消息包发回源开关，再转至等待该数据的处理器。
分布式多处理器比集中式开关多处理器有更高的可靠性和可扩充性，但在访问非局部存储器时有一定的延时，这取决于被访问非局部存储器Mj与处理器Pi的距离。在这样的系统中，操作系统的设计一定要考虑尽量减少这种延时等待。一个设计精良的任务分配算法不但能减少Pi对Mj的请求次数，而且能缩短Pi对Mj的距离。我们将在任务分配策略中讨论这个问题。
其中分布式多处理器被看作是松耦合型(looselycoupled)，多端口存储器方式、集中控制开关方式和多处理器带局部存储器的多处理器被看作是紧耦合型(tightlycoupled).
松耦合多处理架构处理器与输入输出设备之间的连接
1、多端口输入输出设备类似于多端口存储器；设备的每个端口同一个处理器的总线相连接，设备可用此端口进行数据传输和中断处理。
2、由交叉开关连接处理器与输入输出设备，交叉开关的作用类似集中式或分布式开关，但设备开关的硬件逻辑更复杂些。因为一个设备同一个处理器保持联系的时间在一个事务处理过程中(比如读盘、写盘)可能很长，因而用软件来控制开关切换比用硬件实现会更方便。
3、只与一个处理器相连而不能被其他处理器访问的输入输出设备，容易理解，一个处理器只能访问与之相连的设备。如果想访问别的设备，需要软件参与协调，例如，向其他处理器发出一个请求使本处理器能在别的设备上操作。
4、只与一个处理器相连但可被其他处理器访问的输入输出设备；使用分布式开关且用存储器地址而不用输入输出指令来访问输入输出设备时用方式④，因为输入输出操作是对一个存储地址写数据或读数据，所以无需分布式开关做额外工作，处理器就可方便地访问其他设备。尽管处理器能访问任一设备，但从设备发出的数据和中断信号却只能由与之相连接的处理器处理。这种不对称的原因来自两个方面。一方面，设备发出的中断信号必须得到快速响应，这对远程处理器来说是做不到的；另一方面，到非局部存储器的数据传输存在不同的时间延迟，此延迟有可能比设备读或写的时间大。
上述几种方式对操作系统的I输入输出设备控制进程有不同的要求。方式①和②的设备进程要在每个处理器上运行。方式③的设备进程只要在可访问该设备的处理器上运行。方式④的设备进程操作要分成能在所有处理器上运行和在同设备相连的处理器上运行这两种情况考虑
功能的差异
中国曙光一号共享存储多处理机系统对称多处理机操作系统，目前有三种类型：主从式(master-slave)、独立监督式(separatesupervisor)、浮动监督式(floatingsupervisor)。从资源管理观点来看，虽然多处理机操作系统也具有单机操作系统所具有的各种功能，如进程管理、线程管理、存储管理文件与设备管理功能，但在各方面存在不同之处：
1、共享资源
在多处理机环境下，由于多个处理机上运行的进程并行执行，因而可能有若干个进程绝对同时访问某共享资源，这种情况比起单机环境下并发进程交替访问共享资源要难以处理，多处理机操作系统应具有新的进程同步与互斥算法。
2、多处理机调度
对称多处理机调度要考虑到负载平衡才能发挥多处理机体系的最大效能。因此在任务分配时，一方面必须了解每台处理机的能力以便把适合的任务分配给它，另一方面也要确切地了解作业中诸任务之间的关系，即哪些任务必须顺序、哪些任务可以并行执行。
3、存储器访问
在对称多处理机环境下，存储器体系既有局部的又有全局的，其地址变换机构比单机环境复杂。当多个进程竞争访问某存储块时，访问冲突仲裁机构决定哪一个处理机上的进程可立即访问，哪个或哪些处理机上的进程应等待。当共享主存中的数据在多个局部存储器出现时，操作系统应保证这些数据的一致性。
4、提高可靠性
为了提高多处理机系统的可靠性，应使操作系统具有重构能力：当系统中某个处理机或存储块等资源发生故障时，系统自动切除故障资源并换上备份资源，使之能继续工作。如果没有备份资源，则重构系统使之降级运行。如果在故障的处理机上有进程亟待执行，操作系统应能安全地把它迁移到其他处理机上继续运行，处于故障处的其他可利用资源同样也予以安全转移。
系统类型
对称多处理机服务器对称多处理机操作系统，目前有三种类型：
1、主从式(master-slave)
主从式操作系统由一台主处理机记录、控制其它从处理机的状态，并分配任务给从处理机。例如，Cyber-170就是主从式多处理机操作系统，它驻留在一个外围处理机Po上运行，其余所有处理机包括中心处理机都从属于Po。另一个例子是DECSystem10，有两台处理机，一台为主，另一台为从。操作系统在主处理机上运行，从处理机的请求通过陷入传送给主处理机，然后主处理机回答并执行相应的服务操作。主从式操作系统的监控程序及其提供服务的过程不必迁移，因为只有主处理机利用它们。当不可恢复错误发生时，系统很容易导致崩溃，此时必须重新启动主处理机。由于主处理机的责任重大，当它来不及处理进程请求时，其它从属处理机的利用率就会随之降低。
主从式的特点：
A.操作系统程序在一台处理机上运行。如果从处理机需要主处理机提供服务，则向主处理机发出请求，主处理机接受请求并提供服务。不一定要求把整个管理程序都编写成可重入的程序代码，因为只有一个处理机在使用它，但有些公用例程必须是可重入的才行。
B.由于只有一个处理机访问执行表，所以不存在管理表格存取冲突和访问阻塞问题。
C.当主处理机故障时很容易引起整个系统的崩溃。如果主处理机不是固定设计的，管理员可从其他处理机中选一个作为新主处理机并重新启动系统。
D.任务分配不但容易使部分从处理机闲置而导致系统效率下降。
E.用于工作负载不是太重或由功能相差很大的处理机组成的非对称系统。
F.系统由一个主处理机加上若干从处理机组成，硬件和软件结构相对简单，但灵活行差。
Intel奔腾Ⅱ Xeon双核处理器2、独立监督式(separatesupervisor)
独立监督式与主从式不同，在这种类型中，每一个处理机均有各自的管理程序(核心)。采用独立监督式操作系统的多处理机系统有IBM370/158等。
独立监督式的特点：
A.每个处理机将按自身的需要及分配给它的任务的需要来执行各种管理功能，这就是所谓的独立性。
B.由于有好几个处理机在执行管理程序，因此管理程序的代码必须是可重入的，或者为每个处理机装入专用的管理程序副本。
C.因为每个处理机都有其专用的管理程序，故访问公用表格的冲突较少，阻塞情况自然也就较少，系统的效率就高。但冲突仲裁机构仍然是需要的。
D.每个处理相对独立，因此一台处理机出现故障不会引起整个系统崩溃。但是，要想补救故障造成的损害或重新执行故障机未完成的工作非常困难。
E.每个处理机都有专用的I/O设备和文件等。
F.这类操作系统适合于松耦合多处理机体系，因为每个处理机均有一个局部存储器用来存放管理程序副本，存储冗余太多，利用率不高。
G.独立监督式操作系统要实现处理机负载平衡更困难。
对称多处理机系统模型3、浮动监督式(floatingsupervisor)
每次只有一台处理机作为执行全面管理功能的“主处理机”，但根据需要，“主处理机”是可浮动的，即从一台切换到另一台处理机。这是最复杂、最有效、最灵活的一种多处理机操作系统，常用于对称多处理机系统(即系统中所有处理机的权限是相同的，有公用主存和I/O子系统)。浮动监督式操作系统适用于紧耦合多处理机体系。采用这种操作系统的多处理机系统有IBM3081上运行的MVS，VM以及C·mmp上运行的Hydra，等等。
浮动监督式的特点：
A.每次只有一台处理机作为执行全面管理功能的“主处理机”，但容许数台处理机同时执行同一个管理服务子程序。因此，多数管理程序代码必须是可重入的。
B.根据需要，“主处理机”是可浮动的，即从一台切换到另一台处理机。这样，即使执行管理功能的主处理机故障，系统也能照样运行下去。
C.一些非专门的操作（如I/O中断）可送给那些在特定时段内最不忙的处理机去执行，使系统的负载达到较好的平衡。
D.服务请求冲突可通过优先权办法解决，对共享资源的访问冲突用互斥方法解决。
E.系统内的处理机采用处理机集合概念进行管理，其中每一台处理机都可用于控制任一台I/O设备和访问任一存储块。这种管理方式对处理机是透明的，并且有很高的可靠性和相当大的灵活行。
设计的原则
对称多处理机结构对称多处理机操作系统的设计与单处理机多道程序设计的不同主要基于两点：
1、系统的体系结构
各处理机是异构的还是同构的，如果各处理机是异构(nonhomogeneity)的而不是同构(homogeneity)的，则各台处理机上的可执行代码格式不一样，浮动管理就困难。解决的办法之一是通过仿真软件来“抹平”异构机之间的硬件差异。在非对称主存系统中，不是所有的处理机都能访问所有的存储器，这给操作系统的主存管理带来复杂性。
2、程序设计环境
（1）同步的重要性
一个并行程序由两个或多个相互作用的进程组成，进程间的同步和通信显得更加重要。如果并行算法不是设计得很有效，则会降低并行系统的性能。同步原语通常由硬件实现，也可由软件实现，但硬件实现可以减少系统花在同步上的开销。
同步实现模型（2）同步的实现
多处理机器是系统是共享存储的，因此各处理机上的进程可通过共享存储器进行同步。但是，对于松耦合的多处理机，各处理机有很大的独立性，它们的进程一部分采用集中式，另一部分采用分布式同步机制。集中式系统的同步问题已有介绍。在狭义的多处理机系统中，进程间更多的是同步且其实现相对简单。广义的多处理机系统利用计算机网络与分布式系统实现进程间的通信。在那样的环境下，同步被看作为是低级的通信。
（3）利用中心进程实现同步
中心进程又称协调进程，它是多处理机系统管理程序的一部分。中心进程保存了所有用户的存取权限和冲突图(conflictgraph)等信息。每一个要求访问共享资源的进程先向中心进程发送请求消息，中心进程收到该请求后便去查看冲突图。如果该请求不会引起死锁，便将该请求插入请求队列，否则将请求退回。当轮到该请求使用共享资源时，中心进程便向请求进程发送一回答信息并让请求者进入临界段访问共享资源。在退出临界段时，原请求进程还得向中心进程发送一释放资源的消息，中心进程收到消息后又可向下一个请求进程发送回答消息，允许它进入临界段。由此看来，中心进程的作用是安排访问共享资源的顺序。由于任一进程要访问共享资源需要申请、回答、释放3个消息传递，同步的效率不高。
组建
中断控制器要组建SMP系统，首先最关键的一点就是需要合适的CPU相配合。平时看到的CPU都是单颗使用，所以看不出来它们有什么区别，但是，实际上，支持SMP功能并不是没有条件的，要实现SMP功能，使用的CPU必须具备以下要求：
1、CPU内部必须内置APIC（AdvancedProgrammableInterruptControllers）单元。Intel多处理规范的核心就是高级可编程中断控制器（AdvancedProgrammableInterruptControllers--APICs）的使用。CPU通过彼此发送中断来完成它们之间的通信。通过给中断附加动作（actions），不同的CPU可以在某种程度上彼此进行控制。每个CPU有自己的APIC（成为那个CPU的本地APIC），并且还有一个I/OAPIC来处理由I/O设备引起的中断，这个I/OAPIC是安装在主板上的，但每个CPU上的APIC则不可或缺，否则将无法处理多CPU之间的中断协调。
对称频率2、相同的产品型号，同样类型的CPU核心。例如，虽然Athlon和PentiumIII各自都内置有APIC单元，想要让它们一起建立SMP系统是不可能的，当然，即使是Celeron和PentiumIII，那样的可能性也为0，甚至Coppermine核心的PentiumIII和Tualatin的PentiumIII也不能建立SMP系统--这是因为他们的运行指令不完全相同，APIC中断协调差异也很大。
3、完全相同的运行频率。如果要建立双PentiumIII系统，必须两颗866MHz或者两颗1000MHz处理器，不可以用一颗866MHz，另一颗1000MHz来组建，否则系统将无法正常点亮。
4、尽可能保持相同的产品序列编号。即使是同样核心的相同频率处理器，由于生产批次不同也会造成不可思议的问题。两个生产批次的CPU作为双处理器运行的时候，有可能会发生一颗CPU负担过高，而另一颗负担很少的情况，无法发挥最大性能，更糟糕的是可能导致死机，因此，应该尽可能选择同一批生产的处理器来组建SMP系统。
SIMD计算机
SIMD计算机前面已经介绍过，其结构如下图所示，其中PE表示处理单元，P表示处理器，M表示存储器。
SIMD中通常包含大量处理单元PE，而控制部件只有一个。控制部件广播一条指令，所有的处理单元同时执行这条指令，但不同的处理单元操作的数据可能不同。
典型的SIMD计算机有MasPar公司的MP-1系列，Thinking Machines公司的CM-2，Illiac IV，BSP等。MasPar MP-1最多可容纳16384个处理器。当配置16384个处理器时，32位的整数操作的峰值性能可达26000MIPS，单精度浮点运算性能达1.5GFlops，双精度浮点运算性能达650MFlops。CM-2有65536个处理单元，峰值速度达到28GFlops，持续速度达到5.6GFlops。
并行向量处理机在并行向量处理机中有少量专门定制的向量处理器。每个向量处理器有很高的处理能力。并行向量处理机通过向量处理和多个向量处理器并行处理两条途径来提高处理能力。Cray C-90、Cray T-90、NEC SX-4和我国的银河1号都是PVP。PVP通常使用定制的高带宽网络将向量处理器连向共享存储器模块。存储器可以以很高的速度向处理器提供数据。例如，在Cray T-90中，共享存储器能以14GB/s的速率将数据提供给一个处理器。这种机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。其系统结构如下图所示。图中VP表示向量处理器，SM表示共享存储器。
对称多处理机
对称多处理机的最大特点是其中的各处理器完全平等，无主从之分。所有的处理器都可以访问任何存储单元和I/O设备。存储器一般使用共享存储器，只有一个地址空间。因为使用共享存储器，通信可用共享变量（读写同一内存单元）来实现。这使得编程很容易。典型的对称多处理机有Sun SPARC server 10000，Sun SPARC center 2000，SGI Power Challenge以及我国的曙光1号。SMP广泛地用于服务器领域。SMP的结构如下图所示。P/C表示处理器和高速缓存，SM表示共享存储器。
大规模并行处理机
大规模并行处理机一般指规模非常大的并行计算机系统，含有成千上万个处理器。它一般采用分布的存储器，存储器一般为处理器私有，各处理器之间用消息传递的方式通信。大规模并行处理机的互连网络一般是专门设计定制的。典型的MPP有Intel Paragon、IBM SP2以及Option Red。MPP的结构如下图所示。其中MB表示存储器总线，P/C表示处理器和高速缓存，NIC表示网络接口电路，LM表示本地存储器。（网络接口电路（Network Interface Circuitry，NIC）是用来将计算机与网络（例如局域网）连接起来的接口电路。典型的NIC包括一个嵌入式的处理器，一些输入、输出缓冲器，以及一些控制存储器和控制逻辑，它的功能有：将消息格式化、路由选择、流和错误控制等。）
分布式共享存储器多处理机
分布式共享存储器多处理机的主要特点是它的存储器在物理上是分布在各个结点中的，但是通过硬件和软件为用户提供一个单一地址的编程空间，即形成一个虚拟的共享存储器。它通过高速缓存目录支持分布高速缓存的一致性。DSM与SMP的区别在于各结点内有存储器，与MPP的区别在于存储器在逻辑上是共享的。典型的DSM有Stanford DASH、SGI/Cray Origin 2000。DSM的结构如下图所示，其中DIR表示高速缓存目录，其它符号同前。
DSM分布式共享存储结构
美籍并行处理专家黄铠教授早在1993年就指出：“并行处理的发展趋势是用分布式共享存储结构（Distributed Shared Memory，DSM）和标准Unix来构造可扩展超级计算机。”即并行计算机发展的趋势既不是SMP，也不是MPP，而是两者优势互补的DSM。
超级计算机系统可分为两大部分，一部分是包括硬件和系统软件的平台，另一部分是应用软件。对不具有可编程性的超级计算机，即使平台有较高的性价比，但却大大增加了移植原有应用软件的难度和开发新的应用软件的成本，从而导致整个系统的性价比大幅度下降。
市场需要既有可扩展性，又有可编程性的超级计算机。但需要不等于现实。要在分布式环境下实现存储逻辑共享，是一个相当困难和复杂的问题。众所周知，现今的计算机存储器速度远远落后于CPU，这是一个长期得不到很好解决的严重瓶颈。而在分布式共享存储并行机中，一个CPU存取远程节点上的存储单元要像存取本地单元一样，不仅方便而且具有令人满意的效率，这使问题难上加难。
一致性高速缓存(CoherentCache)
非严格的存储一致性（RelaxedMemoryConsistency）
多现场切换技术（MulitipleContext）
工作站机群
工作站机群是一种新兴的并行系统。COW是由高档商品微机（包括工作站）用高速商品互连网络（有的商用机群也使用定制的网络）连接而成。因此COW的每个结点都是一台完整的计算机（可能没有鼠标、显示器等外设）。COW的每个结点上都有完整的操作系统，而MPP的每个结点上通常只有操作系统的微核。COW的每个结点内有本地磁盘，而MPP的结点内没有。COW各结点的网络接口是连接到I/O总线上的（松耦合），而MPP各结点的网络接口是连接到存储总线上的（紧耦合）。COW的结构如下图所示，其中LD表示本地磁盘，B表示存储总线与I/O总线的接口，IOB表示I/O总线。
小结
PVP的处理器和互连网络都是定制的。SMP、MPP多使用商用处理器。MPP的互连网络是定制的。COW基本都使用商品部件。SMP、MPP和COW在本章2.4节中还会详细介绍。
http://comic.sjtu.edu.cn/thucs/GD_jsj_031y/text/ch02/se01/r2_1_4.htm
机群系统
计算机集群简称集群。通常通过局域网把一组计算机连接起来，使它们密切协作，以完成高可用性（一台机子有问题时不影响整体工件），负载均衡（负载合理分摊），高性能大规模计算工作。机群（cluster）系统是互相连接的多个独立计算机的集合，这些计算机可以是单机或多处理器系统（PC、工作站或SMP），每个结点都有自己的存储器、I/O设备和操作系统。机群对用户和应用来说是一个单一的系统，它可以提供低价高效的高性能环境和快速可靠的服务。
基本体系结构
机群系统一般结构
机群系统包括下列组件： ·高性能的计算结点机（PC、工作站或SMP）。 ·具有较强网络功能的微内核操作系统。 ·高效的网络/交换机（如千兆位以太网和Myrinet）。 ·网卡（NICs）。 ·快速传输协议和服务。 ·中间件层，其中包括某些支持硬件，如数字存储通道、硬件分布共享存储器及SMP技术；应用，如系统管理工具和电子表格；运行系统，如软件分布共享存储器和并行文件系统；资源管理和调度软件等。 ·并行程序设计环境与工具，如编译器、语言环境、并行虚拟机（PVM）和消息传递接口（MPI）等。 ·应用，包括串行和并行应用程序。组建机群系统的需求和功能
机群组建时应考虑下面的需求和功能： ·较高带宽的网络，以支持通信需求； ·低延迟的通信机制； ·支持高带宽的多点传送通信方式； ·自动恢复网络和结点错误的能力； ·标准的低级原语，支持通信、同步和时序； ·异构的远程过程调用，以隐藏体系结构、协议和系统的不同性； ·实时性能监视器； ·可靠的批处理工作调度程序； ·分布应用程序开发工具； ·支持传统的高级语言进行异构计算； ·能够开发工作站机群的应用程序； ·新的系统管理工具； ·发展标准化，以保护软件投资。机群系统与其他系统的比较
一个典型机群系统和其他类型系统的对比可参看下表。 基本类型 机群系统可以按照应用或结构进行分类。 1．按应用目标 可分为面向科学计算型或面向关键任务应用型： ·高性能机群（high performance cluster）； ·高可用性机群（high availability cluster）。 2．按组成机群的处理机类型 ·PC机群； ·工作站机群； ·SMP（对称多处理器）机群。 3．按处理机操作系统 ·Linux机群，如Beowulf； ·Solaris机群，如Berkeley NOW； ·NT机群，如HPVM； ·AIX机群，如IBM SP2； ·数字VMS（虚拟存储机）机群； ·HP-UX机群； ·微软Wolfpack机群。 4．按处理机的配置 ·同构型机群：所有结点拥有近似的构造和相同的操作系统； ·非同构型机群：所有结点拥有不同的构造和不同的操作系统。 5．按处理机的位置和数量 ·组机群，结点数量为2～99，通过SANs（系统级网络），如Myrinet，机群实际上装入一个机箱中或存在一个范围之内； ·部门机群，结点数量为几十或几百； ·企业机群，结点数量为几百。 6．按构筑机群的方式 ·专用机群； ·非专用机群。 极高的性能价格比使专用机群深受欢迎。 专用机群 专用机群一般由一组同构的处理机组成（有时也有异构情况），通常安装在一个机房内，或者将主板等安装在一个机柜的各机箱中（商业机群常用这种方式），或像图中那样简单地把PC机堆砌在机架上（Piles of PC）。在这种机群中，每个处理机都是专用的、无属主的，由系统管理员统一管理，用户可通过前端机进行访问，用户无需知道机群的详情，就像使用MPP机一样，易于配置和管理，不受外界干扰，通信可靠且延迟小，适合于面向加速比的并行任务和面向吞吐量批处理作业。专用机群具有相对结构和管理简单、易于扩展等特点，用途极广。专用机群的互联结构
·I/O方式包括普通用LAN、FDDI、ATM等网络连接和共享磁盘连接两种方式。 ·共享存储器方式包括全局共享存储器方式和分布式共享存储器方式。分布式存储器指没有一个集中的存储器，由各处理机内一部分存储器通过软件机制形成。 1994年夏，美国的研究人员建成了第一个Beowulf机群，它由16个DX4处理机组成。1997年，又推出了16个基于PⅡ的机群，只需花费5万美元却具有每秒10亿次的浮点运算能力，而购买具有相同能力并行机的投资数却是它的10倍。 Berkeley的NOW系统也是较早的工作站机群，由上百个Sun Ultra工作站组成，集成到19 英寸机箱中，可使用Myrinet、ATM和终端集中器等多种互联手段，每个结点自带512K缓存、128M内存及2个2.3G硬盘。 此外，各大公司推出的商业专用机群还有很多，如DEC 的VMS机群和TruCluster、惠普的Apollo 9000机群、IBM的Sysplex、Sun的Solaris MC 等。 在国内，曙光公司最新推出了基于NT的天潮系列机群产品，是采用分布式存储的可扩展机群体系。其结点处理器为Intel PⅡ和PⅢ，通过千兆位以太网互联，扩展性好，结点可根据不同的应用，动态地分为多个结点池，如可用两个结点作为服务器、四个结点运行数据库、其他结点用于计算等，结点数量可灵活配置。应用范围包括： 科学计算支持PVM和MPI，使用优化的BLAS库；事务处理在线事务处理（OLTP），如电子商务、证券交易和在线分析处理（OLAP）；并行数据库支持Oracle、DB2等分布式数据库应用； 网络服务器运行各种Internet服务。非专用机群
非专用机群是由分散互联的处理机或在网上寻找到的空闲处理机组成的机群，这些处理机可能分属于不同的个人、组织或单位。据资料统计，一般计算机系统平均使用率仅为30%左右，有的空闲率竟达91%，而许多桌面网络工作站和微机的CPU利用率都小于10％，因此，人们自然想到要利用这些闲散的CPU处理能力，这被称为CPU周期窃取。 通常，网络上计算单元都是拥有者各自孤立地使用其拥有的计算单元，一般处于下列状态： ·处于空闲或等待状态，如夜间； ·文档编辑工作，包括收发E-mail、阅读文档和信息等； ·开发工作，包括编辑、编程、编译、调试等； ·完成某种定时、守候服务和功能； ·运行计算型的程序。 所谓窃取CPU周期就是要窃取上述前四类处理机的CPU 周期给最后一类工作用。显然，被窃取CPU周期的处理机包括空闲的处理机和CPU负载较轻的处理机两类。 非专用机群地理上分布于不同的所有者，由异构系统组成，大部分通过以太网连接，适用于企业级局域网范围，技术难度要高于专用机群。工作站的主人与需占用工作站资源运行程序的远程用户之间存在着矛盾，前者希望与工作站快速交互，而后者只关心能否利用所有的共享CPU来快速运行程序。机器的所有者必须具有参加机群的动机，这意味着他们相信贡献他们的资源是有意义的。但是，这些所有者不希望在他们工作时或他们的系统过于饱和时，受到其他干扰，一个解决的策略是允许所有者退出机群。目前，国际上正在形成一种计算资源的买卖市场，以刺激资源拥有者加入网上机群。此外，由于当前网络通信速度和质量的瓶颈所限及由通信竞争造成的网络不确定性的存在，对非专用机群技术提出了更高的要求，如对进程迁移、负载平衡等技术的需求。但此类系统最为贴近普通用户，可以充分利用网上无穷无尽的资源，而组建投资几乎可忽略不计。可以预见，随着网络瓶颈问题的缓解，非专用机群必然是极有发展前途的一种计算形式。主要应用
网格计算
网格计算或网格集群是一种与集群计算非常相关的技术。网格与传统集群的主要差别是网格是连接一组相关并不信任的计算机，它的运作更像一个计算公共设施而不是一个独立的计算机。还有，网格通常比集群支持更多不同类型的计算机集合。 网格计算是针对有许多独立作业的工作任务作优化，在计算过程中作业间无需共享数据。网格主要服务于管理在独立执行工作的计算机间的作业分配。资源如存储可以被所有结点共享，但作业的中间结果不会影响在其他网格结点上作业的进展。高性能计算集群
高性能计算集群采用将计算任务分配到集群的不同计算节点儿提高计算能力，因而主要应用在科学计算领域。比较流行的HPC采用Linux操作系统和其它一些免费软件来完成并行运算。这一集群配置通常被称为Beowulf集群。这类集群通常运行特定的程序以发挥HPC cluster的并行能力。这类程序一般应用特定的运行库, 比如专为科学计算设计的MPI库。 HPC集群特别适合于在计算中各计算节点之间发生大量数据通讯的计算作业，比如一个节点的中间结果或影响到其它节点计算结果的情况。负载均衡集群
负载均衡集群运行时，一般通过一个或者多个前端负载均衡器，将工作负载分发到后端的一组服务器上，从而达到整个系统的高性能和高可用性。这样的计算机集群有时也被称为服务器群（Server Farm）。 一般高可用性集群和负载均衡集群会使用类似的技术，或同时具有高可用性与负载均衡的特点。 Linux虚拟服务器（LVS）项目在Linux操作系统上提供了最常用的负载均衡软件。
扩展阅读：
http://zh.wikipedia.org/zh/计算机集群
并行计算机的发展趋势与应用前景
李国杰
国家智能计算机研究开发中心
