What Makes Affinity-Based Schedulers So Efficient ?

Olivier Beaumont, Loris Marchal2013

TL;DR

This paper investigates why affinity-based scheduling strategies, which leverage data locality and resource characteristics, are so effective for complex computational tasks on modern supercomputers. The authors propose and analyze novel dynamic scheduling algorithms for matrix multiplication and outer products, demonstrating that theoretical models can accurately predict performance and guide strategy selection, leading to significantly reduced communication overhead.

What Problem Does This Paper Address?

Modern supercomputers are becoming increasingly massive and heterogeneous, featuring a vast number of processing units (CPUs, GPUs) and complex network topologies. This scale and complexity make it extremely difficult to predict the execution time of tasks and the overall performance of applications. Traditional static scheduling approaches, which pre-assign tasks to processors, struggle to cope with this unpredictability and the potential for hardware failures. Consequently, dynamic scheduling strategies, which make decisions at runtime, have gained prominence. These strategies often rely on information like data location and processor availability. However, a deep theoretical understanding of why certain dynamic strategies, particularly those that consider "affinity" (i.e., the relationship between tasks and resources, especially data locality), perform so well has been lacking. This paper aims to bridge this gap by providing a rigorous analytical framework for affinity-based scheduling in the context of fundamental linear algebra operations.

Methods

The core of this paper lies in developing and analyzing dynamic scheduling strategies for two fundamental linear algebra kernels: the outer product of two vectors and matrix multiplication.

  • Dynamic Strategies: The authors propose several dynamic scheduling strategies. These range from simple random allocation (RANDOMOUTER, RANDOMMATRIX) to more sophisticated "data-aware" or "affinity-based" strategies. The key idea behind the advanced strategies (e.g., BASICOUTER, BASICMATRIX) is to exploit the data already present on a processor. When a processor becomes available, instead of fetching new data randomly, it prioritizes tasks that can be computed using data it already possesses, or data that is readily available. This minimizes data movement.
  • Theoretical Analysis: A significant contribution is the development of analytical models for these strategies. The authors use Ordinary Differential Equations (ODEs) to model the continuous evolution of the system's state (e.g., the fraction of processed tasks or data known by a processor) over time. This "mean-field" approach allows for the theoretical prediction of communication volume and task completion times.
  • Switching Strategies: To further optimize performance, the paper explores strategies that dynamically switch between a data-aware approach and a simpler random approach when the number of remaining tasks becomes small. This is guided by a parameter $\beta$, which is analyzed to determine the optimal switching point.
  • Simulation: The theoretical models are validated through extensive simulations on heterogeneous platforms. The performance of various strategies is compared, and their communication amounts are normalized against a theoretical lower bound.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation using synthetic workloads representing outer products and matrix multiplications.

Key Insights and Ideas

  • Affinity is Key: The most striking insight is the confirmation that affinity-based strategies, which prioritize tasks that can leverage existing data on a processor, significantly outperform simple random scheduling. This is crucial for reducing communication overhead, a major bottleneck in large-scale systems.
  • Theoretical Models Predict Reality: The paper demonstrates that analytical models based on ODEs can accurately capture the dynamic behavior of these scheduling strategies. This is a powerful result, as it allows for performance prediction and strategy tuning without extensive empirical testing.
  • Tuning with Theory: The theoretical analysis provides a mechanism to inject static knowledge (like processor speeds and data distribution) into dynamic schedulers. This allows for intelligent decisions, such as when to switch strategies, leading to better overall performance.
  • Complexity vs. Performance Trade-off: More sophisticated strategies (like DYNBLOCKSOUTER/DYNBLOCKSMATRIX) offer superior communication reduction but come with increased scheduling overhead. The paper quantifies this trade-off, showing that for very large problems, the benefits of reduced communication outweigh the scheduling cost.

Key Results

  • Significant Communication Reduction: Affinity-based strategies like DYNBLOCKSOUTER and DYNBLOCKSMATRIX achieved communication amounts close to the theoretical lower bound, often less than twice the bound, while simple random strategies were orders of magnitude worse.
  • Model Accuracy: The theoretical analysis of the BASICOUTER2 and BASICMATRIX2 strategies closely matched simulation results, validating the ODE-based modeling approach.
  • Performance Gains: For outer product strategies, DYNBLOCKSOUTER performed extremely well, achieving communication amounts significantly lower than other strategies, especially when the number of processors or problem size was large.
  • Scheduling Overhead: While advanced strategies like DYNBLOCKSMATRIX were highly effective in reducing communication, they incurred higher scheduling times (e.g., up to 808 seconds for N/l=1000, p=1000 in the outer product case). However, this overhead was deemed acceptable for very large-scale computations.

Limitations and Future Work

  • Analytical Models for All Strategies: The authors acknowledge that analytical models were developed for specific strategies (BASICOUTER, BASICMATRIX) and suggest extending this to all proposed dynamic schedulers.
  • Data and Precedence Dependencies: The current analysis primarily focuses on data locality. Future work could extend the models to handle applications with complex data dependencies and precedence constraints.
  • Other Linear Algebra Kernels: The paper successfully analyzes outer product and matrix multiplication. Extending this work to other dense linear algebra kernels like LU and QR factorization is proposed as a promising next step.
  • Practical Implementation: While the theoretical analysis is strong, further research into the practical implementation and fine-tuning of these strategies in real-world runtime systems would be beneficial.

Summary updated

Abstract

The tremendous increase in the size and heterogeneity of supercomputers makes it very difficult to predict the performance of a scheduling algorithm. Therefore, dynamic solutions, where scheduling decisions are made at runtime have overpassed static allocation strategies. The simplicity and efficiency of dynamic schedulers such as Hadoop are a key of the success of the MapReduce framework. Dynamic schedulers such as StarPU, PaRSEC or StarSs are also developed for more constrained computations, e.g. task graphs coming from linear algebra. To make their decisions, these runtime systems make use of some static information, such as the distance of tasks to the critical path or the affinity between tasks and computing resources (CPU, GPU,...) and of dynamic information, such as where input data are actually located. In this paper, we concentrate on two elementary linear algebra kernels, namely the outer product and the matrix multiplication. For each problem, we propose several dynamic strategies that can be used at runtime and we provide an analytic study of their theoretical performance. We prove that the theoretical analysis provides very good estimate of the amount of communications induced by a dynamic strategy, thus enabling to choose among them for a given problem and architecture.
BibTeX
@misc{beaumont2013what,
  author = {Olivier Beaumont and Loris Marchal},
  title = {{What Makes Affinity-Based Schedulers So Efficient ?}},
  year = {2013},
}

Loading related content...

Figure