Energy and Time Efficient Scheduling of Tasks with Dependencies on Asymmetric Multiprocessors

Ioannis Chatzigiannakis, Georgios Giannoulis, Paul G. Spirakis

Abstract

In this work we study the problem of scheduling tasks with dependencies in multiprocessor architectures where processors have different speeds. We present the preemptive algorithm "Save-Energy" that given a schedule of tasks it post processes it to improve the energy efficiency without any deterioration of the makespan. In terms of time efficiency, we show that preemptive scheduling in an asymmetric system can achieve the same or better optimal makespan than in a symmetric system. Motivited by real multiprocessor systems, we investigate architectures that exhibit limited asymmetry: there are two essentially different speeds. Interestingly, this special case has not been studied in the field of parallel computing and scheduling theory; only the general case was studied where processors have $K$ essentially different speeds. We present the non-preemptive algorithm ``Remnants'' that achieves almost optimal makespan. We provide a refined analysis of a recent scheduling method. Based on this analysis, we specialize the scheduling policy and provide an algorithm of $(3 + o(1))$ expected approximation factor. Note that this improves the previous best factor (6 for two speeds). We believe that our work will convince researchers to revisit this well studied scheduling problem for these simple, yet realistic, asymmetric multiprocessor architectures.

Introduction

As semiconductor manufacturing approaches thermal and power limits, the industry has shifted toward asymmetric architectures. Modern chips, such as ARM’s big.LITTLE or Intel’s hybrid designs, combine a small number of high-performance "big" cores with numerous energy-efficient "small" cores. While this hardware transition is well underway, classical scheduling theory has largely focused on symmetric systems where all processors are identical.

Existing research for systems with $K$ different speeds often fails to provide tight performance guarantees for the specific, "limited asymmetry" case of just two speeds (fast and slow). This paper addresses the challenge of mapping a Directed Acyclic Graph (DAG) of tasks—where dependencies dictate execution order—onto these mixed resources to minimize both the total execution time (makespan) and energy consumption.

Algorithmic Framework

Save-Energy (Preemptive)

The "Save-Energy" algorithm is a post-processing technique designed to enhance the energy efficiency of an existing valid schedule. It operates by identifying "slack" or idle periods in the schedule and migrating tasks from fast processors to slower ones. Since energy consumption is typically a convex function of processor speed, executing tasks at lower speeds whenever possible significantly reduces power usage without extending the total makespan.

Pseudocode for the Save-Energy algorithm, illustrating the iterative process of filling idle 'holes' in lower-speed processors to optimize energy efficiency.

Remnants (Non-preemptive)

For architectures featuring exactly one fast processor and multiple slow ones, the authors propose the "Remnants" algorithm. This greedy approach prioritizes the most critical tasks—those on the longest dependency chains—for the fast core. The remaining tasks, or "remnants," are then distributed across the slow cores to maximize parallel execution.

LP-Relaxation and Randomized Rounding

For the general two-speed case with multiple fast and slow cores, the problem is formulated as a Mixed Integer Program (MIP). By relaxing this into a Linear Program (LP), the authors find an ideal fractional solution. They then employ a randomized rounding strategy to assign tasks to specific speeds. This method allows for a more nuanced distribution of workload that accounts for both task dependencies and processor capabilities.

Visualization of the scheduling rounds used in the refined analysis of task assignment, where tasks from different lists are processed across successive rounds.

Key Insights and Results

A central finding of this work is that asymmetry is a performance feature. The authors prove that an asymmetric system can achieve a superior optimal makespan compared to a symmetric system with the same average speed. Fast cores are uniquely capable of accelerating serial bottlenecks—long chains of dependencies—that would otherwise stall a uniform system.

The paper's primary results include:

  • Improved Approximation: The authors achieve an expected approximation factor of $(3 + o(1))$ for non-preemptive scheduling on two-speed systems, a significant leap from the previous best factor of 6.
  • Near-Optimal Performance: In the single-fast-processor scenario, the Remnants algorithm yields a makespan $T \leq T_{opt} + 1/s$, where $s$ is the fast processor's speed.
  • Energy Optimality: The "Save-Energy" algorithm is proven to reach a state where no further energy can be saved without negatively impacting the makespan.

Conclusion and Future Work

While the current analysis provides strong bounds, it primarily assumes unit task lengths. Future research will focus on extending these refined bounds to tasks of arbitrary lengths without significantly increasing graph complexity. Additionally, the authors aim to explore the "Pareto front" of the energy-time trade-off, helping designers determine the optimal balance between performance gains and energy savings. Further extensions may include more complex forms of heterogeneity, such as specialized hardware accelerators.

Summary updated

Abstract

In this work we study the problem of scheduling tasks with dependencies in multiprocessor architectures where processors have different speeds. We present the preemptive algorithm "Save-Energy" that given a schedule of tasks it post processes it to improve the energy efficiency without any deterioration of the makespan. In terms of time efficiency, we show that preemptive scheduling in an asymmetric system can achieve the same or better optimal makespan than in a symmetric system. Motivited by real multiprocessor systems, we investigate architectures that exhibit limited asymmetry: there are two essentially different speeds. Interestingly, this special case has not been studied in the field of parallel computing and scheduling theory; only the general case was studied where processors have $K$ essentially different speeds. We present the non-preemptive algorithm ``Remnants'' that achieves almost optimal makespan. We provide a refined analysis of a recent scheduling method. Based on this analysis, we specialize the scheduling policy and provide an algorithm of $(3 + o(1))$ expected approximation factor. Note that this improves the previous best factor (6 for two speeds). We believe that our work will convince researchers to revisit this well studied scheduling problem for these simple, yet realistic, asymmetric multiprocessor architectures.
BibTeX
@misc{chatzigiannakis2008energy,
  author = {Ioannis Chatzigiannakis and Georgios Giannoulis and Paul G. Spirakis},
  title = {{Energy and Time Efficient Scheduling of Tasks with Dependencies on Asymmetric Multiprocessors}},
  year = {2008},
  eprint = {0804.4039},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0804.4039},
}
Figure