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.

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

The papers in this special section focus on embedded and networked systems for intelligent vehicles and robots. Embedded and networked systems for intelligent vehicles and robots are expected to have a significant economic, societal, and technological impact on industrial and automotive applications. Among the aspects that will benefit from these technologies the first one is safety, thanks to the reduction of accidents caused by human errors. Another positive effect is expected on sustainability, thanks to the increase in transport systems efficiency. Comfort and inclusiveness will be also improved, ensuring users’ freedom for other activities and “mobility for all.” Logistics and factory automation are among the main areas that will take advantages from intelligent vehicles and robots, that are expected to play a key role in Industry 4.0 scenarios, the so-called fourth industrial revolution, where intelligent vehicles and industrial robots will move and operate autonomously and cooperatively. Such a revolution has many key enabling technologies, such as, networked sensors, actuators, and embedded computing and control platforms, that will be distributed on-board the vehicle/robot. The contribution of artificial intelligence and deep learning computing platforms is also emerging to achieve full intelligent autonomous mobility of vehicles and robots.

In response to the tremendous growth of the Internet, towards what we call the Internet of Things (IoT), there is a need to move from costly, high-time-to-market specific-purpose hardware to flexible, low-time-to-market general-purpose devices for packet processing. Among several such devices, GPUs have attracted attention in the past, mainly because the high computing demand of packet processing applications can, potentially, be satisfied by these throughput-oriented machines. However, another important aspect of such applications is the packet latency which, if not handled carefully, will overshadow the throughput benefits. Unfortunately, until now, this aspect has been mostly ignored. To address this issue, we propose a method that considers the variable bit rate of the traffic and, depending on the current rate, minimizes the latency, while meeting the rate demand. We propose a persistent kernel based software architecture to overcome the challenges inherent in GPU implementation like kernel invocation overhead, CPU-GPU communication and memory access overhead. We have chosen packet classification as the packet processing application to demonstrate our technique. Using the proposed approach, we are able to reduce the packet latency on average by a factor of 3.5, compared to the state-of-the-art solutions, without any packet drop.

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

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

We propose an analytical framework for probabilistic timing analysis of the event-triggered Dynamic segment of the FlexRay communication protocol. Specifically, our framework computes the Deadline Miss Ratio of each message. The core problem is formulated as a Mixed Integer Linear Program (MILP). Given the intractability of the problem, we also propose several techniques that help to mitigate the running times of our tool. This includes the re-engineering of the problem to run it on GPUs as well as reformulating the MILP itself. Most importantly, we also show how our framework can handle correlations between the queuing events of messages. This is challenging because one cannot apply the convolution operator in the same way as in the case of independent queuing events.

In this paper we address the problem of computing the probability response time distribution of periodic tasks scheduled on a uniprocessor systems. Our framework assumes an arbitrary non-idling preemptive scheduling policy that may be either a fixed-priority scheduler (such as Rate Monotonic - RM) or a dynamic-priority scheduler (such as Earliest Deadline First - EDF). At the same time, our framework can handle arbitrary execution time distributions arbitrary deadlines providing numerically accurate results. We also show how the framework can be extended to compute the correlation coefficients between the response times of different jobs by performing the joint analysis.

Modern mobile devices provide ultra-high resolutions in their display panels. This imposes ever increasing workload on the GPU leading to high power consumption and shortened battery life. In this paper, we first show that resolution scaling leads to significant power savings. Second, we propose a perception-aware adaptive scheme that sets the resolution during game play. We exploit the fact that game players are often willing to trade quality for longer battery life. Our scheme uses decision theory, where the predicted user perception is combined with a novel asymmetric loss function that encodes users' alterations in their willingness to save power.

