并行计算机的抽象模型课件

并行计算机的抽象模型并行计算机的理论模型是从物理模型抽象的；为开发并行算法提供了一种方便的框架；用这些模型可求得并行计算机的理论性能界限；可在芯片制作前估算芯片区的VLSI复杂性和执行时间。一、时间与空间复杂性计算机求解一个规模为s的问题的算法复杂性取决于：执行时间存储空间时间复杂性：时间复杂性g(s)为O(f(s))，可读作“数量级为f(s)”，如存在正的常量c和s0，则对所有s>s0的非负值就有g(s)≤cf(s)。空间复杂性为问题规模s的函数。渐近空间复杂性(asymptoticspacecom—plexity)主要与大问题的数据存储有关，而程序(代码)存储的需求和输入数据的存储不考虑在内。串行算法的时间复杂性简称为串行复杂性;并行算法的时间复杂性就称为并行复杂性;并行复杂性应比串行复杂性低，至少是相近。只考虑确定性算法。NP完全性：P类(即多项式类)：具有多项式复杂性算法的问题集，如果存在一多项式p(s)，对任何问题规模s的时间复杂性为O(p(s))，则某算法即具有多项式复杂性。NP类(即不确定性多项式类)：能以多项式时间，用不确定性算法求解的问题集。P

NP确定性算法是不确定算法的特殊情况。P类问题是计算易解的，而NP-P类问题是难解的。现在不知道是否P＝NP或P≠NP。难解的NP类问题又称为具有指数时间复杂性的问题。例题：多项式复杂性和指数复杂性算法：将几个数排序的多项式时间复杂性分别为O(nlogn)，属于P类对两个n×n矩阵相乘算法的多项式时间复杂性分别为O(n3)，属于P类。旅行推销员问题复杂性为O(n22n)和背包问题的复杂性为O(2n/2)指数复杂性问题是属NP类的：到目前为止还未发现这类问题的确定性多项式算法。P、NP和NPC（NP完全问题）二、并行随机存取机模型(ParallelRandom—AccessMachine，PRAM)目的：可用来开发并行算法和分析可扩展性及复杂性。MIMD细粒度严格同步零开销共享变量在PRAM上的一个并行程序由n个进程组成，其中第i个进程留驻在第i个处理器上，且由一串指令所组成。在每个基本时间步(称为周期)，每个处理器执行一条指令。这些指令包括数据传送、算/逻、控制流以及I/O指令，在典型的顺序计算机中均有这些指令。1.同构性规模为1的PRAM退化为传统的RAM。这种机器为SISD。当处理器多于1个时，一个PRAM将访问多个数据流，且通常可执行多个指令流。因此PRAM是一个MIMD机器。MIMD的特例:如果在每一周期，所有处理器必须执行相同指令，即只有一个指令流时，则PRAM就成为单指令(流)、多数据(流)(SIMD)机器。(SPMD)计算：单程序、多数据，所有进程执行同一程序，而由进程指标加以参数化。SIMD和SPMD间的差别是，在SPMD计算中，同一周期可以执行不同指令。2.同步性进程同步是严格的。PRAM是在指令级同步的。3.交互机制这一属性描述了并行进程间如何相互影响行为的特性。在PRAM模型中，进程间通过共享变量(或共享存储器)进行交互。4.地址空间理论PRAM模型的一个重要特征是所有进程对所有存储单元均有相等的访问时间。这种机器为均匀存储器访问(UMA)。在多计算机中，每个处理机有它自己的分离地址空间。这些机器被称为具有多地址空间。多计算机的处理机间通信不是通过共享变量，而是借助消息传递。5.存储器模型各种方案的主要区别在于如何协调CW的冲突。四种PRAM模型方案都与存储器读写如何处理有关。(1)EREW-PRAM模型——这种模型禁止一台以上处理机同时读、写同一存储单元(Snir，1982；Karp和Ramachandran，1988)。这是限制最大的PRAM模型。(2)CREW-PRAM模型——用互斥使写冲突避免。可以并行读同一存储单元。

(3)ERCW-PRAM模型——允许互斥读或并行写同一存储单元。(4)CRCW-PRAM模型——允许在同一时刻并行读或者并行写。写冲突可用下述四种策略之一分解：共用——所有同时进行的写操作将相同数据存入热点存储单元。任选——将任何一个要写的数保存起来，而其它的忽略不计。最小值——将处理机要写的下标值最小的数保存起来。优先——对要写的数用求和或求最大值等联想函数加以组合。

