第十六章 并行算法

《第十六章 并行算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十六章并行算法并行处理技术就是只把一个处理任务分配给多个处理器同时处理，这样可以使得在一个时刻计算机的计算量增加n倍。为并行处理所涉及的计算机称为并行计算机，随着网络的发展，我们可以利用网络上各个点的资源联合进行分布式计算。所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。2021/8/71第十六章并行算法目录16.1并行计算机16.2并行算法的基本概念16.3并行算法的描述16.4SI

2、MD-SM上的非线性方程求根同步并行算法16.5SIMD-SM上的同步并行求和算法16.6SIMD-CC超立方机器上的同步并行求和算法16.7MIMD-SM上的异步并行求和算法2021/8/7216.1并行计算机串行机和并行机都是依据指令对数据进行操作，Flynn分类法就是根据指令流和数据流的个数将计算机分为4类：(1)单指令流单数据流（SingleInstructionStream,SingleDataStream），简写成SISD，它是指单指令流对单数据流进行操作；(2)多指令流单数据流（MultipleInstru

3、ctionStream,SingleDataStream），简写成MISD,它有很多个处理器，但是由一个控制部件管理，一个数据流被传送给一组处理器，通过处理器上不同指令操作最终得到处理结果；(3)单指令流多数据流（SingleInstructionStream,MultipleDataStream），简写成SIMD，是指多个处理器接收不同的指令对相同数据进行操作；(4)多指令流多数据流（MultipleInstructionStream,MultipleDataStream），简写成MIMD，它使用多个控制器来异步地控制

4、多个处理器，从而实现空间上的并行性。2021/8/7316.1并行计算机MIMD与SIMD计算机的区别：SIMD计算机中每台处理器只能执行中央处理器的指令，而MIMD计算机中每台处理器只是接受中央处理器分配的任务，每台处理器各自执行自己的指令，从而达到空间上的并行性。图16.1、16.2、16.3、16.4分别依次表示了SISD、MISD、SIMD和MIMD的结构情况。控制器处理器存储器指令流数据流图16.1SISD2021/8/7416.1并行计算机控制器1控制器2控制器3处理器1存储器处理器2指令流处理器3指令流指令

5、流数据流图16.2MISD2021/8/7516.1并行计算机控制器处理器1处理器2处理器n……数据流1数据流n数据流2公共存储器指令流图16.3SIMD2021/8/7616.1并行计算机控制器1控制器2…控制器n处理器1处理器2处理器n…公共存储器指令流1指令流2指令流n数据流1数据流2数据流n图16.4MIMD2021/8/7716.1并行计算机根据Flynn分类法，并行计算机主要分为SIMD和MIMD两类。SIMD模型还可细分为给予共享存储的SIMD模型和基于互连网络的SIMD模型。MIMD模型也可细分为基于共享

6、存储的MIMD模型和基于异步通信的互连网络模型。SIMD共享存储型的每个处理器都是有独立算术运算能力和逻辑判断能力的，然后每个处理器之间的信息交流都是通过一个共享存储器，比如处理器i要送一个数据给处理器j，那么首先要把该数据写到存储器上的某个地址，处理器j再从这个地址中读这个数据，但是因为共享存储器的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分为3类：(1)EREW(Exclusive-ReadExclusive-Write),即不允许有两个处理器

7、同时读或写一个共享单元；2021/8/7816.1并行计算机(2)CRCW(Concurrent-ReadExclusive-Write)可允许同时读，但不允许同时写，即允许两个处理器同时读一个共享单元，但只允许一个处理器写某个共享单元；(3)ERCW(Exclusive-ReadConcurrent-Write)不允许同时读，但允许同时写；(4)CRCW(Concurrent-ReadConcurrent-Write)允许同时读和同时写；共享存储的MIMD计算模型中所有的处理器也是共享一个公共的存储器，处理器之间的信息

8、交流也是通过公共存储器来完成的。在基于互连网络的MIMD计算模型中，每个处理器都各自有自己的存储器的（数据都是来自各自的存储器的），信息是通过互连网络进行交流的，在这种模型上设计的算法与互连网络的拓扑结构有关，我们介绍几种比较常见的拓扑结构。2021/8/7916.1并行计算机1、一维线性结构这是最简单的连接方式，其