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

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

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.