并行计算大学课件1

第二章并行计算机及并行计算的性能评价并行计算机Flynn分类法并行计算机类型MPMD和SPMD并行程序结构并行计算的性能评价并行计算相关的基本概念加速比定律一、并行计算机Flynn分类法并行计算机类型MPMD和SPMD并行程序结构Flynn分类法Flynn(1966年)分类法是根据系统的指令流(instructionstreams)和数据流(datastreams)对计算机系统进行分类的一种方法。计算机在单个时间点上能够处理的指令流的数量计算机在单个时间点上能够处理的数据流的数量多指令流单数据流MISD多指令流多数据流MIMD单指令流单数据流SISD单指令流多数据流SIMD指令流数据流SISD：传统的单处理机系统。由程序生成的一个单指令流，在任意时刻处理单独的数据项。SIMD：如：阵列处理机系统(ProcessorArrays)。由一个控制器负责从存储器中取出指令并将这些指令发送给各个处理器，每个处理器同时执行相同的指令，但操作不同的数据。MISD：相当于在指令一级并行，而在被操作的数据级串行的情况，实际上这种模型是不能实现的。MIMD：当今绝大多数并行计算机都属于这一类。每个处理器拥有一个单独的程序（段），每个程序（段）为每一个处理器生成一个指令流，每条指令对不同的数据进行操作。Flynn分类法实际上并不能对所有计算机进行分类，如流水线向量处理机就难于按Flynn分类法简单地归为上述四类之一。一、并行计算机Flynn分类法并行计算机类型MPMD和SPMD并行程序结构1972年,诞生了第一台并行计算机ILLIACⅣ(IllinoisIntegratorandAutomaticComputer)

伊利诺斯(理工学院)积分仪和自动计算机由Illinois大学和Burrouphs公司合作研制成功的运算速度为1.5亿次/秒(150M次/秒)由64台处理器组成的阵列机(ArrayComputer)可对数组进行并行计算它是当时性能最高的CDC7600机器速度的2—6倍。并行计算机类型并行计算机类型1）并行向量处理机2）对称多处理机3）大规模并行处理机4）分布式共享存储多处理机系统5）机群系统并行向量处理机(ParallelVectorProcessorsPVP)1976年，出现了具有实用价值的向量处理机Cray-1单处理机模式，向量寄存器运算速度：3—160Mflops平均速度：20—80Mflops向量点积速度：22Mflops利用大量的向量寄存器快速地实现向量运算；1985年，CrayInc.推出Cray-2超级计算机，该机的向量处理速度是Cray-1的12倍(1Gflops)；80年代中、后期是PVP的时代，有很多PVP相继问世。PVP结构模型VPVPVP…交叉开关SMSMSM…VP:VectorProcessorSM:SharedMemory对称多处理机

(SymmetricMultiprocessorSMP)将各处理器经由高速总线（或交叉开关）网与共享存储器相连；每个处理器对共享存储器具有同等的访问权利；每个处理器对I/O设备和其它系统资源享有同等的访问权利；在SMP系统中一般要求每个处理机是相同的；因此称之为对称多处理机。对称多处理机结构模型P/C…总线或交叉开关I/OSMSM…P/CP/CP/C:Processor/CacheSM:SharedMemoryI/O:Input/Output典型SMP机型SGI公司的SGIOnyx系统和SGIPowerChallengeSequentConputerSystem,Inc.的SequentSymmetryS-81系统IBM公司的ES/9000系统和R50Sun公司的SparcCenter2000我国的曙光1号大规模并行处理机(MassivelyParallelProcessorsMPP)采用松耦合体系结构连接各种不同的处理器即各处理器以使用自己的局部内存为主，处理器之间进行同步通信实现数据交换大规模并行处理机结构模型LM1LM2LMnP/C1P/C2P/Cn……

