Modern embedded control applications in Cyber-Physical Systems (CPSs) often have complex inter-dependencies in their functionalities and are hence represented as Directed-Acyclic Task Graphs (DTGs). To meet complex performance as well as deployment-related logistic constraints, these applications may need to be implemented on a distributed and heterogeneous platform. Many-a-times, it becomes necessary to dynamically run a new application like say, an alarm service routine , on an already operational platform, where pre-existing workloads consisting of other application tasks along with their messages are running. However, although there is a significant body of literature dealing with the static scheduling of DTGs on different types of platforms, to the best of our knowledge, there does not exist any prominent work for the dynamic scheduling of dynamically arriving DTG applications on an already preoccupied platform. The primary reason for this dearth in strategies may be attributed to the inherent design as well as computational complexity associated with the dynamic inclusion of a new DTG application by effectively reclaiming the free slots within an already existing schedule. While delivering quick response times to the dynamically arrived application, the newly generated schedule must also ensure that it does not ever cause deadline violations for the already running applications . This work proposes a novel makespan-minimizing scheduling algorithm called DTG Scheduler for Preloaded Platforms ( DSPP ). DSPP is an efficient list-based heuristic strategy for co-scheduling the tasks as well as the inter-task messages of a DTG structured application on preloaded heterogeneous processing elements, interconnected via shared buses. The effectiveness of DSPP has been meticulously examined through simulation, employing benchmark DTGs for evaluation. The conducted experiments reveal the generic efficacy of DSPP across an extensive set of considered test case scenarios. Extensive simulation results show that DSPP can achieve up to ∼13% reduction in makespan in the best case and ∼10% on average, outperforming existing state-of-the-art methods.

Many modern Cyber Physical Systems (CPSs) are composed of multiple independent periodically executing real-time control tasks having inter-dependent component sub-tasks. Each such control task is therefore usually represented asDirected-acyclic Task Graphs(DTGs). These CPSs are often distributed in nature and are quickly shifting from homogeneous to heterogeneous processing platforms in order to meet ever increasing demands for performance and energy savings, within limited resource budgets. In spite of the practical relevance of the problem in today's CPS design scenario, very few research works in literature have tried to address this due to its inherent computational as well as design complexity. This work endeavors to solve the problem of co-scheduling a set of periodic real-time applications each modelled as an independent DTG, to be executed on a distributed platform consisting of heterogeneous processors communicating using shared buses. Assuming the processing platform to be DVFS (Dynamic Voltage Frequency Scaling) enabled, we attempt to minimize dynamic energy dissipation associated with the execution of all DTGs over an hyperperiod$\mathcal {H}$while ensuring that no DTG instance within$\mathcal {H}$misses its deadline. The problem has first been formally represented as a constraint optimization problem. However, an optimal solution using standard solvers become prohibitively compute as well as memory intensive and doesn't scale even for moderate problem sizes. Hence, in this work, we attempt to develop a three-phase list-based hierarchical scheduling algorithm calledSlack Aware Frequency Level Allocator(SAFLA). The efficacy ofSAFLAhas been critically evaluated through simulation using benchmark DTGs.

IPPTS(Improved Predict Priority Task Scheduling) is a list scheduling algorithm that schedules task graphs on fully connected heterogeneous distributed systems, with an objective of minimizing the overall makespan (i.e., schedule length). With respect to the literature on list scheduling techniques for task graphs,IPPTSimproves the task prioritization by considering the“out-degree”of a task. However, we have observed that the IPPTS algorithm contains an ambiguity which introducesthe possibility of assigning higher priority to a task compared to its predecessors in a task graph. This priority inversionmay lead to the generation of an incorrect scheduledue to the violation of precedence-constraints among tasks. In this note, we first highlight this issue using a counter example. Then, we discuss two possible ways to fix the ambiguity in the algorithm.

The dynamic partial reconfiguration (DPR) feature offered by modern FPGAs provides the flexibility of adapting the underlying hardware according to the needs of a particular situation at runtime, in response to application requirements. In recent times, DPR along with drastically reduced reconfiguration overheads has allowed the possibility of scheduling multiple real-time applications on FPGA platforms. However, in order to effectively harness the computation capacity of an FPGA floor, efficient techniques which can schedule real-time applications over both space and time are required. It may be noted that safety-critical systems often require resource-optimal solutions to reduce size, weight, cost and power consumption of the system. However, the scheduling of real-time tasks on FPGAs in the presence of non-negligible reconfigurationlcontext-switching overheads requires careful exploration of the state space which often makes it prohibitively expensive to be applied on-line. Hence, off-line formal approaches are often preferred in the design of reconfiguration controllers (i.e., schedulers) that are correct-by-construction as well as optimal in terms of usage of resources. In this paper, we propose a formal scheduler synthesis framework that generates an optimal scheduler for a set of non-preemptive periodic real-time tasks executing on a FPGA platform. We show the practical viability of our proposed framework by synthesizing schedulers for real-world benchmark applications and implementing them on FPGAs.

