List of publications in the CAPACITES Project

Back to Home Page

[1] Hamza Rihani, Matthieu Moy, Claire Maiza, and Sebastian Altmeyer. WCET analysis in shared resources real-time systems with TDMA buses. In RTNS 2015, 23rd International Conference on Real-Time Networks and Systems, Lille, France, Nov 2015. [ bib | .pdf ]
Predictability is an important aspect in real-time and safety-critical systems, where non-functional properties such as the timing behavior have high impact on the system correctness. As many safety-critical systems have a growing performance demand, simple, but outdated architectures are not sucient anymore. Instead, multi-core systems are more and more popular, even in the real-time domain. To combine the performance bene ts of a multi-core architecture with the required predictability, Time Division Multiple Access (TDMA) buses are often advocated. In this paper, we are interested in accesses to shared resources in such environments. Our approach uses SMT (Satis ability Modulo Theory) to encode the semantics and execution time of the analyzed program in an environment with shared resources. We use an SMT-solver to nd a solution that corresponds to the execution path with correct semantics and maximal execution time. We propose to model a shared bus with TDMA arbitration policy. Using examples, we show how the WCET estimation is enhanced by combining the semantics and the shared bus analysis in SMT.

Keywords: wcet ; tdma ; worst-case execution time ; bus ; multi-core ; smt
[2] Viet Anh NGUYEN, Damien Hardy, and Isabelle Puaut. Scheduling of parallel applications on many-core architectures with caches: bridging the gap between WCET analysis and schedulability analysis. In 9th Junior Researcher Workshop on Real-Time Computing (JRWRTC 2015), Lille, France, November 2015. [ bib | http | .pdf ]
Estimating the worst-case execution time (WCET) of parallel applications running on many-core architectures is a signi cant challenge. Some approaches have been proposed, but they assume the mapping of parallel applications on cores already done. Unfortunately, on architectures with caches, task mapping requires a priori known WCETs for tasks, which in turn requires knowing task mapping (i.e., co-located tasks, co-running tasks) to have tight WCET bounds. Therefore, scheduling parallel applications and estimating their WCET introduce a chicken and egg situa- tion. In this paper, we address this issue by developing an optimal integer linear programming formulation for solving the scheduling problem, whose objective is to minimize the WCET of a parallel application. Our proposed static partitioned non-preemptive mapping strategy addresses the e ect of local caches to tighten the estimated WCET of the parallel application. We report preliminary results obtained on synthetic parallel applications.

Keywords: WCET estimation ; manycores ; real time systems
[3] Stéphane Le Ménec. Interval based parallel computing of the viability kernel. In Summer Workshop on Interval Methods. MBDA/Airbus Group, 2016. [ bib ]
Viability theory provides a set of concepts and algorithms to study continuous dynamical systems (stability, reachability, Validation and Verification). Interval computation provides nice guaranteed numerical methods for approximating sets as those defined by viability theory. Refined interval techniques as contractor programming and guaranteed integration allow more particularly to implement the viability kernel and the capture basin algorithms. A parallel computing architecture based on 256 processors has been used for performing dynamical system integration in interval context. Results based on the car on the hill benchmark will be presented before studying more complex differential game problems (kinematics with two players / controls as in pursuit evasion games). The main contribution of this study is in using a many core architecture that will allow real time performances compatible with the various constraints that happen in embedded systems as light UAVs and ground mobile robots.

[4] Hamza Rihani, Matthieu Moy, Claire Maiza, Robert Davis, and Sebastian Altmeyer. Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor. In RTNS 2016, 24th International Conference on Real-Time Networks and Systems, Brest, France, Oct 2016. [ bib ]
In this paper we introduce a response time analysis technique for Synchronous Data Flow programs mapped to multiple parallel dependent tasks running on a compute cluster of the Kalray MPPA-256 many-core processor. The analysis we derive computes a set of response times and release dates that respect the constraints in the task dependency graph. We extend the Multicore Response Time Analysis (MRTA) framework by deriving a mathematical model of the multi-level bus arbitration policy used by the MPPA. Further, we refine the analysis to account for the release dates and response times of co-runners, and the use of memory banks. Further improvements to the precision of the analysis were achieved by splitting each task into two sequential phases, with the majority of the memory accesses in the first phase, and a small number of writes in the second phase. Our experimental evaluation focused on an avionics case study. Using measurements from the Kalray MPPA-256 as a basis, we show that the new analysis leads to response times that are a factor of 4.25 smaller for this application, than the default approach of assuming worst-case interference on each memory access.

[5] Fabrice Guet, Luca Santinelli, and Jérôme Morio. On the Reliability of the Probabilistic Worst-Case Execution Time Estimates. In 8th European Congress on Embedded Real Time Software and Systems (ERTS 2016), TOULOUSE, France, January 2016. [ bib | http | .pdf ]
Probabilistic Worst-Case Execution Time estimates, through Measurement-Based Probabilistic Timing Analyses and statistical inference, desperately need for formal definition and reliability. The automatic DIAGnostic tool for applying the eXTReMe value theory within the Probabilistic Timing Analysis framework we are proposing defines a complete set of statistical tests for studying execution time traces, e.g., the real-time task average execution behavior, and estimating the extreme behavior of the task execution time, in particular the probabilistic Worst-Case Execution Time. The tool allows also defining and evaluating the reliability of the probabilistic Worst-Case Execution Time estimates with the Extreme Value Theory by applying a fuzzy logic approach. We apply the tool to traces of execution time measurements of a task running on a Commercial off-the-shelf real-time multi-core system under different execution conditions. Application of the diagnostic tool to the traces of execution time measurements particularly validates the hypothesis of using the Extreme Value Theory for estimating the probabilistic Worst-Case Execution Time for this kind of system.