6.原子操作原子操作的定义：一个原子操作是指有如下特性的一种操作。不可分有限更严格的原子操作定义：需要满足以下的4个性质。称这样的原子操作为一个事务操作。

原子性一致性隔离性持续性7.例题例题1：在一台处理机数为n3／logn的PRAM上，用O(logn)时间完成两个”nxn”矩阵的乘法(ViktorPrasanna，1992)设A和B为输入矩阵，假定最初可用的PE数为n3个，后来降为n3／logn个。

假设内存由三维阵列组成，将A、B存入其中两个平面。假设了PE的三维地址指标。PE(i，j，k)，0≤k≤n-1可用来计算输出矩阵的第(i，j)项，0≤i，j≤n-1，n是2的幂。

第一步，对应于每个输出的n乘积项用n个PE在O(1)时间内进行计算。第二步，这些乘积项用O(logn)时间相加产生一个输出。所用的PE总数为n3，结果存在C(i，j，0)中(0≤i，j≤n-1)。假定这里的PRAM采用的是CREW策略。Step1：1．ReadA(i，k)2．ReadB(k，j)3．ComputeA(i，k)×B(k,j)4．StoreinC(I,j,k)

Step2：

1．L←n2．RepeatL←L／2If(k<1)thenbegin

ReadA(i，k)ReadA(i，k)ComputeC(i,j,k)+C(i,j,k,k+l)StoreinC(i,j,k)EndUntil(l=1)上述是每个PE(i，j，k)要执行的程序。所有n3个PE对n3乘法进行并行运算。但对完成(n3-n2)加法最多只有n3／2个PE处于工作状态。为了将PE数降为n3／logn，可采用nXnXn／logn的PE阵列。每个PE负责计算logn个乘积项并将它们求和。第一步很容易改写产生n／logn个部分和，每一个部分和由logn次乘法和(logn-1)次加法完成。我们有数组C(i，j，k)，0≤i，j≤n-1，0≤k≤n／logn-1，它们可在log(n／logn)时间内完成求和，所以将第一步和第二步所花的时间相加，我们就得到总执行时间为2logn-1+log(n／logn)，在n比较大时近似为O(logn)。例题2：PRAM步中的计算复杂性

假设有三个PRAM算法A，B和C，当在一个有n个处理器的PRAM计算机上执行时，各自的时间复杂性为A--7n，B--(nlogn)／4C--nloglogn。根据大O标志：算法A最快：(O(n))，C次之：O(nloglogn)，B为最慢：O(nlogn)。而实际上，当机器的处理器数小于、等于1024时，有logn<log1024=10以及loglogn≤loglog1024<4。如果，处理器数小于1024时：算法B最快，其次是C，而A则是最慢的。与物理模型的差异

实际上，这种并行计算机是不存在的。共享存储器SIMD机是与PRAM模型最接近的结构。更确切地说，共享存储的同步MIMD模式运行。四种PRAM方案中，EREW和CRCW是应用最普遍的模型。每个CRCW算法可用一个EREW算法来模拟。CRCW算法比一个等效的EREW要快，经证明，最好的n—处理机EREW算法要比任一个n-处理机CRCW算法慢O(logn)倍。对研究结构规则的并行性来说，用PRAM比用实际机器模型要好得多。PRAM能指出实际并行计算机性能的上限。三、异步PRAM模型—APRAM是一个异步的PRAM模型，简记为APRAM1.模型特点：由p个处理器组成；每个处理器都有其本地存储器、局部时钟和局部程序；处理器间的通信经过共享全局存储器；无全局时钟各处理器异步地独立执行各自的指令；处理器任何时间依赖关系需明确地在各处理器的程序中加入同步(路)障(SynchronizationBarrier)；一条指令可在非确定但有限的时间内完成。2、APRAM模型中的指令类型有四类指令：①全局读将全局存储单元中的内容读入局存单元中；②局部操作对局存中的数执行操作，其结果存入局存中；③全局写将局存单元中的内容写入全局存储单元中；④同步同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后，才能执行其局部程序。3.APRAM模型中完成的计算

