Fonctionnement d'un ordinateur/Dépendances structurelles

Un livre de Wikilivres.

Il se peut qu'un circuit du processeur doive être manipulé par plusieurs instructions à la fois. Par exemple, deux instructions peuvent ainsi vouloir utiliser l'unité de calcul ou accéder à la mémoire simultanément. Et à moins que le circuit en question soit conçu pour, une seule instruction aura accès au circuit demandé. Le processeur fait alors face à une dépendance structurelle, qui se résout en arbitrant l'accès au circuit. Une instruction a accès au circuit alors que les autres sont mises en attente. Le processeur peut gérer une telle situation de lui-même, s'il est conçu pour.

Le cas des pipelines sans boucle[modifier | modifier le wikicode]

Les étages du pipeline sont censés être indépendants, chacun possédant ses propres circuits, ce qui fait que les dépendances structurelles ne sont pas censées exister. Mais il n'est pas rare que les concepteurs de processeurs laissent des dépendances structurelles pour économiser des transistors. C'est notamment le cas pour ce qui est de la gestion des instructions multi-cycles (qui prennent plusieurs cycles pour s’exécuter). Dans les grandes lignes, il existe trois grandes solutions pour résoudre ces dépendances structurelles : la duplication de circuit, l'échelonnement et l'insertion de bulles de pipeline.

L'échelonnement[modifier | modifier le wikicode]

La première solution consiste à pipeliner, échelonner les instructions. Si jamais vous avez une opération qui prend cinq cycles, pourquoi ne pas lui fournir un seul circuit et l’échelonner en cinq étages ? Pour certains circuits, c'est possible : on peut totalement échelonner une unité de multiplication, par exemple. En faisant ainsi, il est possible de démarrer une nouvelle multiplication à chaque cycle d'horloge dans la même ALU, éliminant ainsi toute dépendance structurelle. Cependant, certaines instructions s’échelonnent mal, notamment les divisions chaque étage peut prendre 10 à 20 cycles pour s’exécuter. Il faut alors trouver une autre solution pour ces instructions.

Exemple avec une unité de multiplication séparée, totalement pipelinée.

La duplication de circuits[modifier | modifier le wikicode]

La seconde solution consiste à dupliquer les unités de calcul. Ainsi, si une instruction bloque une ALU durant plusieurs cycles, on peut exécuter d'autres instructions de calcul dans une autre ALU. En théorie, on peut supprimer toute dépendance structurelle totalement en utilisant autant d'unités de calcul qu'une instruction met de cycles pour s’exécuter. Prenons un exemple : toutes mes instructions arithmétiques prennent un cycle, à part la multiplication qui prend cinq cycles et la division qui prend quarante cycles. Je peux supprimer toute dépendance structurelle en utilisant une ALU pour les opérations en un cycle, cinq ALU capable de faire une multiplication, et quarante ALU dédiées aux divisions.

Les statistiques montrent qu'il est rare que deux opérations nécessitant plusieurs cycles d’horloge se suivent dans un programme, ce qui fait que les unités de calcul sont rarement présentes en un nombre important d'exemplaires. La plupart des processeurs se limitent à utiliser un aval spécialisé pour les opérations en plusieurs cycles, à côté d'une unité de calcul dédiée aux opérations en un seul cycle.

Les bulles de pipeline[modifier | modifier le wikicode]

La dernière technique consiste à laisser la gestion des dépendances au séquenceur. Sur toutes les instructions qui bataillent pour accéder au circuit, une instruction a accès au circuit, les autres étant mises en attente. Pour cela, les dépendances structurelles entre instructions sont vérifiées à l'émission.

Une première solution consiste à déterminer les paires d'instructions consécutives qui peuvent donner lieu à des dépendances structurelles. Par exemple, si une instruction de multiplication de cinq cycles est dans le pipeline, je sais que je ne peux pas démarrer de nouvelle multiplication immédiatement après, vu qu'il n'y a qu'un seul multiplieur. Détecter les dépendances structurelles consiste à comparer l'opcode de l'instruction à émettre, avec les opcodes des instructions en cours d’exécution dans le pipeline. Si jamais l'opcode de l'instruction à émettre et une opcode dans le pipeline forment une paire d'opérations interdite, il y a dépendance structurelle. En conséquence, l'instruction à émettre est bloquée, et l'unité d'émission insère des NOP dans le pipeline. Si jamais l'unité de calcul est échelonnée, on peut adapter ce principe en retirant certains étages du processus de comparaison.

