The design of embedded safety-critical systems such as those used in next-generation automotive and autonomous platforms, is increasingly challenged by escalating system complexity, hardware–software heterogeneity, and the integration of intelligent, data-driven components. Ensuring dependability in such systems requires a holistic approach that spans multiple abstraction layers and encompasses both design- and run-time assurance. Traditional methods for reliability, safety, and security management often fall short in addressing the dynamic and uncertain behaviors introduced by Artificial Intelligence (AI) and Machine Learning (ML) components, especially under stringent real-time, power, and safety constraints. While AI and ML offer powerful predictive, adaptive, and self-optimizing capabilities that can enhance system dependability, their inherent non-determinism, data-dependence, and lack of formal guarantees introduce new challenges for verification, validation, and certification. This paper explores emerging methodologies, architectures, and frameworks for designing dependable autonomous and embedded systems in the era of AI. It highlight advances in reliability modeling, secure system design, and certification approaches that account for imperfect, learning-enabled components, aiming to bridge the gap between AI innovation and certifiable system-level dependability.

Deep Brain Stimulation (DBS) is a highly effective treatment for Parkinson's Disease (PD). Recent research uses reinforcement learning (RL) for DBS, with RL agents modulating the stimulation frequency and amplitude. But, these models rely on biomarkers that are not measurable in patients and are only present in brain-on-chip (BoC) simulations. In this work, we present an RL-based DBS approach that adapts these stimulation parameters according to brain activity measurable in vivo. Using a TD3 based RL agent trained on a model of the basal ganglia region of the brain, we see a greater suppression of biomarkers correlated with PD severity, compared to modern clinical DBS implementations. Our agent outperforms the standard clinical approaches in suppressing PD biomarkers while relying on information that can be measured in a real world environment, thereby opening up the possibility of training personalized RL agents specific to individual patient needs.

When addressing timing issues in real-time systems, approaches for systematic timing debugging and repair have been missing due to (i) Lack of available feedback: most timing analysis techniques, being closed-form analytical techniques, are unable to provide root cause information when a timing property is violated, which is critical for identifying an appropriate repair, and (ii) Pessimism in the analysis: existing schedulability analysis techniques tend to make worst case assumptions in the presence of non-determinism introduced by real-world factors such as release jitter, or sporadic tasks. To address this gap, we propose an SMT encoding of task runs for exact debugging of timing violations, and a procedure to iteratively repair a given task specification. We demonstrate the utility of this procedure by repairing example task sets scheduled under global non-preemptive earliest-deadline-first scheduling, a common choice for many safety-critical systems.

Hardware/software co-design in the context of cyber-physical systems (CPS) [2] takes the form of co-designing (i) a control algorithm, and (ii) its software implementation on a distributed and heterogeneous architecture [5, 6]. In domains such as automotive CPS, this involves the design and implementation of multiple controllers on distributed automotive architectures consisting of different electronic control units (ECUs) and communication buses like CAN, FlexRay and automotive Ethernet [13]. Traditionally, following the principle of separation of concerns, control algorithms were designed independent of the implementation platform details. As a result, they made certain assumptions on delays experienced by control signals and assumed, for example, that all sensor inputs necessary for state estimation arrive at the same time. When trying to implement such controllers on an independently designed implementation platform, where many of the controller design or model-level assumptions are not satisfied, an iterative design process that involves testing and adjustments to the controllers and the implementation decisions became necessary. This led to the development of X-in-the-loop simulations, where X can be software and hardware at various stages of implementation, along with which the control algorithms are simulated [1, 14]. The aim is to ensure that the semantics or the behavior of the controller models (or algorithms) are preserved in the final implementation [12].

Modern cyber-physical systems (CPS) consist of multiple components including sensors, controllers, machine learning (ML) components, real-time schedulers, among others. Each component is usually designed separately with the aim of working perfectly. For example, task schedulers aim to ensure that all deadlines are met and ML components aim to always make perfect inferences. The correctness or "perfection" of the overall CPS is inferred from the correctness of its components. However, none of the CPS components are perfect in reality. Schedulers or tasks sometimes miss deadlines, ML components sometimes make inaccurate inferences, and sensors are occasionally noisy. These imperfections are assumed to be small enough to be ignored. In particular, it is assumed – without guarantees – that these imperfections do not compromise system safety or the correctness of the CPS.We propose to reverse this approach and argue that there is usually sufficient tolerance at the system level. This tolerance should be explicitly modeled, and its impact on the correctness or perfection of system components should be determined. This enables the design of more cost-effective, robust systems. Furthermore, appropriately designing the other components to compensate for the imperfection of individual components ensures that system-level safety remains within the specified margins.

We study the problem where an autonomous system is in a critical situation and is faced with multiple options among which it has to choose to safely evade the criticality. Each of these options is also associated with some uncertainty. Traditional approaches from formal methods require a reachability analysis to evaluate which of the options is safe. While the computational cost of reachability analysis is well known, the presence of uncertainty adds an additional layer of complexity. As a result, performing reachability analysis for all the options before choosing one will not be feasible due to time constraints. This is a practical problem that arises is various scenarios, such as an autonomous vehicle in a potential accident that it has to evade to minimize damage. While models and algorithms for reachability analysis have been widely studied, reachability analysis in the presence of uncertainties have been less so. Despite its many applications, to the best of our knowledge, the problem of choosing in real-time, one of the many options for criticality evasion has not been studied in the past. We address this problem by proposing a new real-time reachable set computation technique for uncertain linear systems using techniques from perturbation theory.

Holographic displays are gaining increasing popularity, particularly as a holy grail solution to augmented and virtual reality (AR/VR) wearable displays. However, the generation of holograms is computationally intensive for AR/VR edge devices, which are expected to be compact and lightweight with low power consumption and heat dissipation to last all day. To address this, we propose a distributed hologram generation framework, dubbed HoloZip, to jointly generate, compress, transmit, and decode computer-generated holograms across the cloud-edge devices. Specifically, we perform compute intensive hologram generation via a vision transformer based backbone on the cloud, compress and transmit before decoding on a local edge device by a lightweight model. Our HoloZip framework supports both both 2D/3D holograms as well as holographic videos, achieving a reconstruction quality of over 30 dB in PSNR (lossy compression standard) with bit rates as low as 0.6 bits per pixel as validated by experiments.

The complexity of current manufacturing systems is growing, increasing the complexity of testing and validating control software. Manufacturing software must be extensively tested to minimize errors that may lead to production stops or machine breakdowns. However, testing on real manufacturing systems is often impractical or limited to small portions of the real systems. This paper presents Frost, an open-source platform supporting early manufacturing software validation and testing. Frost is built on top of the Lingua Franca framework, which ensures deterministic execution, enhancing the reliability of software prototyping and testing. The proposed platform implements a set of reactors and classes designed to model the different parts of a manufacturing system, such as sensors, machines, control software, and communication infrastructure. The effectiveness and capabilities of the Frost platform are validated by comparing the overhead introduced and by implementing a digital twin of a real manufacturing system.

Fourier transforms are vital for a broad range of signal-processing applications. Accelerating FFTs with GPUs offers an orders-of-magnitude improvement vs. CPU-only FFT computation. However, two problems arise when executing FFT tasks with other GPU work. First, concurrent GPU use introduces unpredictability in the form of lengthy response times. Second, it is unclear how to best parameterize and schedule FFT tasks to meet the throughput and timeliness constraints of real-time signal processing. This work investigates how FFT and other GPU-using tasks can concurrently access a GPU while maintaining bounded response-time guarantees without sacrificing throughput. In our experiments, the techniques proposed by this work result in an up to 17% improvement in worst-case FFT response times.

Neighbor Discovery (ND) is the procedure employed by wireless devices to establish a first contact. All ND protocols involve devices sending beacons, and also listening for them. Protocols differ in terms of how the beacon transmissions and reception windows are scheduled, and the device sleeps in between consecutive transmissions and reception windows in order to save energy. A successful discovery constitutes a sending device’s beacon coinciding with a receiving device’s reception window. The goal of all ND protocols is to minimize the discovery latency. In spite of the ubiquity of ND protocols and active research on this topic for over two decades, the basic question “Given a power budget, what is the minimum guaranteed ND latency?”, however, has still remained unanswered. This paper is on the best-achievable ND latency for a given power budget between a pair of devices. In order to compute this lower bound, we introduce a concept called coverage maps, that allows us to analyze the ND procedure in a protocol-independent manner. Using it, we derive discovery latencies for different scenarios, e.g., when both devices have the same or different power budgets. We also show that some existing protocols can be parametrized such that they perform optimally. Our results are restricted to the case when a few devices discover each other at a time, as is the case in most real-life scenarios, while scenarios with large numbers of devices need further study.

Software Defined Vehicles (SDVs) represent a paradigm shift in the automotive industry, where vehicles are increasingly controlled and managed through software, while relying less on mechanical and hardware components. While this allows considerable flexibility in the introduction of new “smart” features and fast tracks innovations in multiple domains, it also creates new challenges and opportunities in architecture design, control, and security. By adopting modular architectures, adaptive control strategies, and robust security measures, SDVs can pave the way for a safer and more efficient future of transportation. In this paper, we cover perspectives from both, industry and academia, in this area. They provide embedded systems researchers an overview of recent developments and emerging challenges in SDV from the perspective of architecture design, control, and security. The emerging challenges also set the foundations for future research in this domain.

Split Computing (SC), where a Deep Neural Network (DNN) is intelligently split with a part of it deployed on an edge device and the rest on a remote server is emerging as a promising approach. It allows the power of DNNs to be leveraged for latency-sensitive applications that do not allow the entire DNN to be deployed remotely, while not having sufficient computation bandwidth available locally. In many such embedded systems scenarios, such as those in the automotive domain, computational resource constraints also necessitate Multi-Task Learning (MTL), where the same DNN is used for multiple inference tasks instead of having dedicated DNNs for each task, which would need more computing bandwidth. However, how to partition such a multi-tasking DNN to be deployed within a SC framework has not been sufficiently studied. This paper studies this problem, and MTL-Split, our novel proposed architecture, shows encouraging results on both synthetic and real-world data. The source code is available at https://github.com/intelligolabs/MTL-Split.

Using WiFi's Channel State Information for human activity recognition—referred to as WiFi sensing—has attracted considerable attention. But despite this interest and many publications over a decade, WiFi sensing has not yet found its way into practice because of a lack of robustness of the inference results. In this paper, we quantitatively show that even “microchanges” in the environment can significantly impact WiFi signals, and potentially alter the ML inference results. We therefore argue that new training and inference techniques might be necessary for mainstream adoption of WiFi sensing.

In the past decade, Deep Neural Networks (DNNs) achieved state-of-the-art performance in a broad range of problems, spanning from object classification and action recognition to smart building and healthcare. The flexibility that makes DNNs such a pervasive technology comes at a price: the computational requirements preclude their deployment on most of the resource-constrained edge devices available today to solve real-time and real-world tasks. This paper introduces a novel approach to address this challenge by combining the concept of predefined sparsity with Split Computing (SC) and Early Exit (EE). In particular, SC aims at splitting a DNN with a part of it deployed on an edge device and the rest on a remote server. Instead, EE allows the system to stop using the remote server and rely solely on the edge device’s computation if the answer is already good enough. Specifically, how to apply such a predefined sparsity to a SC and EE paradigm has never been studied. This paper studies this problem and shows how predefined sparsity significantly reduces the computational, storage, and energy burdens during the training and inference phases, regardless of the hardware platform. This makes it a valuable approach for enhancing the performance of SC and EE applications. Experimental results showcase reductions exceeding 4× in storage and computational complexity without compromising performance. The source code is available at https://github.com/intelligolabs/sparsity_sc_ee.

research-article Share on Introduction to the Special Issue on Automotive CPS Safety & Security: Part 2 Authors: Samarjit Chakraborty The University of North Carolina at Chapel Hill, Chapel Hill, United States The University of North Carolina at Chapel Hill, Chapel Hill, United States 0000-0002-0503-6235View Profile , Somesh Jha University of Wisconsin-Madison, Madison, United States University of Wisconsin-Madison, Madison, United States 0000-0001-5877-0436View Profile , Soheil Samii Linköping University, Linkoping, Sweden Linköping University, Linkoping, Sweden 0000-0002-9572-1091View Profile , Philipp Mundhenk Robert Bosch GmbH, Renningen, Germany Robert Bosch GmbH, Renningen, Germany 0000-0001-6132-3901View Profile Authors Info & Claims ACM Transactions on Cyber-Physical SystemsVolume 8Issue 2Article No.: 10pp 1–17https://doi.org/10.1145/3650210Published:15 May 2024Publication History 0citation71DownloadsMetricsTotal Citations0Total Downloads71Last 12 Months71Last 6 weeks42 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteGet Access

With the emergence of complex autonomous systems, multiple control tasks are increasingly being implemented on shared computational platforms. Due to the resource-constrained nature of such platforms in domains such as automotive, scheduling all the control tasks in a timely manner is often difficult. The usual requirement---that all task invocations must meet their deadlines---stems from the isolated design of a control strategy and its implementation (including scheduling) in software. This separation of concerns, where the control designer sets the deadlines, and the embedded software engineer aims to meet them, eases the design and verification process. However, it is not flexible and is overly conservative. In this paper, we show how to capture the deadline miss patterns under which the safety properties of the controllers will still be satisfied. The allowed patterns of such deadline misses may be captured using what are referred to as "weakly-hard constraints." But scheduling tasks under these weakly-hard constraints is non-trivial since common scheduling policies like fixed-priority or earliest deadline first do not satisfy them in general. The main contribution of this paper is to automatically synthesize schedules from the safety properties of controllers. Using real examples, we demonstrate the effectiveness of this strategy and illustrate that traditional notions of schedulability, e.g., utility ratios, are not applicable when scheduling controllers to satisfy safety properties.

Over the past two decades, the volume of electronics and software in cars have grown tremendously. But this growth has also resulted in hardware and software architectures that are proving to be a bottleneck for further innovation and efficient design flows, especially when implementing compute-intensive functions necessary for modern autonomous features. For example, centralized architectures that are driven by the use of more powerful processors result in higher sensor-to-actuator delays. Similarly, timing uncertainties increase as signal-based in-vehicle communication is being replaced by more dynamic service-oriented communication architectures. Finally, the increasing volume of software running on powerful multicore ECUs is making timing analysis, including WCET estimation, to be very complex. As a result, timing estimates, when safe, are very pessimistic, which makes efficient implementations to be difficult. In this position paper, we outline some of these emerging challenges and discuss potential solutions.

In-vehicle network architectures are evolving from a typical signal-based client-server paradigm to a service-oriented one, introducing flexibility for software updates and upgrades. While signal-based networks are static by nature, service-oriented ones can more easily evolve during and after the design phase. As a result, service-oriented protocols are becoming more prominent in automotive in-vehicle networks. While applications like infotainment are less sensitive to delays, others like sensing and control have more stringent timing and reliability requirements. Hence, wider adoption of service-oriented protocols requires addressing the timing analysis and predictability of such protocols, which is more challenging than in their signal-oriented counterparts. In service-oriented architectures, the discovery phase defines how clients find their required services. The time required to complete the discovery phase is an important parameter since it determines the readiness of a sub-system or even the vehicle. In this paper, we develop a formal timing analysis of the discovery phase of SOME/IP, which is an emerging service-oriented protocol being considered for adoption by several automotive Original Equipment Manufacturers (OEMs) and suppliers.

A crucial requirement for control tasks in safety-critical systems like automotive is that all deadlines be met. This is becoming increasingly difficult when several tasks share common resources. One main reason for this lies in obtaining tight WCET estimations, especially as software and processor architectures continue to become more complex. Using safe but not necessarily tight WCET estimates and meeting all deadlines come at the expense of very pessimistic and inefficient implementations. In this paper, we show that by focusing on “higher-level” properties like control safety, instead of trying to meet all deadlines, it is possible to achieve more efficient implementations of control tasks on shared resources. This has considerable benefits in cost-sensitive domains like automotive. The core of our technique follows the AUTOSAR paradigm where groups of control computations with the same period constitute units of scheduling. Towards this, we suitably increase (boost) or decrease (compress) the sampling periods of control tasks and schedule them in a manner that is cognizant of their high-level safety constraints, but does not necessarily meet all deadlines. Our results for several standard controllers from the automotive domain illustrate the benefits of our approach.

research-article Free Access Share on Introduction to the Special Issue on Automotive CPS Safety & Security: Part 1Just Accepted Authors: Samarjit Chakraborty University of North Carolina at Chapel Hill, USA University of North Carolina at Chapel Hill, USASearch about this author , Somesh Jha University of Wisconsin-Madison, USA University of Wisconsin-Madison, USASearch about this author , Soheil Samii Linköping University, Sweden Linköping University, SwedenSearch about this author , Philipp Mundhenk Robert Bosch GmbH, Germany Robert Bosch GmbH, GermanySearch about this author Authors Info & Claims ACM Transactions on Cyber-Physical SystemsAccepted on February 2023 https://doi.org/10.1145/3579986Published:23 February 2023Publication History 0citation0DownloadsMetricsTotal Citations0Total Downloads0Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Coverage Guided Fuzzing (CGF) is a greybox test generation technique. Bounded Model Checking (BMC) is a whitebox test generation technique. Both these have been highly successful at program coverage as well as error detection. It is well known that CGF fails to cover complex conditionals and deeply nested program points. BMC, on the other hand, fails to scale for programming features such as large loops and arrays. To alleviate the above problems, we propose (1) to combine BMC and CGF by using BMC for a short and potentially incomplete unwinding of a given program to generate effective initial test prefixes, which are then extended into complete test inputs for CGF to fuzz, and (2) in case BMC gets stuck even for the short unwinding, we automatically identify the reason, and rerun BMC with a corresponding remedial strategy. We call this approach as BMCFuzz and implemented it in the VeriFuzz framework. This implementation was experimentally evaluated by participating in Test-Comp 2021 and the results show that BMCFuzz is both effective and efficient at covering branches as well as exposing errors. In this paper, we present the details of BMCFuzz and our analysis of the experimental results.

The core idea of flexible manufacturing is adapting to changes. In this domain, the machine is not confined to a single fixed type of process but can perform different jobs (e.g., cutting, drilling) in different ways (e.g., varying speed, tool, power consumption). This adaptability should be enabled by a detailed view of how the machines work. The idea is to perform machine scheduling by exploiting the dynamical models—expressed as differential equations—of manufacturing processes, i.e., both machines and production items. The main innovation in this paper is the ability to compute a machine’s schedule where the state of the product does not linearly evolve in time but is determined by the set of differential equations instead. Finding the schedule is defined as a multi-objective optimization problem—manufacturers may seek a trade-off between processing time, energy consumption, and other cost functions. The proposed optimization is evaluated using accurate process models, exemplifying how it works and harnesses the expressiveness of differential equations.

Software in autonomous systems, owing to performance requirements, is deployed on heterogeneous hardware comprising task specific accelerators, graphical processing units, and multicore processors. But performing timing analysis for safety critical control software tasks with such heterogeneous hardware is becoming increasingly challenging. Consequently, a number of recent papers have addressed the problem of stability analysis of feedback control loops in the presence of timing uncertainties (cf., deadline misses). In this paper, we address a different class of safety properties, viz., whether the system trajectory deviates too much from the nominal trajectory, with the latter computed for the ideal timing behavior. Verifying such quantitative safety properties involves performing a reachability analysis that is computationally intractable, or is too conservative. To alleviate these problems we propose to provide statistical guarantees over behavior of control systems with timing uncertainties. More specifically, we present a Bayesian hypothesis testing method based on Jeffreys’s Bayes factor test that estimates deviations from a nominal or ideal behavior. We show that our analysis can provide, with high confidence, tighter estimates of the deviation from nominal behavior than using known reachability based methods. We also illustrate the scalability of our techniques by obtaining bounds in cases where reachability analysis fails to converge, thereby establishing the former’s practicality.

As embedded systems architectures become more complex and distributed, checking the safety of feedback control loops implemented on them becomes a crucial problem for emerging autonomous systems. Toward this, a number of recent papers have addressed the problem of checking stability in the presence of deadline misses. In this article, we argue that analyzing quantitative properties like the maximum deviation in system behavior (trajectory in the state space) between an ideal implementation platform and that having timing uncertainties is an equally important problem. We show that different strategies for handling deadline misses (or system overruns), all of which lead to a stable system, might differ considerably when considering such quantitative safety properties. However, analyzing such properties involves reachability analysis that is computationally expensive and, hence, not scalable. We show that suitable approximation strategies can address this computational bottleneck and such quantitative safety properties can be checked for realistic systems. As a result, we are able to identify best combinations of control and deadline miss handling strategies for individual systems and timing uncertainties.

Controller design and their software implementations are usually done in isolated design spaces using respective COTS design tools. However, this separation of concerns can lead to long debugging and integration phases. This is because assumptions made about the implementation platform during the design phase—e.g., related to timing—might not hold in practice, thereby leading to unacceptable control performance. In order to address this, several control/architecture co-design techniques have been proposed in the literature. However, their adoption in practice has been hampered by the lack of design flows using commercial tools. To the best of our knowledge, this is the first article that implements such a co-design method using commercially available design tools in an automotive setting, with the aim of minimally disrupting existing design flows practiced in the industry. The goal of such co-design is to jointly determine controller and platform parameters in order to avoid any design-implementation gap , thereby minimizing implementation time testing and debugging. Our setting involves distributed implementations of control algorithms on automotive electronic control units ( ECUs ) communicating via a FlexRay bus. The co-design and the associated toolchain Co-Flex jointly determines controller and FlexRay parameters (that impact signal delays) in order to optimize specified design metrics. Co-Flex seamlessly integrates the modeling and analysis of control systems in MATLAB/Simulink with platform modeling and configuration in SIMTOOLS/SIMTARGET that is used for configuring FlexRay bus parameters. It automates the generation of multiple Pareto-optimal design options with respect to the quality of control and the resource usage, that an engineer can choose from. In this article, we outline a step-by-step software development process based on Co-Flex tools for distributed control applications. While our exposition is automotive specific, this design flow can easily be extended to other domains.

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.

Neighbor discovery (ND) protocols are used for establishing a first contact between multiple wireless devices. The energy consumption and discovery latency of this procedure are determined by the parametrization of the protocol. In most existing protocols, reception and transmission are temporally coupled. Such schemes are referred to asslotted, for which the problem of finding optimized parametrizations has been studied thoroughly in the literature. However, slotted approaches are not efficient in applications in which new devices join the network gradually and only the joining devices and a master node need to run the ND protocol simultaneously. For example, this is typically the case in IoT scenarios or bluetooth low energy (BLE) piconets. Here,slotlessprotocols that decouple reception and transmission can achieve significantly lower worst-case latencies than slotted ones. In this paper, we study slotless, BLE-like protocols, which schedule receptions and transmissions independently using periodic intervals (PI). For this class of protocols, optimal parameter values remain unknown. To address this, we propose an optimization framework for PI-based protocols, which translates any specified duty-cycle (and therefore energy budget) into a set of optimized parameter values. We show that the parametrizations resulting from one variant of our proposed scheme are optimal when one receiver discovers one transmitter, and no other parametrization or ND protocol – neither slotted nor slotless – can guarantee lower discovery latencies for a given duty-cycle in this scenario. Since the resulting protocol utilizes the channel more aggressively than other ND protocols, beacons will collide more frequently. Hence, due to collisions, the rate of successful discoveries gracefully decreases for larger numbers of devices discovering each other simultaneously. We also propose a scheme for configuring the BLE protocol (and not just BLE-likeprotocols). Though it is not clear whether the resulting parametrizations minimize the latencies of BLE, reasonably low worst-case latencies can be guaranteed.

Vision processing for autonomous systems today involves implementing machine learning algorithms and vision processing libraries on embedded platforms consisting of CPUs, GPUs and FPGAs. Because many of these use closed-source proprietary components, it is very difficult to perform any timing analysis on them. Even measuring or tracing their timing behavior is challenging, although it is the first step towards reasoning about the impact of different algorithmic and implementation choices on the end-to-end timing of the vision processing pipeline. In this paper we discuss some recent progress in developing tracing, measurement and analysis infrastructure for determining the timing behavior of vision processing pipelines implemented on state-of-the-art FPGA and GPU platforms.