计算是由一系列用同步障分开的全局相所组成。在各全局相内，每个处理器异步地运行其局部程序；每个局部程序中的最后一条指令是一条同步障指令；各处理器均可异步地读取和写入全局存储器，在同一相内不允许两个处理器访问同一单元。不同的处理器访问存储单元总是由一同步障所分开，所以指令完成时间上的差异并不影响整个计算4.APRAM模型中的时间计算使用APRAM模型计算算法的时间复杂度时，假定局部操作取单位时间；全局读／写时间为d它定量化了通信延迟，代表读/写全局存储器的平均时间，d随机器中的处理器增加而增加；同步障的时间为B它是处理器数P的非降函数B=B(P)。在APRAM中假定上述参数服从如下关系：2≤d≤B≤P同时：B(P)∈O(dlogP)或B(P)∈O(dlogP/logd)。令tph为全局相内各处理器指令执行时间中最长者，则整个程序运行时间T为各相的时间之和加上B乘以同步障次数，即:T=∑tph+B×同步障次数四.BSP模型BSP-BulkSynchronizationParallel1.BSP模型的提出：哈佛大学的LeslieValiant提出：块同步并行(BSP)，用以克服PRAM模型的缺点，但保留其简单性。一个BSP计算机由n个结点(处理器和存储器对)所组成。2.特点：一个BSP程序有n个进程，每个驻留在一个结点上。基本时间单位是周期(或时间步)。程序按严格的超步序列执行。特点：同步路障迫使进程等待BSP计算机是MIMD系统BSP模型是超步级的松同步在一个超步中，不同进程以不同速率异步执行。BSP模型交互机制是共享变量或是消息传递。3.h关系的定义:一个h关系是任何通信操作的抽象，在其中，每个结点最多发出h个字到各结点，并且每个结点最多接收h个字。在一个BSP计算机中，实现任何h关系的时间不会超过gh个周期。g是由机器平台决定的一个常数。

4.一个超步执行时间的确定计算时间w处理器中完成计算操作所需的最大周期数。同步开销为L。通信开销为gh周期g是实现h关系的比例系数，常数。结论：执行一个超步的时间为w+gh+L5.例题：在一个有n个处理器的EREWPRAM计算机上，对两个N维向量A和B求内积s，可指派每个处理器完成2N／n个加法和乘法（2N／n+logn）；改用BSP机器模型实现一个并行执行上述内积求解。在一个有8个处理器的BSP计算机上，用4个超步完成问题求解：超步１：每个处理器在w=2N／8周期内计算，求出局部和。通信1次：处理器0，2，4，6将其局部和→处理器1，3，5，7。路障同步。超步２：计算１、３、５、７各自完成一次加法；通讯1次：处理器１，５中间结果送处理器３和７。路障同步超步３：计算：处理器３和处理器７，各完成一次加；通讯：处理器３→处理器７，完成一次通讯路障同步。超步4计算：处理器7完成一次加法(w＝１）产生最后和。不再需要任何通信或同步。总执行时间：2N／8+3g+3Ｌ+3个周期总之：点积在一个有n个处理器的BSP计算机上，执行时间为：2N／n+logｎ(g+L+1)个周期。与PRAM计算机的2N／n+logn时间相比:多了两项glogn和Llogn

关于BSP模型的实际优点和评论：比起PRAM模型来，BSP模型更为现实除了用于进程管理的并行性开销外，它考虑了所有其他开销。五.VLSI复杂性模型基本概念VLSI复杂性模型

背景：以ClarkThompson(1980)的研究工作为基础的二维VLSI芯片的AT2模型。AT2模型：

设A是用VLSI电路芯片完成给定运算的芯片面积，T为执行时间，又设s为运算问题的规模。Thompson在其博士论文中曾指出：对某些运算存在一个下界f(s)，有AT2≥O(

f(s))1、芯片面积A的存储界限许多计算在需要处理大型数据集时常受到存储器的限制。计算对存储量的需求常常决定了芯片面积A的下限。2、AT体积的I/O界限可以用乘积AT来表示I／O的下限。3、等分通信界限A1/2Ｔ

等分面积A1/2Ｔ，限定通信的下限。4、例题：矩阵相乘算法的VLSI芯片的实现(VictorPrasanna，1992)

要求：在一个每行和每列处理单元(PE)都有广播总线的网格系统上做n×n矩阵乘法C＝A×B如何计算芯片面积A和计算时间T？分析：二维网格结构如下图所示。PE间的通信通过广播总线实现。每个PE占据一单位面积：总芯片面积为O(n2)。广播总线需要O(n2)