Vehicle platooning has emerged as a prominent Intelligent Transportation Systems (ITS) application due to its promise toward enabling high-speed movement of Connected Autonomous Vehicle (CAV) fleets in a close formation. This close formation is usually associated with stringent constraints such as a short and strictly bounded safety gaps between consecutive platoon vehicles. In order to meet these stringent specifications, CAV fleets critically depend on the underlying platoon communication protocols, which are vulnerable to various types of attacks that may be launched by an attacker. For instance, a common attack, namely False Data Injection (FDI) attack, can potentially disrupt and destabilize a platoon’s close formation by causing collisions among platoon vehicles, or causing potential traffic disruption due to platoon slowdown, thus making the platoon unsafe . One mechanism for mitigating an FDI attack can be the placement of uniformly separated Road-Side Units (RSUs) along the path of a vehicle platoon. The RSUs can act as the root of trust to detect and mitigate attack attempts. However, frequent RSU placements over a path can lead to prohibitive deployment costs. In this work, we first formulate a constraint optimization problem which aims to minimize RSU deployments along a path (by maximizing the inter-RSU distance), while ensuring that the safety of a platoon under a given FDI attack scenario is guaranteed. Our methodology outputs an RSU placement solution such that the worst-case attack (which spans the entire inter-RSU blind spot) is unable to violate the safety guarantee of the platoon. A platoon’s robustness, in the presence of state-of-the-art attack detectors and trusted RSUs, is defined by its resilience against possible stealthy FDI attacks in the inter-RSU blind spots. We leverage this concept and propose a novel SMT-based hierarchical solution strategy. Our method iteratively hypothesizes an inter-RSU distance and formally checks the safety of the resulting platooning solution against possible attack scenarios. The process terminates when the RSU deployment spacings can no longer be relaxed without violating safety constraints. We motivate this work through simulations in PLEXE. Our experimental results demonstrate that the method is able to minimize RSU deployments while preserving safety, under diverse real-world highway platooning scenarios.

Autonomous Delivery Vehicles (ADVs) are increasingly used for transporting goods in 5G network-enabled smart factories, with the compute-intensive localization module presenting a significant opportunity for optimization. We propose ACCESS-AV , an energy-efficient Vehicle-to-Infrastructure (V2I) localization framework that leverages existing 5G infrastructure in smart factory environments. By opportunistically accessing the periodically broadcast 5G Synchronization Signal Blocks (SSBs) for localization, ACCESS-AV obviates the need for dedicated Roadside Units (RSUs) or additional onboard sensors to achieve energy efficiency as well as cost reduction. We implement an Angle-of-Arrival (AoA)-based estimation method using the Multiple Signal Classification (MUSIC) algorithm, optimized for resource-constrained ADV platforms through an adaptive communication-computation strategy that dynamically balances energy consumption with localization accuracy based on environmental conditions such as Signal-to-Noise Ratio (SNR) and vehicle velocity. Experimental results demonstrate that ACCESS-AV achieves an average energy reduction of 43.09% compared to non-adaptive systems employing AoA algorithms such as vanilla MUSIC, ESPRIT, and Root-MUSIC. It maintains sub-30 cm localization accuracy while also delivering substantial reductions in infrastructure and operational costs, establishing its viability for sustainable smart factory environments.

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.

Cyber-Physical Systems (CPSs) operating in remote or field scenarios often face limited local processing capacity, necessitating complex real-time monitoring and control via remote processing through mobile edge networks, satellite systems, or UAVs. With recent advancements, UAVs are increasingly being favored for such applications, particularly in isolated areas beyond edge or satellite network coverage. This paper presents a unified UAV scheduling and routing framework for executing geographically distributed real-time CPS tasks under both periodic and aperiodic arrival models. We address the challenge of minimizing the number of UAVs required while ensuring strict adherence to task deadlines across diverse temporal and spatial settings. At first, we propose an efficient heuristic strategy called UAV Scheduling and Routing Algorithm for Real-time Tasks - Periodic Arrivals (USRART-P), which decomposes applications into task instances and sequentially creates per-UAV routes and schedules within a hyperperiod, maximizing the number of task instances each UAV can cover while meeting deadlines. Adapting to this framework, we develop two additional variants to handle aperiodic CPS tasks: USRART-SA for Synchronous Aperiodic Arrivals (common arrival time, distinct deadlines) and USRART-AA for Asynchronous Aperiodic Arrivals (distinct but known arrival times and deadlines). For the case of periodic tasks, we frame the problem as a constraint optimization formulation which aims to minimize the number of UAVs that are required to generate static hyperperiodic travel routes with task execution schedules for all UAVs, and discuss how the formulation can be adapted for aperiodic tasks. Solution to this formulation using standard off-the-shelf solvers achieves optimality but incurs high computational overheads. Through extensive simulations, we show that USRART exhibits high performance across diverse operational scenarios, varying task distributions, execution demands, and spatial layouts. The results emphasize USRART’s flexibility and effectiveness in real-world UAV-based CPS scenarios, especially in environments with limited resources and infrastructure.

