5G is expected to support ultra-reliable low latency communication to enable real-time applications such as industrial automation and control. 5G configured grant (CG) scheduling features a pre-allocated periodicity-based scheduling approach which reduces control signaling time and guarantees service quality. Although this enables 5G to support hard real-time periodic traffics, efficiently synthesizing the schedule and achieving high resource efficiency while serving multiple traffics, is still an open problem. To address this problem, we first formulate it using satisfiability modulo theories (SMT) so that an SMT-solver can be used to generate optimal solutions. For enhancing scalability, two efficient heuristic approaches are proposed. The experiments demonstrate the effectiveness and scalability of the proposed technique.

Deep neural network (deepnet) applications play a crucial role in safety-critical systems such as autonomous vehicles (AVs). An AV must drive safely towards its destination, avoiding obstacles, and respond quickly when the vehicle must stop. Any transient errors in software calculations or hardware memory in these deepnet applications can potentially lead to dramatically incorrect results. Therefore, assessing and mitigating any transient errors and providing robust results are important for safety-critical systems. Previous research on this subject focused on detecting errors and then recovering from the errors by re-running the network. Other approaches were based on the extent of full network duplication such as the ensemble learning-based approach to boost system fault-tolerance by leveraging each models advantages. However, it is hard to detect errors in a deep neural network, and the computational overhead of full redundancy can be substantial. We first study the impact of the error types and locations in deepnets. We next focus on selecting which part should be duplicated using multiple ranking methods to measure the order of importance among neurons. We find that the duplication overhead for computation and memory is a tradeoff between algorithmic performance and robustness. To achieve higher robustness with less system overhead, we present two error protection mechanisms that only duplicate parts of the network from critical neurons. Finally, we substantiate the practical feasibility of our approach and evaluate the improvement in the accuracy of a deepnet in the presence of errors. We demonstrate these results using a case study with real-world applications on an Nvidia GeForce RTX 2070Ti GPU and an Nvidia Xavier embedded platform used by automotive OEMs.

Time-Sensitive Networking (TSN) is a set of IEEE 802.1 technologies that support real-time and reliable Ethernet communication, commonly used in automotive and industrial automation systems. Time-aware scheduling is adopted in TSN to achieve high temporal predictability. In this paper, we demonstrate that such a scheduling solution alone does not always meet all timing requirements and must be combined with network preemption support. We propose an SMT-based synthesis method for preemptive time-triggered scheduling and routing in TSN. Our experiments demonstrate that schedulability is improved significantly when using frame preemption compared to a standard time-triggered message scheduling approach.

Due to their real-time constraints and high predictability requirements, safety-critical automotive applications are often implemented using time-triggered communication scheduling, which is supported in the Time-Sensitive Networking (TSN) standards. Applications and network communications are assigned Automotive Safety Integrity Levels (ASILs) based on the ISO 26262 standard for functional safety in automotive systems. ISO 26262 outlines, for each ASIL, requirements on coverage of random hardware errors and systematic errors. Prior research has addressed routing and scheduling for time-triggered messages in TSN in the context of random hardware errors and optimization of reliability metrics. However, no work to date has considered the functional safety aspects of addressing systematic errors. Specific to systematic errors, the ISO 26262 standard defines ASIL decomposition as a vehicle to decompose functions into independent components, each with a lower safety requirement than that of the original function. Since the cost of a component is increasing with its ASIL, decomposition can lower the total cost while still meeting the original safety requirements. In this paper, we propose an ASIL decomposition based technique to introduce redundant communication with lower-ASIL components in Ethernet systems with TSN-based time-triggered communication. The ASIL-aware routing and scheduling of messages are determined such that all safety requirements and end-to-end deadlines are satisfied and, at the same time, the total cost of the employed switches is minimized. Extensive experiments have been conducted to evaluate the efficiency of the proposed framework.

