Pipeline logiciel

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Pipelining de boucle)

Le pipeline logiciel (software pipelining, par opposition aux pipelines matériels) est une technique utilisée par les compilateurs pour optimiser l'exécution des boucles. Elle consiste à superposer l'exécution de plusieurs itérations de la boucle, comme un pipeline matériel le fait pour les différentes phases des instructions : une itération du code généré contiendra en fait des instructions provenant de plusieurs itérations d'origine. Le but est de réorganiser les instructions de manière à pouvoir exécuter des instructions provenant d'autres itérations pendant que des instructions coûteuses s'exécutent.

Contrairement au déroulage de boucle, le compilateur cherche à optimiser les interactions entre plusieurs itérations de la boucle compilée, là où le déroulage ne permet que des optimisations locales après avoir dupliqué le code, qui sont limitées par le nombre de duplications.

Exemple d'application[modifier | modifier le code]

La boucle suivante pourra bénéficier du pipelining :

for(i=0; i<n; i++){
   C[i]=A[i]*B[i];
}

Sans pipelining, elle serait traduite dans un assembleur imaginaire sous la forme :

// RA, RB, RC contiennent les adresses des tableaux
// RI le compteur, initialisé à n (>0)
L:
    LOAD R1, RA++   // On charge dans un registre la valeur de l'élément du tableau A
    LOAD R2, RB++   // Pareil pour B
    MUL R3, R1, R2  // On multiplie les deux ; il faudra attendre le résultat plusieurs cycles
    STORE R3, RC++  // On stocke le résultat dans C
    RI--            // On décrémente le compteur
    BN0 RI, L       // Tant qu'il n'est pas nul, on boucle

Malheureusement, les instructions ne se terminent pas forcément toutes à la même vitesse. L'instruction de multiplication est relativement lente, et les instructions de chargement peuvent aussi prendre du temps. Un processeur qui exécuterait les instructions une à une dans l'ordre ne ferait rien tant que l'instruction de l'instruction de multiplication ne serait pas terminée, puisque l'écriture en mémoire a besoin de son résultat. Dans tous les cas, il lira une instruction qu'il ne pourra pas exécuter tout de suite. Le but du pipeline logiciel est d'intercaler un travail utile entre les deux.

Pour cette boucle, on pourrait déjà commencer à charger les éléments suivants du tableau, ce qui pourrait se faire pendant l'exécution de la multiplication. On aurait, si les tableaux sont séparés en mémoire :

    LOAD R1, RA++   // Prologue : On charge les valeurs correspondant à la première itération
    LOAD R2, RB++
    RI--            // On décrémente le compteur
    B0 RI, E       // S'il n'y avait qu'une seule itération, on saute directement à l'épilogue
L:
    MUL R3, R1, R2  // On multiplie les deux valeurs précédentes
    LOAD R1, RA++   // On charge dans un registre la valeur de l'élément suivant du tableau A
    LOAD R2, RB++   // Pareil pour B
    STORE R3, RC++  // On stocke le résultat courant dans C
    RI--            // On décrémente le compteur
    BN0 RI, L       // Tant qu'il n'est pas nul, on boucle
E:
    MUL R3, R1, R2  // Épilogue : On finit les calculs de la dernière itération
    STORE R3, RC++

Cette fois, l'attente du résultat de la multiplication permet tout de même d'exécuter des instructions. Par contre, on a dû rajouter un « prologue » et un « épilogue » pour faire les opérations restantes des premières et dernières itérations.