Feedback control loops are ubiquitous in any autonomous system. The design flow for any controller starts by determining a control strategy, while abstracting away all implementation details. However, when designing controllers for autonomous systems, there is significant computation associated with the perception modules. For example, this involves vision processing using deep neural networks on multicore CPU+accelerator platforms. Such computation can be organized in many different ways, with each choice resulting in very different sensor-to-actuator delays and tradeoffs between cost, delay, and accuracy. Further, each of these choices requires the control strategy to be designed accordingly. It is not possible for a control designer to enumerate and account for all of these choices manually, or abstract them away as “implementation details” as done in traditional controller design. In this paper we outline this problem and discuss how automated controller-synthesis techniques could help in addressing it.

This paper is concerned with the following question: Given a set of control tasks that are not schedulable, i.e., their required timing properties cannot be satisfied, what should be changed? While the real-time systems literature proposes many different schedulability analysis techniques, it surprisingly provides almost no guidelines on what should be changed to make a task set schedulable, when it is not. We show that when the tasks in question are control tasks, this timing debugging question in the context of cyber-physical systems (CPS) may be answered by exploiting the dynamics of the physical systems that these control tasks are expected to influence. Towards this, we study a very simple setup, viz., when a set of periodic tasks with implicit deadlines is not schedulable, by how much should the periods be changed in order to make the task set schedulable? Among the many ways in which the periods can be modified, our proposed strategy is to change the periods in a manner such that while the task set becomes schedulable, the poles of the closed-loop system experience the minimal shift. Since the poles influence the closed loop dynamics of the system, we thereby ensure that we obtain a system with the desired timing properties whose dynamics is very similar to the dynamics of the original (non-schedulable) system. We formulate this CPS timing debugging strategy as an optimization problem and illustrate it with a concrete example.

Future autonomous systems will rely on advanced sensors and deep neural networks for perceiving the environment, and then utilize the perceived information for system planning, control, adaptation, and general decision making. However, due to the inherent uncertainties from the dynamic environment and the lack of methodologies for predicting neural network behavior, the perception modules in autonomous systems often could not provide deterministic guarantees and may sometimes lead the system into unsafe states (e.g., as evident by a number of high-profile accidents with experimental autonomous vehicles). This has significantly impeded the broader application of machine learning techniques, particularly those based on deep neural networks, in safety-critical systems. In this paper, we will discuss these challenges, define open research problems, and introduce our recent work in developing formal methods for quantitatively bounding the output uncertainty of perception neural networks with respect to input perturbations, and leveraging such bounds to formally ensure the safety of system control. Unlike most existing works that only focus on either the perception module or the control module, our approach provides a holistic end-to-end framework that bounds the perception uncertainty and addresses its impact on control.

Distributed embedded applications (DEAs) are typically implemented on diverse embedded nodes interconnected through communication network(s) to exchange data and control information to achieve the desired functionality. Conventional approaches of utilising a single large-bandwidth link in a distributed system are not efficient in large DEAs owing to diverse requirements and factors like cost, reliability, scalability and criticality, among others. Heterogeneous communication is a promising approach in DEAs, where the diverse nature of underlying protocols (wired/wireless, synchronous/asynchronous, multiple access modes and others) can be leveraged to meet such requirements, in addition to the benefits like aggregated bandwidth and robustness. However, utilising them ‘directly’ places significant complexity on the application as it needs to dynamically evaluate the channels and utilise different protocol structures for each case. Virtualising the communication channels would present a unified interface to the application by abstracting away low-level details, similar to virtualisation applied in compute architectures. However, unlike architecture virtualisation, virtualising heterogeneous communication particularly for resource-constrained device networks involves unique challenges imposed by the physical (wired/wireless) and logical domains (limited-bandwidth, small payload, protocols, channel access schemes, etc.), which needs to be concurrently evaluated to optimise the communication system. This paper presents a model and an optimal transmission strategy as the proof of concept for deploying heterogeneous communication in DEAs. The model is described at an abstracted level while capturing transmission parameters of multiple channels, which are then optimised to meet the application’s communication requirements. The model and the optimisation method are validated through simulation and a practical case study.

Since hearing loss is one of the most widespread disabilities and can often be addressed by early detection and intervention, there is a strong interest in technologies for cost-effective and mass-deployable hearing screening. Towards this, smartphones have been used for subjective tests where a sequence of tones are played to a subject who has to appropriately respond upon hearing them. But such tests are inappropriate where, e.g., children are involved who cannot provide reliable feedback, or the test takes too long. In this paper, we investigate an alternative modality to develop an objective screening test using smartphones. It relies on how the cochlea actively distorts tones emitted into the ear. By measuring these distorted signals, it is possible to reliably deduce the subject’s hearing health. But smartphones are not designed to detect such low signals, and the suitability of a phone depends on the signal processing characteristics of the phone’s hardware. In this paper we investigate this issue in detail and conclude that some smartphones are suitable for objective screening tests that require no interaction with a subject. This opens up new screening options that were not available before and have immense societal implications in developing countries.

Today, many industrial, automotive and autonomous systems like robots are deployed in high-temperature and battery-powered environments. Due to cooling and runtime, this limits the energy consumption and makes the design of such embedded real-time systems even more challenging. Though Field Programmable Gate Arrays (FPGAs) offer the required performance, their static and - load-dependent - dynamic energy consumptions continue to prevent a widespread adoption. The existing methods for dynamic power reduction (like clock gating) are either limited in savings or require disruptive changes to well-established FPGA design flows. Whilst the former is caused by optimizing on fabric level only, the latter is due to the lack of support for a more efficient (but not yet mature and standardized) high-level design entry in current tools. In this paper, we thus explore an optimization methodology based on an existing, but not-fully-utilized intermediate level of abstraction that emerges in the IP core integration phase of the design. To this end, we exploit the fact that the vast majority of FPGA-based real-time processing pipelines is not exclusively assembled using a single type of design entry - i.e., neither entirely hand-written nor high-level synthesis only. Instead, suitable IP cores (from a variety of sources) are integrated via standardized bus interfaces such as AXI, Avalon or Wishbone. To facilitate effort- and power-efficient clock gating on integration-level, we present two “insert and save” IP cores that harness application information extracted from current AXI3 and AXI4-Stream interfaces. Based thereon, both cores precisely control the clock signals of every downstream processing stage for maximum energy savings. This approach not only nicely integrates with today's predominantly AXI-based designs but also results in clock gating structures that are particularly suitable for current FPGAs - as demonstrated by experimental evaluations on a Zynq-based Visual Servoing System with energy savings of 26%.

Thermal efficient resource mapping and scheduling techniques are particularly important for mobile processors because of limited opportunities for external cooling. In mobile processors such as the ones using ARM’s big.LITTLE architectures, the cores of either the big or the LITTLE processor cannot be individually voltage/frequency scaled. However, we show that by forcing all the application threads to a single core, and not having any workload on the other cores of a processor, there is still considerable thermal benefit. This is counter intuitive since all the cores run at the same frequency. We show real measurements and discuss what impact this has on thermal-aware scheduling for such multicore processors.

Automotive software implements different functionalities as multiple control applications sharing common platform resources. Although such applications are often developed independently, the control performance of the resulting system depends on how these applications are integrated. A key integration challenge is to efficiently schedule these applications on shared resources with minimal control performance degradation. We formulate this problem as that of scheduling multiple distributed periodic control tasks that communicate via messages with non-zero jitter. The optimization criterion used is a piecewise linear representation of the control performance degradation as a function of the end-to-end latency of the application. The three main contributions of this article are: 1) a constraint programming (CP) formulation to solve this integration problem optimally on time-triggered architectures; 2) an efficient heuristic called Flexi; and 3) an experimental evaluation of the scalability and efficiency of the proposed approaches. In contrast to the CP formulation, which for many real-life problems might have unacceptably long running times, Flexi returns nearly optimal results (0.5 percent loss in control performance compared to optimal) for most problems with more acceptable running times.

Smartphone users require high Battery Cycle Life (BCL) and high Quality of Experience (QoE) during their usage. These two objectives can be conflicting based on the user preference at run-time. Finding the best trade-off between QoE and BCL requires an intelligent resource management approach that considers and learns user preference at run-time. Current approaches focus on one of these two objectives and neglect the other, limiting their efficiency in meeting users’ needs. In this article, we present UBAR, User- and Battery-aware Resource management, which considers dynamic workload, user preference, and user plug-in/out pattern at run-time to provide a suitable trade-off between BCL and QoE. UBAR personalizes this trade-off by learning the user’s habits and using that to satisfy QoE, while considering battery temperature and State of Charge (SOC) pattern to maximize BCL. The evaluation results show that UBAR achieves 10% to 40% improvement compared to the existing state-of-the-art approaches.

Emerging automotive applications such as in-vehicle Augmented Reality (AR) and fully automated parking require a comprehensive understanding of the vehicle’s three-dimensional surrounding represented as anobject-levelenvironmental model. In this model, not only 3D poses (positions and orientations) and 3D sizes of detected objects are registered, but 3D shapes (geometries) need to be reconstructed precisely. A combination of 3D object detection and 3D surface reconstruction techniques, referred to asobject-level 3D reconstruction, is fundamental to building such environmental models. However, the possibilities to incorporate object-level 3D reconstruction in a car have not been sufficiently explored either in academic research or in the industry. This primarily stems from the cost and resource constraints associated with the automotive domain. In this paper, we address these constraints by proposing implementations ofin-vehicle object-level 3D reconstructionin two specific use cases:(i)augmented reality and(ii)automated parking. For augmented reality, we propose a cost-efficient solution called monocular3D Shapingthat requires only a single frame from a monocular camera as input. For automated parking, we propose a resource-efficient alternative that generates more precise 3D reconstruction results by taking advantage of additional 3D sensors (such as Lidars). The crux of our proposed approaches lies in the use of aLatent Shape Space, where various 3D shapes are represented using only two parameters. As a result, highly complex 3D shapes can now be transmitted using a low- to medium-bandwidth in-vehicle communication infrastructure in a cost-effective manner.

Hearing screening devices emit an acoustic signal in the outer ear, which invokes a specific response from a healthy inner ear. However, the high cost of such devices prevents widely deploying them in schools or private homes, especially in developing countries. In this paper, we for the first time show that such tests are also feasible with a device that consists of only one speaker for emitting the signal and using the same speaker - now as a microphone - for also recording the response. Existing devices rely on a speaker and microphone pair, which makes them significantly more complex and costly. We further outline the embedded systems and signal processing challenges that such a setup entails. If successful, it has the potential to make hearing screening available to a much wider population in developing countries.

Power management is quintessential to the successful deployment of edge devices, such as smartphones, in power-, thermal-, and energy-constrained environments. Governors and schedulers operate system sub-routines for power management at the edge. There exist several tools for debugging power issues in Android applications. However, there exists no tool to identify and classify inevitable misdecisions by power managers, given their often inefficient underlying heuristics. In this work, we introduce the first tool - BrezeFlow - designed for unified (scheduling and frequency scaling) power debugging of CPU power managers on Android edge devices. BrezeFlow enables kernel developers to evaluate designs of their power managers retrospectively with closed-source applications in real-world scenarios based on any user-defined strategy and thereby gain insights for better future governor designs. BrezeFlow detected an average of 815 misdecisions per second for the commonly deployed duo, ondemand governor and Completely Fair Scheduler, on mobile edge devices running popular applications.

Modeling and design of automotive systems from a cyber-physical system (CPS) perspective have lately attracted extensive attention. As the trend towards automated driving and connectivity accelerates, strong interactions between vehicles and the infrastructure are expected. This requires modeling and control of the traffic network in a similarly formal manner. Modeling of such networks involves a tradeoff between expressivity of the appropriate features and tractability of the control problem. Back-pressure control of traffic signals is gaining ground due to its decentralized implementation, low computational complexity, and no requirements on prior traffic information. It guarantees maximum stability under idealistic assumptions. However, when deployed in real traffic intersections, the existing back-pressure control algorithms may result in poor junction utilization due to (i) fixed-length control phases; (ii) stability as the only objective; and (iii) obliviousness to finite road capacities and empty roads. In this paper, we propose a CPS-oriented model of traffic intersections and control of traffic signals, aiming to address the utilization issue of the back-pressure algorithms. We consider a more realistic model with transition phases and dedicated turning lanes, the latter influencing computation of the pressure and subsequently the utilization. The main technical contribution is an adaptive controller that enables varying-length control phases and considers both stability and utilization, while taking both cases of full roads and empty roads into account. We implement a mechanism to prevent frequent changes of control phases and thus limit the number of transition phases, which have negative impact on the junction utilization. Microscopic simulation results with SUMO on a 3×3 traffic network under various traffic patterns show that the proposed algorithm is at least about 13% better in performance than the existing fixed-length backpressure control algorithms reported in previous works. This is a significant improvement in the context of traffic signal control.

Low-power wireless communication is a central building block of Cyber-physical Systems and the Internet of Things. Conventional low-power wireless protocols make avoiding packet collisions a cornerstone design choice. The concept of synchronous transmissions challenges this view. As collisions are not necessarily destructive, under specific circumstances, commodity low-power wireless radios are often able to receive useful information even in the presence of superimposed signals from different transmitters. We survey the growing number of protocols that exploit synchronous transmissions for higher robustness and efficiency as well as unprecedented functionality and versatility compared to conventional designs. The illustration of protocols based on synchronous transmissions is cast in a conceptional framework we establish, with the goal of highlighting differences and similarities among the proposed solutions. We conclude the paper with a discussion on open research questions in this field.

Compared to flat PV arrays, PV cells on curved surfaces such as vehicles, wearable devices and building rooftops have varying inclination angles and therefore, non-uniform operating conditions. Dynamic reconfiguration techniques used for tackling partial shading effects can also be deployed for non-uniform operating conditions on curved surfaces. However, designing a reconfigurable PV system for irregular surfaces is significantly different because the placement of reconfiguration switches should account for the curvature, not just random partial shading patterns. In this paper, we propose a designtime framework for identifying the optimal placement of reconfiguration switch sets as well as a dynamic reconfiguration algorithm for a PV array on a given irregular surface. Case studies performed for different irregular surfaces show that our proposed technique reduces the number of reconfiguration switches by 83% while still generating 81% power compared to having reconfiguration switches on all PV atomic units. While the cost reduction due to the reduced number of switches is marginal in most applications because the PV panel cost dominates the total cost, the technique helps in significantly reducing the wiring harness required for dynamic reconfiguration switches, which is a burden for manufacturing.

In this perspective cum case-study paper, we argue the need for designing timing-predictable vision processing algorithms for autonomous systems. Many core functions in systems like autonomous vehicles involve computer vision within a control loop. Designing such closed-loop controllers and guaranteeing their performance requires the vision processing to be predictable. But this is challenging given the multitude of choices when implementing vision processing algorithms, and the heterogeneity of the architectures (involving GPUs and FPGAs) on which such algorithms are implemented. Towards this, we report a tracing and measurement infrastructure we have been building and illustrate its potential utility using a case study.

The availability of real-world data is a key element for novel developments in the fields of automotive and traffic research. Aerial imagery has the major advantage of recording multiple objects simultaneously and overcomes limitations such as occlusions. However, there are only few data sets available. This work describes a process to estimate a precise vehicle position from aerial imagery. A robust object detection is crucial for reliable results, hence the state-of-the-art deep neural network Mask-RCNN is applied for that purpose. Two training data sets are employed: The first one is optimized for detecting the test vehicle, while the second one consists of randomly selected images recorded on public roads. To reduce errors, several aspects are accounted for, such as the drone movement and the perspective projection from a photograph. The estimated position is comapared with a reference system installed in the test vehicle. It is shown, that a mean accuracy of 20 cm can be achieved with flight altitudes up to 100 m, Full-HD resolution and a frame-by-frame detection. A reliable position estimation is the basis for further data processing, such as obtaining additional vehicle state variables. The source code, training weights, labeled data and example videos are made publicly available. This supports researchers to create new traffic data sets with specific local conditions.

Advertisements, or ads, are a major source of income for Internet-related service companies. Meanwhile, ads and trackers consume significant computing resources and power, which are crucial for mobile devices, and can drain a phone's battery. Moreover, most users find ads annoying, which led to the development of ad blockers. In this paper, we characterize the energy consumption of different ads. We find that ad blocking may either not affect the power consumption at all, or result in power savings of up to 50% dependent on the web site, reducing the battery life of the mobile device. Our studies are based on the ad blocking engines provided by the Brave browser. We believe that our results might impact how such engines can be designed in the future.

The high computation/communication requirements along with reliability needs and limited power budgets necessitate complex processing platforms for emerging autonomous systems. Due to the current focus on performance, however, such platforms are increasingly difficult to predict and analyze. This holds true in terms of both performance (e.g., behavioral and temporal) aspects and power consumption. Ensuring functional safety thus requires new techniques to analyze performance, predictability and power. In this paper, we thus propose a novel hybrid tracing methodology to monitor (and, subsequently, optimize) temporal, functional and energy-related properties of Real-time Systems (RTSs). We target current Programmable SoCs (pSoCs) integrating a fixed-function System-on-Chip (SoC) with flexible Field Programmable Gate Array (FPGA) fabric. Although such heterogeneous systems are well suited for high-end, mixed-hardware/software real-time pipelines, they also offer more complex performance/energy trade-offs than software-only platforms. To systematically exploit this complexity, we present a resource-efficient trace IP core for the pSoC’s fabric and an external measurement/interface system – jointly capturing hybrid power/state traces for subsequent (i.e., offline) analysis. By fusing state data from our IP core with events-of-interest gathered from power traces of pSoC and co-monitored I/O components, we gain a holistic view on temporal RTS aspects. Events and synchronized multi-rail power data jointly extend the debugging coverage via automated identification of processing phases, computation of energy baselines, and estimation of potential savings. Our solution thus integrates functional, temporal and energy monitoring into a single, unified workflow, which, in contrast to traditional separate tools, delivers valuable new insights helpful during debugging and reduces both cost and effort. Experimental evaluations on a Zynq-based Visual Servoing System show the method’s various benefits.

In practice, safety-critical cyber-physical systems (CPS) are often implemented using high quality-of-service (QoS) resources to provide maximum performance in all scenarios. Such implementations are oblivious to the changing criticality levels of CPS based on their physical dynamics (e.g., steady or transient state). Considering that high-QoS resources are constrained for cost-sensitive CPS, such criticality-oblivious implementations are highly inefficient. Towards a tighter dimensioning of these resources, state-of-the-art approaches have considered multi-QoS resources and studied criticality-aware dynamic resource allocation along the lines of mixed-criticality systems. However, these approaches have high implementation overheads. Moreover, in safety-critical domains like automotive and avionics, certification of such dynamic policies is challenging and the implementation platforms typically do not support dynamic reconfiguration. To address these challenges, we present GoodSpread that uses a static scheduling strategy and offers the same performance guarantees while saving resources (more than 50 % in certain cases) compared to the existing dynamic schemes. The main idea here is to spread the high-QoS resources as uniformly as possible over time in order to accommodate the uncertainty of when the criticality level might change. Our proposed strategy studies the physical dynamics to determine the spread factor, i.e., how often the high-QoS resources need to be provisioned. We further propose an extensibility-driven optimization approach to obtain a static schedule that will accommodate future workloads on the remaining resources with maximum flexibility.

There is a demand in the automotive industry to connect two CAN-based subsystems. The commercial CAN-CAN gateway supports basic message forwarding with no real-time behavior. To address this issue, a new gateway architecture is described, on which we present a novel worst-case latency analysis. Specifically, we bound the arrival of the messages at the gateway, which is then used by the Pointer Reachability Exploration (PRE) to derive the interfering message jobs. Our analysis computes a safe gateway latency tighter than the conventional one applied in CAN. Furthermore, we propose a Targeted Priority Assignment (TPA) algorithm that targets at the priorities assigned at the CAN bus and runs a reordering at the gateway to enhance the schedulability. TPA performs better than DMPO (Deadline Monotonic Priority Ordering), while OPA (Audsley's Optimal Priority Assignment) cannot be applied in this context. Evaluation over real-life and scalable CAN message sets is conducted. The reported analysis and priority assignment algorithm are developed for dynamic use to improve the acceptance ratio and can also be deployed statically to provide timing guarantees. This work can be easily extended to support multiple CAN subsystems.

In many wireless control networks, sensor data and controller data are exchanged periodically, which requires periodic packet transmissions between the physical plant and the controller. As an alternative, event-triggered control paradigms imply that data is only exchanged when there are significant changes in the state of the plant, e.g., because of disturbances. This is the nature of many IoT scenarios and requires that a receiving device has to listen to the channel for incoming packets during all times. However, especially in mobile networks, in which all devices are battery-powered, continuous scanning would drain the battery quickly and hence, reception needs to be duty-cycled. When optimizing such duty-cycled operation, significant energy savings are possible using intelligent software-enabled communication scheduling. In this paper, we propose a wireless transmission scheme that supports loosely time-triggered control. When optimizing the scheduling of transmissions and reception windows in the communication protocol, our proposed scheme allows for energy-efficient communication without requiring strict clock-synchronization between the devices. We show that such a scheme is practical and can greatly reduce the energy consumption in event-triggered control applications.

introduction Share on Introduction to the Special Issue on Transportation Cyber-Physical Systems Authors: Samarjit Chakraborty University of North Carolina at St., Chapel Hill, NC University of North Carolina at St., Chapel Hill, NCView Profile , Tian He University of North Carolina at Chapel Hill, Minneapolis, MN University of North Carolina at Chapel Hill, Minneapolis, MNView Profile Authors Info & Claims ACM Transactions on Cyber-Physical SystemsVolume 4Issue 1January 2020 Article No.: 1pp 1–3https://doi.org/10.1145/3372495Online:21 January 2020Publication History 0citation159DownloadsMetricsTotal Citations0Total Downloads159Last 12 Months35Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Bluetooth Low Energy (BLE) is a wireless protocol optimized for low-power communication. To design energy-efficient devices, the protocol provides a number of parameters that need to be optimized within an energy, latency, and throughput design space. Therefore, an energy model that can predict the energy consumption of a BLE-based wireless device for different parameter value settings is needed. As BLE differs from the well-known Bluetooth Basic Rate (BR) significantly, models for Bluetooth BR cannot be easily applied to the BLE protocol. In past years, there have been a couple of proposals on energy models for BLE. However, none of them can model all the operating modes of the protocol. This article presents an energy model of the BLE protocol, which allows the computation of a device’s power consumption in all possible operating modes. To the best of our knowledge, our proposed model is not only one of the most accurate ones known so far (because it accounts for all protocol parameters), but it is also the only one that models all the operating modes of BLE. Based on this model, guidelines for system designers are presented that help choose the right parameters for optimizing the energy consumption. The model is publicly available as a software library for download.

In modern autonomous systems, there is typically a large number of connected components realizing complex functionalities. For example, in autonomous vehicles (AVs), there are tens of millions of lines of code implemented on hundreds of sensors, controllers, and actuators. AVs have been deployed, mostly in trials and restricted environments, showing that substantial progress has been made in functionality development. However, they are still faced with two major challenges: (i) performance guarantee of safety-critical functions under all possible scenarios; (ii) functionality implementation with limited resources. These two challenges are conflicting because safety guarantees necessitate a worst-case analysis that is often very pessimistic for complex hardware/software systems, and thus require more resources. To address this, we study an abstraction of a heterogeneous cyber-physical system architecture consisting of a mix of high- and low-quality resources, such as time- and event-triggered resources, or wired and wireless resources. We show that by properly managing such a mix of resources and formulating a formal verification (model checking) problem, it is possible to tightly dimension the high-quality resource to the minimum (50% in certain cases) while providing control performance guarantees.

A central challenge in designing embedded control systems or cyber-physical systems (CPS) is that of translating high-level models of control algorithms into efficient implementations, while ensuring that model-level semantics are preserved. While a large body of techniques for designing provably correct control strategies exist in the control theory literature, when it comes to transforming mathematical descriptions of these strategies to an efficient implementation, the available means are surprisingly ad hoc in nature. Among other reasons, this is because of (i) implementation platform details not sufficiently being accounted for in controller models, (ii) side effects introduced in the code generation process, (iii) various compiler optimizations whose impact on the dynamics of the plant being controlled not being properly understood, (iv) the presence of analog components on the implementation platform whose behavior is difficult to model, (v) computation and communication delays that exist in an implementation but were not accounted for in the model, and (vi) also the effects of image/video processing whose accuracy and timing behavior are difficult to model. As we move towards designing autonomous systems, these issues become biting problems on the path to certification, and striking a balance between performance and certification. In this position paper, we discuss some of these challenges - that we formulate as the need for modeling the interactions between various implementation layers in a CPS - and potential research directions to address them.

Automotive embedded systems are safety-critical, while being highly cost-sensitive at the same time. The former requires resource dimensioning that accounts for the worst case, even if such a case occurs infrequently, while this is in conflict with the latter requirement. In order to manage both of these aspects at the same time, one research direction being explored is to dynamically assign a mixture of resources based on needs and priorities of different tasks. Along this direction, in this paper we show that by properly modeling the physical dynamics of the systems that an automotive control software interacts with, it is possible to better save resources while still guaranteeing safety properties. Towards this, we focus on a distributed controller implementation that uses an automotive FlexRay bus. Our approach combines techniques from timing/schedulability analysis and control theory and shows the significance of synergistically combining the cyber component and physical processes in the cyber-physical systems (CPS) design paradigm.

The smart energy grid features real-time monitoring of electricity usage such that it can control the generation and distribution of electricity as well as utilize dynamic pricing in response to the demands. For this purpose, smart metering systems continuously monitor the electricity usage of customers, and report it back to the Utility Provider (UP). This raises privacy concerns regarding the undesired exposure of human activity and time-of-use of home appliances. Photovoltaics (PV) and a residential Electrical Energy Storage (EES) have proven to be effective in mitigating the privacy concerns. However, this comes at several costs: Installation of PV and EES, their subsequent aging and the possibly increased electricity cost. We quantify the trade-off between privacy exposure and financial costs by formulating a stochastic dynamic programming problem. Our analysis shows that i) there is a quantifiable trade-off between the financial cost and privacy leakage, ii) proper control of the system is crucial for both metrics, iii) a strategy solely focusing on privacy results in high financial costs, and iv) that for a typical residential setting, the costs for a trade-off solution lie in the range of 600 US$-1700 US$. As the load flattening has a peak shaving effect desirable for UPs, increasing privacy is mutually beneficial for both, customers and UPs.

