并行算法的设计基础.PPT

上传人:国*** 文档编号:774498 上传时间:2018-10-31 格式:PPT 页数:68 大小:537KB
下载 相关 举报
并行算法的设计基础.PPT_第1页
第1页 / 共68页
并行算法的设计基础.PPT_第2页
第2页 / 共68页
并行算法的设计基础.PPT_第3页
第3页 / 共68页
并行算法的设计基础.PPT_第4页
第4页 / 共68页
并行算法的设计基础.PPT_第5页
第5页 / 共68页
点击查看更多>>
资源描述

1、第四章 并行算法的设计基础 并行计算相关的研究分支1. 并行计算机体系结构2. 并行计算的性能评价3. 并行算法4. 并行程序设计一、并行算法相关的基本概念及表示二、介绍几种并行计算模型3. 并行算法1. 并行计算机体系结构2. 并行计算的性能评价Date 1一、并行算法相关的基本概念及表示基本概念并行算法的表示并行算法的复杂性度量并行算法的同步与通信Date 21. 基本概念定义 1: 算法 :在有限步骤内求解某一特定问题的一组无二义性的规则。定义 2: 并行算法 是由一些独立的、可以并行运行的计算模块(进程)构成,模块(进程)之间能相互作用和协调,以完成对一个给定问题的求解。Date 3根

2、据算法的不同特征,可以对并行算法进行不同的分类: SIMD算法和 MIMD算法 同步算法和异步算法 数值计算算法和非数值计算算法 共享存储算法和分布存储算法Date 4定义 3: 同步算法 (synchronized algorithm):是指算法的诸进程的执行必须相互等待的一类并行算法。 SIMD算法是同步算法中的一种特例。定义 4: 异步算法 (asynchronous algorithm):是指算法的诸进程的执行不必相互等待的一类并行算法。定义 5: 分布并行算法 (distributed algorithm): 将同一任务分解为若干个子任务,使之分布在由通信链路连接的多个节点上协同完成

3、运算的算法。分布式算法的执行时间,在很大程度上受通信开销的影响。Date 5定义 6: 确定算法 (deterministic algorithm):每个运算步骤上均确定唯一操作的算法。如线性方程组求解的算法。不确定算法 (non-deterministic algorithm): 在问题求解的搜索过程中,提出多种可供选择的操作,它们中的任一种都有希望获得问题的解答,但都不能肯定解出,有时甚至不能确定这些操作中哪一种求解的可能性更大些。对此,只能选择其中任意一种搜索下去。这种搜索方法称为不确定算法。Date 6定义 7: 随机算法 ( randomized algorithm, probabi

4、listic algorithm )计算步骤具有随机性的算法。在算法的某一步或某些步上,可以在指定范围内随机地选择下一个演算步的走向。如果方法得当,可比一般算法更快地得出结果,并且能以较高的概率提供正确的结果。Date 7 表示算法的要求 无二义性 力图直观、易懂 不苛求严格的语法格式 一般的串行算法常用类 Pascal、类 Algol表示2. 并行算法的表示Date 81. par-do语句for i=1 to n par-do : :end for 表示其间的 n (i=1 to n) 次语句序列的执行可以并行完成表示 k 个处理器同时执行其间的语句序列2. for all 语句for a

5、ll Pi where 0 i k-1 do : :end for并行算法常引入以下两条并行语句:Date 93. 并行算法的复杂性度量令 f(n) 和 g(n) 是定义在自然数集合 N 上的两个函数,定义 8: 如果存在两个正数 c 和 n0 , 使得对于所有的 n n0 均有 f(n) c g(n) ,则 标记为: f(n)= ( g(n) )我们称 g(n) 为 f(n) 的 上界 。定义 9: 如果存在两个正数 c 和 n0 , 使得对于所有的 n n0 均有 f(n) c g(n) , 则标记为: f(n)= ( g(n) )我们称 g(n) 为 f(n) 的 下界 。Date 10

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 重点行业资料库 > 1

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。