LecNote_14_并行算法设计(二)

第十四次并行算法设计(二)，分割并行一维FFT问题多体问题N-Body的bans-hut算法流水并行gaus 一维FFT上述二维FFT算法中，虽然没有考虑矩阵的各行(列)如何实现，但假设已经有一维的FFT/DFT函数，虽然没有考虑各行(列)内部是否存在并行性，但是计算任务会对一维的向量进行DFT g并行性：可按bk并行计算的局部性：每个bk的计算需要整体向量(a0、a1、an-1 )，因此为了提高并行性能，(a0、a1、an-1 ) 发现必须分割以提高对问题规模的可扩展性：可以解决问题的规模随着处理器的数量的增加可以提高程序中的数据访问效率：通常，相关数据的规模越小，访问命中率越高的通信问题，bk=(0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15 ) (0，2，4，6，8，10，12，wk (4，12，4，2，2 ) 9 ) wk (5，13 ) wk (3，7，11，15 ) wk (3，11 ) wk (7，15 )、a0、a1、a2、a3、a4、a5、a6、a7、a8、a9、a10、a1、a12、a13、a14、a5、b0、b1 、a0，a1，a2，a3，a4，a5，a6，a7，a8，a9，a10，a11，a12，a13，a14，a5，b1 b2，b3，b4，b5，b6，b7，b8，b9，b10，b11 、bk=(0，1，2，3，4，5，6，7，8，9，10，11，12，14 ) (0，2，4，6，8，10，12，14 ) (0，4，8，12 ) wk (4，14，14 ) (14 ) wk (1，3，5，7，9，11，13 ) (1，5，9 ) wk (5，13 ) wk (3，7，11 ) (311 ) wk (7)，a0，a1，a2，a3，a4，a5，a6，a7，a8，a9 b10，b11，b12，b13，b14，一维FFT并行特性是在相关的两个数据间连接一个边缘时，所有数据间完全关联的图。 在这里， p是每当处理器的数量交换n/p次的通信时按处理器进行重新分组的各处理器上的环路空间nlog(n)p的每环的计算量：一维并行FFT的scalability各处理器上的负载n/p个bk，其各处理器上的数据量为p protinganddividee-and-conquerystrategies划分策略，用于计算消息大小n/p并划分并行性：通常将问题划分为几个组件，除非结合每个组件的结果，否则将整个问题的结果划分为例如，理想的并行策略是一种在将每个组件的结果组合成整个问题的结果时几乎不需要额外计算的划分策略。 分割策略的分类数据分割(datapartitioning)/域分割(domaindecomposition ) :将计算的数据分割为数据的子集，并在不同的子集上并行执行处理。 例如，在二维FFT计算中，具有不同依赖于对每个子集的数据执行的操作的数据子集可以采用数据复制策略来“重叠”数据将整个二维阵列用“行”和“列”分隔的每个“行/列”的一维FFT分解：将计算任务分成独立的功能模块组，同时执行各功能模块。 不同功能模块所需的初始数据例如为Jacobi迭代(求解方程AX=B )，其中每Xi(t )的计算用作功能模块，并且每个功能模块指示关于a的第I行和第Bi行。所有X(t-1 ) (“重叠”的数据部分)、分割策略(divide-and-conquer ) :将复杂问题分成子问题组，每个子问题的形式与原问题相同，但规模比原问题小， 子问题采用该策略能够进一步细分的是另一种特殊情况的分区策略：子问题和原问题除了问题的规模外，都是同一个例子：一维FFT(A )，其中a是长度为n的向量。 我们采用的并行策略是： FFT(A)=FFT(FFT(A0dd )，FFT(Aeven ) )，FFT(A0dd )，FFT(Aeven )和FFT(FFT(A0dd ) )， FFT(Aeven)FFT(A0dd )执行由a的奇数位置的元素构成的向量的一维FFT，问题规模为原问题规模的一半的FFT(Aeven )执行由a的偶数位置的元素构成的向量的一维FFT，问题规模为原问题规模的一半的FFT(FFT(A0dd ) )， FFT(Aeven) )执行由一个2要素构成的向量的一维FFT，M-ary的分割策略将复杂的问题分解为m个子问题，m-2个子问题以与原始问题相同的形式子问题的规模过大时，再将各个子问题分解为m个粒度更细的子问题，递归地， 各子问题的规模变得合适之前，一个4-ary分治的例子：， 用分治策略解决N_Body问题，n个粒子(body )在天体物理学上代表恒星，如地球、太阳、火星等在分子动力学上代表构成一个分子的各个原子各个粒子有一定的状态：位置、速度、加速度、能量、温度等， 这些状态随时间变化影响一个粒子状态变化的因素是，粒子初始状态的其他粒子具有其作用力的任意两个粒子之间有牛顿万引力，关于两个粒子的距离有不同的物理问题，粒子之间有与其他双方状态相关的力。 例如，两个原子之间有电势(与原子的自转速度、原子间的距离等有关)。 问题：对于一个N_Body系统，各粒子的初始状态的最终状态是什么样的，即，在各粒子的状态不再变化的情况下，各粒子的状态是什么样的，在从初始状态向最终状态的变化过程中，变化的轨迹是什么样的，即， 对于我们感兴趣的(若干)状态量(例如电磁场电势分布)，随时间变化的规律是什么？ 参考DesigningandBuildingParallelPrograms第1.4.2节，以“block”方式将n个粒子分成m组，m将处理器数量的各组作为一个粒子的子集分配给处理器，除了存储本地粒子的子集local_body_set之外在每个处理器上，以local_body_set以每个时间步长初始化buffer，以1到m的间隔初始化以下循环，计算在local_body_set中的每个粒子循环的buffer中的每个粒子的力发送到，从“右”邻居接收消息，将与得到的力相应的消息数据存储在缓冲器中(M-1#处理器的“右”邻居是0#处理器)。 为了更新local_body_set中的各粒子的状态，可以以100各粒子、4个处理器为例，在每个时间步骤，0#处理器、0#处理器、0#处理器、0#处理器、 N_Body问题的并行算法：对性能分析问题规模的scalability数据的scalability :计算数据以“block”方式被分成各处理器， 数据存储的能力是与处理器的数目呈线性关系的速率的可缩放性：每一处理器处的主要计算开销是每一时间步骤的复杂度为O(N2M)=O(N2 )，其是对local_body_set的粒子接收到的力的计算。 这里，n是粒子数，m是处理器数通信复杂度：由于按每个时间步骤开始通信的每O(M )通信的数据传输开销o(nm )的合计数据传输开销O(N)N是粒子数，m是处理器数， 使用该算法解决N_Body问题：随着问题规模的增大，无论是否增加处理器数量，计算性能都以O(N2 )的比率大幅下降，在分子模拟和天体物理学计算中，n的数量变多，在104或以上实用N_Body问题的优化并行算法，Barnes-Hutt算法：采用分散战略，进行近似计算的基本思想：对于任何粒子a，在组的粒子和a的距离“足够远”的情况下，这些粒子对a的影响可以用“个体”来替换。 在牛顿力学中，任何粒子b对a的作用与r2成反比，如果a和b之间的距离对于一组粒子B1、b2. bk在空间位置，边的长度在d的立方体的范围内，则r是立方体的中心和a的距离。 只要r大于“足够”且d小于“足够”，在计算B1、B2、Bk对a的影响时，就可以将其视为单个“个体”b，B1、B2、Bk对a的影响用b近似的重要问题被称为“足够”，而“组”是哪个？ N_Body问题的优化并行算法：实现构想，构造树：确定包含相关空间的立方体用一根8分树来表示该空间的下一个划分，同时表现空间中粒子分布的地域性和层次性。 此立方体是根，如果其中只有一个粒子就停止，则以自然方式将它分割为8个相等的子立方体，如果粒子存在，则用子节点表示。 以每个子节点为根，重复上述步骤。 结果：每个叶节点表示粒子，每个粒子由唯一的叶节点表示。 内部节点表示空间单元。 考虑节点实现为由数据结构节点表示的立方体的重心的属性，包括节点所表示的立方体的边的长度d，例如空间位移、质量、速度和加速度。 如果粒子分布在三维空间，则得到一棵八叉树。 如果粒子分布在平面空间，则得到一棵树。 N_Body问题实现了一个想法，计算一个粒子(叶节点)受到的力。 从根部遍历树。 如果空间单元的重心充分远离本粒子，就用其重心处的等价体来计算。 充分距离的标准：设立方体空间边的长度为d，该粒子与其重心的距离为r，可以根据立方体中包含的恒星的质量和重心来计算，所以不需要考虑以下各恒星。 其中，选择在0.51.2之间，越小，意味着近似的精度越高。 该式也表示“距离越远，能近似的空间就越大”的意思。 请注意不同粒子的计算量不同。 在一个粒子中，横穿树时“邻接”的分支深深地横穿。由于树的平均高度为logn，所以计算一颗星的力的平均logn。 因此，整个时间步的计算大约为nlogn。N_Body问题的最佳并行算法：使用并行性分析、Barnes-hut算法解决N_Body问题时，按照每个时间步骤，依次遍历以下四个super-step建树计算数的各个内节点的参数(重心、质量等)， 计算各粒子受到的力来更新粒子属性的各super-step是可并行的建筑：不同的子空间由不同的处理器负责分解，独立操作计算数上的各内部节点的参数：各内部节点的参数计算完全独立地遍历树， 计算各粒子受到的力：以粒子为单位，完全独立地更新粒子的属性：以粒子为单位，完全独立地从各super-step的时间开销比率来看，计算各粒子受到的力是主要的时间开销，N_Body问题是优化并行算法： 关于两个数据结构粒子，各粒子的空间位置、质量、速度、加速度等属性包括树制作过程中得到的8 (或4 )分树：所得到的树在每个时间步骤中，如何划分两个数据结构，如何将计算任务分配给树制作过程，自然的想法是相邻的但是，因为粒子在运动，所以要在每个时间阶段改变粒子间的邻接关系计算哪个粒子受到的力，需要从数量的根中遍历树。 如何划分树呢？每个处理器都有完整的树保存吗？ 在计算单个粒子受到的力时，当然，各处理器负责粒子的力的计算，但是，在单个粒子的力的计算的复杂性是不同的时间步骤，更新同一粒子的力的计算的复杂性不同的粒子的属性的情况下，最好的分配方法是以“block”的方式将粒子均等地分割成各处理器考虑数据分割的最简单方法是，各处理器保存这两个完整的数据结构，但粒子越多，树中的节点的数量也越多，从而损害了对问题规模的scalability，对二维FFT、一维FFS和FOX的算法进行比较三者可以用BSP模型描绘，而且，super-step的数量不依赖于计算出的数据值