Recent FPGA architectures integrate various power management features already established in CPU-driven SoCs to reach more energy-sensitive application domains such as, e.g., automotive and robotics. This also qualifies hybrid Programmable SoCs (pSoCs) that combine fixed-function SoCs with configurable FPGA fabric for heterogeneous Real-time Systems (RTSs), which operate under predefined latency and power constraints in safety-critical environments. Their complex application-specific computation and communication (incl. I/O) architectures result in highly varying power consumption, which requires precise voltage and current sensing on all relevant supply rails to enable dependable evaluation of available and novel power management techniques. In this paper, we propose a low-cost 18-channel 16-bit-resolution measurement system capable of over 200 kSPS (kilo-samples per second) for instrumentation of current pSoC development boards. In addition, we propose to include crucial I/O components such as Ethernet PHYs into the power monitoring to gain a holistic view on the RTS's temporal behavior covering not only computation on FPGA and CPUs, but also communication in terms of, e.g., reception of sensor values and transmission of actuation signals. We present an FMC-sized implementation of our measurement system combined with two Gigabit Ethernet PHYs and one HDMI input. Paired with Xilinx' ZC702 development board, we are able to synchronously acquire power traces of a Zynq pSoC and the two PHYs precise enough to identify individual Ethernet frames.

Active cell balancing is the process of equalizing the charge levels of individual cells in a series-connected high power Lithium-Ion battery packs to improve its usable capacity. Several hardware circuit architectures for exchanging charge between the cells and multiple heuristics for controlling the balancing architectures have been proposed in the literature. However, formulating an optimal balancing algorithm that guarantees minimum energy dissipation has not been studied so far. In this paper, for the first time, we propose an optimal cell balancing strategy for minimizing the energy dissipation in a charge equalization process. Our proposed optimization approach consists of two stages. In the first stage, we formulate the charge equalization as a Mixed Integer Linear Programming problem for identifying the set of charge transfer pairs of cells that will guarantee minimum energy dissipation. For these obtained pairs, we compute the lower bound for the balancing time considering the constraints of the balancing architecture. In the second stage, we propose an iterative scheduling strategy to achieve this lower bound by solving an Integer Linear Programming problem at each iteration. Multiple case studies show that our proposed strategy results up to 41% less energy dissipation than the state-of-the-art approaches and always achieves the computed lower bound for the balancing time.

For many embedded systems, such as automotive electronic systems, security has become a pressing challenge. Limited resources and tight timing constraints often make it difficult to apply even lightweight authentication and intrusion detection schemes, especially when retrofitting existing designs. Moreover, traditional hard deadline assumption is insufficient to describe control tasks that have certain degrees of robustness and can tolerate some deadline misses while satisfying functional properties such as stability. In this work, we explore feasible weakly-hard constraints on control tasks, and then leverage the scheduling flexibility from those allowed misses to enhance system's capability for accommodating security monitoring tasks. We develop a co-design approach that 1) sets feasible weakly-hard constraints on control tasks based on quantitative analysis, ensuring the satisfaction of control stability and performance requirements; and 2) optimizes the allocation, priority, and period assignment of security monitoring tasks, improving system security while meeting timing constraints (including the weakly-hard constraints on control tasks). Experimental results on an industrial case study and a set of synthetic examples demonstrated the significant potential of leveraging weakly-hard constraints to improve security and the effectiveness of our approach in exploring the design space to fully realize such potential.

Wireless devices are becoming increasingly pervasive in our everyday life and hence, robust wireless connectivity is a crucial requirement for a host of applications. In particular, with the IoT becoming a reality, an increasing number of wireless devices are frequently brought into their range of reception simultaneously, which need to interact with each other in an ad-hoc fashion. While effective solutions for reliable connected communication exist, establishing a first contact between devices remains the Achilles' heel of mobile wireless devices. For a reliable operation, every device needs to discover all devices in its range within bounded time. Thus, wireless protocols that bound the time within which devices are discovered need to be designed. However, even in such protocols, it is inevitable that a certain fraction of packets sent by multiple devices discovering each other simultaneously collide. As a result, some discoveries fail and a dependable operation can only be realized if the fraction of failed discoveries is kept negligibly low, even in worst-case scenarios. In addition, most devices are battery-powered and rely on a low-power operation for achieving reasonably long battery lifetimes. In this paper, we discuss how wireless protocols can be designed to realize a highly reliable and dependable connection setup, while at the same time meeting the energy-constraints of mobile IoT devices. Towards this, we analyze the challenges in protocol design and discuss which properties of the wireless hardware impact the robustness of the connection setup procedure of IoT devices.

The goal of this paper is to provide a method, which is able to find categories of traffic scenarios automatically. The architecture consists of three main components: A microscopic traffic simulation, a clustering technique and a classification technique for the operational phase. The developed simulation tool models each vehicle separately, while maintaining the dependencies between each other. The clustering approach consists of a modified unsupervised Random Forest algorithm to find a data adaptive similarity measure between all scenarios. As part of this, the path proximity, a novel technique to determine a similarity based on the Random Forest algorithm is presented. In the second part of the clustering, the similarities are used to define a set of clusters. In the third part, a Random Forest classifier is trained using the defined clusters for the operational phase. A thresholding technique is described to ensure a certain confidence level for the class assignment. The method is applied for highway scenarios. The results show that the proposed method is an excellent approach to automatically categorize traffic scenarios, which is particularly relevant for testing autonomous vehicle functionality.

One of the main difficulties in estimating the Worst Case Execution Time (WCET) at the binary level is that machine instructions do not allow inferring call contexts as precisely as source code, since compiler optimizations obfuscate control flow and type information. On the other hand, WCET estimation at source code level can be precise in tracking call contexts, but it is pessimistic for functions that are not available as source code.

Active cell balancing is performed to minimize the variation in the charge levels of the individual cells in a high-power battery pack, to improve its usable capacity. The process of charge equalization is carried out by scheduling pairs of cells to transfer charge over a hardware circuit. Improving the time for charge equalization has been studied in the power electronics and the electronic design automation domains. However, these approaches have focused on the electronics issues and used heuristics to determine the charge transfer schedule. Hence, no optimality results on charge equalization times are known. We, for the first time, take a real-time systems approach and propose an optimal scheduling framework for active cell balancing. The proposed framework employs a hybrid optimization technique consisting of two sequential stages. In the first stage, we solve a mixed-integer linear programming problem to identify the time-optimal set of charge transfers required to achieve charge equalization. In the second stage, we construct a conflict graph based on the obtained charge transfers, to which we apply the minimum vertex coloring algorithm to synthesize the minimum length schedule. Results show that our proposed framework can reduce the charge equalization time by more than 50% (e.g., from 11 h to 5h). Hence, this has real benefits, e.g., in the context of charging electric vehicles. While task and message scheduling problems have been extensively studied in the real-time systems literature, the scheduling problem we study here, has not been addressed before.

In this paper we discuss the problem of relating machine instructions to source level constructs, and how it has been addressed in the domains of Virtual Prototyping (VP) and Worst-Case Execution Time (WCET) analysis. It has been handled in different ways, although the goals and requirements between both domains are not far from another. This paper shows that there exists a mutual benefit in exchanging solutions between the two research domains, by demonstrating the applicability and utility of VP methods for WCET analysis, and highlighting their shortcomings.

Mobile devices apply neighbor discovery (ND) protocols to wirelessly initiate a first contact within the shortest possible amount of time and with minimal energy consumption. For this purpose, over the last decade, a vast number of ND protocols have been proposed, which have progressively reduced the relation between the time within which discovery is guaranteed and the energy consumption. In spite of the simplicity of the problem statement, even after more than 10 years of research on this specific topic, new solutions are still proposed even today. Despite the large number of known ND protocols, given an energy budget, what is the best achievable latency still remains unclear. This paper addresses this question and for the first time presents safe and tight, duty-cycle-dependent bounds on the worst-case discovery latency that no ND protocol can beat. Surprisingly, several existing protocols are indeed optimal, which has not been known until now. We conclude that there is no further potential to improve the relation between latency and duty-cycle, but future ND protocols can improve their robustness against beacon collisions.

Embedded control applications are widely implemented on small, low-cost and resource-constrained microcontrollers, e.g., in the automotive domain. Conventionally, control algorithms are designed using model-based approaches, without considering the details of the implementation platform. This leads to inefficient utilization of the resources. With the emergence of the cyber-physical system (CPS)-oriented thinking, there has lately been a strong interest in co-design of control algorithms and their implementation platforms. Some recent efforts have shown that a schedule on multiple applications with more on-chip cache reuse is able to improve the control performance. However, it has not been studied how the control performance can be maximized for a given schedule and how an optimal schedule can be computed. In this work, we propose a two-stage framework to compute the schedule maximizing the overall control performance of all the applications. First, a holistic controller design taking all the sampling periods and sensing-to-actuation delays in a schedule into account is presented, aiming to maximize the overall control performance. Second, a hybrid search algorithm for discrete decision space is reported to efficiently compute an optimal schedule. Experimental results on a case study with multiple automotive applications show that a significant improvement of 10-20% in control performance can be achieved by the proposed cache-aware scheduling approach.

Embedded control systems are an important and often safety-critical class of applications that need to operate reliably even in the presence of faults. We show that intermittent fault scenarios caused by wear-out effects due to a higher density and a smaller geometry of the embedded electronic components may become a reliability concern for real-time embedded control applications. To mitigate the effects of such intermittent faults, we propose a novel fault-tolerant controller design method such that the resulting controllers ensure closed loop stability (i.e., guarantee safety) with only possibly degraded performance under such fault scenarios. In order to measure the amortized performance offered by the software implementations of such fault-tolerant controllers, we provide a program analysis methodology that statically estimates the quality of control guaranteed by the C code implementation of the fault-tolerant control law. This combination of fault-tolerant controller design followed by performance feedback computed using a formal analysis is illustrated with a case study from the automotive domain.

Wired fieldbuses have long been proven effective in supporting Cyber-Physical Systems (CPS). However, various domains are now striving for wireless solutions due to ease of deployment or novel functionality requiring the ability to support mobile devices. Low-power wireless protocols have been proposed in response to this need, but requirements of a large class of CPS applications can still not be satisfied. We thus propose Time-Triggered Wireless (TTW), a distributed low-power wireless system design that minimizes communication energy consumption and offers end-to-end timing predictability, runtime adaptability, reliability, and low latency. Evaluation shows a 2× reduction in communication latency and 33-40% lower radio-on time compared with DRP, the closest related work, validating the suitability of TTW for new exciting wireless CPS applications.

Flexible photovoltaic (PV) arrays often have to be mounted on surfaces that have a significant amount of curvature. These include solar-powered vehicles, planes, and also some wearable devices. However, this inevitably leads to non-uniform solar irradiance among connected PV cells. If one cell among series-connected PV cells receives significantly lower solar irradiance, the overall power generation of the string is reduced. While previous works dealt with this by employing sophisticated run-time techniques, we show that design-time approaches that determine the electrical series-parallel connection of a PV array could also significantly enhance the power output. In this paper, we propose a k-means clustering-based algorithm to group PV cells/modules with similar solar irradiance to form a PV string, even allowing irregular arrays, to maximize the power generation of the array for a given irradiance profile. Our experimental results show that the power generation of a PV array could be increased by 84% compared to usual PV array organizations that do not take the curvature of the mounted surface into account.

Short drive range due to limited battery capacity and high battery depreciation costs persist to be the main deterrents to the wide adoption of Electric Vehicles (EVs). High power battery packs consisting of a large number of battery cells require extensive management, such as State of Charge (SOC) balancing and thermal management, in order to keep the operating conditions within a safe and efficient range. In this paper, we propose a novel State of Health (SOH)-aware active cell balancing technique, which is capable of extending the cycle life of the whole battery pack. In contrast to the state-of-the-art active cell balancing techniques, the proposed technique reduces the load current of cells with low SOH using the active cell balancing architecture. Based on the observation that assigning the smallest possible load current to cells with lower SOH extends cycle life, the technique identifies the most beneficial charge transfers. We find that with our proposed scheme, aging could be mitigated by up to 23.5% over passive cell balancing and 17.6% over active SOC cell balancing.

With the increasing use of Ethernet-based communication backbones in safety-critical real-time domains, both efficient and predictable interfacing and cryptographically secure authentication of high-speed data streams are becoming very important. Although the increasing data rates of in-vehicle networks allow the integration of more demanding (e.g., camera-based) applications, processing speeds and, in particular, memory bandwidths are no longer scaling accordingly. The need for authentication, on the other hand, stems from the ongoing convergence of traditionally separated functional domains and the extended connectivity both in- (e.g., smart-phones) and outside (e.g., telemetry, cloud-based services and vehicle-to-X technologies) current vehicles. The inclusion of cryptographic measures thus requires careful interface design to meet throughput, latency, safety, security and power constraints given by the particular application domain. Over the last decades, this has forced system designers to not only optimize their software stacks accordingly, but also incrementally move interface functionalities from software to hardware. This paper discusses existing and emerging methods for dealing with high-speed data streams ranging from software-only via mixed-hardware/software approaches to fully hardware-based solutions. In particular, we introduce two approaches to acquire and authenticate GigE Vision Video Streams at full line rate of Gigabit Ethernet on Programmable SoCs suitable for future heterogeneous automotive processing platforms.

High power Lithium-Ion (Li-Ion) battery packs used in stationary Electrical Energy Storage (EES) systems and Electric Vehicle (EV) applications require a sophisticated Battery Management System (BMS) in order to maintain safe operation and improve their performance. With the increasing complexity of these battery packs and their demand for shorter time-to-market, decentralized approaches for battery management, providing a high degree of modularity, scalability and improved control performance are typically preferred. However, manual design approaches for these complex distributed systems are time consuming and are error-prone resulting in a reduced energy efficiency of the overall system. Here, special design automation techniques considering all abstraction-levels of the battery system are required to obtain highly optimized battery packs. This paper presents from a design automation perspective the recent advances in the domain of battery systems that are a combination of the electrochemical cells and their associated management modules. Specifically, we classify the battery systems into three abstraction levels, cell-level (battery cells and their interconnection schemes), module-level (sensing and charge balancing circuits) and pack-level (computation and control algorithms). We provide an overview of challenges that exist in each abstraction layer and give an outlook towards future design automation techniques that are required to overcome these limitations.

For future autonomous vehicles, the system development life cycle must keep up with the rapid rate of innovation and changing needs of the market. Waterfall is too slow to react to such changes, and therefore, there is a growing emphasis to adopt Agile development concepts in the automotive industry. Ensuring requirements traceability, and thus proving functional safety, is a serious challenge in this direction. Modern cars are complex cyber-physical systems and are traditionally designed using a set of disjoint tools, which adds to the challenge. In this paper, we point out that multi-domain coupling and design automation using correct-by-design approaches can lead to safe designs even in an Agile environment. In this context, we study current industry trends. We further outline the challenges involved in multi-domain coupling and demonstrate using a state-of-the-art approach how these challenges can be addressed by exploiting domain-specific knowledge.

Over the last years, web browsing has been steadily shifting from desktop computers to mobile devices like smartphones and tablets. However, mobile browsers available today have mainly focused on performance rather than power consumption, although the battery life of a mobile device is one of the most important usability metrics. This is because many of these browsers have originated in the desktop domain and have been ported to the mobile domain. Such browsers have multiple power hungry components such as the rendering engine, and the JavaScript engine, and generate high workload without considering the capabilities and the power consumption characteristics of the underlying hardware platform. Also, the lack of coordination between a browser application and the power manager in the operating system (such as Android) results in poor power savings. In this paper, we propose a power manager that takes into account the internal state of a browser -- that we refer to as a phase -- and show with Google's Chrome running on Android that up to 57.4% more energy can be saved over Android's default power managers. We implemented and evaluated our technique on a heterogeneous multiprocessing (HMP) ARM big.LITTLE platform such as the ones found in most modern smartphones.

In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known NP-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.

Cyber-physical systems are systems for which physical processes, control algorithms that control these processes, and the computation and communication platforms on which these control algorithms are implemented must be modeled and designed in a tightly integrated fashion. However, currently available methods and tools are not equipped to handle such integrated modeling and design. Instead different tools are used by different teams to design different parts of the system, which at the end become incompatible. This results in costly integration and debugging processes. Instead, we need automated synthesis approaches that encompass multiple domains - like control algorithms, and also their implementations - and can synthesize complete systems from their partial specifications. In this paper, we discuss the challenges in developing such approaches and possible solutions.

Active cell balancing is the process of improving the usable capacity of a series-connected Lithium-Ion (Li-Ion) battery pack by redistributing the charge levels of individual cells. Depending upon the State-of-Charge (SoC) distribution of the individual cells in the pack, an appropriate charge transfer pattern (cell-to-cell, cell-to-module, module-to-cell or module-to-module) has to be selected for improving the usable energy of the battery pack. However, existing active cell balancing circuits are only capable of performing limited number of charge transfer patterns and, therefore, have a reduced energy efficiency for different types of SoC distribution. In this paper, we propose a modular, multi-pattern active cell balancing architecture that is capable of performing multiple types of charge transfer patterns (cell-to-cell, cell-to-module, module-to-cell and module-to-module) with a reduced number of hardware components and control signals compared to existing solutions. We derive a closed-form, analytical model of our proposed balancing architecture with which we profile the efficiency of the individual charge transfer patterns enabled by our architecture. Using the profiling analysis, we propose a hybrid charge equalization strategy that automatically selects the most energy-efficient charge transfer pattern depending upon the SoC distribution of the battery pack and the characteristics of our proposed balancing architecture. Case studies show that our proposed balancing architecture and hybrid charge equalization strategy provide up to a maximum of 46.83% improvement in energy efficiency compared to existing solutions.

The problem of schedulability analysis, i.e., determining whether a given task set meets its deadline constraints, has been extensively studied in the real-time systems literature. However, if a task set is not schedulable, then the schedulability analysis results using known techniques (such as utilization-based tests) offer little insight into which task parameters could be changed or refined, in order to make the task set schedulable. To address this problem, we encode the schedulability analysis problem as an equivalent model checking problem. By analyzing the counterexamples reported by the model checker, we discover subsets of values of task parameters that lead to timing violations. We propose a procedure that iteratively refines the task specification by rejecting these subsets, thereby converging towards schedulability. We believe that this approach would be useful for timing debugging of real-time systems, which has received relatively less attention in the literature, especially given its practical relevance.

Compiler optimizations are widely used to enhance the average case performance of software, and these techniques are very effective and advance with every compiler version. However, in realtime systems, it is the worst-case performance that matters. While there are techniques that aim at reducing the worst-case execution time (WCET), most of them are specific to certain targets and not implemented in mainstream compilers. In this paper, we present our ongoing work for a generic approach to harness the power of existing compiler optimizations for WCET reduction.

Software-based control of physical systems is common in domains such as automotive, avionics, and industrial automation. Safety of such systems is determined by control-theoretic properties such as stability, settling time, and peak overshoot. These properties strongly depend on the software code generated from high-level controller models, and the implementation of such code on an embedded platform. To ensure safety, the semantics of the system model considered for controller design must be faithfully preserved in the platform implementation. However, traditionally, controller design and implementation platform design are carried out in isolation, followed by their integration, which often relies on simulations to estimate the behavior of the controllers. Thus, safety properties that were proven at the model level using control-theoretic tools can no longer be established in an actual implementation. This makes the design of embedded control systems costly, error prone, and hinders certification. In this paper, we review recent efforts in control-platform cosynthesis techniques toward addressing this problem. Here, the control and the embedded systems communities have come together to adopt a cyber-physical system (CPS)-oriented design paradigm. This cosynthesis paradigm integrates the design of control algorithms and platform parameters within a holistic optimization framework and accounts for relevant details from both sides. We survey the evolution of design approaches for such cosynthesis and show how-the originally disjoint-controller and the platform design methods are gradually converging.

Automotive functionalities typically consist of a large set of periodic/cyclic tasks scheduled under a real-time operating system (OS). Many of the tasks are feedback control applications with stringent performance requirements. OSEK/VDX is a common class of automotive OS that offers preemptive periodic schedules supporting a pre-configured set of periods. The feedback controllers implemented onto such OSEK/VDX-compliant systems need to use one of the pre-configured (sampling) periods. A shorter period is often desired for a higher control performance, and this implies a higher processor load. For a given performance requirement, the longest sampling period that meets this requirement is the optimal one. Given a limited set of pre-configured periods, such optimal sampling periods are often not available, and the practice is to choose a shorter available period—leading to a higher processor load. To address this, we propose a controller that cyclically switches among the available periods, thereby leading to an average sampling period closer to the optimal one. This way, we reduce the processor load and are able to pack more control applications on the same processor. The main challenge in this article is the design of such controllers that takes into account such cyclic switching of sampling periods (i.e., use non-uniform sampling). The controller needs to meet specified performance requirements (settling time) and system constraints (e.g., input saturation). Such a non-convex constrained controller optimization problem as raised in the OS-aware automotive systems design has not been addressed in the traditional optimal control literature. A novel approach based on adaptively parameterized particle swarm optimization (PSO) is proposed to solve it. Using the OS-aware controller design with non-uniform sampling, we show that a higher number of applications can be packed on a processor, which is of particular interest in the cost-sensitive automotive industry.

