In real-time systems optimization, designers often face a challenging problem posed by the non-convex and non-continuous schedulability conditions, which may even lack an analytical form to understand their properties. To tackle this challenging problem, we treat the schedulability analysis as a black box that only returns true/false results. We propose a general and scalable framework to optimize real-time systems with continuous variables, named Numerical Optimizer with Real-Time Highlight (NORTH). NORTH is built upon the gradient-based active-set methods from the numerical optimization literature but with new methods to manage active constraints for the non-differentiable schedulability constraints. In addition, we also generalize NORTH to NORTH+ to collaboratively optimize priority assignments, a common type of discrete variables, with continuous variables based on numerical optimization algorithms. We demonstrate the algorithm performance with two example applications: energy minimization based on dynamic voltage and frequency scaling (DVFS), and optimization of control system performance. In these experiments, NORTH are 10 2 to 10 5 times faster than state-of-the-art methods while maintaining similar or better solution quality. NORTH+ outperforms NORTH by 30% with similar algorithm scalability. Both NORTH and NORTH+ support black-box schedulability analysis, ensuring broad applicability.

We consider the problem of broadcasting a common message (comprised of$L$symbols) over a fully connected network, where each pair of nodes is connected by a noiseless link that can carry one symbol per time slot. The most important constraint is that each node has a single port, i.e., each node can only send to, or receive from, one other node at a given time. We are interested in the minimum number of time slots,$T^{*}$, required for this broadcast problem. We show that$T^{*} \geq \left\lceil\log _{2}(K+1)\right\rceil+L-1$through an information theoretic converse based on port constrained cut-set bounds. For achievability, we provide a routing based protocol that achieves the above$T^{*}$lower bound.

Controller area network (CAN) protocol is an efficient standard enabling communication among electronic control units (ECUs). However, the CAN bus is vulnerable to malicious attacks because of a lack of defense features. In this article, a novel vehicle intrusion detection system (IDS) is developed. The challenge is that existing techniques of IDSs rarely consider attacks with small-batch, which are characterized by their small attack scale and concealed attack patterns, posing a significant threat to driving safety. To solve this problem, we developed an algorithm model that merges multidimensional long short-term memory (MD-LSTM) and self-attention mechanism (SAM), shortly named MULSAM. The MULSAM model was compared with other baseline models, including stacked long short-term memory (LSTM), MD-LSTM, etc. Experiments show that our approach has the best-detection accuracy (98.98%) and training stability. Further, to speed up the inference of MULSAM on edge, the hardware accelerator is implemented on FPGA devices using technologies, such as parallelization, modular, pipeline, and fixed-point quantization. Experiments show that our FPGA-based acceleration scheme has a better-energy efficiency than the CPU platform. Even with a certain degree of quantification, the acceleration model for MULSAM still displays a high-detection accuracy of 98.81% and a low latency of 1.88 ms.

We consider the problem of minimizing emission of a heavy-duty truck transporting freight between two locations subject to a hard deadline constraint. The truck is equipped with a multi-speed transmission and a modern combustion engine that intelligently switches among multiple fuel injection strategies at certain engine speeds (called switching speeds) to achieve lower emission profiles. Our objective is to minimize the emission by optimizing both path and speed planning for heavy-duty trucks with multi-speed transmission and multiple injection strategies in the engine. This emission minimization problem, while pervasive in practice, has two challenges: i) the emission rate function is discontinuous and non-convex due to switching of the fuel injections and gear ratios, which makes the common practice of driving at a constant speed on a road segment not eco-friendly; ii) the problem is NP-hard due to the combinatorial nature of the simultaneous path and speed planning. We tackle the first challenge by considering the case where the truck can travel at a heterogeneous speed profile over a road segment and then formulate the speed planning problem as a convex problem. We further identify special structures in this problem and provide an efficient method for computing the optimal speed profile. We then tackle the second challenge by developing an efficient heuristic for both path planning and speed planning to solve the emission minimization problem on the scale of national highway systems. Our extensive simulations on the US highway system show that our solution reduces up to 46% NOx emission as compared to the commonly-adopted fastest path approach. We also find that optimizing heterogeneous speed profiles reduce up to 32% emission as compared to their homogeneous counterpart, thus are necessary to be considered in eco-friendly truck operations.