The integration of Quality of Service (QoS)-specific communications and Multi-access Edge Computing (MEC) in advanced 5G networks is driving the emergence of innovative applications and business models. An important outcome this development is the ability to execute real-time automated monitoring and control tasks as edge services on MEC servers. Such real-time control applications, which are often modeled as Directed Acyclic Graphs (DAGs) due to their intricate interdependencies, can be periodic and persistent or aperiodic and dynamic (e.g., event-triggered alarms). Tasks within these DAGs may operate at various QoS levels, where higher levels enhance accuracy and reliability, improving the overall application QoS. This paper proposes a QoS-aware anytime scheduling approach for dynamically scheduling an aperiodic DAG-structured application on an MEC system already supporting periodic real-time tasks. We propose the Meta-heuristic QoS-Aware DAG Scheduler (M-QADS), a metaheuristic approach that begins by creating initial base schedules and iteratively improves them through task QoS level enhancements. Extensive simulations using both randomly generated and standard benchmark DAGs, alongside comparisons with the baseline heuristic Enhanced QoS HEFT (EQ-HEFT), reveal that M-QADS outperforms EQ-HEFT across diverse scenarios, demonstrating its effectiveness.

The future of automotive communication hinges on integrating legacy real-time protocols with advanced Ethernet technologies to empower Software-Defined Vehicles (SDVs). SDVs propose the adoption of the zonal computing architectures, which centralize vehicle functions into distinct zones connected by a high-speed communication backbone. While on the one hand, different zones can employ distinct network protocols like CAN, FlexRay, etc., Time Sensitive Ethernet (IEEE802.1Q) is being projected as the most promising protocol for the central backbone network. With such a heterogeneous distributed platform, SDVs demand reliable and deterministic end-to-end communication strategies, especially for zone-to-backbone or interzonal traffic via the central backbone. Although, there exist a few strategies for message transmission across heterogeneous network domains, they are ad-hoc in nature and oblivious to the precise demands of the control applications they cater to. These drawbacks may lead to poor bandwidth utilization and/or network congestion. Opposed to these ad-hoc techniques, this work proposes an optimal SMT (Satisfiability Modulo Theories) formulation for i) multiplexing periodic zonal message frames onto a minimum number of Ethernet frames, taking into account (m, k)-firmness-based relaxations on specific message flows, and ii) routing Ethernet frames between specified source and destination switches. Through extensive experimental evaluations of the proposed formulation using Z3 solver demonstrate substantial performance improvements, showing at least 30% gain in frame utilization under diverse traffic conditions and timing constraints. Our results validate the proposed approach as a robust solution for ensuring efficient and predictable real-time communication in futuristic SDVs.

Many control applications in real-time cyber-physical systems are represented as Directed Acyclic Graphs ( DAGs ) due to complex interactions among their functional components, and executed on distributed heterogeneous platforms. Data communication between dependent task nodes running on different processing elements are often realized through message transmission over a public network, and are hence susceptible to multiple security threats such as snooping , alteration , and spoofing . Several alternative security protocols having varying security strengths and associated implementation overheads are available in the market, for incorporating confidentiality , integrity , and authentication on the transmitted messages. While message size and correspondingly its associated transmission overheads may be marginally increased due to the assignment of security protocols, significant computation overheads must be incurred for securing the message at the location of its source task node and for unlocking security/message extraction at the destination. Obtained security strengths and associated computation overheads vary depending on the set of protocols chosen for a given message from an available pool of protocols. Given lower bounds on the security demands of an application’s messages, selecting the appropriate protocols for each message such that a system’s overall security is maximized while satisfying constraints related to the resource, task precedence and deadline, is a challenging and computationally hard problem. In this article, we propose an efficient heuristic strategy called SHIELD for security-aware real-time scheduling of DAG-structured applications to be executed on distributed heterogeneous systems. The efficacy of the proposed scheduler is exhibited through extensive simulation-based experiments using two DAG-structured application benchmarks. Our performance evaluation results demonstrate that SHIELD significantly outperforms two greedy baseline strategies SHIELDb in terms of solution generation times (i.e., runtimes) and SHIELDf in terms of achieved security utility. Additionally, a case study on the Traction Control application in automotive systems has been included to exhibit the applicability of SHIELD in real-world settings.

