[互联网]第3章分布式系统中的并行计算.ppt
《[互联网]第3章分布式系统中的并行计算.ppt》由会员分享,可在线阅读,更多相关《[互联网]第3章分布式系统中的并行计算.ppt(36页珍藏版)》请在三一办公上搜索。
1、第三章 分布式计算环境下的并行计算,本章主要内容,数据相关性和可并行化并行算法的定义与分类并行计算模型并行算法性能分析并行算法的语言结构并行算法应用举例,相关性与可并行化,伯恩斯坦准则I1O2,即P1的输入变量集与P2的输出变量集不相交;I2O1,即P2的输入变量集与P1的输出变量集不相交;O1O2,即P1和P2的输出变量集不相交可并行处理,数据相关,P1:AB+CP2:DAB其中,变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性,变量A必须是先在P1中写入后方可从P2中读出,即必须先写后读。显然,P1和P2不能并行执行。,数据反相关,P1:ABCP2:CE+DP1通过变
2、量C数据相关于P2。为保证语义正确性,必须等P1将变量C读出后,P2方可向变量C进行写入操作,即必须先读后写。也不可并行化,数据输出相关,P1:AB+CP2:ADE为保证语义正确性,必须保证P1先写入A,然后允许P2再写入A。P1和P2不可并行执行,并行算法的定义与分类,算法是解题的精确描述并行算法是一些可同时执行的诸进程的集合,这些进程互相作用和协调从而达到给定问题的求解。并行算法就是对并行计算过程的精确描述并行算法可以从不同的角度分类为数值计算并行算法和非数值计算并行算法同步并行算法和异步并行算法共享存储并行算法和分布存储并行算法,数值算法与非数值算法,数值计算是指基于代数关系运算的计算问
3、题如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法(Numerical Algorithm)。科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。非数值计算是指基于比较关系运算的计算问题诸如排序、选择、搜索、匹配等符号处理,相应的算法也称为非数值算法(Non-numerical Algorithm)。非数值计算在符号类信息处理中获得广泛应用,如数据库领域的计算问题、海量数据挖掘等,近年来广泛关注的生物信息学主要也是非数值计算,并行算法的表达,描述语言 可以使用类Algol、类Pascal等在描述语言中引入并行语句。并行语句示例Par-do语
4、句for i=1 to n par-doend forfor all语句for all Pi,where 0ikend for,并行算法的复杂性度量,串行算法的复杂性度量最坏情况下的复杂度期望复杂度并行算法的复杂性度量指标运行时间t(n):包含计算时间和通信时间处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量w(n):并行算法求解问题时所完成的总的操作步数。,并行计算模型,计算模型是对计算机的抽象计算模型为设计、分析和评价算法提供基础冯.偌依曼机就是一个理想的串行计算模型但现在还没有一个通用的并行计算模型,常见的并行计算模型,PRAM模型:由Fortune和Wyllie
5、1978年提出,又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器,通过SM的R/W交换数据。异步模型(APRAM):又称分相(Phase)PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序。BSP模型:块同步模型,是一种异步MIMD-DM模型,支持消息传递系统,块内异步并行,块间显式同步。logP模型:由Culler(1993)年提出,是一种分布存储的、点到点通讯的多处理机模型。,PRAM模型,PRAM(Parallel Random Access Machine)模型,即并行随机存取模型,是一种抽象的并行计算模型。假设存在着一个容量无限大的共享存储器;每台处
6、理器有简单的算术运算和逻辑判断功能;在任何时刻各处理器均可以通过共享存储单元交换数据。,PRAM模型,C:Concurrent(允许并发操作)E:Exclusive(排斥并发操作)PRAM模型又可以细分为PRAM-EREW模型:在同一时刻只允许一个处理器对同一存储单元进行读/写,但不允许多个存储器对同一存储单元同时读/写。PRAM-CREW模型:在同一时刻允许多个处理器对同一存储单元并发读但不允许并发写。PRAM-ERCW模型:在同一时刻允许多个处理器对同一存储单元并发写但不允许并发读。PRAM-CRCW模型:在同一时刻允许多个处理器对同一存储单元并发读和并发写。,PRAM模型,SIMD-PR
![[互联网]第3章分布式系统中的并行计算.ppt_第1页](https://www.31ppt.com/fileroot1/2023-4/28/80890967-879a-4566-be40-b8e78a34d291/80890967-879a-4566-be40-b8e78a34d2911.gif)
![[互联网]第3章分布式系统中的并行计算.ppt_第2页](https://www.31ppt.com/fileroot1/2023-4/28/80890967-879a-4566-be40-b8e78a34d291/80890967-879a-4566-be40-b8e78a34d2912.gif)
![[互联网]第3章分布式系统中的并行计算.ppt_第3页](https://www.31ppt.com/fileroot1/2023-4/28/80890967-879a-4566-be40-b8e78a34d291/80890967-879a-4566-be40-b8e78a34d2913.gif)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 互联网 分布式 系统 中的 并行 计算

链接地址:https://www.31ppt.com/p-4602624.html