机群算法的设计原则
对于机群计算,有一个很重要的原则就是设法加大计算时间相对于通信时间的比重,减少通信次数甚至以计算换通信。
这是因为,对于机群系统,一次通信的开销要远远大于一次计算的开销,因此要尽可能降低通信的次数,或将两次通信合并为一次通信。基于同样的原因,机群计算的并行粒度不可能太小,因为这样会大大增加通信的开销。如果能够实现计算和通信的重叠,那将会更大地提高整个程序的执行效率。
因此,对于机群计算,可以是数值或非数值的计算,这些都不是影响性能的关键,也可以是同步、松同步或异步的,但以同步和松同步为主,并行的粒度一般是大粒度或中粒度的。

几种不同的并行执行方式

好的并行算法的模式
一个好的算法一般应该呈现如下的计算模式:

图3-1 适合机群系统的SPMD并行算法的计算模式


上图没有考虑计算与通信的重叠,若能够实现计算与通信的重叠,那将是更理想的计算模式。

 
计算与通信重叠的SPMD并行算法的计算模式

上图是加入了计算和通信重叠技术后的SPMD并行算法的计算模式。

本节小结:
如何设计高效的并行算法是这一部分的关键,而好的并行算法取决于两个方面的因素,一是问题本身内在的并行性,二是实现该并行算法的并行计算机,只有既充分挖掘了问题内在的并行性,又充分适应实际的并行计算机的特点,这样的算法才可以取得高效率。这对机群系统如何减少通信次数,是设计并行算法的关键问题。