The Logical Execution Time (LET) programming model has recently received considerable attention, particularly because of its timing and dataflow determinism. In LET, task computation appears always to take the same amount of time (called the task's LET interval), and the task reads (resp. writes) at the beginning (resp. end) of the interval. Compared to other communication mechanisms, such as implicit communication and Dynamic Buffer Protocol (DBP), LET performs worse on many metrics, such as end-to-end latency (including reaction time and data age) and time disparity jitter. Compared with the default LET setting, the flexible LET (fLET) model shrinks the LET interval while still guaranteeing schedulability by introducing the virtual offset to defer the read operation and using the virtual deadline to move up the write operation. Therefore, fLET has the potential to significantly improve the end-to-end timing performance while keeping the benefits of deterministic behavior on timing and dataflow. To fully realize the potential of fLET, we consider the problem of optimizing the assignments of its virtual offsets and deadlines. We propose new abstractions to describe the task communication pattern and new optimization algorithms to explore the solution space efficiently. The algorithms leverage the linearizability of communication patterns and utilize symbolic operations to achieve efficient optimization while providing a theoretical guarantee. The framework supports optimizing multiple performance metrics, and guarantees bounded suboptimality when optimizing end-to-end latency. Experimental results show that our optimization algorithms improve upon the default LET and its existing extensions and significantly outperform implicit communication and DBP in terms of various metrics, such as end-to-end latency, time disparity, and its jitter.

Global fixed-priority (G-FP) scheduling is a widely applied scheduling policy for real-time systems running on multiprocessor platforms. The state-of-the-art in priority assignment for G-FP follows one of two approaches. The first is to use a simple heuristic for priority assignment that works with any (thus the most accurate) schedulability analysis. The second is to leverage Audsley’s polynomial-time optimal priority assignment (OPA) algorithm, which can only accommodate a less accurate analysis that satisfies the compatibility conditions required by OPA. In this paper, we study this critical issue and present a novel algorithm. We first use the concept of response time estimation range to build a new priority assignment framework, which is optimal with a more accurate schedulability analysis than OPA since its compatibility conditions are much weaker than those of OPA. This new frontier on the second approach is then judiciously combined with the first approach to take advantage of both. We evaluate the effectiveness of the proposed algorithm with various task sets. Compared with existing approaches, our algorithm always achieves the highest acceptance ratio and can outperform them by 25% on average.

Modern real-time systems often involve numerous computational tasks characterized by intricate dependency relationships. Within these systems, data propagate through cause–effect chains from one task to another, making it imperative to minimize end-to-end latency to ensure system safety and reliability. In this article, we introduce innovative nonpreemptive scheduling techniques designed to reduce the worst-case end-to-end latency and/or time disparity for task sets modeled with directed acyclic graphs (DAGs). This is challenging because of the noncontinuous and nonconvex characteristics of the objective functions, hindering the direct application of standard optimization frameworks. Customized optimization frameworks aiming at achieving optimal solutions may suffer from scalability issues, while general heuristic algorithms often lack theoretical performance guarantees. To address this challenge, we incorporate the “1-opt” concept from the optimization literature (Essentially, 1-opt means that the quality of a solution cannot be improved if only one single variable can be changed) into the design of our algorithm. We propose a novel optimization algorithm that effectively balances the tradeoff between theoretical guarantees and algorithm scalability. By demonstrating its theoretical performance guarantees, we establish that the algorithm produces 1-opt solutions while maintaining polynomial run-time complexity. Through extensive large-scale experiments, we demonstrate that our algorithm can effectively reduce the latency metrics by 20% to 40%, compared to state-of-the-art methods.

In the optimization of real-time systems, designers often face a challenging problem where the schedulability conditions are non-convex, non-continuous, or lack an analytical form to understand their properties. In this paper, we propose a general and scalable framework for optimizing real-time systems, named Numerical optimizer with Real-Time Highlight (NORTH). NORTH treats schedulability analysis as a blackbox which may only return true/false results on system schedulability. Built upon the active-set methods from the gradient-based numerical optimization literature, NORTH proposes new methods to manage active constraints to further improve the gradient-based optimizers. We apply the proposed approach to two example problems, one on energy optimization for systems with dynamic voltage and frequency scaling, and the other on the optimization of control performance. Experimental results demonstrate that the proposed framework runs 102to 105times faster than state-of-the-art methods while maintaining similar solution quality.

Equipping real-time systems with soft error resilience can be challenging due to the tradeoff of the timing and failure requirements for mixed-criticality tasks. Violation of these requirements yields failed task scheduling in one way or another. However, not every task requires the same degree of soft error resilience. For example, low-criticality tasks can run with low or even no soft error resilience, whereas mid- or highcriticality tasks may require relatively high resilience depending on their inherent failure requirement. Unfortunately, existing soft error resilience schemes do not have the ability to control the degree of their resilience in a fine-grained way, i.e., they can only be turned on or off as a whole during task execution. To this end, this paper presents RTailor (Resilience Tailor), a compiler-directed parameterized soft error resilience scheme that achieves the desired level of soft error protection according to the demand of each task. The key idea is that for a given protection ratio, compilers can transform a hot loop such that the number of its iterations protected over the total iterations matches the ratio. Compared to full resilience protecting every iteration, RTailor's parameterized soft error resilience significantly reduces the performance overhead of tasks, thereby improving their real-time schedulability. The experimental results highlight that for four representative fault rates, RTailor achieves 15%~average schedulability improvements over the state-of-the-art work that lacks parameterized soft error resilience.

We study the problem of minimizing fuel consumption of a heavy-duty truck traveling across the national highway network subject to a hard deadline. We focus on a real-world setting that traversing a road segment is subject to variable speed ranges due to dynamic traffic conditions. The consideration of dynamic traffic conditions not only differentiates our work from existing ones but also allows us to leverage opportunistic driving to improve fuel efficiency. The idea is for the truck to strategically wait (e.g., at highway rest areas) for benign traffic conditions, so as to traverse subsequent road segments at favorable speeds for saving fuel. We observe that traffic conditions and thus speed ranges are mostly stationary within certain duration of the day, and we term them as phases. We formulate the fuel consumption minimization problem under phased speed ranges, considering path planning, speed planning, and opportunistic driving. We prove that the problem is NP-hard, and develop a dual-subgradient algorithm for large-/national- scale instances. We characterize conditions under which the algorithm generates an optimal solution. We carry out simulations based on real-world traces over the US highway system. The results show that our scheme saves up to 20% fuel than a shortest-path based alternative, of which opportunistic driving contributes 13%. Meanwhile, opportunistic driving also reduces driving time by 6% as compared to only optimizing path planning and speed planning. As such, it offers a desirable design option to simultaneously reduce fuel consumption and hours of driving. Last but not least, our results highlight a perhaps surprising observation that dynamic traffic conditions can be exploited to achieve fuel savings even larger than those under stationary traffic conditions.

With the deep integration of the Internet of Things (IoT) technology and the increase of computational power and memory, vehicles can also serve as the infrastructures for Intelligent Transportation System (ITS), e.g., as fog nodes. However, when connecting vehicles to the internet, alongside with the benefits it brings, it also opens many new challenges such as security attacks. Controller Area Network (CAN) is one of the main in-vehicle communication protocols in modern cars. Its lack of sender verification mechanism makes CAN particularly vulnerable to cyber-attacks including masquerade attack. Fingerprinting Electronic Control Units (ECUs) based on hardware characteristics has been proved feasible and effective on defending CAN buses. However, most state-of-the-art works exploited the supervised learning algorithm to identify the transmitter based on the signal characteristics. This makes the decision process hard to understand, and it also limits the deployment on proprietary CAN bus without prior knowledge. To solve this, we design a novel clock-skew-based approach capable of pinpointing the sender and detecting intrusion on proprietary CAN bus. We take a single CAN frame as the object for measurement, and adjust the measuring process such that our approach can be independent of the transmission time of frames. Based on the statistical analysis of data from real vehicles, we propose a novel box-plot algorithm based on score mechanism to filter the raw data. Finally, the clock skews are estimated and accumulated to build a linear model for representing the transmitter ECU. The evaluation results on one CAN prototype and two production vehicles show that our approach is able to well identify and differentiate ECUs on the bus without prior knowledge. The data processed by the proposed box-plot algorithm can describe the hardware characteristics of ECUs precisely. We also show the ability of our approach to protecting the CAN bus against the masquerade attack.

The Controller Area Network (CAN) is a ubiquitous bus protocol present in the Electrical/Electronic (E/E) systems of almost all vehicles. It is vulnerable to a range of attacks once the attacker gains access to the bus through the vehicle’s attack surface. We address the problem of Intrusion Detection on the CAN bus and present a series of methods based on two classifiers trained with Auxiliary Classifier Generative Adversarial Network (ACGAN) to detect and assign fine-grained labels to Known Attacks and also detect the Unknown Attack class in a dataset containing a mixture of (Normal + Known Attacks + Unknown Attack) messages. The most effective method is a cascaded two-stage classification architecture, with the multi-class Auxiliary Classifier in the first stage for classification of Normal and Known Attacks, passing Out-of-Distribution (OOD) samples to the binary Real-Fake Classifier in the second stage for detection of the Unknown Attack class. Performance evaluation demonstrates that our method achieves both high classification accuracy and low runtime overhead, making it suitable for deployment in the resource-constrained in-vehicle environment.

A Mixed-Criticality System (MCS) features the integration of multiple subsystems that are subject to different levels of safety certification on a shared hardware platform. In cost-sensitive application domains such as automotive E/E systems, it is important to reduce application memory footprint, since such a reduction may enable the adoption of a cheaper microprocessor in the family. Preemption Threshold Scheduling (PTS) is a well-known technique for reducing system stack usage. We consider partitioned multiprocessor scheduling, with Preemption Threshold Adaptive Mixed-Criticality (PT-AMC) as the task scheduling algorithm on each processor and address the optimization problem of finding a feasible task-to-processor mapping with minimum total system stack usage on a resource-constrained multi-processor. We present the Extended Maximal Preemption Threshold Assignment Algorithm (EMPTAA), with dual purposes of improving the taskset’s schedulability if it is not already schedulable, and minimizing system stack usage of the schedulable taskset. We present efficient heuristic algorithms for finding sub-optimal yet high-quality solutions, including Maximum Utilization Difference based Partitioning (MUDP) and MUDP with Backtrack Mapping (MUDP-BM), as well as a Branch-and-Bound (BnB) algorithm for finding the optimal solution. Performance evaluation with synthetic task sets demonstrates the effectiveness and efficiency of the proposed algorithms.

We consider a single-unicast networking scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. We study problems of minimizing peak/average Age-of-Information (AoI) subject to throughput requirements based on a stylized deterministic model in this scenario. The consideration of batch generation and multi-path communication differentiates ourAoIstudy from existing ones. We first show that ourAoIminimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizingAoIand minimizing maximum delay are “roughly” equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any$\alpha $-approximation algorithm of the maximum delay minimization problem to construct an$(\alpha +\mathsf {c})$-approximate solution for minimizingAoI. Here$\mathsf {c}$is a constant depending on the throughput requirements. Furthermore, we show that our results can be extended to the multiple-unicast setting. Simulations over various network topologies validate the effectiveness of our approach. Our results make a major advance to optimizingAoIin multi-path communication, and hence can be of broad interest to the networking research community.

Heterogeneous computing systems are being increasingly deployed on time-critical applications, where tasks need to meet execution deadlines and the energy consumption is to be minimized. Dynamic voltage and frequency scaling (DVFS) has been widely applied for energy saving on computing devices. Unfortunately, DVFS may introduce transient errors and shorten the processor lifetime. There is also time and energy overhead when computing and making the switching. In this article, we investigate scheduling approaches—that are independent of, or weakly dependent on DVFS—for parallel real-time applications with hard deadlines running on heterogeneous computing systems. The aim is to minimise the energy consumption while keeping all deadlines satisfied. First, in the domain without DVFS, we propose a DVFS-nondependent scheduling algorithm (DNDS), which prioritises tasks of high energy consumption during reassignment with slack time. Second, we propose a DVFS-weakly dependent scheduling (DWDS) algorithm, which finds an appropriate frequency for each processor in an iterative manner. DVFS is only allowed when switching applications. Third, based on DWDS, we further propose an algorithm Fast_DWDS, which quickly converges by deploying a binary search method. Our proposed scheduling approaches are evaluated with a large number of directed acyclic graph-based applications of high, low, and random parallelism. The results show that they significantly reduce the energy cost compared to their existing counterparts, i.e., without and with DVFS, respectively, while all deadlines remain satisfied.

We consider the scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Data transmission over a link incurs a cost and a delay, both of which are traffic-dependent. We study the problem of minimizing network transmission cost subject to a maximum delay constraint and a throughput requirement. The problem is important for leveraging edge-cloud computing platforms to support computationally intensive IoT applications, which are sensitive to three critical performance metrics, i.e., cost, maximum delay, and throughput. Our problem jointly considers the three metrics, while existing ones only account for one or two of them. We first show that our problem is uniquely challenging, as (i) it is NP-complete even to find a feasible solution satisfying all constraints, and (ii) directly extending existing solutions to our problem results in problem-dependent maximum delay violations that can be unbounded. We then design both an approximation algorithm and an efficient heuristic. For any feasible instance, our approximation algorithm will achieve a cost no worse than the optimal, while violating the maximum delay constraint and the throughput requirement only by constant ratios. Meanwhile, our heuristic will construct feasible solutions for a large portion (over 60% empirically) of feasible instances, strictly satisfying the maximum delay constraint and the throughput requirement. We further characterize a condition under which the cost of our heuristic must be within a problem-dependent-ratio gap to the optimal. We simulate representative edge computing platforms, and observe that (i) when sacrificing 3% throughput, our approximation algorithm reduces 32% cost as compared to a greedy baseline, and satisfies the maximum delay constraint for 56% simulated instances; (ii) our heuristic solves 62% of feasible instances, and reduces 24% cost as compared to the baseline while strictly satisfying all constraints.

The design of modern real-time systems not only needs to guarantee their timing correctness, but also involves other critical metrics such as control quality and energy consumption. As real-time systems become increasingly complex, there is an urgent need for efficient optimization techniques that can handle large-scale systems. However, the complexity of schedulability analysis often makes it difficult to be directly incorporated in standard optimization frameworks, and inefficient to be checked against a large number of candidate solutions. In this paper, we propose a novel optimization framework for the design of real-time systems. It leverages the sustainability of schedulability analysis that is applicable for a large class of real-time systems. It builds a counterexample-guided iterative procedure to efficiently learn from an unschedulable solution and rule out many similar ones. Compared to the state-of-the-art, the proposed framework may be ten times faster while providing solutions with the same quality.

Controller area network (CAN) is a widely used protocol that allows communication among electronic control units (ECUs) in automotive electronics. It was extended to CAN with flexible data-rate (CAN-FD) to meet the increasing demand for bandwidth generated by the growing number of features in modern automobiles. The signal-to-frame packing problem has been studied in the literature for both CAN and CAN-FD. In this paper, we propose and formulate the signal offset assignment problem (SOAP) in CAN-FD to improve the bus utilization during frame packing. We propose two algorithmic themes to solve SOAP and establish their worst case performance guarantees. The first is a general approximation framework (GAF) which can use any approximation algorithm for the makespan minimization problem (MMP) in multiprocessor systems. Its performance guarantee is the product of the performance guarantee of the MMP algorithm and the number of distinct periods in the frame. The second is a 2-D strip packing-based framework (2DSPF) which uses the bottom left fill algorithm for 2-D strip packing. The performance guarantee is 2G , where G is the minimum number of groups into which the set of signals can be partitioned so that the periods of the signals in the same group form a geometric series. The experimental results for GAF and 2DSPF indicate that by carefully assigning offsets for signals in frame packing schemes, one can achieve about 10.83% improvement in bus utilization in CAN-FD systems.

In cyber-physical systems, certain tasks are activated according to a rotation source. For example, angular tasks in engine control units are triggered whenever the engine crankshaft reaches a specific angular position. To reduce the workload at high speeds, these tasks also adopt different implementations within different rotation speed intervals. However, current studies are limited to the case that the switching speeds at which task implementations should change are configured at design time. In this article, we propose to dynamically adjust the switching speeds at runtime. We develop schedulability analysis techniques for such systems, including a new digraph-based task model to safely approximate the workload from software tasks triggered at predefined rotation angles. We prove that such task transformation has bounded pessimism. We present exact algorithms to find a finite number of representatives to avoid enumerating (an infinite number of) all job sequences. Experiments on synthetic task systems demonstrate that the proposed approach provides substantial benefits on system schedulability.

With the rapid growth of connectivity and autonomy for today’s automobiles, their security vulnerabilities are becoming one of the most urgent concerns in the automotive industry. The lack of message authentication in Controller Area Network (CAN), which is the most popular in-vehicle communication protocol, makes it susceptible to cyber attack. It has been demonstrated that the remote attackers can take over the maneuver of vehicles after getting access to CAN, which poses serious safety threats to the public. To mitigate this issue, we propose a novel intrusion detection system (IDS), called BTMonitor (Bit-time-based CAN Bus Monitor). It utilizes the small but measurable discrepancy of bit time in CAN frames to fingerprint their sender Electronic Control Units (ECUs). To reduce the requirement for high sampling rate, we calculate the bit time of recessive bits and dominant bits, respectively, and extract their statistical features as fingerprint. The generated fingerprint is then used to detect intrusion and pinpoint the attacker. BTMonitor can detect new types of masquerade attack that the state-of-the-art clock-skew-based IDS is unable to identify. We implement a prototype system for BTMonitor using Xilinx Spartan 6 FPGA for data collection. We evaluate our method on both a CAN bus prototype and a real vehicle. The results show that BTMonitor can correctly identify the sender with an average probability of 99.76% on the real vehicle.

The advancing machine learning techniques have been widely applied to data-driven dynamic stability assessment (DSA) in modern smart grids. However, how to extract critical spatial-temporal features from wide-area system stability dynamics still remains an open issue. Emphasizing on short-term voltage stability (SVS) assessment, this paper develops a novel sequential feature learning approach to address this problem in two steps. First, based on visualized voltage contours, it tactfully constructs a comprehensive spatial-temporal sequence model to dynamically characterize multiplex spatial-temporal SVS evolution trends. Second, the time series shapelet classification method is leveraged to subtly extract critical consecutive SVS features in sequential forms, i.e., the multidimensional shapelets (discriminative subshapes). Test results on the real-world Hong Kong power grid demonstrate the efficacy, adaptability, and scalability of the proposed approach for SVS assessment. In addition to the outstanding performances on online DSA, with its favorable interpretability, it is capable of providing intuitive insights into regional SVS patterns from spatial-temporal perspectives.

We consider a common truck operation scenario, where a long-haul heavy-duty truck drives across a national highway system to fulfill multiple geographically-dispersed tasks in a specific order. The objective is to minimize the total fuel consumption subject to the pickup and delivery time window constraints of individual tasks, by jointly optimizing task execution times, path planning, and speed planning. The need to coordinate execution times for multiple tasks differentiates our study from existing ones on single task. We first prove that our problem is NP-hard. Moreover, it is uniquely challenging to solve our problem, as we further show that optimizing task execution times is a non-convex puzzle. We then exploit the problem structure to develop (i) a Fully-Polynomial-Time Approximation Scheme (FPTAS), and (ii) a fast and efficient heuristic algorithm, called SPEED (Sub-gradient-based Price-driven Energy-Efficient Delivery). We characterize sufficient conditions under which SPEED generates an optimal solution, and derive an optimality gap for SPEED when the conditions are not satisfied. We evaluate the practical performances of our solutions using real-world traces over the US national highway. We observe that our solutions can save up to 22% fuel as compared to the fastest-/shortest- path baselines, and up to 10% fuel than a conceivable alternative generalized from the state-of-the-art single-task algorithm. The fuel saving is robust to the number of tasks to be fulfilled. Simulations also show that our algorithms always obtain close-to-optimal solutions and meet time window constraints for all feasible problem instances. In comparison, the conceivable alternative fails to meet time window constraints for up to 45% of the instances.

We consider a single-unicast networking scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Transmission over a link incurs a traffic-dependent link delay. We optimize network delay concerning two popular metrics, namely maximum delay and average delay. Well-known pessimistic results state that a flow cannot simultaneously achieve a maximum delay and an average delay both within bounded-ratio gaps to optimal. Instead, we pose an optimistic note on the fundamental compatibility of the two delay metrics. Specifically, we design two polynomial-time solutions each of which can deliver (1 - ϵ)-fraction of the flow with maximum delay and average delay simultaneously within (1/ϵ)-ratio gap to optimal, for any ϵ ∈ (0, 1). We prove that the ratio (1/ϵ) is at least near-tight. Moreover, our solutions can be extended to the multiple-unicast setting. In this setting, the two delay metrics of our solutions are both within a boundedratio gap of (R/(Rmin · ϵ)) to optimal, where R (resp. Rmin) is the aggregate (resp. minimum) flow rate requirement of all sender-receiver pairs. Hence we pose a similar optimistic note. Simulations based on real-world continent-scale network topology show that the empirical delay gaps observed under practical settings can be much smaller than their theoretical counterparts. In addition, our solutions can achieve over 10% reduction on the maximum delay and average delay simultaneously, only in the cost of losing 3% traffic, as compared to a conceivable delay-aware baseline without traffic loss. Our results can be of particular interest to delay-centric networking applications that can tolerate a small fraction of traffic loss, including cloud video conferencing that recently attracts substantial attention.

We consider a multi-path routing problem of maximizing the aggregate user utility over a multi-hop network, subject to link capacity constraints, maximum end-to-end delay constraints, and user throughput requirements. A user's utility is a concave function of the achieved throughput or the experienced maximum delay. The problem is important for supporting real-time multimedia traffic and is uniquely challenging due to the need of simultaneously considering maximum delay constraints and throughput requirements. In this paper, we first show that it is NP-complete either (i) to construct a feasible solution strictly meeting all constraints, or (ii) to obtain an optimal solution after relaxing either the maximum delay constraints or the throughput requirements. We then develop a polynomial-time approximation algorithm named PASS. The design of PASS leverages a novel understanding between non-convex maximum-delay-aware problems and their convex average-delay-aware counterparts, which can be of independent interest and suggests a new avenue for solving maximum-delay-aware network optimization problems. We prove that PASS always obtains approximate solutions (i.e., with theoretical performance guarantees), at the cost of violating both the maximum delay constraints and the throughput requirements by up to constant ratios. We also develop two variants of PASS, named PASS-M and PASS-T, to generate approximate solutions at the cost of violating either the maximum delay constraints or the throughput requirements by up to problem-dependent ratios. We evaluate our solutions using extensive simulations on Amazon EC2 datacenters supporting video-conferencing traffic. Compared to the existing algorithms and a conceivable baseline, our solutions obtain up to 100% improvement of utilities, by meeting the throughput requirements but relaxing the maximum delay constraints to the extent acceptable for practical video conferencing applications.

Today's automotive engine control systems adopt several control strategies that come with tradeoffs between computational load and performance. The current practice is that the switching speeds at which the engine control system changes control strategy is fixed offline, typically based on the average driving need in a standard driving cycle (i.e., vehicle speed profile over time). This is clearly suboptimal since it fails to capture the variation in the driving cycle, and the actual driving cycle may be considerably different from the standard one. In this paper, we propose to dynamically adjust switching speeds based on the predicted driving cycle. We develop a hybrid set of schedulability analysis techniques to tame the complexity of ensuring the real-time schedulability of engine control tasks. We design an effective and efficient optimization algorithm that provides close-to-optimal solutions. Experimental results demonstrate that our approach efficiently finds dynamic switching speeds that significantly improve engine performance over static ones.

We consider the scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. Our objective is to minimize peak/average Age-of-Information (AoI) subject to throughput requirements. The consideration of batch generation and multi-path communication differentiates our AoI study from existing ones. We first show that our AoI minimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizing AoI and minimizing maximum delay are "roughly" equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any α-approximation algorithm of the maximum delay minimization problem, e.g., the algorithm in [13] with α = 1 + ϵ given any user-defined ϵ > 0, to construct an (α + c)-approximate solution for minimizing AoI. Here c is a constant depending on the throughput requirements. Simulations over various network topologies validate the effectiveness of our approach.

We consider a multiple-unicast network flow problem of maximizing aggregate user utilities under link capacity constraints, maximum delay constraints, and user throughput requirements. A user's utility is a concave function of the achieved throughput or the experienced maximum delay. We first prove that it is NP-complete either (i) to construct a feasible solution meeting all constraints, or (ii) to obtain an optimal solution after we relax maximum delay constraints or throughput requirements. We then leverage a novel understanding between nonconvex maximum-delay-aware problems and their convex average-delay-aware counterparts, and design a polynomial-time approximation algorithm named PASS. PASS achieves constant or problem-dependent approximation ratios, at the cost of violating maximum delay constraints or throughput requirements by up to constant or problem-dependent ratios, under realistic conditions. We empirically evaluate our solutions using simulations of supporting video-conferencing traffic across Amazon EC2 datacenters. Compared to conceivable baselines, PASS obtains up to 100% improvement of utilities, meeting throughput requirements but relaxing maximum delay constraints that are acceptable for video conferencing applications.

In the design optimization of real-time systems scheduled with fixed priority, schedulability analysis is used to define the feasibility region within which tasks meet their deadlines, so that optimization algorithms can find the best solution within the region. However, the complexity of schedulability analysis techniques often makes it difficult to leverage existing optimization frameworks and scale to large designs. In this paper, we propose the concept of unschedulability core, a compact representation of the schedulability conditions, and develop efficient algorithms for its calculation. We present a new optimization framework that leverages such a concept. We show that this concept is applicable to a range of optimization problems, for example, when the decision variables include the task priority assignment and the selection of mechanisms protecting shared buffers. Experimental results on two case studies demonstrate that the new optimization procedure maintains the optimality of the solutions, but is a few orders of magnitude faster than other exact algorithms (branch-and-bound, integer linear programming).

Multicore platforms are becoming increasingly popular in real-time systems. One of the major challenges in designing multicore real-time systems is ensuring consistent and timely access to shared resources. Lock-based protection mechanisms such as MPCP and MSRP have been proposed to guarantee mutually exclusive access in multicore systems at the expense of blocking. In this article, we consider partitioning and scheduling in multicore real-time systems with resource sharing. We first propose a resource-aware task partitioning algorithm for systems with lock-based protection. Wait-free methods, which ensure consistent access to shared memory resources with negligible blocking at the expense of additional memory space, are a suitable alternative when the shared resource is a communication buffer. We propose several approaches to solve the joint problem of task partitioning and the selection of a data consistency mechanism (lock-based or wait-free). The problem is first formulated as an Integer Linear Programming (ILP). For large systems where an ILP solution is not scalable, we propose two heuristic algorithms. Experimental results compare the effectiveness of the proposed approaches in finding schedulable systems with low memory cost and show how the use of wait-free methods can significantly improve schedulability.

We consider the scenario where a source streams a flow at fixed rate to a receiver across a network, possibly using multiple paths. Transmission over a link incurs a delay modeled as a non-negative, non-decreasing and differentiable function of the link aggregated transmission rate. This setting models various practical network communication scenarios. We study network delay optimization concerning two popular metrics, namely maximum delay and average delay experienced by the flow. A well-known pessimistic result says that a flow cannot simultaneously achieve optimal maximum delay and optimal average delay, or even within constant-ratio gaps to the two optimums. In this paper, we pose an optimistic note on the fundamental compatibility of the two delay metrics. Specifically, we design two polynomial-time solutions to deliver (1 -ε) fraction of the flow with maximum delay and average delay simultaneously within 1/ε to the optimums for any ε ∈ (0,1). Hence, the two delay metrics are “largely” compatible. The ratio 1/ε is independent to the network size and link delay function, and we show that it is tight or near-tight. Simulations based on real-world continent-scale network topology verify our theoretical findings. Note that the proposed delay gap 1/ε, upon sacrificing ε fraction of the flow rate, is guaranteed even under the worst theoretical case setting. Our simulation results show that the empirical delay gaps observed under practical settings can be much smaller than 1/ε. Our results are of particular interest to delay-centric networking applications that can tolerate a small fraction of traffic loss, including cloud video conferencing that recently attracts substantial attention.

Priority assignment is a critical issue in the design of real-time systems scheduled with fixed priority. In this paper, we consider the design optimization of a class of such real-time systems, where the schedulability of a task not only depends on the set of higher/lower priority tasks, but also on the response times of other tasks. This makes Audsley's algorithm inapplicable for finding a schedulable priority assignment, not to mention that the design optimization may also involve other metrics such as end-to-end latency in the constraints or objective. The current approaches are to either develop heuristics or use standard exhaustive search algorithms such as Branch-and-Bound (BnB). Instead, we propose a new approach that breaks through the mindset of the current approaches. Our main idea is to introduce the concept of response time estimation range, which is used in place of the actual response time of each task for evaluating the system schedulability. This allows to leverage Audsley's algorithm to generalize from an unschedulable solution to many similar ones. We develop an optimization framework that builds upon such a concept. We then apply the proposed approach to industrial designs of two use cases. One is the real-time wormhole communication in a Network-on-Chip (NoC), where a traffic flow suffers indirect interferences that depend on the response times of higher priority flows. The other is distributed systems with data-driven activation, where a task is triggered by the availability of data, hence by the completion of its immediate predecessor. Experimental results show the proposed technique typically runs several times faster than exhaustive search algorithms based on BnB or Mixed Integer Linear Programming (MILP).

Model-based design using the Simulink modeling formalism and associated toolchain has gained popularity in the development of real-time embedded systems. However, the current research on software synthesis for Simulink models has a critical gap for providing a deterministic, semantics-preserving implementation on multicore architectures with partitioned fixed-priority scheduling. In this paper, we consider a semantics-preservation mechanism that combines (1) the RT blocks from Simulink, and (2) task offset assignment to separate the time windows to access shared buffers by communicating tasks. We study the software synthesis problem that optimizes control performance by judiciously assigning task offsets, task priorities, and task communication mechanisms. We develop a problem-specific exact algorithm that uses an abstraction layer to hide the complexity of timing analysis. Experimental results show that it may run a few orders of magnitude faster than a direct formulation in integer linear programming.

In real-time embedded systems certain tasks are activated according to a rotation source, such as angular tasks in engine control unit triggered whenever the engine crankshaft reaches a specific angular position. To reduce the workload at high speeds, these tasks also adopt different implementations at different rotation speed intervals. However, the current studies limit to the case that the switching speeds at which task implementations should change are configured at design time. In this paper, we propose to study the task model where switching speeds are dynamically adjusted. We develop schedulability analysis techniques for such systems, including a new digraph-based task model to safely approximate the workload from software tasks triggered at predefined rotation angles. Experiments on synthetic task systems demonstrate that the proposed approach provides substantial benefits on system schedulability.

Embedded systems in several domains such as avionics and automotive are subject to inspection from certification authorities. These authorities are interested in verifying the safety-critical aspects of a system and, typically, do not certify non-critical parts. The design of such Mixed-Criticality Systems (MCS) has received increasing attention in recent years. However, although MCS must be designed to overcome transient faults, their susceptibility to transient faults is often overlooked. In this paper, we consider the problem of mapping and scheduling efficient, certifiable MCS that can survive transient faults. We generalize previous MCS models and analysis to support On-Demand Redundancy (ODR). A task set transformation is proposed to generate a modified task set that supports various forms of ODR while satisfying reliability and certification requirements. The analysis is incorporated into a design space exploration algorithm that supports a wide range of fault-tolerance mechanisms and heterogeneous platforms. Experiments show that ODR can improve Quality of Service (QoS) provided to non-critical tasks by 29 percent on average, compared to lockstep execution. Moreover, combining several fault-tolerance mechanisms can lead to additional improvements in schedulability and QoS.

Modern embedded systems, such as automotive, are physically distributed with an increasing number of microcontrollers and buses. They support complex functions such as active safety and autonomous driving features with a high degree of data dependencies. The most common configuration uses periodic activation of tasks and messages coupled with priority-based scheduling. Selecting task and message parameters so that end-to-end deadlines are met can be very challenging, since such deadlines are enforced across a set of microcontrollers and buses. In this paper, we address the problem of optimal selection of task and message activation periods and priorities. Existing approaches cannot scale to large designs and have to settle to optimize period or priority separately, largely due to the complexity of response time analysis techniques. Instead, we present a new, unified framework that simultaneously optimizes period and priority assignment. It avoids the pitfalls of existing approaches by abstracting the response time calculation with the new concept of maximal unschedulable period and deadline assignment. We demonstrate with two industrial case studies that our approach runs magnitudes faster than existing approach on period optimization, while providing substantially better solutions.

We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-complete; thus exact solution is computational prohibited unless P = NP. We then design a fully polynomial time approximation scheme (FPTAS) to solve it. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a heuristic with much lower complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared with a fastest path (resp. shortest path) algorithm adapted from common practice.

Due to their safety-critical nature, cyber-physical systems (CPS) must tolerate faults and security attacks to remain fail-operational. However, conventional techniques for improving safety, such as testing and validation, do not meet this requirement, as shown by many of the real-world system failures in recent years, often with major economic and public-safety implications. We aim to improve the safety of critical CPS through synthesis of runtime enforcers, named safety guards, which are reactive components attached to the original systems to protect them against catastrophic failures. That is, even if the system occasionally malfunctions due to unknown defects, transient errors, or malicious attacks, the guard always reacts instantaneously to ensure that the combined system satisfies a predefined set of safety properties, and the deviation from the original system is kept at minimum. We illustrate the main ideas of this approach with examples, discuss the advantages compared to existing approaches, and point out some research challenges.

In the design optimization of real-time systems, the schedulability analysis is used to define the feasibility region within which tasks meet their deadlines, so that optimization algorithms can find the best solution within the region. However, the complexity of current schedulability analysis techniques often makes it difficult to leverage existing optimization frameworks and scale to large designs. In this paper, we consider the design optimization problems for real-time systems scheduled with fixed priority, where task priority assignment is part of the decision variables. We propose the concept of unschedulability core, a compact representation of the schedulability conditions, and develop efficient algorithms for its calculation. We present a new optimization procedure based on lazy constraint paradigm that leverages such a concept. Experimental results on two case studies show that the new optimization procedure provides optimal solutions, but is a few magnitudes faster than other exact algorithms (Branch-and-Bound, Integer Linear Programming).

The Controller Area Network with Flexible Data-Rate (CAN-FD) is a new communication protocol to meet the bandwidth requirements for the constantly growing volume of data exchanged in modern vehicles. The problem of frame packing for CAN-FD, as studied in the literature, assumes a single sub-system where one CAN-FD bus serves as the communication medium among several Electronic Control Units (ECUs). Modern automotive electronic systems, on the other hand, consist of several sub-systems, each facilitating a certain functional domain such as powertrain, chassis and suspension. A substantial fraction of all signals is exchanged across sub-systems. In this work, we study the frame packing problem for CAN-FD with multiple sub-systems, and propose a two-stage optimization framework. In the first stage, we pack the signals into frames with the objective of minimizing the bandwidth utilization. In the second stage, we extend Audsley's algorithm to assign priorities/identifiers to the frames. In case the resulting solution is not schedulable, our framework provides a potential repacking method. We propose two solution approaches: (a) an Integer Linear Programming (ILP) formulation that provides an optimal solution but is computationally expensive for industrial-size problems; and (b) a greedy heuristic that scales well and provides solutions that are comparable to optimal solutions. Experimental results show the efficiency of our optimization framework in achieving feasible solutions with low bandwidth utilization. The results also show a significant improvement over the case when there is no cross-domain consideration (as in prior work).

Today's Cyber-Physical Systems (CPS) are typically distributed over several computing nodes communicated through buses such as Controller Area Network (CAN). Their control performance gets degraded due to variable delays incurred by messages on the shared CAN bus. This paper presents a novel online delay prediction method that predicts the message delay at runtime based on real-time traffic information on CAN. It leverages the proposed method to improve control quality, by compensating the message delay in the Model Predictive Control (MPC) algorithm design. It demonstrates that the delay prediction is accurate, and the MPC design which takes the message delay into consideration performs considerably better. It also implements the proposed method on an 8-bit 16MHz ATmega328P microcontroller and measures the execution time overhead. The results clearly indicate that the method is computationally feasible for online usage.

We study a delay-sensitive information flow problem where a source streams information to a sink over a directed graph G = (V, E) at a fixed rate R possibly using multiple paths to minimize the maximum end-to-end delay, denoted as the Min-Max-Delay problem. Transmission over an edge incurs a constant delay within the capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay, with time complexity O(log(Ndmax)(N5dmax2.5)(log R + N2dmaxlog(N2dmax))), where N =△max{|V|, |E|} and dmaxis the maximum edge delay. Besides, we show that the integrality gap, which is defined as the ratio of the maximum delay of an optimal integer flow to the maximum delay of an optimal fractional flow, could be arbitrarily large.

Controller Area Network (CAN) is a widely used protocol that allows communication among Electronic Control Units (ECUs) in automotive electronics. It was extended to CAN-FD (CAN with Flexible Data-rate) to meet the increasing demand for bandwidth utilization caused by the growing number of features in modern automobiles. The signal-to-frame packing problem has been studied in literature for both CAN and CAN-FD. In this work, we propose and formulate, for the first time, the signal offset assignment problem (SOAP) in a frame in order to improve the bus bandwidth utilization. We prove that SOAP is NP-complete. We propose a general approximation framework (GAF) for SOAP which can use any approximation algorithm for the makespan minimization problem (MMP) in multiprocessor systems. We derive the performance guarantee provided by GAF as a function of the performance guarantee of the approximation algorithm for MMP and the number of signal periods in the frame. We demonstrate the efficacy of our approach through experiments using three different algorithms (two approximation algorithms and an integer linear programming formulation) for MMP in GAF. Our results indicate that by using offsets for signals in frame packing schemes, one can achieve about 10.54% improvement in bandwidth utilization (on a single bus) in CAN-FD systems.

This paper considers the problem of design optimization for real-time systems scheduled with fixed priority, where task priority assignment is part of the decision variables, and the timing constraints and/or objective function linearly depend on the exact value of task response times (such as end-to-end deadline constraints). The complexity of response time analysis techniques makes it difficult to leverage existing optimization frameworks and scale to large designs. Instead, we propose an efficient optimization framework that is three magnitudes (1,000×) faster than Integer Linear Programming (ILP) while providing solutions with the same quality. The framework centers around three novel ideas: (1) An efficient algorithm that finds a schedulable task priority assignment for minimizing the average worst-case response time; (2) The concept of Maximal Unschedulable Deadline Assignment (MUDA) that abstracts the schedulability conditions, i.e., a set of maximal virtual deadline assignments such that the system is unschedulable; and (3) A new optimization procedure that leverages the concept of MUDA and the efficient algorithm to compute it.

Model-based design using Synchronous Reactive (SR) models is becoming widespread for control software development in industry. However, software synthesis is challenging for multi-rate SR models consisting of blocks modeled with finite state machines, due to the complexity of validating the system’s real-time schedulability. The existing approach uses the simplified periodic task model to allow an efficient schedulability analysis, which leads to pessimistic and suboptimal solutions. Instead, in this paper, we adopt a more accurate but more complex schedulability analysis. We develop several optimization techniques to improve the algorithm’s efficiency. Experimental results on synthetic systems and an industrial case study show that the proposed optimization framework preserves the solution optimality but is much faster (e.g., 1000× for systems with 15 blocks) than the branch-and-bound algorithm, and it generates better control software than the existing approach.

Model-based design using Synchronous Reactive (SR) models enables early design and verification of application functionality in a platform-independent manner, and the implementation on the target platform should guarantee the preservation of application semantic properties. Mixed-Criticality Scheduling (MCS) is an effective approach to addressing diverse certification requirements of safety-critical systems that integrate multiple subsystems with different levels of criticality. This article considers fixed-priority scheduling of mixed-criticality SR models, and considers two scheduling approaches: Adaptive MCS and Elastic MCS. We formulate the optimization problem of minimizing the total system cost of added functional delays in the implementation while guaranteeing schedulability, and present an optimal algorithm based on branch-and-bound search, and an efficient heuristic algorithm.

Increasing the throughput by balancing the traffic load through the whole network is important for the transportation system. User optimal routing service usually results in congestions in the bottleneck links. On the other hand, individual travelers typically have delay constraints to satisfy, which might be ignored in the system optimum. In this work, we look into the traffic assignment problem in the stochastic network, considering the maximum delay constraint, so that any route suggested by the system optimal traffic assignment does not incur a delay longer than the constraint in most cases. We formulate the Stochastic Delay Constrained Maximum Flow problem (SDCMF), and prove that it is NP- Complete. The delay aware algorithms are proposed to solve the SDCMF problem, which not only find a set of paths with maximum flow, but also consider the delay of each path.

Multicore processors are increasingly adopted in resource-constrained real-time embedded applications. In the development of such applications, efficient use of RAM memory is as important as the effective scheduling of software tasks. Preemption Threshold Scheduling (PTS) is a well-known technique for controlling the degree of preemption, possibly improving system schedulability, and to reduce system stack usage. In this paper, we consider partitioned multi-processor scheduling on a multicore processor with either Fixed-Priority or Earliest Deadline First scheduling algorithms with PTS and address the design optimization problem of mapping tasks to processor cores and assignment of task priorities and preemption thresholds with the optimization objective of minimizing system stack usage. We present both optimal solution techniques based on Mixed Integer Linear Programming and efficient heuristic algorithms that can achieve high-quality results. We perform extensive performance evaluations using both synthetic tasksets and industrial case studies.

Automotive in-vehicle systems are distributed systems consisting of multiple ECUs (Electronic Control Units) interconnected with a broadcast network such as FlexRay. Message authentication is an effective mechanism to prevent attackers from injecting malicious messages into the network. In order to reduce timing interference of message authentication operations on application tasks, hardware coprocessors in the form of either FPGA or ASIC are adopted to offload computation-intensive cryptographic algorithms from the ECU. However, it may not be feasible or desirable to equip every ECU with a hardware coprocessor, as modern vehicles can contain more than one hundred ECUs, and the automotive industry is cost-sensitive. In this paper, we consider the problem of mapping an application task graph onto a FlexRay-based distributed hardware platform, to meet security and deadline requirements while minimizing the number of hardware coprocessors needed in the system. We present a Mixed Integer Linear Programming (MILP) formulation, a divide-and-conquer heuristic algorithm, and a Simulated Annealing algorithm. We evaluate the algorithms with industrial case studies.

Memory is a limited resource in cost-sensitive, resource-constrained embedded applications. Preemption Threshold Scheduling (PTS) is a well-known technique for reducing the system stack size requirement. We consider Global Fixed Priority Scheduling with Preemption Threshold (gFPPT), as integration of PTS with global Fixed-Priority scheduling on a homogeneous multiprocessor platform, and formulate the optimization problem of minimizing the system stack size requirement while guaranteeing schedulability. We present schedulability analysis, optimization algorithms for priority and preemption threshold assignment, and an ILP formulation for computing system stack size requirement. Performance evaluation shows that the system stack size requirement can be reduced significantly with gFPPT compared to preemptive scheduling.

Mixed Criticality Systems (MCS) have gained increasing interest in the past few years due to their industrial relevance. When mixed-criticality systems are implemented on multicore architectures, several challenges arise such as the efficient partitioning of these systems. In this paper, we address this issue by presenting a novel mixed-criticality partitioning algorithm, the Dual-Partitioned Mixed-Criticality (DPM) algorithm, that allows limited migration of LO-criticality tasks to enhance the efficiency of the partitioning while maintaining many of the advantages of partitioned systems. Experimental results show that DPM consistently outperforms existing mixed-criticality partitioning algorithms, for example, at utilizations of 0.8 or higher, DPM is able to schedule 17% more systems.

For preemptive scheduling with shared cache, different tasks may cause interference in the shared cache, leading to Cache-Related Preemption Overhead (CRPD). Cache partitioning is a well-known technique for mitigating unpredictable cache interference in preemptive scheduling, but it reduces cache space available to each task, causing an increase in task execution time. Non-preemptive scheduling algorithms do not incur CRPD, but they generally have poor schedulability. Preemption Threshold Scheduling (PTS) is an effective approach to strike a balance between preemptive and non-preemptive scheduling. We propose integration of cache partitioning and PTS to optimize schedulability on a uniprocessor. We force each subset of tasks assigned the same cache partition to be a non-preemptive group, by assigning the same PT to all tasks in the subset that is equal to or higher than the highest priority of the tasks in that subset. This eliminates CRPD within each cache partition, and helps to improve schedulability. We present an ILP formulation as well as an efficient heuristic algorithm.

Multicores are today used in automotive, controls and avionics systems supporting real-time functionality. When real-time tasks allocated on different cores cooperate through the use of shared communication resources, they need to be protected by mechanisms that guarantee access in a mutual exclusive way with bounded worst-case blocking time. Lock-based mechanisms such as MPCP and MSRP have been developed to fulfill this demand, and research papers are today tackling the problem of finding the optimal task placement in multicores while trying to meet the deadlines against blocking times. In this paper, we propose a resource-aware task allocation algorithm for systems that use MSRP to protect shared resources. Furthermore, we leverage the additional opportunity provided by wait-free methods as an alternative data consistency mechanism for the case that the shared resource is communication or state memory. An algorithm that performs both task allocation and data consistency mechanism (MSRP or wait-free) selection is proposed. The selective use of wait-free methods can significantly extend the range of schedulable systems at the cost of memory.

Idling, or running the engine when the vehicle is not moving, accounts for 13%-23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics μB- and qB+, the expected length of short stops and the probability of long stops. We develop two online algorithms, a suboptimal closed-form algorithm and an optimal numerical solution, that combine the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the algorithms perform better than existing solutions in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

In a mixed-criticality system, multiple tasks with different levels of criticality may coexist on the same hardware platform. The scheduling algorithm EDF-VD (Earliest Deadline First with Virtual Deadlines) has been proposed for mixed-criticality systems, which assumes tasks do not share any common resources. We present MC-SRP (Mixed-Criticality Stack Resource Policy), a resource synchronization protocol for EDF-VD, which allows resource sharing among tasks at the same criticality level and guarantees that each task is blocked at most once in each criticality mode. In addition, we present MC-SRPT (MC-SRP with Thresholds) for reducing the application stack size requirement in resource-constrained embedded systems.

Idling, or running the engine when the vehicle is not moving, accounts for 13% - 23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics μB− and qB+, the expectation of short stops' lengths and the probability of long stops. We develop an online algorithm that combines the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the robustness of the algorithm in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

Multicore platforms are increasingly used in realtime embedded applications. In the development of such applications, an efficient use of RAM memory is as important as the effective scheduling of software tasks. Preemption Threshold Scheduling is a well-known technique for controlling the degree of preemption, possibly improving system schedulability, and allowing savings in stack space. In this paper, we target at the optimal mapping of tasks to cores and the assignment of the scheduling parameters for systems scheduled with preemption thresholds. We formulate the optimization problems using Mixed Integer Linear Programming framework, and propose an efficient heuristic as an alternative. We demonstrate the efficiency and quality of both approaches with extensive experiments using random systems as well as two industrial case studies.

In this paper, we propose SAFE (Security Aware FlexRay scheduling Engine), to provide a problem definition and a design framework for FlexRay static segment schedule to address the new challenge on security. From a high level specification of the application, the architecture and communication middleware are synthesized to satisfy security requirements, in addition to extensibility, costs, and end-to-end latencies. The proposed design process is applied to two industrial case studies consisting of a set of active safety functions and an X-by-wire system respectively.

The growing awareness about global climate change has boosted the need to mitigate greenhouse gas emissions from existing power systems and spurred efforts to accelerate the integration of renewable energy sources (e.g. wind and solar power) into the electrical grid. A fundamental difficulty here is that renewable energy sources are usually of high variability. The electrical grid must absorb this variability through employing many additional operations (e.g., operating reserves, energy storage), which will largely raise the cost of electricity from renewable energy sources. To make it affordable, numerous advancements in technologies and methods for the smart grid are required. In this paper, we will confine ourselves to one of them: how to plan the construction of wind farms with high capacity and low variability locally and distributedly. We first study the characteristics of both wind resources and wind turbines and present a more accurate wind power evaluation method based on Gaussian Regression. Then, we analyze a trade-off between wind power's quantity and quality and propose an approach to optimally combine different types of wind turbines to balance the trade-off for a specific site. Finally, we explore geographical diversity among different sites and develop an extended approach that jointly optimizes the combination of sites and turbine types. Extensive experiments using the realistic historical wind resource data are conducted for either of the local and distributed case. Encouraging results are shown for the proposed approaches and some interesting insights are also provided.

The adoption of AUTOSAR and Model Driven Engineering (MDE) for the design of automotive software architectures allows an early analysis of system properties and the automatic synthesis of architecture and software implementation. To select and configure the architecture with respect to timing constraints, knowledge about the worst case execution times (WCET) of functions is required. An accurate evaluation of the WCET is only possible when reusing legacy functionality or very late in the development and procurement process. To drive the integration of SW components belonging to systems with timing constraints, automotive methodologies propose to assign WCET budgets to functions. This paper presents two solutions to assign budgets, while considering at the same time the problem of SW/HW synthesis. The first solution is a one-step algorithm. The second is an iterative improvement procedure with a staged approach that scales better to very large size systems. Both methods are evaluated on industrial systems to study their effectiveness and scalability.

The need to reduce greenhouse gases from our current power systems accelerates the integration of renewable energy sources (for example, wind and solar power). A fundamental difficulty is that renewable energy is usually of high variability. Numerous advancements in technologies and methods for the smart grid are required to mitigate and absorb this variability. In this paper, we focus on one of them: how to plan wind farms with high capacity and low variability locally and distributedly. First, we study the characteristics of both wind resource and wind turbines and propose a novel wind power estimation method based on Gaussian regression. The experimental result shows that our method achieves a more accurate estimation compared to other ones and has a nearly zero error for most of the turbine types. Then, we analyze a tradeoff between wind power's quantity and quality for large-scale wind farms, and find that there is an optimal turbine type for each location as to either the quantity or the quality. We propose an approach to optimally combine different types of wind turbines to balance the tradeoff. Finally, we explore geographical diversity among different locations and develop an extended approach that jointly optimizes the combination of locations and turbine types. Besides applying to plan new wind farms, we also discuss how to adapt the two approaches to decide an upgrade plan for a wind farm and a network of wind farms, respectively. We conduct extensive experiments using two different wind resource data traces for both local and distributed cases. The result shows that the proposed approaches significantly outperform those approaches using a single turbine type and those separately optimizing locations and turbine types. We also provide interesting insights about the quantity-quality balancing.

In the development of real-time embedded applications, especially those on systems-on-chip, an efficient use of RAM memory is as important as the effective scheduling of the computation resources. The protection of communication and state variables accessed by concurrent tasks must provide real-time schedulability guarantees while using the least amount of memory. Several schemes, including preemption thresholds, have been developed to improve schedulability and save stack space by selectively disabling preemption. However, the design synthesis problem is still open. In this article, we target the assignment of the scheduling parameters to minimize memory usage for systems of practical interest, including designs compliant with automotive standards. We propose algorithms either proven optimal or shown to improve on randomized optimization methods like simulated annealing.

Multicore platforms are increasingly used in real-time embedded applications. In control systems, including automotive, avionics, and automation, resources shared by tasks on different cores need to be protected by mechanisms that guarantee access in a mutually exclusive way with bounded worst case blocking time. The evaluation of the tradeoffs among the possible protocols for mutual exclusion requires an estimate of their implementation overheads. In this paper, we summarize the possible protection mechanisms and provide code implementations in real-time operating systems executing on a multicore platform. We discuss the tradeoffs among the different mechanisms based on experimental evaluation of their memory and timing overheads as well as their impact on system schedulability. We propose a heuristic algorithm to select the optimal combination of mechanisms for shared resources in systems with time constraints to minimize their memory requirements. The effectiveness of the optimization procedure is demonstrated by synthetic systems as well as industrial case studies.

Mixed-Criticality Scheduling (MCS) is an effective approach to addressing diverse certification requirements of safety-critical systems that integrate multiple subsystems with different levels of criticality. Preemption Threshold Scheduling (PTS) is a well-known technique for controlling the degree of preemption, ranging from fully-preemptive to fully-non-preemptive scheduling. We present schedulability analysis algorithms to enable integration of PTS with MCS, in order to bring the rich benefits of PTS into MCS, including minimizing the application stack space requirement, reducing the number of runtime task preemptions, and improving schedulability.

Model-based design using synchronous reactive (SR) models is widespread for the development of embedded control software. SR models ease verification and validation, and enable the automatic generation of implementations. In SR models, synchronous finite state machines (FSMs) are commonly used to capture changes of the system state under trigger events. The implementation of a synchronous FSM may be improved by using multiple software tasks instead of the traditional single-task solution. In this work, we propose methods to quantitatively analyze task implementations with respect to a breakdown factor that measures the timing robustness, and an action extensibility metric that measures the capability to accommodate upgrades. We propose an algorithm to generate a correct and efficient task implementation of synchronous FSMs for these two metrics, while guaranteeing the schedulability constraints.

Several models have been proposed to represent conditional executions and dependencies among real-time concurrent tasks for the purpose of schedulability analysis. Among them, task graphs with cyclic recurrent behavior, i.e., those modeled with a single source vertex and a period parameter specifying the minimum amount of time that must elapse between successive activations of the source job, allow for efficient schedulability analysis based on the periodicity of the request and demand bound functions (em rbf and dbf). We leverage results from max-plus algebra to identify a recurrent term in rbf and dbf of general task graph models, even when the execution is neither recurrent nor controlled by a period parameter. As such, the asymptotic complexity of calculating rbf and dbf is independent from the length of the time interval. Experimental results demonstrate significant improvements on the runtime for system schedulability analysis.

The synchronization of accesses to shared memory buffers in multi-core platforms can be realized through lock-based synchronization protocols. If the embedded application executing on the system has hard real-time constraints, the worst-case blocking times for accessing remotely shared resources can negatively impact the schedulability guarantee. In this case, wait-free communication protocols can be an effective alternative. In addition, in a model-based development process, wait-free buffers allow the realization of communication that provably preserves the signal flows and guarantees a correct implementation. Flow-preserving wait-free communication primitives require (in the general case) the execution of buffer updates procedures at task activation time, either by the kernel or by a hook procedure executing at the highest priority level. To minimize the interference of such procedures on the application-level tasks, we present and evaluate an FPGA implementation. Our FPGA implementation is compared with implementations of lock-based policies in terms of memory, time, and area overhead.

The Controller Area Network (CAN) bus is widely used and has been studied in several research works to determine the worst-case response time of messages. More results are being added to study systems that are not constructed according to the ideal behavior of the message queuing and CAN controller assumed in the past. In this paper, we provide an assessment on the practical relevance of several of those results. We also present theory and empirical studies on the relative importance of several implementation issues that are quite common in real systems and further deviate from the ideal behavior. In addition, we propose a heuristic for the design of multiple software queues when using TxObjects without preemption, and derive an upper bound on the worst case response time when message output at the CAN driver is polling based.

Modern development methodologies from the industry and the academia for complex real-time systems define a stage in which application functions are deployed onto an execution platform. The deployment consists of the placement of functions on a distributed network of nodes, the partitioning of functions in tasks and the scheduling of tasks and messages. None of the existing optimization techniques deal with the three stages of the deployment problem at the same time. In this paper, we present a staged approach towards the efficient deployment of real-time functions based on genetic algorithms and mixed integer linear programming techniques. Application to case studies shows the applicability of the method to industry-size systems and the quality of the obtained solutions when compared to the true optimum for small size examples.

Real-Time Calculus (RTC) is a modular performance analysis framework for real-time embedded systems. It can be used to compute the worst-case and best-case response times of tasks with general activation patterns and configurations, such as pipelines of tasks that are connected via finite buffers. In this paper, we extend the existing RTC framework to analyze arbitrary graph configurations of tasks and messages, with mixed periodic and event-based activation models and finite buffers between any pair of nodes. Our extension also improves upon several sources of pessimism in the existing analysis. We present an application of the extended RTC to the Loosely Time-Triggered Architecture (LTTA) implementation of synchronous models, commonly used in the development of embedded automotive, avionics and control systems. We show how our method can be used to model scheduling and communication delays in an LTTA mapping, which gives tighter analysis bounds on the output rate and the latency compared to existing techniques. The evaluation on automotive workloads shows that our approach is scalable and outperforms existing techniques in terms of analysis accuracy.

In mixed-criticality systems, multiple subsystems with different levels of criticality may co-exist on the same hardware platform. Many scheduling algorithms have been proposed to achieve certification at multiple levels of criticality. However, current MCS algorithms and analysis techniques generally assume tasks are independent, i.e., they do not share data that need to be protected with synchronization mechanisms like mutexes or semaphores. In this paper, we address this limitation by presenting an extension to the Stack Resource Protocol (SRP), called Mixed-Criticality-SRP (MC-SRP). Moreover, preemption-threshold scheduling is a well-known technique for reducing stack space size and enhance schedulability in resource-constrained embedded systems.We also present the integration of preemption-thresholds into EDF-based mixed-criticality scheduling (MCS) algorithms, and develop the schedulability analysis methods to such systems.

In the design of time-critical applications, schedulability analysis is used to define the feasibility region of tasks with deadlines, so that optimization techniques can find the best design solution within the timing constraints. The formulation of the feasibility region based on the response time calculation requires many integer variables and is too complex for solvers. Approximation techniques have been used to define a convex subset of the feasibility region, used in conjunction with a branch and bound approach to compute suboptimal solutions for optimal task period selection, priority assignment, or placement of tasks onto CPUs. In this paper, we provide an improved and simpler real-time schedulability test that allows an exact and efficient definition of the feasibility region in Mixed Integer Linear Programming (MILP) optimization. Our method requires a significantly smaller number of binary variables and is viable for the treatment of industrial-size problem, as shown by the experiments.

Model-based design of embedded control systems using Synchronous Reactive (SR) models is among the best practices for software development in the automotive and aeronautics industry. SR models allow to formally verify the correctness of the design and to automatically generate the implementation code. This improves productivity and, more importantly, can ensure a correct software implementation (preserving the model semantics). Previous research focuses on the concurrent implementation of the dataflow part of SR models, including the optimization of the block-to-task mapping and communication buffer sizing. When the system also consists of blocks implementing finite state machines, as in modern modeling tools like Simulink and SCADE, the task implementation can be further optimized with respect to time and memory. In this paper we analyze problems and opportunities in the implementation of finite state machine subsystems. We define the constraints and efficient policies for the task implementation of such systems.

Model-based design of embedded systems using Synchronous Reactive (SR) models is among the best practices for software development in the automotive and aeronautics industry. The correct implementation of an SR model must guarantee the synchronous assumption, that is, all the system reactions complete before the next event. This assumption can be verified using schedulability analysis, but the analysis can be quite challenging when the system also consists of blocks implementing finite state machines, as in modern modeling tools like Simulink and SCADE. In this paper, we discuss the schedulability analysis of such systems, including the applicability of traditional task analysis methods and an algorithmic solution to compute the exact demand and request bound functions. In addition, we define conditions for computing these functions using a periodic recurrent term, even when there is no cyclic recurrent behavior in the model.

In the development of some real-time embedded applications, especially systems-on-chip, an efficient use of RAM memory is as important as the effective scheduling of the computation resources. The design problem is to find a schedulable solution that fits within the memory budget. In a real-time concurrent system, preemption plays an important role in the exploration of these tradeoffs. Several schemes, including preemption thresholds and non-preemption groups, have been developed to improve schedulability and saving stack memory space by selectively disabling preemption. However, the design synthesis problem for such systems and protocols is still an open problem. We target at the efficient assignment of the scheduling parameters for systems scheduled according to these policies in several cases of practical interest, including those that are compliant with automotive standards.

The complexity and physical distribution of modern active safety, chassis, and powertrain automotive applications requires the use of distributed architectures. Complex functions designed as networks of function blocks exchanging signal information are deployed onto the physical HW and implemented in a SW architecture consisting of a set of tasks and messages. The typical configuration features priority-based scheduling of tasks and messages and imposes end-to-end deadlines. In this work, we present and compare formulations and procedures for the optimization of the task allocation, the signal to message mapping, and the assignment of priorities to tasks and messages in order to meet end-to-end deadline constraints and minimize latencies. Our formulations leverage worst-case response time analysis within a mixed integer linear optimization framework and are compared for performance against a simulated annealing implementation. The methods are applied for evaluation to an automotive case study of complexity comparable to industrial design problems.

FlexRay is a new high-bandwidth communication protocol for the automotive domain, providing support for the transmission of time-critical periodic frames in a static segment and priority-based scheduling of event-triggered frames in a dynamic segment. The design of a system scheduling with communication over the FlexRay static segment is not an easy task because of protocol constraints and the demand for extensibility and flexibility. We study the problem of the ECU and FlexRay bus scheduling synthesis from the perspective of the application designer, interested in optimizing the scheduling subject to timing constraints with respect to latency- or extensibility-related metric functions. We provide solutions for a task and signal scheduling problem, including different task scheduling policies based on existing industry standards. The solutions are based on the Mixed-Integer Linear Programming optimization framework. We show the results of the application of the method to case studies consisting of an X-by-wire system on actual prototype vehicles.

In the current environment of rapidly changing in-vehicle requirements and ever-increasing functional content for automotive EE systems, there are several sources of uncertainties in the definition of EE architecture design. This is also true for communication schedule synthesis where key decisions are taken early because of interactions with the suppliers. The possibility of change necessitates a design process that can analyze schedules for robustness to uncertainties, e.g., changes in estimated task durations or communication load. A robust design would be able to accommodate these changes incrementally without changes in the system scheduling, thus reducing validation times and increasing reusability. This paper introduces a novel approach based on the info-gap decision theory that provides a systematic scheme for analyzing robustness of schedules by computing the greatest horizon of uncertainty that still satisfies the performance requirements. The paper formulates info-gap models for potential uncertainties in schedule synthesis for a distributed automotive system communicating over a FlexRay network, and shows their application to a case study.

In the design of time-critical applications, schedulability analysis can be used to define the feasibility region of tasks so that optimization techniques can find the best design solution that satisfies the deadlines. This method has been applied to obtain the optimal task implementation, priority assignment or placement of tasks onto CPUs in previous work. The definition of the feasibility region based on response time calculation requires many integer variables and is too complex for solvers. Approximation techniques have been used to define a convex subset of the feasibility region, often used in conjunction with branch and bound to compute sub-optimal solutions. In this paper, we provide an improved and simpler feasibility analysis method that allows an exact definition of the feasibility region in Mixed Integer Linear Programming (MILP) optimization methods. The encoding of the feasibility region using our method requires a significantly smaller number of binary variables and is viable for the treatment of industrial-size problems as shown by the experiments.

This work describes methods for the analysis of CAN message traces to identify the configuration of systems with a missing or incomplete message set specification, and also to detect the cause and find the possible remedy to timing faults or non-ideal timing behaviors. Based on the message id and time stamp recorded at a tracing node by a bus probe, the analysis reconstructs the expected message arrival time at the source node and detects the queuing and transmission policies used at the middleware- and driver-level by the supplier of each node. We show the application of our analysis method to two automotive case studies. In the first, a timing fault is analyzed and its causes are detected. In the second, the objective is to identify the message set and its configuration when this information is not available.

Model-based design of embedded control systems using Synchronous Reactive (SR) models is among the best practices for software development in the automotive and aeronautic industry. SR models allow to formally verify the correctness of the design and automatically generate the implementation code. This feature is a major productivity enhancement and, more importantly, can ensure correct-by-design software provided that the code generator is provably correct. This paper presents an improvement of code generation technology for SR obtained via a novel algorithm for optimizing the multitask implementation of Simulink models on single-processor platforms with limited availability of memory. Existing code generation tools require the addition of zero-order hold (ZOH) blocks, and therefore additional memory, and possibly also additional functional delays whenever there is a rate transition in the computation and communication flow. Our algorithm leverages a novel efficient encoding of the scheduling feasibility region to find the task implementation of function blocks with minimum additional functional delays within timing and memory constraints. The algorithm is applied to an automotive case study with tens of function blocks and very high utilization to test its applicability to complex systems.

Automotive electrical/electronic (E/E) architectures need to be evaluated and selected based on the estimated performance of the functions deployed on them before the details of these functions are known. End-to-end delays of controls must be estimated using incomplete and aggregate information on the computation and communication load for ECUs and buses. We describe the use of statistical analysis to compute the probability distribution of Controller Area Network (CAN) message response times when only partial information is available about the functionality and architecture of a vehicle. We provide results compared to simulations as well as trace data. These results demonstrate that our statistical inference can be used for predicting the distribution of the response time of a CAN message, once its priority has been assigned, from limited information such as the bus utilization of higher priority messages.

FlexRay is a new communication protocol for automotive systems, providing support for transmission of periodic messages in static segments and priority-based scheduling of event-triggered messages in dynamic segments. The design of a FlexRay schedule is not an easy task because of protocol constraints and demands for extensibility and flexibility. We study the problem of FlexRay bus scheduling from the perspective of the application designer, interested in optimizing the performance of application related timing metrics or extensibility. We provide solutions for different task scheduling policies on existing industry standards based on a mixed integer linear programming (MILP) framework.

Many automotive applications, including most of those developed for active safety and chassis systems, must comply with hard real-time deadlines, and are also sensitive to the average latency of the end-to-end computations from sensors to actuators. A characterization of the timing behavior of functions is used to estimate the quality of an architecture configuration in the early stages of architecture selection. In this paper, we extend previous work on stochastic analysis of response times for software tasks to controller area network messages, then compose them with sampling delays to compute probability distributions of end-to-end latencies. We present the results of the analysis on a realistic complex distributed automotive system. The distributions predicted by our method are very close to the probability of latency values measured on a simulated system. However, the faster computation time of the stochastic analysis is much better suited to the architecture exploration process, allowing a much larger number of configurations to be analyzed and evaluated.

The large variety of architectural dimensions in automotive electronics design, for example, bus protocols, number of nodes, sensors and actuators interconnections and power distribution topologies, makes architecture design task a very complex but crucial design step especially for OEMs. This situation motivates the need for a design environment that accommodates the integration of a variety of models in a manner that enables the exploration of design alternatives in an efficient and seamless fashion. Exploring these design alternatives in a virtual environment and evaluating them with respect to metrics such as cost, latency, flexibility and reliability provide an important competitive advantage to OEMs and help minimize integration risks later in the design cycle. In particular, the choice of the degree of decentralization of the architecture has become a crucial issue in automotive electronics. In this paper, we demonstrate how a rigorous methodology (platform-based design) and the Metropolis framework can be used to find the balance between centralized and decentralized architectures