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