This article presents a methodology for cross-layer control–communication co-synthesis of cyber-physical systems (CPSs), communicating over Ethernet networks, with stability guarantees. We consider the recently developed IEEE 802.1 Time-Sensitive Networking standards for real-time Ethernet communication, in particular 802.1Qbv-2015, which is gaining traction in automotive and industrial automation applications. Specifically, we address routing and static scheduling of Ethernet control packets in a CPS with a switched Ethernet communication network connecting sensors, computers, and actuators. The design problem spans the network and control application layers. Our proposed SMT-based solution integrates many decision variables and objectives related to message routing, scheduling, and control application stability.

Time-sensitive Networking (TSN) on Ethernet is a promising communication technology in the automotive and industrial automation industries due to its real-time and high-bandwidth communication capabilities. Time-triggered scheduling and static routing are often adopted in these areas due to high requirements on predictability for safety-critical applications. Deadline-constrained routing and scheduling in TSN have been studied extensively in past research. However, scheduling and routing with reliability requirements in the context of transient faults are not yet studied. In this work, we propose an Satisfiability Modulo Theory-based technique to perform scheduling and routing that takes both reliability constraints and end-to-end deadline constraints into consideration. Heuristics have been applied to improve the scalability of the solution. Extensive experiments have been conducted to demonstrate the efficiency of our proposed technique.

Security for outsourced control applications can be provided if the physical plant is enabled with a mechanism to verify the control signal received from the cloud. Recent developments in modern cryptography claim the applicability of verifiable computation techniques. Such techniques allow a client to check the correctness of a remote execution. This article delivers a proof of concept for applicability of the verifiable computation scheme to control applications over the cloud. We showcase the practicality of verifiable computation on physical plants with different timing demands and deliver a real-life example using a watertank system as the client and Microsoft Azure as the cloud. We show the effectiveness of the verifiable computation scheme on cloud-based implementation of advanced control methods, such as Model Predictive Control.

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.

Modern hardware accelerators such as GP-GPUs and DSPs are commonly being used in real-time settings such as high-performance multimedia systems and autonomous vehicles. In fact, the throughput of a wide variety of computationally demanding tasks from 3D graphics and rendering to image processing and deep learning can benefit from such specialized hardware. Such heterogeneity can affect the performance of applications running simultaneously on the same accelerator. Prior studies on resource sharing and scheduling on hardware accelerators have not attempted to account for this context. In this work, we provide a portable tagging-based cooperative scheduler and resource monitor for use by heterogeneous applications sharing a single hardware accelerator in a soft real-time environment. We also offer practical insight into how various types of applications use the hardware accelerators differently. We substantiate the feasibility of our approach and evaluate the improvement of various scheduling policies over a proprietary scheduler in several case-studies with real-world applications on 2 NVIDIA platforms: a GeForce GTX 1070 GPU and an Xavier embedded platform 1 . Although we focus on GPUs in this paper, our underlying observations and framework can also be used for sharing execution on other types of hardware accelerators.

Today, it is common knowledge in the cyber-physical systems domain that the tight interaction between the cyber and physical elements provides the possibility of substantially improving the performance of these systems that is otherwise impossible. On the downside, however, this tight interaction with cyber elements makes it easier for an adversary to compromise the safety of the system. This becomes particularly important, since such systems typically are composed of several critical physical components, e.g., adaptive cruise control or engine control that allow deep intervention in the driving of a vehicle. As a result, it is important to ensure not only the reliability of such systems, e.g., in terms of schedulability and stability of control plants, but also resilience to adversarial attacks.

In this article, we propose a security-aware methodology for routing and scheduling for control applications in Ethernet networks. The goal is to maximize the resilience of control applications within these networked control systems to malicious interference while guaranteeing the stability of all control plants, despite the stringent resource constraints in such cyber-physical systems. Our experimental evaluations demonstrate that careful optimization of available resources can significantly improve the resilience of these networked control systems to attacks.

