Abstract
This paper introduces GEDF-H, a specialized Global Earliest-Deadline-First scheduling algorithm designed for heterogeneous multiprocessors—systems comprising cores with varying processing speeds. While traditional hard real-time scheduling often requires sacrificing significant system capacity (utilization loss) to guarantee deadlines, GEDF-H supports soft real-time (SRT) workloads with zero utilization loss. By implementing a "heavy-to-fast" processor selection rule, the algorithm ensures that high-demand tasks are mapped to high-speed cores, maintaining bounded and predictable response times even when the system is fully loaded.
Introduction
Modern computing architectures, such as ARM’s big.LITTLE, increasingly rely on heterogeneous multiprocessors to balance performance and energy efficiency. However, scheduling real-time tasks on such hardware presents a significant challenge. In Hard Real-Time (HRT) systems, where every deadline is critical, researchers often must under-utilize the processor to provide safety guarantees.
This paper focuses on Soft Real-Time (SRT) systems, where occasional deadline misses are acceptable as long as the total delay (lateness) remains bounded. Standard Global EDF (GEDF) works efficiently on identical cores but fails on heterogeneous systems. Without intelligent processor assignment, a "heavy" task (one requiring more than a single unit-speed core's capacity) might be assigned to a slow core, causing its backlog to grow indefinitely.
The GEDF-H Algorithm
The authors propose GEDF-H (GEDF for Heterogeneous) to address these scheduling failures. The algorithm maintains the standard "earliest deadline first" prioritization for jobs but introduces a critical new rule for processor selection.
The "Heavy-to-Fast" Selection Rule
- Prioritization: Jobs are ordered by their absolute deadlines.
- Utilization Awareness: When a job is ready to run, the algorithm evaluates its utilization (the ratio of its execution time to its period on a reference unit-speed core).
- Mapping: Tasks with high utilization (greater than 1.0) are prioritized for high-speed processors. If all high-speed processors are occupied by "lighter" tasks, GEDF-H will preempt a lighter task, moving it to a slower core to accommodate the heavy task.
To prove that this rule guarantees bounded lateness, the authors use "lag-based analysis." They compare the actual GEDF-H schedule to an ideal Processor Sharing (PS) schedule, where each task receives a constant fraction of processing power proportional to its utilization.
Evaluation and Results
The algorithm was evaluated through extensive simulations of Intel’s QuickIA heterogeneous prototype, which features two unit-speed cores and two double-speed cores (total capacity = 6.0). The researchers tested 10,000 randomly generated task sets with varying periods and utilization levels.
Key Findings
- Zero Utilization Loss: The primary theoretical contribution is the proof that as long as the total task demand ($U_{sum}$) does not exceed the total hardware capacity ($R_{sum}$), the system remains schedulable with bounded delays.
- Predictable Latency: In simulations, the maximum observed response time was typically less than three task periods. For a task with a 100ms period, this translates to a maximum delay of 300ms.
- Scalability: GEDF-H proved robust even as task utilizations increased, effectively eliminating the "bin-packing" inefficiencies associated with partitioned scheduling.
Conclusion
GEDF-H demonstrates that intelligent processor selection is the "secret sauce" for real-time scheduling on heterogeneous hardware. By ensuring heavy tasks are matched with fast processors, the algorithm achieves full hardware utilization without the risk of explosive delays.
Future work will address the practical overheads of task migration between cores, which the current theoretical model assumes to be zero. Additionally, the authors plan to extend the analysis to constrained-deadline tasks and systems involving I/O-induced self-suspensions.
Summary updated