This article tackles the problem of optimal placement of complex real-time embedded applications on heterogeneous platforms. Applications are composed of directed acyclic graphs of tasks, with each directed-acyclic-graph (DAG) having a minimum inter-arrival period for its activation requests and an end-to-end deadline within which all of the computations need to terminate since each activation. The platforms of interest are heterogeneous power-aware multi-core platforms with Dynamic Voltage and Frequency Scaling (DVFS) capabilities, including big.LITTLE Arm architectures and platforms with GPU or FPGA hardware accelerators with Dynamic Partial Reconfiguration capabilities. Tasks can be deployed on CPUs using partitioned EDF-based scheduling. Additionally, some of the tasks may have an alternate implementation available for one of the accelerators on the target platform, which are assumed to serve requests in non-preemptive FIFO order. The system can be optimized by minimizing power consumption, respecting precise timing constraints, maximizing the applications’ slack, respecting given power consumption constraints, or even a combination of these, in a multi-objective formulation. We propose an off-line optimization of the mentioned problem based on mixed-integer quadratic constraint programming (MIQCP). The optimization provides the DVFS configuration of all the CPUs (or accelerators) capable of frequency switching and the placement to be followed by each task in the DAGs, including the software-vs.-hardware implementation choice for tasks that can be hardware accelerated. For relatively big problems, we developed heuristic solvers capable of providing suboptimal solutions in a significantly reduced time compared to the MIQCP strategy, thus widening the applicability of the proposed framework. We validate the approach by running a set of randomly generated DAGs on Linux under SCHED_DEADLINE, deployed onto two real boards, one with Arm big.LITTLE architecture, the other with FPGA acceleration, verifying that the experimental runs meet the theoretical expectations in terms of timing and power optimization goals.

Abstract We present , a framework for the integration of modern verification tools in the context of AUTOSAR, a widely-used open standard for the development of automotive software systems. Our framework enables the automatic end-to-end verification of system-level properties using a compositional approach. It combines software model checking techniques for the verification of software components at the code level with a contract-based analysis for verifying their correct composition. In this paper, we present the tool through its application on a representative automotive case study, discussing the main functionalities provided and the results obtained.

Modern automotive applications are increasingly characterized by the need to transfer massive amounts of data in a predictable and deterministic way, possibly leveraging the Logical Execution Time (LET) paradigm. However, current proposals for LET communications are limited to core-commanded data transfers, which may result in large delays for data-intensive systems. To address this issue, we explore the use of Direct Memory Access (DMA) to handle LET communication with improved parallelism. Each DMA transfer operates on a contiguous memory area, thus calling for an optimized memory mapping to maximize performance. Modern DMA engines offer also advanced configurations, such as linked-lists of data transfers, which may provide more flexibility at the expenses of an increased (initial) programming overhead. Leveraging all such features of DMA engines, we propose a set of designs and protocols for LET communications with trade-offs between latency and space requirements. For each option we present the formulation to compute the optimal scheduling and memory allocation solution as a mixed-integer linear programming problem. Experimental results show the feasibility of the approach and a comparison of the solutions obtained using the proposed methods, showing a considerable improvement in terms of data acquisition latency when compared to LET communication without DMA.

Analysis models, technologies and tools are extensively used in the automotive domain to validate and optimize the design and implementation of SW systems. This is especially true for modern systems including advanced autonomous (and complex) features. The range of analysis methods that can be applied is extremely wide and goes from functional correctness to functional safety to timing (and schedulability), security, and possibly even more. The AUTOSAR automotive standard has been defined with the purpose of standardizing the SW architecture of automotive systems and enable the construction of systems by composing SW components that are portable and abstract with respect to the underlying HW/SW platform. However, AUTOSAR was originally developed with portability of code in mind, and even if it quickly evolved to include a system-level modeling language (with its metamodel) and later extensions to deal with the needs of analysis methods (and tools), it is hardly comprehensive and still affected by several omissions and limitations. To fix the limitations with respect to timing and schedulability analysis Bosch developed the Amalthea (later App4MC) metamodel and tools. In Huawei, a more general (and ambitious) approach was undertaken to support not only timing analysis, but also model checking (or other types of formal verification), safety analysis and even design optimization. The approach is based on the concepts of a unified (modular) metamodel and a framework based on Eclipse to integrate analysis methods and tools. In this paper we describe the framework and the results obtained with respect to the objectives of functional verification and timing analysis.

The Logical Execution Time (LET) paradigm is increasingly used to achieve predictable communications in modern multicore automotive applications. Direct Memory Access (DMA) engines can perform the data copies that are needed in a LET implementation on behalf of the cores with improved parallelism and reduced overheads. However, each DMA transfer operates on contiguous memory areas, and the performance is strongly dependent on the allocation in memory of the variables to be copied. This paper proposes a protocol to perform LET communications with a DMA and presents an optimal memory allocation scheme and scheduling using a mixed-integer linear programming formulation. Experimental results are reported to compare the performance of different communication approaches.

The weakly hard real-time model is an abstraction for applications, including control systems, that can tolerate occasional deadline misses, but can also be compromised if a sufficiently high number of late terminations occur in a given time window. The weakly hard model allows us to constrain the maximum number of acceptable missed deadlines in any set of consecutive task executions. A big challenge for weakly hard systems is to provide a schedulability analysis that applies to a general task model, while avoiding excessive pessimism. In this work, we develop a general weakly hard analysis based on a Mixed Integer Linear Programming (MILP) formulation. The analysis applies to constrained-deadline periodic real-time systems scheduled with fixed priority and no knowledge of the task activation offsets, while allowing for activation jitter. Our analysis considers two common policies for handling missed deadlines, i.e., (i) letting the job continue until completion or (ii) killing its execution immediately. For this policy, ours is the first and only m-k analysis currently available. Experiments conducted on randomly generated task sets show the applicability and accuracy of the proposed technique as well as the improvements with respect to competing techniques.

