Suchergebnisse

Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%. ; This work was supported in part by MINECO/AEI/ERDF (EU) under Grant TIN2016-76635-C2-1-R, Grant TIN2017-86727-C2-1-R, and Grant PID2019-105660RB-C21; in part by the Aragón Government under Grant T58_20R research group; in part by the Generalitat de Catalunya under Grant 2017 SGR 786 and Grant FI-DGR 2015; and in part by the Construyendo Europa desde Aragón under Grant ERDF 2014-2020. ; Peer Reviewed ; Postprint (published version)

The whole class ensemble tuition (WCET) programme in English schools is a somewhat singular and relatively recent arrival onto the teaching and learning scene. It arose from a remark made by an English politician, and has grown from there into becoming a regular feature in the music education landscape in primary schools. It has elements which will be familiar to music educators in many parts of the world, whilst having some aspects which are unique to the English context. In order to place the WCET programme into perspective, this paper outlines the policy context which gave rise to it, and explains what it involves, and how it is operationalised in schools.

Measurement-Based Probabilistic Timing Analysis (MBPTA) facilitates the analysis of complex software running on hardware comprising high-performance features. MBPTA also aims at preventing additional analysis costs for timing analysis techniques and preserving the confidence on derived WCET estimates. Cache behavior has a deep influence on WCET estimates and hence on "the amount of software" that can be consolidated onto a single hardware platform. Deterministic replacement policies such as LRU (Least Recently Used) and NMRU (Non-Most Recently Used) have systematic pathological cases that may lead to high execution times and WCET estimates. Instead, random replacement (RR) decreases pathological cases probability, at the cost of temporal locality. We present two new MBPTA-amenable replacement policies that completely remove the presented pathological cases. The first policy, Random Permutations (RP) preserves higher temporal locality than RR; while the second, NMRU Random Permutations (NMRURP), also protects the Most Recently Used line from eviction. Both proposed policies build upon restricted random replacement choices. Our simulation evaluation (validated against a real prototype) using the Mälardalen benchmarks and a case study shows that RP and NMRURP deliver both high average performance (within 1% of LRUs and NRMU performance) and tight WCET estimates 11% and 24% lower than those of RR. ; This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P, the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 772773) and the HiPEACH Network of Excellence. Pedro Benedicte and Jaume Abella have been partially supported by the MINECO under FPU15/01394 grant and Ramon y Cajal postdoctoral fellowship number RYC- 2019-14717 respectively. ; Peer Reviewed ; Postprint (author's final draft)

Critical Real-Time Embedded Systems require functional and timing validation to prove that they will perform their functionalities correctly and in time. For timing validation, a bound to the Worst-Case Execution Time (WCET) for each task is derived and passed as an input to the scheduling algorithm to ensure that tasks execute timely. Bounds to WCET can be derived with deterministic timing analysis (DTA) and probabilistic timing analysis (PTA), each of which relies upon certain predictability properties coming from the hardware/software platform beneath. In particular, specific hardware designs are needed for both DTA and PTA, which challenges their adoption by hardware vendors. This paper makes a step towards reconciling the hardware needs of DTA and PTA timing analyses to increase the likelihood of those hardware designs to be adopted by hardware vendors. In particular, we show how Time Division Multiple Access (TDMA), which has been regarded as one of the main DTA-compliant arbitration policies, can be used in the context of PTA and, in particular, of the industrially-friendly Measurement-Based PTA (MBPTA). We show how the execution time measurements taken as input for MBPTA need to be padded to obtain reliable and tight WCET estimates on top of TDMA-arbitrated hardware resources with no further hardware support. Our results show that TDMA delivers tighter WCET estimates than MBPTA-friendly arbitration policies, whereas MBPTA-friendly policies provide higher average performance. Thus, the best policy to choose depends on the particular needs of the end user. ; The research leading to these results has been funded by the EU FP7 under grant agreement no. 611085 (PROXIMA) and 287519 (parMERASA). This work has also been partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P and the HiPEAC Network of Excellence. Miloˇs Pani´c is funded by the Spanish Ministry of Education under the FPU grant FPU12/05966. Jaume Abella has been partially supported by the MINECO under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717. ; Peer Reviewed ; Postprint (author's final draft)

Critical Real-Time Embedded Systems require functional and timing validation to prove that they will perform their functionalities correctly and in time. For timing validation, a bound to the Worst-Case Execution Time (WCET) for each task is derived and passed as an input to the scheduling algorithm to ensure that tasks execute timely. Bounds to WCET can be derived with deterministic timing analysis (DTA) and probabilistic timing analysis (PTA), each of which relies upon certain predictability properties coming from the hardware/software platform beneath. In particular, specific hardware designs are needed for both DTA and PTA, which challenges their adoption by hardware vendors. This paper makes a step towards reconciling the hardware needs of DTA and PTA timing analyses to increase the likelihood of those hardware designs to be adopted by hardware vendors. In particular, we show how Time Division Multiple Access (TDMA), which has been regarded as one of the main DTA-compliant arbitration policies, can be used in the context of PTA and, in particular, of the industrially-friendly Measurement-Based PTA (MBPTA). We show how the execution time measurements taken as input for MBPTA need to be padded to obtain reliable and tight WCET estimates on top of TDMA-arbitrated hardware resources with no further hardware support. Our results show that TDMA delivers tighter WCET estimates than MBPTA-friendly arbitration policies, whereas MBPTA-friendly policies provide higher average performance. Thus, the best policy to choose depends on the particular needs of the end user. ; The research leading to these results has been funded by the EU FP7 under grant agreement no. 611085 (PROXIMA) and 287519 (parMERASA). This work has also been partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P and the HiPEAC Network of Excellence. Miloˇs Pani´c is funded by the Spanish Ministry of Education under the FPU grant FPU12/05966. Jaume Abella has been partially supported by the MINECO under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717. ; Peer Reviewed ; Postprint (author's final draft)

National audience ; Ce travail porte sur l'ordonnancement de systèmes embarqués critiques. Ces systèmes sont multi-périodiques et soumis à des contraintes d'échéances. L'implémentation d'un tel système doit de plus être fonctionnellement déterministe (les mêmes sorties produites pour les mêmes entrées), ce qui nécessite de contrôler précisément l'ordre des communications entre tâches, à l'aide de contraintes de précédence. Nous nous intéressons donc à l'ordonnancement de tâches périodiques reliées par des contraintes de précédence étendues (entre tâches de périodes différentes), à l'aide de politiques basées sur les priorités. En raison du caractère critique des applications considérées, on s'intéresse à des politiques d'ordonancement sans sémaphores, afin d'éliminer tout risque d'anomalie d'ordonnancement (un système prouvé ordonnançable avant l'exécution sur la base des WCET devenant non-ordonnaçable à l'exécution en raison d'une tâche ne prenant pas son WCET). Nous proposons une politique d'ordonnancement optimale pour le problème présenté ci-dessus, en priorité dynamique.

National audience ; Ce travail porte sur l'ordonnancement de systèmes embarqués critiques. Ces systèmes sont multi-périodiques et soumis à des contraintes d'échéances. L'implémentation d'un tel système doit de plus être fonctionnellement déterministe (les mêmes sorties produites pour les mêmes entrées), ce qui nécessite de contrôler précisément l'ordre des communications entre tâches, à l'aide de contraintes de précédence. Nous nous intéressons donc à l'ordonnancement de tâches périodiques reliées par des contraintes de précédence étendues (entre tâches de périodes différentes), à l'aide de politiques basées sur les priorités. En raison du caractère critique des applications considérées, on s'intéresse à des politiques d'ordonancement sans sémaphores, afin d'éliminer tout risque d'anomalie d'ordonnancement (un système prouvé ordonnançable avant l'exécution sur la base des WCET devenant non-ordonnaçable à l'exécution en raison d'une tâche ne prenant pas son WCET). Nous proposons une politique d'ordonnancement optimale pour le problème présenté ci-dessus, en priorité dynamique.

National audience ; Ce travail porte sur l'ordonnancement de systèmes embarqués critiques. Ces systèmes sont multi-périodiques et soumis à des contraintes d'échéances. L'implémentation d'un tel système doit de plus être fonctionnellement déterministe (les mêmes sorties produites pour les mêmes entrées), ce qui nécessite de contrôler précisément l'ordre des communications entre tâches, à l'aide de contraintes de précédence. Nous nous intéressons donc à l'ordonnancement de tâches périodiques reliées par des contraintes de précédence étendues (entre tâches de périodes différentes), à l'aide de politiques basées sur les priorités. En raison du caractère critique des applications considérées, on s'intéresse à des politiques d'ordonancement sans sémaphores, afin d'éliminer tout risque d'anomalie d'ordonnancement (un système prouvé ordonnançable avant l'exécution sur la base des WCET devenant non-ordonnaçable à l'exécution en raison d'une tâche ne prenant pas son WCET). Nous proposons une politique d'ordonnancement optimale pour le problème présenté ci-dessus, en priorité dynamique.

