通用多核集群上的并行调优策略研究

【作者】 王鹏；

【导师】 朱传琪；

【作者基本信息】 复旦大学 ， 计算机体系结构， 2011， 博士

【摘要】 随着高性能计算进入多核时代,通用多核集群已逐步成为当前大规模并行计算的主流平台。这类集群系统以多路通用多核服务器(Multi-Socket Multicore Server)为基本计算节点,节点间采用Infiniband等高速网络互联。通用多核集群的兴起带来了并行调优方面的深刻转变和挑战,主要表现为这类集群上的并行编程和调优环境还不成熟,与硬件之间存在巨大鸿沟,目前这类系统上的并行程序调优工作主要依靠程序员手工完成。一个极具现实意义的问题是,给定一个应用程序和目标集群,应遵循怎样的流程来优化并行程序以尽量发挥系统性能?解决这一问题的技术统称为并行调优策略,该技术定义了一套系统化的分析、理解和优化并行程序的方法。目前,面向应用的以大规模通用多核集群为目标平台的并行调优策略的研究刚刚起步,本文即是这个方向的一次尝试。本文针对当前主流并行调优技术的不足,以科学计算中最常见的FMM和Stencil计算为目标,提出一种能够用于指导在通用多核集群上对应用程序进行并行调优的新策略。该策略首先将影响程序性能的主要因素分为计算、访存、通讯和负载均衡(分别简称为P、M、C、B)四个主要类别,不同程序的PMCB的特性是不一样,需要区别对待。FMM类程序的主要性能特征都能手工精确计算,对于这类程序我们提出一套基于静态分析的优化策略,收到了很好的效果。Stencil计算中计算优化相对独立,可以独立确定,访存和通讯则相互影响,其中一部分访存优化可以通过静态分析决定如何选择优化参数,剩下的访存优化和通讯优化相互影响不易确定,为了确定这部分优化组合,我们开发了访存和通讯微测试程序来模拟Stencil计算中常见的访存和通讯模式,通过微测试程序可以有效比对不同访存和通讯的优化组合之间的相对优劣。由于避免了直接运行程序带来的高开销,新策略只需要自优化10%的时间就能达到自优化95%的效果。Stencil计算中的Line-Sweep计算具有特殊的访存和通讯特征,简单的负载均衡策略(保证各计算节点的计算、访存和通讯量一致)并不能保证性能最优。这是因为简单的负载均衡策略在某些情况下会导致访存量和通讯量过多。为了解决这一缺陷,本文提出均衡数据划分,进一步放松对数据分割和处理器分配的非本质约束,以利于在计算、访存和通讯这三种开销之间达到最佳平衡。文中给出生成最佳均衡数据划分的算法,它包含3个关键技术：首先建立性能模型,在该模型中均衡数据划分的性能只与数据分割方式有关；接着基于该模型缩减数据分割方式的搜索空间,并以该模型为判据搜索性能最佳的数据分割方式；最后设计处理机分配函数以满足均衡数据划分的条件。我们将均衡数据划分应用于APPBT和APPSP程序。实验结果表明,当均衡数据划分与多重数据划分的数据分割方式相同时,二者性能基本一致：当两种数据分割方式不同时均衡数据划分效率远高于多重数据划分。从整体看,均衡数据划分的并行效率在不同计算节点数下的方差较小。更多还原

【Abstract】 Nowadays, clusters constituted of Multi-Socket Multicore servers and high speed cLANs such as infiniband have become mainstream high performance computing platforms. The rising of such kind of parallel computing platforms has a significant impact on performance tuning, because tuning application performance on such platforms is very difficult and most work is done by hand due to the software-hardware gap. The main problem lays ahead of programmers is how to tune a given application on a target Multicore cluster. This paper tries to solve this problem by developing a parallel performance tuning scheme which can synthesize all kinds of possible optimizations efficiently.The target applications of our scheme are FMM and Stencil computing. Firstly, the scheme divides all factors affecting application performance into four classes: computation, memory access, communication and load balance (referred to as P, M, C, B in sequence). As different types of applications are characterized by different PMCB patterns, our tuning scheme develops tuning procedure for FMM and Stencil computing respectively. In FMM applications, all important characters that can affect performance can be figured out by hand precisely. For such kind of applications, our scheme use a static analysis based tuning algorithm to synthesize all optimizations and the experiment results are satisfying. In stencil computing, computation pattern is essentially independent of memory access and communication pattern, which means the computation related optimizations can be determined independently first. Then our scheme tries to determine optimizations belonging to M as much as possible. After this step, there remain some M and C optimizations which interact with each other and are hard to be figured out by static analysis. For these optimizations, we develop a suite of microbenchmarks to simulate memory access and communication patterns that occurs in target applications. We use these microbenchmarks to compare all possible optimization combinations and choose the one with best performance. As a result, our scheme works well. It can deliver 95% performance of auto-tuning while spending only 10% amount of auto-tuning time because the microbenchmarks can effectively depict interferences of optimizations and avoid simulate the whole application.As to FMM and some target stencil computing programs, load balance just means distributing computation, memory access and communications equally among all computing nodes. But for Line-Sweep computing, which is also a stencil computing, a load-balance scheme that guarantees every processor the same amount of computation, memory access and communication cannot always 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. 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 Balance-Partition outperforms Multi-Partition significantly.更多还原