《并行计算的设计基础》由会员分享，可在线阅读，更多相关《并行计算的设计基础（29页珍藏版）》请在金锄头文库上搜索。
1、并 行 计 算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2004年12月Date1现代密码学理论与实践之五第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程Date2现代密码学理论与实践之五第四章 并行算法的设计基础4.1 并行算法的基础知识4.2 并行计算模型Date3现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date4现代密码学理论与实践之五并行算法的定
2、义和分类 并行算法的定义 算法 并行算法：一些可同时执行的诸进程的集合，这些进 程互相作用和协调动作从而达到给定问题的求解。 并行算法的分类 数值计算和非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法Date5现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date6现代密码学理论与实践之五并行算法的表达 描述语言 可以使用类Algol、类Pascal等； 在描述语言中引入并行语句。 并行语句示例 Par-do语句for i=1 to n par-doend
3、 for for all语句for all Pi, where 0ikend for Date7现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date8现代密码学理论与实践之五并行算法的复杂性度量 串行算法的复杂性度量 最坏情况下的复杂度(Worst-CASE Complexity) 期望复杂度(Expected Complexity) 并行算法的几个复杂性度量指标 运行时间t(n):包含计算时间和通讯时间，分别用计算 时间步和选路时间步作单位。n为问题实例的输入规模
4、 。 处理器数p(n) 并行算法成本c(n): c(n)=t(n)p(n) 总运算量W(n): 并行算法求解问题时所完成的总的操 作步数。Date9现代密码学理论与实践之五并行算法的复杂性度量 Brent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间内执行完毕。 W(n)和c(n)密切相关 P=O(W(n)/T(n)时，W(n)和c(n)两者是渐进一致的 对于任意的p，c(n)W(n)Date10现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3
5、 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date11现代密码学理论与实践之五并行算法的同步 同步概念 同步是在时间上强使各执行进程在某一点必须互相等待； 可用软件、硬件和固件的办法来实现。 同步语句示例 算法4.1 共享存储多处理器上求和算法输入：A=(a0,an-1),处理器数p输出：S=aiBegin (1)S=0 (2.3) lock(S) (2)for all Pi where 0ip-1 do S=S+L(2.1) L=0 (2.4) unlock(S)(2.2) for j=i to n step p do end forL=L+aj Endend forend f
6、or Date12现代密码学理论与实践之五并行算法的通讯 通讯 共享存储多处理器使用：global read(X,Y)和global write(X,Y) 分布存储多计算机使用：send(X,i)和receive(Y,j) 通讯语句示例 算法4.2 分布存储多计算机上矩阵向量乘算法输入：处理器数p, A划分为B=A1n,(i-1)r+1ir, x划分为w=w(i-1)r+1;ir 输出：P1保存乘积AXBegin (1) Compute z=Bw(2) if i=1 then yi=0 else receive(y,left) endif(3) y=y+z(4) send(y,right)(5
7、) if i=1 then receive(y,left)End Date13现代密码学理论与实践之五第四章 并行算法的设计基础4.1 并行算法的基础知识4.2 并行计算模型Date14现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date15现代密码学理论与实践之五Date16现代密码学理论与实践之五PRAM模型 基本概念 由Fortune和Wyllie1978年提出，又称SIMD-SM模型 。有一个集中的共享存储器和一个指令控制器，通过 SM的R/W交换数据，隐式同步计算。 结构图Contro
8、l UnitInterconnection NetworkPLMPLMPLMPLMShared MemoryDate17现代密码学理论与实践之五PRAM模型 分类 PRAM-CRCW并发读并发写 CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据 PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入 APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入 PRAM-CREW并发读互斥写 PRAM-EREW互斥读互斥写 计算能力比较 PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模
9、拟 PRAM-CREW和PRAM-CRCW Date18现代密码学理论与实践之五PRAM模型 优点 适合并行算法表示和复杂性分析，易于使用，隐藏了 并行机的通讯、同步等细节。 缺点 不适合MIMD并行机，忽略了SM的竞争、通讯延迟 等因素Date19现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date20现代密码学理论与实践之五异步APRAM模型 基本概念 又称分相（Phase）PRAM或MIMD-SM。每个处理 器有其局部存储器、局部时钟、局部程序；无全局时 钟，各处理器异步执行；处理器通过S
10、M进行通讯； 处理器间依赖关系，需在并行程序中显式地加入同步 路障。 指令类型(1)全局读 (2)全局写 (3)局部操作 (4)同步 Date21现代密码学理论与实践之五异步APRAM模型 计算过程 由同步障分开的全局相组成 Date22现代密码学理论与实践之五异步APRAM模型 计算时间设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数 目的增加而增加；同步路障时间为B=B(p)非降函数。满足关系 ； 或令 为全局相内各处理器执行时间最长者，则APRAM上的计算时 间为 优缺点易编程和分析算法的复杂度，算法的正确性容易保证;但与现实相 差较远，其上并行算法非常有限，也不适合MIMD
11、-DM模型。Date23现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date24现代密码学理论与实践之五BSP模型 基本概念 由Valiant(1990)提出的，“块”同步模型，是一种异步 MIMD-DM模型，支持消息传递系统，块内异步并行 ，块间显式同步。 模型参数 p：处理器数(带有存储器) l：同步障时间(Barrier synchronization time) g：带宽因子(time steps/packet)=1/bandwidth Date25现代密码学理论与实践之五BSP模型 计
12、算过程 由若干超级步组成， 每个超级步计算模式为左图 优缺点强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。Date26现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date27现代密码学理论与实践之五logP模型 基本概念 由Culler(1993)年提出的，是一种分布存储的、点到 点通讯的多处理机模型，其中通讯由一组参数描述， 实行隐式同步。 模型参数 L：network latency o：communication overhe
13、ad g：gap=1/bandwidth P：#processors 注：L和g反映了通讯网络的容量 Date28现代密码学理论与实践之五logP模型 优缺点捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议 ，可以应用到共享存储、消息传递、数据并行的编程模型中；但难 以进行算法描述、设计和分析。 BSP vs. LogP BSPLogP：BSP块同步BSP子集同步BSP进程对同步 LogP BSP可以常数因子模拟LogP，LogP可以对数因子模拟BSP BSPLogP+BarriersOverhead BSP提供了更方便的程设环境，LogP更好地利用了机器资源 BSP似乎更简单、方便和符合结构化编程 Date29现代密码学理论与实践之五
