Tous droits réservés

Trivial Computation et simplification matérielle des calculs

Utiliser le renommage de registres et certaines opérandes pour simplifier des calculs en hardware

Publié :

Le meilleur moyen pour gagner en performance, c'est avant tout de ne pas faire de calcul inutiles. A ce petit jeu, les compilateurs tentent toujours de calculer un maximum de choses lors de la compilation, grâce à des optimisations basées sur un bon usage des constantes.

Certains calculs dont toutes les opérandes sont constantes sont réalisés à la compilation, histoire d'éviter au processeur de travailler pour rien. De même, le compilateur peut simplifier certains calculs (multiplication par 0 ou 1, addition avec 0, etc). L'usage de constant folding ou de la propagation de constante est parfois aidé par certaines fonctionnalités des langages de programmation (mot-clé const, constexpr du C++, immutabilité des variables dans les langages fonctionnels, etc).

Mais aussi bizarre que cela puisse paraitre, cela ne suffit pas. Des expériences menées sur des benchmarks connus (SPEC 95) ont montré que de nombreuses simplifications peuvent être faites à l'exécution. Le premier papier sur le sujet est "Caching Function Results: Faster Arithmetic by Avoiding Unnecessary Computation" par Richardson, en 1992. Il a été suivi par les mesures réalisées dans l'étude "Improving Processor Performance by Simplifying and Bypassing Trivial Computations" de Joshua Yi et David Lilja : ces mesures montrent qu'à l’exécution, les calculs simplifiables comme des multiplications par 0, 1, 2, ou des additions avec 0 sont monnaie courantes.

De nos jours, il existe des tentatives pour simplifier ces calculs à l’exécution, au niveau matériel : ce sont des techniques de Trivial Computation.

Instructions simplifiables

Quand on parle d'instructions simplifiables, il faut faire la distinction entre instructions inutiles, et instructions simplifiables. Dans le premier cas le résultat est connu à partir des opérandes du calcul à faire : le calcul est inutile, et le résultat vaut soit zéro, soit une des opérandes. Dans l'autre cas, le calcul peut être remplacé par un calcul plus simple.

Typiquement, les instructions qui peuvent être supprimées sont :

  • les décalages par zéro ;
  • les additions et soustractions avec zéro ;
  • la multiplication par 0, 1 ;
  • les divisions du style 0 / Y, ou X/X ;
  • les opérations bit à bit avec 0 ou la valeur entière maximale : X ET 0 donne toujours 0, X OU 0 donne toujours X, etc.

Les calculs simplifiables correspondent aux multiplication et division par une puissance de deux, qui se simplifient en décalages.

Dans ce qui va suivre, nous allons uniquement parler du premier cas : les instructions peuvent être supprimées, et le résultat est une des opérandes du calcul supprimé. On peut remarquer que ces calculs correspondent dans la plupart des cas à des calculs dont une opérande vaut zéro ou 1. Nous nous limiterons à ces calculs.

Trivial Computation

La détection des calculs simplifiable est assez simple : il suffit de comparer les opérandes avec zéro ou 1. Cela permet de détecter la majorité des calculs simplifiables. En somme, détecter les calculs à simplifier demande juste d'utiliser un paquet de comparateurs, comparateurs qui sont regroupés dans une unité de détection des calculs triviaux.

Ces calculs simplifiables peuvent être détectés à deux endroits du processeur :

  • soit directement en entrée de l'unité de calcul ;
  • soit lors de l'étape de décodage.

Ce qui fait que les entrées de l'unité de calcul (ou les reservations stations) sont reliées à l'unité de détection.

Quand un calcul simplifiable est détecté à l'entrée de l'unité de calcul, on sait que le résultat vaut soit zéro, soit une des opérandes. A ce moment, l'unité de calcul ne va pas effectuer le calcul : elle va bypasser soit zéro, soit l'opérande en sortie de l'unité de calcul.

Il faut aussi agir sur la table de renommage de registre. Si le résultat du calcul simplifié est une des opérandes, le registre de destination de l'instruction simplifiée est renommé pour pointer sur l'opérande : la correspondance registre virtuel -> registre physique va maintenant pointer sur le registre source qui contient l’opérande résultat.

Si le résultat est nul, on considère que la correspondance est invalide et on met le registre physique à une valeur invalide, similaire au pointeur null du C. Si, lors du renommage, un calcul lit comme registre physique la valeur invalide, celui-ci sera automatiquement simplifié par l'unité de renommage : le registre physique qui correspond à l'autre opérande sera attribué automatiquement comme registre de destination du résultat dans la table de renommage.

Défauts

Généralement, cette technique a tout de même des problèmes. Il faut savoir que les circuits qui se chargent de décider quelle instruction envoyer aux unités de calcul à chaque cycle (Issue), n'aiment pas les latences variables : pour eux, il vaut mieux connaitre à l'avance le temps d’exécution d'une instruction. C'est d'autant plus vrai sur certains pipelines, comme les pipelines à replay.

En effet, il arrive qu'une instruction simplifiée envoie son résultat au register file plus tôt que ce que l'unité d'Issue avait prévu. Dans ce cas, le résultat entre parfois en conflit avec une autre instruction pour l'accès au register file. Seule solution : mettre en attente le résultat de l'instruction simplifiée. Mais même avec ce problème, la simplification a des avantages : cela libère l'unité de calcul.

Mais le problème est aussi que si jamais le scheduler prévoit une certaine latence pour l'instruction, il vaut mieux qu'elle soit respectée : dans le cas contraire, l'ordre des écritures dans un registre peut changer. Si jamais un registre est écrit par deux instructions, en simplifier une peut faire que l'instruction simplifiée écrit dans le registre avant l'autre. Si cela arrive, le contenu du registre sera invalide. Dans ce cas, une seule solution : détecter les problèmes, et vider le pipeline en cas de détection (comme pour une mauvaise prédiction de branchements).


4 commentaires

L'article de ce que j'en ai compris est assez intéressant, mais pour tout saisir j'ai l'impression qu'il faut avoir fait un peu de langage d'assemblage non ? T'aurais des tutos / cours / bouquins pas trop long pour apprendre un peu le vocabulaire que t'emploie ? Merci d'avance pour ta réponse ! :)

Tous les crétois sont menteurs. Livres Recommandés : C++ Primer 5, SFML Game Development

+0 -0

C'est pas de connaissances en langage d'assemblage qu'il faut pour comprendre cet article, mais de connaissances sur la microarchitecture d'un processeur.

Je conseille la lecture des derniers chapitres de mon tutoriel Fonctionnement d'un ordinateur depuis zéro, dans la partie "Le parallélisme d'instruction et les processeurs modernes". C'est la seule ressource en francais que je connaisse sur le sujet, et elle est assez complète.

Édité

+0 -0

Un petit schéma d'un flux d'exécution/décision serait pas mal pour se rendre compte facilement du charabia :) Ou alors mettre un lien vers ton tuto sur les architectures car tu rentre dans le vif du sujet sans trop de préambule et vu le titre il y a parfois des ambiguités pour quelqu'un qui ne s'y connait pas trop ;)

+0 -0
Staff

J'ai pas vraiment tout compris (je ne connait rien au fonctionnement des compilateurs), mais ça à l'air vraiment intéressant.

(Ceci est un « bon article ! » déguisé.)

Hier, dans le parc, j'ai vu une petite vieille entourée de dinosaures aviens. Je donne pas cher de sa peau.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte