A Probabilistically Analyzable Cache to Estimate Timing Bounds

- Modern computer architectures are targeted towards speeding up the average performance of software running on it. Architectural features like: deep pipelines, branch prediction, outof-order execution, and multi-level memory hierarchies have an adverse impact on software timing prediction. Particularly, it is hard or even impossible to make an accurate estimation of the worst case execution-time (WCET) of a program or software running on a particular hardware platform. Critical real-time embedded systems (CRTESs), e.g. computing systems in aerospace require strict timing constraints to guarantee their proper operational behavior. WCET analysis is the central idea of the real-time systems development because real-time systems always need to meet their deadlines. In order to meet the deadline requirements, WCET of the real-time systems tasks must be determined, and this is only possible if the hardware architecture is time-predictable. Due to the unpredictable nature of the modern computing hardware, it is not practical to use advanced computing systems in CRTESs. The real-time systems do not need to meet high-performance requirements. The processor designed to improve average cases performance may not fit the requirements for the real-time systems due to predictability issues. Current timing analysis techniques are well established, but require detailed knowledge of the internal operations and the state of the system for both hardware and software. Lack of in-depth knowledge of the architectural operations become an obstacle for adopting the deterministic timing analysis (DTA) techniques for WCET measurement. Probabilistic timing analysis (PTA) is a technique that emerged for the timing analysis of the next-generation real-time systems. The PTA techniques reduce the extent of knowledge of a software execution platform that is needed to perform the accurate WCET estimations. In this thesis, we propose the development of a new probabilistically analyzable cache and applied PTA techniques for time-prediction. In this work, we implemented a randomized cache for MIPS- 32 and Leon-3 processors. We designed and implemented random placement and replacement policies, and applied probabilistic timing techniques to measure probabilistic WCET (pWCET). We also measured the level of pessimism incurred by the probabilistic techniques and compared it with the deterministic cache configuration. The WCET prediction provided by the PTA techniques is closer to the real execution-time of the program. We compared the estimates with the measurements done on the processor to help the designer to evaluate the level of pessimism introduced by the cache architecture for each probabilistic timing analysis technique. This work makes a first attempt towards the comparison of deterministic, static, and measurement-based probabilistic timing analysis for time-prediction under varying cache configurations. We identify strengths and limitations of each technique for time- prediction, and provide guidelines for the design of the processor that minimize the pessimism associated with WCET. Our experiments show that the cache fulfills all the requirements for PTA and program prediction can be determined with arbitrary accuracy. Such probabilistic computer architecture carries unmatched potential and great promise for next generation CRTESs.

Résumé

Les architectures informatiques modernes cherchent à accélérer la performance moyenne des logiciels en cours d'exécution. Les caractéristiques architecturales comme : deep pipelines, prédiction de branchement, exécution hors ordre, et hiérarchie des mémoire à multiple niveaux ont un impact négatif sur le logiciel de prédiction temporelle. En particulier, il est difficile, voire impossible, de faire une estimation précise du pire cas de temps d'exécution (WCET) d'un programme ou d'un logiciel en cours d'exécution sur une plateforme informatique particulière. Les systèmes embarqués critiques temps réel (CRTESs), par exemple les systèmes informatiques dans le domaine aérospatiale, exigent des contraintes de temps strictes pour garantir leur fonctionnement opérationnel. L'analyse du WCET est l'idée centrale du développement des systèmes temps réel puisque les systèmes temps réel ont toujours besoin de respecter leurs échéances. Afin de répondre aux exigences du délai, le WCET des tâches des systèmes temps réel doivent être déterminées, et cela est seulement possible si l'architecture informatique est temporellement prévisible. En raison de la nature imprévisible des systems informatiques modernes, il est peu pratique d'utiliser des systèmes informatiques avancés dans les CRTESs. En temps réel, les systèmes ne doivent pas répondre aux exigences de haute performance. Les processeurs conçus pour améliorer la performance des systèmes informatiques en général peuvent ne pas être compatibles avec les exigences pour les systèmes temps réel en raison de problèmes de prédictabilité. Les techniques d'analyse temporelle actuelles sont bien établies, mais nécessitent une connaissance détaillée des opérations internes et de l'état du système pour le matériel et le logiciel. Le manque de connaissances approfondies des opérations architecturales devient un obstacle à l'adoption de techniques déterministes de l'analyse temporelle (DTA) pour mesurer le WCET. Les techniques probabilistes de l'analyse temporelle (PTA) ont, quant à elles, émergé comme les techniques d'analyse temporelle pour la prochaine génération de systèmes temps réel. Les techniques PTA réduisent l'étendue des connaissances nécessaires pour l'exécution d'un logiciel informatique afin d'effectuer des estimations précises du WCET. Dans cette thèse, nous proposons le développement d'une nouvelle technique pour un cache probabilistiquement analysable, tout en appliquant les techniques PTA pour prédire le temps d'exécution d'un logiciel. Dans ce travail, nous avons mis en place une cache aléatoire pour les processeurs MIPS-32 et Leon-3. Nous avons conçu et mis en œuvre les politiques de placement et remplacement aléatoire et appliquer des techniques temporelles probabilistiques pour mesurer le WCET probabiliste (pWCET). Nous avons également mesuré le niveau de pessimisme encouru par les techniques probabilistes et comparé cela avec la configuration du cache déterministe. La prédiction du WCET fournie par les techniques PTA est plus proche de la durée d'exécution réelle du programme. Nous avons comparé les estimations avec les mesures effectuées sur le processeur pour aider le concepteur à évaluer le niveau de pessimisme introduit par l'architecture du cache pour chaque technique d'analyse temporelle probabiliste. Ce travail fait une première tentative de comparaison des analyses temporelles déterministes, statiques et de l'analyse temporelle probabiliste basée sur des mesures pour l'estimation du temps d'execution sous différentes configurations de cache. Nous avons identifié les points forts et les limites de chaque technique pour la prévision du temps d'execution, puis nous avons fourni des directives pour la conception du processeur qui minimisent le pessimisme associé au WCET. Nos expériences montrent que le cache répond à toutes les conditions pour PTA et la prévision du programme peut être déterminée avec une précision arbitraire. Une telle architecture probabiliste offre un potentiel inégalé et prometteur pour les prochaines générations du CRTESs.