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.

The major drawback of using static schedules to execute dataflow applications is their high inflexibility. In real-time systems, periodic schedules make it easier to assert safety guarantees and to decrease the schedule size, but their characteristics remain hard to compute. This article presents an approach to automatically generate fixed priority schedules from a dataflow specification. To do so, precedence dependencies between actors in the dataflow graphs are abstracted, as well as the task periods, by using affine relations . This abstraction allows us to synthesize schedules efficiently considering two main objectives: the maximization of throughput and the minimization of buffer sizes. Given a dataflow graph to execute in a real-time environment, we transform it into an Affine Dataflow Graph (ADFG) and compute the task priorities, their mapping, the number of delays in the buffers, and the buffer sizes. This article is the first to present an overview of both theoretical and practical aspects of ADFG. On the theoretical side, it presents corrections and improvements on the fixed priority case. On the practical side, benchmark evaluations demonstrate the robustness and maturity of the approach that our scheduling synthesizer implements. Synthesized schedules are evaluated by using scheduling simulation and real-time implementation. Last but not least, the synthesized periods reach the optimal throughput if enough processors are available, and most of the time the periods reach the maximal processor utilization factor in the uni-processor case. Moreover, execution time of the synthesis is about only 1 second for the main proposed algorithms.

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.

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.

Novel memory architectures have been introduced in multi/many-core processors to address the performance bottle neck due to shared memory accesses. Taking the advantages brought by these architectures in scheduling analysis is still an open challenge. In this article, we present a scheduling analysis technique that exploits a shared multi-bank memory architecture to efficiently schedule parallel real-time applications modeled as synchronous data flow (SDF) graphs by minimizing the memory access contentions. Our approach aims at producing a static time-triggered schedule with the objective of minimizing the makespan and buffer size requirements while respecting consistency and data dependency constraints. An Integer Linear Programming formulation of the scheduling problem is presented, as well as a heuristic with significantly lower time complexity. Experimental results are given using synthetic SDF graphs generated by the SDF3 tool and applications available in the StreamIt benchmark.

Transformation of synchronous data flow graphs (SDF) into equivalent homogeneous SDF representations has been extensively applied as a pre-processing stage when mapping signal processing algorithms onto parallel platforms. While this transformation helps fully expose task and data parallelism, it also presents several limitations such as an exponential increase in the number of actors and excessive communication overhead. Partial expansion graphs were introduced to address these limitations for multi-core platforms. However, existing solutions are not well-suited to achieve efficient scheduling on many-core architectures. In this article, we develop a new approach that employs cyclo-static data flow techniques to provide a simple but efficient method of coordinating the data production and consumption in the expanded graphs. We demonstrate the advantage of our approach through experiments on real application models.

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.

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.