Neighbor discovery is the procedure in which two wireless devices initiate a first contact. In low power ad-hoc networks, radios are duty-cycled and the latency until a packet meets a reception phase of another device is determined by a random process. Most research considers slotted protocols, in which the points in time for reception are temporally coupled to beacon transmissions. In contrast, many recent protocols, such as ANT/ANT+ and Bluetooth Low Energy (BLE) use a slotless, periodic-interval based scheme for neighbor discovery. Here, one device periodically broadcasts packets, whereas the other device periodically listens to the channel. Both periods are independent from each other and drawn over continuous time. Such protocols provide 3 degrees of freedom (viz., the intervals for advertising and scanning and the duration of each scan phase). Though billions of existing BLE devices rely on these protocols, neither their expected latencies nor beneficial configurations with good latency-duty-cycle relations are known. Parametrizations for the participating devices are usually determined based on a “good guess”. In this paper, we, for the first time, present a mathematical theory which can compute the neighbor discovery latencies for all possible parametrizations. Further, our theory shows that upper bounds on the latency can be guaranteed for all parametrizations, except for a finite number of singularities. Therefore, slotless, periodic interval-based protocols can be used in applications with deterministic latency demands, which have been reserved for slotted protocols until now. Our proposed theory can be used for analyzing the neighbor discovery latencies, for tweaking protocol parameters and for developing new protocols.

Current automotive E/E architectures are comprised of hardware and software and are mostly designed in a monolithic approach, static over the lifetime of the vehicle. Design, implementation and updates are mostly performed on a per-component-basis, exchanging complete Electronic Control Units (ECUs) or their software image as a whole. With an increasing amount of functionality being realized in software, the benefits of software can be used increasingly. This includes modularization of components, which forms the basis for updates and addition of functions. Additionally, this modularization allows the consolidation of ECUs and supports a higher level of integration. Such modularization and dynamic behavior over the lifetime of a vehicle feet, as well as a single vehicle does, however, hold a lot of challenges for safety-critical systems. Safety-critical systems, such as cars, require their behavior to be deterministic. The design of such modular systems needs to consider and cope with uncertainties in modular architectures. This paper highlights some of the dimensions of uncertainty, which will exist in future E/E architectures and presents initial approaches on how to manage these.

Modern automotive systems consist of hundreds of functionalities implemented in software. Moreover, these functionalities are constantly evolving with increasing demand for automation, industry competition and changing sensor and actuator capabilities. Correspondingly, it is important to adapt the engineering and software development processes for such systems to consider fast management of this evolution at minimum cost. Towards this, in this paper, we outline three different problems in the context of evolving automotive software and discuss potential solutions for each of them. First, we outline a framework that can accommodate variability in specifications while developing software for automotive product lines. Secondly, a technique is illustrated to addresses after-sales addition of new features in existing systems by studying corresponding acceptable performance degradation of existing functionalities. Finally, we discuss how an inconsistency management framework and regression verification can ensure consistent evolution of engineering processes for automotive mechatronic systems.

Increasingly more software-based applications are being developed and deployed in modern vehicles. As a result, the extensibility of a system design has become an important issue in order to accommodate more future applications and update of existing ones on one hand and reduce the effort and cost of re-design, test and validation on the other. In this paper, we discuss the extensibility-driven design in the automotive E/E architecture. We explain the motivation for such a design objective and discuss the definition of extensibility metric and extensibility-driven design methods under two different setting, namely the system based on CAN bus and FlexRay bus. Based on these two examples, we illustrate the importance and advantages of extensibility-driven design in the automotive E/E architecture.

Games are one of the most popular and at the same time most computation intensive and energy consuming class of applications on mobile devices like smartphones and tablets. Dynamic voltage and frequency scaling (DVFS) is a common technique for reducing the processing power. However, highly variable and non-deterministic workload characteristics of mobile games mandate sophisticated workload prediction models to predict low-utilization phases of games during which the processor's frequency can be decreased to save energy. While prior works exhibit significant improvements, one main question is left open: How large is the gap between the developed techniques and the theoretically optimal power manager, i.e., a power manager which exactly knows the future workload and, hence, can select the optimal sequence of frequencies that minimizes the power consumption under given timing constraints. In this paper, we discuss that estimating the savings from such an optimal power manager is non-trivial due to the non-deterministic nature of games and the underlying system. In order to address this, we suggest a statistical model of the optimal power manager using which we estimate the potential savings of popular closed-source games. The results of our work have several implications: We reveal a significant gap between savings obtained from recently proposed game power managers and the theoretically optimum savings (up to 54.4% energy savings are possible). Our work strongly motivates future research endeavors to minimize the gap between the optimum and the existing power managers.

The process of two wireless devices meeting over-the-air for the first time is referred to as neighbor discovery. In mobile ad-hoc networks, battery powered devices duty-cycle their radios during neighbor discovery. As a result, they transmit and receive for very short durations of time and sleep at other times. Energy-efficient protocols, which guarantee short, bounded latencies while achieving low energy-consumptions are highly important for long battery lifetimes. In the past, neighbor discovery has been carried out mostly using slotted protocols, which subdivide time into multiple, equal length periods, called slots. An alternative are slotless protocols, which decouple beaconing from listening and can potentially achieve lower latency-duty-cycle-relations. As in slotted protocols, they also guarantee bounded latencies. However, understanding the mechanisms that ensure these deterministic bounds is more complex than for slotted protocols, since they rely on less intuitive concepts. In this demo, we propose a setup that visualizes the operation of two radios with slotless protocols in real-time, thereby providing insights that help in understanding slotless neighbor discovery. This demo is supposed to accompany the paper entitled "Griassdi: Mutually Assisted Slotless Neighbor Discovery Protocols", which appeared at IPSN 2017 as a regular paper.

Recent results show that slotless, purely-interval based neighbor discovery protocols, in which time is assumed to be continuous, achieve significantly lower worst-case discovery latencies than time-slotted protocols. In slotted protocols, the discovery of device A by B and vice-versa occurs within the same slot, and hence the latencies for one-way and two-way discovery are identical. However, in purely interval-based protocols, these latencies are independent from each other, leading to longer mean latencies for two-way discovery. In this paper, we propose a cooperative approach to reduce this two-way discovery latency. In particular, each side broadcasts information on the time-period until its next reception phase takes place. The remote device adjusts its beacon schedule accordingly once a first packet is received. Compared to non-cooperative slotless protocols, this technique can reduce the two-way discovery latency by up to 43 %. We propose a theory to model such protocols and show that with an optimized schedule, our proposed protocol achieves considerably shorter mean latencies than all known protocols, while still guaranteeing worst-case latencies that are similar to the best known solutions. For example, compared to Searchlight-Striped, our proposed protocol achieves by up to 89 % lower mean latencies and by up to 86 % lower worst-case latencies.

Recent advances in battery and drone technologies have opened up possibilities of commercial use of drones. Private companies are looking into the possibilities of using drones for commercial deliveries from the legal, technical, and economical perspective. Nevertheless, the battery management perspective of such businesses has not yet been thoroughly investigated. In this paper, we identify that battery management of such application has a major impact of the costs, and formulate an optimization problem to reduce the aging of batteries. We identify two sub-problems, battery assignment, and battery scheduling to derive a solution that minimizes the aging of the batteries. We show that the formulation enables leveraging the trade-off relationships between the packet waiting time and battery purchasing cost. The experimental results show the proposed method reduce the electricity and battery purchasing cost by 25%, and average packet waiting time by more than 50%.

The design of automotive in-vehicle networks is influenced by several factors like bandwidth, real-time properties, reliability and cost. This has led to a number of protocols and communication standards like CAN, MOST, FlexRay and more recently the use of Ethernet. In the future, wireless in-vehicle communication might also become a possibility. In all of these cases, often hybrid schemes such as the combination of time-triggered (TT) and event-triggered (ET) paradigms have been considered to be useful. Thus, hybrid protocols like FlexRay and TTEthernet, offering advantages of TT and ET communications, are becoming more popular. However, until now the hybrid nature of the protocols has not been exploited in application design. In this paper, we will discuss design strategies for automotive control applications that exploit the hybrid nature of the underlying communication architecture on which they are mapped. Towards this, we will consider a mix of time- and event-triggered schemes as well as a combination of reliable and unreliable communication. Correspondingly, we will show how appropriate abstractions of these hybrid schemes could be lifted to the application design stage.

The rapid growth in the size and complexity of modern Cyber-Physical Systems (CPS) imposes increasing demand for the embedded resources, especially the communication resources. As a result, resource-efficient CPS design has become an important issue. Towards the design of networked embedded control systems, a major branch of CPS, reliable and deterministic communication is able to achieve satisfactory control performance. However, the amount of this type of resource that can be provided by the embedded platform is often limited. On the other hand, it is difficult to guarantee the control performance with non-deterministic communication resources, due to their unpredictable behavior. In this paper, we propose a novel control scheme to efficiently utilize elastic communication resources. In general, the non-deterministic communication resources are flexibly deployed on top of the deterministic communication resources to achieve stability and good control performance. In the rare worst-case, when non-deterministic communication is completely unavailable, the deterministic communication resources are used to guarantee stability and the control performance satisfying the design requirement. The experimental results show that the performance of the control application is ensured to satisfy the design requirement in the worst case and that better control performance is achieved when non-deterministic resources are available.

Modern vehicles employ a large amount of distributed computation and require the underlying communication scheme to provide high bandwidth and low latency. Existing communication protocols like Controller Area Network (CAN) and FlexRay do not provide the required bandwidth, paving the way for adoption of Ethernet as the next generation network backbone for in-vehicle systems. Ethernet would co-exist with safety-critical communication on legacy networks, providing a scalable platform for evolving vehicular systems. This requires a high-performance network gateway that can simultaneously handle high bandwidth, low latency, and isolation; features that are not achievable with traditional processor based gateway implementations. We present VEGa, a configurable vehicular Ethernet gateway architecture utilising a hybrid FPGA to closely couple software control on a processor with dedicated switching circuit on the reconfigurable fabric. The fabric implements isolated interface ports and an accelerated routing mechanism, which can be controlled and monitored from software. Further, reconfigurability enables the switching behaviour to be altered at runtime under software control, while the configurable architecture allows easy adaptation to different vehicular architectures using highlevel parameter settings. We demonstrate the architecture on the Xilinx Zynq platform and evaluate the bandwidth, latency, and isolation using extensive tests in hardware.

Control applications are often implemented on highly cost-sensitive and resource-constrained embedded platforms, such as microcontrollers with a small on-chip memory. Typically, control algorithms are designed using model-based approaches, where the details of the implementation platform are completely ignored. As a result, optimizations that integrate platform-level characteristics into the control algorithms design are largely missing. With the emergence of cyber-physical systems (CPS)-oriented thinking, there has lately been a strong interest in co-design of control algorithms and their implementation platforms, leading to work on networked control systems and computation-aware control algorithms design. However, there has so far been no work on integrating the characteristics of a memory architecture into the design of control algorithms. In this paper we, for the first time, show that accounting for the impact of on-chip memory (or cache) reuse on the performance of control applications motivates new techniques for control algorithms design. This leads to significant improvement in quality of control for given resource availability, or more efficient implementations of embedded control applications. We believe that this paper opens up a variety of possibilities for memory-related optimizations of embedded control systems, that will be pursued by researchers working on computer-aided design for CPS.

Active cell balancing improves the performance of a battery pack by transferring charge from one cell to another. Associated design questions require multiple simulations with 100 cells over several hours. Since the most efficient transfer methods switch between phases in the kilohertz range, these simulations require high computational effort or reduced accuracy. To enable detailed analysis on a large scale, this paper includes state-of-the-art electrical battery models in active balancing simulation while keeping the computation effort for one transfer in the low millisecond range. This is achieved in three steps. First, we model the dynamics of each transfer phase using standard equivalent circuit abstraction. Next, we find closed form equations for the so-defined phase dynamics, yielding an iterative approach that saves computation time by replacing the numerical solver. Finally, we employ error control techniques to aggregate phases in that iteration, systematically reducing the millions of phase evaluations that would be necessary otherwise. Our experiments show that the speedup from equivalent circuit dynamics to error-controlled aggregation almost reaches five orders of magnitude while introducing virtually no additional error. This enables simulations of realistic balancing scenarios in less than a second and is hence suitable for design space exploration.

FlexRay is a hybrid communication protocol tailored to the requirements in the automotive domain, supporting both time-triggered and event-triggered communication with high data-rates. The time-triggered static segment is commonly used for in-vehicle communication while the event-triggered dynamic segment is used for diagnostics and configuration. This paper addresses the problem of synthesizing schedules for the static FlexRay segment for asynchronous scheduling, following the design approach of current automotive architectures. Previous approaches largely focused on FlexRay 2.1 while the few existing approaches for FlexRay 3.0 are nonoptimal in several aspects. As a remedy, our framework makes use of all new features of version 3.0 while supporting the still predominantly used FlexRay 2.1, making it backward compatible. The following approaches are proposed: 1) a single-stage integer linear programming (ILP) approach that determines an optimal solution but does not scale; 2) a multistage ILP for combining previously generated subsystem schedules to a global schedule. It clearly improves the scalability but is not optimal. The multistage approach allows to integrate and convert existing FlexRay 2.1 schedules into a FlexRay 3.0 schedule which is important for legacy reasons, i.e., to reduce testing and certification efforts; 3) a greedy heuristic which scales well and obtains high quality solutions in comparison with the optimal solution, but is unsuitable to integrate existing schedules; and 4) metaheuristic approaches based on genetic algorithms or simulated annealing to evaluate the benefits of the proposed approaches.

Due to the growing interconnectedness and complexity of in-vehicle networks, in addition to safety, security is becoming an increasingly important topic in the automotive domain. In this paper, we study techniques for detecting security infringements in automotive electrical and electronic (E/E) architectures. Toward this we propose in-vehicle network traffic monitoring to detect increased transmission rates of manipulated message streams. Attacks causing timing violations can disrupt safety-critical functions and have severe consequences. To reduce costs and prevent single points of failure, our approach enables an automatic distribution of detection tasks among selected E/E architecture components, such as a subset of electronic control units. First, we analyze a concrete E/E system architecture to determine the communication parameters and properties necessary for detecting security attacks. These are then used for a parametrization of the corresponding detection algorithms and the distribution of attack detection tasks. We use a lightweight message monitoring method and optimize the placement of detection tasks to ensure a full-coverage of the E/E system architecture and a timely detection of an attack.

With the increasing amount of interconnections between vehicles, the attack surface of internal vehicle networks is rising steeply. Although these networks are shielded against external attacks, they often do not have any internal security to protect against malicious components or adversaries who can breach the network perimeter. To secure the in-vehicle network, all communicating components must be authenticated, and only authorized components should be allowed to send and receive messages. This is achieved through the use of an authentication framework. Cryptography is widely used to authenticate communicating parties and provide secure communication channels (e.g., Internet communication). However, the real-time performance requirements of in-vehicle networks restrict the types of cryptographic algorithms and protocols that may be used. In particular, asymmetric cryptography is computationally infeasible during vehicle operation. In this work, we address the challenges of designing authentication protocols for automotive systems. We present Lightweight Authentication for Secure Automotive Networks (LASAN), a full lifecycle authentication approach. We describe the core LASAN protocols and show how they protect the internal vehicle network while complying with the real-time constraints and low computational resources of this domain. By leveraging the fixed structure of automotive networks, we minimize bandwidth and computation requirements. Unlike previous work, we also explain how this framework can be integrated into all aspects of the automotive product lifecycle, including manufacturing, vehicle maintenance, and software updates. We evaluate LASAN in two different ways: First, we analyze the security properties of the protocols using established protocol verification techniques based on formal methods. Second, we evaluate the timing requirements of LASAN and compare these to other frameworks using a new highly modular discrete event simulator for in-vehicle networks, which we have developed for this evaluation.

High-voltage battery packs consist of series-connected lithium-ion cells and require sophisticated battery management systems (BMSs) to maintain safe operating conditions. Active cell balancing is an important task of a BMS, performed in order to improve the usable capacity of the battery pack by equalizing the charge levels of individual cells. With the emerging trend of distributed BMS topologies, the associated balancing architectures are required to be modular, consisting of homogeneous units that minimize integration efforts. In this paper, we propose a modular active charge balancing architecture along with its control scheme for implementation toward such distributed BMSs. Compared with existing approaches, our proposed architecture provides increased charge transfer capabilities, with reduced hardware and control complexity. We propose a closed-form analytical model of the balancing architecture, which can be used to perform fast system-level simulation studies and design space exploration for analyzing efficient device combinations. A hardware implementation of the proposed balancing architecture is developed and measurements made with it are used to validate each part of our analytical model. Using the validated analytical model, we performed a case study, which shows that our proposed architecture provides a 14.5 % improvement in charge transfer efficiency compared with existing approaches.

This paper presents an overview of recent trends in Battery System Management Architectures (BSMAs). After introducing the main characteristics of large battery packs, the state of the art in BSMAs is discussed. Two emerging concepts are in the focus of this contribution. On the one hand, there is a development from centralized battery management architectures with a single control entity towards decentralized management where the computational resources are distributed across the battery pack and, hence, move closer to the individual battery cells. This enables a more scalable and modular battery system architecture, while, at the same time, posing challenges regarding hardware and management algorithm design. On the other hand, the static setup of the series- and parallel-connected cells forming the battery pack may be developed towards a reconfigurable architecture such that the electrical topology of the pack can be adaptively changed. Such reconfigurability could increase the reliability of battery packs and reduce management efforts such as cell balancing. At the same time, limited energy efficiency of the additional hardware poses a challenge. We give an outlook how these two trends could be combined into distributed reconfigurable BSMAs. This introduces a set of challenges which have to be solved in order to benefit from the increased scalability, reliability and safety such designs could offer.

One emerging research direction to address the design of Cyber-Physical Systems (CPS) is the co-design of the architecture and the controllers. The co-design techniques integrate the design of control and architecture in an early phase and the parameters on both sides can be synthesized according to certain design objectives. This explores the characteristics on both sides to achieve more efficient design of such systems. In this paper, we give an overview of the automated synthesis of CPS from joint controller/architecture specifications by explaining the background and motivation for such methods and illustrating this design paradigm with a concrete example of a FlexRay-based embedded control system. Furthermore, we provide the future outlook in this direction by explaining possible extensions and the related challenges.

Automotive platforms today run hundreds of millions of lines of software code implementing a large number of different control applications spanning across safety-critical functionality to driver assistance and comfort-related functions. While such control software today is largely designed following model-based approaches, the underlying models do not take into account the details of the implementation platforms, on which the software would eventually run. Following the state-of-the-art in control theory, the focus in such design is restricted to ensuring the stability of the designed controllers and meeting control performance objectives, such as settling time or peak overshoot. However, automotive platforms are highly cost-sensitive and the issue of designing “resource-efficient” controllers has largely been ignored so far and is addressed using very ad hoc techniques. In this paper, we will illustrate how, following traditional embedded systems design oriented thinking, computation, communication and memory issues can be incorporated in the controller design stage, thereby resulting in control software not only satisfying the usual control performance metrics but also making efficient utilization of the resources on distributed automotive architectures.

Drones, also referred to as unmanned aerial vehicles (UAVs), are recently expanding their field of usage beyond military surveillance and tactical applications. Commercial drone delivery service is one of the promising applications in the near future, and a number of companies are already pushing forward the legal and technical barriers to realize the concept. Unlike conventional applications of drones, the success of a commercial application depends critically on the profitability. The major sources of expense are the electricity cost and battery purchasing cost due to aging. Hence, it is crucial to maximize the energy efficiency and mitigate battery aging of the drone delivery business. However, no prior work has extensively assessed the problem for the business as a whole. This paper, for the first time, proposes a holistic and detailed analysis on the profitability and time to delivery of the drone delivery business. This paper identifies the major design parameters and runtime management potentials that affect the profitability and time to delivery of the business. We have implemented a discrete event simulator based on detailed models of the comprising components. We perform a design space exploration to understand the effects of the various battery configurations, battery attachment technique, drone flight speed, etc., on time to delivery, electricity cost, and battery purchasing cost. Our results show that such control knobs have a significant impact on the time to delivery and the operating cost of the business.

The development of automotive electronics and software systems is often associated with high costs due to their multi-domain nature (including control engineering, electronics, hydraulics, mechanics, etc). The involvement of these different disciplines makes it difficult for control engineers to test their controllers with them being integrated in the whole system, in early development phases. By introducing the "XiL approach", ETAS wants to leverage virtualization techniques in order to bring embedded systems to the desk of every developer. The XiL approach implies fast development cycles due to easy integration of software, vehicle and plant components on the PC. XiL strives for seamless transition between X-in-the-loop setups, with X representing any control model (M), software (S), or hardware (H) under test. This paper will outline this methodology with an engine management system example.

Games belong to the most popular but power-hungry applications on smartphones. Gaming workloads exhibit highly variable and user-interactive behavior, which makes it hard to predict the workload. Modern MPSoC (multiprocessor system-on-chip) platforms are equipped with heterogeneous multi-processing (HMP) processors comprising performance-oriented and energy-efficiency cores in order to better exploit power-performance trade-offs among different types of applications. To minimize the energy consumption of games on HMP platforms, it is essential to precisely predict the gaming workload and perform joint thread-to-core allocation as well as dynamic voltage and frequency scaling (DVFS). In this paper, we propose a frame- and thread-based MPSoC power management strategy for games. We focus on the fact that gaming workload has high temporal correlation among frames and evaluate selected workload predictors on a per-frame basis. Moreover, we find that there are two categories of thread workloads, periodic and aperiodic, and hence, propose to use a hybrid workload predictor. Based on the per-thread predictions, the power manager allocates the threads among the heterogeneous cores in an evenly distributed fashion in order to minimize the operating frequency while keeping the frames-per-second (FPS) constraint. We implement the game power manager as an Android governor on a state-of-the-art platform based on the Exynos5422 SoC, which is also incorporated in the Samsung Galaxy S5 smartphone. Our measurement results show that we save on average 41.9% of energy compared to the Android default governor. Further, we have performed a user study to evaluate the user perception of our governor. The gaming experience was rated between good and very good for all games.

The application of Model Checking to compute WCET has not been explored as much as Integer Linear Programming (ILP), primarily because model checkers fail to scale for complex programs. These programs have loops with large or unknown bounds, leading to a state space explosion that model checkers cannot handle. To overcome this, we have developed a technique, TIC, that employs slicing, loop acceleration and over-approximation on time-annotated source code, enabling Model Checking to scale better for WCET computation. Further, our approach is parametric, so that the user can make a trade-off between the tightness of WCET estimate and the analysis time. We conducted experiments on the Mälardalen benchmarks to evaluate the effect of various abstractions on the WCET estimate and analysis time. Additionally, we compared our estimates to those made by an ILP-based analyzer and found that our estimates were tighter for more than 30% of the examples and were equal for the rest.

With the Internet of Things (IoT) becoming a reality, power-efficient techniques are crucial to achieve sufficient battery lifetimes. Whereas current medical IoT devices typically acquire data with a constant quality, we propose an architecture that dynamically adjusts the data quality adaptively based on the current medical condition of the subject being monitored. Since transmission and processing make up a large fraction of the energy consumption, the reduction of the link traffic and processing effort caused by such an adjustment results in a decreased energy consumption of the devices. For example, if anomalies in the monitored data are detected, the monitoring is performed with an increased granularity and more exhaustive processing. Further, not all data generated by the medical sensors needs to be transmitted during all times. Only if certain events are detected, the transmission of the complete data needs to be activated. In this paper, we present a novel approach for body-worn medical IoT devices. In particular, a generic, distributed architecture for the power-management of the whole system, which is based on dynamically switching services, is presented. We show that such an architecture can reduce the energy-consumption of medical sensors by up to 80 % in real-world measurements.

