performance - écoulées - optimiser code c




Pourquoi introduire des instructions MOV inutiles accélérer une boucle serrée dans l'assemblage x86_64? (3)

Préparation du cache

Le déplacement des opérations en mémoire peut préparer le cache et accélérer les opérations de déplacement ultérieures. Un processeur a généralement deux unités de chargement et une unité de stockage. Une unité de chargement peut lire de la mémoire dans un registre (une lecture par cycle), une unité de stockage stocke du registre à la mémoire. Il existe également d'autres unités qui effectuent des opérations entre les registres. Toutes les unités travaillent en parallèle. Ainsi, à chaque cycle, nous pouvons effectuer plusieurs opérations à la fois, mais pas plus de deux chargements, un magasin et plusieurs opérations de registre. Habituellement, il y a jusqu'à 4 opérations simples avec des registres simples, jusqu'à 3 opérations simples avec des registres XMM / YMM et 1-2 opérations complexes avec n'importe quel type de registres. Votre code a beaucoup d'opérations avec des registres, donc une opération de stockage de mémoire factice est libre (puisqu'il y a plus de 4 opérations de registre de toute façon), mais il prépare le cache mémoire pour l'opération de stockage suivante. Pour connaître le fonctionnement des mémoires, reportez-vous au Manuel de référence de l'optimisation des architectures Intel 64 et IA-32 .

Briser les fausses dépendances

Bien que cela ne se réfère pas exactement à votre cas, mais parfois en utilisant des opérations mobiles 32 bits sous le processeur 64 bits (comme dans votre cas) sont utilisés pour effacer les bits supérieurs (32-63) et briser les chaînes de dépendance.

Il est bien connu que sous x86-64, l'utilisation d'opérandes de 32 bits efface les bits les plus élevés du registre de 64 bits. Veuillez lire la section appropriée - 3.4.1.1 - du Manuel du développeur de logiciels pour architectures Intel® 64 et IA-32 Volume 1 :

Les opérandes de 32 bits génèrent un résultat de 32 bits, étendu à zéro à un résultat de 64 bits dans le registre d'usage général de destination

Ainsi, les instructions mov, qui peuvent sembler inutiles au premier coup d'œil, effacent les bits les plus hauts des registres appropriés. Qu'est-ce que ça nous donne? Il casse les chaînes de dépendances et permet aux instructions de s'exécuter en parallèle, dans un ordre aléatoire, grâce à l' algorithme Out-of-Order implémenté en interne par les processeurs depuis Pentium Pro en 1995.

Une citation du manuel de référence sur l'optimisation des architectures Intel® 64 et IA-32 , section 3.5.1.8:

Les séquences de code qui modifient le registre partiel peuvent rencontrer un certain retard dans sa chaîne de dépendance, mais peuvent être évitées en utilisant des idiomes de rupture de dépendance. Dans les processeurs basés sur la micro-architecture Intel Core, un certain nombre d'instructions peuvent aider à éliminer la dépendance d'exécution lorsque le logiciel utilise ces instructions pour effacer le contenu du registre à zéro. Rompez les dépendances sur les parties de registres entre les instructions en opérant sur des registres 32 bits au lieu de registres partiels. Pour les mouvements, cela peut être accompli avec des déplacements de 32 bits ou en utilisant MOVZX.

Règle de codage de l'assemblage / compilateur 37. (Impact M, généralité MH) : Rompre les dépendances sur les parties de registres entre les instructions en opérant sur des registres de 32 bits au lieu de registres partiels. Pour les mouvements, cela peut être accompli avec des déplacements de 32 bits ou en utilisant MOVZX.

Le MOVZX et le MOV avec des opérandes de 32 bits pour x64 sont équivalents - ils cassent tous les chaînes de dépendances.

C'est pourquoi votre code s'exécute plus rapidement. S'il n'y a pas de dépendances, le CPU peut renommer les registres en interne, même si au premier coup d'oeil, il peut sembler que la seconde instruction modifie un registre utilisé par la première instruction, et les deux ne peuvent pas s'exécuter en parallèle. Mais en raison de l'inscription de renommer, ils peuvent.

