---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------并行编程模型与并行语言
并行编程模型
目前最重要的并行编程模型是数据并行和消息传递,数据并行编程模型的编程级别比较高
,编程相对简单,但它仅适用于数据并行问题;消息传递编程模型的编程级别相对较低,但消息传递编程模型可以有更广泛的应用范围。数据并行即将相同的操作同时作用于不同的数据,数据并行编程模型提供给编程者一个全局的地址空间,一般这种形式的语言本身就提供并行执行的语义,因此对于编程者来说,只需要简单地指明执行什么样的并行操作和并行操作的对象,就实现了数据并行的编程
消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、控制执行。消息传递一般是面向分布式内存的,但是它也可适用于共享内存的并行机。
数据并行与消息传递并行编程模型的比较
讲解:
不同的并行编程模型也就是不同的通过并行程序解决问题的模式,数据并行的主要特征是以数据为中心,通过对数据的划分和并行处理来解决问题,消息传递当然也可以实现上述功能,但是消息传递在问题的表述上更具体,更低级,可以解决的问题相对于数据并行模型来说也更广泛。在一定程度上,可以把数据并行看作是消息传递的特殊形式。
为什么说数据并行编程模型比消息传递编程模型级别高?
数据并行将复杂的消息传递工作交给了编译器去完成,而消息传递模型下这些工作都需要编程者来完成
你知道的其它编程模型还有哪些?
函数式并行,共享变量
现在串行编程语言几乎都是高级语言,为什么在并行计算领域编程语言却还相对级别较低?
并行计算目前还缺乏统一的模型和标准
你知道的并行语言有哪些?
HPF,各种并行C,并行C++,并行PASCAL
你认为串行语言和并行语言的区别有哪些?
是否提供并行的结构,是否提供并行的语义
------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------并 行 算 法
并行算法一般是浅而宽,串行算法是深而窄
并行算法划分方法:
根据运算的基本对象的不同划分
数值并行算法(数值计算)和非数值并行算法(符号计算)
根据进程之间的依赖关系划分
同步并行算法(步调一致)、异步并行算法(步调、进展互不相同)和纯并行算法(各部分之间没有关系)
粗粒度并行算法(一个并行任务包含较长的程序段和较大的计算量)、细粒度并行算法(一个并行任务包含较短的程序段和较小的计算量)以及介于二者之间的中粒度并行算法根据并行计算任务的大小划分,一般而言,并行的粒度越小,就有可能开发更多的并行性,提高并行度,这是有利的方面,但是另一个不利的方面就是并行的粒度越小,通信次数和通信量就相对增多,这样就增加了额外的开销,因此合适的并行粒度需要根据计算量、通信量、计算速度、通信速度进行综合平衡,这样才能够取得高效率。
并行算法分类的不同代表算法特点的不同,即具体的操作模式的不同,问题的不同,并行计算机特点的不同,是选择不同并行算法的主要依据。
机群算法的设计原则 :就是设法加大计算时间相对于通信时间的比重,减少通信次数甚至以计算换通信。
这是因为,对于机群系统,一次通信的开销要远远大于一次计算的开销,因此要尽可能降低通信的次数,或将两次通信合并为一次通信。基于同样的原因,机群计算的并行粒度不可能太小,因为这样会大大增加通信的开销。如果能够实现计算和通信的重叠,那将会更大地提高整个程序的执行效率。
习题:
并行算法的分类是怎样的?
粗粒度/细粒度并行算法,同步/异步并行算法
同步并行算法在具有什么特点的并行计算机上可以高效实现?
SIMD类并行计算机
粗粒度的并行算法在什么条件下性能优于细粒度的并行算法?
并行的粒度越小就有可能开发更多的并行性提高并行度这是有利的方面但是另一个不利的方面就是并行的粒度越小通信次数和通信量就相对增多这样就增加了额外的开销因此合适的并行粒度需要根据计算量通信量计算速度通信速度进行综合平衡这样才能够取得高效率。
一个好的并行算法的前提是什么?
一个好的并行算法要既能很好地匹配并行计算机硬件体系结构的特点又能反映问题内在并行性
如何设计适合机群系统的并行算法?
对于机群系统一次通信的开销要远远大于一次计算的开销,因此要尽可能降低通信的次数或将两次通信合并为一次通信,基于同样的原因,机群计算的并行粒度不可能太小,因为这样会大大增加通信的开销,如果能够实现计算和通信的重叠那将会更大地提高整个程序的执行效率。对于MPMD 并行算法,各并行部分一般是异步执行的而不是象SPMD 那样的同步或松同步方式,因此只要能够大大降低通信次数,增大计算相对于通信的比重,则该MPMD 算法就可以取得较高的效率设计一个适合机群系统的并行查找算法。