Design and analysis of scheduling strategies for multi-CPU and multi-GPU architectures

João V. F. Lima, Thierry Gautier, Vincent Danjean, Bruno Raffin, Nicolas MaillardParallel Comput 2015 · DOI

TL;DR

This paper explores how to best assign computational tasks to a mix of CPUs and GPUs in modern supercomputers. They found that for highly regular tasks, strategies that consider processing power (like HEFT) excel, while for more irregular tasks with complex data dependencies, strategies that prioritize data locality (like locality-aware work stealing) perform better. This research is crucial for optimizing performance and efficiency in increasingly heterogeneous computing environments.

What Problem Does This Paper Address?

Modern high-performance computing systems are becoming increasingly heterogeneous, featuring a combination of powerful CPUs and specialized GPUs. Effectively utilizing these diverse resources for parallel computation presents a significant challenge. The core problem is designing efficient "scheduling strategies" – algorithms that decide which task runs on which processor (CPU or GPU) at any given time. This is complicated by varying processing speeds, memory access patterns, and data dependencies between tasks. Previous work has explored various scheduling approaches, but few have comprehensively compared dynamic scheduling strategies against cost-model-based approaches on combined multi-CPU and multi-GPU architectures. This paper aims to fill that gap by evaluating four distinct scheduling strategies on such systems.

Methods

The authors developed and evaluated four scheduling strategies on top of the XKaapi runtime system:

  • Work Stealing: A classic dynamic approach where idle processors "steal" tasks from busy ones.
  • Data-Aware Work Stealing: An enhancement of work stealing that considers where task data is located to minimize data transfers.
  • Locality-Aware Work Stealing: Another work stealing variant that prioritizes data locality, aiming to reduce cache invalidations.
  • Heterogeneous Earliest-Finish-Time (HEFT): A cost-model-based strategy that estimates task completion times on different processors and assigns tasks to minimize overall finish time.

These strategies were implemented within XKaapi's framework, which supports explicit task parallelism and data-flow dependencies. The HEFT strategy was augmented with a performance model that estimates task execution time and communication costs.

Datasets

The paper does not introduce new datasets. Instead, it uses four established benchmarks to evaluate the scheduling strategies:

  • SAXPY: A simple, highly regular, memory-bound vector operation.
  • Jacobi 2D: An iterative computation commonly used in stencil applications.
  • Cholesky: A dense linear algebra algorithm (specifically, a right-looking implementation).
  • LU: Another dense linear algebra algorithm (using partial pivoting).

These benchmarks were chosen to represent a range of computational characteristics, from highly regular to more irregular with complex data dependencies.

Key Insights and Ideas

  • No One-Size-Fits-All: The study clearly demonstrates that the "best" scheduling strategy is highly dependent on the application's characteristics.
  • Regularity Favors Cost Models: For very regular computations like SAXPY, strategies that consider the raw processing power of resources (like HEFT) tend to perform best, likely because data locality is less of a bottleneck.
  • Irregularity Benefits from Data Locality: For applications with complex data dependencies and irregular access patterns, such as LU factorization with pivoting, strategies that prioritize data locality (locality-aware work stealing) show significant performance improvements.
  • Annotations Matter: The use of task annotations (like SetArch in XKaapi) to guide the scheduler towards specific processor types (e.g., assigning GPU-intensive tasks to GPUs) can significantly boost performance, especially for highly parallel GPU tasks.
  • Work Stealing's Cache Issue: Pure work stealing, while dynamic, can be "cache-unfriendly," leading to lower performance compared to strategies that actively manage data locality.

Key Results

  • SAXPY: The heft+data strategy achieved the highest speedup (around 2.8x) on CPU, suggesting that for highly regular tasks, considering processing power is key.
  • Jacobi 2D: HEFT outperformed other strategies by a significant margin (113.63% better than locality-aware on 4 CPUs-8 GPUs), highlighting its effectiveness for iterative computations where both data locality and processing power are important.
  • Cholesky: The locality-aware strategy showed superior performance on 4-7 GPUs and for larger matrices, outperforming heft+data by up to 4.51%. This indicates its strength in handling complex data dependencies.
  • LU: Similar to Cholesky, locality-aware performed best on 4 GPUs and larger matrices. However, heft+data was better for some cases, particularly on CPU-heavy configurations.
  • Data Footprint: HEFT generally achieved the lowest data footprint for Jacobi 2D, while locality-aware was best for LU. This suggests that strategies focused on data management can significantly reduce memory transfers.
  • Runtime Overhead: XKaapi demonstrated low runtime overhead on both CPUs and GPUs, consistent with previous findings.

Limitations and Future Work

  • Annotation Dependency: The performance of locality-aware work stealing can be significantly enhanced by task annotations. Without them, its awareness of specific architecture efficiencies is limited, which can be a drawback on heterogeneous systems.
  • Model Applicability: The performance models used by HEFT are most effective for regular computations. Applying them to highly irregular applications where workload is unknown until execution remains a challenge.
  • Data-Aware vs. Locality-Aware: The paper notes that data-aware work stealing's performance was not as consistently superior as expected, sometimes performing only slightly better than pure work stealing. This suggests further investigation into its effectiveness for coarse-grained tasks with data-intensive computations.

Future work suggested includes:

  • More extensive experimental evaluations of cost models with different performance schemes (e.g., energy consumption).
  • Developing dynamic scheduling strategies with performance models built at runtime.
  • Further exploring the impact of task annotations on performance.

Summary updated

BibTeX
@article{lima2015design,
  author = {João V. F. Lima and Thierry Gautier and Vincent Danjean and Bruno Raffin and Nicolas Maillard},
  title = {{Design and analysis of scheduling strategies for multi-CPU and multi-GPU architectures}},
  journal = {Parallel Comput.},
  year = {2015},
  doi = {10.1016/j.parco.2015.03.001},
}
Figure