Modern real-time embedded systems increasingly integrate software with varying criticality levels, which increases the interest in mixed criticality scheduling (MCS). MCS provides runtime adaptation mechanisms when low criticality tasks exceed their allocated execution budgets in order to guarantee the timing constraints of high criticality tasks. Most of the current research on MCS adaptation mechanisms focuses on guaranteeing timing constraints by interrupting and discarding low criticality tasks when their budgets are exceeded. They consider only the temporal dimension, without taking into account the quality of the results obtained. Quality is defined as the accuracy level of the results computed by a task within a given execution time. In this article, we propose an approach to integrate quality in a new task model to establish a relationship between quality and scheduling design. We propose the q-AMC scheduling algorithm to validate our task model. This algorithm integrates quality degradation into the scheduling adaptation mechanism. Simulation-based experiments show that our approach increases the quality up to 44.6% compared to the original AMC approach.

In this article, we investigate the interest in applying a mixed-criticality approach to schedule convolutional neural network (CNN) applications on multicore architectures. We deal with software composed of real-time interactive applications and CNNs that have different criticality levels. A classical means to schedule software with various criticality levels is to apply partitioning methods to enforce spatial and temporal isolation, which may be inefficient if application execution times have a high level of variability. In that case, applying a mixed-criticality approach may improve resource usage. We conducted a measurement campaign to assess the variability of CNN execution time and investigate whether this kind of application could benefit from a mixed-criticality approach. The results show that the execution times of the chosen CNN application vary with an average execution time of 109 ms and a worst case of 252 ms. Furthermore, they indicate a potential save of computing resources up to 73 % when applying a mixed-criticality approach instead of partitioning methods.

In order to ease the early verification of uniprocessor real-time systems, the tool Cheddar provides a service that guarantees the applicability of a schedulability analysis method for a given architecture model. This verification service uses a catalog of design patterns. In this article, we propose to extend these patterns to multiprocessor architectures. Designing such extension is a challenge because the knowledge of both the software and the hardware architectures are essential to decide on the schedulability of a task set in that context. Indeed, parallel execution of tasks involves hardware resource sharing, that has in turn an effect on the task execution times. Currently, no general method is able to assess the schedulability of a high-performance multicore system with a limited level of pessimism, except if assumptions or usage restrictions are set to simplify the system analysis. So, the research community is developing multiple schedulability tests based on various assumptions which constrain the task models and their execution platforms. In this article, we propose a framework based on Prolog that allows engineers to verify the conditions to apply a test are met. Prolog facts model the software and hardware architecture, and the inference engine checks whether these facts conform to a design pattern associated to a given verification method. The design pattern compliance framework is integrated with the Cheddar tool. Three examples of multiprocessor analyses illustrate the proposal. A scalability analysis shows the tool is able to verify the compliance of architectures composed of 600 tasks and 60 cores, in less than 140s on a desktop computer.

This paper deals with scheduling anomalies in real-time systems. Scheduling anomalies jeopardize schedulability analysis made prior to execution. In this paper, we propose a model to specify conditions leading to scheduling anomalies. A scheduling anomaly is modeled as a set of constraints on the architecture. We use this model to detect scheduling anomalies by offline and online analysis. To validate our approach, we implemented the approach as an extension to Cheddar, a schedulability tool. We apply our approach to seven scheduling anomalies and we show that most of these anomalies can be successfully detected.

Network-on-Chips (NoC) are widely used in industrial applications since they provide communication parallelism and reduce energy consumption. The use of NoC has been recently extended to real-time systems, whose execution has to meet temporal constraints. Communication delays introduced by the network make the scheduling analysis challenging. In this article, we propose a new NoC communication model called ECTM. The main goal of this model is to assess the schedulability of dependent periodic tasks exchanging messages on a NoC. ECTM is a model allowing schedulability analysis of messages and tasks of the NoC. To achieve schedulability, ECTM produces an analysis model by transforming NoC messages to tasks in order to take into account communication delays during the scheduling analysis. Schedulability of the system is assessed using simulation over the feasibility interval with a list scheduling, ECTM supports Store-And-Forward and Wormhole NoC. In this article, we have demonstrated the correctness of the transformations of ECTM. ECTM has been implemented in a real-time scheduling analysis tool called Cheddar and we performed experiments to assess its efficiency. ECTM is more efficient than existing solutions with an improvement of 30% for Store-And-Forward NoCs and up to 100% for Wormhole NoCs, while the proposed model requires a larger computation time about 17% for Store-And-Forward NoCs.

