一种任意维Line—Sweep计算的数据划分算法.pdfVIP

第 35卷 第 12期 计 算 机 学 报 Vo1．35 NO．12 2012年 12月 CH1NESEJOURNAL OF C0M PUTERS Dec．2O12 一 种任意维Line—Sweep计算的数据划分算法 王 鹏” 邱 枫 张为华” 臧斌宇” 朱传琪” (复旦大学计算机学院 上海 200433) (复旦大学并行处理研究所 上海 200433) (复旦大学高分子科学系 上海 200433) 摘 要 数据划分是在当前主流高性能计算平 台上高效并行化应用程序的关键技术 ，它包括数据分割和处理机分 配两个主要部分．Line—Sweep计算模式被众多科学工程计算核心采用，目前该计算模式的并行化主要采用多重数 据划分．多重数据划分能保证各处理机 的计算量、访存量和通讯量相等 ，但在某些情况下也会导致访存量和通讯量 过多，因此无法保证性能最优．为解决这一缺陷，文中提出均衡数据划分 ，进一步放松对数据分割和处理器分配的 非本质约束，以利于在计算、访存和通讯这 3种开销之间达到最佳平衡．文中给出生成最佳均衡数据划分的算法 ， 它包含 3个关键技术：首先建立性能模型，在该模型中均衡数据划分的性能只与数据分割方式有关；接着基于该模 型缩减数据分割方式的有哪些信誉好的足球投注网站空间，并以该模型为判据有哪些信誉好的足球投注网站性能最佳的数据分割方式；最后设计处理机分配函数以满 足均衡数据划分的条件．均衡数据划分被应用于NPB并行测试包中的SP程序和高分子材料计算程序 LineABC．实 验结果表明，当均衡数据划分与多重数据划分的数据分割方式相同时，二者性能基本一致；当两种数据分割方式不同 时(对于 SP和 IineABC，这种情况所 占比例分别高达 38．7 和 37．9 )，采用均衡数据划分的SP程序和 IineABC 程序的并行效率比多重数据划分平均分别高出44．45 和 22．15 ． 关键词 Line—Sweep计算 ；负载均衡 ；多重数据划分 ；均衡数据划分 ；性能模型 中图法分类号 TP302 DOI号 ：10．3724／SP．J．1016．2012．02573 A DataPartitionAlgorithm forArbitraryDimensionalLine—SweepComputing WANG Peng ， QIu Feng ZHANGWei—Hua’， ZANGBi Yu ’ ZHU Chuan-Qi ”(SchoolofComputerScience，FudanUniversity，Shanghai 200433) ’(ParallelProcessing Institute，FudanUniversity，Shanghai 200433) (DepartmentofMacromolecularScience，FudanUniversity，Shanghai 200433) Abstract Datapartition isakeyoptimization techniquethatparallelizesapplicationsonmain— stream highperformancecomputingplatforms．Thistechniqueiscomposedoftwoparts：dividing dataandassigningdataamongprocessors．Line—Sweepcomputingisoneofthemostwidely—used kernelsinavarietyofnumericalmethodsandhow toparallelizeithasbeen aresearch hotspot． Untilnow，mostpriorresearchestry toparallelizeLine—Sweep algorithm thr