Contribution to the compilation of irregular programs for complex architectures

Contribution à la compilation de programmes irréguliers pour des architecturescomplexesLes architectures multicoeurs sont omniprésentes dans les processeurs généralistes et embarqués. Plusieurs flôts d'instructions (threads) sont exécutés, augmentant le parallélisme, évitant des contentions de ressources.L'execution concurrente d'un thread est déterminant pour le temps d'execution de l'application. Ainsi, l'exploitation fine d'un coeur est indispensable afin de découvrir du parallelisme d'instructions (ILP) au sein d'un flot d'instructions.Cette thèse traite de l'optimisation monocoeur de codes irréguliers comportant du parallélisme "caché". Nous avons conçus des transformations permettant d'augmenter leur ILP : Deep Jam convertissant du parallelisme à gros grain,restructuration des arbres de décisions et une plateforme d'ordonnancement d'instructions unifiant les dépendences de données et les contraintes de ressources complexes. Des accélérations par rapport à des techniques et compilateurs de pointe ont été obtenues sur Itanium 2.Contribution to the Compilation of Irregular Programs for Complex ArchitecturesMulticore architectures are ubiquitous in general purpose and embedded systems. Modern processors execute several instruction flows (threads) increasing the parallelism and accommodating for resource stalls. Both the execution of a thread and its interaction with the others shape the overall performance of an application. Thus, an accurate exploitation of a single core is mandatory: it leads to the necessity to discover the instruction-level parallelism (ILP) within an instruction flow.This thesis focuses on the monocore optimization of irregular codes hoseparallelism is "hidden" behind complex control flow. We designedtransformations to increase their ILP: Deep Jam converting coarse-grain parallelism, decision tree reshaping and an instruction-scheduling framework unifying data dependences and complex resource constraints. Everytransformation leads to significant speedups on a wide issue architecture(Itanium), compared to state-of-the-art techniques and compilers.VERSAILLES-BU Sciences et IUT (786462101) / SudocSudocFranceF