Task-graph scheduling extensions for efficient synchronization and communication
Task-graph scheduling extensions for efficient synchronization and communication
复制标题
DOI：
10.1145/3447818.3461616
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Seonmyeong Bak;Oscar R. Hernandez;Mark Gates;P. Luszczek;Vivek Sarkar
中科院分区：
文献类型：
--
作者：
Seonmyeong Bak;Oscar R. Hernandez;Mark Gates;P. Luszczek;Vivek Sarkar
数十年来，已经研究了任务图，以安排不规则并行应用程序，并将其纳入包括OpenMP在内的许多编程模型中。尽管许多高性能并行库基于任务图，但它们还具有其他调度要求，例如在数据并行性的内部级别和内部阻止通信内的内部同步。在本文中，我们将任务编程计划扩展为支持任务内的有效同步和通信。与过去的工作相比，我们的调度程序避免了对工人线程的僵局和过度检查，并完善了受害者的选择以增加同胞任务的重叠。据我们所知，我们的方法是第一个将帮派策划和窃取工作策划的方法。我们的方法已在板岩高性能线性代数库上进行了评估。相对于LLVM OMP运行时，我们的运行时分别显示了LU，QR和Cholesky的性能提高高达13.82％，15.2％和36.94％，在与矩阵大小，节点数量和使用相关的不同配置中进行了评估。 CPU与GPU。
Task graphs have been studied for decades as a foundation for scheduling irregular parallel applications and incorporated in many programming models including OpenMP. While many high-performance parallel libraries are based on task graphs, they also have additional scheduling requirements, such as synchronization within inner levels of data parallelism and internal blocking communications. In this paper, we extend task-graph scheduling to support efficient synchronization and communication within tasks. Compared to past work, our scheduler avoids deadlock and oversubscription of worker threads, and refines victim selection to increase the overlap of sibling tasks. To the best of our knowledge, our approach is the first to combine gang-scheduling and work-stealing in a single runtime. Our approach has been evaluated on the SLATE high-performance linear algebra library. Relative to the LLVM OMP runtime, our runtime demonstrates performance improvements of up to 13.82%, 15.2%, and 36.94% for LU, QR, and Cholesky, respectively, evaluated across different configurations related to matrix size, number of nodes, and use of CPUs vs GPUs.