The rapid adoption of Electric Vehicles (EVs), driven by stringent environmental regulations and rising fuel costs, is reshaping the landscape of Vehicle Routing Problems (VRP). This shift has led to the Electric Vehicle Routing Problem (EVRP), which incorporates EV-specific operational constraints such as limited driving range, energy consumption, recharging strategies, and detour-related charging costs. The challenge becomes even more critical in modern mixed fleets , where Electric and Internal Combustion Engine Vehicles (ICEVs) coexist and must be co-routed efficiently. A widely adopted two-step strategy first uses Capacitated VRP (CVRP) algorithms to generate energy-oblivious routes, then makes EV routes energy-feasible via charging station insertion. While VRP and CVRP are extensively studied, methods for efficiently ensuring energy feasibility for EVs on fixed routes remain limited. This article introduces the Fixed Route Vehicle Charging Problem with Discrete Partial Charging (FRVCP-DPC) , extending FRVCP by allowing partial recharging up to predefined discrete levels. We develop a scalable optimal Dynamic Programming algorithm, Best Energy Feasible Route Generator (BEFRG) , to select detour points, charging stations, and charge levels that minimize total route time while maintaining energy feasibility. To evaluate BEFRG in dynamic traffic conditions, we introduce EFRGen , a traffic-aware EVRP simulator built on Simulation of Urban Mobility (SUMO) and OpenStreetMap (OSM). Experiments on the Montoya benchmark—spanning 120 instances with up to 320 demand points and 38 charging stations—show that BEFRG computes optimal solutions for all cases within one minute.

Cyber-Physical Systems controlling assembly line operations are central to manufacturing processes. Assembly line systems have diversified over time, depending on multiple factors, including the products being manufactured, the workstations and resources used, factory layouts, and so on. This diversity in assembly line configurations has added layers of complexity to the Assembly Line Balancing Problem (ALBP). While many powerful meta-heuristic techniques exist, their performance can vary significantly depending on the specific characteristics of the ALBP instance, such as the structure of the precedence graph, the distribution of task times, and the number of workstations. Recognizing the need for a more versatile solution, this article introduces a generic local search strategy called Flexible Meta-Heuristic (FMH), which includes a set of adjustable tuning parameters for adapting to specific scenarios. FMH combines and extends the strengths of Hill Climbing (HC), Simulated Annealing (SA), and Genetic Algorithm (GA) to provide effective solutions across a wide range of problems. Through extensive experiments using standard benchmarks and randomly generated datasets, FMH demonstrates high accuracy, deviating by at most 0.9% from best-known benchmark values. Additionally, FMH is significantly less resource-intensive, solving problems with up to 150 tasks in minutes where exact solvers can take hours, making it more scalable and applicable to large industrial scenarios. Our findings suggest that the algorithm’s flexibility and strategic hyper-parameter tuning contribute significantly to its effectiveness in solving diverse ALBPs.

Time Sensitive Ethernet is quickly emerging to be the preferred choice as the backbone network for in-vehicle communication, due to its high bandwidth, reliability, scalability, backward compatibility, and support for diverse traffic types. However, individual real-time control subsystems which may need to communicate via this backbone network, may be driven by non-Ethernet protocols like CAN, FlexRay, etc. Beyond ad hoc approaches, this highlights the need for a systematic message scheduling mechanism that enables seamless real-time message transmission over heterogeneous network domains. In this context, this work proposes a formal SMT (Satisfiability Modulo Theories) formulation for statically scheduling a set of persistent, periodic real-time messages. While the sources and destinations of these messages are in different CAN-network domains, the message transmissions must be conducted via an intermediate Time Sensitive Networking (TSN; IEEE802.1Q) backbone. Although, this formal strategy achieves high resource utilization while guaranteeing end-to-end timeliness, it is computationally exponential in nature with overheads becoming prohibitively expensive even for moderate problem sizes. Hence, we propose a lower overhead scheduling strategy called CAN-THER which can deliver efficient and quick solutions even for large problem sizes. The proposed scheduling strategies have been analyzed and compared using extensive simulation based experiments. Results reveal that CAN-THER is able to achieve performance that is up to 90% of the SMT formulation, while producing solutions at speeds that are approximately 104times faster for problems having up to 12 CAN flows and 15 TSN switches.

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.