Predictable execution models have been proposed over the years to achieve contention-free execution of real-time tasks by preloading data into dedicated local memories. In this way, memory access delays can be hidden by delegating a DMA engine to perform memory transfers in parallel with processor execution. Nevertheless, state-of-the-art protocols introduce additional blocking due to priority inversion, which may severely penalize latency-sensitive applications and even worsen the system schedulability with respect to the use of classical scheduling schemes. This paper proposes a new protocol that allows hiding memory transfer delays while reducing priority inversion, thus favoring the schedulability of latency-sensitive tasks. The corresponding analysis is formulated as an optimization problem. Experimental results show the advantages of the proposed protocol against state-of-the-art solutions.

This paper presents a set of sufficient-only, but accurate schedulability tests for fixed-priority scheduling. The tests apply to the general case of scheduling with constrained deadline where tasks can incur in blocking times, be subject to release jitters, activated with fixed offsets, or involved in transactions with other tasks. The proposed tests come in a linear closed-form with a number of conditions polynomial in the number of tasks. All tests are targeted for use when encoding schedulability constraints within Mixed-Integer Linear Programming for the purpose of optimizing real-time systems (e.g., to address task partitioning in a multicore system). The tests are evaluated with a large-scale experimental study based on synthetic workload, revealing a failure rate (with respect to the state-of-the-art reference tests) of less than 1% in average, and at most of 2% in a very small number of limit-case configurations.

The move to multicore systems requires methods and tools to support the designer in the partitioning of functions among the available cores and the definition of the task model. In this paper we present the formulation of a functional partitioning for real-time systems and we provide an optimization method for an efficient implementation of the Logical Execution Time (LET) paradigm, to enforce causality and determinism in the development of time-and safety-critical applications. A novel schedulability analysis for partitioned tasks executing according to the LET paradigm is also provided. Our methods are applied to the industry-size model of the WATERS challenge and compute solutions that easily outperform the initial solution provided.

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

Most works in schedulability analysis theory are based on the assumption that constraints on the performance of the application can be expressed by a very limited set of timing constraints (often simply hard deadlines) on a task model. This model is insufficient to represent a large number of systems in which deadlines can be missed, or in which late task responses affect the performance, but not the correctness of the application. For systems with a possible temporary overload, models like the m-K deadline have been proposed in the past. However, the m-K model has several limitations since it does not consider the state of the system and is largely unaware of the way in which the performance is affected by deadline misses (except for critical failures). In this paper, we present a state-based representation of the evolution of a system with respect to each deadline hit or miss event. Our representation is much more general (while hopefully concise enough) to represent the evolution in time of the performance of time-sensitive systems with possible time overloads. We provide the theoretical foundations for our model and also show an application to a simple system to give examples of the state representations and their use.

Next generation automotive applications require support for safe, predictable, and deterministic execution. The Logical Execution Time (LET) model has been introduced to improve the predictability and correctness of time-critical applications. The advent of multicore architectures, together with the need to ensure time predictability despite the complex memory hierarchy and the hardware resources shared by the cores, is an additional motivation for the use of the LET paradigm in conjunction with a suitable scheduling and memory access model. In this paper, we show how an implementation of the LET model on actual multicore platforms for automotive systems brings the potential to improve time determinism at the price of a modicum run-time overhead. Multiple implementation options are discussed using the automotive AUTOSAR model and operating system standard, and a realistic application defined by Bosch for the 2017 WATERS challenge. Experimental data of executions on the Infineon Aurix platform show the feasibility of the proposed approach. The paper also provides a discussion on further implementation optimizations and other issues related to the general problem of memory-aware analysis of automotive applications on multicores.

Engine control systems include computational activities that are triggered at predetermined angular values of the crankshaft, and therefore generate a workload that tends to increase with the engine speed. To cope with overload conditions, a common practice adopted by the automotive industry is to design such angular tasks with a set of modes that switch at given rotation speeds to adapt the computational demand. This paper presents an exact response time analysis for engine control applications consisting of periodic and engine-triggered tasks scheduled by fixed priority. The proposed analysis explicitly takes into account the physical constraints of the considered systems and is based on the derivation of dominant speeds, which are particular engine speeds that are proved to determine the worst-case behavior of engine-triggered tasks from a timing perspective. Experimental results are finally reported to validate the proposed approach and compare it against an existing sufficient test.

Engine control applications include functions that need to be executed at specific rotation angles of the crankshaft. The tasks performing these functions are activated at variable rates and are programmed to be adaptive with respect to the rotation speed of the engine to avoid overloading the CPU. Simplified control implementations are used at high speeds; for example, reducing the number of fuel injections or the complexity of the computations. Such different control implementations define execution modes with different execution times for different ranges of the rotation speed. The selection of the switching speeds for the operating modes of such tasks is an optimization problem, consisting in determining the optimal transition speeds that maximize the engine performance while guaranteeing schedulability. This article presents three methods for tackling such an optimization problem under a set of assumptions about the performance metrics: two heuristics and a branch and bound method that guarantees finding the optimal solution within a given speed granularity. In addition, a simple method to compute a performance upper bound is presented. The approach and the hypothesis are validated using a Simulink model of the engine and the computational tasks, considering the engine efficiency and the production of pollutants (NO 2 ) as metrics of interest. Simulation experiments show that the performance of proposed heuristics is quite close to that of the upper bound and the optimum within a finite granularity.