Demands for high performance as well as reliability within stringent resource budgets are driving a shift from homogeneous to heterogeneous processing platforms for the implementation of today’s cyber-physical systems (CPSs). These CPSs are typically represented as directed-acyclic task graphs (DTGs) due to the complex interactions between their functional components which are often distributed in nature. This work deals with the problem of scheduling a CPS modeled as DTG. First, we present an optimal solution using integer linear programming (ILP) for the DTGs, to be executed on distributed heterogeneous processors which are interconnected via shared buses. However, this ILP-based optimal solution exhibits high computational complexity and does not scale for moderately large problem sizes. Hence, we propose a low-overhead heuristic algorithm called the contention cognizant task and message scheduler (CC-TMS), which is able to produce satisfactorily efficient as well as fast solutions within a reasonable time. The efficiency of the proposed scheme has been extensively evaluated through simulation-based experiments using benchmark DTGs. Through the case study of a real-worldautomotive traction controller, we demonstrate the practical applicability of our proposed scheme.

Continuous demands for higher performance and reliability within stringent resource budgets is driving a shift from homogeneous to heterogeneous processing platforms for the implementation of today’s cyber-physical systems (CPSs). These CPSs are typically represented as Directed-acyclic Task Graph (DTG) due to the complex interactions between their functional components that are often distributed in nature. In this article, we consider the problem of scheduling a real-time application modelled as a single DTG, where tasks may have multiple implementations designated as quality-levels, with higher quality-levels producing more accurate results and contributing to higher rewards/Quality-of-Service for the system. First, we introduce an optimal solution using Integer Linear Programming (ILP) for a DTG with multiple quality-levels, to be executed on a heterogeneous distributed platform . However, this ILP-based optimal solution exhibits high computational complexity and does not scale for moderately large problem sizes. Hence, we propose two low-overhead heuristic algorithms called Global Slack Aware Quality-level Allocator ( G-SLAQA ) and Total Slack Aware Quality-level Allocator ( T-SLAQA ), which are able to produce satisfactorily efficient as well as fast solutions within a reasonable time. G-SLAQA , the baseline heuristic, is greedier and faster than its counter-part T-SLAQA , whose performance is at least as efficient as G-SLAQA . The efficiency of all the proposed schemes have been extensively evaluated through simulation-based experiments using benchmark and randomly generated DTGs. Through the case study of a real-world automotive traction controller , we generate schedules using our proposed schemes to demonstrate their practical applicability.

Real-time control applications are highly parallelizable and can be used to effectively harness the capacity of a given computing platform when appropriately scheduled. Given a multicore platform for executing a set of parallelizable applications, it is necessary to ensure proper functioning of the system even in the presence of transient processor faults. However, most existing scheduling approaches for parallel applications have been heuristic schemes which are often based only on the satisfaction of a set of sufficiency conditions and cannot take into consideration of all necessary schedulability requirements. Consequently, such schemes lead to suboptimal usage of resources resulting in higher design costs. Formal model-based safe design methodologies such as supervisory control are often desirable in the design of correct-by-construction fault-tolerant schedulers. This article proposes a supervisory control-based fault-tolerant scheduler synthesis scheme for real-time tasks modeled as precedence-constrained task graphs, executing on multicores. Further, we devise search strategies to obtain schedules that 1) maximize fault-tolerance and 2) minimize peak-power (MPP) dissipation. Conducted experiments using real-world benchmarks reveal the efficacy of our scheme.

Real-time applications in today's distributed cyber-physical control systems are often represented as Precedence-constrained Task Graphs (PTGs) and increasingly implemented on heterogeneous platforms to cater to their high performance demands. Optimal scheduling solutions for such systems can provide advantages in terms of performance, reliability, cost etc. However, existing research works dealing with the optimal scheduling of PTGs, typically assume platforms consisting of homogeneous processing elements which interact through a fully connected network of homogeneous communication channels. In this work, we propose an Integer Linear Programming based optimal solution strategy for scheduling PTGs executing on a distributed platform composed of heterogeneous processing elements and inter-connected through a set of heterogeneous shared buses. Through the real-world case study of an automotive cruise controller, we generate an optimal schedule using our proposed scheme in order to demonstrate its generic applicability. Conducted experiments on benchmark PTGs reveal the practical efficacy of our scheme.

