异构系统上基于任务窃取的负载平衡研究

Nowadays, the mainstream supercomputers in the world are not always homogeneous. Many of them are equipped with accelerators such as GPUs. In large scale computation, load balance is a very important factor for performance and energy efficiency. Traditional task scheduling methods are not sufficient for achieving load balance on heterogeneous systems. This project will investigate load balancing method based on work stealing, mainly targeting at applications that can make good use of accelerators like GPUs. These applications include some chemistry computation such as TCE, SCF, and other applications like n-body problem. The main research topics are (1) Modifying the work stealing scheme. By using different task sizes, with coordination among queues for different processors, we can optimize the work stealing algorithms to get better load balance. (2) Using pipelining and kernel consolidation for tasks on accelerators, thus making good use of the computing research, to achieve load balance. (3) Optimizing the scheduling algorithm according to data locality, thus enabling more efficient access to global data. This project will explore the computing power of heterogeneous systems, providing insights for load balancing on Exascale systems.

当今世界主流的超级计算系统往往不是单一结构的，很多都配有GPU等加速器。在大规模计算当中，负载平衡对计算的性能、功耗至关重要。而传统的任务调度方法往往很难直接用于异构系统，使之实现负载平衡。 本项目将基于广泛使用的任务窃取方法，针对能够充分利用GPU等加速器的程序进行负载平衡研究。这类程序包括一些化学计算方法（TCE、SCF等）以及n-body问题等。主要研究内容包括：（1）改进任务窃取方案，通过使用不同大小任务、不同处理器任务队列调配等方法，优化窃取机制。（2）对加速器上的任务进行流水化和批处理，以充分利用计算资源，更好地实现负载平衡。（3）根据数据局部性对任务调度进行优化，使共享数据的访问更加高效。本项目的研究充分挖掘异构系统的计算潜力，为未来E级系统上的负载平衡研究提供基础。

本项目旨在通过研究任务窃取等负载平衡机制，提高并行系统性能。.在项目执行期间，我们着重调研和实现了一些重要的机器学习算法，对其进行并行化，并研究这些算法在并行运行中的特性。在对stencil计算的研究中，我们提出了一种新的面向计算重用的GPU上代码生成方法，利用计算重叠图对stencil算子进行分析，进而生成优化的GPU代码。此项工作成果发表在2016年《Journal of Computer Science and Technology》。.我们为Fisher Vector算法开发了GPU上的并行代码，并进行了优化。在使用了循环展开，条件分支语句集中判断，向量化等优化方法之外，我们对dense sift的代码实现做了改进，使之更易于并行化并提高性能。另外，我们将dense sift计算中图像的尺度从9个降到8个，去掉了最大尺度，性能大大提升，而实验证明精度与原算法非常接近。成果发表在2016年ICMR，代码已开源。我们的工作使Fisher Vector算法能够实时处理视频，为机器视频领域的研究和应用提供重要工具。.我们为structural SVM设计开发了GPU集群上的并行代码，使之在使用非线性核函数时仍然能处理海量数据。我们对原有代码做了大量优化，并通过使用和改进任务窃取机制，达到更好的性能优化效果。此项工作为序列预测类机器学习算法提供重要研究工具。