National audience ; Ce travail porte sur l'ordonnancement de systèmes embarqués critiques. Ces systèmes sont multi-périodiques et soumis à des contraintes d'échéances. L'implémentation d'un tel système doit de plus être fonctionnellement déterministe (les mêmes sorties produites pour les mêmes entrées), ce qui nécessite de contrôler précisément l'ordre des communications entre tâches, à l'aide de contraintes de précédence. Nous nous intéressons donc à l'ordonnancement de tâches périodiques reliées par des contraintes de précédence étendues (entre tâches de périodes différentes), à l'aide de politiques basées sur les priorités. En raison du caractère critique des applications considérées, on s'intéresse à des politiques d'ordonancement sans sémaphores, afin d'éliminer tout risque d'anomalie d'ordonnancement (un système prouvé ordonnançable avant l'exécution sur la base des WCET devenant non-ordonnaçable à l'exécution en raison d'une tâche ne prenant pas son WCET). Nous proposons une politique d'ordonnancement optimale pour le problème présenté ci-dessus, en priorité dynamique.

Manycores are capable of providing the computational demands required by functionally-advanced critical applications in domains such as automotive and avionics. In manycores a network-on-chip (NoC) provides access to shared caches and memories and hence concentrates most of the contention that tasks suffer, with effects on the worst-case contention delay (WCD) of packets and tasks' WCET. While several proposals minimize the impact of individual NoC parameters on WCD, e.g. mapping and routing, there are strong dependences among these NoC parameters. Hence, finding the optimal NoC configurations requires optimizing all parameters simultaneously, which represents a multidimensional optimization problem. In this paper we propose NoCo, a novel approach that combines ILP and stochastic optimization to find NoC configurations in terms of packet routing, application mapping, and arbitration weight allocation. Our results show that NoCo improves other techniques that optimize a subset of NoC parameters. ; This work has been partially supported by the Spanish Ministry of Economy and Competitiveness under grant TIN2015- 65316-P and the HiPEAC Network of Excellence. It also received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (agreement No. 772773). Carles Hernández is jointly supported by the MINECO and FEDER funds through grant TIN2014-60404-JIN. Jaume Abella has been partially supported by the Spanish Ministry of Economy and Competitiveness under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717. Enrico Mezzetti has been partially supported by the Spanish Ministry of Economy and Competitiveness under Juan de la Cierva-Incorporaci´on postdoctoral fellowship number IJCI-2016-27396. ; Peer Reviewed ; Postprint (author's final draft)