Increasing internet connectivity poses an existential threat for cyber-physical systems. Securing these safety-critical systems becomes an important challenge. Cyber-physical systems often comprise several control applications that are implemented on shared platforms where both high and low criticality tasks execute together (to reduce cost). Such resource sharing may lead to complex timing behaviors and, in turn, counter-intuitive timing anomalies that can be exploited by adversaries to destabilize a critical control system, resulting in irreversible consequences. We introduce the butterfly attack, a new attack scenario against cyber-physical systems that carefully exploits the sensitivity of control applications with respect to the implementation on the underlying execution platforms. We illustrate the possibility of such attacks using two case-studies from the automotive and avionic domains.

Switched Ethernet has been, and will also be increasingly common in current and future real-time and embedded systems. The IEEE 802.1 working group has recently developed standards and technologies, commonly referred to as Time-Sensitive Networking (TSN), to enhance switched Ethernet with timeliness and dependability. We address, for the first time, the synthesis problem for the TSN frame preemption standards IEEE 802.3br-2016 and 802.1Qbu-2016 by introducing two new configuration parameters: flow to queue and queue to Express/Preemptable MAC interface assignments. We present an optimization framework to determine these configuration parameters with reliability as the optimization goal. Our proposed framework is shown to outperform commonly used priority-assignment as well as intuitive approaches.

Modern real-time embedded and cyber-physical systems comprise a large number of applications, often of different criticalities, executing on the same computing platform. Partitioned scheduling is used to provide temporal isolation among tasks with different criticalities. Isolation is often a requirement, for example, in order to avoid the case when a low criticality task overruns or fails in such a way that causes a failure in a high criticality task. When the number of partitions increases in mixed criticality systems, the size of the schedule table can become extremely large, which becomes a critical bottleneck due to design time and memory constraints of embedded systems. In addition, switching between partitions at runtime causes CPU overhead due to preemption. In this paper, we propose a design framework comprising a hyper-period optimization algorithm, which reduces the size of schedule table and preserves schedulability, and a re-scheduling algorithm to reduce the number of preemptions. Extensive experiments demonstrate the effectiveness of proposed algorithms and design framework.

Due to the advent of active safety features and automated driving capabilities, the complexity of embedded computing systems within automobiles continues to increase. Such advanced driver assistance systems (ADAS) are inherently safety-critical and must tolerate failures in any subsystem. However, fault-tolerance in safety-critical systems has been traditionally supported by hardware replication, which is prohibitively expensive in terms of cost, weight, and size for the automotive market. Recent work has studied the use of software-based fault-tolerance techniques that utilize task-level hot and cold standbys to tolerate fail-stop processor and task failures. The benefit of using standbys is maximal when a task and any of its standbys obey the placement constraint of not being co-located on the same processor. We propose a new heuristic based on a “tiered” placement constraint, and show that our heuristic produces a better task assignment that saves at least one processor up to 40% of the time relative to the best known heuristic to date. We then introduce a task allocation algorithm that, for the first time to our knowledge, leverages the run-time attributes of cold standbys. Our empirical study finds that our heuristic uses no more than one additional processor in most cases relative to an optimal allocation that we construct for evaluation purposes using a creative technique. We also extend our heuristic to support mixed-criticality systems which allow for overload operation. We have designed and implemented our software fault-tolerance framework in AUTOSAR, an automotive industry standard. We use this implementation to provide an experimental evaluation of our task-level fault-tolerance features. Finally, we present an analysis of the worst-case behavior of our task recovery features.

Modern real-time embedded and cyber-physical systems comprise a large number of applications, often of different criticalities, executing on the same computing platform. Partitioned scheduling is used to provide temporal isolation among tasks with different criticalities. Isolation is often a requirement, for example, in order to avoid the case when a low criticality task overruns or fails in such a way that causes a failure in a high criticality task. When the number of partitions increases in mixed criticality systems, the size of the schedule table can become extremely large, which becomes a critical bottleneck due to design time and memory constraints of embedded systems. In addition, switching between partitions causes CPU overhead due to preemption. In this paper, we propose a design framework comprising the trade-off between schedule table size and system utilization, as well as a re-scheduling algorithm to reduce the effect of preemptions on utilization. Extensive experiments demonstrate the effectiveness of the proposed algorithms and design framework.

