Execution time prediction for applications running on multi-core architectures
Prédiction du temps d'exécution d'applications dans des architectures multi-coeur
Résumé
The execution time of a task depends both on the input data, which define the sequence of instructions executed, and on the execution platform, which determines the duration of these instructions. In the context of real-time critical systems (e.g. avionics, spatial), it is crucial to know the Worst-Case Execution Time (WCET) of the tasks in order to guarantee that they all meet their timing constraints, which ensure a safe execution of the system (e.g. deadline). The WCET problem has already been studied in a lot of research works but they must be updated to take into account the recent hardware evolutions. Therefore, for more than a decade, multi-core architectures have been at the center of many research works. Indeed, manufacturers prefer them over single-core architectures because they offer performance, energy and space gains. However, timing verification is more challenging for these architectures due to the presence of shared resources that are sources of interference. Contentions appear when at least two cores simultaneously attempt to access a same resource. In this case, some tasks may take longer than expected to use the shared resource. This additional delay must be taken into account in the WCET of the tasks although it is difficult to predict the number of contentions that may occur and their moment.The first part of the thesis focuses on the multi-phase task model, which can be used during the scheduling and the interference analyses to compute the contentions with more precision. Indeed, tasks are no longer represented as a single temporal block but divided into several phases, each of which represents a portion of the task execution. With this model, accesses are no longer considered to be performed from the beginning to the end of the task but rather in a subset of the phases. This model was introduced prior to the thesis but we propose a more generic multi-phase model that we use to conservatively compute the number of accesses that may be performed in the phases for any multi-phase profile. We present 3 formal correctness criteria which guarantee that the method to compute the accesses in the phases is safe, and that the implementation of the model in the code, using synchronizations, is correct given a static schedule.The second part proposes techniques to design and optimize multi-phase profiles from their execution traces. The first technique is based on Kernel Density Estimation (KDE) that is used to cluster the instructions performing accesses in phases. We also present optimization and correction methods to maximize the efficiency of the profile during the interference analysis, along with a method to select synchronizations. Then, as our problem is multi-criteria and admits a lot of solutions, we propose two methods based on Genetic Algorithms (GA) respectively to create and to optimize multi-phase profiles. The design techniques presented are compared and evaluated using two case studies.The last part addresses the static scheduling of multi-phase tasks in multi-core architectures. The problem is presented with an ILP formulation that considers both the tasks dependencies and the effects of contentions to minimize the worst-case response time of the system. Then, we propose heuristics with different strategies to take advantage of the multi-phase model and to include the effects of contentions. We performed a statistical study over a large number of synthetic multi-phase tasks systems in order to compare the methods in different configurations and to prove the efficiency of the multi-phase model. The experiments end with two case studies that confront the heuristics to more realistic multi-phase profiles and bigger systems.
Le temps d'exécution d'un programme varie en fonction de ses entrées, qui définissent la séquence des instructions exécutées et de la plateforme d'exécution qui détermine la durée de ces instructions. Dans le contexte des systèmes temps-réel critiques (avionique, spatial...), il est crucial de connaître le temps d'exécution pire-cas des tâches, ou ac{WCET}, afin de garantir qu'elles respectent les contraintes temporelles qui régissent le bon fonctionnement du système comme la date d'échéance. De nombreuses recherches ont déjà étudié la prédiction du temps d’exécution et le ac{WCET} mais elles doivent être mises à jour pour tenir compte des évolutions matérielles. Ainsi, depuis plus d'une décennie, beaucoup de ces recherches ciblent les architectures multi-cœur qui sont plébiscitées par les industriels (meilleures performances, efficacité énergétique, gain de place...). Cependant, la présence de ressources partagées entre plusieurs cœurs fait apparaître des interférences lorsqu’ils tentent d’y accéder de façon concurrente. Certaines tâches peuvent alors attendre plus longtemps que prévu pour être servies par la ressource. L'analyse temporelle doit prendre en compte ces délais bien que la quantité d'interférences et leurs dates soient compliquées à prédire.La première partie de la thèse s’intéresse à l’utilisation d’un modèle de tâche plus précis qui peut être utilisé durant l’ordonnancement et l’analyse d’interférences appelé modèle multi-phase. Il consiste à représenter une tâche non plus sous la forme d’un seul bloc temporel mais divisée en plusieurs phases. Par conséquent, au lieu de considérer que les accès d’une tâche peuvent s’effectuer du début à la fin de cette tâche, on peut compartimenter ces accès dans les phases et ainsi calculer les interférences à l’échelle plus fine des phases. Ce modèle a déjà été utilisé avant la thèse mais nous proposons une formalisation plus générique ainsi qu'une méthode pour calculer de façon conservative le nombre d’accès dans les phases de n’importe quel profil multi-phase d’une tâche. Nous introduisons aussi 3 critères de correction pour garantir que la méthode de calcul des accès est sûre et que l’implémentation du modèle multi-phase dans le code, à l’aide de synchronisations, est correcte d’après un ordonnancement statique donné.La deuxième partie propose des techniques de construction et d’optimisation de profils multi-phase à partir des traces d'exécution d'une tâche. La première technique utilise l'estimation de densité par noyau avec pour objectif de grouper les instructions effectuant des accès dans des phases. À cette technique s'ajoutent des optimisations et corrections pour maximiser l’efficacité du profil durant l’analyse d’interférences, ainsi qu'une méthode pour sélectionner des synchronisations. Par la suite, nous proposons 2 méthodes basées sur des Algorithmes Génétiques (GA) respectivement pour créer et optimiser des profils. En effet, les GA sont adaptés aux problèmes multi-critères avec un large espace de solutions. Nous utilisons deux cas d'études pour comparer et évaluer les méthodes présentées.La dernière partie s'intéresse à l'ordonnancement statique des tâches multi-phase sur les architectures multi-cœur. Le problème est présenté avec une formulation ILP considérant des dépendances entre tâches et les possibles effets des interférences pour minimiser le pire temps de réponse du système. Ensuite, nous proposons des heuristiques avec différentes stratégies pour tirer profit du caractère multi-phase des tâches et inclure les effets des interférences. Enfin, nous menons une étude statistique avec des systèmes synthétiques pour comparer les méthodes dans différentes configurations et mesurer l'efficacité du modèle multi-phase. L'étude se poursuit avec 2 études de cas pour confronter les heuristiques à des formes de profils plus réalistes et de plus gros systèmes.
| Origine | Version validée par le jury (STAR) |
|---|