专用互连网络P/C:Processor/CacheLM:LocalMemoryMPP的优点：突破了只看到一个统一的存储空间的方式具有良好的可扩展性MPP的缺点：分布存储要求用户必须将被操作的数据分配到各局部存储器中运算过程中用户要考虑数据在各节点间的传送和同步典型的MPP机型：Intel公司的ParagonXP/SMasPar公司的MP-2ThinkingMachine公司的CM-5IBM公司的SP2Cray公司的CrayT3D我国的曙光1000分布式共享存储多处理机系统(DistributedSharedMemoryDSM)DSM系统具有以下特点：存储器在物理上分布于各处理器附近，但在逻辑上可由多个处理器共享整个内存DSM系统实际上是SMP和MPP结构的折中DSM的优点：避免了集中式存储结构中处理器和存储器的复杂连接有良好的可扩展性相对MPP来说，更容易编程分布式共享存储多处理机系统LM1LM2LMnP/C1P/C2P/Cn……专用互连网络DSM的优点：避免了集中式存储结构中处理器和存储器的复杂连接有良好的可扩展性相对MPP来说，更容易编程DSM系统需着重考虑的问题：系统应具有维持存储器访问一致性的硬件支持相对SMP系统来说，其访问非物理局部存储器的时间要更长。典型的DSM机型：Cray公司的CrayT3ESGI/Cray公司的Origon2000BBN公司的TC2000机群系统（工作站机群）(ClusterOfWorkstationsCOW,NetworkedOfWorkstationsNOW)COW的结构特点：每一个节点机都是一个完整的工作站或PC机各节点机通过成本较低的商业网络连接起来各节点内都有本地磁盘一个完整的操作系统驻留在每个节点中工作站机群结构模型LM1LM2LMnP/C1P/C2P/Cn……通用互连网络LD1LD2LDn…P/C:Processor/CacheLM:LocalMemoryLD:LocalDiskCOW结构的优点：系统开发周期短，用户投资风险小系统价格低，节约系统资源系统的扩展性好，用户编程方便COW系统应考虑的主要问题：如何减少节点机间的通信开销如何改善并行程序设计环境如何充分利用全局资源并行向量处理机PVP对称多处理机SMP大规模并行处理机MPP分布式共享存储多处理机DSM工作站机群COW共享存储多处理机系统分布式共享存储器系统消息传递多计算机系统消息传递多计算机系统共享存储的多处理机（系统）MP与

分布存储的多计算机（系统）MC的比较性能多处理机(MP)多计算机(MC)存储器编址单地址多地址处理机间的数据传送共享变量消息传递数据传递的同步紧（同步）松（同步）或异步编程容易复杂可扩展性差好一、并行计算机Flynn分类法并行计算机类型MPMD和SPMD并行程序结构SIMD和MIMD计算机SIMD：由一个控制器负责从存储器中取出指令并将这些指令发送给各个处理器，每个处理器同步执行相同的指令，但操作不同的数据。数据阵列计算、图像处理MIMD：每个处理器拥有一个单独的程序，每个程序为每一个处理器生成一个指令流，每条指令对不同的数据进行操作。MPMD和SPMD并行程序结构进程：完成一定功能的一段程序的一次运行活动。在并行计算中，进程的并行执行方式：MPMD(MultiplePrograms&MultipleData)控制并行结构：在这种并行结构中各进程执行的程序不同，操作的数据也不同。各进程既可以是异步执行的，也可以以同步方式执行。SPMD(SingleProgram&MultipleData)数据域并行结构：在分布存储并行系统上执行的程序，每个进程执行相同的程序，但处理不同的数据。MPMD和SPMD并行程序结构在SPMD程序设计中，所有节点机得到相同的程序副本，但程序中可以含有条件语句来决定哪个节点机执行某段程序与否。SPMD和SIMD的区别SIMD计算机上执行的并行程序往往是由硬件来保障各处理器同步执行指令的过程，它是紧同步的。而SPMD结构的并行程序，既可以紧同步形式执行，同时也可以松散同步的形式执行。P1P2P3Pp……时间并行程序执行时间第二章并行计算机及并行计算的性能评价并行计算机Flynn分类法并行计算机类型MPMD和SPMD并行程序结构并行计算的性能评价并行计算相关的基本概念加速比定律二、并行计算的性能评价并行计算相关的基本概念加速比定律适用于固定计算负载的Amdahl定律适用于扩展问题的Gustsfson定律并行计算相关的基本概念并行计算(parallelcomputing)—在紧耦合并行机上的计算分布计算(distributedcomputing)—在松耦合（异地）并行机上的计算网格计算(gridcomputing)—属于分布计算范畴，利用互联网把分散在不同地理位置的性能较高的计算机组织成一个“虚拟的超级计算机”，来完成的计算。超强的数据处理能力；能够充分利用网络上的闲置处理能力（计算、存储）。并行计算相关的基本概念云计算(cloudcomputing)狭义云计算是指通过网络以按需、易扩展的方式获得所需的资源（硬件、平台、软件）。提供资源的网络被称为“云”。“云”中的资源在使用者看来是可以无限扩展的，并且可以随时获取，按需使用，随时扩展，按使用付费。这种特性经常被称为像水电一样使用IT基础设施。广义云计算是指通过网络以按需、易扩展的方式获得所需的服务。这种服务可以是IT和软件、互联网相关的，也可以是任意其他的服务。云计算是并行计算、分布式计算和网格计算的发展，或者说是这些计算机科学概念的商业实现。云计算的特点超大规模——“云”具有相当的规模，Google云计算已经拥有100多万台服务器，Amazon、IBM、微软、Yahoo等的“云”均拥有几十万台服务器。虚拟化——云计算支持用户在任意位置、使用各种终端获取应用服务。用户只需要一台笔记本或者一个手机，就可以通过网络服务来实现我们需要的一切，甚至包括超级计算这样的任务。高可靠性——“云”使用了数据多副本容错、计算节点同构可互换等措施来保障服务的高可靠性。通用性——云计算不针对特定的应用，在“云”的支撑下可以构造出千变万化的应用，同一个“云”可以同时支撑不同的应用运行。云计算的特点（续）高可扩展性——“云”的规模可以动态伸缩，满足应用和用户规模增长的需要。按需服务——“云”是一个庞大的资源池，你按需购买；云可以象自来水，电，煤气那样计费。极其廉价——由于“云”的特殊容错措施可以采用极其廉价的节点来构成云，“云”的自动化集中式管理使大量企业无需负担日益高昂的数据中心管理成本，“云”的通用性使资源的利用率较之传统系统大幅提升，因此用户可以充分享受“云”的低成本优势，经常只要花费几百美元、几天时间就能完成以前需要数万美元、数月时间才能完成的任务。微操作级并行化串行处理程序级并行化子程序级并行化语句级并行化操作级并行化粗粒度中粒度细粒度二、并行计算的性能评价并行处理(parallelProcessing)：在同一时间段内，在多个处理机中执行同一任务的不同部分。多道处理(multiprocessing)：强调由一台计算机利用一个处理机同时交错地执行多道程序。并发处理(concurrent)：与多道处理类似。并行计算相关的基本概念巨型(超级)计算机(supercomputer)：超级计算机是一个相对概念，不同的年代它的性能是不一样的。它是运算速度特别快，数据输入/输出能力特别强的大型计算机系统。1993年6月世界第一的计算机：59.7Gflops，