Many of today’s complex cyber–physical systems (CPSs) are represented as a set of independent co-executing real-time control applications, where each such application is represented as a precedence-constrained task graph. The applications execute in infinite loops, periodically acquiring data from the environment through sensors at a particular frequency, processing the same, and then producing processed data via actuators. These CPSs often execute under stringent resource constraints (such as limited energy budgets) in distributed networked environments and may be heterogeneous to be able to satisfactorily meet stipulated performance specifications. This work presents a list-based energy-aware scheduler called DVFS-enabled periodic multi-DAG real-time scheduler for heterogeneous systems (DPMRS) for a set of real-time control applications co-executing in a heterogeneous distributed environment.DPMRSintroduces a novel approach for the integrated behavioral representation of a set of co-executing real-time DAG-structured applications. Each task in this integrated representation is then scheduled by determining its relative execution start time on a particular processor, which operates at an appropriately chosen frequency when the task runs on this processor. The overall objective ofDPMRSis to minimize aggregate energy consumed in the execution of all tasks. The efficacy of the proposed scheduler has been exhibited through extensive simulation experiments using benchmark task graphs from different application domains. Additionally, a case study on automotive control systems has been included to show the applicability of the proposed work in real-world settings.

A memory controller manages the flow of data to and from attached memory devices. The order in which a set of contending memory requests from different tasks are serviced significantly influences the rate of progress and completion times of these tasks. This in turn may affect the Quality-of-Service (QoS) delivered by these tasks. In this article, we focus towards the design of a QoS-aware memory controller targeted towards soft real-time systems. The proposed memory controller tries to generate an urgency-based schedule for the contending memory requests based on the allowable response time latencies associated with each request. The objective is to improve task-level response time predictability while maximizing acquired QoS. Exhaustive experiments carried out using real memory traces and standard simulation tools exhibit the practical efficacy of the proposed memory controller design.

To meet application-specific performance demands, recent embedded platforms often involve the use of intricate micro-architectural designs and very small feature sizes leading to complex chips with multi-million gates. Such ultra-high gate densities often make these chips susceptible to inappropriate surges in core temperatures. Temperature surges above a specific threshold may throttle processor performance, enhance cooling costs, and reduce processor life expectancy. This work proposes a generic temperature management strategy that can be easily employed to adapt existing state-of-the-art task graph schedulers so that schedules generated by them never violate stipulated thermal bounds. The overall temperature-aware task graph scheduling problem has first been formally modeled as a constraint optimization formulation whose solution is shown to be prohibitively expensive in terms of computational overheads. Based on insights obtained through the formal model, a new fast and efficient heuristic algorithm called TMDS has been designed. Experimental evaluation over diverse test case scenarios shows that TMDS is able to deliver lower schedule lengths compared to the temperature-aware versions of four prominent makespan minimizing algorithms, namely, HEFT , PEFT , PPTS , and PSLS . Additionally, a case study with an adaptive cruise controller in automotive systems has been included to exhibit the applicability of TMDS in real-world settings.

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.

Hybrid memory systems with a combination of DRAM and Non-Volatile Memory (NVM) types can make use of scalability and performance of both NVM and DRAM. Random placement of pages in Phase Change Memory (PCM) with more write accesses incurs higher write latencies. So, migrating write intensive pages from PCM to DRAM helps to reduce execution time and memory response time for applications. Existing techniques mainly focus on selecting the page migration candidate and migrate it immediately when it becomes eligible. This direct migration approach can hamper the response time of regular memory accesses. So, in our paper, we identify migration candidates and in addition, schedule when they can be migrated to DRAM. To realize this, we have used Selection and Run-time Scheduling of page Migration (SRS-Mig), a frame-based scheduling approach for migrations and read/write requests. SRS-Mig reduces migration overhead and guarantees future accesses to migrated pages to yield an improved execution time and memory response time for the applications. Experimental evaluation shows 30% improvement in execution time; 26% improvement memory response time, and considerable energy savings with the existing baseline techniques.