This paper presents the work performed at (removed for blind review) to automate the integration of virtual systems development (VSD) and simulation in its embedded software development process. The approach is based on a combination of metamodels, model transformations and design patterns, the SysML standard and the use of the open source Eclipse framework. The purpose is to derive all the design refinements, including the production code and the code used for simulation and verification from a single set of SysML models. Stereotypes and model transformations are defined to allow the integration of automatically generated interfaces and manually produced code implementing virtual platforms for the simulation of HW/SW heterogeneous systems on the SIMICS platform.

This paper presents a method to check data secure flow in security annotated AUTOSAR models. The approach is based on information flow analysis and abstract interpretation. The analysis computes the lowest security level of data sent on a communication, according to the annotations in the model and the code of runnables. An abstract interpreter executes runnables on abstract domains that abstract from real values and consider only data dependency levels. Data secure flow is verified if data sent on a communication always satisfy the security annotation in the model. The work has been developed in the EU project Safure, where modeling extensions to AUTOSAR have been proposed to improve security in automotive communications.

The hard deadline model is very popular in real-time research, but is representative or applicable to a small number of systems. Many applications, including control systems, are capable of tolerating occasional deadline misses, but are seriously compromised by a repeating pattern of late terminations. The weakly hard real-time model tries to capture these requirements by analyzing the conditions that guarantee that a maximum number of deadlines can be possibly missed in any set of consecutive activations. We provide a new weakly hard schedulability analysis method that applies to constrained-deadline periodic real-time systems scheduled with fixed priority and without knowledge of the task activation offsets. The analysis is based on a Mixed Integer Linear Programming (MILP) problem formulation; it is very general and can be adapted to include the consideration of resource sharing and activation jitter. A set of experiments conducted on an automotive engine control application and randomly generated tasksets show the applicability and accuracy of the proposed technique.

The new CAN-FD standard for automotive communication provides support for real-time predictability at an increased rate and with a larger payload than the existing CAN standard. The adoption of CAN-FD requires the migration and possibly the redesign of the existing message sets to exploit the features of the protocol, by repacking the application signals in the new larger frames. Previous works provided algorithms that consider timing constraints and try to reduce the required bandwidth. The state of the art solutions are however based on two-step heuristics. A single-step formulation, with a suitable set of (optional) bound relaxation techniques has the potential to provide better solutions (with lower bus utilization) and also be more easily adapted to the consideration of the constraints and limitations that typically apply to the signal remapping.

This paper presents a master algorithm for co-simulation of hybrid systems using the Functional Mock-up Interface (FMI) standard. Our algorithm introduces step revision to achieve an accurate and precise handling of mixtures of continuous-time and discrete-event signals, particularly in the situation where components are unable to accurately extrapolate their input. Step revision provides an efficient means to respect the error bounds of numerical approximation algorithms that operate inside co-simulated FMUs. We first explain the most fundamental issues associated with hybrid co-simulation and analyze them in the framework of FMI. We demonstrate the necessity for step revision to address some of these issues and formally describe a master algorithm that supports it. Finally, we present experimental results obtained through our reference implementation that is part of our publicly available open-source toolchain called FIDE.

The sampling periods of real-time embedded control functions have a significant impact on control performance and system schedulability. Exploring period assignment for optimizing control performance while meeting schedulability constraints is very challenging, in particular for distributed systems where control loops share a network of computation and communication resources. In this work, we propose an efficient approach that approximates the performance of each control loop in the system with a piecewise linear function of its sampling period and end-to-end delay, and then optimizes the periods of tasks and messages by exploring the linear partitions of the approximated functions and solving a series of geometric programming (GP) formulations. Experiments on sample control models, an automotive industrial case study and a set of synthetic examples demonstrate the effectiveness and efficiency of our approach.

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

Engine control applications require the execution of tasks activated in relation to specific system variables, such as the crankshaft rotation angle. To prevent possible overload conditions at high rotation speeds, such tasks are designed to vary their functionality (hence their computational requirements) for different speed ranges. Modeling and analyzing such a type of tasks poses new research challenges in the schedulability analysis that are now being addressed in the real-time literature. This paper advances the state of the art by presenting a method for computing the exact worst-case interference of such adaptive variable-rate tasks under fixed priority scheduling, enabling a tight analysis and design of engine control applications.

Model-Based Design is widely adopted in control domains for the early validation of systems properties using simulation or formal verification and the possibility of automatic generation of code. Most tools used in the industrial practice allow for the representation of the controller functionality abstracted from the implementation details. These models may be inaccurate in those cases in which computation and communication delays affect the performance of the controls. To address this problem, we propose a Model-Driven approach in which a Simulink functional model of controls is matched to a model of the execution platform through a mapping model, representing the implementation as a set of tasks and messages. The platform and the implementation are modeled in SysM-L/MARTE and are used to automatically generate a new Simulink model with an additional set of blocks representing the execution time of the tasks running under the control of a selected scheduler. Acceleo and QVTo model-to-text and model-to-model standard transformation languages are used to automatically generate the intermediate models, the task and scheduler blocks.

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

