单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,并行处理及体系结构,实践部分,,联系方式：,,信息科学与工程学院计算机系,,信息馆413 王璿,,,E-mail:,,研究方向：并行计算、生物计算,,主要参考文献,1 陈国良等编著 《并行算法实践 》2004年 高等教育出版社,,2. Bary Wilkinson著 陆鑫达译 《并行程序设计》 2002年 机械工业出版社,,3.Calvin Lin等著，陆鑫达译 《并行程序设计原理》 2009年 机械工业出版社,,4.Brian Goetz等著， 《Java并发编程实战》 2012 机械工业出版社,,问题的并行求解过程,一个物理问题并行求解的最终目的是将该问题映射到并行机上，这一物理上的映射是通过不同层次上的抽象映射来实现的在并行机上求解问题，首先要写出求解问题的并行算法并行算法是在并行计算模型上设计出来的，而并行计算模型是从不同的并行计算机体系结构模型中抽象出来的然后，根据并行算法进行并行程序设计为了达到将问题的并行求解算法转化为特定的适合并行计算模型的并行算法的目的需要解决两方面的问题：,首先是问题的并行求解算法必须能够将问题内在的并行特征充分体现出来,，,否则并行求解算法将无法利用这些并行特征，从而使问题的高效并行求解成为不可能；,其次是并行求解模型要和并行计算模型尽量吻合，,这样，就为问题向并行机上的高效解决提供了前提。
1 并行计算模型,什么是并行计算模型？,,并行计算模型是并行计算机,基本特征的抽象,并行计算模型从并行计算机中,抽取,若干个能够反映计算特征的可以计算或者可以测量的,参数,，按照,模型所定义的计算行为,构造成本函数，从而进行算法的性能分析，是算法设计和分析的基础编程模型,,计算模型,,体系结构模型,,机器模型,用户,系统,,,1.1 PRAM模型,,（,Parallel Random Access Machine,）,又称为SIMD-SM模型（共享存储的SIMD）由Fortune和Wyllie1978年提出,有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算在PRAM中有一个,同步时钟,，所有操作都是同步进行的结构图,,回顾：共享存储的多处理机模型,,,PRAM模型特点,优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素,模型中使用了一个全局共享存储器，且局存容量较小，,,不足以描述分布主存多处理机的性能瓶颈，,,而且共享单一存储器的假定，,,显然不适合于分布存储结构的MIMD机器,PRAM模型是同步的，因此，,所有的指令都按照锁步的方式,,操作,，用户虽然感觉不到同步的存在，,,但同步的存在的确很耗费时间,，,,而且不能反映现实中很多系统的异步性,PRAM模型假设了每个处理器可在单位时间访问,,共享存储器的任一单元，因此要求处理机间通信无延迟、,,无限带宽和无开销，略去了实际存在,,比如资源竞争和有限带宽，这是不现实的,,1.2 异步APRAM模型,基本概念,,又称分相（Phase）PRAM或MIMD-SM。
每个处理器有其局部存储器、局部时钟、局部程序,；,无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障,计算过程：由同步障分开的全局相组成,,,计算时间,,设局部操作为单位时间；全局读/写平均时间为d，,,d随着处理器数目的增加而增加；,,同步路障时间为B=B(p)非降函数满足关系,,令 为全局相内各处理器执行时间最长者，则APRAM上的计算时间为,,,,,优缺点：,,易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型回顾：分布式存储多处理机模型,,,1.3 BSP模型,基本概念,,由Valiant(1990)提出的，其含义为“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统块内异步并行，块间显示同步模型参数,,● p: 处理器数(带有存储器）,,● g: 路由器吞吐率,（也称为带宽因子 1/bandwidth） 处理器模块之间点对点传递消息的路由器；,,● L: 同步障时间,全局同步之间的时间间隔,；,,计算过程,,由若干超级步组成，每个超级步计算模式为右图,,优缺点,,强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。
但需要显式同步机制，限制至多h条 消息的传递等1.4 LogP模型,基本概念,,由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步模型参数,,L：network latency,,o：communication overhead,,g：gap=1/bandwidth,,P：#processors,,注：L和g反映了通讯网络的容量,,（1）L(Latency),表示源节点与接收节点进行消息传递所需要的等待或延迟时间的上限2）o(overhead),处理器发送或接收一个消息所需的处理时间开销3）g(gap),表示一台处理机连续两次发送或接收消息时的最小时间间隔，其倒数即每个处理器的有效通信带宽4）P(Processor),处理机/存储器模块个数,,LogP模型上设计的算法和BSP模型上相似，只是算法不再有超级步的概念所有的进程异步地执行，通过消息传递显示地同步，处理器接收到消息后可以立即在后面计算中使用，充分利用了处理器的计算资源.,,,优缺点,,捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。
BSP,,LogP,：,BSP,块同步,,BSP,子集同步,,,BSP,进程对同步＝,LogP,,回顾：分布式共享存储多处理机模型,,1.5 分层模型,属于分布共享存储模型，包括均匀存储层次UMH模型和分布存储层次DRAM（h）模型及层次并行存储HPM模型等分层计算模型可将单一模型中的功能按要求分配到模型不同的层次中，缓解单一计算模型的精确性与可用性之间的矛盾分层后，各层次模型职能不同，目标单一，各负其责，易于设计和实现实例：四种并行计算模型上N体问题求解算法,N体问题及其串行算法,,N 体问题可以描述如下: 在一定的物理空间中, 分布有N个粒子, 每对粒子间都存在相互作用力( 如万有引力、库仑力等) 它们从一个初始的状态开始, 每隔一定的时间步, 由于粒子间的相互作用, 粒子的状态会有一个增量, 需要对粒子的加速度、速度、位置信息进行更新下面给出N 体问题的串行算法r,,算法1.1 N 体问题求解的串行算法,输入: 空间中N 个粒子的状态信息, 包括初始速度、位置等信息输出: 给出经过一个时间步后所有N 个粒子的新的状态信息Begin,,( 1) 读入N 个粒子的初始信息,,( 2) For,i=1 to N,,For,j=1 to N,,If,i≠j,Then,,计算粒子j 对粒子i 的作用力, 并且累加;,,Endif,,Endfor,,Endfor,,( 3) For i=1 to N,,根据牛顿定律, 用( 2) 中计算出的粒子i 受到的力更新粒子i 的状态信息,,Endfor,N个天体，每个天体计算N-1次受力，因此需要计算N×(N-1)次受力。
因此算法复杂度为O(N,2,),,算法1.2 PRAM模型上N 体问题求解并行算法,Begin,,( 1) 每个处理器读入N/P 个粒子的初始信息,,( 2),For all Pi Where i∈[0, P- 1] Par- Do,,For j=i×N/P+1 to ( i+1) ×N/P Do,,,For k=1 to N Do,,If j≠k Then,,计算粒子k 对粒子j 的作用力, 并且累加;,,Endif,,Endfor,,Endfor,,Endfor,//粒子j 各处理器中的N/P个粒子,//k 共享存储器中的N个粒子,,原来串行算法的计算量平均分配给P个处理器因此算法复杂度为O(N,2,/P),,( 3) For all Pi Where i∈[0, P- 1] Par- Do,,For j=i×N/P+1 to ( i+1) ×N/P Do,,根据牛顿定律, 用( 2) 中计算出的粒子j 受到的力更新粒子j 的状态信息,,Endfor,,Endfor,,,P个处理器各自负责计算N/P个粒子的受力以及对这些粒子的状态进行更新因为SM因此不考虑通讯假设：N=16 P=4,SM,N/P,P,0,N/P,P,1,N/P,P,2,N/P,P,3,1~4,5~8,9~12,13~16,1~16,1~N/P,N/P+1~2N/P,2N/P+1~3N/P,3N/P+1~4N/P,1~N,,算法1.3 APRAM模型上N 体问题求解的并行算法,Begin,,( 1) 每个处理器处理N/P 个粒子, 读入N/P 个粒子的初始状态信息;,,( 2),每个处理器将其上N/P 个粒子写入到共享单元SM中;,,( 3)Barrier; /* 实施路障同步*/,,( 4) For all Pi Where i∈[0, P- 1] Par- Do,,,For j=1 to N/P Do,,,For k=1 to P- 1 Do,,,For l=1 to N/P Do,,,u=[( i+k)%P]×(N/P) +1;,,计算Pi 中粒子j 和共享单元中粒子k 之间的作用力, 并且累加;,,Endfor,,Endfor,,Barrier; /* 实施路障同步*/,,Endfor,,Endfor,,//粒子j 各处理器自己的N/P个粒子,//k 除自己之外的其他P-1个处理器,//l 共享单元中其他处理器中的N/P个粒子,//u 防止多个处理器同时读取同一个共享单元，每个处理器对共享单元中读取顺序不同。
第（4）步处理本处理机与共享单元中粒子之间的受力其中计算某个粒子N-1个受力时，有(P-1)×N/P个要从共享单元中读取 5),For all Pi Where i∈[0, P- 1] Par- Do,,计算Pi 中N/P 个粒子间的作用力, 并且累加;,,Endfor,,( 6) For all Pi Where i∈[0, P- 1] Par- Do,,For j=1 to N/P,,,根据牛顿定律, 用( 5) 中计算出的粒子j 受到的力, 更新粒子j的状态信息,,Endfor,,Endfor,第（5）步处理本处理机N/P个粒子之间的受力其中计算某个粒子N-1个受力时，有N/P个从本地存储单元中读取根据第4和5步，每个处理器的计算时间仍为O(N,2,/P)但第4步中，每个处理器异步读写全局存储器，令全局读写开销为d计算某个粒子N-1个受力时，有(P-1)×N/P个要从共享单元中读取，则需要时间为d× (P-1)×N/P因此算法复杂度为 O(N,2,/P)+d ×N,,SM,LM,,1~N/P,LM,,N/P+1~2N/P,P,0,P,1,P,2,P,3,1~N/P,,s,0,N/P+1~2N/P,,s,1,2N/P+1~3N/P,,s,2,3N/P+1~4N/P,,s,3,LM,,2N/P+1~3N/P,LM,,3N/P+1~4N/P,(2),( 4)计算Pi 中粒子j 和共享单元中粒子k 之间的作用力, 并且累加;,,,这里 u=[( i+k)%P]×(N/P) +1;,,i=0 k=1 u=[(0+1)%4]×N/P+1=N/p+1,,k=2 u= [(0+2)%4]×N/P+1=2N/p+1,,k=3 u= [(0+3)%4]×N/P+1=3N/p+1,,因此，P,0,号处理器读取共享存储器的顺序为s1,s2,s3,,同理，P,1,号读取顺序为s2,s3,s0；P,2,号读取顺序为s3,s0,s1；,,P,3,号读取顺序为s0,s1,s2,（4）,（5）处理本处理机N/P个粒子之间的受力,（5）,,算法1.4 BSP模型上N 体问题并行算法,Begin,,( 1) 每个处理器处理N/P 个粒子, 读入N/P 个粒子的初始状态信息;,,( 2) For all Pi Where i∈[0, P- 1] Par- Do,,计算Pi 内部粒子间的作用力;,,,Pi 把其内N/P 个粒子的状态信息发送给其右邻居;,,Endfor,,( 3),Barrier,;,,内部N/P个粒子受力计算(N/P),×,(N/P-1) ，然后将本地N/P个粒子的状态信息发送,通讯时间为 （N/P）,×g。
则第一个超级步内包含计算时间和发送时间然后进入之后的P-1个超级步 4),For all Pi Where i∈[0, P- 1] Par- Do,,,For j=0 to P- 2 Do,,,Pi 接收其左邻居发送过来的粒子信息,;,,Pi 计算其内粒子和收到的粒子间的作用力, 并且累加;,,,Pi 把其接收到粒子的状态信息发送给其右邻居,;,,,Barrier;,,Endfor,,Endfor,,每个超级步内包括计算时间，通信时间和同步时间整个计算需要超级步为O(P)因此算法执行时间为：,,,O(,P,×((N/P),2,+ 2 × N/P ×g +B))=,,O(N,2,/P+2 × N×g+B ×P),通信时间N/P ×g,通信时间N/P ×g,计算时间,,N/P × N/P,同步时间,,B,,( 5) For all Pi Where i∈[0, P- 1] Par- Do,,For j=1 to N/P,,根据牛顿定律, 用( 5) 中计算出的粒子j 受到的力, 更新粒子j 的状态信息;,,Endfor,,Endfor,,,,,算法1.5 LogP模型上N 体问题并行算法,Begin,,( 1) 每个处理器处理N/P 个粒子, 读入N/P 个粒子的初始状态信息;,,( 2) For all Pi Where i∈[0, P- 1],,计算Pi 内部粒子间的作用力;,,Pi 把其内N/P 个粒子的状态信息发送给其右邻居;,,,( 3) For all Pi Where i∈[0, P- 1] Par- Do,,For j=0 to P- 2 Do,,Pi 接收其左邻居发送过来的粒子信息;,,Pi 把其接收到粒子的状态信息发送给其右邻居;,,Pi 计算其内粒子和收到的粒子间的作用力;,,Endfor,,Endfor,进程异步执行,,( 4) For all Pi Where i∈[0, P- 1] Do,,For j=1 to N/P,,根据牛顿定律, 用( 3) 中计算出的粒子j 受到的力, 更新粒子j 的状态信息;,,Endfor,,Endfor,,,所有计算平均分配到P个处理器上执行，因此计算时间为,O(N,2,/P)。
每个处理器需要进行P-1次消息传递，每次传递N/P个粒子信息处理器传递大小为N/P的信息包的开销为2,×,o+L+ (N/P),×g因为,每个处理器,需要与其他P-1个处理器进行通信，,通信开销为(P-1) ×(,2,×,o+L+ (N/P),×g)这样P个处理器,总的通信开销为,P,×((P-1) ×(,2,×,o+L+ (N/P),×g)),因此，算法总体执行时间为：,,O(,N,2,/P+ P,×((P-1) ×(,2,×,o+L+ (N/P),×g))),,,课后练习：,,1. 通过N体问题在四个不同并行计算模型上算法设计，了解四种模型的特点课后阅读：,,苗乾坤等.若干并行计算模型上的N体问题求解算法.计算机工程与应用.2007,43(10):52-55,,,。