1并行计算模型.ppt

并行处理及体系结构 实践部分 联系方式： 信息科学与工程学院计算机系 信息馆413 王璿 E-mail: wangxuan@ysu.edu.cn 研究方向：并行计算、生物计算 主要参考文献 1 陈国良等编著 《并行算法实践 》2004年 高等教育出版社 2. Bary Wilkinson著 陆鑫达译 《并行程序设计》 2002年 机械工业出版社 3.Calvin Lin等著，陆鑫达译 《并行程序设计原理》 2009年 机械工业出版社 4.Brian Goetz等著， 《Java并发编程实战》 2012 机械工业出版社 问题的并行求解过程 一个物理问题并行求解的最终目的是将该问题映射到并行机上，这一物理上的映射是通过不同层次上的抽象映射来实现的。 在并行机上求解问题，首先要写出求解问题的并行算法。并行算法是在并行计算模型上设计出来的，而并行计算模型是从不同的并行计算机体系结构模型中抽象出来的。然后，根据并行算法进行并行程序设计。 为了达到将问题的并行求解算法转化为特定的适合并行计算模型的并行算法的目的。需要解决两方面的问题：首先是问题的并行求解算法必须能够将问题内在的并行特征充分体现出来，否则并行求解算法将无法利用这些并行特征，从而使问题的高效并行求解成为不可能；其次是并行求解模型要和并行计算模型尽量吻合，这样，就为问题向并行机上的高效解决提供了前提。 回顾：共享存储的多处理机模型 PRAM模型特点 优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。 缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素 1.2 异步APRAM模型 基本概念 又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。 计算过程：由同步障分开的全局相组成 回顾：分布式存储多处理机模型 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的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。 1.5 分层模型 属于分布共享存储模型，包括均匀存储层次UMH模型和分布存储层次DRAM（h）模型及层次并行存储HPM模型等。 分层计算模型可将单一模型中的功能按要求分配到模型不同的层次中，缓解单一计算模型的精确性与可用性之间的矛盾。分层后，各层次模型职能不同，目标单一，各负其责，易于设计和实现。 ( 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 ( 5) For all Pi Where