Scheduling real-time applications modelled as directed acyclic graphs on heterogeneous distributed platforms is known to be a challenging as well as a computationally demanding problem. This article deals with the design of an efficient scheduler for executing a real-time task graph on a distributed platform consisting of a set of fully connected heterogeneous processors. The objective of the scheduling strategy is to minimize ageneric penalty functionwhich can be amicably adopted toward its deployment in various application domains such as real-time embedded systems, cloud/fog computing, industrial automation and IoTs, smart grids, automotive and avionic systems, etc. We have first encoded the problem as a constraint satisfaction problem and then developed an efficient list-based heuristic scheduling algorithm calledPenalty-aware REal-time Scheduler for Task graphs on heterOgeneous platforms(PRESTO), to generate a minimal penalty deadline-meeting static schedule. The generic efficacy ofPRESTOis exhibited through extensive simulation-based experiments using standard benchmark task graphs. The practical applicability ofPRESTOin diverse scenarios have further been exhibited by using the scheme in two different real-world case studies, the first of which relates to automotive embedded systems, while the second is in the domain of fog computing.

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.

In recent years, mobile data traffic has increased enormously with an increase of mobile and smart devices. The global mobile data traffic is set to increase manifold in the coming years. With the rise in mobile data traffic and heterogeneous mobile devices, substantial improvement has been achieved in wireless media technology in providing a varied range of multimedia services. These multimedia services are often resource-hungry and require high-speed data and low latency transmissions. High-speed networks like the fifth-generation (5G) network helps in faster data delivery resulting in less congestion at the backhaul links and higher transmission capacity. Integrating Mobile Edge Computing (MEC) capabilities into the cellular architecture provides advantages like intelligent and efficient context-aware caching and video adaptations for content delivery. The primary objective of this work is to reduce the overall backhaul congestion and access delay by increasing the cache hit rate at the MEC server. This work proposes a deep learning-based model for caching at the MEC servers based on the content popularity at different time slots of a day. Experimental results reveal that the proposed model outperforms the state-of-the-art standard caching approaches, improves the cache hit probability by almost 21%, and decreases backhaul usage and access delay by approximately 18%.

Phase Change Memory (PCM) has emerged as a viable alternative to traditional DRAM memories especially in real-time embedded systems, due to their higher density and lower leakage power dissipation. However, PCM comes with its own drawbacks. Although, the performances of DRAM and PCM are comparable for memory reads, PCM is about three times slower in terms of write latency, and suffers from significantly lower write endurance. The high write latency of PCM may be detrimental to delivered QoS and may lead to deadline misses in real-time systems. To circumvent the problem, this paper proposes a novel memory scheduling scheme which employs separate write request buffer in order to prioritize reads over writes. The read requests are scheduled using an urgency based scheduler where urgency depends on allowable response times of tasks. The write requests are serviced when there are no pending reads using a similar urgency based scheduler as used for read requests. Experimental evaluation using standard benchmarks reveal that the proposed scheme is able to achieve better normalized QoS compared to existing scheduling techniques for PCM and comparable access latencies with respect to DRAM.

Cyber-Physical Systems, including those in the automotive domain, are often designed by assigning to each task an appropriate criticality-based reward value which is acquired by the system on its successful execution. Additionally, each task may have multiple implementations designated as service-levels, with higher service-levels producing more accurate results and contributing to higher rewards for the system. This work proposes strategies for co-scheduling a set of periodic tasks with multiple service-levels, on homogeneous processors and system buses. The problem is modeled as a Multi-dimensional Multiple-Choice Knapsack formulation (MMCKP) with the objective of maximizing overall system level rewards. A Dynamic Programming (DP) solution is proposed to solve the MMCKP. It was observed that although the DP based solution produces optimal results, its complexity is highly sensitive to the number of tasks, processors, buses as well as to the number of task service-levels, which severely restricts scalability of the strategy. Therefore, we have also proposed a fast yet efficient heuristic algorithm called Accurate Low Overhead Level Allocator (ALOLA), which attempts to achieve the same objective. Our simulation based experimental evaluation shows that even on moderately large systems consisting of 90 tasks with 5 service-levels each, 16 processors and 4 buses, while MMCKP incurs a run-time of more than 1 hour 20 minutes and approximately 68 GB main memory, ALOLA takes only about 196 $\mu s$ (speedup of the order of 106times) and less than 1 MB of memory. Moreover, while being fast, ALOLA is also efficient being able to control performance degradations to at most 13% compared to the optimal results produced by MMCKP. We use an automated flight control system employed in modern avionic systems, a real-world application to illustrate the general applicability of our proposed scheme.