Keywords: Probabilistic timing analysis ; Extreme Value Theory ; Probabilistic Worst-Case Execution Time
[6] Kostiantyn Berezovskyi, Fabrice Guet, Luca Santinelli, Konstantinos Bletsas, and Eduardo Tovar. Measurement-Based Probabilistic Timing Analysis for Graphics Processor Units, pages 223--236. Springer International Publishing, Cham, 2016. [ bib | DOI | http ]
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.

[7] Fabrice Guet, Luca Santinelli, and Jeryme Morio. Probabilistic analysis of cache memories and cache memories impacts on multi-core embedded systems. In Industrial Embedded Systems (SIES), 2016 11th IEEE Symposium on, pages 1--10. IEEE, 2016. [ bib | http ]
Task execution is heavily affected by the different elements composing real-time systems. Modeling and analyzing such effects would allow reducing the pessimism lying behind the worst-cases. A measurement-based probabilistic approach is developed in order to characterize cache behavior with probabilistic average and worst-case profiles. The approach applies also statistics for studying the impact that different system configurations have on the profiles as well as for evaluating the impact of caches on task execution times. The quality of the probabilistic models is verified through test cases with benchmark tasks running on non time-randomized multi-core real-time systems.

[8] Chao Chen, Luca Santinelli, Jeryme Hugues, and Giovanni Beltrame. Static probabilistic timing analysis in presence of faults. In Industrial Embedded Systems (SIES), 2016 11th IEEE Symposium on, pages 1--10. IEEE, 2016. [ bib ]
Accurate timing prediction for software execution is becoming a problem due to the increasing complexity of computer architecture, and the presence of mixed-criticality workloads. Probabilistic caches were proposed to set bounds to Worst Case Execution Time (WCET) estimates and help designers improve system resource usage. However, as technology scales down, system fault rates increase and timing behavior is affected. In this paper, we propose a Static Probabilistic Timing Analysis (SPTA) approach for caches with evict-on-miss random replacement policy using a state space modeling technique, with consideration of fault impacts on both timing analysis and task WCET. Different scenarios of transient and permanent faults are investigated. Results show that our proposed approach provides tight probabilistic WCET (pWCET) estimates and as fault rate increases, the timing behavior of the system can be affected significantly.

[9] Hamza Rihani, Claire Maiza, and Matthieu Moy. Efficient Execution of Dependent Tasks on Many-Core Processors. In RTSOPS 2016, 7th International Real-Time Scheduling Open Problems Seminar, Toulouse, France, Jul 2016. [ bib | .pdf ]
Keywords: WCRT Analysis; Shared Resource Interference; Dependent Tasks; Synchronous Data flow; Many-cores; Scheduling
[10] Omayma Matoussi and Frédéric Pétrot. Loop aware ir-level annotation framework for performance estimation in native simulation. In Proceedings of the 2017 Asia and South Pacific Design Automation Conference. IEEE, January 2017. Accepted for publication. [ bib ]
Native simulation is an interesting virtual prototyping candidate to speed-up architecture exploration and early software developments. It however does not provide out-of-the box non-functional information needed for software performance estimation. Annotating software with information is complex as high-level codes and binary codes have different structures due to compiler optimizations. This work proposes an annotation framework at compiler IR-level that focuses on loop structures, and reflects optimizations through a mapping scheme between the binary and the high-level IR. Experiments on instruction count show in average around 2% of error.

[11] L. Santinelli (ONERA), Z. Guo (UNC), and L. George (LIGM – ESIEE). Fault-aware sensitivity analysis for probabilistic real-time systems. In DFT 2016, 2016. [ bib ]
[12] Corentin Damman, Gregory Edison, Fabrice Guet, Eric Noulard, Luca Santinelli, and Jerome Hugues. Architectural performance analysis of FPGA synthesized LEON processors. In RSP 2016, 2016. [ bib ]
[13] Pierre Guillou, Benoît Pin, Fabien Coelho, and François Irigoin. A Dynamic to Static DSL Compiler for Image Processing Applications. In 19th Workshop on Compilers for Parallel Computing, Valladolid, Spain, July 2016. [ bib | http | .pdf ]
[14] Quentin Perret, Pascal Maurère, Éric Noulard, Claire Pagetti, Pascal Sainrat, and Benoit Triquet. Predictable composition of memory accesses on many-core processors. In Embedded Real Time Software and Systems (ERTS'16), January 2016. [ bib ]
[15] Quentin Perret, Pascal Maurère, Éric Noulard, Claire Pagetti, Pascal Sainrat, and Benoit Triquet. Temporal isolation of hard real-time applications on many-core processors. In 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1--11, April 2016. [ bib ]
[16] Quentin Perret, Pascal Maurère, Éric Noulard, Claire Pagetti, Pascal Sainrat, and Benoit Triquet. Mapping hard real-time applications on many-core processors. In RTNS 2016, 24th International Conference on Real-Time Networks and Systems, Brest, France, Oct 2016. [ bib ]

This file was generated by bibtex2html 1.98.