《并行计算的数据分配》由会员分享，可在线阅读，更多相关《并行计算的数据分配（8页珍藏版）》请在金锄头文库上搜索。
1、并行计算的数据分配并行计算的数据分配1997 年 5 月May1997计算机工程与科学COMPUTERENGINEERING-SCIENCE第 19 卷第 5 期Voi.I9No.2.,一一/(国防科技大学计算机系)(DepartmentofComputerSienee,NationalUniveIofDefenseTaebnology)摘要本文主要讨论分布式存储环境下并行计算的最佳数据分配方案.通过理论分析和两个共型询太规模科技计算礴 l 是绮数值央验表明,傲据分配是影响井行计算性能的主要因素之一ABSTRACTThepaperdiscussestheoptimaldatadistribut
2、ionschemefordis“ribuiedenvironraents.The:theoreticalanalysisantinumericalexperimentoftwotypicalmance,maxmultiplication,shall0w-watequatiDn.Xol,-6分布式存储的多计算机系统是当前高性能计算机的一个主流方向.同构或异构的工作站通过高速网络联结,协同工作,完成大规模科学计算应用问题,如数值天气预报,石油勘探,图象信号处理等.大规模并行计算的第一步是将数据分配到各个计算机,分布式计算的每一处理机单独完成一个子任务,由于数据的非共享,并行计算过程中相邻区域的数据
3、需要相互交换,通过消息传递进行处理机问的通信.数据分配决定负载平衡和通信粒度,负载平衡和通信延迟是影响并行计算挂能的主要因素.相对于处理机的CPU速度,数据的发送和接收所需的网络延迟和消息处理开销太大,因此分布式存储环境下数据分配是影响并行性能的主要因素一,数据分配夔塑醒旦丝星将任务加载到并行系统的各个计算机,数据分配的最佳方案的目2i 融长期从事大规59.戮一燕标是在最短的时间内获得问题的解.下面我们考虑二维环面互联网络结构的分布式多机系统,假设规模为 16 台计算机,这样要解的问题可平均划分为 16 个子任务.分布式存储环境下太规模科学计算的数据分配方式太体可分为两类;网捂捌分和数据割1
4、阚格划分网格划分主要用于解决基于网格离散的偏微分方程数据分配的方法有子块财分诸,行趣 f 分法和列划分法,如图 I 所示.这里先考虑邻区域的边界数据交换,假设问题规模为 NM 二维数组,下面我们来分析各种数据分配法的通信量.(1)子块数据分配法,每个子区域与其一团田目邻区域的总通信量可用 2(N/4)-F2图 1 数据分配方法(M/4)字来估算,整个问题 l 舶通信量为 l6(N/2+M/Z)字.(2)列数据分配法,每个子区域与其邻区域的总通信量可用 2M 来估算,整个问题的通信量为 162M 字.(3)行数据分配法,每个子区域与其邻区域舶总通信量可用 2XN 来估算,整个问题的通信量为 16
5、2N 字.2 数据分割.数据分割主要用于图形处理,代数运算等并行处理,下面分板这类席题中常用的矩阵录操作.假设 N1XN2 阶矩阵 A 和 N2XN3 阶矩阵 B 相乘 tC=AB 为 N1N3 矩阵,N1,N2,N3 能被 1 嘲 E 昧,面筏 f 门分析矩阵幂的两种数据分析方法的并行计算通信量.(1)A 和 B 按行J/0“配法,昌 9A 按行平均分配科 16 台处理机 A=(AlA:,A),B 按列平均分配到 16 台处理机三一(莒,官,韧同处一台处理机i1,2,16),C=AB,即丑 1且B11岛AzX1BXBz?这样第一步计算可得到 AtB【,AiBi(i 不等于 j)则需要进行数据
6、交换才能计算.将B 进行_,_瑚数据交换 B=(Bz,B3,Bs,B,此时可计笋得蓟茂 B+t 和 Ae.对 Bl 进行 16-1 次=15 敬列数据交换,并进行计算即可得到 c,整个计 l 算程的舄通信量可用(16-1)N1N315N1N3 来估算.(2)A 和 B 都按子块分配法分配到 16 台处理机,即C1,lG1c.1丑 I|Bl,BnB“lBBIBlBH1风蛐AXX#AAAl1日XAlfC:2P1IIlJJBBBqq=nn8CCCC“如如=8 扎如“似如“nnm=A其中 cAuBi1,Aii 和 B1I 同处一台处理机,这样第一步计算可得到 A,AdBlj(i 不等于 j)则需要进行
7、数据交换才能计算,将 B 进行列数据交换得到f,“且一B 且 a 岛 jl 马且 a 且?马-I?【且且 a 且.且 1J通过计算可得到 A【Bu+和 ABl,对 B 进行 41 次一 3 次数据交换,通信量为3N2XN3,并进行计算后得到.Ad,最后作一次加法得到 C,通信量为 3XN1XN3,整个计算过程的总通信量可用 3XN2XN3+3N1N3=3(N1+N2)N3 来估算.许多大型科学计算问题往往归结为对矩阵的操作,矩阵乘又是最常用的,而浅水波方程是大气物理中一个典型的简化方程,因此矩阵乘和解浅水渡方程在科技计算中具有典型性.下面进一步通过数值试验分析数据分配对并行处理的影响.数据分配
8、影响并行处理的负载平衡和通讯粒度,矩阵乘和解浅水波方程采用平均分配数据可达到处理机的负载平衡,这里仅分析通讯粒度对并行计算的影响.我们的试验环境是四台 SGI工作站,并行消息传递平台为 EXPRESS 和 PVM.浅水渡方程采用 EXPRESS 的 FORTRAN 程序,由于浅水波方程的数据区域的对称性,行列数据划分法具有同样的特性,这里仅考虑两种区域划分法:子块划分法(SDI:SubblockDomainImage)和列划分法(CDI:ColumnDo-圈田 mainImage),如图 2 所示.图 2SDI 和 CDI完成一个时间层后邻区域间需要进行数据交换.假设区域的网格点数为 NN,第
9、二节的理论分析已阐明 SDI 划分法一个时间层整个区域的通讯量为 8N/2 字=4XN 字,CDI 划分法一个时间层整个区域的通讯量为 5N 字.为了比较这两种数据分配法的优劣性,我们测试了三种问题规模的并行计算结果,如表 1.裹 1 三种问墨规横并行计算结果从表 1 可以看出,解浅水波方程的子块数据分配法的并行计算加速比均大于列数据分配法的并行计算加速比,子块数据分配法有利于浅水波方程的并行计算.61矩阵乘采用 PVM 的 C 程序模式,数据分配法如第 2 节所述:子块分配法(subbloek)和列行(columnrow)分配法.矩阵 A 为 N1N2 阶矩阵,B 为 N2N3阶矩阵,行列和
10、分配法的总遵信量为 3N1N3 字,子块分配法的总量为(N1+N2)N3 字.为了比较这两种数据分配法对并行计算性能的影响,我们作了四种规模的矩阵乘并行计算,其并行计算结果如表 2.r 寰 2 四种规模矩阵秉并行计算结果从表 2 可以看出,矩阵乘中子块分配法的并行计算效率优予列行分配法得到的并行计算效率.至此,我们从理论分析和数值试验结果得到:子块划分法有利于矩阵乘和解浅水渡方程的并行计算.三,结束语相对处理机的 CPU 速度来说,网络传输速度慢,而且每次数据的发进和接收都需要一定的网络接口系统开销和消息处理开销.恰当的数据分配,不仅可保证并行计算的负载平衡,还可减少数据通信次数和每次通信的数
11、据量,以提高并行计算效率.数据分配是影响并行计算性能的一个重要因素,当然为了并行计算的高性能,我们还应当考虑计算与通信的重叠和问题边界区域与内部区域的并行处理等,尽量减少通信开销.参考文献孙安香.来君强.李晓棒.工作蛄网络并行计算的性能分析.国防科技大学.1997.(2)莫尉尧,李晓梅工作站网络环境下的并行计算.计算机?1997温洪?王鼎?郏伟民.异构机群系统中的最优赴理机丹配算击计算机 1996.(3)伍湘君?朱君强?李晓棒.工作蛄机群上矩阵熏的并行计算.数值计算与计算封崆用,(拟发表)X.Zhangeta1.LatecyMetriclAnExpurlmentaMethodforMeasur
12、ingandEvaluatingParallelProgramandAt-ehitecturescahbility.JournslotParallelandDistributedComputing.1994.22NilsonNJ.ProgramSolvlngMethodsinArdfical|ateligence.NewYorkrMcGrawHill,1971ChuWWeta1.TaskA11ocationinDistributedDataProcessing.IEEEComput.mag.,1980.13(11)r5769L0VM.HeuristicAlgorithmtotTaskAssignmentinDistributedSystlts.TE 髓TransComputers.1988J.Song.A.Song.X.Li.ParallelComputation0fShallow-WaterModelonWorkstationsCluster.WuhanChina:ICPA.199S62t 一_,tjl 一