ARINC 653 introduces the concept of partition that allows time and space isolation in real-time avionic systems. Tasks are assigned to partitions according to various objective functions or constraints such as safety, performance, and security. Some of these objective functions may be conflicting as an improvement of one objective leads to a decrease of another. For example, improving safety by active redundancy may decrease performance. In this paper, we investigate the conflicting aspect between schedulability and security in Time and Space Partitioning (TSP) systems. Many researches have shown that enforcing the security of a system results in an overhead affecting its schedulability. We formulate a design space exploration (DSE) process with a meta-heuristic to explore solutions defined by the tasks to partitions assignment according to security requirements and timing constraints. Experiments are conducted with the Cheddar scheduling analyzer to characterize applications that are concerned by this conflicting issue and to evaluate the tradeoffs between schedulability and security.

A Mixed Criticality System (MCS) combines real-time software tasks with different criticality levels. In a MCS, the criticality level specifies the level of assurance against system failure. For high-critical flows of messages, it is imperative to meet deadlines; otherwise, the whole system might fail, leading to catastrophic results, like loss of life or serious damage to the environment. In contrast, low-critical flows may tolerate some delays. Furthermore, in MCS, flow performances such as the Worst Case Communication Time (WCCT) may vary depending on the criticality level of the applications. Then execution platforms must provide different operating modes for applications with different levels of criticality. To conclude, in Network-On-Chip (NoC), sharing resources between communication flows can lead to unpredictable latencies and subsequently turns the implementation of MCS in many-core architectures challenging. In this article, we propose and evaluate a new NoC router to support MCS based on an accurate WCCT analysis for high-critical flows. The proposed router, called Double Arbiter and Switching router (DAS), jointly uses Wormhole and Store And Forward communication techniques for low- and high-critical flows, respectively. It ensures that high-critical flows meet their deadlines while maximizing the bandwidth remaining for the low-critical flows. We also propose a new method for high-critical communication time analysis, applied to Store And Forward switching mode with virtual channels. For low-critical flows communication time analysis, we adapt an existing wormhole communication time analysis with share policy to our context. The second contribution of this article is a multi-abstraction-level evaluation of DAS. We evaluate the communication time of flows, the system mode change, the cost, and four properties of DAS. Simulations with a cycle-accurate SystemC NoC simulator show that, with a 15% network use rate, the communication delay of high-critical flows is reduced by 80% while communication delay of low-critical flow is increased by 18% compared to solutions based on routers with multiple virtual channels. For 10% of network interferences, using system mode change, DAS reduces the high-critical communication delays about 66%. We synthesize our router with a 28nm SOI technology and show that the size overhead is limited of 2.5% compared to the solution based on virtual channel router. Finally, we applied model checking verification techniques to automatically prove several DAS properties required by critical systems designers.

Mixed-Criticality Systems (MCS) are real-time systems characterized by two or more distinct levels of criticality. In MCS, it is imperative that high-critical flows meet their deadlines while low critical flows can tolerate some delays. Sharing resources between flows in Network-On-Chip (NoC) can lead to different unpredictable latencies and subsequently complicate the implementation of MCS in many-core architectures. This paper proposes a new virtual channel router designed for MCS deployed over NoCs. The first objective of this router is to reduce the worst-case communication latency of high-critical flows. The second aim is to improve the network use rate and reduce the communication latency for low-critical flows. The proposed router, called DAS (Double Arbiter and Switching router), jointly uses Wormhole and Store And Forward techniques for low and high-critical flows respectively. Simulations with a cycle-accurate SystemC NoC simulator show that, with a 15% network use rate, the communication delay of high-critical flows is reduced by 80% while communication delay of low-critical flow is increased by 18% compared to usual solutions based on routers with multiple virtual channels.

External sorting algorithms are commonly used by data-centric applications to sort quantities of data that are larger than the main-memory. Many external sorting algorithms were proposed in state-of-the-art studies to take advantage of SSD performance properties to accelerate the sorting process. In this paper, we demonstrate that unfortunately, many of those algorithms fail to scale when it comes to increasing the dataset size under memory pressure. In order to address this issue, we propose a new sorting algorithm named MONTRES. MONTRES relies on SSD performance model while decreasing the overall number of I/O operations. It does this by reducing the amount of temporary data generated during the sorting process by continuously evicting small values in the final sorted file. MONTRES scales well with growing datasets under memory pressure. We tested MONTRES using several data distributions, different amounts of main-memory workspace and three SSD models. Results showed that MONTRES outperforms state-of-the-art algorithms as it reduces the sorting execution time of TPC-H datasets by more than 30 percent when the file size to main-memory size ratio is high.

