Méthodes efficaces de parallélisation de l'analyse de traces noyau

Les architectures hautement parallèles sont de plus en plus répandues, non seulement dans les systèmes haute-performance, mais aussi dans les ordinateurs grand public. La détection et la résolution de problèmes lors de l'exécution parallèle de logiciels sur ces types de systèmes sont des tâches complexes auxquelles les outils classiques de débogage ne sont pas adaptés. Des études précédentes ont démontré que le traçage s'avère être une solution efficace à la résolution de problèmes dans des systèmes hautement parallèles. Cependant, l'augmentation du nombre d'unités parallèles dans les systèmes tracés cause aussi une augmentation de la quantité de données générées par le traçage. Les architectures distribuées ne font qu'exacerber ce problème puisque chaque nœud peut contenir plusieurs processeurs multicœurs. Les données de trace doivent être analysées par un outil d'analyse de traces afin de pouvoir extraire les métriques importantes qui permettront de résoudre les problèmes. Or, les outils d'analyse de traces disponibles sont conçus de manière à s'exécuter séquentiellement, sans tirer avantage des capacités d'exécution parallèle. Nous nous retrouvons donc face à une différence de plus en plus grande entre la quantité de données produite par le traçage et la vitesse à laquelle ces données peuvent être analysées. La présente recherche a pour but d'explorer l'utilisation du calcul parallèle afin d'accélérer l'analyse de traces. Nous proposons une méthode efficace de parallélisation de l'analyse de traces qui supporte la mise à l'échelle. Nous nous concentrons sur les traces en format CTF générées par le traceur LTTng sur Linux. La solution présentée prend en compte des facteurs clés de la parallélisation efficace, notamment un bon équilibrage de la charge, un minimum de synchronisation et une résolution efficace des dépendances de données. Notre solution se base sur des aspects clés du format de trace CTF afin de créer des charges de travail équilibrées et facilement parallélisables. Nous proposons aussi un algorithme permettant la détection et la résolution de dépendances de données, pendant l'analyse de traces, qui utilise au minimum le verrouillage et la synchronisation entre les fils d'exécution. Nous implémentons trois analyses de traces parallèles à l'aide de cette solution : la première permet de compter les événements d'une trace, la seconde de mesurer le temps CPU utilisé par processus et la troisième de mesurer la quantité de données lues et écrites par processus. Nous utilisons ces analyses afin de mesurer la mise à l'échelle possible de notre solution, en utilisant le concept d'efficacité parallèle. Puisque les traces peuvent être potentiellement très volumineuses, elles ne peuvent être gardées en mémoire et sont donc lues à partir du disque. Afin d'évaluer l'impact de la performance des périphériques de stockages sur notre implémentation parallèle, nous utilisons un programme simulant des charges de travail sur le CPU et sur le disque, typiques de l'analyse de traces. Nous évaluons ensuite la performance de ce programme sur plusieurs types de périphériques de stockage, tels que des disques durs et des disques SSD, afin de démontrer que la performance de l'analyse parallèle de traces n'est pas gravement limitée par les accès au disque, surtout avec des périphériques de stockage modernes. Nous utilisons aussi ce programme afin d'évaluer l'effet d'améliorations futures au décodage de la trace, sur la mise à l'échelle de l'analyse parallèle. Notre solution offre une efficacité parallèle au-dessus de 56% jusqu'à 32 cœurs, lors de l'exécution de l'analyse de traces parallèle, ce qui signifie une accélération de 18 fois par rapport au temps de traitement séquentiel. De plus, les résultats de performance obtenus à partir du programme de simulation confirment que l'efficacité parallèle n'est pas sérieusement affectée par les accès au disque lorsque des périphériques de type SSD sont utilisés. Cette observation tient d'ailleurs même lorsque le décodage de la trace est plus rapide. Certains facteurs qui nuisent à la mise à l'échelle sont dus au modèle séquentiel de la bibliothèque de lecture de traces et peuvent être réglés avec une refonte de celle-ci, tandis que d'autres proviennent de goulots d'étranglement au sein du module de gestion de la mémoire du noyau et pourraient être améliorés ou contournés.

Abstract

Highly parallel computer architectures are now increasingly commonplace, whether in com- mercial or consumer-grade systems. Detecting and solving runtime problems, in software running in a parallel environment, is a complicated task, where classic debugging tools are of little help. Previous research has shown that tracing offers an efficient and scalable way to resolve these problems. However, as the number of parallel units in the traced system increases, so does the amount of data generated in the trace. This problem also compounds when tracing distributed systems, where each individual node may have many-core processors. Trace data has to be analyzed by a trace analysis tool, in order to extract significant metrics which can be used to resolve problems. However, the current trace analysis tools are designed for serial analysis on a single thread. We therefore have an ever widening gap between the amount of data produced in the trace and the speed at which we can analyse this data. This research explores the use of parallel processing in order to accelerate trace analysis. The aim is to develop an efficient and scalable parallel method for analyzing traces. We focus on traces in the CTF format, generated by the LTTng tracer on Linux. We present a solution which takes into account key factors of parallelization, such as good load balancing, low synchronization overhead and an efficient resolution of data dependencies. Our solution uses key aspects of the CTF trace format to create balanced, parallelizable workloads. We also propose an algorithm to detect and resolve data dependencies during trace analysis, with minimal locking and synchronization. Using this solution, we implement three trace analyses (counting events; measuring CPU time per-process; measuring amount of data read and written per-process) which we use in order to assess the scalability in terms of parallel efficiency. Traces, being potentially very large, are not kept entirely in memory and must be read from disk. In order to assess the effect of the speed of storage devices on the parallel implementation of trace analysis, we create a program that simulates the CPU and I/O workloads typical of trace analysis. We then benchmark this program on various storage devices (e.g. HDD, SSD, etc.) in order to show that parallel trace analysis is not seriously hindered by I/O-boundedness problems, especially with modern storage hardware. We also use this program in order to assess the effect of future improvements in trace decoding on the analysis. Our solution shows parallel efficiency above 56% up to 32 cores, when running the parallel trace analyses, which translates to a speedup of 18 times the serial speed. Furthermore, benchmarks on the simulation program confirm that these efficiencies are not seriously affected by disk I/O on solid state devices, even in the case of faster trace decoding. Some factors affecting scalability are found within the serial design of the tracing library and can be fixed by a re-design, while others come from bottlenecks within the memory management unit of the kernel which could be improved or worked around.