No abstract available.

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

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

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

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

Models are used in control domains for early validation of system properties, using simulation or formal verification, and for the automatic generation of a software implementation. We propose an approach in which a functional model of the controls is matched to a model of the execution platform through an intermediate mapping model, that represents the software tasks and communication messages. The functional model is (partly) developed in Simulink and code is generated for each subsystem. Next, an abstract view of the functional model is imported in SysML. Using SysML, a model of the execution platform is created, and an implementation of the subsystems as a set of tasks and messages is defined and evaluated. The M2T Acceleo tool processes the mapping model and generates the Orocos-compliant task code executing the C/C++ functions generated from Simulink, and the inter-task communication. This paper outlines the proposed flow and provides the description of a robotic car testbench used to show the application of the methodology. The testbench has enough functional complexity and a distributed implementation to justify the creation of architecture models, while requiring a moderate cost and effort for its construction by the interested researchers.

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

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

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

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

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

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

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

Modeling languages and tools, including Simulink, Scicos, SysML and the Eclipse Modeling Framework (EMF), bring the promise of an improved quality and productivity in the development of embedded systems and software. Unfortunately, none of these modeling languages, taken individually, is capable of fulfilling all the needs in the development of complex distributed embedded applications, from the modeling, analysis and validation stages to the automatic generation of the implementation. Overall, their strengths and weaknesses are somewhat complementary and an integrated approach could be the most promising solution. In this paper, we present a framework for integrated code generation in complex real-time distributed systems, where MBD approaches are used for the analysis and the generation of the functional (or behavioral) part, and MDA approaches (SysML/EMF) are used for modeling the execution platform, the task model and the deployment of functions onto the platform resources. This paper presents a meta-model for the description of execution platforms and an open-source code generation framework, based on the selected mapping of the functional components on the chosen platform.

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

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

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.

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

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

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

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

Cost pressure, flexibility, extensibility and the need for coping with increased functional complexity are changing the fundamental paradigms for the definition of automotive and aeronautics architectures. Traditional designs are based on the concept of aFederated Architecturein which integrated hardware/software components [Electronic Control Units (ECUs)] realize mostly independent or loosely interconnected functions. These components are connected by bus and cooperate by exchanging messages. This paradigm is now being replaced by theIntegrated Architecture,—the concept comes from Integrated Modular Avionics (IMA) introduced by the avionics community (see C. B. Watkins and R. Walter, “Transitioning from federated avionics architectures to integrated modular avionics,” in Proc. 26th Digital Avionics Syst. Conf., Oct. 2007) but it is certainly general and applicable to other fields and in particular, automotive—in which software components can be supplied from multiple sources, integrated on the same hardware platform or physically distributed and possibly moved from one CPU to another without loss of functional and time correctness and providing a guaranteed level of reliability. This shift will decouple software design from the hardware platform design and provide opportunities for the optimization of the architecture configuration, increased extensibility, flexibility and modularity. However, the integration of software components in a distributed system realizing a complex functional behavior and characterized by safety, time and reliability constraints requires a much tighter control on the component model and its semantics, new methods and tools for analyzing the results of the composition, whether by simulation or formal methods, and methods for exploring the architecture solution space and optimizing the configuration. We provide a general overview of existing challenges and possible solutions to the design and analysis problem,with special focus on the automotive domain. The development of such methods and tools must necessarily consider compatibility with existing modeling languages and standards, including UML, AUTOSAR and synchronous reactive models, on which the widely used commercial products Simulink and SCADE are based.

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

Model-based design methodologies are gaining attention in the industrial community because of the possibility of early and efficient functional validation and formal verification of properties at high levels of abstraction. The advantages of validating the design using high-level models can be lost entirely if errors and modifications that are not back-annotated to the higher abstraction levels are introduced when refining the design to lower levels of abstraction. To overcome this problem and to reduce design time, automatic synthesis has been used for the refinement process from Register Transfer Languages (RTLs) to logic gates for digital circuit design. This approach guarantees (assuming that the synthesis algorithms are correctly implemented) that the semantic of the RTL description is semantically equivalent to the semantic of the logic circuit. Automatic code generation is similar in intent and applicability. However, the software implementation of the abstract model must make efficient use of the platform resources that may not reflect all the assumptions of the code generation algorithms. The implementation of communication in a synchronous reactive model requires buffering and access procedures at the kernel level. In previous work, we obtained tight bounds on the size of communication buffers to maintain semantic equivalence. In realtime systems, however, because of the longer execution times of access procedures, an implementation with minimum buffer size may lead to the violation of deadlines. To solve this problem, we propose a Mixed Integer Linear Programming (MILP)-based optimization approach that provides the minimum memory implementation of a set of communication channels while guaranteeing that the task deadline constraints are met. The analysis is validated by an OSEK/VDX-compliant implementation that provides an estimate of actual runtime overheads. The approach is applied to a set of task graphs and an automotive case study.

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

We consider a set of control tasks that must be executed on distributed platforms so that end-to-end latencies are within deadlines. We investigate how to allocate tasks to nodes, pack signals to messages, allocate messages to buses, and assign priorities to tasks and messages, so that the design is extensible and robust with respect to changes in task requirements. We adopt a notion of extensibility metric that measures how much the execution times of tasks can be increased without violating end-to-end deadlines. We optimize the task and message design with respect to this metric by adopting a mathematical programming front-end followed by postprocessing heuristics. The proposed algorithm as applied to industrial strength test cases shows its effectiveness in optimizing extensibility and a marked improvement in running time with respect to an approach based on randomized optimization.

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