This paper proposes a storage system cost model for Infrastructure as a Service (IaaS) Cloud. The proposed cost model takes into account the virtualization environment, the storage system characteristics in addition to energy and QoS related parameters (Service Level Agreement and penalties). We show that those parameters are relevant and allow us to predict an accurate estimation of the overall cost of the IaaS infrastructure. We validate this cost model against real measures and we show less than 10% of error in most cases. Designers and administrators can use this cost model to perform optimization, load balancing, configuration and pricing of the Cloud infrastructure.

Real-time embedded systems may be composed of a large number of time constrained functions. During software architecture design, these functions must be assigned to tasks that will run the functions on the top of a real-time operating systems (RTOS). This is a challenging work due to the large number of valid candidate functions to tasks assignment solutions. Moreover, the impact of the assignment on the system performance criteria (often conflicting) should be taken into account in the architecture exploration. The automation of the design exploration by the use of metaheuristics such as multi-objective evolutionary algorithm (MOEA) is a suitable way to help the designers. MOEAs approximate near-optimal alternatives at a reasonable time when compared to an exact search method. However, for large-scale systems even a MOEA method is impractical due to the increased time required to solve a problem instance. To tackle this problem, we present in this article a parallel implementation of the Pareto Archived Evolution Strategy (PAES) algorithm used as a MOEA for the design exploration. The proposed parallelization method is based on the well-known Master-Slave paradigm. Additionally, it involves a new selection scheme in the PAES algorithm. Results of experimentations provide evidence that, on one hand, the parallel approach can considerably speed up the design exploration and the optimization processes. On the other hand, the proposed selection strategy improves the quality of obtained solutions as compared to the original PAES selection schema.

Handling cache related preemption delay (CRPD) in preemptive scheduling context for real-time embedded systems still stays an open issue despite of its practical importance. Indeed, classical priority assignment algorithms are only optimal when preemption costs are neglected. For example, with Audsley's Optimal Priority Assignment (OPA), as the original algorithm does not take CRPD into account, it fails frequently in identifying the schedulable task sets as it happens that the algorithm qualifies a task set to be schedulable, while it is practically not because of CRPD. In this article, we propose an approach to adapt fixed priority assignment algorithms to real-time embedded systems with cache memory. For such a purpose, we propose three extensions of the original OPA algorithm that have different degrees of pessimism, different complexities, and give different results in terms of schedulable task sets coverage. Exhaustive experimentations were achieved to evaluate the proposed approaches in terms of complexity and efficiency. The result shows that our approach provides a mean to guarantee the schedulability of the real-time embedded system while taking into account CRPD.

This article deals with real-time embedded system design and verification. Real-time embedded systems are frequently designed according to multi-tasking architectures that have timing constraints to meet. The design of real-time embedded systems expressed as a set of tasks raises a major challenge since designers have to decide how functions of the system must be assigned to tasks. Assigning each function to a different task will result in a high number of tasks, and then in higher preemption overhead. In contrast, mapping many functions on a limited number of tasks leads to a less flexible design which is more expensive to change when the functions of the system evolve. This article presents a method based on an optimization technique to investigate the assignment of functions to tasks. We propose a multi-objective evolution strategy formulation which both minimizes the number of preemptions and maximizes task laxities. Our method allows designers to explore the search space of all possible function to task assignments and to find good tradeoffs between the two optimization objectives among schedulable solutions. After explaining our mapping approach, we present a set of experiments which demonstrates its effectiveness for different system sizes.

In this paper, a schedulability test is proposed for tree-shaped transactions with non-immediate tasks. A tree-shaped transaction is a group of precedence dependent tasks, partitioned on different processors, which may release several other tasks upon completion. When there are non-immediate tasks, tasks are not necessarily released immediately upon their predecessor's completion. The schedulability test we propose is based on an existing test that does not handle non-immediate tasks directly. Simulation results show that tighter response time upper-bounds can be accessed when effects of non-immediateness are considered. Our schedulability test is motivated by real industrial TDMA systems developed at Thales, and experimental results show it provides less pessimistic schedulability results compared to current methods used by Thales system engineers.