第500名：0.42Gflops2011年6月世界第一的计算机：8162Tflops，

第500名：40.19Tflops数据并行(dataparallelism)：利用多个处理器对一个数据集上的不同元素同时进行相同的操作。控制并行(controlparallelism)：为了完成一个任务要对不同的数据元素同时进行不同的操作。并行计算相关的基本概念并行计算机存储器访问模型分为两大类：共享存储型(sharedmemory)

在这种并行机中，每个处理器都可以经由互连网络对共用内存进行存取操作。系统对共享内存各模块进行统一编址。均匀存储访问模型UMA和非均匀存储访问模型NUMA非共享(分布)存储型(distributedmemory)

在这种并行机中，每个处理器拥有自己的局部内存。并行计算相关的基本概念（并行算法的）加速比

(speedup)或加速系数(speedupfactor)：完成计算的最佳串行算法所需的时间与完成相同任务的并行算法所需的时间之比。并行效率(parallelefficiency)：加速比与所用处理机个数之比。并行效率表示在并行机执行并行算法时，平均每个处理机的执行效率。并行计算相关的基本概念为了对一个并行任务评估，通常我们使用在单处理机上运行最快的已知算法的执行时间与并行任务的执行时间进行比较，即加速比。加速比S(p)=使用单处理器最佳串行算法执行时间在具有p台处理机的系统上算法的执行时间对于

p

个处理器来说，其最大加速比为p。当计算任务可被分成相等执行时间的进程时，一个进程映射到一个处理器上时，若此时没有其它开销就可获得最大加速比p。一般表示p：并行系统中处理器的个数(thenumberofprocessors)W：问题规模或工作负载(workload)Ws：应用问题中必须串行执行的部分Wp

：应用问题中可并行执行的部分

W=Ws+Wpf：串行执行部分

Ws占全部工作负载W的比例

f=Ws/W

一般表示ts

：整个任务在串行机上执行所需的时间tp

：整个任务在并行机上执行所需的时间Ts：完成Ws

所需要的时间Tp：在并行机上完成Wp