Multicores are becoming ubiquitous in automotive. Yet, the expected benefits on integration are challenged by multicore contention concerns on timing V&V. Worst-case execution time (WCET) estimates are required as early as possible in the software development, to enable prompt detection of timing misbehavior. Factoring in multicore contention necessarily builds on conservative assumptions on interference, independent of co-runners load on shared hardware. We propose a contention model for automotive multicores that balances time-composability with tightness by exploiting available information on contenders. We tailor the model to the AURIX TC27x and provide tight WCET estimates using information from performance monitors and software configurations. ; The research leading to this work has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 644080 (SAFURE). This work has also been partially funded by the Spanish Ministry of Science and Innovation under grant TIN2015-65316-P and the HiPEAC Network of Excellence. The Ministry of Economy and Competitiveness partially supported Jaume Abella under Ramon y Cajal postdoctoral fellowship (RYC-2013-14717) and Enrico Mezzetti under Juan de la Cierva-Incorporación postdoctoral fellowship (IJCI-2016-27396). ; Peer Reviewed ; Postprint (published version)

Multicores are becoming ubiquitous in automotive. Yet, the expected benefits on integration are challenged by multicore contention concerns on timing V&V. Worst-case execution time (WCET) estimates are required as early as possible in the software development, to enable prompt detection of timing misbehavior. Factoring in multicore contention necessarily builds on conservative assumptions on interference, independent of co-runners load on shared hardware. We propose a contention model for automotive multicores that balances time-composability with tightness by exploiting available information on contenders. We tailor the model to the AURIX TC27x and provide tight WCET estimates using information from performance monitors and software configurations. ; The research leading to this work has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 644080 (SAFURE). This work has also been partially funded by the Spanish Ministry of Science and Innovation under grant TIN2015-65316-P and the HiPEAC Network of Excellence. The Ministry of Economy and Competitiveness partially supported Jaume Abella under Ramon y Cajal postdoctoral fellowship (RYC-2013-14717) and Enrico Mezzetti under Juan de la Cierva-Incorporación postdoctoral fellowship (IJCI-2016-27396). ; Peer Reviewed ; Postprint (published version)