The adoption of AUTOSAR in the development of automotive electronics can increase the portability and reuse of functional components. Inside each component, the behavior is represented by a set of runnables, defining reactions executed in response to an event or periodic computations. The implementation of AUTOSAR runnables in a concurrent program executing as a set of tasks reveals several issues and trade-offs because of the need to protect communication and state variables and to ensure time determinism. We discuss some of these tradeoffs and options and outline a problem formulation that can be used to compute the solution with minimum memory requirements executing within the deadlines.

FlexRay [9] is an automotive standard for high-speed and reliable communication that is being widely deployed for next generation cars. The protocol has powerful error-detection mechanisms, but its error-management scheme forces a corrupted frame to be dropped without any notification to the transmitter. In this paper, we analyze the feasibility of and propose an optimization approach for an application-level acknowledgement and retransmission scheme for which transmission time is allocated on top of an existing schedule. We formulate the problem as a Mixed Integer Linear Program. The optimization is comprised of two stages. The first stage optimizes a fault tolerance metric; the second improves scheduling by minimizing the latencies of the acknowledgement and retransmission messages. We demonstrate the effectiveness of our approach on a case study based on an experimental vehicle designed at General Motors.

We consider a set of control tasks that must be executed on distributed platforms so that end-to-end latencies are within deadlines. We investigate how to allocate tasks to nodes, pack signals to messages, allocate messages to buses, and assign priorities to tasks and messages, so that the design is robust with respect to changes in task requirements. The notion of extensibility is used to measure robustness. The extensibility metric measures how much the execution times of tasks can be increased without violating end-to-end deadlines. We optimize this metric by adopting a mathematical programming front-end followed by post-processing heuristics. The proposed algorithm as applied to industrial strength test cases shows its effectiveness in optimizing extensibility and a marked improvement in running time with respect to an approach based on randomized optimization.

This special section on automotive systems collects four of the presentations given on a special day at the DATE 08 Conference, held in Munich, Germany, in April 2008.

Model-based development of embedded applications is a major trend in industry because of the possibility of early validation and verification of properties by simulation or formal methods. Synchronous reactive models are characterized by a formally specified semantics, which avoids ambiguities in the interpretation of the model, and by the availability of efficient code generation tools, which help increase productivity. The validity of the simulation and/or verification results on the model is retained only if the generated code is guaranteed to preserve model semantics. At the same time, the implementation must make efficient use of the execution platform resources. One of the essential issues for efficient implementation is the use of communication buffers that exploit the multirate behavior of the components. In most embedded devices, RAM memory is scarce and buffer size should be kept at a minimum. We present an approach to buffer size optimization by using timing information about the components. The approach was applied to an automotive case study, showing for the specific case an improvement of at least 7.5% with respect to previous methods.

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

This section will provide insight into new developments and advances in electronics automotive architectures. The design of innovative chip architectures, new upcoming standards for high-bandwidth and deterministic communication (FlexRay) and sensors are the domains of interest, with emphasis on reliability and support for advanced active safety functions.

Automotive systems are increasingly distributed and complex. Reduced time-to-market, cost and safety concerns require advance validation of the integrated systems and its components, from the functional, timing, and reliability standpoints. In particular, function correctness and performance may depend on communication and computation delays imposed by the selected architecture platform. Hence, the need for methods and tools capable of predicting the system-level timing behaviour (latencies and jitter), resulting from the HW platform selection, the synchronization between tasks and messages, and also from the synchronization and queuing policies of the middleware and RTOS levels. In this paper, we review methods and tools for the evaluation of the function performance and its timing correctness by simulation or by worst case static analysis.

System-level integration requires an overall understanding of the interplay of the sub-systems to enable component-based development with portability, reconfigurability and extensibility, together with guaranteed reliability and performance levels. Integration by simple interfaces and plug-and-play of sub-systems, which is the main objective of AUTOSAR, requires solving essential technical problems. We discuss to what degree the existing AUTOSAR standard can support the development of safety- and time-critical software and what is required to move toward the desirable goal of timing isolation when integrating multiple applications into the same execution platform.

Start of the above-titled section of the conference proceedings record.

A fundamental asset of a model-based development process is the capability of providing an automatic implementation of the model that preserves its semantics and, at the same time, makes an efficient use of the resources of the execution platform. The implementation of communication between functional blocks in a synchronous reactive model requires buffering schemes and access procedures at the kernel level. Previous research has provided two competing proposals for the sizing of the communication buffer. We demonstrate how it is possible to leverage task timing information to obtain tighter bounds for the case of sporadic tasks or periodic tasks with unknown activation phase, and we propose an approach that applies to a more general model. Furthermore, we provide the description of the data structures and constant-time access procedures for writer and reader tasks, and an implementation compliant with the OSEK OS standard.

Synchronous systems offer a clean semantics and an easy verification path at the expense of often inefficient implementations. Capturing design specifications as synchronous models and then implementing the specifications in a less restrictive platform allow to address a much larger design space. The key issue in this approach is maintaining semantic equivalence between the synchronous model and its implementation. We address this problem by showing how to map a synchronous model onto a loosely time-triggered architecture that is fairly straightforward to implement as it does not require global synchronization or blocking communication. We show how to maintain semantic equivalence between specification and implementation using an intermediate model (similar to a Kahn process network but with finite queues) that helps in defining the transformation. Performance of the semantic preserving implementation is studied for the general case as well as for a few special cases.

