Guaranteed Component Assembly with Round Trip Analysis for Energy Efficient High-integrity Multi-core Systems

Funder

Organizational Unit

Publications

Run-Time Monitoring Environments for Real-Time and Safety Critical Systems

Publication . Nelissen, Geoffrey; Carvalho, Humberto; Pereira, David; Tovar, Eduardo

In this work, we present four different implementations of a run-time monitoring framework suited to real-time and safety critical systems. Two implementations are written in Ada and follow the Ravenscar profile, which make them particularly suited to the development of high integrity systems. The first version is available as a standalone library for Ada programs while the second has been integrated in the GNAT run-time environment and instruments the ORK+ micro-kernel. Information on the task scheduling events, directly originating from the kernel, can thus be used by the monitors to check if the system follows all its requirements. The third implementation is a standalone library written in C++ that can be used in any POSIX compliant run-time environment. It is therefore compatible with the vast majority of operating systems used in embedded systems. The last implementation is a loadable kernel module for Linux. It has for main advantage to be able to enforce complete space partitioning between the monitors and the monitored applications. It is therefore impossible for memory faults to propagate and corrupt the state of the monitors.

2016Other

Open access

Measurement-Based Probabilistic Timing Analysis for Graphics Processor Units

Publication . Berezovskyi, Kostiantyn; Guet, Fabrice; Santinelli, Luca; Bletsas, Konstantinos; Tovar, Eduardo

Purely analytical worst-case execution time (WCET) estimation approaches for Graphics Processor Units (GPUs) cannot go far because of insufficient public information for the hardware. Therefore measurement-based probabilistic timing analysis (MBPTA) seems the way forward. We recently demonstrated MBPTA for GPUs, based on Extreme Value Theory (EVT) of the “Block Maxima” paradigm. In this newer work, we formulate and experimentally evaluate a more robust MBPTA approach based on the EVT “Peak over Threshold” paradigm with a complete set of tests for verifying EVT applicability. It optimally selects parameters to best-fit the input measurements for more accurate probabilistic WCET estimates. Different system configuration parameters (cache arrangements, thread block size) and their effect on the pWCET are considered, enhancing models of worst-case GPU behavior.

2016Conference object

Restricted access

Response Time Analysis of Sporadic DAG Tasks under Partitioned Scheduling

Publication . Fonseca, José; Nelissen, Geoffrey; Nelis, Vincent; Pinho, Luís Miguel

Several schedulability analyses have been proposed for a variety of parallel task systems with real-time constraints. However, these analyses are mostly restricted to global scheduling policies. The problem with global scheduling is that it adds uncertainty to the lower-level timing analysis which on multicore systems are heavily context-dependent. As parallel tasks typically exhibit intense communication and concurrency among their sequential computational units, this problem is further exacerbated. This paper considers instead the schedulability of partitioned parallel tasks. More precisely, we present a response time analysis for sporadic DAG tasks atop multiprocessors under partitioned fixed-priority scheduling. We assume the partitioning to be given. We show that a partitioned DAG task can be modeled as a set of self-suspending tasks. We then propose an algorithm to traverse a DAG and characterize such worst-case scheduling scenario. With minor modifications, any state-of-the-art technique for sporadic self-suspending tasks can thus be used to derived the worstcase response time of a partitioned DAG task. Experiments show that the proposed approach significantly tightens the worst-case response time of partitioned parallel tasks comparatively to the state-of-the-art when the most accurate technique is chosen.

2016Conference object

Restricted access

A New Approach for Limited Preemptive Scheduling in Systems with Preemption Overhead

Publication . Nasri, Mitra; Nelissen, Geoffrey; Fohler, Gerhard

This paper considers the problem of reducing the number of preemptions in a system with periodic tasks and preemption overhead. The proposed solution is based on the key observation that for periodic task sets, the task with the smallest period plays an important role in determining the maximum interval of time during which a lower priority task can be executed without being preempted. We use this property to build a new limited preemptive scheduling algorithm, named RSLP, based on fixed-priority scheduling. In RS-LP, the length of each task’s non-preemptive region is varying during the system execution so as to keep the preemptions aligned with the releases of the highest priority task. This simple mechanism allows us to reduce the overall number of preemptions. The proposed algorithm, decides whether or not to preempt the currently executing task based on the maximum blocking tolerance of the higher priority tasks. In any case, the preemptions are authorized only at release instants of the task with the smallest period, thereby limiting the maximum number of preemptions to the number of releases of the highest priority task. Moreover, in this paper, we provide two different preemption overhead aware schedulability tests for periodic and loose-harmonic task sets (i.e., where each period is an integer multiple of the smallest period), together with a lower bound on the maximum number of preemptions. To conclude, extensive experiments comparing RS-LP with the state of the art limited preemptive scheduling algorithms are finally presented.

2016Conference object

Restricted access

Cache-Persistence-Aware Response-Time Analysis for Fixed-Priority Preemptive Systems

Publication . Rashid, Syed Aftab; Nelissen, Geoffrey; Hardy, Damien; Åkesson, Benny; Puaut, Isabelle; Tovar, Eduardo

A task can be preempted by several jobs of higher priority tasks during its response time. Assuming the worst-case memory demand for each of these jobs leads to pessimistic worstcase response time (WCRT) estimations. Indeed, there is a big chance that a large portion of the instructions and data associated with the preempting task τj are still available in the cache when τj releases its next jobs. Accounting for this observation allows the pessimism of WCRT analysis to be significantly reduced, which is not considered by existing work. The four main contributions of this paper are: 1) The concept of persistent cache blocks is introduced in the context of WCRT analysis, which allows re-use of cache blocks to be captured, 2) A cache-persistence-aware WCRT analysis for fixed-priority preemptive systems exploiting the PCBs to reduce the WCRT bound, 3) An multi-set extension of the analysis that further improves the WCRT bound, and 4) An evaluation showing that our cache-persistence-aware WCRT analysis results in up to 10% higher schedulability than state-of-the-art approaches.

2016Conference object

Open access