基于双向消息的并行归约算法的研究和实验.pdfVIP

基于双向消息的并行归约算法的研究与实验 何斌漆锋滨 摘要 本文在传统并行规约算法的基础上．充分利用双向消息的特点．提出r两种新的并行规约 算法，井与传统算法进行了比较，实验证明新算法分别适用于不同规模的规均运算．具有明显的 优势。 关键词：并行规约双向消息并行算法并行效率 一、引言 气象领域一直是并行机的主要应用方向之一。数值天气预报具有计算复杂度高、数 据量大、时效性等要求，程序中存在大量的规约运算．如T106L19中需要归约计算的包含 涡度、散度等太数组在内的谱系数归约总量就达7兆多字节．做lO天预报就需归约960 次，所以归约函数效率的高低直接影响整个系统的时效，必须寻求一种高效的归约算法。 为了便于讨论．本文的规约以规约求和为例，其他规约操作类似。并行规约是指将各处理 机的一个或一组数据求和，并将计算结果返回到各个处理机，即 ^ ／TL=l。2，3，……，n g(m)=己^(m) ‘=I 其中，A。表示第i台处理机上的数据，有Ai(1)，AL(2)，．．．．．．．^(n)组成．n表示归约长 度．i表示处理机的坐标．i-0，1．……^表示第i个处理机，x为规约结果。 传统的规约算法n]的处理过程可以分成两个阶段：首先将数据以二叉树的方式向上 传递．在根处理机上求出最终结果．然后将结果逐步向下传递给其他所有处理机。不难看 出。此算法没有充分利用阿络的对分带宽．特别是计算只在部分处理机上执行，而大部分 处理机空阚。所以如何将计算和通信合理的分布到各个处理机，就成为提高并行规约效 率的关键。为了便于讨论．本文在算法l中介绍了传统算法，算法2和算法3为两种新的 规约算法。 二、算法描述 为了讨论方便，令： P： 处理机个数，且P为2的N幂 n： 规约数据长度，n个字节 T。d： 单向发送，每次发送n个数据的时间 7Ik： 双向发送．每次发送n个数据的时间 Ld： 双向发送．每次发送n／2个数据的时间 L“ 计算n个数据的时间 ·158· 算法l(传统算法)： 该算法分两个阶段实现： 第一阶段：根据二叉树规则，执行l092”步通信和计算后，某一处理机得到所有处理机 的归约结果。在第1次中，处理机Pi(iMOD201=21。1—1)发送全部数据到处理机P；(i_i +2。1)上，收到消息的处理机只进行计算，消息长度为n； 第一阶段：把计算结果广播到所有处理机。其处理过程和第一阶段的通信处理过程 MOD 正好相反，执行h也”次通信：在第1次通信过程中，Ij(i21=2。1—1)接收Pi(j=i+ 201)发送的数据，其数据长度为u。 在第一阶段，每次发送或接收n个数据，接收方对接收的数据进行处理，作为下一次 消息发送的源数据；在第二阶段，获得归约结果的处理机以二更树原则广播到所有处理 机。在整个处理过程中需要通信的次数为2*lo趣”，每次的通信数据量为n通信的开销 为2*l啦”*1k，，计算开铬为l。懂9*10，所以此算法总的计算时间为： TI=2*loga”*‘11眦1+l092”*％ 图】为率算法的处理机问通信示意图， 圈1算法1通信示意囝 算法2(双向蝶式算法l： 从图1可以看出，算法1的通信次数太多达2*l啦”次。为了减少通信．把单向消 息改成双向消息可以得到算法2。 根据蝶式算法，执行l哩9次通信和计算后所有处理机都得到归约运算的最终结果。 数据n，接收消息后．本地数据和接收的消息进行归约运算，结果作为下一次发进消息的 源数据。 在本算法中，每个处理机同时发送和接收消息．对接收到的数据进行处理，计算量为 n个数据。整个过程的通信开销为l啦9*L衅，计算开销为10＆9*k。总的时问开销为： T=loar*Tm+l092。*。I■ 图2为算法2的处理机间通信示意图。