Recently, research on control and architecture co- design has been drawing increasingly more attention. This is because these techniques integrate the design of the controllers and the architecture and explore the characteristics on both sides to achieve more efficient design of embedded control systems. However, there still exist several challenges like the large design space and inadequate trade-off opportunities for different objectives like control performance and resource utilization. In this paper, we propose a co-optimization approach for FlexRay-based distributed control systems, that synthesizes both the controllers and the task and communication schedules. This approach exploits some FlexRay protocol specific characteristics to reduce the complexity of the whole optimization problem. This is done by employing a customized control design and a nested two-layered optimization technique. Therefore, compared to existing methods, the proposed approach is more scalable. It also allows multi-objective optimization taking into account both the overall control performance and the bus resource utilization. This approach generates a Pareto front representing the trade-offs between these two, which allows the engineers to make suitable design choices.

The innovation in the automotive domain is shifting considerably to the Electrical/Electronics system and software. The evolution cycle of the electronic system and the software is significantly shorter than the life cycle of a vehicle and therefore the functionality of a vehicle might become 'outdated' easily in the future. Thus, it would be advantageous if new applications can be installed or existing applications can be upgraded via cloud services after sales in a plug-and-play fashion. This requires that the underlying system possesses a certain degree of adaptivity and reconfigurability. One important issue in this case is the allocation of computation and communication resources. In the case of a time-triggered system, the task and network schedules need to be adapted to accommodate new applications. Towards addressing this problem, we propose a schedule management framework to obtain, synthesize and manage schedules efficiently online for Ethernet-based time-triggered systems in the automotive context. This framework is based on a client-server architecture and each side consists of a web module, a synthesis module and a configuration pool. It utilizes the Internet access of modern vehicles to exploit the computation and storage capacity on the server in a cloud-computing manner and can facilitate the reuse of generated schedule sets. In the synthesis module, a four-stage strategy is introduced to reduce the synthesis time and the disturbance to existing applications. The experimental results show that the proposed framework can be applied to generate and manage schedules online and benefit from both onboard and cloud-based schedule synthesis. The result also shows the applicability of the introduced four-stage synthesis~strategy.

Discusses the current state of the journal, reports on current and future areas of exploration and research, and presents new editors.

Car manufacturers provide a growing variety of models and configuration options for customers. In the highly competitive and cost-driven automotive industry, managing these variants and increasing the reuse of functionality in different variants has therefore become one of the key challenges. This paper addresses the problem of generating variant schedules for time-triggered electrical/electronic-architectures. We propose a multischedule synthesis approach that determines the common parts of multiple variants and generates a schedule that exploits this commonality. Hence, a multischedule defines individual variant schedules with an identical schedule for applications common to different variants. This makes these applications variant-independent, thus, reduces the testing and integration efforts as it only has to be done once. Multischedule synthesis involves several challenges, viz., identification of commonality between different variants, schedule synthesis for common parts, and the integration of uncommon parts. Consequently, the schedule synthesis approach presented here is very different from conventional approaches. Finally, to address the increased complexity, we also propose a divide-and-conquer approach to partition the problem, improving the scalability.

With the perennial demand for longer runtime of battery-powered Wireless Sensor Nodes (WSNs), several techniques have been proposed to increase the battery runtime. One such class of techniques exploiting the battery recovery effect phenomenon claims that performing an intermittent discharge instead of a continuous discharge will increase the usable battery capacity. Several works in the areas of embedded systems and wireless sensor networks have assumed the existence of this recovery effect and proposed different power management techniques in the form of power supply architectures (multiple battery setup) and communication protocols (burst mode transmission) in order to exploit it. However, until now, a systematic experimental evaluation of the recovery effect has not been performed with real battery cells, using high-accuracy battery testers to confirm the existence of this recovery phenomenon. In this article, a systematic evaluation procedure is developed to verify the existence of this battery recovery effect. Using our evaluation procedure, we investigated Alkaline, Nickel-Metal Hydride (NiMH), and Lithium-Ion (Li-Ion) battery chemistries, which are commonly used as power supplies for Wireless Sensor Node (WSN) applications. Our experimental results do not show any evidence of the aforementioned recovery effect in these battery chemistries. In particular, our results show a significant deviation from the stochastic battery models, which were used by many power management techniques. Therefore, the existing power management approaches that rely on this recovery effect do not hold in practice. Instead of a battery recovery effect, our experimental results show the existence of the rate capacity effect , which is the reduction of usable battery capacity with higher discharge power, to be the dominant electrochemical phenomenon that should be considered for maximizing the runtime of WSN applications. We outline power management techniques that minimize the rate capacity effect in order to obtain a higher energy output from the battery.

This article introduces a Cyber-physical Co-Simulation Framework (CPCSF) for design and analysis of smart cells that enable scalable battery pack and Battery Management System (BMS) architectures. In contrast to conventional cells in battery packs, where all cells are monitored and controlled centrally, each smart cell is equipped with its own electronics in the form of a Cell Management Unit (CMU). The CMU maintains the cell in a safe and healthy operating state, while system-level battery management functions are performed by cooperation of the smart cells via communication. Here, the smart cells collaborate in a self-organizing fashion without a central controller instance. This enables maximum scalability and modularity, significantly simplifying integration of battery packs. However, for this emerging architecture, system-level design methodologies and tools have not been investigated yet. By contrast, components are developed individually and then manually tested in a hardware development platform. Consequently, the systematic design of the hardware/software architecture of smart cells requires a cyber-physical multi-level co-simulation of the network of smart cells that has to include all the components from the software, electronic, electric, and electrochemical domains. This comprises distributed BMS algorithms running on the CMUs, the communication network, control circuitry, cell balancing hardware, and battery cell behavior. For this purpose, we introduce a CPCSF that enables rapid design and analysis of smart cell hardware/software architectures. Our framework is then applied to investigate request-driven active cell balancing strategies that make use of the decentralized system architecture. In an exhaustive analysis on a realistic 21.6kW h Electric Vehicle (EV) battery pack containing 96 smart cells in series, the CPCSF is able to simulate hundreds of balancing runs together with all system characteristics, using the proposed request-driven balancing strategies at highest accuracy within an overall time frame of several hours. Consequently, the presented CPCSF for the first time allows us to quantitatively and qualitatively analyze the behavior of smart cell architectures for real-world applications.

Automotive software applications implement a variety of control algorithms, with many of them being safety-critical in nature. A typical design flow starts with modeling these control algorithms using tools like MATLAB/Simulink. However, at this stage, a number of assumptions, like negligible sensor-to-actuator delay and instantaneous computation of the controller software, are often made. In particular, the details of the software implementation and the computing platform, both eventually defining the timing properties of the applications, are not accounted for. Such idealistic assumptions can cause a significant deviation of the control performance compared to what was proven at the modeling stage. This is usually addressed with multiple design iterations, which are costly and may lead to over-provisioned and thus poorly designed systems. In this paper we attempt to address this problem by proposing a design-and tool flow that integrates software-and platform-level timing information into the high-level modeling stage. We outline our proposed flow using concrete, industry-strength design tools.

To handle complexity, embedded software is usually divided into components that are developed independently from each other and then need to be integrated in a reliable and deterministic manner. This involves buffering and synchronizing exchanged signals, as well as finding a feasible execution schedule, which is a tedious and error-prone procedure. We propose a model of computation that enables a programming framework which automatically performs such an integration, without requiring access to the components' source code. The developer only needs to declare interface signals between the components, connect them and define their execution periods. A software library then synthesizes deterministic communication mechanisms and provides a flexible, yet safe interface for time-triggered execution. Our approach does not require any run-time environment or special compiler, which makes it light-weight and amenable to be used on embedded platforms with limited resources.

In the context of active cell balancing of electric vehicle battery cells, we deal with circuit architectures for inductor-based charge transfer and the corresponding high-level modeling and strategy development. In this work, we introduce a circuit architecture to transfer charge between arbitrarily many source and destination cells (many-to-many) for the first time and analyze the advantages over one-to-one transfer. Balancing simulation with numerical solvers remains challenging because of non-differentiable PWM signals, while the search space for high-level strategy design - crucial for time and energy efficiency - becomes even larger. Consequently, we develop a closed-form charge transfer model that extends state-of-the-art approaches and is three orders of magnitude faster than step-size controlled simulation. With an initial algorithm design based on experimentally derived rules, we demonstrate that many-to-many transfer dominates neighbor-only approaches in speed and efficiency even though it requires only one additional switch per circuit module.

This paper proposes a novel approach to security analysis of automotive architectures at the system-level. With an increasing amount of software and connectedness of cars, security challenges are emerging in the automotive domain. Our proposed approach enables assessment of the security of architecture variants and can be used by decision makers in the design process. First, the automotive Electronic Control Units (ECUs) and networks are modelled at the system-level using parameters per component, including an exploitability score and patching rates that are derived from an automated or manual assessment. For any specific architecture variant, a Continuous-Time Markov Chain (CTMC) model is determined and analyzed in terms of confidentiality, integrity and availability, using probabilistic model checking. The introduced case study demonstrates the applicability of our approach, enabling, for instance, the exploration of parameters like patch rate targets for ECU manufacturers.

Reducing the energy consumption to the minimum is a crucial design requirement for all body area sensor networks. Sensors deployed on the human body, especially at the limbs often move along different positions. Usually, the transmit power is set to a sufficiently high value to achieve reliable transmission for the constellation with highest attenuation. For periodic movements, data transmission can be carried out at the position of the lowest path loss between the sender and the receiver, provided this position can be reliably identified. We propose a novel framework that predicts this position using acceleration data and the received signal strength. By learning a correlation between these signals, accurate predictions can be performed and up to 24.7% of the power spent by a Bluetooth Low Energy module for the transmission of a packet can be saved while still achieving the same packet error rate as with sending using the higher transmit power.

Bluetooth Low Energy is a time-slotted wireless protocol aimed towards low power communication for battery-driven devices. As a power-management capability, whenever there is less data to send, the slave is allowed to remain in a low power mode during a given number of time-slots in a row. However, since the master does not know the exact sleep behavior of the slave, it has to wake-up at every time-slot and repeat its packets until the slave is awake. As a result, applications with variable throughput lead to many energy-consuming idle-slots at the master. In such applications, usually the connection parameters are chosen considering the worst case at design time and remain constant during operation. In this paper, we propose a novel power-management framework for BLE. Rather than skipping slots at the slave side, the proposed system updates the interval between two consecutive time-slots during runtime by applying online algorithms. To avoid data-loss or high delays, the framework guarantees that constraints on latency are met and buffers never overflow. Energy measurements of three different test-cases show that up to 42 percent of the energy consumption of a BLE master can be saved with our power management system.

In this paper we consider the case of a network of Electronic Control Units (ECUs) connected through a Flex Ray bus in the automotive domain. Multiple distributed applications can run on this underlying architecture, each partitioned into tasks that are mapped on different ECUs. These applications can often be executed in different functional modes with different requirements on the communication resources in terms of data size and sampling period. Moreover, new applications can be deployed on to the ECUs at run-time. To efficiently utilize the communication resources and accommodate new applications, a certain flexibility in reallocation of the resource is necessary. However, the Flex Ray bus requires static configuration of schedules and data mapping in order to guarantee a more deterministic system behavior, allowing little room for flexibility. In order to address this problem, we propose a reconfigurable communication middleware that lies between the application layer and the communication controller layer, which maps messages onto Flex Ray schedules, and can be reconfigured at runtime. The configuration is synthesized and deployed online, allowing a certain reallocation of communication resources to applications. In this paper, we describe the design of such a reconfigurable communication middleware and demonstrate its function with an implementation using industry-strength Flex Ray design tools.

In this paper, we present Smart2, an advanced smartphone charger that mitigates battery's capacity fading, which until now has usually been ignored. Smart2 exploits the fact that many users charge their phones over night. Since the overnight charging duration is unnecessarily long, the battery is subjected to a high average state of charge (SOC), which accelerates battery aging. Therefore, we delay the charging adaptively to be done shortly before the phone is unplugged. With this scheme, clearly when averaged over the duration of the night, the average SOC is lower and hence aging is reduced. Indicators are a set alarm clock and/or statistics of previous usage. Similarly, we lower the maximum target SOC. To enable this, the main challenges are firstly to find a solution that does not negatively influence the usability and secondly to quantify the achieved savings in terms of aging mitigation. Towards this, we propose a novel charging scheme which can be implemented in the smartphone's firmware. Furthermore, we propose a modified battery charging device that can be used with almost all existing smart phone models. Using our proposed techniques, the average battery cycle life can be nearly doubled from 3.7 to 6.6 years.

Runtime power management using dynamic voltage and frequency scaling (DVFS) has been extensively studied for video processing applications. But there is only a little work on game power management although gaming applications are now widely run on battery-operated portable devices like mobile phones. Taking a cue from video power management, where PID controllers have been successfully used, they were recently applied to game workload prediction and DVFS. However, the use of hand-tuned PID controller gains on relatively short game plays left open questions on the robustness of the controller and the sensitivity of prediction quality on the choice of the gain values. In this paper, we try to systematically answer these questions. We first show that from the space of PID controller gain values, only a small subset leads to good game quality and power savings. Further, the choice of this set highly depends on the scene and the game application. For most gain values the controller becomes unstable, which can lead to large oscillations in the processor’s frequency setting and thereby poor results. We then study a number of time series models, such as a Least Mean Squares (LMS) Linear Predictor and its generalizations in the form of Autoregressive Moving Average (ARMA) models. These models learn most of the relevant model parameters iteratively as the game progresses, thereby dramatically reducing the complexity of manual parameter estimation. This makes them deployable in real setups, where all game plays and even game applications are not a priori known. We have evaluated each of these models (PID, LMS, and ARMA) for a variety of games—ranging from Quake II to more recent closed-source games such as Crysis, Need for Speed—Shift and World in Conflict—with very encouraging results. To the best of our knowledge, this is the first work that systematically explores (a) the feasibility of manually tuning PID controller parameters for power management, (b) time series models for workload prediction for gaming applications, and (c) power management for closed-source games.

Today, most of the innovation in the automotive domain is in the areas of electronics and software. Modern cars have already been transformed, from largely mechanical entities, to complex embedded systems running on four wheels. High-end cars currently have around 100 electronic control units (ECUs), each with one or more, possibly multicore, processors. These ECUs communicate using different communication buses such as CAN, FlexRay, LIN, and more recently also Ethernet, and are connected to various cameras, radars, ultrasonic sensors, and also to a host of actuators. Such architectures are used to run several millions of lines of software code spanning across safety-critical, driver assistance, comfort, and entertainment related applications.

Current mobile devices extensively run video players that are power hungry. Further, higher power densities as a result of technology scaling results in higher on-chip temperatures. Unlike general purpose computer systems, mobile devices that run on batteries cannot afford to have expensive cooling mechanisms. Therefore, in order to satisfy thermal constraints while running power hungry applications, dynamic thermal management (DTM) techniques have been employed. For multimedia applications, the techniques primarily relied on dynamic voltage and frequency scaling (DVFS) and dynamic power management (DPM) while taking care that maximum video quality is achieved. However, no prior work has exploited frame drops to lower the inserted idle times under predetermined quality constraints. In this work, we propose a DPM framework that utilizes frame drops to dynamically insert low idle times in order to satisfy a peak temperature constraint under a given quality constraint. This also reduces the end-to-end latency. The latencies are further reduced by maintaining lightweight workload histories. For the videos used in our experiments, it was observed that a small reduction in quality of 2 dB (reduction from 32 dB to 30 dB) due to frame drops in motion videos results in a maximum latency reduction of 1.7 sec.

The design process of safety-critical systems requires formal analysis methods to ensure their correct functionality without over-sized safety margins and extensive testing. For architectures with state-based events or scheduling, such as load-dependent frequency scaling, model checking has emerged as a promising tool. It formally verifies timing behavior of realtime systems with minimal over-approximation of the worst case delays. In this context, Event Count Automata (ECAs) have become a valuable modeling approach because they are specifically designed to handle typical arrival patterns and integrate well with analytic techniques. In this work, we propose an extension of the ECA framework's semantics and use it in a Fixed-Priority Non-preemptive Scheduling (FPNS) model that correctly abstracts the intra-slot behavior in the slotted-time model of the ECA. This is challenging because straightforward implementations cannot capture the full behavior of event-triggered scheduling with such a time model that the ECA shares with most model checking based methods. In a case study, we obtain bounds via model checking a basic model and then our proposed model. We compare these bounds with a SystemC simulation. This shows that the bounds from the basic model are too optimistic - and exceeded in practice - because it does not capture the full behavior, while the bounds from the proposed extended model are both safe and reasonably tight.

This paper presents a novel approach to detect resources in distributed systems with an increased occurrence of intermittent faults that exceed the amount of unavoidable transient faults caused by environmental phenomena. Intermittent faults occur due to stressed resources and often are a precursor of permanent faults. The proposed early fault detection and diagnosis allows the use of precautionary measures before the permanent failure of a component in a distributed system occurs. In this paper, we present four methods that can implicitly detect intermittent faults by taking the distributed applications and their dependencies into account. Thus, explicit tests are not required which would lead to additional costs and resource load. On the other hand, the implicit approach may considerably reduce the number of plausibility tests compared to the conservative solution with one test per resource. We analyzed and evaluated implementations of the proposed fault detection principle. The experimental results give evidence of the feasibility of our approach and show a comparison of the implemented methods in terms of runtime and detection rate.

In this paper, we study time-triggered distributed systems where periodic application tasks are mapped onto different end stations (processing units) communicating over a switched Ethernet network. We address the problem of application level (i.e., both task- and network-level) schedule synthesis and optimization. In this context, most of the recent works [10], [11] either focus on communication schedule or consider a simplified task model. In this work, we formulate the co-synthesis problem of task and communication schedules as a Mixed Integer Programming (MIP) model taking into account a number of Ethernet-specific timing parameters such as interframe gap, precision and synchronization error. Our formulation is able to handle one or multiple timing objectives such as application response time, end-to-end delay and their combinations. We show the applicability of our formulation considering an industrial size case study using a number of different sets of objectives. Further, we show that our formulation scales to systems with reasonably large size.

In this paper, we describe how we combine active and passive user input modes in clinical environments for knowledge discovery and knowledge acquisition towards decision support in clinical environments. Active input modes include digital pens, smartphones, and automatic handwriting recognition for a direct digitalisation of patient data. Passive input modes include sensors of the clinical environment and or mobile smartphones. This combination for knowledge acquisition and decision support (while using machine learning techniques) has not yet been explored in clinical environments and is of specific interest because it combines previously unconnected information sources for individualised treatments. The innovative aspect is a holistic view on individual patients based on ontologies, terminologies, and textual patient records whereby individual active and passive real-time patient data can be taken into account for improving clinical decision support.

Intelligent automotive electronics significantly improved driving safety in the last decades. With the increasing complexity of automotive systems, dependability of the electronic components themselves and of their interaction must be assured to avoid any risk to driving safety due to unexpected failures caused by internal or external faults.

We have experienced rapid development of augmented reality (AR) systems and platforms in the automotive industry. However, to bring AR into production cars, we still face a range of challenges to design an AR system that meets vehicle specific requirements. Based on our experience with an AR prototype car, we analyze the influence of augmented reality on the design of the in-vehicle electric/electronic (E/E) architecture.

Automotive Electrical/Electronic (E/E)-architectures consist of various components which are generally developed independently. Due to the increasing size and complexity, component integration is highly challenging and already slight modifications to components or subsystems often require expensive re-testing and re-validation. As a remedy, we propose a framework for modular architectures based on a data-centric description and a fully time-triggered scheduling. This modular design approach is enabled by a novel methodology for schedule integration where local schedules are defined independently for subsystems before being integrated into a global schedule. This divide-and-conquer approach significantly reduces the integration complexity while the system becomes highly composable. Our experimental results give evidence of the efficiency and versatility of the proposed approach, using networks based on a time-triggered automotive Ethernet.

We deal with synthesis of distributed embedded control systems closed over a faulty or severely constrained communication network. Such overloaded communication networks are common in cost-sensitive domains such as automotive. Design of such systems aims to meet all deadlines following the traditional notion of schedulability. In this work, we aim to exploit robustness of the controller and propose a novel implementation approach to achieve a tighter design. Toward this, we answer two research questions: (i) given a distributed architecture, how to characterize and formally verify the bound on deadline misses, (ii) given such a bound, how to design a controller such that desired stability and Quality of Control (QoC) requirements are met. We address question (i) by modeling a distributed embedded architecture as a network of Event Count Automata (ECA), and subsequently introducing and formally verifying a property formulation with reduced complexity. We address question (ii) by introducing a novel fault-tolerant control strategy which adjusts the control input at runtime based on the occurrence of fault or drop. We show that QoC under faulty communication improves significantly using the proposed fault-tolerant strategy.

This paper presents an approach to optimal dimensioning of active cell balancing architectures, which are of increasing relevance in Electrical Energy Storages (EESs) for Electric Vehicles (EVs) or stationary applications such as smart grids. Active cell balancing equalizes the state of charge of cells within a battery pack via charge transfers, increasing the effective capacity and lifetime. While optimization approaches have been introduced into the design process of several aspects of EESs, active cell balancing architectures have, until now, not been systematically optimized in terms of their components. Therefore, this paper analyzes existing architectures to develop design metrics for energy dissipation, installation volume, and balancing current. Based on these design metrics, a methodology to efficiently obtain Pareto-optimal configurations for a wide range of inductors and transistors at different balancing currents is developed. Our methodology is then applied to a case study, optimizing two state-of-the-art architectures using realistic balancing algorithms. The results give evidence of the applicability of systematic optimization in the domain of cell balancing, leading to higher energy efficiencies with minimized installation space.

Battery-operated portable electronics, from smartphones to notebook computers, are generally sold with a dedicated power supply. The power supply operates the device and also charges the built-in battery. Most users are concerned about the battery aging while the device is operated by the built-in battery. This is the first paper to our knowledge that discovers, analyzes and mitigates the built-in battery aging when the device is operated with the provided power supply. We focus on the fact that in an effort to reduce size and weight, the capacity of the power supply is optimized for the average power demand rather than the maximum power demand. Such a reduced-capacity power supply brings advantages in terms of size, weight and cost but it accelerates the battery aging because the aging progresses even when the device is operated by the power supply, which is different from the expectation of most users. We quantitatively analyze such battery aging with various operating scenarios based on standard benchmark programs. We show that the battery experiences significant aging, i.e., the battery lifetime can be reduced to 23% of its shelf lifetime. Finally, we propose a cost-effective supercapacior hybrid to mitigate such battery aging when the device is operated using the power supply. The simulation results show that 10, 1 and 0.1 mF supercapacitors can reduce the battery aging by 68.6%, 55.1% and 4.6%, respectively.

In the last three years, a number of automotive Augmented Reality (AR) concepts and demonstrators have been presented, all looking for an interpretation of what AR in a car may look like. In October 2013, Mercedes-Benz exhibited to a public audience the AR In-Vehicle Infotainment (AR-IVI) system aimed at defining an overall in-vehicle electric/electronic (E/E) architecture for augmented reality rather than showing specific use cases. In this paper, we explain the requirements and design decisions that lead to the systemdesign, and we share the challenges and experiences in developing the AR-IVI system in the prototype vehicle. Based on our experiences, we give an outlook on future software and E/E architectural challenges of in-vehicle augmented reality.

On behalf of the IEEE Technical Committee on Real-Time Systems, it is our pleasure to welcome you to the 20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2014), held in Berlin, Germany, as part of the Cyber-Physical Systems Week!

In this paper, for the first time, we propose a battery- and aging-aware optimization framework for embedded control systems design in electric vehicles (EVs). Performance and reliability of an EV are influenced by feedback control loops implemented into in-vehicle electrical/electronic (E/E) architecture. In this context, we consider the following design aspects of an EV: (i) battery usage, (ii) processor aging of the in-vehicle embedded platform. In this work, we propose a design optimization framework for embedded controllers with gradient-based and stochastic methods taking into account quality of control (QoC), battery usage and processor aging. First, we obtain a Pareto front between QoC and battery usage utilizing the optimization framework. Well-distributed non-dominated solutions are achieved by solving a constrained bi-objective optimization problem. In general, QoC of a control loop highly depends on the sampling period. When the processor ages, on-chip monitors could be used to measure the delay of the critical path, based on which, the processor operating frequency is reduced to ensure correct functioning. As a result, the sampling period gets longer opening up the possibility of QoC deterioration, which is highly undesirable for safety-critical applications in EVs. Utilizing the proposed framework, we take into account the effect of processor aging by re-optimizing the controller design with the prolonged sampling period resulting from processor aging. We illustrate the approach considering electric motor control in EVs. Our experimental results show that the effect of processor aging on QoC deterioration can be mitigated by controller re-optimization with a slight compromise on battery usage.