The existing approaches to design efficient safety critical control applications is constrained by limited in-vehicle sensing and computational capabilities. In the context of automated driving, we argue that there is a need to leverage resources "out-of-the-vehicle" to meet the sensing and powerful processing requirements of sophisticated algorithms (e.g., deep neural networks). To realize the need, a suitable computation offloading technique that meets the vehicle safety and stability requirements, even in the presence of unreliable communication network, has to be identified. In this work, we propose an adaptive offloading technique for control computations into the cloud. The proposed approach considers both current network conditions and control application requirements to determine the feasibility of leveraging remote computation and storage resources. As a case study, we describe a cloud-based path following controller application that leverages crowdsensed data for path planning.

Time-Sensitive Networking standards for Ethernet provide real-time and dependability mechanisms such as traffic shaping and scheduling, time synchronization, and redundancy. This article provides a review of these standards in light of possible future use cases in automotive systems using in-vehicle Ethernet networks.

Safety-critical real-time systems like modern automobiles with advanced driving-assist features must employ redundancy for crucial software tasks to tolerate permanent crash faults. This redundancy can be achieved by using techniques like active replication or the primary-backup approach. In such systems, the recovery time which is the amount of time it takes for a redundant task to take over execution on the failure of a primary task becomes a very important design parameter. The recovery time for a given task depends on various factors like task allocation, primary and redundant task priorities, system load and the scheduling policy. Each task can also have a different recovery time requirement (RTR). For example, in automobiles with automated driving features, safety-critical tasks like perception and steering control have strict RTRs, whereas such requirements are more relaxed in the case of tasks like heating control and mission planning. In this paper, we analyze the recovery time for software tasks in a real-time system employing Rate-Monotonic Scheduling (RMS). We derive bounds on the recovery times for different redundant task options and propose techniques to determine the redundant-task type for a task to satisfy its RTR. We also address the fault-tolerant task allocation problem, with the additional constraint of satisfying the RTR of each task in the system. Given that the problem of assigning tasks to processors is a well-known NP-hard bin-packing problem we propose computationally-efficient heuristics to find a feasible allocation of tasks and their redundant copies. We also apply the simulated annealing method to the fault-tolerant task allocation problem with RTR constraints and compare against our heuristics.

Real-time communication over Ethernet is becoming important in various application areas of cyber-physical systems such as industrial automation and control, avionics, and automotive networking. Since such applications are typically time critical, Ethernet technology has been enhanced to support time driven communication through the IEEE 802.1 TSN standards. The performance and stability of control applications is strongly impacted by the timing of the network communication. Thus, in order to guarantee stability requirements, when synthesizing the communication schedule and routing, it is needed to consider the degree to which control applications can tolerate message delays and jitters. In this paper we jointly solve the message scheduling and routing problem for networked cyber-physical systems based on the time-triggered Ethernet TSN standards. Moreover, we consider this communication synthesis problem in the context. of control applications and guarantee their worst-case stability, taking explicitly into consideration the impact of communication delay and jitter on control quality. Considering the inherent complexity of the network communication synthesis problem, we also propose new heuristics to improve synthesis efficiency without any major loss of quality. Experiments demonstrate the effectiveness of the proposed solutions.

Time-Sensitive Networking (TSN) is a set of IEEE standards that extend Ethernet for safety-critical and real-time applications. TSN is envisioned to be widely used in several applications areas, from industrial automation to in-vehicle networking. A TSN network is composed of end systems interconnected by physical links and bridges (switches). The data in TSN is exchanged via streams. We address safety-critical real-time systems, and we consider that the streams use the Urgency-Based Scheduler (UBS) traffic-type, suitable for hard real-time traffic. We are interested in determining a fault-tolerant network topology, consisting of redundant physical links and bridges, the routing of each stream in the applications, such that the architecture cost is minimized, the applications are fault-tolerant (i.e., the critical streams have redundant disjoint routes), and the timing constraints of the applications are satisfied. We propose three approaches to solve this optimization problem: (1) a heuristic solution, (2) a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, and (3) a Constraint Programming based model. The approaches are evaluated on several test cases, including a test case from General Motors Company.

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.

