6.2 并行处理技术的发展
6.3 SIMD并行处理机
6.4 多处理机结构
6.5 多处理机高速缓冲存储器（ cache）一致性
6.5 多处理机举例第六章、并行处理技术和多处理机
6.1 概述
6.6 并行处理软件本章重点书 P252 6.1~6.9
一 并行性概念并行处理是一种有效的强调开发计算过程中并行事件的信息处理方式,
在数值计算，数据处理，知识处理或人工智能求解过程中，可能存在某些能同时进行运算或操作的部分。
同时性（ simultaneity）,指两个或多个事件在同一时刻发生在多个资源中。
并发性（ concurrency）,指两个或多个事件在同一时间间隔内发生在多个资源中
6.1 概述在同一时刻或同一时间间隔内完成多个性质相同或不同的任务
1．从计算机信息加工步骤和阶段看，并行性等级可分为：
存贮器操作并行 ----并行存贮器系统和以相联存贮器为核心构成的相联处理机。
处理器操作步骤并行 ----可以是一条指令的取指、分析、执行等操作步骤，也可以是具体运算。
处理器操作并行 ----为支持向量、数组运算，可以通过重复设置处理单元进行，如并行处理机指令、任务、作业并行 ----称为较高级并行，属于多指令流多数据流计算机。
二,并行的等级和分类
2,从系统结构发展看,
高性能的单处理机,SIMD并行处理机,多处理机,多计算机系统非冯,诺依曼计算机 (属于多处理机系统 )
并行性的开发还可以按程序大小划分不同粒度的开发方式 。
我们先来介绍两个概念：
颗粒规模 （ grain size） 或粒度 （ granularity） ---- 是衡量软件进程所含计算量的尺度 。 测量方法是数一下颗粒 （ 程序段
） 中的指令数目 。 一般用细,中,粗来描述,
时延 -（ TC ） 是机器各子系统间通信开销的时间量度 。 如：存贮时延是处理机访问存贮器所需时间；同步时延是两台处理机互相同步所需的时间 。
3,程序划分和粒度并行性粒度,每次并行处理的规模大小 。 用字母 G表示
G=TW/TC
TW：所有处理器进行计算的时间总和；
TC：所有处理器进行通信的时间总和。（设系统共有 P个处理器）
当 TC较大时，通信量大，则 G 较小处理粒度较细。反之对于粗粒度的并行，通信量较小。
作业级（程序）
任务级 （ 过程或程序段 ）
子任务级（例行程序，或子程序）
指令或语句循环或递归循环级 5
级 4
级 3
级 2
级 1
通信需求与调度开销 并行程度粗粒度中粒度细粒度现代计算机程序运行并行性级别五种程序执行级别体现了不同的算法粒度规模以及通信和控制要求的变化 。 级别越低,软件进程的粒度越细 。 一般情况,程序可在这些级别的组合状态下运行 。
（ 1） 指令级,并行性发生在指令内部微操作之间或指令之间 。
取决于程序的具体情况 。 可借助于优化编译器开发细粒度并行性,它能自动检测并行性并将源代码换成运行时系统能识别的并行形式 。
（ 2） 循环级,相当于迭代循环操作,典型循环包含的指令大约几百条,循环级并行性是并行机或向量计算机上运行的最优程序结构,并行处理主要由编译器在循环级中进行开发 。
（ 3） 子任务级,属于中粒度 。 子程序是在单处理机或多处理机的多道程序设计这一级进行的 。 这一级并行性由算法设计者或程序员开发而非用编译器开发 。
（ 4） 任务级,这是与任务,过程,程序段,协同程序级相对应的中粒度或粗粒度规模 。 典型粒度包含的指令几千条,检测本级的并行性比细粒度级困难得多,需要更多地涉及过程间的相关性分析 。 需编译器支持 。
（ 5）作业（程序）级,对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。
小结：
细粒度并行性常在指令级或循环级上借助于并行化或向量化编译器来进行开发的 。
任务或作业步骤 （ 过程级 ） 中粒度并行性开发需要程序员和编译器的共同作用 。
开发程序作业级的粗粒度并行性主要取决于高效的操作系统和所用算法的效率 。
共享变量通信常用于支持中,细粒度计算 。 消息传递型多计算机用于中粒度和粗粒度的计算 。 通常情况下,粒度越细,并行性潜力越大,通信和调度的开销也越大 。 细粒度能提供较高的并行度,但与粗粒度计算相比,其通信开销也较大 。 大规模并行性通常是在细粒度级上开发 。 如,SIMD或
MIMD计算机上开发的数据并行性 。
提高计算机系统的并行性的技术途径,(单机系统 )
时间重叠（ Time Interleaving）,在并行性概念中引入时间因素。让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。
资源重复（ Resource Replication）,并行性概念中引入空间因素。通过重复设置的硬件资源来提高系统可靠性或性能。
例如，通过使用两台或多台完全相同的计算机完成同样的任务来提高可靠性。
资源共享（ Resource Sharing）,利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，
这样相应地提高整个系统的性能。例如多道程序分时系统,
6.2 并行处理技术及发展
(多机系统 )
功能专用化,机间互连,网络化技术途径发展成异构型多处理机,同构型多处理机,分布式处理机系统多道程序分时系统虚拟存储器多终端远程终端分布处理系统局域计算机网通信处理机计算机网多存储体多操作部件相联处理机并行处理机同构型多处理机系统可重构,容错多处理机紧密耦合系统现行控制高速缓存指令操作宏流水线异构型多处理机系统高级语言数据库处理机松散耦合系统、专用外围处理机多计算机系统单处理机资源共享资源重复时间重叠多机互连 功能专用化网络化并行处理技术发展一,并行处理机的基本构成并行处理机是通过重复设置大量相同的处理单元 PE（
Processing Element），将它们按一定的方式互连，在统一的控制部件 CU（ Control Unit）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。它依靠操作一级的并行处理来提高系统的速度。
并行处理机的控制部件中进行的是单指令流，因此与高性能单处理机一样，指令基本上是串行执行，最多加上使用指令重叠或流水线的方式工作。
指令重叠是将指令分成两类，把只适合串行处理的控制和标量类指令留给控制部件自己执行，而把适合于并行处理的向量类指令播送到所有处理单元，控制让处于活跃的那些处理单元去并行执行。因此这是一种标量控制类指令和向量类指令的重叠执行。
6.3 SIMD并行计算机（阵列处理机）
二 并行处理机分类并行处理机根据存贮器采用的组成方式不同分成两种基本构成 。
（ 1） 分布存贮的并行处理机各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器
（ Processing Element Memory） PEM。在控制部件 CU内设有一个用来存放程序的主存贮器 CUM。整个系统在 CU统一控制下运行系统程序的用户程序。执行主存中的用户程序指令播送给各个 PE，控制 PE并行地执行。
（ 2） 共享存贮的并行处理机 。
每个 PE没有局部存触器,存储模块以集中形式为所有
PE共享 。 互连网 IN受 CU控制,具有双向性采用分布式存贮器组成基本结构 。
…
ICN
PE0 PE1 PEN-1
MM0 MM1 MMN-1
CU SC
I/O-CH
I/O SM
…
…
PEM0
PE0
PEM1
PE1
PEMN-1
PEMN-1
ICN
CU
CUM
I/O
接口
D
SC
（ A）具有共享存贮器并行处理机结构
（ B）分布存贮器并行处理机结构
ILLIAC-IV 结构 （ 分 布存贮器并行处理机结构）
处理单元阵列 由 64个 PUi构成,每个 Pui包括 (PEi和 PEMi)
由 64个结构完全相同的处理单元 PEi 构成，每个处理单元
PEi字长 64位,PEMi为隶属于 PEi的局部存储器，每个存储器有
2K字，全部 PEi由 CU统一管理,PEi都有一根方式位线，用来向
CU传送每个 PEi的方式寄存器 D中的方式位，使 CU能了解各 PEi
的状态是否活动，作为控制它们工作的依据。
阵列控制器 CU 相当一台小型控制计算机对处理单元阵列实现控制,(发控制信号,广播公共地址,
广播公共数据 )对指令流进行译码控制,利用 CU内部资源可以进行标量操作,接受和处理各类中断，其他输入输出操作。
I/O系统由磁盘文件系统 DFS，输入输出子系统和宿主计算机 S/C
构成（驻留操作系统，编译程序,I/O服务程序等）
0
1
2047
PEM0
。。。。
0
1
2047
PEM1
。。。。
0
1
2047
PEM63
。。。。
X
D
A
B
RS
PE0
X
D
A
B
RS
PE1 PE63
0
1
63
。。。。
ACAR0
ACAR1
ACAR2
ACAR3
ALU
控制器 CU
累加器ADB
......
......
方位总线 指令控制线
CU总线
......
到 PE63 到 PE0
ILLIAC-IV的处理单元原理图
…..,D为方式位寄存器
R路由器互连用
PU1
6
PU0
PU8
PU7
PU5
5
PU6
3
PU0 PU1 PU7
PU8 PU9 PU15
PU56 PU57 PU63
PU0 PU1 PU7
PU5
6
PU5
7
PU5
8
ILLIAC-IV的处理单元互连图将 PU63传送到 PU10，最快可经
PU63→PU7→PU8→PU9→PU10 。
（ 1） 并行处理机,并行机中每个处理器以 160ns的时钟周期进行向量计算 。 所有 16个算术单元 AE对不同的数据组 （ 从并行处理机控制器广播来 ） 进行同一种指令操作 。
（ 2） 控制处理器,除了用以控制并行处理机以外,还提供了与系统管理机相连的接口 。
（ 3） 文件存储器,半导体辅助存储器 。 BSP的计算任务文件从系统管理机加载到它上面 。 然后对这些任务进行排队,
由控制处理机加以执行 。
（ 4） 对准网络,包完全交叉开关以及用来实现数据从一个源广播至几个目的地以及当几个源寻找一个目的地地址时能分解冲突的硬件 。 这就需要在算术单元阵列和存储器模块之间具备通用的互连特性 。 而存储模块和对准网络的组合功能则提供了并行存储器的无冲突访问能力 。 算术单元也利用输出对准网络来实现一些诸如数据压缩和扩展操作以及快速傅立叶变换算法等专用功能 。
科学处理机 BSP系统结构（集中式共享存贮器 )
指令译码控制部件处理器存储器
NW2NW1
17个存储块
16个处理单元对准网络对准网络
BSP的五级数据流水线构图 （集中式共享存贮器）
作用：
（ 1） 由 17个存储器模块并行读出 16个操作数；
（ 2） 经对准网络 NW1将 16个操作数重新排列成 16个处理单元所需要的次序；
（ 3） 将排列好的 16个操作送到并行处理单元完成操作；
（ 4） 所得的 16个结果经过对准网络 NW2重新排列成 17个存储器模块所需要的次序；
（ 5） 写入存储器；
BSP的五级数据流水线在 BSP中，存储器 -存储器型的浮点运算是流水进行的。
BSP的流水线组织由五个功能级组成。尤其是并行处理机包括有 16个处理单元,17个存储器模块和 2套互连网络（亦称对准网络）组合在一起，就形成了一条五级的数据流水线，使连续几条向量指令能在时间下重叠起来执行。
共同特点,可以通过各种途径把它们转化成为对数组或向量的处理,利用多个处理单元对向量或数组所包含的各个分量同时进行运算,从而易于获得很高的处理速度 。
三 并行处理机的特点并行处理机有如下特点：
（ 1） 利用资源重复 （ 空间因素 ） 而非时间重叠 。
（ 2） 利用同时性而非并发性 。 它的每个处理单元在同一时刻要同等地担负起各种运算功能 。
（ 3） 提高运算速度主要是靠增大处理单元个数,比起向量流水线处理机主要依靠缩短时钟周期来说,速度提高的潜力要大得多 。
（ 4） 使用简单而又规整的互连网络来确定多个处理单元之间的连接模式 。
（ 5） 并行处理机 （ 阵列机 ） 研究必须与并行算法研究密切结合,使之适应性更强,应用面更广 。
6,3,2 SIMD 并行处理机算法一,矩阵加矩阵加 (配比加 )是最简单的情况。假定两个 8*8的矩阵
A,B，相加，所得结果矩阵 C也是一个 8*8的矩阵 。设 A B
的分量元素分别存在 PEM i的 Z,Z+1单元中,所得结果矩阵 C
各分量存在 PEM i 的 Z+2单元中用下面三条指令可一次完成 (64个处理单元并行 )
LDA Z；全部（ Z）由 PEMi送到 PE的累加器 RGAi
ADRN Z+1；全部 （ Z+1） 与 （ RGAi） 进行浮点规舍加结果送 RGAi
STA Z+2；全部 （ RGAi） 由 PE送到 DEMi的 （ Z+2） 单元这里 0≤ i ≤63
Z
Z+1
Z+2
A（ 0,0）
B（ 0,0）
C（ 0,0）
PEM0
A（ 0,1）
B（ 0,1）
C（ 0,1）
PEM1
A（ 7,7）
B（ 7,7）
C（ 7,7）
PEM63
......
矩阵加存储器分举例矩阵乘是涉及二维数组运算 。 它比矩阵加复杂的多 。 设
A,B和 C为 3个 8*8的二维矩阵 。 若给定 A和 B,则为计算
C=A*B的 64个分量,可用下列公式：
其中 0≤i≤7,0≤j≤7 。
二,矩阵乘
bac kjikij *?
在 SISD计算机上求解这个问题,可执行 FORTRAN语言编写的下列程序 （ I,J,K三重循环,每重循环执行 8次,共需 512次乘,加的时间 ）
DO 10 I = 0,7
DO 10 J= 0,7
C（ I,J） = 0
DO 10 K = 0,7
10 C（ I,J） = C（ I,J） +A（ I,K） *B（ K,J）
A(0,0)
A(1,0)...
A(7,0)
B(0,0)
B(1,0)...
B(7,0)
C(0,0)
C(1,0)
...
C(7,0)
A(0,1)
A(1,1)...
A(7,1)
B(0,1)
B(1,1)...
B(7,1)
C(0,1)
C(1,1)
...
C(7,1)
A(0,7)
A(1,7)...
A(7,7)
B(0,7)
B(1,7)...
B(7,7)
C(0,7)
C(1,7)
...
C(7,7)
PEM1 PEM2 PEM7
...
矩阵乘存储器分配举例 （设用八个处理单元即 PU并行）
………………………...
八个局部存储器 PEM i,每个连续存放 A,B和结果向量 C的一列元素在 SIMD计算机上求解这个问题,(相当于原来的 J循环,用八个处理器同时进行一次乘加运算,共需 64次乘加时间 )
DO 10 I = 0,7
C（ I,J） = 0
DO 10 K = 0,7
10 C（ I,J） = C（ I,J） +A（ I,K） *B（ K,J）
进一步把 K循环也改为并行,相当于 64个单元全部并行运算,
DO 10 I = 0,7
C（ I,J） = 0
10 C（ I,J） = C（ I,J） +A（ I,K） *B（ K,J）
这时,数据重新分配在 64个局部存储器上,同时,八个中间积 A
（ I,K） *B（ K,J） 能够并行加 (累加 ),速度提高 8/Log28
三 累加和这是一个将 N个数的顺序相加过程转变为并行相加过程的问题。
设 N为 8,即有 8个数 A（ I） 顺序累加,其中 0<=I<=7
在 SISD计算机上可写成下列程序：
C=0
DO 10 I=0,7
10 C=C+A（ I）
用成对递归算法,只需 Log2 8=3
在 SISD计算机上可写成下列程序
C=A
DO 10 K=0,Log2 8 - 1
10 C=C+SHFTR(C,2**K)
其中 SHFTR(C,2**K)
是向量传送语句,C向量各分量向右传送步距为 2的 K次幂设原始数据 A（ I）分别存在 PEM的某个单元中
K=0 K=1 K=2
A0 A0 A0 A0
A1 A0+A1 A0+A1 A0+A1
A2 A1+A2 A0+A1+A2 A0+A1+A2
A3 A2+A3 A0+A1+A2+A3 A0+A1+A2+A3
A4 A3+A4 A1+A2+A3+A4 A0+A1+A2+A3+A4
A5 A4+A5 A2+A3+A4+A5 A0+A1+A2+A3+A4+A5
A6 A5+A6 A3+A4+A5+A6 A0+A1+A2+A3+A4+A5+A6
A7 A6+A7 A4+A5+A6+A7 A0+A1+A2+A3+A4+A5+A6+A7
步距 1 步距 2 步距 4
一,多处理机概念和特点多处理机是一种系统构造方式,具有多个处理机 （ 由多个指令部件执行部件分别控制 ） 共享主存或输入输出子系统,在统一操作系统控制下,通过共享主存或高速通讯网络进行通讯,在硬件,软件各级上相互作用,来协同求解问题,实现作业,任务级甚至指令级间并行 。
6.4 多处理机结构许多多处理机系统除了共享主存外,每个处理机都有自己局部存储器,甚至输入,输出设备,本身就构成了一台完整的计算机,每台计算机分别受各自独立操作系统控制,机间往往以通道或通信线路进行通讯,以文件或数据集交互作用实现任务作业级并行,这就是多计算机系统,我们以下讨论中笼统称为多处理机系统 。
6.4 多处理机结构 (MIMD)
一,多处理机概念特点多台处理机,通过共享主存或通讯网进行通讯,在软件,硬件各级相互作用,协同求解问题,实现指令间,到作业,任务级的并行。
（ 1） 具有更大的灵活性和更强的通用性 。
（ 2） 主要开发高层次作业及任务级 （ 粗粒性 ） 并行性
（ 3） 并行任务的派生需要用显式的专用语句或指令加以表示
,在 SIMD机中,并行操作由单独指令表示和控制,故不需要设置专门的指令 。
（ 4） 并发执行的进程间的同步需要采取特殊措施,以保证程序原来的正确语义 。 而在 SIMD机中,由于受统一控制器控制
,因此工作是自然同步的 。
（ 5） 对资源分配和任务分配要进行良好的调度,因此要采取软件手段,否则系统性能将受较大影响
（ 6） MIMD系统在执行条件语句时比 SIMD系统有较高的效率
（ 7） MIMD的异步特性使得它在执行一串完成时间可变的指令时,比 SIMD有更快的速率处理机 1
处理机 N
...
处理机 2
存储器存储器
...
存储器互连网络
I/O
I/O
（ a）共享存储型紧耦和系统处理机 1
处理机 N
...
处理机 2
存储器存储器
...
存储器互连网络
I/O
I/O
...
I/O
（ b）点对点型松耦合系统二,两种多处理机结构根据存储器存取方式分为三种模型均匀存储器存取 (Uniform-Memory-Access）简称 UMA
非均匀存储器存取（ Nonuniform-Memory-Access） NUMA
高速缓存存储结构（ Cache-Only-Memory Architecture）
COMA模型一,共享存储型多处理机多处理机系统中，多个处理器，高速缓存（ cache）一般利用公共总线实现互连。这类机器是通过共享主存实现处理机间的相互通信，（主存对所有处理器有统一的地址编址）
因此相互间的联系是比较紧密的。所有处理机共享 I/O设备或通过通道和外设相连，整个系统有统一的操作系统管理，提供处理机及程序之间的作业、任务、文件、数据各个级别上的相互联系。
UMA 模型,这 种 模 型 结 构 图 物 理 存 储 器 SM1,
SM2…… SMm被所有处理机均匀共享,所有处理机对所有存储字具有相同存取时间,每台处理机允许私有的 cache,系统的外部设备也可以一定形式共享 。
NUMA模型,是另一种共享存储器系统,其访问时间随存储字的位置不同而变化,其共享存储器物理上是分布在所有处理机的本地存储器上 。 所有本地存储器的集合组成了全局地址空间,可被所有的处理机访问 。
COMA模型,只用高速缓存的多处理机,是 NUMA机的一种特例,只是将后者分布主存储器换成了高速缓存,在每个处理机结点上没有存储器层次结构,全部高速缓冲存储器组成了全局地址空间 。
紧耦合系统多处理机分类进一步说明
I/O SM1 SMm
P1 P2 Pn
系统互连
(总线,交叉开关,多级网络 )
处理机
。。。。
。。。。
共享存储器
UMA多处理机模型
LM1 P1
LM2 P2
LMn Pn
互连网络。。
。
。
。
。
。
。
。。。。GSM
全局互连网络
GSM GSM
。
。
。
。
。
。
。
。
C
I
N
P
P
P
。
。
。
。
CSM
CSM
CSM
。
。
。
。
P
P
P
CSM
CSM
CSM
。。。。 CI
N
（ a） NUMA共享本地存储器（如 BBN
Butterfly）
（ b）层次式机群模型（如伊利诺伊大学的 Cedar系统）
多处理机系统的两种 NUMA模型互连网络
D
C
P
D
C
P
D
C
P
...
多处理机的 COMA模型它由多个计算机模块组成，每个节点有一台处理机和局部存储器及本身的输入输出设备，通过节点总线连在一起，计算机模块又通过节点接口接到互连网上，通过消息传递实现互相通信。各处理机物理连接松散，多分布式存储器，适于粗粒度的并行。松散耦合多处理机系统可分为层次型和非层次型。
松散耦合多处理机系统层次式,常采用多级总线实现层次连接。例子如机群系统，美国的卡内基 -梅隆大学研制的系统，是有 50个 LSI-11小型机组成三层总线的多处理机系统。
非层次式,各结点机（包括处理机，存储器,I/O系统和网络接口（ NI）
通过节点总线连在一起），而各个计算机模块又通过网络接口连到外部互连网上。通过消息传输系统（ MTS）对各结点机进行多个访问请求的仲裁。
松散耦合多计算机系统数据传送速度低，延迟时间长，各节点间距离不等，相互联系少。互连网如前面已讨论的各种构成多计算机的静态网络拓扑结构。环形、树形、网格、超立方体、带环立方体等。结点之间要求有相同的通信模式
P M I/O
NI
模块 1
消息传送系统 MTS
P M I/O
NI
模块 N
....
计算机模块
（ 节点机 ）
N1- 节点机接口松散耦合的多处理机系统
Cmn层次式多机系统单处理机,cache一致性问题只存在于 cache与主存之间,即使有 I/O通道共享 cache亦可通过全写法或回写法较好地加以解决；
多处理机,由于每一个处理机都有一个 cache,因此在写操作时,必须保证各 cache之间的数据一致性 。
导致多处理机系统中 cache内容不一致的因素有三个：
（ 1）可写数据的共享。 一台处理机采用全写法或回写法修改某一个数据块时，引起其它处理机的 cache中同一副本的不一致。
（ 2）输入输出活动。 如果输入输出处理机直接接在系统总线上，也会导致 cache不一致。
（ 3）进程迁移。 进程迁移就是把一个尚未执行完的进程调度到另一个空闲的处理机中去执行。为提高整个系统的效率，有的系统允许进程迁移，
使系统负载平衡。这将引起 cache的不一致。
四 多处理机 cache一致性硬件为基础方法,
监视 cache协议法（ snoopy cache protocol）
各个处理机中的 cache控制器都有一个监听部件，随时都在监视着其它 cache的行动。当一个处理机写入本身 cache中某一个数据块时，同时也写入主存，这个操作，起到了向总线上的其它处理机发送保持一致命令的作用，通知这些处理机，就应把这个副本作废或更新，以此来达到 cache的一致性。
把数据块作废的办法叫写作废法（ weite-invalidate），
把数据块更新的办法叫写更新法（ write-update）
解决多处理机 CACHE一致性有以硬件，软件为基础的两种方法当处理机数目很多,不采用总线结构时,监视协议法很困难。
将采用目录表法目录表法 （ directory scheme）
这种方法要在主存中建立一个目录表,记录各公用的数据块都存放在哪几个处理机的 cache中 。 表的每一项中记录一个数据块的使用情况,内容包括有几个指示器,指示器指出这个数据块的副本放在哪几个处理机的 cache中
,还有指示位表示是否已有 cache向这个数据块写入过新内容等 。 有了这个目录表,当一个处理机写入本身的
cache时,只需要有选择地通知存有这个数据块的处理机的 cache即可 。 使其内容或废除或更新 。
有三种目录表
* 全幅目录表法
* 有限目录表法
* 链接目录表法共享存储器
X,。。。c - - 数据- - -
Cache
P1
读 X
Cache
P2
读 X
Cache
P3
读 X
。。。
共享存储器X,。。。c - -
数据- - -
Cache
P1
Cache
P2
Cache
P3
X:数据 X:数据 X:数据
（ a）全幅目录表共享存储器
X,数据c
Cache
P3
CacheX:数据
P2
CacheX:数据
CT
P1P1
Cache Cache
P2
Cache
P3
。。。X:数据共享存储器
X,数据c
CT
读 X
（ c）链接目录表共享存储器
X,数据c
Cache
P1
Cache
P2
Cache
P3
读 X
。。。X:数据 X:数据 Cache
P1
Cache
P2
Cache
P3
。。。X:数据 X:数据共享存储器
X,数据c
（ b）有限目录表三种目录表法靠软件的作用来限制一些公用的可写数据存放到 cache中 。
在编译时,通过编译程序分析,把数据分为能用 cache
的 （ cacheable） 和不能用 cache的 （ noncacheable） 两部分
,不能用 cache的数据只能存在主存中 。 为了尽量提高工作效率,并不是把所有要写入的数据都归入不能用 cache的数据之列,编译程序在分析时,要看一下可写数据是否在哪一段时间里可以安全地存入 cache,哪一段时间里不允许写到 cache
中 。 使它在安全的期间使用 cache存放,等到这段安全时期终了时,再把这个可写数据在 cache中的副本作废,并规定不能用 cache。
这种方法比较简单，实际是避开了在 CACHE中实现可写数据的共享问题，影响系统性能。
以软件为基础的办法并行算法略（单设有并行算法课）
6.6.4 多处理机操作系统分类多处理机操作系统的功能：
资源分配和管理
表格和数据保护
防止系统死锁
非正常情况下的结束 （ 例外情况处理 ）
输入输出负载平衡
处理机负荷平衡
系统重新组合
主从型 Master-Slave Configuration）
主从型其管理程序只在一个指定的处理机（主处理机）上运行。该主处理机可以是专门的执行管理功能的控制处理机，也可以是与其它从处理机相同的通用机，除执行管理功能外，也能作其它方面的应用。
优点：
1,硬件结构比较简单；
2,简化了管理控制的实现；
3,实现起来简单、经济、方便，是目前大多数多处理机操作系统所采用的方式；
缺点：
1,对主处理机的可靠性要求很高；
2,整个系统显得不够灵活；
3,如果负荷过重，也会影响整个系统的性能；
各自独立型（ Separate Supervisor）
各自独立型将控制功能分散给多台处理机，共同完成对整个系统的控制工作。每台处理机都有一个独立的管理程序（操作系统的内核）在运行，即每台处理机都有一个内核的副本，
按自身的需要及分配给它的程序需要来执行各种管理功能。
优点：
1,很适应分布处理的模块化结构特点，减少对大型控制专用处理机的需求；
2,某个处理机发生故障，不会引起整个系统瘫痪，有较高的可靠性；
3,每台处理机都有其专用控制表格，使访问系统表格的冲突较少，也不会有许多公用的执行表，同时控制进程和用户进程一起进 行调度，能取得较高的系统效率。
缺点：
1,这种方式实现复杂；
2,某台处理机一旦发生故障，要想恢复和重新执行未完成的工作较困难；
3,使整个系统的输入输出结构变换需要操作员干预；
4,各台处理机需有局部存储器存放管理程序副本，降低了存储器的利用率。
浮动型方式 （ Floating Supervisor）
浮动型操作系统是界于主从型和各自独立型之间的一种折中方式，其管理程序可以在处理机之间浮动。在一段较长的时间里指定某一台处理机为控制处理机，但是具体指定哪一台处理机以及担任多长时间控制都不是固定的。这是一种最灵活但又最复杂的结构，系统中的负载平衡容易实现，适于对称紧耦合多处理机系统，其他优缺点介于二者之间,
6.7 多处理机系统举例 (自学 )
MPP大规模并行处理机我国研制的曙光 1000
SMP共享存储型多处理机机群系统
6.7.4 机群系统机群系统,利用高速通用网络将一组高性能工作站或高档 PC
机，按某种结构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。
原因：
（ 1） 由于 RISC技术的发展,使得微处理器的性能不断提高,价格在不断下降,直接使用商用工作站或 PC机作为运算结点的机群系统在结点性能上能够同处理器的发展保持同步增长 。 （ 2） 网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解 。 网络传输速度的提高,有效地提高了应用程序之间的通信带宽 。
（ 3） 并行编程环境的开发使得新编并行程序或改写串行程序更为容易 。 并行应用程序的开发和不同系统之间的可移植性一直是传统并行系统能否广泛应用的一个问题 。
机群系统的特点
1,系统开发周期短 。 开发的重点在通信和并行编程环境上,既不用重新研制计算结点,又不用重新设计操作系统和编译系统,
这就节省了大量的研制时间 。
2,用户投资风险小 。 机群系统不仅是一个并行处理系统,它的每个结点同时也是一台独立的工作站,即使整个系统对某些应用问题并行效率不高,它的结点仍然可以作为单个工作站使用 。
3,系统价格低 。 由于生产批量小,传统巨型机或 MPP的价格都比较昂贵,往往要几百万到上千万美元 。 工作站或高档 PC机由于它们是批量生产出来的,因而售价较低 。
4,节约系统资源 。 可以充分利用现有设备 。 单从使用效率上看,
机群系统的资源利用率也比单机系统要高的多
5,系统扩展性好 。 从规模上说,机群系统大多使用通用网络,
系统扩展容易；从性能上说,对大多数中,粗粒度的并行应用都有较高的效率 。
6,用户编程方便 。 机群系统中,程序的并行化只是在原有的
C,C++或 Fortran串行环境中,插入相应的通信原语 。 用户使用的仍然是熟悉的编程环境,不用适应新的环境,这样就可以继承原有的软件财富,对串行程序做并不很多的修改 。
机群系统的关键技术
1,高效的通信系统
2,并行程序设计环境
3,多种并行语言支持
4,全局资源的管理与利用
5,机群负载平衡技术在机群系统上,负载平衡要解决的问题主要有以下几点：
（ 1） 系统资源使用不均 。
（ 2）机群系统是多用户系统，同时可能有几个用户运行各自的作业。
四,几种典型系统目前国内外许多科研机构都在对机群系统下的通信技术进行深入的研究，如 UCB（ University of California，
Berkeley）提出的 NOW计划,Cornell大学研制的 U-Net系统，
清华大学提出的精简通信协议 RCP和快速消息传递机制
FMP等。
6.3 SIMD并行处理机
6.4 多处理机结构
6.5 多处理机高速缓冲存储器（ cache）一致性
6.5 多处理机举例第六章、并行处理技术和多处理机
6.1 概述
6.6 并行处理软件本章重点书 P252 6.1~6.9
一 并行性概念并行处理是一种有效的强调开发计算过程中并行事件的信息处理方式,
在数值计算，数据处理，知识处理或人工智能求解过程中，可能存在某些能同时进行运算或操作的部分。
同时性（ simultaneity）,指两个或多个事件在同一时刻发生在多个资源中。
并发性（ concurrency）,指两个或多个事件在同一时间间隔内发生在多个资源中
6.1 概述在同一时刻或同一时间间隔内完成多个性质相同或不同的任务
1．从计算机信息加工步骤和阶段看，并行性等级可分为：
存贮器操作并行 ----并行存贮器系统和以相联存贮器为核心构成的相联处理机。
处理器操作步骤并行 ----可以是一条指令的取指、分析、执行等操作步骤，也可以是具体运算。
处理器操作并行 ----为支持向量、数组运算，可以通过重复设置处理单元进行，如并行处理机指令、任务、作业并行 ----称为较高级并行，属于多指令流多数据流计算机。
二,并行的等级和分类
2,从系统结构发展看,
高性能的单处理机,SIMD并行处理机,多处理机,多计算机系统非冯,诺依曼计算机 (属于多处理机系统 )
并行性的开发还可以按程序大小划分不同粒度的开发方式 。
我们先来介绍两个概念：
颗粒规模 （ grain size） 或粒度 （ granularity） ---- 是衡量软件进程所含计算量的尺度 。 测量方法是数一下颗粒 （ 程序段
） 中的指令数目 。 一般用细,中,粗来描述,
时延 -（ TC ） 是机器各子系统间通信开销的时间量度 。 如：存贮时延是处理机访问存贮器所需时间；同步时延是两台处理机互相同步所需的时间 。
3,程序划分和粒度并行性粒度,每次并行处理的规模大小 。 用字母 G表示
G=TW/TC
TW：所有处理器进行计算的时间总和；
TC：所有处理器进行通信的时间总和。（设系统共有 P个处理器）
当 TC较大时，通信量大，则 G 较小处理粒度较细。反之对于粗粒度的并行，通信量较小。
作业级（程序）
任务级 （ 过程或程序段 ）
子任务级（例行程序，或子程序）
指令或语句循环或递归循环级 5
级 4
级 3
级 2
级 1
通信需求与调度开销 并行程度粗粒度中粒度细粒度现代计算机程序运行并行性级别五种程序执行级别体现了不同的算法粒度规模以及通信和控制要求的变化 。 级别越低,软件进程的粒度越细 。 一般情况,程序可在这些级别的组合状态下运行 。
（ 1） 指令级,并行性发生在指令内部微操作之间或指令之间 。
取决于程序的具体情况 。 可借助于优化编译器开发细粒度并行性,它能自动检测并行性并将源代码换成运行时系统能识别的并行形式 。
（ 2） 循环级,相当于迭代循环操作,典型循环包含的指令大约几百条,循环级并行性是并行机或向量计算机上运行的最优程序结构,并行处理主要由编译器在循环级中进行开发 。
（ 3） 子任务级,属于中粒度 。 子程序是在单处理机或多处理机的多道程序设计这一级进行的 。 这一级并行性由算法设计者或程序员开发而非用编译器开发 。
（ 4） 任务级,这是与任务,过程,程序段,协同程序级相对应的中粒度或粗粒度规模 。 典型粒度包含的指令几千条,检测本级的并行性比细粒度级困难得多,需要更多地涉及过程间的相关性分析 。 需编译器支持 。
（ 5）作业（程序）级,对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。
小结：
细粒度并行性常在指令级或循环级上借助于并行化或向量化编译器来进行开发的 。
任务或作业步骤 （ 过程级 ） 中粒度并行性开发需要程序员和编译器的共同作用 。
开发程序作业级的粗粒度并行性主要取决于高效的操作系统和所用算法的效率 。
共享变量通信常用于支持中,细粒度计算 。 消息传递型多计算机用于中粒度和粗粒度的计算 。 通常情况下,粒度越细,并行性潜力越大,通信和调度的开销也越大 。 细粒度能提供较高的并行度,但与粗粒度计算相比,其通信开销也较大 。 大规模并行性通常是在细粒度级上开发 。 如,SIMD或
MIMD计算机上开发的数据并行性 。
提高计算机系统的并行性的技术途径,(单机系统 )
时间重叠（ Time Interleaving）,在并行性概念中引入时间因素。让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。
资源重复（ Resource Replication）,并行性概念中引入空间因素。通过重复设置的硬件资源来提高系统可靠性或性能。
例如，通过使用两台或多台完全相同的计算机完成同样的任务来提高可靠性。
资源共享（ Resource Sharing）,利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，
这样相应地提高整个系统的性能。例如多道程序分时系统,
6.2 并行处理技术及发展
(多机系统 )
功能专用化,机间互连,网络化技术途径发展成异构型多处理机,同构型多处理机,分布式处理机系统多道程序分时系统虚拟存储器多终端远程终端分布处理系统局域计算机网通信处理机计算机网多存储体多操作部件相联处理机并行处理机同构型多处理机系统可重构,容错多处理机紧密耦合系统现行控制高速缓存指令操作宏流水线异构型多处理机系统高级语言数据库处理机松散耦合系统、专用外围处理机多计算机系统单处理机资源共享资源重复时间重叠多机互连 功能专用化网络化并行处理技术发展一,并行处理机的基本构成并行处理机是通过重复设置大量相同的处理单元 PE（
Processing Element），将它们按一定的方式互连，在统一的控制部件 CU（ Control Unit）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。它依靠操作一级的并行处理来提高系统的速度。
并行处理机的控制部件中进行的是单指令流，因此与高性能单处理机一样，指令基本上是串行执行，最多加上使用指令重叠或流水线的方式工作。
指令重叠是将指令分成两类，把只适合串行处理的控制和标量类指令留给控制部件自己执行，而把适合于并行处理的向量类指令播送到所有处理单元，控制让处于活跃的那些处理单元去并行执行。因此这是一种标量控制类指令和向量类指令的重叠执行。
6.3 SIMD并行计算机（阵列处理机）
二 并行处理机分类并行处理机根据存贮器采用的组成方式不同分成两种基本构成 。
（ 1） 分布存贮的并行处理机各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器
（ Processing Element Memory） PEM。在控制部件 CU内设有一个用来存放程序的主存贮器 CUM。整个系统在 CU统一控制下运行系统程序的用户程序。执行主存中的用户程序指令播送给各个 PE，控制 PE并行地执行。
（ 2） 共享存贮的并行处理机 。
每个 PE没有局部存触器,存储模块以集中形式为所有
PE共享 。 互连网 IN受 CU控制,具有双向性采用分布式存贮器组成基本结构 。
…
ICN
PE0 PE1 PEN-1
MM0 MM1 MMN-1
CU SC
I/O-CH
I/O SM
…
…
PEM0
PE0
PEM1
PE1
PEMN-1
PEMN-1
ICN
CU
CUM
I/O
接口
D
SC
（ A）具有共享存贮器并行处理机结构
（ B）分布存贮器并行处理机结构
ILLIAC-IV 结构 （ 分 布存贮器并行处理机结构）
处理单元阵列 由 64个 PUi构成,每个 Pui包括 (PEi和 PEMi)
由 64个结构完全相同的处理单元 PEi 构成，每个处理单元
PEi字长 64位,PEMi为隶属于 PEi的局部存储器，每个存储器有
2K字，全部 PEi由 CU统一管理,PEi都有一根方式位线，用来向
CU传送每个 PEi的方式寄存器 D中的方式位，使 CU能了解各 PEi
的状态是否活动，作为控制它们工作的依据。
阵列控制器 CU 相当一台小型控制计算机对处理单元阵列实现控制,(发控制信号,广播公共地址,
广播公共数据 )对指令流进行译码控制,利用 CU内部资源可以进行标量操作,接受和处理各类中断，其他输入输出操作。
I/O系统由磁盘文件系统 DFS，输入输出子系统和宿主计算机 S/C
构成（驻留操作系统，编译程序,I/O服务程序等）
0
1
2047
PEM0
。。。。
0
1
2047
PEM1
。。。。
0
1
2047
PEM63
。。。。
X
D
A
B
RS
PE0
X
D
A
B
RS
PE1 PE63
0
1
63
。。。。
ACAR0
ACAR1
ACAR2
ACAR3
ALU
控制器 CU
累加器ADB
......
......
方位总线 指令控制线
CU总线
......
到 PE63 到 PE0
ILLIAC-IV的处理单元原理图
…..,D为方式位寄存器
R路由器互连用
PU1
6
PU0
PU8
PU7
PU5
5
PU6
3
PU0 PU1 PU7
PU8 PU9 PU15
PU56 PU57 PU63
PU0 PU1 PU7
PU5
6
PU5
7
PU5
8
ILLIAC-IV的处理单元互连图将 PU63传送到 PU10，最快可经
PU63→PU7→PU8→PU9→PU10 。
（ 1） 并行处理机,并行机中每个处理器以 160ns的时钟周期进行向量计算 。 所有 16个算术单元 AE对不同的数据组 （ 从并行处理机控制器广播来 ） 进行同一种指令操作 。
（ 2） 控制处理器,除了用以控制并行处理机以外,还提供了与系统管理机相连的接口 。
（ 3） 文件存储器,半导体辅助存储器 。 BSP的计算任务文件从系统管理机加载到它上面 。 然后对这些任务进行排队,
由控制处理机加以执行 。
（ 4） 对准网络,包完全交叉开关以及用来实现数据从一个源广播至几个目的地以及当几个源寻找一个目的地地址时能分解冲突的硬件 。 这就需要在算术单元阵列和存储器模块之间具备通用的互连特性 。 而存储模块和对准网络的组合功能则提供了并行存储器的无冲突访问能力 。 算术单元也利用输出对准网络来实现一些诸如数据压缩和扩展操作以及快速傅立叶变换算法等专用功能 。
科学处理机 BSP系统结构（集中式共享存贮器 )
指令译码控制部件处理器存储器
NW2NW1
17个存储块
16个处理单元对准网络对准网络
BSP的五级数据流水线构图 （集中式共享存贮器）
作用：
（ 1） 由 17个存储器模块并行读出 16个操作数；
（ 2） 经对准网络 NW1将 16个操作数重新排列成 16个处理单元所需要的次序；
（ 3） 将排列好的 16个操作送到并行处理单元完成操作；
（ 4） 所得的 16个结果经过对准网络 NW2重新排列成 17个存储器模块所需要的次序；
（ 5） 写入存储器；
BSP的五级数据流水线在 BSP中，存储器 -存储器型的浮点运算是流水进行的。
BSP的流水线组织由五个功能级组成。尤其是并行处理机包括有 16个处理单元,17个存储器模块和 2套互连网络（亦称对准网络）组合在一起，就形成了一条五级的数据流水线，使连续几条向量指令能在时间下重叠起来执行。
共同特点,可以通过各种途径把它们转化成为对数组或向量的处理,利用多个处理单元对向量或数组所包含的各个分量同时进行运算,从而易于获得很高的处理速度 。
三 并行处理机的特点并行处理机有如下特点：
（ 1） 利用资源重复 （ 空间因素 ） 而非时间重叠 。
（ 2） 利用同时性而非并发性 。 它的每个处理单元在同一时刻要同等地担负起各种运算功能 。
（ 3） 提高运算速度主要是靠增大处理单元个数,比起向量流水线处理机主要依靠缩短时钟周期来说,速度提高的潜力要大得多 。
（ 4） 使用简单而又规整的互连网络来确定多个处理单元之间的连接模式 。
（ 5） 并行处理机 （ 阵列机 ） 研究必须与并行算法研究密切结合,使之适应性更强,应用面更广 。
6,3,2 SIMD 并行处理机算法一,矩阵加矩阵加 (配比加 )是最简单的情况。假定两个 8*8的矩阵
A,B，相加，所得结果矩阵 C也是一个 8*8的矩阵 。设 A B
的分量元素分别存在 PEM i的 Z,Z+1单元中,所得结果矩阵 C
各分量存在 PEM i 的 Z+2单元中用下面三条指令可一次完成 (64个处理单元并行 )
LDA Z；全部（ Z）由 PEMi送到 PE的累加器 RGAi
ADRN Z+1；全部 （ Z+1） 与 （ RGAi） 进行浮点规舍加结果送 RGAi
STA Z+2；全部 （ RGAi） 由 PE送到 DEMi的 （ Z+2） 单元这里 0≤ i ≤63
Z
Z+1
Z+2
A（ 0,0）
B（ 0,0）
C（ 0,0）
PEM0
A（ 0,1）
B（ 0,1）
C（ 0,1）
PEM1
A（ 7,7）
B（ 7,7）
C（ 7,7）
PEM63
......
矩阵加存储器分举例矩阵乘是涉及二维数组运算 。 它比矩阵加复杂的多 。 设
A,B和 C为 3个 8*8的二维矩阵 。 若给定 A和 B,则为计算
C=A*B的 64个分量,可用下列公式：
其中 0≤i≤7,0≤j≤7 。
二,矩阵乘
bac kjikij *?
在 SISD计算机上求解这个问题,可执行 FORTRAN语言编写的下列程序 （ I,J,K三重循环,每重循环执行 8次,共需 512次乘,加的时间 ）
DO 10 I = 0,7
DO 10 J= 0,7
C（ I,J） = 0
DO 10 K = 0,7
10 C（ I,J） = C（ I,J） +A（ I,K） *B（ K,J）
A(0,0)
A(1,0)...
A(7,0)
B(0,0)
B(1,0)...
B(7,0)
C(0,0)
C(1,0)
...
C(7,0)
A(0,1)
A(1,1)...
A(7,1)
B(0,1)
B(1,1)...
B(7,1)
C(0,1)
C(1,1)
...
C(7,1)
A(0,7)
A(1,7)...
A(7,7)
B(0,7)
B(1,7)...
B(7,7)
C(0,7)
C(1,7)
...
C(7,7)
PEM1 PEM2 PEM7
...
矩阵乘存储器分配举例 （设用八个处理单元即 PU并行）
………………………...
八个局部存储器 PEM i,每个连续存放 A,B和结果向量 C的一列元素在 SIMD计算机上求解这个问题,(相当于原来的 J循环,用八个处理器同时进行一次乘加运算,共需 64次乘加时间 )
DO 10 I = 0,7
C（ I,J） = 0
DO 10 K = 0,7
10 C（ I,J） = C（ I,J） +A（ I,K） *B（ K,J）
进一步把 K循环也改为并行,相当于 64个单元全部并行运算,
DO 10 I = 0,7
C（ I,J） = 0
10 C（ I,J） = C（ I,J） +A（ I,K） *B（ K,J）
这时,数据重新分配在 64个局部存储器上,同时,八个中间积 A
（ I,K） *B（ K,J） 能够并行加 (累加 ),速度提高 8/Log28
三 累加和这是一个将 N个数的顺序相加过程转变为并行相加过程的问题。
设 N为 8,即有 8个数 A（ I） 顺序累加,其中 0<=I<=7
在 SISD计算机上可写成下列程序：
C=0
DO 10 I=0,7
10 C=C+A（ I）
用成对递归算法,只需 Log2 8=3
在 SISD计算机上可写成下列程序
C=A
DO 10 K=0,Log2 8 - 1
10 C=C+SHFTR(C,2**K)
其中 SHFTR(C,2**K)
是向量传送语句,C向量各分量向右传送步距为 2的 K次幂设原始数据 A（ I）分别存在 PEM的某个单元中
K=0 K=1 K=2
A0 A0 A0 A0
A1 A0+A1 A0+A1 A0+A1
A2 A1+A2 A0+A1+A2 A0+A1+A2
A3 A2+A3 A0+A1+A2+A3 A0+A1+A2+A3
A4 A3+A4 A1+A2+A3+A4 A0+A1+A2+A3+A4
A5 A4+A5 A2+A3+A4+A5 A0+A1+A2+A3+A4+A5
A6 A5+A6 A3+A4+A5+A6 A0+A1+A2+A3+A4+A5+A6
A7 A6+A7 A4+A5+A6+A7 A0+A1+A2+A3+A4+A5+A6+A7
步距 1 步距 2 步距 4
一,多处理机概念和特点多处理机是一种系统构造方式,具有多个处理机 （ 由多个指令部件执行部件分别控制 ） 共享主存或输入输出子系统,在统一操作系统控制下,通过共享主存或高速通讯网络进行通讯,在硬件,软件各级上相互作用,来协同求解问题,实现作业,任务级甚至指令级间并行 。
6.4 多处理机结构许多多处理机系统除了共享主存外,每个处理机都有自己局部存储器,甚至输入,输出设备,本身就构成了一台完整的计算机,每台计算机分别受各自独立操作系统控制,机间往往以通道或通信线路进行通讯,以文件或数据集交互作用实现任务作业级并行,这就是多计算机系统,我们以下讨论中笼统称为多处理机系统 。
6.4 多处理机结构 (MIMD)
一,多处理机概念特点多台处理机,通过共享主存或通讯网进行通讯,在软件,硬件各级相互作用,协同求解问题,实现指令间,到作业,任务级的并行。
（ 1） 具有更大的灵活性和更强的通用性 。
（ 2） 主要开发高层次作业及任务级 （ 粗粒性 ） 并行性
（ 3） 并行任务的派生需要用显式的专用语句或指令加以表示
,在 SIMD机中,并行操作由单独指令表示和控制,故不需要设置专门的指令 。
（ 4） 并发执行的进程间的同步需要采取特殊措施,以保证程序原来的正确语义 。 而在 SIMD机中,由于受统一控制器控制
,因此工作是自然同步的 。
（ 5） 对资源分配和任务分配要进行良好的调度,因此要采取软件手段,否则系统性能将受较大影响
（ 6） MIMD系统在执行条件语句时比 SIMD系统有较高的效率
（ 7） MIMD的异步特性使得它在执行一串完成时间可变的指令时,比 SIMD有更快的速率处理机 1
处理机 N
...
处理机 2
存储器存储器
...
存储器互连网络
I/O
I/O
（ a）共享存储型紧耦和系统处理机 1
处理机 N
...
处理机 2
存储器存储器
...
存储器互连网络
I/O
I/O
...
I/O
（ b）点对点型松耦合系统二,两种多处理机结构根据存储器存取方式分为三种模型均匀存储器存取 (Uniform-Memory-Access）简称 UMA
非均匀存储器存取（ Nonuniform-Memory-Access） NUMA
高速缓存存储结构（ Cache-Only-Memory Architecture）
COMA模型一,共享存储型多处理机多处理机系统中，多个处理器，高速缓存（ cache）一般利用公共总线实现互连。这类机器是通过共享主存实现处理机间的相互通信，（主存对所有处理器有统一的地址编址）
因此相互间的联系是比较紧密的。所有处理机共享 I/O设备或通过通道和外设相连，整个系统有统一的操作系统管理，提供处理机及程序之间的作业、任务、文件、数据各个级别上的相互联系。
UMA 模型,这 种 模 型 结 构 图 物 理 存 储 器 SM1,
SM2…… SMm被所有处理机均匀共享,所有处理机对所有存储字具有相同存取时间,每台处理机允许私有的 cache,系统的外部设备也可以一定形式共享 。
NUMA模型,是另一种共享存储器系统,其访问时间随存储字的位置不同而变化,其共享存储器物理上是分布在所有处理机的本地存储器上 。 所有本地存储器的集合组成了全局地址空间,可被所有的处理机访问 。
COMA模型,只用高速缓存的多处理机,是 NUMA机的一种特例,只是将后者分布主存储器换成了高速缓存,在每个处理机结点上没有存储器层次结构,全部高速缓冲存储器组成了全局地址空间 。
紧耦合系统多处理机分类进一步说明
I/O SM1 SMm
P1 P2 Pn
系统互连
(总线,交叉开关,多级网络 )
处理机
。。。。
。。。。
共享存储器
UMA多处理机模型
LM1 P1
LM2 P2
LMn Pn
互连网络。。
。
。
。
。
。
。
。。。。GSM
全局互连网络
GSM GSM
。
。
。
。
。
。
。
。
C
I
N
P
P
P
。
。
。
。
CSM
CSM
CSM
。
。
。
。
P
P
P
CSM
CSM
CSM
。。。。 CI
N
（ a） NUMA共享本地存储器（如 BBN
Butterfly）
（ b）层次式机群模型（如伊利诺伊大学的 Cedar系统）
多处理机系统的两种 NUMA模型互连网络
D
C
P
D
C
P
D
C
P
...
多处理机的 COMA模型它由多个计算机模块组成，每个节点有一台处理机和局部存储器及本身的输入输出设备，通过节点总线连在一起，计算机模块又通过节点接口接到互连网上，通过消息传递实现互相通信。各处理机物理连接松散，多分布式存储器，适于粗粒度的并行。松散耦合多处理机系统可分为层次型和非层次型。
松散耦合多处理机系统层次式,常采用多级总线实现层次连接。例子如机群系统，美国的卡内基 -梅隆大学研制的系统，是有 50个 LSI-11小型机组成三层总线的多处理机系统。
非层次式,各结点机（包括处理机，存储器,I/O系统和网络接口（ NI）
通过节点总线连在一起），而各个计算机模块又通过网络接口连到外部互连网上。通过消息传输系统（ MTS）对各结点机进行多个访问请求的仲裁。
松散耦合多计算机系统数据传送速度低，延迟时间长，各节点间距离不等，相互联系少。互连网如前面已讨论的各种构成多计算机的静态网络拓扑结构。环形、树形、网格、超立方体、带环立方体等。结点之间要求有相同的通信模式
P M I/O
NI
模块 1
消息传送系统 MTS
P M I/O
NI
模块 N
....
计算机模块
（ 节点机 ）
N1- 节点机接口松散耦合的多处理机系统
Cmn层次式多机系统单处理机,cache一致性问题只存在于 cache与主存之间,即使有 I/O通道共享 cache亦可通过全写法或回写法较好地加以解决；
多处理机,由于每一个处理机都有一个 cache,因此在写操作时,必须保证各 cache之间的数据一致性 。
导致多处理机系统中 cache内容不一致的因素有三个：
（ 1）可写数据的共享。 一台处理机采用全写法或回写法修改某一个数据块时，引起其它处理机的 cache中同一副本的不一致。
（ 2）输入输出活动。 如果输入输出处理机直接接在系统总线上，也会导致 cache不一致。
（ 3）进程迁移。 进程迁移就是把一个尚未执行完的进程调度到另一个空闲的处理机中去执行。为提高整个系统的效率，有的系统允许进程迁移，
使系统负载平衡。这将引起 cache的不一致。
四 多处理机 cache一致性硬件为基础方法,
监视 cache协议法（ snoopy cache protocol）
各个处理机中的 cache控制器都有一个监听部件，随时都在监视着其它 cache的行动。当一个处理机写入本身 cache中某一个数据块时，同时也写入主存，这个操作，起到了向总线上的其它处理机发送保持一致命令的作用，通知这些处理机，就应把这个副本作废或更新，以此来达到 cache的一致性。
把数据块作废的办法叫写作废法（ weite-invalidate），
把数据块更新的办法叫写更新法（ write-update）
解决多处理机 CACHE一致性有以硬件，软件为基础的两种方法当处理机数目很多,不采用总线结构时,监视协议法很困难。
将采用目录表法目录表法 （ directory scheme）
这种方法要在主存中建立一个目录表,记录各公用的数据块都存放在哪几个处理机的 cache中 。 表的每一项中记录一个数据块的使用情况,内容包括有几个指示器,指示器指出这个数据块的副本放在哪几个处理机的 cache中
,还有指示位表示是否已有 cache向这个数据块写入过新内容等 。 有了这个目录表,当一个处理机写入本身的
cache时,只需要有选择地通知存有这个数据块的处理机的 cache即可 。 使其内容或废除或更新 。
有三种目录表
* 全幅目录表法
* 有限目录表法
* 链接目录表法共享存储器
X,。。。c - - 数据- - -
Cache
P1
读 X
Cache
P2
读 X
Cache
P3
读 X
。。。
共享存储器X,。。。c - -
数据- - -
Cache
P1
Cache
P2
Cache
P3
X:数据 X:数据 X:数据
（ a）全幅目录表共享存储器
X,数据c
Cache
P3
CacheX:数据
P2
CacheX:数据
CT
P1P1
Cache Cache
P2
Cache
P3
。。。X:数据共享存储器
X,数据c
CT
读 X
（ c）链接目录表共享存储器
X,数据c
Cache
P1
Cache
P2
Cache
P3
读 X
。。。X:数据 X:数据 Cache
P1
Cache
P2
Cache
P3
。。。X:数据 X:数据共享存储器
X,数据c
（ b）有限目录表三种目录表法靠软件的作用来限制一些公用的可写数据存放到 cache中 。
在编译时,通过编译程序分析,把数据分为能用 cache
的 （ cacheable） 和不能用 cache的 （ noncacheable） 两部分
,不能用 cache的数据只能存在主存中 。 为了尽量提高工作效率,并不是把所有要写入的数据都归入不能用 cache的数据之列,编译程序在分析时,要看一下可写数据是否在哪一段时间里可以安全地存入 cache,哪一段时间里不允许写到 cache
中 。 使它在安全的期间使用 cache存放,等到这段安全时期终了时,再把这个可写数据在 cache中的副本作废,并规定不能用 cache。
这种方法比较简单，实际是避开了在 CACHE中实现可写数据的共享问题，影响系统性能。
以软件为基础的办法并行算法略（单设有并行算法课）
6.6.4 多处理机操作系统分类多处理机操作系统的功能：
资源分配和管理
表格和数据保护
防止系统死锁
非正常情况下的结束 （ 例外情况处理 ）
输入输出负载平衡
处理机负荷平衡
系统重新组合
主从型 Master-Slave Configuration）
主从型其管理程序只在一个指定的处理机（主处理机）上运行。该主处理机可以是专门的执行管理功能的控制处理机，也可以是与其它从处理机相同的通用机，除执行管理功能外，也能作其它方面的应用。
优点：
1,硬件结构比较简单；
2,简化了管理控制的实现；
3,实现起来简单、经济、方便，是目前大多数多处理机操作系统所采用的方式；
缺点：
1,对主处理机的可靠性要求很高；
2,整个系统显得不够灵活；
3,如果负荷过重，也会影响整个系统的性能；
各自独立型（ Separate Supervisor）
各自独立型将控制功能分散给多台处理机，共同完成对整个系统的控制工作。每台处理机都有一个独立的管理程序（操作系统的内核）在运行，即每台处理机都有一个内核的副本，
按自身的需要及分配给它的程序需要来执行各种管理功能。
优点：
1,很适应分布处理的模块化结构特点，减少对大型控制专用处理机的需求；
2,某个处理机发生故障，不会引起整个系统瘫痪，有较高的可靠性；
3,每台处理机都有其专用控制表格，使访问系统表格的冲突较少，也不会有许多公用的执行表，同时控制进程和用户进程一起进 行调度，能取得较高的系统效率。
缺点：
1,这种方式实现复杂；
2,某台处理机一旦发生故障，要想恢复和重新执行未完成的工作较困难；
3,使整个系统的输入输出结构变换需要操作员干预；
4,各台处理机需有局部存储器存放管理程序副本，降低了存储器的利用率。
浮动型方式 （ Floating Supervisor）
浮动型操作系统是界于主从型和各自独立型之间的一种折中方式，其管理程序可以在处理机之间浮动。在一段较长的时间里指定某一台处理机为控制处理机，但是具体指定哪一台处理机以及担任多长时间控制都不是固定的。这是一种最灵活但又最复杂的结构，系统中的负载平衡容易实现，适于对称紧耦合多处理机系统，其他优缺点介于二者之间,
6.7 多处理机系统举例 (自学 )
MPP大规模并行处理机我国研制的曙光 1000
SMP共享存储型多处理机机群系统
6.7.4 机群系统机群系统,利用高速通用网络将一组高性能工作站或高档 PC
机，按某种结构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。
原因：
（ 1） 由于 RISC技术的发展,使得微处理器的性能不断提高,价格在不断下降,直接使用商用工作站或 PC机作为运算结点的机群系统在结点性能上能够同处理器的发展保持同步增长 。 （ 2） 网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解 。 网络传输速度的提高,有效地提高了应用程序之间的通信带宽 。
（ 3） 并行编程环境的开发使得新编并行程序或改写串行程序更为容易 。 并行应用程序的开发和不同系统之间的可移植性一直是传统并行系统能否广泛应用的一个问题 。
机群系统的特点
1,系统开发周期短 。 开发的重点在通信和并行编程环境上,既不用重新研制计算结点,又不用重新设计操作系统和编译系统,
这就节省了大量的研制时间 。
2,用户投资风险小 。 机群系统不仅是一个并行处理系统,它的每个结点同时也是一台独立的工作站,即使整个系统对某些应用问题并行效率不高,它的结点仍然可以作为单个工作站使用 。
3,系统价格低 。 由于生产批量小,传统巨型机或 MPP的价格都比较昂贵,往往要几百万到上千万美元 。 工作站或高档 PC机由于它们是批量生产出来的,因而售价较低 。
4,节约系统资源 。 可以充分利用现有设备 。 单从使用效率上看,
机群系统的资源利用率也比单机系统要高的多
5,系统扩展性好 。 从规模上说,机群系统大多使用通用网络,
系统扩展容易；从性能上说,对大多数中,粗粒度的并行应用都有较高的效率 。
6,用户编程方便 。 机群系统中,程序的并行化只是在原有的
C,C++或 Fortran串行环境中,插入相应的通信原语 。 用户使用的仍然是熟悉的编程环境,不用适应新的环境,这样就可以继承原有的软件财富,对串行程序做并不很多的修改 。
机群系统的关键技术
1,高效的通信系统
2,并行程序设计环境
3,多种并行语言支持
4,全局资源的管理与利用
5,机群负载平衡技术在机群系统上,负载平衡要解决的问题主要有以下几点：
（ 1） 系统资源使用不均 。
（ 2）机群系统是多用户系统，同时可能有几个用户运行各自的作业。
四,几种典型系统目前国内外许多科研机构都在对机群系统下的通信技术进行深入的研究，如 UCB（ University of California，
Berkeley）提出的 NOW计划,Cornell大学研制的 U-Net系统，
清华大学提出的精简通信协议 RCP和快速消息传递机制
FMP等。