Une autre solution est de connaître, pour chaque unité, le temps nécessaire avant de pouvoir lancer une nouvelle instruction dans l'aval. Les instructions ayant des durées fixées, quelques compteurs dans le séquenceur permettent de dire dans combien de temps telle ou telle unité de calcul sera libre. Seules les instructions d'accès mémoire, seules à avoir des temps de latence variable, sont gérées différemment. Pour les accès mémoire, c'est l'unité de gestion mémoire qui indique si elle est libre : elle génère un bit MEM_FREE qui dira si la mémoire est accessible ou non. L'unité d'émission aura jute à vérifier ce signal pour savoir si elle peut émettre une nouvelle instruction d'accès mémoire.

Le cas des pipelines avec boucles[modifier | modifier le wikicode]

Certains pipelines sont un peu plus compliqués, et contiennent des boucles : certains étages peuvent envoyer leur résultat à des étages précédents. Alors certes, les pipelines de ce type sont très rares, mais ils existent. Avec des boucles, la gestion des dépendances structurelles devient beaucoup plus compliquée, et diverses solutions existent. Toutes ces solutions consistent à envoyer des bulles de pipeline au bon moment.

Le registre de décalage de contrôle[modifier | modifier le wikicode]

Ces solutions se basent sur des tables de réservation, des tables dans lesquelles on indique quel étage est occupé par une instruction, et à quel moment.

Par exemple, le pipeline suivant…

Exemple de pipeline avec une boucle.

… aura la table de réservation suivante.

Étage 1 Étage 2 Étage 3 Étage 4
X - - -
- X - -
X - - -
- X - -
- - X -
- - - X

Supposons que je lance une instruction dans le pipeline à un temps t0. Par la suite, k cycles plus tard, je veux lancer la même instruction dans le pipeline. Pour détecter les collisions, il me suffit de prendre la table de l'instruction en deux exemplaires : un pour l'instruction lancée à t0 et un autre décalé de k cycles, qui correspond à l'instruction qu'on veut émettre.

Nous allons supposer que l'on lance deux instructions à la suite dans le pipeline. Dans la table de réservation, on voit bien qu'il n'y a pas de conflit : les instructions occupent des étages différents à chaque instant.

Étage 1 Étage 2 Étage 3 Étage 4
X - - -
x X - -
X x - -
x X - -
- x X -
- - x X
- - - x

Maintenant, supposons que les instructions soient lancées à deux cycles d'intervalle. La table de réservation est alors celle-ci. On le voit clairement : certains étages sont occupés par plusieurs instructions, ce qui n'est pas possible. En clair : il n'est pas possible de démarrer une nouvelle instruction deux cycles après une autre.

Étage 1 Étage 2 Étage 3 Étage 4
X - - -
- X - -
X x - - -
- X x - -
x - X -
- x - X
- - x -
- - - x

Fort heureusement, le processeur n'a pas à calculer lui-même la possibilité de conflits en utilisant des tables de réservation. Il peut précalculer les latences autorisées et interdites entre deux instructions dans ce qu'on appelle un vecteur de collision. Pour un pipeline de n étages, ce vecteur de collision est un simple ensemble de n bits, numérotés de 1 à n, le bit numéro x indiquant si il y a conflit entre deux instructions émises à x cycles d'intervalle. Par exemple, le bit 1 indiquera si on peut démarrer deux instructions consécutives, le bit 2 indiquera si on peut lancer une nouvelle instruction deux cycles plus tard, etc. Ce vecteur de collision est précalculé pour chaque aval du processeur, et est ensuite utilisé par l'unité d'émission pour déterminer si une nouvelle instruction peut être émise. Avec une méthode naïve, l'unité d'émission va regarder combien de cycles se sont écoulés depuis la dernière instruction émise dans l’aval : ce nombre de cycles sera noté n dans ce qui suit. Ensuite, il lui reste à regarder le n-ième bit du vecteur de collision : la nouvelle instruction doit être mise en attente s'il vaut zéro, et peut être émise s'il vaut 1.

