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 processor technology shifts toward chip multiprocessors (CMPs), "asymmetric" designs—mixing high-performance (fast) and low-power (slow) cores—have become prevalent. While hardware-efficient, these architectures complicate software task scheduling. Scheduling tasks with dependencies, represented as Directed Acyclic Graphs (DAGs), is NP-hard even on identical processors; adding varying speeds increases complexity significantly.
Most existing research addresses the general case where every processor may have a unique speed. However, real-world hardware often exhibits "limited asymmetry," typically featuring just two speeds (e.g., ARM's big.LITTLE). This paper addresses this gap by developing specialized algorithms for two-speed systems, proving that asymmetry can actually be a performance feature rather than a bottleneck.
Algorithmic Methods
The authors propose three primary algorithmic strategies to optimize for both time and energy.
1. Save-Energy (Preemptive)
This post-processing algorithm takes an existing valid schedule and reassigns tasks to slower processors where possible, provided the overall makespan is not delayed. This approach leverages the fact that energy consumption is a convex function of speed ($c^\alpha$); thus, running a task at a lower speed is significantly more energy-efficient.
2. Remnants (Non-preemptive)
Designed for systems with one fast processor and multiple slow ones, the "Remnants" algorithm greedily assigns the fast processor to critical tasks in each round. The slow processors are then used to maximize parallelism for the remaining tasks (the "remnants").
3. LP-Relaxation & Randomized Rounding
For the general two-speed case ($m_s$ fast cores, $m-m_s$ slow cores), the problem is formulated as a Mixed Integer Program (MIP). By relaxing this into a Linear Program (LP), the authors use randomized rounding to assign tasks to specific speeds, ensuring a high-quality schedule with provable bounds.
Key Insights and Results
A central finding is that asymmetric systems can outperform symmetric ones with the same average speed. Fast cores can "blast through" serial bottlenecks and critical paths that would otherwise limit a symmetric system.
Key results include:
- Time Efficiency: Theorems 3 and 4 formally prove that asymmetric multiprocessors achieve better or equal makespans compared to symmetric counterparts of equal total capacity.
- Near-Optimal Remnants: For the single-fast-processor model, the algorithm achieves a makespan $T \le T_{opt} + 1/s$, where $s$ is the fast processor's speed.
- Improved Approximation: The randomized rounding approach for general DAGs achieves an expected makespan of at most $(3 + o(1)) \cdot T_{opt}$, a significant improvement over the previous factor of 6.
- Energy Optimality: The "Save-Energy" algorithm is proven to reach a state where no further energy can be saved without increasing the makespan.
Conclusion
This work demonstrates that limited asymmetry in multicore systems offers significant opportunities for optimization. While some proofs assume unit task lengths, the core principles provide a robust framework for future heterogeneous architectures. Future work may explore deeper trade-offs between makespan and energy savings, as well as heterogeneity beyond clock speed, such as specialized instruction sets.
Summary updated