Due to the advent of active safety features and automated driving capabilities, the complexity of embedded computing systems within automobiles continues to increase. Such advanced driver assistance systems (ADAS) are inherently safety-critical and must tolerate failures in any subsystem. However, fault-tolerance in safety-critical systems has been traditionally supported by hardware replication, which is prohibitively expensive in terms of cost, weight, and size for the automotive market. Recent work has studied the use of software-based fault-tolerance techniques that utilize task-level hot and cold standbys to tolerate fail-stop processor and task failures. The benefit of using standbys is maximal when a task and any of its standbys obey the placement constraint of not being co-located on the same processor. We propose a new heuristic based on a "tiered" placement constraint, and show that our heuristic produces a better task assignment that saves at least one processor up to 40% of the time relative to the best known heuristic to date. We then introduce a task allocation algorithm that, for the first time to our knowledge, leverages the run-time attributes of cold standbys. Our empirical study finds that our heuristic uses no more than one additional processor in most cases relative to an optimal allocation that we construct for evaluation purposes using a creative technique. We have designed and implemented our software fault-tolerance framework in AUTOSAR, an automotive industry standard. We use this implementation to provide an experimental evaluation of our task-level fault-tolerance features. Finally, we present an analysis of the worst-case behavior of our task recovery features.

Real-time switched Ethernet communication is of increasing importance in many cyber-physical and embedded systems application areas such as automotive electronics, avionics, and industrial control. The IEEE 802.1 Time-Sensitive Networking (TSN) task group develops standards for real-time Ethernet, for example a time-triggered traffic class (IEEE 802.1Qbv-2015). New application areas, such as active safety and autonomous driving using radar, lidar, and camera sensors, which do not fall into the strictly periodic, time-triggered communication model, require a flexible traffic class that can accommodate various communication models while still providing hard real-time guarantees. In our previous work, we developed such a traffic class, Urgency-Based Scheduler (UBS), and its worst-case latency analysis. UBS is currently under standardization (P802.1Qcr) in the TSN task group. In this paper, we introduce and solve the UBS synthesis problem of assigning hard real-time data flows to queues and priority levels to queues, the main parameters that determine communication latencies. The synthesis problem is particularly challenging due to the flexibility offered by UBS to aggregate flows and assign individual priority levels per network hop. We present an SMT approach, a cluster-based heuristic, and an extensive experimental evaluation.

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).

Due to increasing bandwidth requirements, Ethernet technology is emerging in embedded systems application areas such as automotive, avionics, and industrial control. In the automotive domain, Ethernet enables integration of cameras, radars, and fusion to build active safety and automated driving systems. While Ethernet provides the necessary communication bandwidth, solutions are needed to satisfy stringent dependability and temporal requirements of such safety-critical systems. This paper introduces an asynchronous traffic scheduling algorithm, which gives low delay guarantees in a switched Ethernet network, while maintaining a low implementation complexity. We present a timing analysis and demonstrate the tightness of the delay bounds by extensive simulation experiments.

CAN with flexible data rate (CAN-FD) allows transmission of larger payloads compared to standard CAN. However, efficient utilization of CAN-FD bandwidth space calls for a systematic strategy. The challenge arises from the nature of the frame sizes stipulated by CAN-FD as well as the heterogeneity of the periods of the messages and the signals. In this paper, we formulate a frame packing problem for CAN-FD with the optimization objective of bandwidth utilization while meeting temporal constraints. As part of the solution, first, we propose a formula to compute the best-case and the worst-case transmission times of the CAN-FD frames. Thereafter, we propose a framework that solves the optimization problem in pseudo-polynomial time. Experiments show the gains achieved by our framework. The results also show that, when applied to standard CAN, our heuristic provides improved results over existing techniques.