Safety-critical systems implemented on multicore platforms need to satisfy stringent power dissipation constraints such as thermal design power (TDP) thresholds used by chip manufacturers. Power dissipation beyond TDP may trigger dynamic thermal management (DTM) in order to ensure thermal stability of the system. However, the application of DTM makes the system susceptible to higher unpredictability and performance degradations for real-time tasks. This paper proposes a formal scheduler synthesis framework that guarantees adherence to a system level peak power constraint while allowing optimal resource utilization in multicores. Our proposed framework makes use of supervisory control of timed discrete event systems as the underlying formalism. All steps starting from individual models to construction of the scheduler have been implemented through binary decision diagram based symbolic computation, so that the state-space complexity associated with the framework may be controlled. Furthermore, the synthesis framework has been extended to handle tasks with phased execution behavior. Conducted experiments have shown promising results and indicate to the practical efficacy of our approach.

HTTP adaptive streaming (HAS) which provides the flexibility of video bit-rate adjustments, is becoming the de facto framework for live and on-demand video streaming services. The flexibility of HAS is further empowered by the scalable video coding (SVC) technique which allows low overhead quality upgradations of transmitted video segments. In this paper, we present a client-side finite-state machine (FSM) supported quality of experience (QoE) centric video bit-rate adaptation and management mechanism. The proposed strategy simultaneously manages three important QoE verticals: 1) providing stutter-free video viewing experience; 2) minimizing flickers in video outputs by controlling and smoothing the rates of encoding quality switches over time; and 3) maximizing aggregate video quality over a video playout session. Based on careful consideration of these QoE verticals, the management policy dynamically decides whether to download a new segment or upgrade the quality of an already downloaded segment in the playout buffer. We have implemented and evaluated the performance of our proposed framework in a multi-client SVC video steaming test-bed. Conducted experiments using real-world network traces reveal that the proposed strategy is able to outperform other state-of-the-art adaptive streaming techniques and deliver satisfactory QoE even in the face of highly varying channel conditions.

Development of efficient resource allocation strategies for real-time tasks on heterogeneous platforms has traditionally proved to be a challenging as well as a computationally expensive problem. However, strategies which can efficiently schedule real-time task sets on generic heterogeneous platforms having an arbitrary number of processor types, are rare. Most of the existing strategies are oriented towards systems with restricted number of processing core types. Hence, this paper proposes an effective low-overhead heuristic approach called COST, for scheduling a set of periodic tasks executing on a heterogeneous multi-core system. The proposed strategy works in three-phases namely, Core Clustering, Task Partitioning, and Task Scheduling. The Core Clustering step attempts to combine the available processing cores into a group of clusters. Each cluster consists of two cores and a disjoint subset of the given task set is assigned to it. The tasks assigned to a cluster are then allocated to the processing cores of the cluster and scheduled in a fair manner. Experimental studies show that our proposed scheme provides high resource utilisation with satisfactory acceptance ratios for a wide-range of task sets.

Real-time systems are increasingly being implemented on heterogeneous multi-core platforms to efficiently cater to their diverse and high computation demands. Over the years, researchers have developed mechanisms to efficiently schedule tasks on homogeneous multi-cores such that all tasks meet their execution and deadline requirements. However, devising an efficient scheduling strategy for real-time tasks on heterogeneous platforms has proved to be a challenging as well as computationally expensive problem. Today, there is a severe dearth of low-overhead techniques towards real-time scheduling on heterogeneous platforms. Hence, we propose an effective low-overhead heuristic approach for scheduling a set of periodic tasks executing on a heterogeneous multi-core platform. Employing the concept of deadline partitioning to obtain a set of discrete time slices, we propose a scheme to efficiently schedule tasks over these time slices while incurring low and bounded number of migrations. Conducted experiments have shown promising results and indicate to the practical efficacy of our approach.

Safety-critical real-time systems must meet stringent timing and fault-tolerance requirements. This article proposes a methodology for synthesizing an optimal preemptive multiprocessor aperiodic task scheduler using a formal supervisory control framework. The scheduler can tolerate single/multiple permanent processor faults. Further, the synthesis framework has been empowered with a novel BDD-based symbolic computation mechanism to control the exponential state-space complexity of the optimal exhaustive enumeration-oriented synthesis methodology.