Automatic generation of a controller implementation from a synchronous reactive model is among the best practices for software development in the automotive and aeronautics industry, because of the possibility of simulation, model checking, and error-free implementation. This paper discusses an algorithm for optimizing the single-processor multitask implementation of Simulink models with real-time execution constraints, derived from the sampling rates of the functional blocks. Existing code generation tools enforce the addition of extra buffering and latencies whenever there is a rate transition among functional blocks. This work shows how timing analysis can be used to find the cases in which additional buffering and latency can be avoided, improving the space and time performance of the application. The proposed search algorithm allows finding a solution with reduced and possibly minimal use of buffering even for very high values of processor utilization.

The complexity and physical distribution of modern active-safety automotive applications requires the use of distributed architectures. These architectures consist of multiple electronic control units (ECUs) connected with standardized buses. The most common configuration features periodic activation of tasks and messages coupled with run-time priority-based scheduling. The correct deployment of applications on such architectures requires end-to-end latency deadlines to be met. This is challenging since deadlines must be enforced across a set of ECUs and buses, each of which supports multiple functionality. The need for accommodating legacy tasks and messages further complicates the scenario.

This paper outlines a methodology based on virtual platforms and timing analysis to perform the exploration and selection of automotive architecture solutions. The analysis provides a quantitative evaluation of architecture options with respect to para-functional metrics. The satisfaction of deadline constraints and the optimization with respect to latency on end-to-end computations is considered. In addition, we discuss to what degree existing standards, including OSEK and AUTOSAR and model-based development practices can support the development of time predictable software and what is required to move toward the desirable goal of timing isolation when integrating multiple applications into the same execution platform. Finally, the paper provides a quick glance at recent results in the the optimization of the software architecture for complex distributed systems with respect to worst case timing behavior.

Architecture design is a critical stage of the electronics/controls/software (ECS)-based vehicle design flow. Traditional approaches relying on component-level design and analysis are no longer effective as they do not always allow for the quantitative evaluation of properties arising from the composition of subsystems. This paper presents a system level architecture design methodology that is supported by tools and methods for the quantitative evaluation of key metrics of interest related to timing, dependability and cost. An example of its application to a by-wire system case study is presented, and the challenges faced in its application in the context of the actual development process are discussed

Modern automotive architectures support the execution of distributed safety- and time-critical functions on a complex networked system with several buses and tens of ECUs. Schedulability theory allows the analysis of the worst case end-to-end latencies and the evaluation of the possible architecture configurations options with respect to timing constraints. The paper presents an optimization framework, based on an ILP formulation of the problem, to select the communication and synchronization model that leverages the trade-offs between the purely periodic and the precedence constrained data-driven activation models to meet the latency and jitter requirements of the application. The authors demonstrate its effectiveness by optimizing a complex automotive architecture

We address the problem of mapping a set of processes which communicate synchronously on a distributed platform. The Time Triggered Architecture (TTA) proposed by Kopetz for the communication mechanism of a distributed platform offers a direct mapping that would preserve the semantics of the specification. However, its exact implementation may, at times, be problematic as it requires the distributed platform to have the clocks of its components perfectly synchronized. We propose as implementation architecture a relaxation of TTA called Loosely Time-Triggered Architecture (LTTA), in which computing units perform writes into and reads from the communication medium independently, triggered by local, quasi-periodic but non synchronized, clocks. LTTA offers some of the advantages of TTA with lower hardware cost and greater flexibility. So far LTTA was studied for single directional two-users communications over an LTT bus. General topology was not studied. In this paper we propose a design flow that ensures semantics preservation for an LTT communication network with arbitrary topology. Key elements are two new protocols for clock regeneration and predictive traffic shaping. Our approach relies on a mathematical Model of Communication (MoC) that we describe in detail.

The availability of programmable hardware devices with high density of logic elements and the possibility of implementing CPUs (called softcores) using a fraction of the FPGA area offers additional flexibility for the implementation of embedded applications with real-time constraints. When implementing functions on such devices, designers can choose between hardware and software. Also, the designer can select the number of CPUs that must be created to best support the execution of the real-time software. In this paper, we define a design optimization procedure for hard real-time systems, in which each functional block can be implemented in HW, using the logic elements available on the FPGA, or in SW, by means of a real-time task executed by a softcore. The optimizer allocates the functions and the softcores such that the HW implemented part is mapped within the area constraints and the software part is allocated so that schedulability can be guaranteed. When feasible solutions exist, the minimum utilization solution is computed

Schedulability theory provides support for the analysis of the worst case latencies in distributed computations when the architecture of the system is known and the communication and synchronization mechanisms have been defined. In the design of complex automotive systems, however, a great benefit of schedulability analysis may come from its use as an aid in the exploration of the software architecture configurations that can best support the target application. We present an optimization algorithm that leverages the trade-offs between the purely periodic and the data-driven activation models to meet the latency requirements of distributed vehicle functions. We demonstrate its effectiveness on a complex automotive architecture

The complexity and physical distribution of modern active safety, chassis and powertrain automotive applications requires the use of distributed architectures. Complex functions designed as networks of function blocks exchanging signal information are deployed onto the physical HW and implemented in a SW architecture consisting of a set of tasks and messages. The typical configuration features priority-based scheduling of tasks and messages and imposes end- to-end deadlines. In this work, we optimize the task placement and the signal to message mapping and we automate the assignment of priorities to tasks and messages in order to meet end-to-end deadline constraints and minimize latencies. This is accomplished by leveraging worst case response time analysis within a mixed integer linear optimization framework. Our approach is applied to an automotive case study to prove its feasibility.

