Data partition is a key optimization technique that parallelizes applications on mainstream high performance computing platforms. This technique is composed of two parts: dividing data and assigning data among processors. Line-Sweep computing is one of the most widely-used kernels in a variety of numerical methods and how to parallelize it has been a research hotspot. Until now, most prior researches try to parallelize Line-Sweep algorithm through applying a Multi-Partition, which tries to guarantee every processor the same amount of computation, memory access and communication. However, it cannot achieve the best overall performance because it brings up too much memory access and communication under some conditions. To overcome this problem, we propose a new data partition scheme named Balance-Partition for Line-Sweep algorithm. Our scheme can effectively balance the cost of computation, memory access and communication by reducing unessential constraints. This algorithm contains three main key techniques.Firstly, a performance model is designed. In this model, the performance will only be determined by the way it divides data. And then, we reduce the search space of Balance-Partitions based on this model and find the best way to divide data. Finally, we design a processor assignment function to generate a Balance-Partition. To test the effectiveness of our approach, we applied it to the NPB/SP benchmark and a real world polymer material computing application named LineABC. Experiment results show that when the best Balance-Partition and the best Multi-Partition share the same way to divide data, their performances are almost the same. However, when they divide data differently (which accounts for 38. 7% and 37. 9% for SP and LineABC each) , Balance-Partition outperforms Multi-Partition by 44. 45% and 22. 15% for SP and LineABC respectively.%数据划分是在当前主流高性能计算平台上高效并行化应用程序的关键技术,它包括数据分割和处理机分配两个主要部分.Line-Sweep计算模式被众多科学工程计算核心采用,目前该计算模式的并行化主要采用多重数据划分.多重数据划分能保证各处理机的计算量、访存量和通讯量相等,但在某些情况下也会导致访存量和通讯量过多,因此无法保证性能最优.为解决这一缺陷,文中提出均衡数据划分,进一步放松对数据分割和处理器分配的非本质约束,以利于在计算、访存和通讯这3种开销之间达到最佳平衡.文中给出生成最佳均衡数据划分的算法,它包含3个关键技术:首先建立性能模型,在该模型中均衡数据划分的性能只与数据分割方式有关；接着基于该模型缩减数据分割方式的搜索空间,并以该模型为判据搜索性能最佳的数据分割方式；最后设计处理机分配函数以满足均衡数据划分的条件.均衡数据划分被应用于NPB并行测试包中的SP程序和高分子材料计算程序LineABC.实验结果表明,当均衡数据划分与多重数据划分的数据分割方式相同时,二者性能基本一致；当两种数据分割方式不同时(对于SP和LineABC,这种情况所占比例分别高达38.7％和37.9％),采用均衡数据划分的SP程序和LineABC程序的并行效率比多重数据划分平均分别高出44.45％和22.15％.
展开▼