The ability to maintain functional and temporal correctness in the presence of faults is a key requirement in many safety-critical embedded systems. This work proposes an efficient fault recovery mechanism for real-time multiprocessor systems scheduled using a low overhead, semi-partitioned optimal proportional fair scheduling technique. We assume a system that can handle a single permanent processor fault at any time, using cold back-ups (with pre-specified activation / recovery time subsequent to the detection of a fault). As a result of the fault, the system may suffer transient overloads during such recovery periods, potentially leading to unacceptable fairness deviations and consequent rejections / early terminations of critical jobs. The proposed fault-tolerant scheduler, called Fault Tolerant Fair Scheduler (FT-FS), attempts to minimize such job terminations / rejections during recovery, by judiciously redistributing slacks accumulated by a subset of jobs, delivering more sustainable performance in the process. Experimental results reveal that the proposed FT-FS algorithm performs appreciably even under high system loads. Practical applicability of our proposed scheme has been illustrated using a case study on aircraft flight control system.

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.

The problem of scheduling Directed Acyclic Graphs in order to minimizemakespan(schedule length), is known to be a challenging and computationally hard problem. Therefore, researchers have endeavored towards the design of various heuristic solution generation techniques both for homogeneous as well as heterogeneous computing platforms. This work first presentsHMDS-Bl, a list-based heuristicmakespanminimization algorithm for task graphs on fully connected heterogeneous platforms. Subsequently,HMDS-Blhas been enhanced by empowering it with a low-overhead depth-first branch and bound based search approach, resulting in a new algorithm calledHMDS.HMDShas been equipped with a set of novel tunable pruning mechanisms, which allow the designer to obtain a judicious balance between performance (makespan) and solution generation times, depending on the specific scenario at hand. Experimental analyses using randomly generated DAGs as well as benchmark task graphs, have shown thatHMDSis able to comprehensively outperform state-of-the-art algorithms such asHEFT,PEFT,PPTS, etc., in terms of archivedmakespanswhile incurring bounded additional computation time overhead.

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.

Power shortage is a serious issue especially in developing nations. Such power deficits are traditionally handled through rolling blackouts - a service area is divided into subareas, each of which is denied power during a designated time in the day. Today, smart grids provide the opportunity of avoiding complete blackouts, converting them to brownouts which allow selective provisioning of power supply to support essential loads while curtailing supply to less critical loads. We formulate the brownout based power distribution problem as aninteger linear programming (ILP)and show that solution strategies such asconventional dynamic programming (DP)impose substantial overheads. So, we propose thestreamlined DP-based priority level allocator (SDPA)which utilizes the discrete nature of power demands of each subarea and generates the overall optimal solution far quicker by focusing on a lower number of non-dominating partial DP-solutions.SDPAis found to be about 9 to 33 times faster thanDPand applicable to real-time brown-out based power distribution in moderate sized grids. However, evenSDPAmay fail to meet the real-time requirements of dynamic power imbalance mitigation in very large grids. So, a fast yet effective power adjustment approach namely,Proportionally Balanced Priority level Allocator (PBPA), has been designed and implemented. Experimental results show that although solutions provided byPBPAcould be less effective by upto 12 percent compared to optimal dynamic programming based schemes, being about 4 orders of magnitude faster, it can be deployed for real time allocations of power.

Developing energy-efficient schedulers for real-time heterogeneous platforms executing periodic tasks is an onerous as well as a computationally challenging issue. This research presents a heuristic strategy named, EA-HRT, for DVFS based energy-aware scheduling of a set of periodic tasks executing on a heterogeneous multicore platform. Initially it calculates the execution demands of every task on each of the different type of cores. Then, it simultaneously allocates each task on available cores and selects operating frequencies for the concerned cores such that the summation of execution demands of all tasks are met as well as there is minimum change in energy consumption for the system. Experimental results show that our proposed strategy is not only able to achieve appreciable energy savings with respect to state-of-the-art (2% to 37% on average) but also enables significant improvement in resource utilization (as high as 57%).

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.