FlexRay has now become a well-established in-vehicle communication bus at most original equipment manufacturers (OEMs) such as BMW, Audi, and GM. Given the increasing cost of verification and the high degree of crosslinking between components in automotive architectures, an incremental design process is commonly followed. In order to incorporate FlexRay-based designs in such a process, the resulting schedules must be extensible , that is: (i) when messages are added in later iterations, they must preserve deadline guarantees of already scheduled messages, and (ii) they must accommodate as many new messages as possible without changes to existing schedules. Apart from extensible scheduling having not received much attention so far, traditional metrics used for quantifying them cannot be trivially adapted to FlexRay schedules. This is because they do not exploit specific properties of the FlexRay protocol. In this article we, for the first time, introduce new notions of extensibility for FlexRay that capture all the protocol-specific properties. In particular, we focus on the dynamic segment of FlexRay and we present a number of metrics to quantify extensible schedules. Based on the introduced metrics, we propose strategies to synthesize extensible schedules and compare the results of different scheduling algorithms. We demonstrate the applicability of the results with industrial-size case studies and also show that the proposed metrics may also be visually represented, thereby allowing for easy interpretation.

We study distributed controllers where sensor, controller, and actuator tasks are mapped onto different processors or Electronic Control Units (ECUs) in a distributed automotive architecture, communicating via a shared bus. Controllers in such setups are designed with a sampling period equal to the worst-case sensor-to-actuator message delay. However, this assumption of all messages having to meet their deadlines is too pessimistic. The inherent robustness of most controllers allows some of the messages to miss their deadlines, while still meeting specified control performance constraints. Given a controller, in this paper we first quantify the frequency of its acceptable deadline misses and represent this as a Linear Temporal Logic (LTL) formula. Further, we model the distributed architecture as a network of Time-Stamped Event Count Automata (TS-ECAs). Such a network of TS-ECAs is then model-checked to verify whether it satisfies the LTL formula. The verification ensures that the controller may be mapped onto the architecture and the control performance constraints will be satisfied. We have implemented this methodology in Symbolic Analysis Laboratory (SAL), which is a well-known framework combining different tools for system verification. Our implementation and case studies using standard controller design shows the applicability of our proposed controller/architecture co-verification. It represents a significant improvement in current design flows where, although controller models are formally verified, their implementation on a distributed architecture is done in an ad hoc fashion with extensive testing and integration effort.

This paper presents a framework for schedule integration of time-triggered systems tailored to the automotive domain. In-vehicle networks might be very large and complex and hence obtaining a schedule for a fully synchronous system becomes a challenging task since all bus and processor constraints as well as end-to-end-timing constraints have to be taken concurrently into account. Existing optimization approaches apply the schedule optimization to the entire network, limiting their application due to scalability issues. In contrast, the presented framework obtains the schedule for the entire network, using a two-step approach where for each cluster a local schedule is obtained first and the local schedules are then merged to the global schedule. This approach is also in accordance with the design process in the automotive industry where different subsystems are developed independently to reduce the design complexity and are finally combined in the integration stage. In this paper, a generic framework for schedule integration of time-triggered systems is presented. Further, we show how this framework is implemented for a FlexRay network using an Integer Linear Programming (ILP) approach which might also be easily adapted to other protocols. A realistic case study and a scalability analysis give evidence of the applicability and efficiency of our approach.

Today high-end cars have extremely complex E/E architectures -- with 50--100 electronic control units (ECUs), connected by communication buses like CAN, FlexRay and Ethernet. They are used to run several (control) applications with many million lines of code. We propose a radically new architecture where all these applications are instead run on a mobile phone being carried by the driver. The car now has a considerably simpler architecture with few or no ECUs, using RF links to connect sensors and actuators to the mobile phone with a powerful multicore processor. We discuss the advantages and challenges and describe a small prototype implementation with an adaptive cruise control application.

Today, modern high-end cars have close to 100 electronic control units (ECUs) that are used to implement a variety of applications ranging from safety-critical control to driver assistance and comfort-related functionalities. The total sum of these applications is several million lines of software code. The ECUs are connected to different sensors and actuators and communicate via a variety of communication buses like CAN, FlexRay and now also Ethernet. In the case of electric vehicles, both the amount and the importance of such electronics and software are even higher. Here, a number of hydraulic or pneumatic controls are replaced by corresponding software-implemented controllers in order to reduce the overall weight of the car and hence to improve its driving range. Until recently, most of the software and system design in the automotive domain -- as in many other domains -- relied on an always correctly functioning or a zero-defect hardware implementation platform. However, as the device geometries of integrated circuits continue to shrink, this assumption is increasingly not true. Incorporating large safety margins in the design process results in very pessimistic design and expensive processors. Further, the processors in cars -- in contrast to those in many consumer electronics devices like mobile phones -- are exposed to harsh environments, extreme temperature variations, and often, strong electromagnetic fields. Hence, their reliability is even more questionable and must be explicitly accounted for in all layers of design abstraction -- starting from circuit design to architecture design, to software design and runtime management and monitoring. In this paper we outline some of these issues, currently followed practices, and the challenges that lie ahead of us in the automotive and electric vehicles domain.

Most innovations in the automotive domain are realized by electronics and software. Modern cars have up to 100 Electronic Control Units (ECUs) that implement a variety of control applications in a distributed fashion. The tasks are mapped onto different ECUs, communicating via a heterogeneous network, comprising communication buses like CAN, FlexRay, and Ethernet. For electric vehicles, software functions play an essential role, replacing hydraulic and mechanic control systems. While model-based software development and verification are already used extensively in the automotive domain, their importance significantly increases in electric vehicles as safety-critical functions might no longer rely on mechanical (fall-back) solutions. The need for reducing costs, size, and weight in electric vehicles has also resulted in a considerable interest in topics such as the consolidation of ECUs as well as efficient implementation of control software. In this paper we discuss two broad issues related to model-based software development and verification in electric vehicles. The first is concerned with how to ensure that model-level semantics are preserved in an implementation, which has important implications on the verification and certification of control software. The second issue is related to techniques for reducing the computational and communication demands of distributed automotive control algorithms. For both these topics we provide a broad introduction to the problem followed by a discussion on state-of-the-art techniques.

This paper proposes a novel modular architecture for Electrical Energy Storages (EESs), consisting of multiple series-connected cells. In contrast to state-of-the-art architectures, the presented approach significantly improves the energy utilization, safety, and availability of EESs. For this purpose, each cell is equipped with a circuit that enables an individual control within a homogeneous architecture. One major advantage of our approach is a direct and concurrent charge transfer between each cell of the EES using inductors. To enable a system-level modeling and performance analysis of the architecture, a detailed investigation of the components and their interaction with the Pulse Width Modulation (PWM) control was performed at transistor-level. At system-level, we propose a control algorithm for the charge transfer that aims at minimizing the energy loss and balancing time. The results give evidence of the significant advantages of our architecture over existing passive and active balancing methods in terms of energy efficiency and charge equalization time.

This paper gives an overview of the system architecture and software design challenges for Electric Vehicles (EVs). First, we introduce the EV-specific components and their control, considering the battery, electric motor, and electric powertrain. Moreover, technologies that will help to advance safety and energy efficiency of EVs such as drive-by-wire and information systems are discussed. Regarding the system architecture, we present challenges in the domain of communication and computation platforms. A paradigm shift towards time-triggered in-vehicle communication systems becomes inevitable for the sake of determinism, making the introduction of new bus systems and protocols necessary. At the same time, novel computational devices promise high processing power at low cost which will make a reduction in the number of Electronic Control Units (ECUs) possible. As a result, the software design has to be performed in a holistic manner, considering the controlled component while transparently abstracting the underlying hardware architecture. For this purpose, we show how middleware and verification techniques can help to reduce the design and test complexity. At the same time, with the growing connectivity of EVs, security has to become a major design objective, considering possible threats and a security-aware design as discussed in this paper.

Applications that stream multiple video/audio or video+audio clips are being implemented in embedded devices. A Picture-in-Picture (PiP) application is one such application scenario, where two videos are played simultaneously. Although the PiP application is very efficiently handled in televisions and personal computers by providing maximum quality of service to the multiple streams, it is a difficult task in devices with resource constraints. In order to efficiently utilize the resources, it is essential to derive the necessary processor cycles for multiple video streams such that they are displayed with some prespecified quality constraint. Therefore, we propose a network calculus based formal framework to help schedule multiple media streams in the presence of buffer contraints. Further, our framework also presents a schedulability analysis condition to check if the multimedia streams can be scheduled such that a prespecified quality constraint is satisfied with the available service. We present this framework in the context of a PiP application, but it is applicable in general for multiple media streams. The results obtained using the formal framework were further verified using experiments involving system simulation.

Automotive software mostly consists of a set of applications controlling the vehicle dynamics, engine and many other processes or plants. Since automotive systems design is highly cost driven, an important goal is to maximize the number of control applications to be packed onto a single processor or electronic control unit (ECU). Current design methods start with a controller design step, where the sampling period and controller gain values are decided based on given control performance objectives. However, operating systems (OS) on the ECU (e.g., ERCOSek) are usually pre-configured and offer only a limited set of sampling periods. Hence, a controller is implemented using an available sampling period, which is the shorter period closest to the one determined in the controller design step. However, this increases the load on the ECU (i.e., the processor runs the controller more often than what is actually required by design). This reduces the number of applications that can be mapped, and increases costs of the system. To overcome this predicament, we propose a multirate controller, which switches between multiple available sampling periods offered by the OS on the ECU. Apart from meeting all control objectives, this avoids the unnecessary ECU overload resulting from always sampling at a constant, higher rate.

This paper presents a methodology based on mathematical programming for the priority assignment of processes and messages in event-triggered systems with tight end-to-end real-time deadlines. For this purpose, the problem is converted into a Quadratically Constrained Quadratic Program (QCQP) and addressed with a state-of-the-art solver. The formulation includes preemptive as well as non-preemptive schedulers and avoids cyclic dependencies that may lead to intractable real-time analysis problems. For problems with stringent real-time requirements, the proposed mathematical programming method is capable of finding a feasible solution efficiently where other approaches suffer from a poor scalability. In case there exists no feasible solution, an algorithm is presented that uses the proposed method to find a minimal reason for the infeasibility which may be used as a feedback to the designer. To give evidence of the scalability of the proposed method and in order to show the clear benefit over existing approaches, a set of synthetic test cases is evaluated. Finally, a large realistic case study is introduced and solved, showing the applicability of the proposed method in the automotive domain.

This paper is an introduction to security challenges for the design of automotive hardware/software architectures. State-of-the-art automotive architectures are highly heterogeneous and complex systems that rely on distributed functions based on electronics and software. As cars are getting more connected with their environment, the vulnerability to attacks is rapidly growing. Examples for such wireless communication are keyless entry systems, WiFi, or Bluetooth. Despite this increasing vulnerability, the design of automotive architectures is still mainly driven by safety and cost issues rather than security. In this paper, we present potential threats and vulnerabilities, and outline upcoming security challenges in automotive architectures. In particular, we discuss the challenges arising in electric vehicles, like the vulnerability to attacks involving tampering with the battery safety. Finally, we discuss future automotive architectures based on Ethernet/IP and how formal verification methods might be used to increase their security.

In this paper we study distributed automotive control applications whose tasks are mapped onto different ECUs communicating via a switched Ethernet network. As traditional automotive communication buses like CAN, FlexRay, LIN and MOST are gradually reaching their performance limits because of the increasing complexity of automotive architectures and applications, Ethernet-based in-vehicle communication systems have attracted a lot of attention in recent times. However, currently there is very little work on systematic timing analysis for Ethernet which is important for its deployment in safety-critical scenarios like in an automotive architecture. In this work, we propose a compositional timing analysis technique that takes various features of switched Ethernet into account like network topology, frame priorities, communication delay, memory requirement on switches, performance, etc. Such an analysis technique is particularly suitable during early design phases of automotive architectures and control software deployment. We demonstrate its use in analyzing mixed-criticality traffic patterns consisting of messages from performance-oriented control loops and timing-sensitive real-time tasks. We further evaluate the tightness of the obtained analytical bounds with an OMNeT++ based network simulation environment, which involves long simulation time and does not provide formal guarantees.

Compute intensive games currently represent the class of most popular and at the same time most power consuming applications on mobile phones. To reduce the power consumption of games we have developed a game state specific power management technique. Games typically consist of several states such as the game loading, main menu, in-game menu and gaming state. Each of these states has its specific processing requirements, e.g., the game loading state is likely to be memory bound and menu scenes are less interactive than gaming states and hence do not require high frame rates to satisfy the user's perception. Our game state specific governor (i) recognizes these game states by intercepting and analyzing calls made by the game application to the graphics library, and (ii) exploits these state-specific characteristics to enable power management strategies targeted to these individual states at runtime. Thereby, we achieve significant power savings of up to 50.8% compared to Android's default interactive governor.

This paper proposes a modular framework that enables a scheduling for time-triggered distributed embedded systems. The framework provides a symbolic representation that is used by an Integer Linear Programming (ILP) solver to determine a schedule that respects all bus and processor constraints as well as end-to-end timing constraints. Unlike other approaches, the proposed technique complies with automotive specific requirements at system-level and is fully extensible. Formulations for common time-triggered automotive operating systems and bus systems are presented. The proposed model supports the automotive bus systems FlexRay 2.1 and 3.0. For the operating systems, formulations for an eCos-based non-preemptive component and a preemptive OSEKtime operating system are introduced. A case study from the automotive domain gives evidence of the applicability of the proposed approach by scheduling multiple distributed control functions concurrently. Finally, a scalability analysis is carried out with synthetic test cases.

We propose a performance verification technique for cyber-physical systems that consist of multiple control loops implemented on a distributed architecture. The architectures we consider are fairly generic and arise in domains such as automotive and industrial automation; they are multiple processors or electronic control units (ECUs) communicating over buses like FlexRay and CAN. Current practice involves analyzing the architecture to estimate worst-case end-to-end message delays and using these delays to design the control applications. This involves a significant amount of pessimism since the worst-case delays often occur very rarely. We show how to combine functional analysis techniques with model checking in order to derive a delay-frequency interface that quantifies the interleavings between messages with worst-case delays and those with smaller delays. In other words, we bound the frequency with which control messages might suffer the worst-case delay. We show that such a delay-frequency interface enables us to verify much tigher control performance properties compared to what would be possible with only worst-case delay bounds.

The design of electric vehicles require a complete paradigm shift in terms of embedded systems architectures and software design techniques that are followed within the conventional automotive systems domain. It is increasingly being realized that the evolutionary approach of replacing the engine of a car by an electric engine will not be able to address issues like acceptable vehicle range, battery lifetime performance, battery management techniques, costs and weight, which are the core issues for the success of electric vehicles. While battery technology has crucial importance in the domain of electric vehicles, how these batteries are used and managed pose new problems in the area of embedded systems architecture and software for electric vehicles. At the same time, the communication and computation design challenges in electric vehicles also have to be addressed appropriately. This paper discusses some of these research challenges.

We present an automatic schedule synthesis framework for applications that are mapped onto distributed time-triggered automotive platforms where multiple Electronic Control Units (ECUs) are synchronized over a FlexRay bus. We classify applications into two categories (i) safety-critical control applications with stability and performance constraints, and (ii) time-critical applications with only deadline constraints. Our proposed framework can handle such mixed constraints arising from timing, control stability, and performance requirements. In particular, we synthesize schedules that optimize control performance and respects the timing requirements of the real-time applications. An Integer Linear Programming (ILP) problem is formulated by modeling the ECU and bus schedules as a set of constraints for optimizing both linear or quadratic control performance functions.

Many cyber-physical systems consist of a collection of control loops implemented on multiple electronic control units (ECUs) communicating via buses such as FlexRay. Such buses support hybrid communication protocols consisting of a mix of time- and event-triggered slots. The time-triggered slots may be perfectly synchronized to the ECUs and hence result in zero communication delay, while the event-triggered slots are arbitrated using a priority-based policy and hence messages mapped onto them can suffer non-negligible delays. In this paper, we study a switching scheme where control messages are dynamically scheduled between the time-triggered and the event-triggered slots. This allows more efficient use of time-triggered slots which are often scarce and therefore should be used sparingly. Our focus is to perform a schedulability analysis for this setup, i.e., in the event of an external disturbance, can a message be switched from an event-triggered to a time-triggered slot within a specified deadline? We show that this analysis can check whether desired control performance objectives may be satisfied, with a limited number of time-triggered slots being used.

Electric vehicles are emerging as a solution to environmental changes and transportation challenges in growing mega-cities. Compared to combustion engine vehicles, electric vehicles bring along new challenges in the CPS design. This paper gives an overview of several of these challenges and presents initial and potential solutions for the design of the electric powertrain and E/E architectures for electric vehicles. The powertrain consists of multiple complex CPS such as the battery, the electric motor, and a distributed energy management system. These components require a complex monitoring and control in order to guarantee safety and maintain a high efficiency. For this purpose, novel E/E architectures become necessary that facilitate a predictable distributed computation and communication, requiring a paradigm shift towards fully time-triggered systems. These E/E architectures will also enable novel CPS such as innovative driver assistance systems, x-by-wire control to further increase the safety and energy-efficiency of electric vehicles, and a pervasive interaction of the vehicle and the grid. Instead of focusing on the specific applications, this paper describes the prerequisite architectural changes that are necessary to implement these novel functions.

Multiprocessor platforms have been widely adopted to accommodate the increasing computation requirement of modern applications. Partitioned scheduling (or packing) has been widely exploited by partitioning real-time tasks onto processors to meet the timing constraints, which has been shown to be NP-complete in the strong sense. This paper studies the approximation of partitioned scheduling by exploiting resource augmentation with (1) speeding up or (2) allocating more processors. When adopting speeding up to meet timing constraints, we provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions only with the assumption that the ratio of the maximum relative deadline to the minimum relative deadline is a constant. The previously known PTAS for this problem imposes additional restrictions on the periods and the execution times of tasks. By removing these additional constraints, our scheme can be adopted for wider task sets. When considering the resource augmentation by allocating more processors, we show that there does not exist any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP.

Application-specific instruction-set processors (ASIPs) allow the designer to extend the instruction set of the base processor with selected custom instructions to tailor-fit the application. In this paper, with the help of a motivational example, we first demonstrate that different custom instructions are vulnerable to faults with varying probabilities. This shows that by ignoring the vulnerability to faults, traditional methods of instruction set customization can provide no guarantees on the reliability of the system. Apart from such inherent disparity in error vulnerability across custom instructions, each custom instruction can have multiple implementation choices corresponding to varying hardened levels. Hardening reduces the vulnerability to errors but this comes at the overhead of area costs and reduced performance gain. In this paper, we propose a framework to select custom instructions and their respective hardening levels such that reliability is optimized while the performance gain is satisfied and area costs are met as well. Our framework is based on a novel analytical method to compute the overall system reliability based on the probability of failure of individual instructions. Wide range of experiments that were conducted illustrate how our tool navigates the design space to reveal interesting tradeoffs.

With the rapid progress in semiconductor technology and the shrinking of device geometries, the resulting processors are increasingly becoming prone to effects like aging and soft errors. As a processor ages, its electrical characteristics degrade, i.e., the switching times of its transistors increase. Hence, the processor cannot continue error-free operation at the same clock frequency and/or voltage for which it was originally designed. In order to mitigate such effects, recent research proposes to equip processors with special circuitry that automatically adapts its clock frequency in response to changes in its circuit-level timing properties (arising from changes in its electrical characteristics). From the point of view of tasks running on these processors, such autonomic frequency scaling(AFS) processors become slower as they gradually age. This leads to additional execution delay for tasks, which needs to be analyzed carefully, particularly in the context of hard real time or safety-critical systems. Hence, for real-time systems based on AFS processors, the associated schedulability analysis should be aging-aware which is a relatively unexplored topic so far. In this paper we propose a schedulability analysis framework that accounts such aging-induced degradation and changes in timing properties of the processor, when designing hard real-time systems. In particular, we address the schedulability and task mapping problem by taking a lifetime constraint of the system into account. In other words, the system should be designed to be fully operational (i.e., meet all deadlines) till a given minimum period of time (i.e., its lifetime). The proposed framework is based on an aging model of the processor which we discuss in detail. In addition to studying the effects of aging on the schedulability of real-time tasks, we also discuss its impact on task mapping and resource dimensioning.

No abstract available.

Over the last decade, there has been an increasing emphasis on driver-assistance systems for the automotive domain. In this article, we report our work on designing a camera-based surveillance system embedded in a “smart” car door. Such a camera is used to monitor the ambient environment outside the car, for instance, the presence of obstacles such as approaching cars or cyclists who might collide with the car door if opened—and automatically control the car door operations. This is an enhancement to the currently available side-view mirrors that the driver/passenger checks before opening the car door. The focus of this article is on fast and robust image processing algorithms specifically targeting such a smart car door system. The requirement is to quickly detect traffic objects of interest from grayscale images captured by omnidirectional cameras. While known algorithms for object extraction from the image processing literature rely on color information and are sensitive to shadows and illumination changes, our proposed algorithms are highly robust, can operate on grayscale images (color images are not available in our setup), and output results in real time. We present a number of experimental results based on image sequences captured from real-life traffic scenarios to demonstrate the applicability of our algorithm.

Multimedia decoders mapped onto MPSoC platforms exhibit degraded video quality when the critical system resources such as buffer and processor frequency are constrained. Hence, it is essential for system designers to find the appropriate mix of resources, living within the constraints, for a desired output video quality. A naive approach to do this would be to run expensive system simulations of the decoder tasks mapped onto a model of the underlying MPSoC architecture. This turns out to be inefficient when the input video library set has a large number of video clips. We propose a fast hybrid simulation framework to quantitatively estimate decoded video quality in the context of an MPEG-2 decoder. Here, the workload of simulation heavy tasks are estimated using accurate analytical models. The workload of other light (but difficult to analytically model) tasks are obtained from system simulations. This framework enables the system designer to perform a fast trade-off analysis of the system resources in order to choose the optimal combination of resources for the desired video quality. When compared to a naive system simulation approach, the hybrid simulation-based framework shows speed-up factors of about 5× for motion and 8× for still videos. The results obtained using this framework highlight important trade-offs such as the decoded video quality (measured in terms of the peak signal to noise ratio (PSNR)) vs buffer size and PSNR vs processor frequency.

In this paper, we consider a cyber-physical architecture where control applications are divided into multiple tasks, spatially distributed over various processing units that communicate via a shared bus. While control signals are exchanged over the communication bus, they have to wait for bus access and therefore experience a delay. We propose certain (co-)design guidelines for (i) the communication schedule, and (ii) the controller, such that stability of the control applications is guaranteed for more flexible communication delay constraints than what has been studied before. We illustrate the applicability of our design approach using the FlexRay dynamic segment as the communication medium for the processing units.

FlexRay has emerged as the de-facto next generation in-vehicle communication protocol. Messages are scheduled incrementally on FlexRay according to the automotive design paradigm where new applications are added iteratively. On this account, the schedules must be (i) sustainable, i.e., when messages are added in later iterations, they must preserve deadline guarantees of existing messages and (ii) extensible, i.e., they must accommodate future messages without changes to existing schedules. Unfortunately, traditionally used metrics of sustainability and extensibility for timing and schedulability analysis are generic and can not be trivially adapted to FlexRay schedules. This is because of platform-specific properties of FlexRay like being a hybrid paradigm, where both time-triggered and event-triggered segments are used for communication. In this paper, we first introduce new notions of sustainability and extensibility for FlexRay that capture protocol-specific properties and then present novel metrics to quantify sustainable and extensible schedules. We demonstrate the applicability of our results with industrial-size case studies and show that our proposed metrics may be visually represented allowing easy interpretation by system designers in the automotive industry.