In this paper, we propose a design framework for distributed embedded control systems that ensures reliable execution and high quality of control even if some computation nodes fail. When a node fails, the configuration of the underlying distributed system changes and the system must adapt to this new situation by activating tasks at operational nodes. The task mapping as well as schedules and control laws that are customized for the new configuration influence the control quality and must, therefore, be optimized. The number of possible configurations due to faults is exponential in the number of nodes in the system. This design-space complexity leads to unaffordable design time and large memory requirements to store information related to mappings, schedules, and controllers. We demonstrate that it is sufficient to synthesize solutions for a small number of base and minimal configurations to achieve fault tolerance with an inherent minimum level of control quality. We also propose an algorithm to further improve control quality with a priority-based search of the set of configurations and trade-offs between task migration and replication.

Many embedded systems comprise several controllers sharing available resources. It is well known that such resource sharing leads to complex timing behavior that degrades the quality of control, and more importantly, can jeopardize stability in the worst-case, if not properly taken into account during design. Although stability of the control applications is absolutely essential, a design flow driven by the worst-case scenario often leads to poor control quality due to the significant amount of pessimism involved and the fact that the worst-case scenario occurs very rarely. On the other hand, designing the system merely based on control quality, determined by the expected (average-case) behavior, does not guarantee the stability of control applications in the worst-case. Therefore, both control quality and worst-case stability have to be considered during the design process, i.e., period assignment, task scheduling, and control-synthesis. In this paper, we present an integrated approach for designing high-quality embedded control systems, while guaranteeing their stability.

Many embedded control systems are implemented on execution platforms with several computation nodes and communication components. Distributed embedded control systems typically comprise multiple control loops that share the available computation and communication resources of the platform. It is well known that such resource sharing leads to complex delay characteristics that degrade the control quality if not properly taken into account at design time. Scheduling in computation nodes and communication infrastructure, as well as execution periods of the controllers impact the delay characteristics and, consequently, the control quality. In addition, mapping of tasks on computation nodes affect both scheduling of tasks and messages, and the assignment of periods of the control applications. Therefore, control synthesis must be considered during mapping, scheduling, and period assignment in order to achieve high control quality. This paper presents a control-quality optimization approach for integrated mapping, scheduling, period selection, and control synthesis for distributed embedded control systems.

FlexRay is a popular communication protocol in modern automotive systems with several computation nodes and communication units. The complex temporal behavior of such systems depends highly on the FlexRay configuration and influences the performance of running control applications. In our previous work, we presented a design framework for integrated scheduling and design of embedded control applications, where control quality is the optimization objective. This paper presents our extension to the design framework to handle FlexRay-based embedded control systems. Our contribution is a method for the decision of FlexRay parameters and optimization of control quality.

This thesis addresses several synthesis and optimization issues for embedded control systems. Examples of such systems are automotive and avionics systems in which physical processes are controlled by embedded computers through sensor and actuator interfaces. The execution of multiple control applications, spanning several computation and communication components, leads to a complex temporal behavior that affects control quality. The relationship between system timing and control quality is a key issue to consider across the control design and computer implementation phases in an integrated manner. We present such an integrated framework for scheduling, controller synthesis, and quality optimization for distributed embedded control systems.

At runtime, an embedded control system may need to adapt to environmental changes that affect its workload and computational capacity. Examples of such changes, which inherently increase the design complexity, are mode changes, component failures, and resource usages of the running control applications. For these three cases, we present trade-offs among control quality, resource usage, and the time complexity of design and runtime algorithms for embedded control systems.

The solutions proposed in this thesis have been validated by extensive experiments. The experimental results demonstrate the efficiency and importance of the presented techniques.

Time-triggered periodic control implementations are over provisioned for many execution scenarios in which the states of the controlled plants are close to equilibrium. To address this inefficient use of computation resources, researchers have proposed self-triggered control approaches in which the control task computes its execution deadline at runtime based on the state and dynamical properties of the controlled plant. The potential advantages of this control approach cannot, however, be achieved without adequate online resource-management policies. This paper addresses scheduling of multiple self-triggered control tasks that execute on a uniprocessor platform, where the optimization objective is to find tradeoffs between the control performance and CPU usage of all control tasks. Our experimental results show that efficiency in terms of control performance and reduced CPU usage can be achieved with the heuristic proposed in this paper.

