SHF: Small: Locality Aware Scheduling in Multi-GPU Systems

由中央处理单元（CPU）和图形处理单元（GPU）组成的异构多处理器架构越来越多地用于加速高性能计算（HPC）和云计算等并行工作负载。与传统的多核CPU相比，GPU在性能上有显著的提高，因此被大量用作加速器。采用多个GPU来进一步加快执行速度并提高存储容量。当前的多GPU架构（如DGX）提供超高带宽NVLink通信，以直接在GPU之间传输数据。然而，基于各种存储器和通信模型在多GPU中划分这些计算和数据对程序员提出了巨大的挑战。该项目为不同的应用程序开发基于图的分区技术，同时考虑GPU中计算之间的数据局部性。其次，目前关于异构调度的文献没有考虑GPU内部的处理，而是将其留给制造商。本项目还将基于图的技术扩展到高速缓存块共享中，开发了一个基于局部性的线程块调度器。首先，它开发了用于测量多GPU架构中执行的计算和通信成本的微基准。开发了一个评测工具来测量GPU执行的TB之间的数据共享。其次，为多GPU数据划分设计了一个邻接图，其中顶点表示计算，边表示顶点之间的通信开销。还为GPU内部的数据共享开发了类似的图模型，其中顶点表示TB，边表示TB之间的共享块的数量。第三，递归二分区技术开发的邻接图使用已知的算法和软件，以实现负载平衡之间的分区，并最大限度地减少在多GPU系统中的分区之间的通信成本。TB调度也提出了考虑L2缓存大小和GPU内部的资源限制。第四，该技术被扩展到在异构多处理器中的CPU和GPU之间划分数据和计算。最后，分析了LU分解和Wavefront两个常规应用，并在GPU架构上进行了真实的实现，实现了多GPU调度。此外，我们还分析了Rodinia和CUDA-SDK基准测试中的一些不规则应用程序，以开发图形模型，并在GPGPUSim上执行，验证GPU内部的TB调度。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响评审标准进行评估，被认为值得支持。

Heterogeneous multiprocessor architectures consisting of Central Processing Units (CPUs) and Graphical Processing Units (GPUs) are increasingly used to accelerate parallel workloads like High Performance Computing (HPC) and cloud computing. GPUs provide significant improvements in performance compared to traditional multi-core CPUs, and therefore, are heavily used as accelerators. Multiple GPUs are employed to further speed up the execution and improve storage capacity. Current multi-GPU architectures, such as DGX, provide ultra-high bandwidth NVLink communication to transfer the data directly between the GPUs. However, partitioning those computations and data in multi-GPUs based on various memory and communication models poses a tremendous challenge to the programmers. This project develops graph-based partitioning techniques for different applications considering data locality among the computations in the GPUs. Secondly, the current literature on heterogeneous scheduling does not consider processing inside the GPU, leaving it to the manufacturer. This project also develops a locality-based Thread Block (TB) scheduler by extending the same graph-based technique to cache block sharing.The project is carried out in several steps. First, it develops micro-benchmarks for measuring the computation and communication cost for execution in a multi-GPU architecture. A profiling tool is developed to measure the data sharing among the TBs for GPU execution. Second, an adjacency graph is designed for the multi-GPU data partition, where the vertices represent the computation, and edges represent the communication cost between the vertices. A similar graph model is also developed for data sharing inside a GPU, where vertices represent the TBs and edges represent the number of shared blocks between the TBs. Third, a recursive bi-partitioning technique is developed for the adjacency graph using known heuristics and software to achieve load balance among the partitions and minimize the communication cost between the partitions in a multi-GPU system. TB scheduling is also proposed considering the L2 cache size and the resource limit inside a GPU. Fourth, the technique is extended to partition data and computations between CPUs and GPUs in a heterogeneous multiprocessor. Finally, two regular applications, LU decomposition and Wavefront, are analyzed, and multi-GPU scheduling is developed through real implementation using GPU architectures. Some irregular applications from the Rodinia and CUDA-SDK benchmarks are also analyzed to develop graph models and execute them on the GPGPUSim for verification of the TB scheduling inside the GPU.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.