In this paper, we consider a cyber-physical architecture where multiple control applications are divided into multiple tasks, spatially distributed over various processing units that communicate over a bus implementing a hybrid communication protocol, i.e., a protocol with both time-triggered and event-triggered communication schedules (e.g., FlexRay). In spite of efficient utilization of communication bandwidth (BW), event-triggered protocols suffer from unpredictable temporal behavior, which is exactly the opposite in the case of their time-triggered counterparts. In the context of communication delays experienced by the control-related messages exchanged over the shared communication bus, we observe that a distributed control application is more prone to performance deterioration in transient phases compared to in the steady-state. We exploit this observation to re-engineer control applications to operate in two modes, in order to optimally exploit the bi-modal (time- and event-triggered) characteristics of the underlying communication medium. Depending on the state (transient or steady) of the system, both, the control inputs and the communication schedule are now switched. Using a FlexRay-based case study, we show that such a design provides a good trade-off between control performance and bus utilization.

It is projected that the communication data volume in electric vehicles will significantly increase compared to state-of-the-art vehicles due to additional functionalities like x-by-wire and safety functions. This paper presents a networking concept for electric vehicles to cope with the high data volume in cases where a single FlexRay bus is not sufficient. We present a FlexRay switch concept that is capable of increasing the effective bandwidth and improving the safety of existing FlexRay buses. A prototype FPGA implementation shows the feasibility of our approach. Further, a scheduling approach for the FlexRay switch that obtains the optimal results based on Integer Linear Programming (ILP) is presented. Since the ILP approach becomes intractable for real-world problems, we present a heuristic three-step approach that determines the branches of the network, performs a local scheduling for each node, and finally assembles the local schedules into a global schedule. Test cases and an entire realistic in-vehicle network are used to emphasize the benefits of the proposed approach.

Automotive architectures today consist of up to 100 electronic control units (ECUs) that communicate via one or more FlexRay and CAN buses. Multiple control applications - like cruise control, brake control, etc. are specified as Simulink/Stateflow models, from which code is generated and mapped onto the different ECUs. In addition, scheduling policies and parameters, both for the ECUs and the buses, need to be specified. Code generation/optimization from the Simulink/Stateflow models, task partitioning and mapping decisions, as well as the parameters chosen for the schedulers all of these impact the execution times and timing behaviour of the control tasks and control messages. These in turn affect control performance, such as stability and steady-/transient-state behaviour. This paper discusses different aspects of this multi-layered design flow and the associated research challenges. The emphasis is on model-based code generation, analysis, testing and verification of control software for automotive architectures, as well as on architecture or platform configuration to ensure that the required control performance requirements are satisfied.

High-end cars today consist of more than 100 electronic control units (ECUs) that are connected to a set of sensors and actuators and run multiple distributed control applications. The design flow of such architectures consists of specifying control applications as Simulink/Stateflow models, followed by generating code from them and finally mapping such code onto multiple ECUs. In addition, the scheduling policies and parameters on both the ECUs and the communication buses over which they communicate also need to be specified. These policies and parameters are computed from high-level timing and control performance constraints. The proposed tutorial will cover different aspects of this design flow, with a focus on timing and schedulability problems. After reviewing the basic concepts of worst-case execution time analysis and schedulability analysis, we will discuss the differences between meeting timing constraints (as in classical real-time systems) and meeting control performance constraints (e.g., stability, steady and transient state performance). We will then describe various control performance related schedulability analysis techniques and how they may be tied to model-based software development. Finally, we will discuss various schedule synthesis techniques, both for ECUs as well as for communication protocols like FlexRay, so that control performance constraints specified at the model-level may be satisfied. Throughout the tutorial different commercial as well as academic tools will be discussed and demonstrated.

We study the impact of a novel prioritized frame dropping scheme in buffer-constrained multiprocessor system-on-chip (MPSoC) platforms. Accurate buffer dimensioning has attracted lot of research interest as large on-chip buffers result in increased silicon area and higher costs. Multimedia applications present the flexibility of trading off quality for buffer space without any noticeable deterioration in video quality. The frame dropping scheme is crucial here to drop frames appropriately such that the required buffer size is reduced and target quality requirement is satisfied. Towards this, we propose a simple prioritized frame dropping mechanism which reduces the required buffer space more than existing frame dropping policies. We also provide a fast iterative procedure to find the minimum buffer size for a video clip with O(log(Ndrop)) number of iterations, where Ndropis the maximum number of frames that can be dropped for a video clip so that a prespecified quality in terms of peak signal to noise ratio (PSNR) value is satisfied.

Personal location information is regarded as the most important contextual information transmitted in ubiquitous systems. Many pedestrian indoor localization systems rely on map-matching to constrain sensor errors. The maps required for computer aided localization and tracking need to incorporate a semantic structure. Such maps are not readily available and therefore most groups working on localization solutions manually create the required maps for specific testing scenarios. To provide a solution for map generation on a larger scale, we have developed a map generation toolkit that parses standard CAD-plans, to automatically generate topological maps for indoor environments. We propose a heuristic parser that separates superfluous data from the information depicting semantic building entities, e.g. rooms and doors. In our experiments approximately 95% of all structures were detected successfully. After the extraction we transform the extracted building information into an object-based building model designed for the application of fast particle-filter-based map-matching algorithms. A performance test with a typical filter implementation demonstrates that the model is sufficiently optimized to achieve pedestrian tracking and localization in real-time.

Admission control decisions involve determining whether a new task can be accepted by a running system such that the new task and the already running tasks all meet their deadlines. Since such decisions need to be taken on-line, there is a strong interest in developing fast and yet accurate algorithms for different setups. In this paper, we propose a constant-time admission control test for tasks that are scheduled under the Deadline Monotonic (DM) policy. The proposed test approximates the execution demand of DM tasks using a configurable number of linear segments. The more segments are used, the higher the running time of the test. However, a small number of segments normally suffice for a near-optimal admission control. The main innovation introduced by our test is that approximation segments are distributed in a non-uniform manner. We can concentrate more segments for approximating critical parts of the execution demand and reduce the number of segments where this does not change significantly. In particular, the tasks with shorter deadlines dominate the worst-case response time under DM and, hence, these should be approximated more accurately for a better performance of the algorithm. In contrast to other constant-time tests based on well-known techniques from the literature, our algorithm is remarkably less pessimistic and allows accepting a much greater number of tasks. We evaluate this through detailed experiments based on a large number of synthetic tasks and a case study.

We study the impact of video frame drops in buffer constrained multiprocessor system-on-chip (MPSoC) platforms. Since on-chip buffer memory occupies a significant amount of silicon area, accurate buffer sizing has attracted a lot of research interest lately. However, all previous work studied this problem with the underlying assumption that no video frame drops can be tolerated. In reality, multimedia applications can often tolerate some frame drops without significantly deteriorating their output quality. Although system simulations can be used to perform video quality driven buffer sizing, they are time consuming. In this paper, we first demonstrate a dual-buffer management scheme to drop only the less significant frames. Based on this scheme, we then propose a formal framework to evaluate the buffer size vs. video quality trade-offs, which in turn will help a system designer to perform quality driven buffer sizing. In particular, we mathematically characterize the maximum numbers of frame drops for various buffer sizes and evaluate how they affect the worst-case PSNR value of the decoded video. We evaluate our proposed framework with anMPEG-2 decoder and compare the obtained results with that of a cycle-accurate simulator. Our evaluations show that for an acceptable quality of 30 dB, it is possible to reduce the buffer size by up to 28.6% which amounts to 25.88 megabits.

In recent work, approximation of the demand bound function for a sporadic task uses a linear approximation when the interval length of interest is larger than the relative deadline of the task. Such an approximation leads to a factor 2 for resource augmentation under a naive analysis, i.e., if the schedulability test using this approximate demand bound function fails, the task set is not schedulable by slowing down the system to 50% of the original speed. In this paper we provide a tighter analysis of such an approach on uniprocessor systems and on identical multiprocessor systems with partitioned scheduling under the earliest-deadline-first strategy. For uniprocessor systems, we prove that the resource augmentation factor is at most 2e-1/e ≈ 1.6322, where e is the Euler number. For identical multiprocessor systems with M processors, with respect to resource augmentation, we show that deadline-monotonic partitioning with approximate demand bound functions leads to a factor 3e-1/e-1/M ≈ 2.6322-1/M for constrained-deadline task sets and a factor 3-1/M for arbitrary-deadline task sets, in which the best results known so far are 3-1/M for constrained-deadline ones and 4-2/M for arbitrary-deadline ones. Moreover, we also provide concrete input instances to show that the lower bound of resource augmentation factors for uniprocessor systems (identical multiprocessor systems under an arbitrary order of fitting and a large number of processors, respectively) under such approaches is 1.5 (2.5, respectively).

The Bluetooth SIG recently released the Health Device Profile (HDP) in an effort to standardize health device communication using Bluetooth technology. HDP uses the IEEE 11073-20601 Data Exchange Protocol as the transport content. The same traffic can be sent using the popular Serial Port Profile (SPP), but this profile is not configured for health device communication. HDP's strict configurations and health device-specific requirements give the impression that it would have a reduced performance in comparison to SPP. In this paper we compare HDP with SPP by analyzing multi-rate data transmission in the context of a cardiovascular monitoring application. In particular, we model the expected number of transmissions and packet loss incurred by the two profiles. Our results show that in contrast to popular belief the transmission energy is similar for both profiles, but HDP offers the advantage of plug-and-play interoperability.

Synchronous languages like Esterel have gained wide popularity in certain domains such as avionics. However, platform-specific timing analysis of code generated from Esterel-like specifications have mostly been neglected so far. The growing volume of electronics and software in domains like automotive, calls for formal-specification based code generation to replace manually written and optimized code. Such cost-sensitive domains require tight estimation of timing properties of the generated code. Towards this goal, we propose a scheme for generating C code from Esterel specifications for a multiprocessor platform, followed by timing analysis of the generated code. Due to dependencies across program fragments mapped onto different processors, traditional Worst-Case Execution Time (WCET) analysis techniques for sequential programs cannot applied be to this setting. Our proposed timing analysis technique is tailored to capture such inter-processor code dependencies. Our main novelty stems from how we detect and remove infeasible paths arising from a multiprocessor implementation during our timing analysis. We apply our timing analysis on a number of standard Esterel benchmarks, which show that performing the proposed inter-processor infeasible path elimination may lead to up to 14.3% tighter estimation of the WCRT, thereby leading to resource over-dimensioning and poor design.

The admission control problem is concerned with determining whether a new task may be accepted by a system consisting of a set of running tasks, such that the already admitted and the new task are all schedulable. Clearly, admission control decisions are to be taken on-line, and hence, this constitutes a general problem that arises in many real-time and embedded systems. As a result, there has always been a strong interest in developing efficient admission control algorithms for various setups. In this paper, we propose a novel constant-time admission control test for the Deadline Monotonic (DM) policy, i.e., the time taken by the test does not depend on the number of admitted tasks currently in the system. While it is possible to adapt known utilization bounds from the literature to derive constant-time admission control tests (e.g., the Liu and Layland bound, or the more recent hyperbolic bound), the test we propose is less pessimistic. We illustrate this analytically where possible and through a set of detailed experiments. Apart from the practical relevance of the proposed test in the specific context of DM tasks, the underlying technique is general enough and can possibly be extended to other scheduling policies as well.

An admission control test is responsible for deciding whether a new task may be accepted by a set of running tasks, such that the already admitted and the new task are all schedulable. Admission control decisions have to betaken on-line and, hence, there is a strong interest in developing efficient algorithms for different setups. In this paper, we propose a novel constant-time admission control test for tasks scheduled on identical processors under partitioned Earliest Deadline First (EDF), i.e., once tasks have been assigned to a processor they remain on that processor. In particular, to model demanding real-time systems, we consider the case where relative deadlines may be less than the minimum separation between two consecutive task activations or jobs. The main advantage of the proposed test is that the time it takes is independent of the number of tasks currently admitted in the system. While it is possible to adapt polynomial-time schedulability tests from the literature to design a linear or even constant-time admission control for this setup, the test we propose provides a better accuracy/complexity ratio. We evaluate this test through a set of detailed experiments based on synthetic tasks and a realistic case study consisting of a real-time multimedia server.

This tutorial is concerned with various aspects of model-based design of hardware/software architectures of automotive systems. It will be split into three parts, the first dealing with model-based analysis of automotive ECU networks, the second with synthesis of schedules for such networks, and finally the third with model-based testing of such architectures.

Automotive architectures consist of multiple electronic control units (ECUs) which run distributed control applications. Such ECUs are connected to sensors and actuators and communicate via shared buses. Resource arbitration at the ECUs and also in the communication medium, coupled with variabilities in execution requirements of tasks results in jitter in the signal/data streams existing in the system. As a result, buffers are required at the ECUs and bus controllers. However, these buffers often implement different semantics -- FIFO queuing, which is the most straightforward buffering scheme, and data refreshing, where stale data is overwritten by freshly sampled data. Traditional timing and schedulability analysis that are used to compute, e.g., end-to-end delays, in such automotive architectures can only model FIFO buffering. As a result, they return pessimistic delay and resource estimates because in reality paper we propose an analytical framework for accurately modeling such data refresh semantics. Our model exploits a novel feedback control mechanism and is purely functional in nature. As a result, it is scalable and does not involve any explicit state modeling. Using this model we can estimate various timing and performance metrics for automotive ECU networks consisting of buffers implementing different data handling semantics. We illustrate the utility of this model through three case studies from the automotive electronics domain.

The design process for automotive electronics is an iterative process, where new components and distributed applications are added over several design cycles incrementally. Hence, at each design iteration an existing communication schedule is extended by new messages that have to be scheduled appropriately. In this paper, the goal has been to synthesize schedules under real-time constraints for the dynamic segment of Flex Ray with respect to the 64-cycle protocol specification. We propose a flexible scheduling framework to generate all feasible schedules for a set of messages satisfying real-time and protocol constraints. Further, we present an optimization procedure to retain schedules according to suitable design metrics. Even though the size of the possible design space is exponential in the number of messages, our proposed method keeps down the schedule synthesis time to practically acceptable values as shown in the experiments.

While dynamic voltage and frequency scaling (DVFS) based power management has been widely studied for video processing, there is very little work on game power management. Recent work on proportional-integral-derivative (PID) controllers fro predicting game workload used hand-turned PID controller gains on relatively short game plays. This left open questions on the robustness of the PID controller and how sensitive the prediction quality is on the choice of the gain values, especially for long game plays involving different scenarios and scene changes. In this paper we propose a Least Mean Squares (LMS) Linear Predictor, which is a regression model commonly used for system parameter identification. Our results show that game workload variation can be estimated using a linear-in-parameters (LIP) model. This observation dramatically reduces the complexity of parameter estimation as the LMS Linear Predictor learns the relevant parameters of the model iteratively as the game progresses. The only parameter to be tuned by the system designer is the learning rate, which is relatively straightforward. Our experimental results using the LMS Linear Predictor show comparable power savings and game quality with those obtained from a highly-tuned PID controller.

Maximizing passengers comfort is an important research topic in the domain of automotive systems engineering. In particular, an automatic adjustment of seat position according to driver height significantly increases the level of comfort during ingress. In this paper, we present a new method to estimate the height of approaching car drivers based on a single omni directional camera integrated with the side-view mirror of a car. Towards this, we propose mathematical descriptions of standard parking scenarios, allowing for an accurate height estimation. First, approaching drivers are extracted from image frames captured by the camera. Second, the scenario and height are initially estimated based on gathered samples of angles to head and foot-points of an approaching driver. An iterative optimization process removes outliers and refines the initially estimated scenario and height. Finally, we present a number of experimental results based on image sequences captured from real-life ingress scenarios.

Techniques for hardware virtualization have been successfully used to provide hardware-independent services and increase isolation between applications in the desktop domain. However, these characteristics make hardware virtualization also interesting for other domains like those involving control tasks. Since these techniques were initially not conceived for this kind of environments where, in particular, timing constraints must be guaranteed, it is necessary to analyze their behavior and investigate the viability of possible solutions based on them. In this paper, we are concerned with using VMs (Virtual Machines) to provide real-time services in the context of automotive control applications. For this purpose, we make use of the Xen hyper visor to design a real-time control loop on the top of a virtualization layer. We first analyze a typical Xen configuration and identify problems that arise when it is used for real-time applications. We show that the worst-case performance of Xen's standard SEDF scheduler (Simple Earliest Deadline First) can be improved by incorporating some minimal modifications. In addition, in order to reduce latency and jitter in a real-time control loop, we propose a new scheduler for the Xen hyper visor that uses the concept of a real-time VM. Real-time VMs are then scheduled before any other VM and under a fixed-priority policy. The proposed VM-based solution is shown to guarantee timing constraints typically encountered in automotive control applications. We further illustrate this through an extensive set of experiments.

Due to the growing complexity of multiprocessor systems-on-chip (MPSoCs), there is an increasing demand on efficient design space exploration techniques. In addition to the analysis of diverse hardware architectures, these techniques should assist the designer in the flexible evaluation of various scheduling policies and application mappings while taking effects of the shared on-chip communication infrastructure into account. Most available simulation approaches are either unable to cover all these aspects jointly or have poor simulation performance. In this paper, we present a framework for timing analysis of MPSoC architectures using abstract and yet accurate traces. The traces capture both precise processing latencies and memory access patterns and represent application- and OS-related workload. Performance estimation is performed by an interleaved execution of the traces on a highly configurable multiprocessor platform modeled in our trace-driven SystemC TLM simulator. Using the flexible scheduler model presented in this paper, various mappings and scheduling policies can be rapidly evaluated while considering on-chip interconnect contention and usage of shared resources. Due to the abstraction of the trace-driven simulations, the proposed framework allows for both fast and accurate explorations of MPSoC design alternatives.

Proceedings - Design Automation Conference

In this paper, a design method for automotive architectures is proposed. The two main technical contributions are (i) a novel hardware/software architecture encoding that unifies a number of design steps, i.e., resource allocation, process binding, message routing, scheduling, and parameter estimation for the processor and bus schedulers, and (ii) a hybrid scheme that allows different timing analysis techniques to be applied to different bus protocols (viz., CAN and FlexRay) within the same architecture in order to derive global performance estimates such as end-to-end delays of messages. The use of the compact encoding technique substantially reduces the underlying search space, and the hybrid timing analysis scheme allows the combination of known timing analysis techniques from the real-time systems domain. The proposed techniques were combined into a tool-chain and a real-life case study to illustrate their advantages.

Traditionally, synchronous languages, such as Esterel, have been compiled into hardware, where timing analysis is relatively easy. When compiled into software -- e.g., into sequential C code -- very conservative estimation techniques have been used, where the focus has only been on obtaining safe timing estimates and not on the cost of the implementation. While this was acceptable in avionics, efficient implementations and hence tight timing estimates are needed in more cost-sensitive application domains. Lately, a number of advances in Worst-Case Execution Time (WCET) analysis techniques, coupled with the growing use of software in domains such as automotives, have led to a considerable interest in timing analysis of code generated from Esterel specifications. In this paper we propose techniques to obtain tight estimates on the processing time of input events by sequential C code generated from Esterel programs. Execution of an Esterel program -- as in all other synchronous languages -- is logically made up of a sequence of clock ticks. In reality, they take non-zero time which depends on the generated C code as well as the underlying hardware platform on which this code is executed. Apart from exploiting the specific structure of this C code to obtain tight WCET estimates, we capture program-level contexts across ticks in order to obtain tight estimates on response times of events whose processing spans across multiple clock ticks. Such tighter estimates immediately translate into more cost-effective implementations. Our experimental results with realistic case studies show 30% reduction in timing estimates when program level context information is taken into account.

Over the last few years, Real-Time Calculus has been used extensively to model and analyze embedded systems processing continuous data/event streams. Towards this, bounds on the arrival process of streams and bounds on the processing capacity of resources serve as inputs to the model, which are used to calculate end-to-end delays suffered by streams, maximum backlog, utilization of resources, etc. This "functional'' model, although amenable to computationally inexpensive analysis methods, has limited modeling capability. In particular, "state-based'' processing, e.g. blocking write - where the processing depends on the "state'' or fill-level of the buffer - cannot be modeled in a straightforward manner. This has led to a number of recent proposals on using automata-theoretic models for stream processing systems (e.g. Event Count Automata [RTSS 2005]). Although such models offer better modeling flexibility, they suffer from the usual state-space explosion problem. In this paper we show that a number of complex state-dependencies can be modeled in a lightweight manner, using a feedback control technique. This avoids explicit state modeling, and hence the state-space explosion problem. Our proposed modeling and analysis therefore extend the original Real-Time Calculus-based functional modeling in a very useful way, and cover much larger problem domain compared to what was previously possible without explicit state-modeling. We illustrate its utility through two case studies and also compare our analysis results with those obtained from detailed system simulations (which are significantly more time consuming).

Many embedded platforms consist of a heterogeneous collection of processing elements, memory modules, and communication subsystems. These components often implement different scheduling/arbitration policies, have different interfaces, and are supplied by different vendors. Hence, compositional techniques for modeling and analyzing such platforms are of interest. In prior work, the real-time calculus framework has proven to be very effective in this regard. However, real-time calculus has heretofore been limited to systems with uniprocessor processing elements, which is a serious impediment given the advent of multicore technologies. In this paper, a two-step approach is proposed that allows the power of real-time calculus to be applied in globally-scheduled multiprocessor systems: first, assuming that job response-time bounds are given, determine whether these bounds are met; second, using these bounds, determine the resulting residual processor supply and streams of job completion events using formalisms from real-time calculus. For this methodology to be applied in settings where response-time bounds are not specified, such bounds must be determined. Though this is an issue that warrants further investigation, a method is discussed for calculating such bounds that is applicable to a large family of fixed job-priority schedulers. The utility of the proposed analysis framework is demonstrated using a case study.

Many embedded systems operate in multiple modes, where mode switches can be both time- as well as event-triggered. While timing and schedulability analysis of the system when it is operating in a single mode has been well studied, it is always difficult to piece together the results from different modes in order to deduce the timing properties of a multi-mode system. As a result, often certain restrictive assumptions are made, e.g., restricting the time instants at which mode changes might occur. The problem becomes more complex when both time- and event-triggered mode changes are allowed. Further, for complex systems that cannot be described by traditional periodic/sporadic event models (i.e., where event streams are more complex/bursty) modeling multiple modes is largely an open problem. In this paper we propose a model and associated analysis techniques to describe embedded systems that process multiple bursty/complex event/data streams and in which mode changes are both time- and event-triggered. Compared to previous studies, our model is very general and can capture a wide variety of real-life systems. Our analysis techniques can be used to determine different performance metrics, such as the maximum fill-levels of different buffers and the delays suffered by the streams being processed by the system. The main novelty in our analysis lies in how we piece together results from the different modes in order to obtain performance metrics for the full system. Towards this, we propose both - exact, but computationally expensive, as well as safe approximation techniques. The utility of our model and analysis has been illustrated using a detailed smart-phone case study.

We propose a control theory-based dynamic voltage scaling (DVS) algorithm for interactive 3D game applications running on battery-powered portable devices. Using this scheme, we periodically adjust the game workload prediction based on the feedback from recent prediction errors. Although such control-theoretic feedback mechanisms have been widely applied to predict the workload of video decoding applications, they heavily rely on estimating the queue lengths of video frame buffers. Given the interactive nature of games -- where game frames cannot be buffered - the control-theoretic DVS schemes for video applications can no longer be applied. Our main contribution is to suitably adapt these schemes for interactive games. Compared to history-based workload prediction schemes - where the workload of a game frame is predicted by averaging the workload of the previously-rendered frames -- our proposed scheme yields significant improvement on different platforms (e.g. a laptop and a PDA) both in terms of energy savings as well as output quality.