Cache prediction for real-time systems in a preemptive scheduling context is still an open issue despite its practical importance. In this paper, we propose a modeling approach for taking into account the cache memory in realtime scheduling analysis. The goal is to have a simple but practical implementation to handle the cache memory with a real-time scheduling analyzer. The proposed contribution consists of three main parts: (1) modeling the targeted system with the Architecture Analysis and Design Language (AADL), (2) applying the cache analysis methods in a real time scheduling analysis tool and (3) performing scheduling simulation to access schedulability. For such a purpose, we present an extension of both the scheduling analysis tool Cheddar and of the AADL modeling language in order to integrate the cache modeling and analysis methodology we proposed. Experiments are presented to illustrate our propositions. They provide results on analysis that show examples of the timing impact of task preemption as well as the increase in overall responses time of the task set. This impact is important and the developed tool provides means to precisely assess it.

As real-time systems have become more and more complex, architects rely on abstract models of computation in order to design and analyse these systems. In order to ease the production of source code that respects such models of computation, developper can take advantage of code generators and/or middleware. However, when analyzing an abstract model of computation, timing overheads due to generated code or middleware components are not taken into account. Answering this issue is even more problematic in the domain of embedded systems because of the variability of execution platforms. To tackle this problem, we present in this paper a model refinement and timing analysis framework: abstract models of computation are first transformed in more precise models, which include the timing characteristics of the execution platform. These refined models are then used for a more precise timing analysis. The experiment results we present in this paper show that our method can deal with realistic software architecture of real-time systems.

The design of hard real-time embedded systems has to comply with strong requirements with respect to time determinism and resource consumption. However, interacting tasks may induce pessimism in schedulability analysis or introduce significant overheads in memory usage. In this paper, we restrict the execution and communication models to enforce an efficient and predictable implementation. To ensure determinism, a message sent by an emitting task is delivered at its deadline. We take advantage of a wait-free specialized message queues to provide predictable and efficient implementation. The integration of such mechanisms is assisted by a model driven engineering framework1.

Model-Based Engineering is now a valuable asset to design complex real-time systems. Toolchains are assembled to cover the various stages of the process: high-level modeling, analysis and code generation. Yet tools put heterogeneous requirements on models: specific modeling patterns must be respected so that a given analysis is performed. This creates an interoperability paradox: models must be tuned not given system requirements, but to abide to tools capabilities. In this paper, we propose a systematic process to define the definition, comparison and enforcement of tools-specific subsets. Thus, we guide the user in selecting the tools that could support its engineering process. Our contribution is illustrated in the context of the AADL Architecture Design Language.

Real-Time Embedded systems must respect a wide range of non-functional properties, including safety, respect of deadlines, power or memory consumption. We note that correct hardware resource dimensioning requires taking into account the impact of the whole software, both the user code and the underlying run time environment. AADL allows one to precisely capture all of them. In this article, we evaluate the AADL modeling to define memory architectures, and then verification rules to assess that the memory is correctly dimensioned. We use the REAL domain-specific language to express memory requirements (such as layout or size) and then validate them on a case-study using the VxWorks real-time kernel.

Cheddar is a framework dedicated to the specification of real-time schedulers, and to their analysis by simulation. It is developed in Ada. Some parts of its modular architecture are generated by Platypus, a software engineering tool based on the STEP standards. Cheddar owns a dedicated specification language. It can also process AADL v1 specifications. In order to extend the scope of Cheddar to AADL v2 specifications, we introduced a translation component called Dairy. It aims at creating valid Cheddar data from AADL v2 specifications. The frontend of Dairy comes from Osate v2. Hence, the backend of Dairy must produce Cheddar data from instances of the AADL metamodel that has been implemented into Osate. Both of Cheddar and Osate are legacy systems built with different frameworks, different standards and different languages. Hence, the design of Dairy poses the problem of their integration. We postulate that an implemented metamodel should neither be rewritten nor be duplicated in order to keep unchanged its legacy equipment. Then, integration should better rely on data interoperability standards. In this paper, we illustrate this idea by investigating six different designs of Dairy to perform the integration of Cheddar and Osate. We compare them with each other according to reusability, code generation, and transformation of metamodels.