所需要的时间S：加速比：S(p)=ts/tp

E：并行效率：E=S(p)/p*100%加速比定律适用于固定计算负载的Amdahl定律适用于扩展问题的Gustsfson定律适用于固定计算负载的Amdahl定律当并行计算机中处理器数目增加时，固定负载就被分配给更多的处理器去并行执行，其主要目的是想尽可能快地的得出结果，即计算任务的实时性要求更高。Amdahl定律(1967)：设f为给定计算任务中必须串行执行的部分所占比例(0≤f≤1)，对于一台含有p

个处理器的并行计算机，其最大可能的加速比为：S=1f+(1-f)/p……ts(1-f)tsfts多处理机：：：p个处理机单处理机串行部分可并行化部分tp(1-f)ts/p……S=Ws+WpWs+Wp/p=fW

+(1-f)WfW

+((1-f)W)

/p=f+(1-f)f+(1-f)

/p=1f+(1-f)

/pS=tsf*ts+(1-f)ts/p=1f+(1-f)

/p在假设算法中每个计算步的执行时间是相等的情况下，算法的执行时间也常用计算步来计算。WpWpWpWpWpWpWpWpWsWsWsWsWsWsWsWs12345678处理机个数W工作负载

Ts

TsTs

Ts

Ts

Ts

Ts

TsTpTpTpTpTpTpTpTp12345678处理机个数T执行时间筛法求质数的例子问题----筛法求质数对给定的正整数N，求出2到N内所有的质数。23456789101112131415161718192021222324252627282930234567891011121314151617181920212223242526272829302923191713117532

最终结果2345678910111213141516171819202122232425262728293023456789101112131415161718192021222324252627282930筛法求质数的例子筛法求质数的顺序算法需要三个关键的数据结构：1、对应于自然数2，3，4，…,N

的布尔数组；2、目前找到的下一个质数；3、用于标记当前质数倍数的循环变量。筛法求质数串行算法fori:=2toNdoS[i]:=true;//初始化UpLimit:=sqrt(N);NextPrime:=2;whileNextPrime<=UpLimitdobeginfori:=NextPrimetoNdivNextPrimedoS[i*NextPrime]:=false;//筛掉当前质数的倍数

repeat//找下一个新质数

NextPrime:=NextPrime+1;untilS[NextPrime]end;考虑在带有I/O设备的共享存储型并行机上数据并行算法I/O设备当前质数234567N共享存储器P0

循环变量P1

循环变量Pp-1

循环变量…当N=106时，其串行算法要完成：1）对质数倍数标记的次数为2,122,0482）需要输出78,498个质数假设标记质数的倍数一次和输出一个质数的时间均为1个单位时间，则串行算法的执行时间为：2,122,048+78,498=2,200,546

f=78,498/2,200,546=0.0357在具有p个处理器的并行机上可能获得的最大加速比为:10.0357+0.9643

/p加速比161284148121620242832处理器个数1

4

812处理机个数时间计算时间I/O时间S=S(p)=1f+(1-f)

/p当p

无限增加时，加速比趋于1/f。从刚才的例子中看出：f=0.0357，那么可获得的最大加速比不会超过1/0.0357≈28，它与处理机的个数无关。即当处理机的个数超过一定数量后，加速比不会随着其增加而增加。Amdahl定律曾经给并行计算理论的研究带来了很大的负面影响。适用于扩展问题的Gustsfson定律Amdahl定律的一个主要缺点：固定负载妨碍了并行机性能可扩展性的开发。有些计算任务要求在给定的时间内希望提高计算精度，即在给定的时间内增加处理器的数量使计算量提高，如我们希望数值天气预报的数据采样模型的单位更小。在精度占主导位置的应用领域中，我们希望象在小机器上解小问题一样，在大机器上能解规模大的问题，并使二者所花费的时间大体相同。Gustafson定律(1988)：对于一台并行计算机，当问题中可并行部分扩大p

倍时，其加速比也随之增长：S’=p+(1-p)f=f+(1-f)p适用于扩展问题的Gustsfson定律=Ws+pWpWs+WpS’=Ws+pWpWs+pWp/p若我们用f

来表示，可将上式变为：S’=fW

+p(1-f)WfW

+p(1-f)W/p=f

+p(1-f)f

+(1-f)=f

