Placement des tâches temps-réel dur sur des multi-coeurs en réseau-sur-puce (NoC)

In this dissertation, we tackle the problem of execution complex multi-thread real-time applications on modern Network-on-Chip architectures. Network-on-Chip (NoC) is a promising technology that fits the increasing performance demands of Cyber-Physical Systems (CPS). The introduction of NoCs is justified by the fact that classical multi-core single-bus architectures fail to address the performance requirements and the predictability needs of modern CPS applications, especially as the number of cores increases. Even if the use of cache memories mitigates the bottleneck effect of single bus architectures, caches introduce unpredictable delays in accessing data, which in turn make it difficult to estimate the execution time of tasks. Most CPS applications are time-sensitive: tasks are assigned deadlines that must never exceed, otherwise a critical failure may occur. Such systems are denoted by hard real-time. Consequently, the communications that occur in the network, denoted by on-chip communications, must be predictable and as fast as possible to prevent deadline-missing. Since the task position on the NoC determines its communication cost, the allocation of the application tasks on the chip cores is a crucial problem. In this thesis, we address specifically the problem of allocating a set of real-time applications, each composed of several parallel tasks, whose structure is described by a Directed Acyclic Graph (DAG), onto a Network-on-Chip processor. First, we study the problem of bounding the communication cost depending on the different message scheduling policies at the router level. Then we address the problem of task scheduling and of verifying the schedulability of a certain allocation. Then, we propose an approach to reduce the complexity of the task allocation problem and its analysis cost. Moreover, we propose a task mapping strategy through a meta-heuristic which performs an effective design-space exploration for DAG (Directed Acyclic Graph) tasks. Lastly, in addition to on-chip communications, we studied the mapping problem when the off-chip communications are integrated into the model.Dans cette thèse, nous abordons le problème de l'exécution d'applications temps réel multi-thread complexes sur des architectures modernes de type Network-on-Chip. Les réseaux sur puce (NoC) sont une technologie prometteuse qui répond aux exigences croissantes de performance des systèmes cyber-physiques (CPS). L'introduction des NoC se justifie par le fait que les architectures classiques multi-cœurs à bus unique ne répondent pas aux exigences de performance et aux besoins de prévisibilité des applications CPS modernes, en particulier lorsque le nombre de cœurs augmente. Même si l'utilisation de mémoires cache atténue l'effet de goulot d'étranglement des architectures à bus unique, les caches introduisent des retards imprévisibles dans l'accès aux données, ce qui rend difficile l'estimation du temps d'exécution des tâches. La plupart des applications CPS sont sensibles au temps : les tâches se voient attribuer des délais qu'elles ne doivent jamais dépasser, sous peine de subir une défaillance critique. De tels systèmes sont qualifiés de temps réel dur. Par conséquent, les communications qui se produisent dans le réseau, désignées par les communications sur puce, doivent être prévisibles et aussi rapides que possible pour éviter le dépassement des délais. Puisque la position de la tâche sur le NoC détermine son coût de communication, l'allocation des tâches d'application sur les cœurs de la puce est un problème crucial. Dans cette thèse, nous abordons spécifiquement le problème de l'allocation d'un ensemble d'applications temps réel, chacune composée de plusieurs tâches parallèles, dont la structure est décrite par un graphe acyclique dirigé (DAG), sur un processeur Network-on-Chip. Dans un premier temps, nous étudions le problème de la limitation du coût de communication en fonction des différentes politiques d'ordonnancement des messages au niveau du routeur. Ensuite, nous abordons le problème de l'ordonnancement des tâches et de la vérification de l'ordonnançabilité d'une certaine allocation. Ensuite, nous proposons une approche pour réduire la complexité du problème d'allocation des tâches et son coût d'analyse. De plus, nous proposons une stratégie de placement des tâches par le biais d'une méta-heuristique qui effectue une exploration efficace de l'espace des solutions pour les tâches DAG (Directed Acyclic Graph). Enfin, en plus des communications intra-puce, nous avons étudié le problème de placement lorsque les communications hors puce sont intégrées au modèle