Je suis sur le point d'analyser certains "canaux de synchronisation" de certains codes binaires x86. Je poste une question pour comprendre les opcodes bsf / bsr .
Si haut niveau, ces deux opcodes peuvent être modélisés comme une "boucle", qui compte les zéros de début et de fin d'un opérande. Le manuel x86 a une bonne formalisation de ces opcodes, quelque chose comme ce qui suit:
IF SRC = 0
THEN
ZF ↠1;
DEST is undefined;
ELSE
ZF ↠0;
temp ↠OperandSize – 1;
WHILE Bit(SRC, temp) = 0
DO
temp ↠temp - 1;
OD;
DEST ↠temp;
FI;
Mais à ma grande surprise, bsf / bsr semblent avoir des cycles de processeur fixes . D'après certains documents que j'ai trouvés ici: https://gmplib.org/~tege/x86-timing .pdf , il semble qu'il faut toujours 8 cycles CPU pour terminer.
Voici donc mes questions:
Je confirme que ces instructions ont des cycles CPU fixes. En d'autres termes, quel que soit l'opérande donné, ils prennent toujours le même temps à traiter, et il n'y a pas de "canal de synchronisation" derrière. Je ne trouve pas les spécifications correspondantes dans les documents officiels d'Intel.
Alors pourquoi est-ce possible? Apparemment, c'est une "boucle" ou un peu, du moins de haut niveau. Quelle est la décision de conception derrière? Plus facile pour les pipelines CPU?
3 Réponses :
Les performances BSF / BSR ne dépendent pas des données des processeurs modernes. Voir https: / /agner.org/optimize/ , https://uops.info/ (Intel uniquement), ou http://instlatx64.atw.hu/ pour les résultats de chronométrage expérimental, ainsi que le https://gmplib.org/~tege/x86-timing.pdf que vous avez trouvé. < / p>
Sur Intel moderne, ils décodent en 1 uop avec une latence de 3 cycles et un débit de 1 / horloge, fonctionnant uniquement sur le port 1. Ryzen les exécute également avec une latence de 3c pour BSF, une latence de 4c pour BSR, mais plusieurs uops. Les versions antérieures d'AMD sont parfois encore plus lentes.
Votre coût "8 cycles" (latence et débit) semble être pour BSF 32 bits sur AMD K8, d'après la table de Granlund que vous avez liée. Le tableau d'Agner Fog est d'accord, (et montre qu'il décode à 21 uops au lieu d'avoir une unité d'exécution de bit-scan dédiée. Mais l'implémentation microcodée est vraisemblablement toujours sans branche et non dépendante des données). Aucune idée de la raison pour laquelle vous avez choisi ce numéro; K8 n'a pas de SMT / Hyperthreading, donc l'opportunité d'un canal latéral ALU-timing est beaucoup plus réduite.
Notez qu'ils ont une dépendance de sortie sur le registre de destination, qu'ils laissent inchangé si l'entrée était nulle. AMD documente ce comportement, Intel l'implémente dans le matériel mais le documente comme un résultat" indéfini ", donc malheureusement les compilateurs n'en profiteront pas et les programmeurs humains devraient peut-être être prudents . IDK si un ancien processeur 32 bits uniquement avait un comportement différent, ou si Intel prévoit de changer un jour (douteux!), Mais j'aimerais qu'Intel documente le comportement au moins pour le mode 64 bits (ce qui exclut les anciens processeurs). < / p>
lzcnt / tzcnt et popcnt sur les processeurs Intel (mais pas AMD) ont la même dépendance de sortie avant Skylake et avant Cannon Lake (respectivement ), même si sur le plan architectural, le résultat est bien défini pour toutes les entrées. Ils utilisent tous la même unité d'exécution. ( Comment POPCNT est-il implémenté dans le matériel? ). AMD Bulldozer / Ryzen construit son unité d'exécution de balayage de bits sans la dépendance de sortie intégrée, donc BSF / BSR sont plus lents que LZCNT / TZCNT (plusieurs uops pour gérer le cas d'entrée = 0, et probablement également définir ZF en fonction de l'entrée, pas le résultat).
(Il n'est pas possible de tirer parti de cela avec les intrinsèques; pas même avec le _BitScanReverse64 de MSVC qui utilise un argument de sortie par référence que vous pouvez définir en premier. MSVC ne respecte pas la valeur précédente et suppose qu'il s'agit d'une sortie uniquement. VS: comportement d'optimisation inattendu avec _BitScanReverse64 intrinsèque )
(c'est-à-dire que ce n'est pas nécessairement la façon dont le matériel ou le microcode fonctionne).
Il donne exactement le même résultat dans tous les cas, vous pouvez donc l'utiliser pour comprendre exactement ce qui se passera pour les cas d'angle sur lesquels le texte vous pose des questions. C'est tout .
Le but est d'être simple et facile à comprendre, et cela signifie modéliser les choses en termes d'opérations simples à 2 entrées qui se produisent en série. C / Fortran / pseudocode typique n'a pas d'opérateurs pour plusieurs entrées AND, OR ou XOR, mais vous pouvez l'intégrer dans le matériel jusqu'à un certain point ( limité par fan-in , l'opposé de fan-out).
L'ajout d'entiers peut être modélisé comme un transfert d'ondulation en série de bits, mais ce n'est pas ainsi que cela est implémenté! Au lieu de cela, nous obtenons une latence à un cycle pour l'ajout de 64 bits avec beaucoup moins de 64 délais de porte en utilisant des astuces comme transporter des ajouts d'anticipation .
Les techniques d'implémentation réelles utilisées dans l'unité d'exécution bit-scan / popcnt d'Intel sont décrites dans US Brevet US8214414 B2 .
Un chemin de données fusionné pour PopCount et BitScan est décrit. Un matériel le circuit comprend un arbre de compresseur utilisé pour une fonction PopCount, qui est réutilisé par une fonction BitScan (par exemple, Bit Scan Forward (BSF) ou bit scan inverse (BSR)).
La logique de sélection permet à l'arborescence du compresseur fonctionner sur un mot d'entrée pour l'opération PopCount ou BitScan, basé sur une instruction de microprocesseur. Le mot d'entrée est codé si un L'opération BitScan est sélectionnée.
L'arborescence du compresseur reçoit l'entrée mot, fonctionne sur les bits comme si tous les bits avaient le même niveau de signification (par exemple, pour un mot d'entrée de N bits, le mot d'entrée est traité comme N entrées un bit). Le résultat du circuit de l'arbre des compresseurs est un valeur binaire représentant un nombre lié à l'opération effectuée (le nombre de bits définis pour PopCount, ou la position de bits du premier définir le bit rencontré en scannant le mot d'entrée ).
Il est assez sûr de supposer que le silicium réel d'Intel fonctionne de la même manière. D'autres brevets d'Intel pour des choses comme les machines en panne (ROB, RS) ont tendance à correspondre aux expériences de performances que nous pouvons effectuer.
AMD peut faire quelque chose de différent, mais malgré les tests de performances, nous savons qu'il n'est pas dépendant des données.
Il est bien connu que la latence fixe est une chose extrêmement bénéfique pour la planification dans le désordre, il est donc très surprenant que les instructions ne aient pas été corrigées latence. Sandybridge est même allé jusqu'à standardiser les latences pour simplifier l'ordonnanceur et réduire les opportunités de conflits de réécriture (par exemple, une latence de 3 cycles suivie d'une latence de 2 cycles sur le même port produirait 2 aboutit au même cycle). Cela signifiait que le LEA complexe (avec les 3 composants: [disp + base + idx * scale] ) prenait 3 cycles au lieu de seulement 2 pour les 2 ajouts comme sur les processeurs précédents. Il n'y a pas d'augmentation de latence à 2 cycles sur la famille Sandybridge. (Il y a des instructions de latence à 2 cycles, car elles décodent à 2 uops avec 1c de latence chacune, mais le planificateur planifie des uops, pas des instructions).
Une des rares exceptions à la règle de latence fixe pour les uops ALU est division / sqrt, qui utilise une unité d'exécution non entièrement pipelined. La division est intrinsèquement itérative, contrairement à la multiplication où vous pouvez créer du matériel large qui effectue les produits partiels et les ajouts partiels en parallèle.
Sur les processeurs Intel, la latence variable pour l'accès au cache L1d peut produire des relectures des uops dépendants si les données n'étaient pas prêtes alors que le planificateur espérait qu'elles le seraient de manière optimiste.
Selon ceci , les deux bsf / bsr avaient des latences variables dans la IA-32 Execution Layer , qui est essentiellement un émulateur de logiciel pour x86 sur Itanium, en utilisant une séquence inefficace d'instructions Itanium. Le brevet lui-même propose un certain nombre d'algorithmes à latence fixe et rapide (dont certains utilisent l'instruction compute zero index (czx) sur Itanium.
Le manuel 80x86 a une bonne description du comportement attendu, mais cela n'a rien à voir avec la façon dont il est réellement implémenté dans le silicium dans n'importe quel modèle de n'importe quel fabricant.
Disons qu'il y a eu 50 conceptions de CPU différentes d'Intel, 25 conceptions de CPU d'AMD, puis 25 de plus d'autres fabricants (VIA, Cyrix, SiS / Vortex, NSC, ...). Sur ces 100 conceptions de CPU différentes, peut-être qu'il y a 20 façons complètement différentes d'implémenter BSF , et peut-être 10 d'entre elles ont une synchronisation fixe, 5 ont une synchronisation qui dépend de chaque bit de l'opérande source, et 5 dépendent des groupes de bits de l'opérande source (par exemple, peut-être comme "si les 32 bits les plus élevés de l'opérande 64 bits sont des zéros {passer à une logique 32 bits qui est 2 cycles plus rapide}").
Je confirme que ces instructions ont des cycles CPU fixes. En d'autres termes, quel que soit l'opérande donné, ils prennent toujours le même temps à traiter, et il n'y a pas de "canal de synchronisation" derrière. Je ne trouve pas les spécifications correspondantes dans les documents officiels d'Intel.
Vous ne pouvez pas. Plus précisément, vous pouvez tester ou rechercher des processeurs existants, mais c'est une perte de temps car la semaine prochaine, Intel (ou AMD ou VIA ou quelqu'un d'autre) peut sortir un nouveau processeur qui a un timing complètement différent.
Dès que vous comptez sur "mesuré à partir des processeurs existants", vous le faites mal. Vous devez vous fier aux "garanties architecturales" qui s'appliquent à tous les futurs processeurs. Il n'y a pas de "garantie architecturale". Vous devez supposer qu'il peut y avoir un canal secondaire de synchronisation (même s'il n'y en a pas pour les processeurs actuels)
Alors pourquoi est-ce possible? Apparemment, c'est une "boucle" ou un peu, du moins de haut niveau. Quelle est la décision de conception derrière? Plus facile pour les pipelines CPU?
Au lieu de faire un BSF 64 bits, pourquoi ne pas le diviser en deux morceaux 32 bits et les faire en parallèle, puis fusionner les résultats? Pourquoi ne pas le diviser en huit morceaux 8 bits? Pourquoi ne pas utiliser une recherche de table pour chaque élément 8 bits?
Il est théoriquement possible que les instructions deviennent dépendantes des données des futurs processeurs, mais c'est extrêmement improbable pour du matériel réel à moins que quelque chose de complètement fondamental ne change dans la conception des processeurs. Hadi a commenté que la couche d'émulation d'Itanium avait une latence variable bsf / bsr , mais je pense que l'émulation est le seul cas plausible. (Cela pourrait inclure le Crusoe de Transmeta, où l'optimisation JIT interne à plus longue portée pourrait être optimisée pour un cas avec une plage d'entrée connue ou une valeur constante.)
Mais oui, +1 pour la recherche de garanties architecturales, comme je pense que AES-NI prévoit AESENC / AESDEC. Bien sûr, vous n'en trouverez pas pour les instructions "normales", donc tout ce que nous pouvons vraiment dire, c'est que vous ne pouvez pas garantir cela de manière totalement pérenne, principalement à cause des émulateurs.
Les réponses publiées ont bien expliqué que l'implémentation est différente du pseudocode. Mais si vous êtes toujours curieux de savoir pourquoi la latence est fixe et non dépendante des données ou utilise des boucles pour cette question, vous devez voir le côté électronique des choses. Une façon de mettre en œuvre cette fonctionnalité dans le matériel consiste à utiliser un encodeur de priorité .
Un encodeur prioritaire acceptera n lignes d'entrée qui peuvent être une ou off (0 ou 1) et donnera l'index de la ligne de priorité la plus élevée qui est activée. Vous trouverez ci-dessous un tableau de l'article Wikipédia lié modifié pour une fonction de bit d'ensemble la plus significative.
input | output index of first set bit 0000 | xx undefined 0001 | 00 0 001x | 01 1 01xx | 10 2 1xxx | 11 3
x indique que la valeur de bit n'a pas d'importance et peut être n'importe quoi
Si vous voyez le schéma de circuit sur l'article, il n'y a aucune boucle d'aucune sorte, tout est parallèle.
Le pseudocode manuel Intel n'est pas une implémentation stricte; le CPU est libre de mettre en œuvre comme il le souhaite tant que le résultat final est le même.