Today, battery-life is a major design concern for all portable devices ranging from cell phones to PDAs and portable game consoles. The purpose of this tutorial will be to give an overview of power management techniques that are applicable to multimedia applications running on such battery-operated portable devices. In particular, we will discuss a host of techniques, some of which are applicable to audio processing applications, some to video processing, and the others to interactive 3D game applications. The tutorial will be helpful to students, researchers, application developers and engineers who have a background in traditional real-time multimedia applications and would like to get an overview of the important issues and solutions pertaining to using and developing power management techniques for the multimedia domain.

Interactive 3D games are now widely available on a variety of mobile devices for which battery-life is a major concern. Many of these devices support voltage/frequency-scalable processors and dynamic voltage scaling (DVS) has emerged as a powerful technique for energy management in such devices. Although DVS algorithms have been very successfully applied to video encoding/decoding applications, their use in interactive computer games has not been sufficiently explored so far. In this paper we propose a novel DVS scheme that is specifically directed towards interactive 3D game applications running on battery-operated portable devices. The key to this DVS scheme lies in an accurate prediction of the rendering workload of a current game scene. We have applied this scheme to first person shooter games (e.g. Quake II) and obtained significant power savings while maintaining high frame rates. Based on the observation that there exist two types of workload variations in such games, we compute the voltage/frequency setting for any game scene using a hybrid combination of two different techniques: (i) adjusting the workload prediction using a control-theoretical feedback mechanism, and (ii) analyzing the graphical objects in the current game scene by parsing the corresponding frame. Our scheme is significantly different from those commonly applied to video decoding applications (where only technique (i) is used) and has shown very encouraging results when evaluated with different setups (e.g. laptop running Windows, PDA running Windows Mobile and a configurable simulation platform).

Message sequence charts (MSCs) are widely used for describing interaction scenarios between the components of a distributed system. Consequently, worst-case response time estimation and schedulability analysis of MSC-based specifications form natural building blocks for designing distributed real-time systems. However, currently there exists a large gap between the timing and quantitative performance analysis techniques that exist in the real-time systems literature, and the modeling/specification techniques that are advocated by the formal methods community. As a result, although a number of schedulability analysis techniques are known for a variety of task graph-based models, it is not clear if they can be used to effectively analyze standard specification formalisms such as MSCs. In this paper we make an attempt to bridge this gap by proposing a schedulability analysis technique for MSC-based system specifications. We show that compared to existing timing analysis techniques for distributed real-time systems, our proposed analysis gives tighter results, which immediately translate to better system design and improved resource dimensioning. We illustrate the details of our analysis using a setup from the automotive electronics domain, which consist of two real-life application programs (that are naturally modeled using MSCs) running on a platform consisting of multiple electronic control units (ECUs) connected via a FlexRay bus.

The Real-Time Calculus (RTC) framework proposed in [Chakraborty et al., DATE 2003] and subsequently extended in [Wandeler et al., Real-Time Systems 29(2-3), 2005] and a number of other papers is geared towards the analysis of real-time systems that process various types of streaming data. The main strength of RTC is a count-based abstraction, where arrival patterns of event streams are specified as constraints on the number of events that may arrive over any specified time interval. In this framework, algebraic techniques can be used to compute system properties in a compositional way. However, the main drawback of RTC is that it cannot model state information in a natural way. For example, when a scheduling policy depends on the fill-level of a certain buffer or there is a shift from one type of data stream into another. In this paper, we extend RTC in a manner that enables state information to be easily captured while limiting the state-space explosion caused by fine grained state-based models such as timed automata. Our model, called "multi-mode RTC", specifies event streams as finite automata whose states are annotated with functions that specify constraints on the arrival patterns of event streams or the service available to process them. Our new framework combines the expressiveness of state-based models with the algebraic and compositional features of the RTC formalism. In particular, system properties within a single mode can be analyzed using the RTC-based algebraic techniques and state-space exploration can be used to piece together the results obtained algebraically for the individual modes. We show how to determine typical system properties with the focus on efficient approximate techniques and illustrate the advantages of multi-mode RTC using two case studies.

Today, most personal mobile devices (e.g., cell phones and PDAs) are multimedia-enabled and support a variety of concurrently running applications, such as audio/video players, word processors, and web browsers. Media-processing applications are often computationally expensive and most of these devices typically have 100--400-MHz processors. As a result, the user-perceived application response times are often poor when multiple applications are concurrently fired. In this paper, we show that by using application-specific dynamic buffering techniques, the workload of these applications can be suitably “shaped” to fit the available processor bandwidth. Our techniques are analogous to traffic shaping , which is widely used in communication networks to optimally utilize network bandwidth. Such shaping techniques have recently attracted a lot of attention in the context of embedded systems design (e.g., for dynamic voltage scaling). However, they have not been exploited for enhanced schedulability of multiple applications, as we do in this paper.

It is now widely believed that FlexRay will emerge as the predominant protocol for in-vehicle automotive communication systems. As a result, there has been a lot of recent interest in timing and predictability analysis techniques that are specifically targeted towards FlexRay. In this paper we propose a compositional performance analysis framework for a network of electronic control units (ECUs) that communicate via a FlexRay bus. Given a specification of the tasks running on the different ECUs, the scheduling policy used at each ECU, and a specification of the FlexRay bus (e.g. slot sizes and message priorities), our framework can answer questions related to the maximum end-to-end delay experienced by any message, the amount of buffer required at each communication controller and the utilization of the different ECUs and the bus. In contrast to previous timing analysis techniques which analyze the FlexRay bus in isolation, our framework is fully compositional and allows the modeling of the schedulers at the ECUs and the FlexRay protocol in a seamless manner. As a result, it can be used to analyze large systems and does not involve any computationally expensive step like solving an ILP (which previous approaches require). We illustrate our framework using detailed examples and also present results from a Matlab-based implementation.

It is now common for multimedia applications to be partitioned and mapped onto multiple processing elements of a system-on-chip architecture. An important design constraint in such architectures is that the FIFO buffers connecting the processing elements (in a pipelined fashion) should not overflow and the playout buffer should never underflow. To meet these constraints, an usual design practice is to increase the initial playout delay after which the output device starts reading from the playout buffer. Although implementing this technique is straightforward and involves only the the computation of an appropriate playout delay, it suffers from the downside of a large playout buffer being required. In this paper, instead of associating the playout delay solely with the output device, we propose to redistribute this delay among all the processing elements running the various tasks of the multimedia application. We show that this delay redistribution technique can signficantly reduce (up to 70%) the total on-chip memory required.

Of late, there has been a considerable interest in models, algorithms and methodologies specifically targeted towards designing hardware and software for streaming applications. Such applications process potentially infinite streams of audio/video data or network packets and are found in a wide range of devices, starting from mobile phones to set-top boxes. Given a streaming application and an architecture, the timing analysis problem is to determine the timing properties of the processed data stream, given the timing properties of the input stream. Most of the previous work related to estimating or optimizing these timing properties take a high-level view of the architecture and neglect microarchitectural features such as caches. In this paper, we show that an accurate estimation of a streaming application's timing properties, however, heavily relies on an appropriate modeling of the processor micro-architecture, such as its instruction cache. Towards this, we present a novel framework for timing analysis of stream processing applications. Our framework accurately models the evolution of the instruction cache of the underlying processor as a stream is processed, and the fact that the execution time involved in processing any data item depends on all the previous data items occurring in the stream. We have implemented a prototype of this framework partly in C and partly in Mathematica and plan to integrate it into a design-space exploration tool for system-level design of hardware-software architectures for streaming applications.

Most of today's real-time embedded systems consist of a heterogeneous mix of fully-programmable processors, fixed-function components or hardware accelerators, and partially-programmable engines. Hence, system designers are faced with an array of implementation possibilities for an application at hand. Such possibilities typically come with different tradeoffs involving cost, power consumption and packaging constraints. As a result, a designer is no longer interested in one implementation that meets the specified real-time constraints (i.e. is schedulable), but would rather like to identify all schedulable implementations that expose the different possible performance tradeoffs. In this paper we formally define this multicriteria schedulability analysis problem and derive a polynomial-time approximation algorithm for solving it. This result is interesting because the problem of optimally computing even one schedulable solution in our setup (and in most common setups) is computationally intractable (NP-hard). Further, our algorithm is reasonably easy to implement, returns good quality (approximate) solutions, and offers significant speedups over optimally computing all schedulable tradeoffs

In this paper we explore the possibility of using commodity graphics processing units (GPUs) to speedup standard schedulability analysis algorithms. Our long-term goal is to exploit GPUs to accelerate common electronic design automation algorithms, most of which tend to be computationally expensive. Our main contribution in this paper is a reformulation of a standard demand bound criteria-based schedulability analysis algorithm as a streaming algorithm expressed in terms of computer graphics primitives. This allows the algorithm to be efficiently implemented on a GPU, thereby resulting in very attractive speedups.

We present a performance analysis technique for distributed real-time systems in a setting where certain components are modeled in a purely functional manner, while the remaining components require additional modeling of state information. The functional models can be efficiently analyzed but have restricted expressiveness. On the other hand, state-based models are more expressive and offer a richer set of analyzable properties but are computationally more expensive to analyze. We show that by appropriately composing these two classes of models it is possible to leverage on their respective advantages. To this end, we propose an interface between components that are modeled using real-time calculus [Chakraborty, Kiinzli and Thiele, DATE 2003] and those that are modeled using event count automata [Chakraborty, Phan and Thiagarajan, RTSS 2005]. The resulting modeling technique is as expressive as event count automata, but is amenable to more efficient analysis. We illustrate these advantages using a number of examples and a detailed case study.

A typical design process for real-time embedded systems involves choosing the values of certain system parameters and performing a schedulability analysis to determine whether all deadline constraints can be satisfied. If such an analysis returns a negative answer, then some of the parameters are modified and the analysis is invoked once again. This iteration is repeated until a schedulable design is obtained. However, the schedulability analysis problem for most task models is intractable (usually co-NP hard) and, hence, such an iterative design process is often very expensive. To get around this problem, we introduce the concept of “interactive” schedulability analysis. It is based on the observation that if only a small number of system parameters are changed, then it is not necessary to rerun the full schedulability analysis algorithm, thereby making the iterative design process considerably faster. We refer to this analysis as being “interactive” because it is supposed to be run in an interactive mode. This concept is fairly general and can be applied to a wide variety of task models. In this paper, we have chosen the recurring real-time task model, because it can be used to represent realistic applications from the embedded systems domain (containing conditional branches and fine-grained deadline constraints). Our experimental results show that using our scheme can lead to more than 20× speedup for each invocation of the schedulability analysis algorithm, compared to the case where the full algorithm is run.

Graphics-intensive computer games are no longer restricted to high-performance desktops, but are also available on a variety of portable devices ranging from notebooks to PDAs and mobile phones. Battery life has been a major concern in the design of both the hardware and the software for such devices. Towards this, dynamic voltage and frequency scaling (DVFS) has emerged as a powerful technique. However, the showcase application for DVFS algorithms so far has largely been video decoding, primarily because it is computationally expensive and its workload exhibits a high degree of variability. This paper investigates the possibility of applying DVFS to interactive computer games, which to the best of our knowledge has not been studied before. We show that the variability in the workload associated with a popular First Person Shooter game like Quake II is significantly higher than video decoding. Although this variability makes game applications an attractive candidate for DVFS, it is unclear if DVFS algorithms can be applied to games due to their interactive (and hence highly unpredictable) nature. In this paper, we show using detailed experiments that (surprisingly) interactive computer games are highly amenable to DVFS. Towards this we present a novel workload characterization of computer games, based on the game engine for Quake II. We believe that our findings might potentially lead to a number of innovative DVFS algorithms targeted towards game applications, exactly as video decoding has motivated a variety of schemes for DVFS.

The recurring real-time task model was recently proposed as a model for real-time processes that contain code with conditional branches. In this paper, we present a necessary and sufficient condition for uniprocessor non-preemptive schedulability analysis for this task model. We also derive a polynomial-time approximation algorithm for testing this condition. Preemptive schedulers usually have a larger schedulability region compared to their non-preemptive counterparts. Further, for most realistic task models, schedulability analysis for the non-preemptive version is computationally more complex compared to the corresponding preemptive version. Our results in this paper show that (surprisingly) the recurring real-time task model does not fall in line with these intuitive expectations, i.e. there exists polynomial-time approximation algorithms for both preemptive and non-preemptive versions of schedulability analysis. This has important implications on the applicability of this model, since fully preemptive scheduling algorithms often have significantly larger runtime overheads

Real-time multimedia applications today represent the predominant workload in embedded devices ranging from set-top boxes to mobile phones and PDAs. However, implementing and performance tuning of such applications on embedded architectures is a challenging problem. On one hand, such architectures are increasingly becoming complex, with multiple processors, different kinds of memory subsystems and diverse on-chip communication architectures. On the other hand, designers of embedded devices, as well as application developers targeting such devices are faced with stringent performance constraints and time-to-market pressures. This has led to a lot of interest in (i) generic System-on-Chip (SoC) platform or template architectures which can be easily tuned for the application at hand, (ii) techniques for rapidly mapping/developing applications for such architectures, (iii) models and tools for analyzing and performance debugging of such implementations. This tutorial will provide a comprehensive overview of the recent developments in this area. It will be helpful to students, researchers, application developers and engineers who have a background in traditional real-time multimedia applications and would like to get an overview of the important issues and solutions pertaining to developing and performance debugging of multimedia applications for embedded SoC platforms.

In this paper we address the "rate analysis" problem for media-processing pla$brnzs consisting oJ'rnultiple processor cores connected zn a pipelined fashion. More precisely, we aim at determining tight bounds on the rates at which multimedia streams can be fed into such urchitectures. These bounds depend on urchitectuml constt-uints (e.g. the available on-chip memory, bus urhitrution policies, etc.), as well as the upplicution churacteristics (e.g. application partitioning und mapping, workloud rutes generaled by different tasks, etc.). The proposed frurnework for rate analysis can be used for fast design space exploration to determine how these bounds change with different architrctural parameters, mapping of the application, or chunging the QoS requirements associated with the input strrarns.

Hierarchical scheduling frameworks have lately received a lot of attention for component-based design of complex real-time systems. The specification of the resource reservation policy play a dominant role in such frameworks. In this context, the notion of real-time virtual resources results a very flexible representation of resource reservation schemes. We intend to combine the advantages offered by virtual resource scheduling with very general event models specified using real-time calculus. Our proposed framework permits resource partitioning to be extended to multiple levels and handles a wider range of scheduling algorithms and task models. In addition, it allows the handling of data dependencies between tasks from different task groups in the hierarchy.

Interface-based design is now considered to be one of the keys to tackling the increasing complexity of modern embedded systems. The central idea is that different components comprising such systems can be developed independently and a system designer can connect them together only if their interfaces match, without knowing the details of their internals. We use the concept of rate interfaces for compositional (correct-by-construction) design of embedded systems whose components communicate through data streams. Using the associated rate interface algebra, two components can be connected together if the output rate of one component is "compatible" with the input rate of the other component. We formalize this notion of compatibility and show that such an algebra is non-trivial because it has to accurately model the burstiness in the arrival rates of such data streams and the variability in their processing requirements. We discuss how rate interfaces simplify compositional design and at the same time help in functional and performance verification which would be difficult to address otherwise. Finally, we illustrate these advantages through a realistic case study involving a component-based design of a multiprocessor architecture running a picture-in-picture application

Recently, a number of event-centric models have been proposed for analyzing multimedia applications running on multiprocessor system-on-chip (SoC) platforms. This has given shape to a general framework using which different timing and performance analysis questions can be answered in a single coherent manner. Central to this framework is a model for expressing the timing properties associated with different multimedia streams and a means for computing how these properties change as a stream gets successively processed by the different processors of a platform. In contrast to standard event models like periodic or sporadic, this model can accurately capture the data-dependent execution time variabilities associated multimedia tasks and the burstiness of on-chip traffic resulting from multimedia processing. In this paper, we give a high-level view of this framework, describe setups which currently can be modelled using it, and identify possible directions in which this framework should be extended to make it more usable.

System-level design methods specifically targeted towards multimedia applications have recently received a lot of attention. Multimedia workloads are known to have a high degree of variability. Therefore, designs based on a worstcase analysis of such workloads tend of be overly pessimistic. We address this issue by introducing a new concept called approximate variability characterization curves (or Approximate VCCs), to characterize the "average-case" behavior of multimedia workloads in a parameterized fashion. Since most multimedia applications only have soft real-time constraints, it is often possible to tolerate a small amount of performance degradation. By allowing such small degradations in the performance, large amounts of resource savings are possible. The concept of Approximate VCCs that we present in this paper allows a designer to quantitatively account for the performance degradation and the associated resource savings. We illustrate this using two typical system design cases.

In this paper, we introduce a new task model that is specifically targeted towards representing stream processing applications. Examples of such applications are those involved in network packet processing (such as a software-based router) and multimedia processing (such as an MPEG decoder application). Our task model is made up of two parts: (i) a new task structure to accurately model the software structures of stream processing applications such as conditional branches and different end-to-end deadlines for different types of input data items, and (ii) a new event model to represent the arrival pattern of the data items to be processed, which triggers the task structure. This event model is more expressive than classical models such as purely periodic, periodic with jitter or sporadic event models. We then present algorithms for the schedulability analysis of this task model. The basic scheme underlying our algorithms is a generalization of the techniques used for the schedulability analysis of the recently proposed generalized multiframe and the recurring real-time task models.

Dynamic voltage/frequency scheduling algorithms for multimedia applications have recently been a subject of intensive research. Many of these algorithms use control-theoretic feedback techniques to predict the future execution demand of an application based on the demand in the recent past. Such techniques suffer from two major disadvantages: (i) they are computationally expensive, and (ii) it is difficult to give performance or quality-of-service guarantees based on these techniques (since the predictions can occasionally turn out to be incorrect). To address these shortcomings, in this paper we propose a completely new approach for dynamic voltage and frequency scaling. Our technique is based on an offline bitstream analysis of multimedia files. Based on this analysis, we insert metadata information describing the computational demand that will be generated when decoding the file. Such bitstream analysis and metadata insertion can be done when the multimedia file is being downloaded into a portable device from a desktop computer. In this paper we illustrate this technique using the MPEG-2 decoder application. We show that the amount of metadata that needs to be inserted is a very small fraction of the total size of the video clip and it can lead to significant energy savings. The metadata inserted will typically consist of the frequency value at which the processor needs to be run at different points in time during the decoding process. Lastly, in contrast to runtime prediction-based techniques, our scheme can be used to provide performance and quality-of-service guarantees and at the same time avoids any runtime computation overhead.

We propose a new workload-scalable audio decoding scheme that would enable users to control the tradeoff between playback quality and power consumption in battery-powered portable audio players. Our objective is to give users a control at the decoder side, similar to the Long Play (LP) recording mode at the encoder side in many media recording devices. The main contribution of this paper is a proposal for a Bandwidth and Stereo-image Scalable (BSS) decoding scheme for single-layer audio formats such as MP3. The proposed scheme is based on an analysis of the perceptual relevance of different audio components in the compressed bitstream. The bandwidth and stereo-image scalability directly translates into scalability in terms of the computational workload generated by the decoder. This can be exploited by a voltage/frequency scalable processor to save energy and prolong the battery life.

Multimedia applications today constitute a significant fraction of the workload running on portable devices such as mobile phones, PDAs and MP3 players. However, the processors in such devices are usually not powerful enough to support multiple concurrently executing multimedia tasks. In this context, different processor scheduling algorithms have attracted a lot of attention. This paper attempts to address the CPU constraint problem from a different perspective. It is based on the observation that by increasing the playout delay of a multimedia task, the minimum processor frequency required to run the task decreases. This is due to the high data-dependent variability in the execution requirements of multimedia tasks. We also present a framework, using which it is possible to compute the minimum processor frequency corresponding to any playout delay. Given a set of concurrently executing multimedia tasks, using our framework it is possible to compute the playout delays for each of these tasks, such that the sum of their corresponding processor cycle requirements do not exceed the maximum frequency supported by the processor.

Recently there has been a growing interest in models and methods targeted towards the (co)design of stream processing applications; e.g. those for audio/video processing. Streams processed by such applications tend to be highly bursty and exhibit a high data-dependent variability in their processing requirements. As a result, classical event and service models such as periodic, sporadic, etc. can be overly pessimistic when dealing with such applications. In this paper, we present a new model called event count automata (ECA) for capturing the timing properties of such streams. Our model can be used to cleanly formulate properties relevant to stream processing on heterogeneous multiprocessor architectures, such as buffer overflow/underflow constraints. It can also provide the basis for developing analysis methods to compute delay/timing properties of the processed streams under different scheduling policies. Our ECAs, though similar in flavor to timed and hybrid automata, have a different semantics, are more light-weight, and are specifically suited for modeling stream processing applications and architectures. We present the basic aspects of this model and illustrate its modeling potential. We then apply it in a specific stream processing setting and develop an analysis technique based on the formalism of colored Petri nets (CPNs). Finally, we validate our modeling and analysis techniques with the help of preliminary experimental results generated using the CPN simulation tool

Of late, there has been a considerable interest in generic and configurable system-on-chip platforms specifically targeted towards implementing multimedia applications. A number of such platforms offer the possibility of including processor soft cores which are highly customizable. For voltage/frequency scaled processors, such customization includes the selection of appropriate voltage/frequency operating points which are tuned to the application set to be mapped onto the platform. In this context, we present an analytical framework that can guide a system designer in identifying the frequency ranges that should be supported by the different processors of a platform architecture. This framework can also be used to identify how such frequency ranges depend on the different parameters of the architecture (such as on-chip buffer sizes), and the performance impacts associated with selecting a particular frequency range. In the case of multimedia streaming applications, identifying such performance impacts and tradeoffs involved in customizing a platform architecture is especially difficult due to the bursty nature of on-chip traffic arising out of multimedia processing and the high variability in their execution requirements. The framework presented here is designed to precisely capture such characteristics and can be used in the design-space exploration of energy-aware platform architectures for multimedia processing.

Many real-time embedded systems involve a collection of independently executing event-driven code blocks, having hard real-time constraints. Tasks in many such systems, like network processors, are either not preemptable or have restrictions on the number of preemptions allowed. All the previous work on the schedulability analysis of such systems either have exponential complexity, or allow unbounded number of preemptions and are usually based on heuristics. In this paper we present the exact necessary and sufficient conditions under EDF, for the schedulability of such a collection of code blocks in a non-preemptive environment, and give efficient algorithms for testing them. We validate our analytical results with experiments and show that the schedulability analysis problem in such systems can be exactly and efficiently solved in practice.

We present an analytical method to evaluate embedded network packet processor architectures, and to explore their design space. Our approach is in contrast to those based on simulation, which tend to be infeasible when the design space is very large. We illustrate the feasibility of our method using a detailed case study.

The schedulability analysis problem for many realistic task models is intractable. Therefore, known algorithms either have exponential complexity or at best can be solved in pseudo-polynomial time, thereby restricting application of the concerned models to a large extent. We introduce the notion of "approximate schedulability analysis" and show that if a small amount of "error" (which is specified as an input to the algorithm) can be tolerated in decisions made by the algorithm, then this problem can be solved in polynomial time. Our algorithms are analogous to fully polynomial time approximation schemes in the context of optimization problems. We show that this concept of approximate schedulability analysis is fairly general and can be applied to any task model which satisfies certain "task-independence" assumptions. Lastly, we substantiate our theoretical results with experimental evidence and clearly show tradeoffs between running time of the schedulability analysis and the error incurred for various values of the input error parameter.

This paper establishes a link between three areas, namely Max-Plus Linear System Theory as used for dealing with certain classes of discrete event systems, Network Calculus for establishing time bounds in communication networks, and real-time scheduling. In particular, it is shown that important results from scheduling theory can be easily derived and unified using Max-Plus Algebra. Based on the proposed network theory for real-time systems, the first polynomial algorithm for the feasibility analysis and optimal priority assignment for a general task model is derived.