Reconfigurable devices that promise to offer the twin benefits of flexibility as in general-purpose processors along with the efficiency of dedicated hardwares often provide a lucrative solution for many of today’s highly complex real-time embedded systems. However, online scheduling of dynamic hard real-time tasks on such systems with efficient resource utilization in terms of both space and time poses an enormously challenging problem. We attempt to solve this problem using a combined offline-online approach. The offline component generates and stores various optional feasible placement solutions for different sub-sets of tasks that may possibly be co-mapped together. Given a set of periodic preemptive real-time tasks that requires to be executed at runtime, the online scheduler first carries out an admission control procedure and then produces a schedule, which is guaranteed to meet all timing constraints provided it is spatially feasible to place designated subsets of these tasks at specified scheduling points within a future time interval. These feasibility checks are done and actual placement solutions are obtained through a low overhead search of the statically precomputed placement solutions. Based on this approach, we have proposed a periodic preemptive real-time scheduling methodology for runtime partially reconfigurable devices. Effectiveness of the proposed strategy has been verified through simulation based experiments and we observed that the strategy achieves high resource utilization with low task rejection rates over various simulation scenarios.

The ever increasing demand for high bandwidth, low latency multimedia applications on mobile devices is set to pose a considerable challenge on the bandwidth allocation and multiplexing mechanisms in LTE and future wireless networks. This paper proposes a low overhead Scalable Video Coding (SVC) based dynamic adaptive streaming framework (called TLS-AV) which attempt to maintain a minimum satisfactory Quality of Experience (QoE) for all end users even during transient network overloads. Two fast and efficient radio resource allocation heuristics namely, the TLS-AV Water-Filling Heuristic (TWH) and TLS-AV Balanced Water-Filling Heuristic (TBWH) have been implemented over the proposed framework. Experimental results reveal that both the developed heuristics are able to restrict packet loss rate below ~ 10% while simultaneously achieving high video qualities and fairness among the transmitted qualities of video flows, on average.

Proportional fair schedulers with their ability to provide optimal schedulability along with hard timeliness and quality-of-service guarantees on multiprocessors form an attractive alternative in real-time embedded systems that concurrently run a mix of independent applications with varying timeliness constraints. This article presents ERfair Scheduler with Suspension on Multiprocessors (ESSM) , an efficient, optimal proportional fair scheduler that attempts to reduce system wide energy consumption by locally maximizing the processor suspension intervals while not sacrificing the ERfairness timing constraints of the system. The proposed technique takes advantage of higher execution rates of tasks in underloaded ERfair systems and uses a procrastination scheme to search for time points within the schedule where suspension intervals are locally maximal. Evaluation results reveal that ESSM achieves good sleep efficiency and provides up to 50% higher effective total sleep durations as compared to the Basic-ERfair scheduler on systems consisting of 2 to 20 processors.

Putting the processor into shutdown state when it is idling is one of the primary methodologies towards the reduction of energy consumption in today's systems where leakage power is emerging as a dominant concern. This paper presents ERfair Scheduler with Processor Shutdown (ESPS), a uniprocessor ERfair scheduler that attempts to minimize energy consumption in rate-based periodic real-time task systems by locally maximizing processor shut-down intervals while simultaneously maintaining proportional fairness among task executions. Evaluation results show that our proposed algorithm achieves good shut-down efficiency and provides upto 9 times higher effective shutdown lengths as compared to the Basic_ERfair scheduler.

All known real-time proportional fair scheduling mechanisms either have high scheduling overheads (O(lg n) per time-slot) or do not efficiently handle dynamic task sets. This paper presents frame-based proportional round-robin (FBPRR), a real-time fair scheduler providing high and bounded proportional fairness accuracy and O(1) scheduling overhead with the ability to efficiently handle a set of dynamic tasks. FBPRR achieves this by applying the benefits of virtual-time round-robin (VTRR) scheduling mechanism within a frame-based scheduling approach. Simulation results show that the algorithm gains a speedup of 5 to 20 times (over O(lg n) complexity schedulers) with fairly high fairness