Manycores are capable of providing the computational demands required by functionally-advanced critical applications in domains such as automotive and avionics. In manycores a network-on-chip (NoC) provides access to shared caches and memories and hence concentrates most of the contention that tasks suffer, with effects on the worst-case contention delay (WCD) of packets and tasks' WCET. While several proposals minimize the impact of individual NoC parameters on WCD, e.g. mapping and routing, there are strong dependences among these NoC parameters. Hence, finding the optimal NoC configurations requires optimizing all parameters simultaneously, which represents a multidimensional optimization problem. In this paper we propose NoCo, a novel approach that combines ILP and stochastic optimization to find NoC configurations in terms of packet routing, application mapping, and arbitration weight allocation. Our results show that NoCo improves other techniques that optimize a subset of NoC parameters. ; This work has been partially supported by the Spanish Ministry of Economy and Competitiveness under grant TIN2015- 65316-P and the HiPEAC Network of Excellence. It also received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (agreement No. 772773). Carles Hernández is jointly supported by the MINECO and FEDER funds through grant TIN2014-60404-JIN. Jaume Abella has been partially supported by the Spanish Ministry of Economy and Competitiveness under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717. Enrico Mezzetti has been partially supported by the Spanish Ministry of Economy and Competitiveness under Juan de la Cierva-Incorporaci´on postdoctoral fellowship number IJCI-2016-27396. ; Peer Reviewed ; Postprint (author's final draft)

Extreme Value Theory has been used to model the WCET probabilistically, relying on the assumption that probabilistic WCET (pWCET) estimates can be upper-bounded with exponential distributions, but this is only assessed on execution time samples with pass/fail hypothesis tests. However, the degree of fulfilment of this hypothesis for the execution time sample has a direct impact on the tightness of the pWCET estimate. This paper tackles this limitation of pass/fail tests by applying 3 alternative methods to model the distribution of high execution times through the analysis of the number of finite moments of execution time samples. These methods provide information on the degree of fulfilment of the exponentiality hypothesis, rather than a simple pass/fail response. Hence, whenever the number of finite moments is shown to be low, despite pass/fail tests are passed, these methods indicate that pWCET estimates may be untight. We show that those methods complement each other and the information obtained - number of finite moments proven to exist - can be used to increase the execution time sample size opportunistically to obtain tighter pWCET estimates. ; This work was partially funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No.772773), the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P and the HiPEAC Network of Excellence. Jaume Abella has been partially funded by MINECO under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717. ; Peer Reviewed ; Postprint (author's final draft)