FlexRay is an automotive communication protocol that combines the comprehensive time-triggered paradigm with an adaptive phase that is more suitable for event-based communication. We study optimization of average response times by assigning priorities and frame identifiers to tasks and messages. Our optimization approach is based on immune genetic algorithms, where in addition to the crossover and mutation operators, we use a vaccination operator that results in considerable improvements in optimization time and quality.

Many embedded control systems comprise several control loops that are closed over a network of computation nodes. In such systems, complex timing behavior and communication lead to delay and jitter, which both degrade the performance of each control loop and must be considered during the controller synthesis. Also, the control performance should be taken into account during system scheduling. The contribution of this paper is a control-scheduling co-design method that integrates controller design with both static and priority-based scheduling of the tasks and messages, and in which the overall control performance is optimized.

At runtime, an embedded control system can switch between alternative functional modes. In each mode, the system operates by using a schedule and controllers that exploit the available computation and communication resources to optimize the control performance in the running mode. The number of modes is usually exponential in the number of control loops, which means that all controllers and schedules cannot be produced in affordable design-time and stored in memory. This paper addresses synthesis of multi-mode embedded control systems. Our contribution is a method that trades control quality with optimization time, and that efficiently selects the schedules and controllers to be synthesized and stored in memory.

In this paper, we propose a simulation-based methodology for worst-case response time estimation of distributed real-time systems. Schedulability analysis produces pessimistic upper bounds on process response times. Consequently, such an analysis can lead to overdesigned systems resulting in unnecessarily increased costs. Simulations, if well conducted, can lead to tight lower bounds on worst-case response times, which can be an essential input at design time. Moreover, such a simulation methodology is very important in situations when the running application or the underlying platform is such that no formal timing analysis is available. Another important application of the proposed simulation environment is the validation of formal analysis approaches, by estimating their degree of pessimism. We have performed such an estimation of pessimism for two response-time analysis approaches for distributed embedded systems based on two of the most important automotive communication protocols: CAN and FlexRay.

Concurrent testing of the cores in a core-based system- on-chip reduces the test application time but increases the test power consumption. Power models, test architecture design, and scheduling algorithms have been proposed to schedule the tests as concurrently as possible while respecting the power budget. The commonly used global peak power model, with a single value capturing the power dissipated by a core when tested, is simple for a scheduling algorithm to handle but is pessimistic. In this paper, we propose a cycle-accurate power model with a power value per clock cycle and a corresponding test architecture design and scheduling algorithm. The power model takes into account the switching activity in the scan chains caused by both the test stimuli and the expected test responses during scan-in, launch-and-capture, and scan-out. Furthermore, we allow a unique power model per wrapper-chain configuration as the activity in a core will be different depending on the number of wrapper chains at a core. Through circuit simulations on ISCAS'89 benchmarks, we demonstrate a high correlation between the real test power dissipation and our cycle-accurate test power model. Extensive experiments on ITC'02 benchmarks and an industrial design show that the testing time can be reduced substantially by using the proposed cycle-accurate test power model.

Concurrent testing of the cores in a modular core-based System-on-Chip reduces the test application time but increases the test power consumption. Power models and scheduling algorithms have been proposed to schedule the tests as concurrently as possible while respecting the power budget. The commonly used global peak power model, with a single value capturing the power dissipated by a core when tested, is pessimistic but simple for a scheduling algorithm to handle. In this paper, we propose a cycle-accurate power model with a power value per clock cycle and a corresponding scheduling algorithm. The model takes into account the switching activity in the scan chains caused by both the test stimuli and the test responses during scan-in, launch-and-capture, and scan-out. Further, we allow a unique power model per wrapper chain configuration as the activity in a core will be different depending on the number of wrapper chains at a core. Extensive experiments on ITC'02 benchmarks and an industrial design show that the testing time can be substantially reduced (on average 16.5% reduction) by using the proposed cycle-accurate test power model.