Compression et prédiction de branchement

Philippe Clauss & Alain Ketterlin

Présentation

Les architectures des microprocesseurs contemporains sont en général structurées selon un pipeline. L'exécution d'une instruction y est réalisée étape par étape et, pour augmenter l'efficacité, l'exécution d'une instruction commence avant la fin de celle qui la précède. Un processus pipeliné comporte N étapes, et est donc à tout moment en train d'exécuter N instructions simultanément, chaque instruction se trouvant à une étape différente de son exécution.

C'est du moins la situation idéale que l'on aimerait atteindre. Malheureusement, certaines instructions (ou certains effets d'instruction) empêchent que ce dispositif soit utilisé à son maximum. Par exemple, si l'instruction est un branchement conditionnel on ne peut pas être sûr que l'instruction suivante sera effectivement exécutée. On peut dans ce cas soit bloquer le pipeline (c'est-à-dire ne pas commencer à exécuter l'instruction suivante), soit se préparer à annuler les effets des premières étapes des instructions suivant le branchement, et ceci jusqu'à ce que le branchement conditionnel arrive à l'étape où son résultat (pris ou pas pris) soit connu. Dans les deux cas, la perte de temps est importante, à un point tel que l'avantage du pipeline est presque annulé.

Il est donc très utile de pouvoir prédire le résultat d'un branchement dès le début de son exécution. Si on arrive à prédire ce résultat correctement dans 90% des cas par exemple, le temps perdu lié à l'aléa de branchement est divisé par 10. Bien sûr il n'est pas possible de prédire un résultat correct dans 100% des cas, parce que cela signifierait qu'on a une connaissance parfaite du comportement du programme, et donc qu'il n'est plus nécessaire de l'exécuter. De plus, dans une architecture réelle, on dispose de peu d'information pour faire une prédiction (en général quelques bits ou quelques octets de mémoire). Dans un premier, nous ignorerons les contraintes matérielles, et nous autoriserons par exemple une mémoire arbitrairement large, mais nous resterons dans le cas où le prédicteur n'a pas accès au reste de l'état du processeur : il est donc seul chargé de gérer sa mémoire, et d'y conserver les informations qui peuvent lui être utiles.

Les branchements sont les seules instructions qui modifient le déroulement d'un programme. On considère donc que les seules informations nécessaires à la prédiction sont les résultats soit des branchements précédents, soit des précédentes exécutions du branchement dont on essaie de prédire le résultat. Nous resterons dans ce schéma, sans décider au préalable des branchements à considérer où à ignorer. Une partie du travail consistera à déterminer les critères à utiliser pour obtenir les meilleurs résultats de prédiction.

Problématique

On peut modéliser le problème de la façon suivante : étant donné un historique des branchements récents :

(a₁,r₁), (a₂,r₂) ... (a_n,r_n)

et un nouveau branchement donné par son adresse a_n+1, il s'agit de prédire le résultat r_n+1. Dans ces notations :

• a_i est l'adresse de l'instruction de branchement. Dans un programme donné, nous ne trouverons en général qu'entre quelques dizaines et quelques milliers d'adresses différentes. De plus, pour chaque adresse nous savons s'il s'agit d'un branchement inconditionnel (tel qu'un appel de fonction) qui est donc toujours pris, ou d'un branchement conditionnel (un if ou la fin d'une boucle par exemple).

• r_i est le résultat du branchement, à savoir un bit indiquant si le branchement a été pris ou pas.

Il existe beaucoup de techniques de prédiction de branchement, et le travail commencera par une rapide étude bibliographique permettant de catégoriser les techniques utilisées.

Démarche

L'idée centrale de ce travail est la suivante : si on dispose d'un historique H=(a₁,r₁) ... (a_n,r_n), on peut construire deux « :futurs historiques » :

1. H₀ = (a₁,r₁) ... (a_n,r_n) (a_n+1,0)

2. H₁ = (a₁,r₁) ... (a_n,r_n) (a_n+1,1)

correspondant aux deux résultats possibles. Si le résultat dépend de l'historique, alors les compressions des deux historiques H₀ et H₁ doivent fournir des résultats de longueurs différentes, puisque le résultat exact est plus cohérent avec H. Cela suppose bien sûr que la technique de compression utilisée sache tirer parti des régularités dans les comportement des branchements. Mais cela devrait être le cas, puisque c'est le principe même de la plupart des méthodes de compression. Notre prédicteur de branchement va donc se contenter de prédire la valeur qui fournit un « futur historique » qui se compresse mieux que son concurrent.

(Nous avons fait une première tentative de mise en oeuvre de cette idée, en utilisant l'infrastructure proposée par le Championship Branch Prediction pour la simulation à base de traces, et une bibliothèque de compression populaire (zlib). Les résultats sont très mauvais... Cependant, ils ne nous permettent pas d'affirmer que le raisonnement est fautif, simplement que la mise en oeuvre a une importance. Dans le cas présent, la méthode de compression utilisée considère ses données octet par octet, alors que nos données sont constituées d'une part de mots de 32 bits (pour les adresses) et d'autre de simples bits (pour le résultat). Il y a donc bien un biais de représentation, largement négatif dans notre cas.)

Travail à réaliser

Le but de ce TER est donc de retenter l'expérience mentionnée ci-dessus de façon plus raisonnée. Il faut pour cela :

• Déterminer un codage adapté des informations disponibles (adresse et résultat). Les possibilités immédiates sont un codage sur 33 bits, le hachage de l'adresse sur N bits auquel on ajoute un bit pour le résultat, une numérotation explicite des branchements et l'utilisation du nombre de bits nécessaires à leur identification, etc. Bien sûr, d'autres possibilités pourront (devront ?) être explorées.

• La programmation de certains algorithmes de compression, de façon à respecter le codage défini, c'est-à-dire à ne pas agglomérer ou scinder arbitrairement les éléments de l'historique. Les algorithmes envisagés sont :

  • Un codage de Huffman adaptatif

  • Une variante (à déterminer) de l'algorithme de Lempel et Ziv (utilisé entre autres dans compress et gzip)

  • la compression par rotation de blocs de Burrows et Wheeler (utilisée dans bzip2).

  Une mise en oeuvre portable et réutilisable de ces algorithmes sera nécessaire.

• Une analyse systématique de l'effet des différents paramètres (codage et algorithme, ainsi que des paramètres spécifiques aux algorithmes) sur la qualité de la prédiction.

• Enfin, si le temps le permet, on pourra envisager d'utiliser la même stratégie de prédiction dans d'autres contextes, par exemple, la prédiction d'accès à la mémoire.

Ce TER est prévu pour un ou deux étudiants. Quelques connaissances de base sont nécessaires (sur l'architecture des ordinateurs en particulier), mais le travail portera surtout sur les méthodes de compression (en particulier la famille LZ et l'algorithme de Burrows-Wheeler).