Optimal Dataflow Scheduling on a Heterogeneous Multiprocessor With Reduced Response Time Bounds

Cong Liu, Zheng Dong, Cong Liu 0005, Alan Gatherer, Lee McFearin, Peter Yan, James H. AndersonEcrts 2017 · DOI

TL;DR

This paper introduces a novel analytical framework for scheduling dataflow tasks on heterogeneous multiprocessor systems, proving that the classic Earliest Deadline First (EDF) algorithm is optimal for minimizing response times. The proposed method significantly reduces worst-case response time bounds compared to existing techniques, making it suitable for real-time industrial applications.

What Problem Does This Paper Address?

Many modern systems, like those in cellular networks, process continuous data streams (dataflows) that require fast and predictable responses (soft real-time requirements). These systems often use heterogeneous computing platforms with specialized processors (CPUs, DSPs, etc.) where tasks have fixed affinities to certain processor types. A major challenge is developing scheduling algorithms and analysis techniques that can guarantee bounded response times for these dataflow tasks on such complex hardware, while maximizing resource utilization. Existing approaches often struggle with the interplay of task dependencies, heterogeneous resources, and the need for provable real-time guarantees.

Methods

The core contribution is a new set of schedulability analysis techniques for the Earliest Deadline First (EDF) scheduling algorithm on heterogeneous multiprocessors. The authors extend EDF to handle dataflow tasks with pre-defined resource affinities. The analysis breaks down the problem by first bounding the "PS-induced tardiness" (tardiness arising from the processor sharing model) and then the "EDF-induced tardiness" (tardiness due to EDF's scheduling decisions compared to an ideal processor sharing model). This is achieved through a series of lemmas and theorems that carefully analyze the workload, dependencies, and potential delays introduced by competing tasks. The analysis leverages concepts like "lag" (the difference in processing time allocated between a processor sharing schedule and an EDF schedule) to derive bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic workloads for experiments.

Key Insights and Ideas

  • EDF is Optimal for Heterogeneous Dataflows: The paper proves that EDF, a well-established real-time scheduler, is not only capable of scheduling dataflow tasks on heterogeneous platforms but is also optimal in terms of system utilization, meaning it can handle the maximum possible workload without capacity loss.
  • Decomposing Tardiness: The novel approach of separating tardiness into "PS-induced" and "EDF-induced" components simplifies the analysis and allows for more precise bounding.
  • Lag as a Key Metric: The concept of "lag" is crucial for quantifying the difference in resource allocation between an ideal processor sharing model and the actual EDF schedule, which directly relates to tardiness.
  • Addressing Dependencies: The analysis carefully accounts for the dependencies between subtasks within a dataflow task, which is a significant challenge in heterogeneous systems.

Key Results

  • The proposed analytical techniques provide provably bounded response times for dataflow tasks scheduled under EDF on heterogeneous multiprocessors.
  • Experiments with synthetic workloads demonstrated that the derived response time bounds are significantly reduced compared to existing state-of-the-art soft real-time analysis techniques, achieving an average reduction of 68%.
  • The analytical bounds were shown to be reasonably small and "tight" in practice, closely matching observed runtime response times in many scenarios.

Limitations and Future Work

  • Preemption Assumption: The analysis assumes job preemption and migration are allowed. The authors note that enforcing non-preemptive execution on certain processor types is a direction for future work.
  • Synthetic Workloads: While the experiments used a wide range of parameters to mimic industrial scenarios, they were based on synthetic workloads. Future work could involve validation on real-world industrial systems.
  • Specific Processor Affinities: The analysis is tailored to tasks with pre-defined affinities to specific processor types. Extending this to more flexible or dynamic affinity models could be a future research direction.

Summary updated

BibTeX
@inproceedings{liu2017optimal,
  author = {Cong Liu and Zheng Dong and Cong Liu and Alan Gatherer and Lee McFearin and Peter Yan and James H. Anderson},
  title = {{Optimal Dataflow Scheduling on a Heterogeneous Multiprocessor With Reduced Response Time Bounds}},
  booktitle = {Ecrts},
  year = {2017},
  doi = {10.4230/lipics.ecrts.2017.15},
}
Figure