+p(1-f)=p+(1-p)f12345678处理机个数W工作负载WsWsWsWsWsWsWsWsWpWpWpWpWpWpWpWpTpTpTpTpTpTpTpTpTsTsTsTsTsTsTsTs12345678处理机个数T执行时间例：设某应用问题在单节点机器上求解时需要执行的运算量为1107次浮点运算（工作负载）,其中有1105次浮点运算必须顺序执行。现考虑在一包含10个节点的多计算机系统求解该问题，同时将工作负载按以下两种情况进行调整：总运算量为1107次浮点运算，其中1105次浮点运算可由任一节点执行；可并行的部分按节点数扩大为9.9107次浮点运算，而必须顺序执行的1105次浮点运算可由任一节点执行。试计算a)和b)两种情况下获得的加速比。a)已知：p=10

，W=1107，

Ws=1105，可得：Wp=1107-1105=99105f=Ws/W=0.01总运算量为1107次浮点运算，其中1105次浮点运算可由任一结点执行；a)属于工作负载不变的情况，应使用Amdahl定律求其加速比：S(p)=1/(f+(1-f)/p)=1/(0.01+0.99/10)=9.17b)已知：

p=10

，原W=1107，

Ws

=1105，可得：

f=Ws/W=0.01现Wp=(1107-1105)

p=99105*10=

9.9107总运算量增加到9.9107+1105=9.91107次浮点运算，其中的1105次浮点运算可由任一结点执行。b)属于工作负载随处理机个数增加而增加的情况，应使用Gustsfson定律求其加速比：S'=(Ws+Wp*p)/(Ws+Wp)=f+(1-f)*p=0.01+0.99*10=9.91筛法求质数--并行算法控制并行算法数据域并行算法有共享存储器的数据并行算法没有共享存储器的数据并行算法带I/O操作的数据并行算法(已解释）1)控制并行算法当前质数234567N共享存储器互连网络P0

循环变量P1

循环变量Pp-1

循环变量…算法中每一个处理机重复做两件：找下一个质数从该质数的平方开始标记该质数的倍数各处理机直到遇到下一个质数>sqrt(N)为止。处理机P0从22开始标记2的倍数；处理机P1从32开始标记3的倍数；处理机P2从52开始标记5的倍数；……假设每一次标记质数的倍数

花费1个单位时间串行算法的执行时间ts：假设有k个≤Sqrt(N)

的质数:1,2,…,kts

=N-12+11N-22+12N-k2+1k++…+=N+1-121N+1-222N+1-k2k++…+=N-32N-83N+1-k2k++…+当N=1000时,其串行算法的时间为1411(单位时间)。控制并行算法的执行时间：假设有k个≤Sqrt(N)

的质数:1,2,…,k01002003004005006007008009001000110012001300140015002357111317--31177213115311321375加速比=1411/706≈2并行效率≈2/2≈1加速比=1411/499≈2.83并行效率≈2.83/3≈0.94控制并行算法的执行时间当处理器的个数为2时：加速比=1411/706≈2，并行效率=2/2=1当处理器的个数为3时：加速比=1411/499≈2.83并行效率=2.83/3=0.94当处理器的个数为4时：加速比=1411/499≈2.83并行效率=2.83/4=0.71这个并行算法的加速比的上限为2.83。并行效率随着处理器的个数（p>2）的增加而下降。2)数据并行算法数据并行算法可分为下列两种情况：基于共享存储并行机模型的并行算法基于分布存储并行机模型的并行算法共享存储型----数据并行算法当前质数234567N共享存储器互连网络P0

循环变量P1

循环变量Pp-1

循环变量…在共享存储器并行机上，算法思路如下:当一个处理器处于空闲时，它首先找下一个质数;所有的处理器同时对布尔数组进行相同的操作----筛掉当前质数的倍数，只是每个处理器负责布尔数组的一段。第k

个处理器对应的语句为：

fori:=k+NextPrimeto(NdivNextPrime)stepp

doS[i*NextPrime]:=false;

其中假设处理器的编号为0到p-1。在共享存储型并行机上筛法求质数算法的运行时间：假设系统有

p

个处理器，且N

是p的整倍数。tdp

=N-12+11*pN-22+12*pN-k2+1k*p++…+=N-32*pN-83*pN+1-k2k*p++…+当N=1000、p=8时，其并行算法的时间为：1411/8=177(单位时间)加速比S(p)=1411/177≈8数据域并行算法（分布存储）互连网络P1

当前质数循环变量

234N/pP2

当前质数循环变量

N/p+12N/pPp

当前质数循环变量

(p-1)N/p+1N我们可以做如下假设：布尔