( 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 N/P个粒子之间的受力 （5 ）处理本处理机 因此，P0号处理器读取共享存储器的顺序为s1,s2,s3 同理，P1号读取顺序为s2,s3,s0；P2号读取顺序为s3,s0,s1； P3号读取顺序为s0,s1,s2
P个处理器各自负责计算N/P个粒子的受 力以及对这些粒子的状态进行更新。因 为SM因此不考虑通讯。 假设：N=16 P=4

1~N/P 1~4 P0 N/P
2N/P+1~3N/P 3N/P+1~4N/P N/P+1~2N/P 5~8 9~12 13~16 P1 P2 P3 N/P 1~16 1~N N/P N/P
BSPLogP：BSP块同步BSP子集同步 BSP进程对同步＝LogP

LogP模型上设计的算法和BSP模型上相似，只是 算法不再有超级步的概念。所有的进程异步地执 行，通过消息传递显示地同步，处理器接收到消 息后可以立即在后面计算中使用，充分利用了处 理器的计算资源. 优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络 拓扑、路由、协议，可以应用到共享存储、消息 传递、数据并行的编程模型中；但难以进行算法 描述、设计和分析。
算法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 //k 共享存储器中的N个粒子 Endfor Endfor 原来串行算法的计算量平 Endfor 均分配给P个处理器。因此
Barrier; /* 实施路障同步*/ Endfor Endfor

第（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
并行处理及体系结构
实践部分

联系方式： 信息科学与工程学院计算机系 信息馆413 王璿 E-mail: wangxuan@ 研究方向：并行计算、生物计算

主要参考文献




1 陈国良等编著 《并行算法实践 》2004年 高等教育出版社 2. Bary Wilkinson著 陆鑫达译 《并行程序 设计》 2002年 机械工业出版社 3.Calvin Lin等著，陆鑫达译 《并行程序设 计原理》 2009年 机械工业出版社 4.Brian Goetz等著， 《Java并发编程实战》 2012 机械工业出版社

为了达到将问题的并行求解算法转化为特 定的适合并行计算模型的并行算法的目的。 需要解决两方面的问题：首先是问题的并 行求解算法必须能够将问题内在的并行特 征充分体现出来，否则并行求解算法将无 法利用这些并行特征，从而使问题的高效 并行求解成为不可能；其次是并行求解模 型要和并行计算模型尽量吻合，这样，就 为问题向并行机上的高效解决提供了前提。
根据牛顿定律, 用( 5) 中计算出的粒子j 受到的力, 更新粒子j的状态信息

Endfor Endfor
第（5）步处理本处理机N/P个粒子之间的受力。 其中计算某个粒子N-1个受力时，有N/P个从本地 存储单元中读取。
根据第4和5步，每个处理器的计算时间仍为O(N2/P)。 但第4步中，每个处理器异步读写全局存储器，令全局 读写开销为d。计算某个粒子N-1个受力时，有(P1)×N/P个要从共享单元中读取，则需要时间为d× (P1)×N/P。 因此算法复杂度为 O(N2/P)+d ×N
1.2 异步APRAM模型

基本概念

又称分相（Phase）PRAM或MIMD-SM。每 个处理器有其局部存储器、局部时钟、局部 程序；无全局时钟，各处理器异步执行；处 理器通过SM进行通讯；处理器间依赖关系， 需在并行程序中显式地加入同步路障。
计算过程：由同步障分开的全局相组成

计算时间 设局部操作为单位时间；全局读/写平均时间为d， d随着处理器数目的增加而增加； 同步路障时间为B=B(p)非降函数。 满足关系 令 t ph为全局相内各处理器执行时间最长者，则 APRAM上的计算时间为


（1）L(Latency) 表示源节点与接收节点进行消 息传递所需要的等待或延迟时间的上限。 （2）o(overhead) 处理器发送或接收一个消息所 需的处理时间开销。 （3）g(gap) 表示一台处理机连续两次发送或接 收消息时的最小时间间隔，其倒数即每个处理器 的有效通信带宽。 （4）P(Processor) 处理机/存储器模块个数
1 并行计算模型

什么是并行计算模型？ 并行计算模型是并行计算机基本特征的抽象。 并行计算模型从并行计算机中抽取若干个能够反映 计算特征的可以计算或者可以测量的参数，按照模 型所定义的计算行为构造成本函数，从而进行算法 的性能分析，是算法设计和分析的基础。
用户 —编程模型 —计算模型 —体系结构模型 系统
实例：四种并行计算模型上N体问题求解算法

N体问题及其串行算法 N 体问题可以描述如下: 在 一定的物理空间中, 分布有 N个粒子, 每对粒子间都存 在相互作用力( 如万有引 力、库仑力等) 。它们从 一个初始的状态开始, 每隔 一定的时间步, 由于粒子间 的相互作用, 粒子的状态会 有一个增量, 需要对粒子的 加速度、速度、位置信息 进行更新。下面给出N 体 问题的串行算法。
T t ph B 同步障次数
优缺点： 易编程和分析算法的复杂度，但与现实相差较远，其 上并行算法非常有限，也不适合MIMD-DM模型。
回顾：分布式存储多处理机模型
1.3 BSP模型

基本概念

由Valiant(1990)提出的，其含义为“块”同步模型， 是一种异步MIMD-DM模型，支持消息传递系统。 块内异步并行，块间显示同步。
问题的并行求解过程

一个物理问题 并行求解的最 终目的是将该 问题映射到并 行机上，这一 物理上的映射 是通过不同层 次上的抽象映 射来实现的。

在并行机上求解问题，首先要写出求解问 题的并行算法。并行算法是在并行计算模 型上设计出来的，而并行计算模型是从不 同的并行计算机体系结构模型中抽象出来 的。然后，根据并行算法进行并行程序设 计。
结构图
回顾：共享存储的多处理机模型
PRAM模型特点
优点：适合并行算法表示和复杂性分析，易于 使用，隐藏了并行机的通讯、同步等细节。 缺点：不适合MIMD并行机，忽略了SM的竞争、 通讯延迟等因素
PRAM 模型是同步的，因此，所有的指令都按照锁步的方式 模型中使用了一个全局共享存储器，且局存容量较小， PRAM模型假设了每个处理器可在单位时间访问 操作，用户虽然感觉不到同步的存在， 不足以描述分布主存多处理机的性能瓶颈， 共享存储器的任一单元，因此要求处理机间通信无延迟、 但同步的存在的确很耗费时间， 而且共享单一存储器的假定， 无限带宽和无开销，略去了实际存在 而且不能反映现实中很多系统的异步性 显然不适合于分布存储结构的 MIMD机器 比如资源竞争和有限带宽，这是不现实的
—机器模型
1.1 PRAM模型
（ Parallel Random Access Machine ）

又称为SIMD-SM模型（共享存储的SIMD）。由Fortune和 Wyllie1978年提出。有一个集中的共享存储器和一个指令 控制器，通过SM的R/W交换数据，隐式同步计算。在 PRAM中有一个同步时钟，所有操作都是同步进行的。
1.4 LogP模型

基本概念 由Culler(1993)年提出的，是一种分布存储的、点到点通 讯的多处理机模型，其中通讯由一组参数描述，实行隐 式同步。 模型参y o：communication overhead g：gap=1/bandwidth P：#processors 注：L和g反映了通讯网络的容量

模型参数
● p: 处理器数(带有存储器） ● g: 路由器吞吐率（也称为带宽因子 1/bandwidth） 处理器模块之间点对点传递消息的路由器； ● L: 同步障时间 全局同步之间的时间间隔；


计算过程 由若干超级 步组成，每个超 级步计算模式为 右图 优缺点 强调了计算和通 讯的分离，提供 了一个编程环境， 易于程序复杂性 分析。但需要显 式同步机制，限 制至多h条 消息 的传递等。
//粒子j 各处理器中的N/P个粒子
算法复杂度为O(N2/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


For l=1 to N/P Do //l 共享单元中其他处理器中的N/P个粒子 u=[( i+k)%P]×(N/P) +1; 计算Pi 中粒子j 和共享单元中粒子k 之间的作用力, 并且累加; //u 防止多个处理器同时读取同一个共享单元，每 Endfor 个处理器对共享单元中读取顺序不同。 Endfor