并行算法
本章首先介绍了并行算法的各种分类方法然后讲述了如何在目前特别流行的一种并行
系统—机群系统上设计高效的并行算法说明了在机群系统上适合什么样的并行算法给出
了一些基本的原则和方法为以后的并行程序设计打下基础
3.1 并行算法分类
并行算法是给定并行模型的一种具体明确的解决方法和步骤按照不同的划分方法
并行算法有多种不同的分类
根据运算的基本对象的不同可以将并行算法分为数值并行算法数值计算和非数值
并行算法符号计算当然这两种算法也不是截然分开的比如在数值计算的过程中会
用到查找匹配等非数值计算的成分当然非数值计算中也一般会用到数值计算的方法划
分为什么类型的算法主要取决于主要的计算量和宏观的计算方法
根据进程之间的依赖关系可以分为同步并行算法步调一致异步并行算法步调
进展互不相同和纯并行算法各部分之间没有关系对于同步并行算法任务的各个部
分是同步向前推进的有一个全局的时钟不一定是物理的来控制各部分的步伐而对于
异步并行算法各部分的步伐是互不相同的它们根据计算过程的不同阶段决定等待继续
或终止纯并行算法是最理想的情况各部分之间可以尽可能快地向前推进不需要任何同
步或等待但是一般这样的问题是少见的
根据并行计算任务的大小可以分为粗粒度并行算法一个并行任务包含较长的程序段
和较大的计算量细粒度并行算法一个并行任务包含较短的程序段和较小的计算量以
及介于二者之间的中粒度并行算法一般而言并行的粒度越小就有可能开发更多的并行
性提高并行度这是有利的方面但是另一个不利的方面就是并行的粒度越小通信次数
和通信量就相对增多这样就增加了额外的开销因此合适的并行粒度需要根据计算量通
信量计算速度通信速度进行综合平衡这样才能够取得高效率
|
