An Efficient OpenMP Loop Scheduler for Irregular Applications on Large-Scale NUMA Machines

Marie Durand, François Broquedis, Thierry Gautier, Bruno RaffinIWOMP 2013 · DOI

TL;DR

This paper introduces "adaptive," a novel OpenMP loop scheduler designed to efficiently handle irregular, memory-bound applications on large-scale NUMA (Non-Uniform Memory Access) architectures. By dynamically adjusting work granularity and leveraging data placement information, "adaptive" significantly outperforms existing schedulers in balancing load and maintaining memory locality, leading to substantial performance improvements.

What Problem Does This Paper Address?

Modern High-Performance Computing (HPC) systems are increasingly characterized by a massive number of cores organized in a hierarchical NUMA architecture. Exploiting these systems to their full potential is a significant challenge for application programmers, especially when dealing with applications that exhibit irregular workloads. These applications make it difficult to achieve both efficient load balancing across many cores and optimal memory locality, which is crucial for performance on NUMA systems. OpenMP, a popular parallel programming standard, offers loop scheduling constructs, but existing options like static and dynamic have limitations. static performs poorly with irregular workloads, while dynamic can disrupt memory locality on NUMA architectures due to its non-deterministic nature. Programmers often struggle to find a portable and efficient way to configure these schedulers and define work granularity.

Methods

The paper proposes a new OpenMP loop scheduler called adaptive. Its core innovation lies in its ability to dynamically adapt the granularity of work within parallel loops. Instead of relying on a fixed chunk_size defined by the programmer, "adaptive" uses a work-stealing approach inspired by Cilk's THE algorithm.

Key aspects of the "adaptive" scheduler:

  • Dynamic Granularity: The scheduler dynamically adjusts the amount of work a thread steals based on the remaining work of its victim. This contrasts with the fixed chunk_size of the dynamic scheduler.
  • Per-Thread Data Structures: Each thread maintains its own data structure representing its assigned range of iterations, avoiding a centralized queue and the associated contention.
  • NUMA-Awareness: The scheduler is extended to consider NUMA architectures. It prioritizes stealing work from threads on the same NUMA node (locality domain) to improve memory locality. If local steals are insufficient, it resorts to stealing from any node.
  • Data Distribution APIs: New runtime APIs are introduced to facilitate explicit data distribution (e.g., bloc and bloc-cyclic) across NUMA nodes, complementing the adaptive scheduling.

Datasets

Not discussed in the paper. The paper evaluates its approach using standard benchmarks and a real-world application.

Key Insights and Ideas

  • Dynamic Granularity is Key for Irregular Workloads: The paper strongly suggests that fixed chunk sizes are a bottleneck for irregular applications on modern architectures. Dynamically adjusting work units on-the-fly is crucial for effective load balancing.
  • Work-Stealing for NUMA Locality: The "adaptive" scheduler's approach of prioritizing local steals on NUMA nodes is a clever way to combine load balancing with memory affinity, a significant challenge in previous OpenMP implementations.
  • The Trade-off Between Static and Dynamic: The paper highlights that static scheduling is good for regular workloads and locality, while dynamic is better for irregular workloads but sacrifices locality. "Adaptive" aims to bridge this gap, offering a compromise that often achieves the best of both worlds.
  • Runtime-Level Solution: By implementing "adaptive" as a runtime extension to libGOMP, the authors provide a solution that doesn't require modifying the compiler or application code significantly, making it more accessible.

Key Results

  • STREAM Benchmark: On memory-bound STREAM kernels, "adaptive" achieved performance comparable to static scheduling, with a slight advantage in some cases, especially when combined with explicit bloc data distribution. The NUMA-aware extension reduced steal operations.
  • K-Means Benchmark: For the irregular K-Means kernel, "adaptive" significantly outperformed static, dynamic, and guided schedulers, particularly for smaller chunk sizes where dynamic load balancing is more effective. It achieved the best performance.
  • PMA Simulation: In the PMA simulation, "adaptive" demonstrated a speed-up of 2.35 over the static scheduler. It provided a good compromise between load balancing and memory locality, outperforming other schedulers even with bloc data distribution.
  • Overhead: The "adaptive" scheduler introduces a small overhead (around 25µs) compared to static, which is attributed to work-stealing operations and termination detection. This overhead is considered acceptable given the performance gains.

Limitations and Future Work

  • Optimization: The authors acknowledge that their current implementation is not as optimized as other libGOMP schedulers and plan to add optimizations like memory alignment and lazy initialization.
  • Task Parallelism: The paper suggests extending the "adaptive" approach to task parallelism, allowing programmers to annotate functions that can generate parallelism on demand by splitting tasks.
  • OpenMP Places: Future work could involve leveraging the "places" concept in the OpenMP standard to provide programmers with more portable ways to control memory allocation on hierarchical architectures.

Summary updated

BibTeX
@inproceedings{durand2013efficient,
  author = {Marie Durand and François Broquedis and Thierry Gautier and Bruno Raffin},
  title = {{An Efficient OpenMP Loop Scheduler for Irregular Applications on Large-Scale NUMA Machines}},
  booktitle = {IWOMP},
  year = {2013},
  doi = {10.1007/978-3-642-40698-0\_11},
}
Figure