At early stages in the design of real-time embedded applications, the timing attributes of the computational activities are often incompletely specified or subject to changes. Later in the development cycle, schedulability analysis can be used to check the feasibility of the task set. However, the knowledge of the worst-case response times of tasks is often not sufficient to precisely determine the actions that would correct a non-schedulable design. In these situations, sensitivity analysis provides useful information for changing the implementation, by giving a measure of those computation times that must be reduced to achieve feasibility, or those that can be increased in case of a product extension, or providing the range of feasible periods for selecting the proper task activation rates. In this work, we exploit the concept of feasibility region to propose a faster and more concise solution to the sensitivity analysis problem with respect to existing techniques based on binary search. Furthermore, we show how the formalization of other problems in the feasibility domain, such as managing overloads through elastic scheduling, can be extended to the exact analysis

The development of software for complex reactive embedded systems requires automated support for the verification of functional and nonfunctional properties. Currently, a language (or a design methodology) that can provide both at the same time without incurring in excessive inefficiencies is not available and separation of concerns is the solution advocated by many. Most research and commercial languages and tools focus on providing support for the design and validation of functional properties. At a different level, models and theory have been developed for supporting the description of the threads and resources composing the software architecture, and schedulability analysis provides support for the validation of timing constraints. However, the design of the concurrent structure of the application is still done manually. The system designer has to decide the number of threads, their structure and interactions, without the possibility of evaluating the trade-off between different solutions. This paper presents a solution towards what we believe to be a key objective, that is the synthesis of the architecture-level design and the automated logical-to-architectural mapping. Our proposal tries to reduce the overheads and excessive priority inversions of existing solutions that map all functional blocks (or reactions) into a single thread or assign a thread of execution to each action or possibly to each active object. After presenting our algorithm, we compare it with existing solutions and provide a schedulability analysis of the resulting system.

The design phase of any real-time system requires balancing the limited computational resources against the functional requirements and the performance of the application. The optimal design solution can be obtained by solving an optimization problem where the system performance is maximized within the schedulability constraints. In this paper, we provide a procedure that finds the task activation rates maximizing a performance function within the deadline constraints in systems scheduled by fixed priorities. First, we describe the exact feasibility region in the domain of task frequencies. Then, we introduce a procedure that starts by finding an initial solution, and incrementally improves it by using an original branch and bound search, until the global optimum is reached. Experiments show that our algorithm finds the optimal task periods for practical problems with a remarkable speedup, if compared with existing techniques. When the size of the problem makes the global search intractable, the experiments show that the algorithm can still find a high quality solution in the very early steps.

This paper discusses a model-based design flow for requirements in distributed embedded software development. Such requirements are specified using a language similar to linear temporal logic which allows one to reason about time and sequencing. They consist of assertions which must hold for a design, given some assumptions on its environment. They can be checked both during simulation and, at least for a subset, even on the target. The key contribution of the paper is the extension to the embedded software domain of assertion-based verification, and the automated generation of property-checking code in multiple target languages, from simulation, to prototyping, to final production.

HRT-HOOD has methodological strengths that deserve to be preserved in the face of the commercial decline of HOOD technology. The UML (Unified Modeling Language) meta-model, on the other hand, has a level of flexibility that makes it an especially attractive platform to express the specific real-time design minded features of the HRT-HOOD method. The object-oriented connotation of the method that results from mapping HRT-HOOD onto UML raises methodological issues that we deem of interest to the real-time community at large. This paper discusses three such issues in particular: the prevalence of objects over classes in real-time design, with the consequent inversion of the standard object-oriented development paradigm; the need to derive classes "by example", which arises from the demand to allow multiple, yet static, instances of real-time objects initially designed as singleton; the opportunity of reuse-oriented component-based real-time development, which descends from using interfaces instead of classes as the target of associations among objects.

The research on real-time software systems has produced algorithms that allow to effectively schedule system resources while guaranteeing the deadlines of the application and to group tasks in a very short number of non-preemptive sets which require much less RAM memory for stack. Unfortunately, up to now the research focus has been on time guarantees rather than the optimization of RAM usage. Furthermore, these techniques do not apply to multiprocessor architectures which are likely to be widely used in future microcontrollers. This paper presents a fast and simple algorithm for sharing resources in multiprocessor systems, together with an innovative procedure for assigning preemption thresholds to tasks. This allows to guarantee the schedulability of hard real-time task sets while minimizing RAM usage. The experimental part shows the effectiveness of a simulated annealing-based tool that allows to find a near-optimal task allocation. When used in conjunction with our preemption threshold assignment algorithm, our tool further reduces the RAM usage in multiprocessor systems.

This paper addresses the problem of schedu ling reactive real-time tran saction s(task groups) implementing a net work of extend ed Finite State Machines comm unicating asynchronously. Task instances are activated in response to internal and/or external ev ents.The objective is avoiding the loss of events exchanged by the tasks. This sc heduling problem has many similarities with the conventional formulation of real-tim e problems and yet it differs enough to justify a rethinking of the assu mptions an d techniques used to solve the problem. Our iterative solution targets fixed p riority systems and offers a priority assignment scheme together with a sufficiently tight worst-case analysis.