Ethernet AVB is being actively considered by the automotive industry as a candidate for in-vehicle communication backbone. However, several questions pertaining to schedulability of hard real-time messages transmitted via such a switch remain unanswered. In this paper, we attempt to fill this void. We derive equations to perform worst-case response time analysis on Ethernet AVB switches by considering its credit-based shaping algorithm. Also, we propose several approaches to reduce the pessimism in the analysis to provide tighter bounds.

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

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 propose an analytical framework for probabilistic timing analysis of the event-triggered Dynamic segment of the Flex Ray communication protocol. Specifically, our framework computes the Deadline Miss Ratios of each message. The core problem is formulated as a Mixed Integer Linear Program (MILP). Given the intractability of the problem, we also propose several techniques that help to mitigate the running times of our tool. This includes the re-engineering of the problem to run it on GPUs as well as re-formulating the MILP itself.

Variants of the 0-1 knapsack problem manifest themselves at the core of several system-level optimization problems. The running times of such system-level optimization techniques are adversely affected because the knapsack problem is NP-hard. In this paper, we propose a new GPU-based approach to accelerate the multiple-choice knapsack problem, which is a general version of the 0-1 knapsack problem. Apart from exploiting the parallelism offered by the GPUs, we also employ a variety of GPU-specific optimizations to further accelerate the running times of the knapsack problem. Moreover, our technique is scalable in the sense that even when running large instances of the multiple-choice knapsack problems, we can efficiently utilize the GPU compute resources and memory bandwidth to achieve significant speedups.

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

FlexRay, developed by a consortium of over hundred automotive companies, is a real-time communication protocol for automotive networks. In this paper, we propose a new approach for timing analysis of the event-triggered component of FlexRay, known as the dynamic segment. Our technique accounts for the fact that the FlexRay standard allows slot multiplexing, i.e., the same priority can be assigned to more than one message. Existing techniques have either ignored slot multiplexing in their analysis or made simplifying assumptions that severely limit achieving high bandwidth utilization. Moreover, we show that our technique returns less pessimistic results compared to previously known techniques even in the case where slot multiplexing is ignored.

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.

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.

FlexRay is gaining wide acceptance as the next generation bus protocol for automotive networks. This has led to tremendous research interest in techniques for scheduling signals, which are generated by real-time applications, on the FlexRay bus. Signals are first packed together into frames at the application-level and the frames are then transmitted over the bus. To ensure reliability of frames in the presence of faults, frames must be retransmitted over the bus but this comes at the cost of higher bandwidth utilization. To address this issue, in this paper, we propose a novel frame packing method for FlexRay bus. Our method computes the required number of retransmissions of frames that ensures the specified reliability goal. The proposed frame packing method also ensures that none of the signals violates its deadline and that the desired reliability goal for guaranteeing fault-tolerance is met at the minimum bandwidth cost. Extensive experiments on synthetic as well as a industrial case study demonstrate the benefits of our method.

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.

FlexRay has been widely accepted as the next generation bus protocol for automotive networks. This has led to tremendous research interest in techniques for scheduling messages on the FlexRay bus, in order to meet the hard real-time deadlines of the automotive applications. However, these techniques do not generate reliable schedules in the sense that they do not provide any performance guarantees in the presence of faults. In this work, we will present a framework for generating fault-tolerant message schedules on the time-triggered (static) segment of the FlexRay bus. We provide formal guarantees that the generated fault-tolerant schedules achieve the reliability goal even in the presence of transient and intermittent faults. Moreover, our technique minimizes the required number of re-transmissions of the messages in order to achieve such fault tolerant schedules, thereby, optimizing the bandwidth utilization. Towards this, we formulate the optimization problem in Constraint Logic Programming (CLP), which returns optimal results. However, this procedure is computationally intensive and hence, we also propose an efficient heuristic. The heuristic guarantees the reliability of the constructed schedules but might be sub-optimal with respect to bandwidth utilization. Extensive experiments run on synthetic test cases and real-life case studies illustrate that the heuristic performs extremely well. The experiments also establish that our heuristic scales significantly better than the CLP formulation.

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.

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.

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.

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.