Safe Implementation of Hard Real-Time Applications on Many-Core Platforms

Les systèmes temps-réel critiques sont conçus pour garantir non seulement les fonctionnalités mais aussi des contraintes temporelles. Parmi ces systèmes, nous pouvons citer le domaine des transports (avionique, automobile, ferroviaire) mais aussi le domaine médical ou celui de l'énergie. Cette dernière décennie, ces systèmes ont été mis en œuvre sur des plateformes complexes telles que des plateformes multi/pluri-cœurs. La prédictibilité de ces systèmes est garantie par le calcul de temps d'exécution pire-cas pour une application et une plateforme données; auxquels s'ajoutent, dans le cas de plateformes multi-cœurs, les coûts des interférences dues aux accès aux ressources partagées.L'utilisation de plateformes multi/pluri-cœurs pour les systèmes temps-réel critiques est de plus en plus répandue dans l'industrie, et elle est un sujet d'étude bien représenté dans le monde de la recherche. Cette thèse fournit des solutions et études comparatives concernant plusieurs points clés. Notre flot de conception se concentre sur le choix de modèles d'exécution, sur le placement des tâches sur les cœurs et en mémoire ainsi que leur ordonnancement, et sur une modélisation de la plateforme cible et des interférences qu'elle induit. Ainsi, le flot proposé permet d'obtenir une implémentation sûre des applications critiques, avec des bornes garanties sur leurs temps de réponse.Les applications temps-réel critique que nous étudions sont celles qui peuvent être représentées sous forme de graphe dirigé acyclique (Directed Acyclic Graph, DAG), où les nœuds correspondent au code fonctionnel (tâches), et les arrêtes représentent des contraintes de précédence et/ou des communications de données. Ce type de représentation est typique de ce que produisent les environnements de développement de haut-niveau utilisés dans l'industrie. Dans cette thèse, nous étudions majoritairement des applications générées par l'outil SCADE, dont des études de cas directement extraites, ou largement inspirées d'applications industrielles.Dans le cadre de cette thèse, la plateforme cible est le processeur Kalray MPPA qui offre des caractéristiques intéressantes vis-à-vis de la prédictibilité. Cette architecture est pluri-cœurs, c'est-à-dire qu'elle offre deux niveaux de parallélisme : un ensemble de cœurs de calculs parallèles forme un multi-cœur (cluster), et l'ensemble des clusters parallèles forme la plateforme complète. Dans cette thèse, nous étudions différents modèles d'exécution qui permettent d'obtenir plus de prédictibilité sur des plateformes pluri/multi-cœurs. Une méthode d'implémentation de ces différents modèles sur Kalray MPPA2 et MPPA3 est proposée, qui permet de les comparer en terme de type de modèle (exécution phasée) et d'implémentation en isolation complète ou partielle (avec prise en compte des délais d'interférence). Ces travaux ont montré qu'il était, dans notre contexte, plus intéressant de ne pas utiliser une isolation complète mais de modéliser de façon précise les interférences et leurs effets. Pour les phases de placement sur les cœurs et la mémoire ainsi que l'ordonnancement, nous avons mis l'accent sur l'utilisation mémoire et les coûts de communication. Un algorithme préliminaire nous permet de montrer que ces deux facteurs sont primordiaux et devraient être centraux pour les travaux futurs.L'utilisation d'une nouvelle plateforme (Kalray MPPA3) a nécessité une modélisation fine des temps d'accès aux ressources partagées, ainsi que le développement d'une méthode de calcul des délais dûs aux interférences. Un modèle des communications (intra et inter-clusters) a été développé et couplé à un outil d'analyse de temps de réponse. Pour tous ces travaux, des extensions d'outils académiques et industriels ont été réalisées: modèle du MPPA3 pour l'analyse temporelle (Multi-Core Interference Analysis, MIA) et le développement d'applications (SHIM),génération du code de communication et d'orchestration pour les applications produite par SCADE.Hard real-time systems are designed to be functionally correct, but also require the guarantee of timing constraints. Some examples of such systems are the central command of an airplane, electronic control units inside a car and a power plant monitoring room.Multi/many-core architectures tends to be used in such systems. The predictability of these systems is directly connected to being able to compute the worst-case response time of an application on a given architecture. Additionally, on multi/many-core architectures, when numerous cores access shared hardware resources at the same time, they interfere with each other, mutually slowing them down. To guarantee the respect of timing constraints of a real-time system, the interference sources must be identified and taken into account.The use of multi/many-core architecture on safety-critical real-time systems is increasing in the industry, as well as being an intense topic of research. This thesis provides solutions and comparative studies on several problems raised by the implementation of critical applications on such platforms. We focus on providing an integrated approach in order to confidently use multi/many-core architectures for hard real-time systems. This integrated workflow covers the choice of an execution model, a strategy to map and schedule tasks and a hardware model to provide safe bounds on the response time.The critical application to be analyzed is represented in the form of a Directed Acyclic Graph (DAG), with precedence constraints between nodes and explicit communication. This application can be issued from synchronous data flow languages or any other language or model-based development environment providing a DAG at the end of the compilation process. Most of our case study comes from the SCADE tool, some of them being industrial case study.The target architecture, the Kalray MPPA3 is a COTS processor but with interesting characteristics that make it a good candidate for real-time systems. At the core level, it has in-order pipeline and private caches with a predictable replacement policy. At the cluster level, it provides low latency scratchpad memory and predictable arbitration policies. At the SoC level, it provides an AXI bus relying the different clusters with constant traversal time.We present and explore several execution models that help to provide predictable execution on multi-core platform. They are applied to the many-core processors Kalray MPPA2 and MPPA3 and compared to enlighten the best approach in terms of task phased execution and memory access restrictions. We show that in our context, the isolation of tasks executed concurrently is too expensive in terms of response-time. The best execution model corresponds to a development process where interference analysis between task memory accesses are integrated in the implementation step.An additional improvement that has a significant impact on the overall response time of a program is the task mapping and scheduling on a given platform. With a high number of cores and clusters, it has become essential to provide a good positioning and ordering, at the risk of under utilizing the potential parallelism. Therefore we provide an initial work with multiple steps, taking into account the local memory use, communication cost and clusterization. We show that our memory use criteria is a good one to be used in future work.The Kalray MPPA3 is the main target architecture of this work and for its use in hard real-time systems, the arbitration points and shared resource access delay have been analyzed. A hardware model of intra and inter-cluster memory accesses is developed, combined with a response time analysis framework. Throughout this thesis several extensions and improvements were made to different industrial and academic tools: SCADE code generator, multi-core interference analysis and a high-level hardware model