Controller area networks (CANs) are widely used in real-time automobile control and are gaining wider acceptance as a standard for factory automation. This paper discusses the applicability of earliest-deadline-first (EDF) techniques to the scheduling of CAN messages. EDF can guarantee higher network utilization than fixed-priority schemes like deadline- or rate-monotonic (DM, RM), but it is difficult to implement in local area networks or local buses. The reason is the need for updating the deadlines (priorities) at each scheduling round and the limited number of priority levels offered by the arbitration protocol. This deadline encoding problem results in an additional priority inversion factor when considering the schedulability analysis of hard real-time messages. This paper describes an effective deadline encoding method and discusses its implementation and its effects on the guarantee analysis. In spite of a limited processor overhead (less than 5% of CPU time), the proposed EDF implementation allows an increase (up to 20%) in the feasible network workload. This tradeoff will be made more convenient as controller technology evolves.

A typical approach for realizing digital controllers is to synthesize the control law in the continuous-time domain and then to implement it as a set of periodic threads complying with tight temporal constraints. The strict respect of all deadlines can often be obtained only by selecting low activation rates which determine a remarkable performance degradation. On the other hand, many control systems are known to tolerate a certain amount of deadline misses. We realized a software tool which allows to numerically evaluate the quality of the control resulting from the scheduling. The tool has been applied to a robotic case study. Considering a meaningful set of trajectories, we have drawn experimental evidence that the use of soft real-time constraints on the threads leads to significant improvements in the system performance. The performance improvement is more evident if scheduling approaches like resource reservation schemes, able to separate the thread importance from its activation rate, are used.

The problem of scheduling real-time tasks with minimum jitter is particularly important in many control applications; nevertheless, it has rarely been studied in the scientific literature. This paper presents an unconventional scheduling approach for distributed static systems where tasks are periodic and have arbitrary deadlines, precedence, and exclusion constraints. The solution presented in this work not only creates feasible schedules, but also minimizes jitter for periodic tasks. We present a general framework consisting of an abstract architecture model and a general programming model. We show how to design a surprisingly simple and flexible scheduling method based on simulated annealing. Experimental results demonstrate the significant improvement of our algorithm over earliest deadline first and rate monotonic algorithms.

The paper presents a scheme for guaranteeing the scheduling of real-time computations in a distributed environment. The authors propose a process model where only true (local or end-to-end) deadlines need to be specified. They assume all local interactions among processes are based on shared memory communication, protected by priority ceiling semaphores. Remote interactions are client-server blocking communications. The result is both a scheduling policy and a methodology to guarantee the integrated scheduling of processes and network messages. Both processes and messages are scheduled according to a fixed-priority scheme that can easily be implemented on most operating systems and a few network protocols. The procedure that checks the schedulability of the distributed computation against end-to-end deadlines is simple enough to be proposed as a scheme for a dynamic guarantee.

The paper presents a methodology for scheduling real time tasks in embedded systems where the task layout is known at design time and does not change at execution time (static systems) and where the cache miss costs are significant when compared to the normal execution time of the tasks. The scheduling model assumes a time driven dispatching of the application tasks which are ordered in a pre defined sequence. Building such a sequence in a way that is not only efficient but accounts for optimal cache sequencing is the aim of our method. The refinement of the schedule towards an optimal solution is done by simulated annealing techniques. The evaluation of the schedules is done by considering the effects of instruction caching when evaluating the computation time of the tasks.

In this paper, we describe an integrated environment to assist the development of hard real-time applications. It includes an interactive graphic interface which allows the user to describe the application requirements according to three hierarchical levels: the application level, the component level, and the object level. The development model we propose is based on an iterative process in which the real-time scheduling support is considered since the beginning of the design phases. Our graphic environment integrates several tools to analyse, test, and simulate the real-time application under development. In particular, the tools we have implemented are: a Design Tool, to describe the structure of the application, a Schedulability Analyser Tool (SAT), to verify off-line the feasibility of the schedule of a critical task set, a Scheduling Simulator, to test the average behaviour of the application, and a Maximum Execution Time (MET) estimator to bound the worst case duration of each task.

This paper presents a non-conventional scheduling approach for distributed static systems where tasks are periodic and have arbitrary deadlines, precedence, and exclusion constraints. The solution presented in this work not only creates feasible schedules, but also minimizes jitter for periodic tasks. The problem of scheduling real-time tasks with minimum jitter is particularly important in many control applications, nevertheless, it has been rarely studied in the scientific literature. We present a general framework consisting of an abstract architecture model and a general programming model. We show how to design a surprisingly simple and flexible scheduling method based on simulated annealing and present some experimental results.

Many distributed real-time applications are structured as a set of processes communicating through synchronous channels. Unfortunately, process interactions and especially synchronous communications make the problem of predictably scheduling the tasks more complex. In distributed systems the local and remote tasks as well as the messages over the network must be properly scheduled and synchronized to meet the deadlines of the application. To find such a, schedule is not an easy task, in fact, this problem is NP complete even if one has complete knowledge of the future arrival times for all the processes in the system. The objective of this paper is to develop a scheme that allows for the dynamic scheduling and guaranteeing of distributed processes communicating via synchronous primitives. For efficiency reasons a combination of off-line and on-line scheduling is performed. Precedence and communication constraints are converted off-line into pseudo-deadlines for each task, enabling efficient on-line processing. The on-line scheduling operates in parallel at the sites involved in the distributed computation, further obtaining efficiency. The overall end-to-end scheduling includes the joint and coordinated scheduling of tasks and messages in a reflective memory distributed architecture.>