减少交互开销影响的方法

《减少交互开销影响的方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、减少交互开销影响的方法进程间的交互开销取决于许多因素，如进程间交互的数据大小、交互的频率、交互的时空属性等减少交互开销的一般性方法：最大化数据局部性；最小化竞争与Hotspot；计算与交互重叠；数据复制或重复计算；利用优化过的聚合交互操作；将交互开销相互重叠。2021/6/181最大化数据局部性减少进程间交互的数据量采用恰当的分解与调度策略以利用局部数据执行尽可能多的操作，例如对矩阵乘法，采用二维分布比一维分布时具有更少的共享数据使用局部数据来存储中间结果，并且只在进行最后结果的计算时，才访问共享数据，例如内积的计算减少进程间交互的次数在许多体系结

2、构上，交互的起步时间一般相对比较长通过对算法进行重新组织，使得对共享数据的访问与使用以成片方式进行，可以减少进程间交互的频率例如，稀疏矩阵与向量的乘法2021/6/182最大化数据局部性(续)对共享数据进行整合，减少交互次数01237456891011P0:y0(x1,x4,x8)；y4(x0,x5,x8,x9)；y5(x1,x2x4,x6,x9)；y8(x0,x4,x6)P1:y1(x0,x2,x5,x6)；y2(x1,x3,x5,x6)；y3(x2,x7)；y7(x3,x6)P2:y6(x1,x2,x5,x7,x9,x10,x11)；y9(x4

3、,x5,x6,x10)；y10(x6,x9)；y11(x6)2021/6/183最小化竞争与Hotspot数据访问与进程间交互常引起竞争。多个任务同时访问相同的资源的可能情况如：经过同一条物理链路的多个消息同时传输对同一个存储块的多个访问同时进行在同一时候多个进程向同一个进程发送消息2021/6/184最小化竞争与Hotspot(续)在二维输出划分下，进行并行矩阵乘法时，对每个块Cij，0i,j

4、时间内可以安排一些有用的计算，这就是计算与通信重叠一个简单的方法是尽早地开始进行交互，使得需要利用该交互的结果进行计算之前，交互就已经完成在大多数情况下，将计算与交互重叠需要编程语言、操作系统与硬件的支持2021/6/186数据复制或重复计算在有些并行程序中，多个进程可能需要频繁地对共享数据结构进行只读访问在消息传递语言中，数据复制更有利，这不仅可以减少交互开销，也有利于简化并行程序的编写数据复制是有代价的。数据复制将增加程序的存储需求，只能有选择性地采用这种技术来复制一些存储需求相对较小的数据执行并行程序的进程往往共享一些中间结果，计算这些中间结

5、果也许比通过交互获取需时更少。如FFT的并行计算。2021/6/187利用优化过的聚合交互操作许多重要的聚合交互操作在很多并行算法中经常出现，如广播与归约为了最小化数据传输开销与竞争，已经设计了这些聚合交互操作的优化得很好的实现算法。在许多并行计算机上，生产厂商研制的并行库如MPI内一般都包含这些实现的函数2021/6/188将交互开销相互重叠有时，采用并行库内的聚合交互函数效率不高，或者某些聚合交互操作在并行库内并没有实现2021/6/189