Mais on peut légèrement optimiser le tout. Lors de l'émission d'une nouvelle instruction, un registre à décalage est initialisé avec le vecteur de collision. À chaque cycle, ce registre à décalage est décalé d’un cran vers la gauche. Ainsi, si ce registre a été initialisé il y a n cycles, alors c'est le n-ième bit qui sortira de ce registre. Le bit qui sortira de ce registre sera donc le bit qui indique si on peut émettre une nouvelle instruction. Malheureusement, ce registre seul ne marche pas : si on initialise le registre à décalage avec le vecteur de collision de l'instruction émise, alors son ancien contenu est perdu. Conséquence : il ne prend en compte que les dépendances avec la dernière instruction à avoir été émise, et pas celles émises avant. Pour résoudre ce problème, il faut mixer les vecteurs de collision de toutes les instructions précédentes. Pour cela, on doit rajouter un circuit qui mixe convenablement le vecteur de collision avec le contenu du registre à décalage. La solution consiste donc à faire un OU entre le vecteur de collision à ajouter dans le registre, et le contenu de ce registre.

Le diagramme d'état[modifier | modifier le wikicode]

En utilisant la technique du dessus, on n'obtient pas un résultat optimal. Dans certains cas, démarrer une instruction dès que possible peut ne pas être la meilleure solution, contrairement au fait d'attendre quelques cycles avant l'Issue. La raison est basée sur des mathématiques assez complexes, aussi je me permets de la passer sous silence. Il est toutefois possible d'obtenir un résultat meilleur en adaptant le circuit d'émission.

Le circuit d'émission est un circuit séquentiel, qui peut se décrire intégralement avec un graphe de transitions. Pour créer ce graphe, il faut commencer par créer un nœud contenant le vecteur de collision initial. Ce nœud représente le contenu du registre à décalage quand on vient tout juste de démarrer une instruction dans un pipeline / aval totalement vide. À partir de ce vecteur de collision, on pourra émettre des instructions après un certain nombre de cycles. Par exemple, on suppose que les latences autorisées sont 2, 3, 7, 8+ (8 et supérieur) : dans ce cas, on pourra émettre une nouvelle instruction 2, 3, 7, 8 cycles après une autre. Une fois ces instructions émises, le registre à décalage aura été modifié. Dans ce cas, on crée un nœud pour chaque latence autorisée, et on met le contenu du registre à décalage obtenu dans ce nœud. On numérote la flèche avec le nombre de cycles qui séparent les deux instructions. Et on recommence à partir de chacun des nœuds obtenu à cette étape. On poursuit ainsi de suite jusqu'à retomber sur un nœud déjà présent dans le graphe. Au bout d'un moment, on obtient alors le graphe de transition total.

Pour savoir comment gérer au mieux ces transitions, il faut trouver les boucles dans ce graphe qui partent du nœud de pipeline vide et qui retournent à ce nœud. La boucle idéale est celle dont la somme des numéros des flèches est la plus petite possible.

L'aval multifonction[modifier | modifier le wikicode]

Certains avals sont capables d'effectuer plusieurs opérations différentes : par exemple, on peut avoir un aval qui peut faire soit des multiplications, soit des divisions. Dans ces conditions, les techniques vues au-dessus doivent être améliorées un petit peu. Par exemple, la technique avec un registre à décalage et des portes OU peut être adaptée : il suffit de rajouter plusieurs registres à décalage, et quelques vecteurs de collision. Reprenons l'exemple avec un aval qui peut faire soit des multiplications, soit des divisions, on devrait utiliser deux registres à décalage : un pour autoriser l'émission des divisions, et un autre pour les multiplications. Techniquement, il faut autant de registres à décalages que l'on a d'instruction. Il faudrait aussi utiliser autant de vecteurs de collision qu'il y a de paires d'instructions possible (on lance une instruction après l'autre, ce qui donne une paire). Pour l'exemple avec multiplication et division, on aurait :

  • un des vecteurs de collision serait celui obtenu en superposant la table de réservation d'une addition suivie d'une multiplication ;
  • un autre serait obtenu en superposant la table de réservation d'une multiplication suivie d'une addition ;
  • un autre serait obtenu en superposant la table de réservation d'une multiplication suivie d'une multiplication ;
  • un autre serait obtenu en superposant la table de réservation d'une addition suivie d'une addition.