Thesis defence of Pierre Ravenel (MADMAX team): Improving the performance of in-order processors under hardware complexity constraints

Pierre RAVENEL - MADMAX team

Thesis direction
Frédéric PÉTROT - Thesis director - Full professor - TIMA Laboratory
Arthur PERAIS - Thesis co-supervisor - Researcher - TIMA Laboratory
Benoît DUPONT DE DINECHIN - Thesis co-supervisor - Engineer - KALRAY

Rapporteurs
Steven DERRIEN - Rapporteur - Full professor - Université Bretagne Occidentale
Thomas CARLE - Rapporteur - Associate professor - Université de Toulouse

Composition of the jury
Frédéric PÉTROT - Thesis director - Full professor - TIMA Laboratory
Steven DERRIEN - Rapporteur - Full professor - Université Bretagne Occidentale
Thomas CARLE - Rapporteur - Associate professor - Université de Toulouse
Abdoulaye GAMATIÉ - Examinator - Research Director - CNRS Occitanie Est
Claire MAIZA - Examinator - Associate professor - Grenoble INP - UGA
Pierre MICHAUD - Examinator - Researcher - Centre de l'INRIA de l'Université de Rennes
Arthur PERAIS - Guest - Researcher - TIMA Laboratory
Benoît DUPONT DE DINECHIN - Guest - Engineer - KALRAY

Title: Improving the performance of in-order processors under hardware complexity constraints 
Keywords: Processors, In-Order Execution, Hardware Complexity, Value Prediction, Scheduling,
Abstract: The sequential performance of processors is and will remain a necessity in the design of future generations of circuits. Indeed, even though a large portion of modern programs is parallelizable and can execute on dedicated components, orchestration will always occur through a central processor. This idea is supported by Amdahl’s law, which states that even with infinite parallel computing power, the performance bottleneck will always be the sequential portion. However, it is not always desirable to build ever-larger processors, whose costs increase quadratically relative to the performance gains achieved. Today, we observe a convergence of design methods between simple embedded processors and high-performance superscalar, out-of-order machines. The objective, therefore, is to reconcile performance and energy efficiency—that is, to achieve more with limited resources. This thesis is situated in this context and proposes, through clever mechanisms, a transition from a simple, in-order, processor to an enhanced version capable of executing complex modern applications without relying on the traditional methods used in current high-performance processors, such as dynamic scheduling or full register renaming, which require a significant increase in internal buffer sizes and reduce power efficiency. Rather than building expensive hardware, we exploit the intrinsic characteristics of modern programs to circumvent the hardware bottlenecks that limit performance. Indeed, in-order processors are particularly affected by memory access latencies, which account for the majority of lost cycles during execution. In this context, this thesis proposes two innovative techniques to overcome this limitation. The first consists of value prediction, allowing the execution of younger instructions to proceed with a speculated value. If the prediction is correct, the speculative execution is valid, effectively hiding memory-related stalls. The second consists of reordering instructions to separate dependent operations. By applying a dataflow–based reordering to static instructions without considering dynamic latencies, it becomes possible for older instructions to execute before younger instructions that would otherwise be stalled. Finally, this work presents techniques that significantly improve performance while remaining minimally intrusive to the processor pipeline, both in terms of additional pipeline stages and logic layers between stages, thereby avoiding impacts on critical paths and increasing performance at a constant clock frequency.

Titre : Amélioration de la performance des processeurs à exécution dans l’ordre sous contrainte de complexité matérielle
Mots-clés : Processeurs, Prédiction de valeur, Complexité matérielle, Ordonnancement
Résumé : La performance séquentielle des processeurs est et restera une nécessité dans la conception des futures générations de circuits. En effet, même si une grande partie des programmes modernes est parallélisable et peut s’exécuter sur des composants dédiés, l’orchestration se fera toujours via un processeur central. Ce principe est à la base de la loi d’Amdahl, qui stipule que, même si l’on dispose d’une puissance de calcul parallèle infinie, la partie limitante en terme de performance restera la partie séquentielle. Cependant, il n’est pas toujours souhaitable de construire des processeurs toujours plus gros, dont les coûts augmentent de manière quadratique vis-à-vis du gain de performance apporté. Ainsi, nous assistons aujourd’hui à une convergence entre les processeurs embarqués de conception simple et les machines superscalaires à exécution dans le désordre visant la haute performance. L’objectif ici est donc de concilier performance et efficacité énergétique, c’est-à-dire atteindre de meilleures performances avec des ressources limitées. Cette thèse s’inscrit dans ce contexte et propose, à partir de mécanismes astucieux, de passer d’un processeur à exécution dans l’ordre de conception simple à une version enrichie capable d’exécuter des applications modernes complexes sans recourir aux méthodes traditionnellement utilisées dans les processeurs haute performance actuels, telles que l’ordonnancement dynamique ou le renommage complet, qui nécessitent une augmentation significative de la taille des tampons internes et entraînent une baisse importante de l’efficacité énergétique. Plutôt que de construire du matériel coûteux, nous avons exploité les caractéristiques intrinsèques des programmes modernes pour contourner les goulots d’étranglement matériels qui limitent la performance. En effet, les processeurs à exécution dans l’ordre souffrent particulièrement des latences d’accès mémoire, qui représentent la majeure partie des cycles perdus lors de l’exécution. Dans ce cadre, cette thèse propose deux techniques innovantes permettant de limiter l'impact de ces latences. La première consiste en une prédiction de valeurs, permettant de débloquer l’exécution des instructions plus jeunes avec la valeur spéculée. Si la prédiction est correcte, l’exécution spéculative est valide et les cycles perdus à cause de la latence mémoire sont masqués. La seconde consiste à réordonner les instructions de façon à éloigner celles qui sont dépendantes. Grâce à un réordonnancement basé sur le flux de données appliqué aux instructions statiques, sans tenir compte des latences dynamiques, il est possible de permettre à des instructions plus anciennes de s’exécuter avant les instructions plus jeunes qui seraient bloquées. Finalement, dans ce travail nous proposons des techniques permettant d’augmenter significativement la performance tout en restant peu intrusives sur le pipeline du processeur, à la fois en nombre d’étages supplémentaires et en couches logiques entre les étages, afin de préserver les chemins critiques et ainsi améliorer la performance à fréquence constante.