Dynamic scheduling techniques for adaptive applications on real-time embedded systems

Abstract

The ability to trade off Quality-of-Service (QoS) with resources on modern embedded platforms makes adaptive applications an interesting value proposition. Applying dynamic scheduling for such applications will bring further flexibility for meeting the overall system's performance goals. However, the state-of-the-art dynamic scheduling strategies, in general, either are incapable of QoS optimizations, or ignore the increasing platform-introduced impacts that may substantially deteriorate the scheduling performance.

This thesis focuses on the design of dynamic scheduling algorithms for adaptive applications, with the goal of maximizing QoS based on the runtime slack reclamation and re-distribution. For the QoS modeling, both the Imprecise-Computation (IC) model and a proposed generic model, are validated and studied. The algorithms are built upon increasingly complicated assumptions, namely scheduling (1) IC-modeled tasks on uni-processor systems, (2) dependent IC-modeled tasks on homogeneous multiprocessors, and (3) a generic QoS model on heterogeneous multiprocessors considering the leakage energy and QoS deterioration due to inter-processor communications.

First, a dynamic algorithm for scheduling IC tasks mapped on a single processor is presented. We prove that the QoS maximization can be achieved by employing the intra-task Dynamic Voltage Scaling (DVS). The derived theorem leads to the convenient selection of a slack receiver, by comparing the QoS gradients of the IC-modeled receivers. A Gradient Curve Shifting (GCS) approach is proposed to make the theorem applicable to both linear and concave QoS models.

Second, we extend to scheduling IC tasks on homogeneous multiprocessors. Although it is possible to apply the uni-processor algorithm to dedicate the whole slack to only one receiver, we consider all parallel receivers in multiprocessors, and optimally derive the slack distribution strategy that outperforms the uniprocessor-based algorithm. Beyond that, a heuristic slack receiver selection strategy is presented to select the best receiver set that potentially produces the maximal QoS.

Third, we extend the idealized IC model by proposing a more practical generic QoS model, and present a dynamic scheduling algorithm targeting heterogeneous multiprocessors, where each processor has its individual frequency and energy characteristics. We propose a Guided-Search algorithm that efficiently determines the receiver execution speed, in order to achieve the QoS maximization for the generic model. The receiver selection methodology is also designed for the generic model. Moreover, an enhancement on the scheduling performance by taking care of slack losses due to inter-processor communications is reported.

Finally, to make our work self-contained, we develop a static scheduling algorithm targeting inter-processor communications on Network-on-Chip (NoC) architectures. While our dynamic approaches are assumed to adopt any static scheduling results, the proposed method is a unified approach that optimally achieves the computation element mapping, the communication path decision, and the execution time scheduling.

We support our proposed algorithms by evaluating the performance of scheduling numerous synthesized task sets and realistic adaptive applications. The evaluation software, employing cycle-accurate architecture and NoC simulators, is also introduced in detail.