Le renommage de registre est une technique utilisée en interne par une unité centrale qui élimine les fausses dépendances de données résultant de la réutilisation de registres par des instructions successives qui n'ont pas de véritables dépendances de données entre elles.

Je pense que vous voyez maintenant que c'est trop évident.

Contexte:

Tout en optimisant du code Pascal avec un langage d'assemblage intégré, j'ai remarqué une instruction MOV inutile et l'ai supprimée.

À ma grande surprise, en supprimant l'instruction inutile, mon programme a ralenti .

J'ai trouvé que l' ajout d'instructions MOV arbitraires et inutiles augmentait encore les performances .

L'effet est erratique et change en fonction de l'ordre d'exécution: les mêmes instructions d'ordure transposées vers le haut ou vers le bas par une seule ligne produisent un ralentissement .

Je comprends que le processeur fait toutes sortes d'optimisations et de rationalisation, mais cela ressemble plus à de la magie noire.

Les données:

Une version de mon code compile conditionnellement trois opérations indésirables au milieu d'une boucle qui exécute 2**20==1048576 fois. (Le programme environnant calcule simplement les hachages SHA-256 ).

Les résultats sur mon ancienne machine (Intel (R) Core (TM) 2 CPU 6400 à 2,13 GHz):

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

Les programmes ont été exécutés 25 fois en boucle, l'ordre de passage changeant de manière aléatoire à chaque fois.

Extrait:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn't actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

Essayez-le vous-même:

Le code est en ligne sur GitHub si vous voulez l'essayer vous-même.

Mes questions:

  • Pourquoi copier inutilement le contenu d'un registre dans la RAM augmenterait-il les performances?
  • Pourquoi la même instruction inutile permettrait-elle une accélération sur certaines lignes et un ralentissement sur d'autres?
  • Ce comportement peut-il être exploité de manière prévisible par un compilateur?

Je crois dans les processeurs modernes que les instructions d'assemblage, tout en étant la dernière couche visible à un programmeur pour fournir des instructions d'exécution à un processeur, sont en réalité plusieurs couches de l'exécution réelle par le CPU.

Les processeurs modernes sont RISC hybrides RISC / CISC qui traduisent les instructions CISC x86 en instructions internes dont le comportement est plus RISC. De plus, il existe des analyseurs d'exécution désordonnés, des prédicteurs de branchement, la «fusion de micro-ops» d'Intel qui essaie de regrouper les instructions en plus gros lots de travaux simultanés (un peu comme le VLIW / Itanium ). Il y a même des limites de cache qui pourraient rendre le code plus rapide pour Dieu-sait-pourquoi s'il est plus grand (peut-être que le contrôleur de cache le place plus intelligemment, ou le garde plus longtemps).

Le CISC a toujours eu une couche de traduction assembleur-microcode, mais le fait est qu'avec les processeurs modernes, les choses sont beaucoup plus compliquées. Avec tous les transistors supplémentaires dans les usines de fabrication de semi-conducteurs modernes, les processeurs peuvent probablement appliquer plusieurs approches d'optimisation en parallèle, puis sélectionner celui qui offre la meilleure accélération. Les instructions supplémentaires peuvent biaiser la CPU pour utiliser un chemin d'optimisation meilleur que les autres.

L'effet des instructions supplémentaires dépend probablement du modèle / de la génération / du fabricant de l'UC et n'est pas susceptible d'être prévisible. L'optimisation du langage d'assemblage de cette manière nécessiterait une exécution contre de nombreuses générations d'architectures CPU, utilisant peut-être des chemins d'exécution spécifiques au CPU, et serait seulement souhaitable pour les sections vraiment très importantes, bien que vous le sachiez déjà.


Vous souhaiterez peut-être lire http://research.google.com/pubs/pub37077.html

TL; DR: insérer des instructions nop au hasard dans des programmes peut facilement augmenter les performances de 5% ou plus, et non, les compilateurs ne peuvent pas facilement exploiter cela. Il s'agit généralement d'une combinaison de prédicteur de branche et de comportement de cache, mais il peut tout aussi bien s'agir d'un blocage de station de réservation (même si aucune chaîne de dépendances n'est brisée ou que les surabonnements de ressources sont évidents).







freepascal