Skip to content

Que faire sans le gather et le scatter rapides dans les instructions AVX2 ?

Après notre longue recherche d'informations, nous avons trouvé la solution à cette question que certains lecteurs peuvent se poser. Nous vous donnons la réponse et nous espérons qu'elle vous sera très utile.

Solution :

IDK pourquoi vous utilisez différentes parties de la même... cur[8] array pour les indices et les valeurs ; cela a rendu la source plus difficile à comprendre pour comprendre qu'il n'y avait qu'un seul vrai tableau. L'autre était juste pour faire rebondir les vecteurs en scalaires.

Il semble que vous n'allez jamais que vecteur -> scalaire, et non pas réinsérer des scalaires dans un vecteur. Et aussi que rien à l'intérieur de la boucle ne dépend d'aucune donnée dans... sieveX[]; Je ne suis pas familier avec votre algorithme de tamisage mais je suppose que le but est de créer des données en mémoire pour une utilisation ultérieure.


AVX2 a des rassemblements (pas des dispersions), mais ils ne sont rapides que sur Skylake et les plus récents.. Ils sont ok sur Broadwell, slowish sur Haswell, et lent sur AMD. (Comme un par 12 horloges pour Ryzen. vpgatherqq). Voir http://agner.org/optimize/ et d'autres liens de performance dans le wiki des tags x86.

Le manuel d'optimisation d'Intel a une petite section sur le rassemblement / la dispersion manuelle (en utilisant l'insertion / l'extraction ou le. movhps) par rapport aux instructions matérielles, qui vaut peut-être la peine d'être lue. Dans ce cas où les indices sont des variables d'exécution (pas un stride constant ou quelque chose), je pense que Skylake peut bénéficier des instructions AVX2 gather ici.

Voir le guide intrinsèque d'Intel pour rechercher l'intrinsèque pour les instructions asm comme. movhps. Je ne parle que de ce que vous voulez que votre compilateur émette, car c'est ce qui est important et les mnémoniques asm sont plus courtes à taper et ne nécessitent pas de casting. Vous devez connaître la mnémonique asm pour les rechercher dans les tables d'instructions d'Agner Fog, ou pour lire la sortie du compilateur à partir de l'auto-vectorisation, donc je pense habituellement en asm et ensuite je traduis cela en intrinsèques.


Avec AVX, vous avez 3 options principales :

  • faire tout en scalaire. La pression du registre peut être un problème, mais générer des indices selon les besoins (au lieu de faire les 4 ajouts ou subs pour générer.... curr[4..7] en une seule fois) pourrait aider. A moins que ces mask aient des valeurs différentes dans différents éléments.

(Utiliser des sources de mémoire pour les constantes scalaires pourrait ne pas être mauvais, cependant, s'ils ne tiennent pas dans les immédiats 32 bits et si vous ne goulottez pas sur 2 ops de mémoire par horloge. La destination de la mémoire or utiliseraient des modes d'adressage indexés, donc le store-AGU dédié sur le port 7 sur Haswell et plus tard ne pourrait pas être utilisé. Ainsi, le débit de l'AGU pourrait être un goulot d'étranglement).

Extraire les 4 éléments d'un vecteur comme scalaire est plus coûteux que 4x scalaire. add ou des instructions de décalage, mais vous faites plus de travail que cela. Tout de même, avec BMI2 pour les décalages à nombre variable de 1 uops (au lieu de 3 sur Intel), cela pourrait ne pas être terrible. Je pense que nous pouvons faire mieux avec SIMD, cependant, surtout avec un réglage minutieux.

  • extraire les indices et les valeurs en scalaire comme vous le faites maintenant, de sorte que le OU en sieveX[] est un pur scalaire.. Cela fonctionne même lorsque deux ou plusieurs indices sont identiques.

    Cela vous coûte environ 7 uops par vecteur ymm -> 4x registres scalaires en utilisant des instructions ALU d'extraction, ou 5 uops en utilisant store/reload (à considérer pour le compilateur, peut-être pour un ou deux des 4 extraits de vecteurs, parce que ce code ne parvient probablement pas à embouteiller sur le débit du port de chargement / stockage...). Si le compilateur transforme le store/reload dans le source C en instructions shuffle/extract, cependant, vous ne pouvez pas facilement passer outre sa stratégie, sauf peut-être en utilisant le paramètre volatile. Et BTW, vous voudriez utiliser alignas(32) cur[8] pour vous assurer que les stockages vectoriels réels ne traversent pas une limite de ligne de cache.

or [rdi + rax*8], rdx (avec un mode d'adressage indexé empêchant la micro-fusion complète) est de 3 uops sur les CPU Intel modernes (Haswell et plus). Nous pourrions éviter un mode d'adressage indexé (ce qui ferait 2 uops pour le front-end) en mettant à l'échelle + en ajoutant à l'adresse de base du tableau en utilisant SIMD.: par ex. srli par 3 au lieu de 6, en masquant les 3 bits de poids faible (vpand), et vpaddq avec set1_epi64(sieveX). Cela coûte donc 2 instructions SIMD supplémentaires pour économiser 4 uops sur SnB-family, par vecteur d'indices. (Vous auriez extrait uint64_t* éléments de pointeur au lieu de uint64_t indices. Ou si sieveX peut être une adresse absolue de 32 bits 1 on peut sauter l'adresse vpaddq et extraire des indices déjà mis à l'échelle pour le même gain).

Cela permettrait également aux uops de stockage d'adresse de fonctionner sur le port 7 (Haswell et plus).; l'AGU simple sur le port7 ne peut gérer que les modes d'adressage non indexés. (Cela rend l'extraction de valeurs vers le scalaire avec store+reload plus attrayante. Vous voulez une latence plus faible pour l'extraction des indices, car les valeurs ne sont pas nécessaires avant la partie de chargement d'une mémoire-dst. or se termine). Cela signifie plus d'uops de domaine non fusionné pour l'ordonnanceur / unités d'exécution, mais pourrait bien valoir le compromis.

Ce n'est pas une victoire sur les autres CPU AVX2 (Excavator / Ryzen ou Xeon Phi) ; seule la famille SnB a un coût frontal et des restrictions de port d'exécution pour les modes d'adressage indexés.

  • extraire les indices, les rassembler manuellement dans un vecteur avec vmovq / vmovhps pour un SIMD vporpuis disperser à nouveau avec vmovq / vmovhps.

    Tout comme un rassemblement/diffusion HW, l'exactitude exige que tous les indices soient uniques, donc vous voudrez utiliser l'une des options ci-dessus jusqu'à ce que vous arriviez à ce point dans votre algo. (La détection des conflits vectoriels + fallback ne vaudrait pas le coût par rapport à une simple extraction vers le scalaire : Implémentation de fallback pour la détection de conflit dans AVX2).

    Voir sélectivement xor-ing éléments d'une liste avec des instructions AVX2 pour une version intrinsèque. (Je savais que j'avais récemment écrit une réponse avec un rassemblement / dispersion manuel, mais il m'a fallu un certain temps pour le trouver !). Dans ce cas, je n'ai utilisé que des vecteurs de 128 bits parce qu'il n'y avait pas de travail SIMD supplémentaire pour justifier les instructions supplémentaires. vinserti128 / vextracti128.

En fait, je pense qu'ici vous voudriez extraire la moitié haute de l'élément _mm256_sllv_epi64 donc vous avez (les données qui seraient) cur[4..5] et cur[6..7] dans deux __m128i distinctes. Vous auriez vextracti128 / 2x vpor xmm au lieu de vinserti128 / vpor ymm / vextracti128.

Le premier a moins de pression sur le port5, et a un meilleur parallélisme au niveau des instructions : Les deux moitiés de 128 bits sont des chaînes de dépendance séparées qui ne sont pas couplées l'une à l'autre. Les deux moitiés de 128 bits sont des chaînes de dépendances séparées qui ne sont pas couplées l'une à l'autre.

Faire le calcul d'adresse dans un vecteur de 256b et extraire des pointeurs au lieu d'indices rendrait... vmovhps chargements moins chers sur Intel (les chargements indexés ne peuvent pas rester micro-fusibles à vmovhps2). Voir le point précédent. Mais vmovq les chargements/stockages sont toujours une seule uop, et vmovhps les magasins indexés peuvent rester micro-fusionnés sur Haswell et plus, donc c'est le point mort pour le débit frontal et pire sur AMD ou KNL. Cela signifie également plus d'uops de domaine non fusionné pour l'ordonnanceur / les unités d'exécution, ce qui ressemble plus à un goulot d'étranglement potentiel que la pression de l'AGU port2/3. Le seul avantage est que les uops de stockage d'adresse peuvent s'exécuter sur le port 7, soulageant un peu la pression.

AVX2 nous donne une nouvelle option :

  • AVX2 vpgatherqq pour le rassemblement (_mm256_i64gather_epi64(sieveX, srli_result, 8)), puis extraire les indices et disperser manuellement. C'est donc exactement comme le gather / scatter manuel, sauf que vous remplacez le gather manuel par un gather matériel AVX2. (Deux gather de 128 bits coûtent plus cher qu'un gather de 256 bits, donc vous voudriez prendre le coup de parallélisme au niveau des instructions et rassembler dans un seul registre de 256 bits).

Possiblement une victoire sur Skylake (où vpgatherqq ymm est 4 uops / 4c throughput, plus 1 uop de configuration), mais même pas Broadwell (9 uops, un par 6c throughput) et certainement pas Haswell (22 uops / 9c throughput). Vous avez de toute façon besoin des indices dans des registres scalaires, donc vous êtes... seulement sauver la partie manuelle de la collecte du travail. C'est assez bon marché.


Coût total pour chaque stratégie sur Skylake

Il semble que cela ne va pas embouteiller gravement sur un seul port. GP reg->xmm a besoin du port 5, mais xmm->int a besoin du port 0 sur les CPU de la famille SnB, il est donc moins probable que cela goulotte sur le port 5 lorsqu'il est mélangé avec les brassages nécessaires à l'extraction. (par exemple vpextrq rax, xmm0, 1 est une instruction à 2 uop, un uop de shuffle sur le port 5 pour saisir le qword haut, et un uop sur le port 0 pour envoyer ces données du SIMD au domaine entier).

Donc, votre calcul SIMD où vous avez besoin de fréquemment. extraire un vecteur en scalaire
est moins mauvais que si vous aviez besoin d'insérer fréquemment des résultats de calculs scalaires dans des vecteurs. Voir aussi Charger un xmm à partir de regs GP, mais cela parle des données qui commencent dans les regs GP, pas dans la mémoire.

  • extraire les deux / scalaire OU : Total = 24 uops = 6 cycles de débit frontal.

  • vpaddq + vpand address calc (2 uops pour le port 0/1/5 sur Skylake).

  • 2x vextracti128 (2 uops pour le port 5)

  • 4x vmovq (4 p0)

  • 4x vpextrq (8 : 4p0 4p5)

  • 4x or [r], r (4x2 = 8 uops front-end chacun. back-end : 4p0156 4p23 (load) 4p237 (store-addres) 4p4 (store-data)). Mode d'adressage non indexé.

Total = 6 uops pour p5, ça tient à peine. Store/reload pour un extrait de données semble raisonnable, si vous pouviez obtenir votre compilateur pour le faire. (Mais les compilateurs ne modélisent généralement pas le pipeline de manière assez détaillée pour utiliser un mélange de stratégies dans la même boucle afin d'équilibrer la pression des ports).

  • rassembler/diffuser manuellement : 20 uops, 5 cycles de débit frontal. (Haswell / BDW / Skylake). Également bon sur Ryzen.

  • (facultatif, ne vaut probablement pas la peine) : vpaddq + vpand address calc (2 uops pour le port 0/1/5 sur Skylake) Sautez-les si vous pouvez utiliser non-VEX. movhps pour une charge indexée micro-fusionnée de 1 uop. (Mais alors les magasins p237 deviennent p23).

  • pointeurs vextracti128 (1 uop pour le port 5)

  • 2x vmovq extrait (2p0)

  • 2x vpextrq (4 = 2p0 2p5)

  • 2x vmovq charge (2p23)

  • 2x vmovhps xmm, xmm, [r] charge non-indexée (2 uops frontaux microfusés : 2p23 + 2p5)

  • vextracti128 diviser les données (p5)

  • 2x vpor xmm (2p015)

  • 2x vmovq store (2x 1 uop micro fusionné, 2p237 + 2p4)

  • 2x vmovhps magasin (2x 1 uop micro fusionné, 2p237 + 2p4)

Goulots d'étranglement des ports : 4 p0 et 4 p5 s'insèrent confortablement dans 5 cycles, surtout lorsque vous mélangez cela avec votre boucle qui peut exécuter plusieurs de ses uops sur le port 1. Sur Haswell paddq est seulement p15 (et non p015), et les décalages sont seulement p0 (et non p01). AVX2 _mm256_sllv_epi64 est de 1 uop (p01) sur Skylake, mais sur Haswell, il est de 3 uops = 2p0 + p5. Donc Haswell pourrait être plus proche d'un goulot d'étranglement p0 ou p5 pour cette boucle, auquel cas vous pourriez vouloir examiner une stratégie d'extraction de stockage/rechargement pour un vecteur d'indices.

Sauter le calcul de l'adresse SIMD est probablement bon, car la pression AGU ne semble pas être un problème à moins que vous n'utilisiez un extrait de stockage/rechargement. Et cela signifie moins d'instructions / une taille de code plus petite et moins d'uop dans le cache uop. (Le délaminage ne se produit pas avant les décodeurs / cache uop, donc vous bénéficiez toujours de la micro-fusion dans les premières parties du front-end, juste pas au goulot d'étranglement de l'émission).

  • Skylake AVX2 rassembler / diffusion manuelle : Total = 18 uops, 4,5 cycles de débit frontal. (Pire sur tout uarch antérieur ou sur AMD).

  • indices vextracti128 (1 uop pour le port 5).

  • 2x vmovq extrait (2p0)

  • 2x vpextrq (4 = 2p0 2p5)

  • vpcmpeqd ymm0,ymm0,ymm0 créer un masque tout-venant pour vpgatherqq (p015)

  • vpgatherqq ymm1, [rdi + ymm2*8], ymm0 4 uops pour certains ports.

  • vpor ymm (p015)

  • vextracti128 sur le résultat du OU (p5)

  • 2x vmovq store (2x 1 micro-fusion uop, 2p23 + 2p4). Notez l'absence de port7, nous utilisons des magasins indexés.

  • 2x vmovhps store (2x 1 uop micro-fusionné, 2p23 + 2p4).

Donc, même avec le meilleur choix de débit, nous ne gérons toujours que 4 charges / 4 magasins par 4,5 cycles, et c'est sans considérer le travail SIMD dans la boucle qui coûte un peu de débit frontal. Donc, nous ne sommes pas près d'un goulot d'étranglement sur le débit de l'AGU et d'avoir à se soucier de l'utilisation du port 7.

Nous pourrions peut-être penser au store/reload pour l'un des extraits (si nous étions le compilateur), en remplaçant la séquence 7 uop 5 instructions vextracti128 / 2x vmovq / 2x vpextrq par un store 5 uops / 4x load.


Globalement : Une boucle jusqu'à ce que nous ayons fini avec les conflits, puis une boucle de rassemblement SIMD.

Vous dites qu'après un certain point, vous n'avez plus de conflits (chevauchement) entre les indices comme... cur[0] == cur[2].

Vous voulez certainement une boucle séparée qui ne vérifie pas du tout les conflits pour tirer parti de cela. Même si vous aviez AVX512, la technologie Skylake vpconflictq de Skylake est un micro-code et n'est pas rapide (KNL a une boucle unique). vpconflictq mais c'est toujours plus rapide de l'éviter complètement).

Je vous laisse le soin (ou une question distincte) de savoir comment déterminer avec certitude quand vous en avez fini avec les conflits et pouvez laisser la boucle qui tient compte de cette possibilité.

Vous voulez probablement la stratégie d'extraction des indices + données tant qu'il peut y avoir des conflits. La vérification des conflits SIMD est possible, mais ce n'est pas bon marché, 11 uops pour des éléments 32 bits : Implémentation de fallback pour la détection des conflits dans AVX2. Une version qword est évidemment beaucoup moins chère que dword (moins de mélanges et de comparaisons pour obtenir tout contre tout), mais vous ne voulez probablement toujours le faire que toutes les 10 itérations environ de votre boucle d'extraction.

Il n'y a pas un énorme speedup de la meilleure version scalaire-ou à la meilleure version gather (6 cycles contre 4,5 ne tient pas compte de l'autre travail dans la boucle, donc le ratio est encore plus petit que cela). Quitter la version légèrement plus lente dès que possible ne vaut pas la peine de la rendre beaucoup plus lente.

Donc si vous pouvez de manière fiable détecter quand vous en avez fini avec les conflits, utilisez quelque chose comme

int conflictcheck = 10;

do {

    if (--conflictcheck == 0) {
       vector stuff to check for conflicts
       if (no conflicts now or in the future)
           break;

       conflictcheck = 10;  // reset the down-counter
    }

    main loop body,  extract -> scalar OR strategy

} while(blah);

// then fall into the gather/scatter loop.
do {
    main loop body, gather + manual scatter strategy
} while();

Cela devrait se compiler en un dec / je qui ne coûte qu'un uop dans le cas non pris.

En effectuant 9 itérations supplémentaires au total de la boucle légèrement plus lente, on obtient beaucoup plus mieux que de faire des milliers de vérifications de conflits supplémentaires et coûteuses.


Note de bas de page 1:

Si sieveX est statique et que vous construisez du code non-PIC sur Linux (et non sur MacOS), alors son adresse tiendra dans une balise disp32 comme partie d'un [reg+disp32] mode d'adressage. Dans ce cas, vous pouvez laisser de côté l'élément vpaddq. Mais faire en sorte qu'un compilateur traite un uint64_t comme un index de tableau déjà mis à l'échelle (avec ses bits bas effacés) serait laid. Il faudrait probablement couler sieveX en uintptr_t et ajouter, puis refondre.

Ceci n'est pas possible dans un exécutable PIE ou une bibliothèque partagée (où les adresses absolues 32 bits ne sont pas autorisées), ou sur OS X du tout (où les adresses statiques sont toujours supérieures à 2^32). Je ne suis pas sûr de ce que Windows autorise. Notez que [disp32 + reg*8] n'a qu'un seul registre, mais c'est toujours un mode d'adressage indexé, donc toutes les pénalités de la famille SnB s'appliquent. Mais si vous n'avez pas besoin de mise à l'échelle, reg + disp32 est juste base + disp32.

Note de bas de page 2: Fait amusant : non-VEX movhps Les charges peuvent rester microfondues sur Haswell. Ca ne causera pas un blocage SSE/AVX sur Skylake, mais vous n'aurez pas un compilateur pour émettre la version non-VEX au milieu d'une fonction AVX2..

IACA (l'outil d'analyse statique d'Intel) se trompe cependant 🙁 Qu'est-ce que IACA et comment l'utiliser ?

Il s'agit essentiellement d'une optimisation manquée pour les fonctions suivantes -mtune=skylake, mais il serait décrocher sur Haswell : Pourquoi ce code SSE est-il 6 fois plus lent sans VZEROUPPER sur Skylake ?

La "pénalité A" (exécuter SSE avec dirty upper) sur Skylake est simplement une fausse dépendance à ce seul registre. (Et un uop de fusion pour des instructions qui seraient autrement en écriture seule, mais.... movhps est déjà une lecture-modification-écriture de sa destination). J'ai testé cela sur Skylake avec Linux perf pour compter les uops, avec cette boucle :

    mov     r15d, 100000000

.loop:
    vpaddq  ymm0, ymm1, ymm2      ; dirty the upper part
    vpaddq  ymm3, ymm1, ymm2      ; dirty another register for good measure

    vmovq  xmm0, [rdi+rbx*8]       ; zero the full register, breaking dependencies
    movhps xmm0, [rdi+rbx*8+8]     ; RMW the low 128 bits
                          ; fast on Skylake, will stall on Haswell

    dec r15d
    jnz .loop

La boucle s'exécute à ~1,25 cycles par itération sur Skylake (i7-6700k), maximisant le débit frontal de 4 uops par horloge. 5 uops totaux du domaine fusionné (uops_issued.any), 6 uops de domaine non fusionné (uops_executed.thread). Donc, la micro-fusion était bien présente pour movhps sans aucun problème de SSE/AVX.

En le changeant en vmovhps xmm0, xmm0, [rdi+rbx*8+8] l'a ralenti à 1,50 cycles par itération, maintenant 6 uops de domaine fusionné, mais toujours les mêmes 6 uops de domaine non fusionné.

Il n'y a pas d'uop supplémentaire si la moitié supérieure de ymm0 est sale quand movhps xmm0, [mem] s'exécute. Je l'ai testé en commentant l'élément vmovq. Mais en changeant vmovq en movqfait résulte en un uop supplémentaire : movq devient un micro-fusion load+merge qui remplace les 64 bits inférieurs (et met toujours à zéro les 64 bits supérieurs de xmm0 donc ce n'est pas tout à fait movlps).


Notez également que pinsrq xmm0, [mem], 1 ne peut pas être microfusionné même sans VEX. Mais avec VEX, vous devriez préférer vmovhps pour des raisons de taille de code.

Votre compilateur peut vouloir "optimiser" l'intrinsèque pour... movhps sur les données entières en vpinsrq, cependant, je n'ai pas vérifié.

Je viens de regarder exactement ce que vous faites ici : Pour le mod1 = mod3 = _mm256_set1_epi64x(1); vous définissez simplement des bits uniques dans un bitmap avec des éléments de type ans comme index.

Et c'est déroulé par deux, avec ans et ans2 fonctionnant en parallèle, en utilisant... mod1 << ans et mod3 << ans2. Commentez votre code et expliquez ce qui se passe dans l'ensemble en utilisant du texte anglais ! Il s'agit juste d'une implémentation très compliquée de la boucle de réglage des bits d'un tamis d'Eratosthène normal. (Il aurait donc été bien que la question le dise en premier lieu).

Unrolling avec plusieurs start/strides en parallèle est une très bonne optimisation, donc vous fixez normalement plusieurs bits dans une ligne de cache pendant qu'elle est encore chaude dans L1d. Le blocage du cache pour moins de facteurs différents à la fois a des avantages similaires.. Itérer sur le même morceau de mémoire de 8kiB ou 16kiB de façon répétée pour plusieurs facteurs (strides) avant de passer au suivant. Unrolling avec 4 offsets pour chacun des 2 strides différents pourrait être un bon moyen de créer plus d'ILP.

Plus vous exécutez de strides en parallèle, plus vous passez lentement par de nouvelles lignes de cache la première fois que vous les touchez, cependant. (Donner de la place au cache / TLB prefetch pour éviter même un stall initial). Donc, le blocage du cache ne supprime pas tous les avantages des strides multiples.


Cas spécial possible pour les strides <256>

Un seul chargement/VPOR/store de vecteur de 256 bits peut fixer plusieurs bits. L'astuce consiste à créer une constante vectorielle, ou un ensemble de constantes vectorielles, avec des bits dans la bonne position. Le motif répétitif est quelque chose comme LCM(256, bit_stride) bits de long, cependant. Par exemple, stride=3 se répéterait dans un motif de 3 vecteurs de long. Cela devient très vite inutilisable pour les strides impairs / premiers, à moins qu'il n'y ait quelque chose de plus astucieux :(.

Le scalaire 64 bits est intéressant car la rotation par bit est disponible pour créer une séquence de motifs, mais la rotation à nombre variable sur les CPU de la famille SnB coûte 2 uops.

Il pourrait y avoir plus que vous pouvez faire avec cela ; peut-être que les charges non alignées pourraient aider d'une manière ou d'une autre.

Un motif répétitif de bitmasks pourrait être utile même pour le cas des grandes foulées, par exemple en tournant par. stride % 8 à chaque fois. Mais cela serait plus utile si vous faisiez du JIT sur une boucle qui codait en dur le motif dans. or byte [mem], imm8avec un facteur de déroulement choisi pour être congruent avec la longueur de répétition.


Réduction des conflits avec des charges/stores plus étroits.

Vous n'avez pas besoin de charger/modifier/stocker des chunks de 64 bits lorsque vous ne réglez qu'un seul bit. Plus vos opérations RMW sont étroites, plus vos indices de bits peuvent être proches sans entrer en conflit.

(Mais vous n'avez pas une longue chaîne de dep transportée en boucle sur le même emplacement ; vous passerez à autre chose avant que OoO exec ne décroche en attendant un rechargement à la fin d'une longue chaîne. Donc si les conflits ne sont pas un problème de correction, il est peu probable que cela fasse une grande différence de perforation ici. Contrairement à un histogramme bitmap ou quelque chose où une longue chaîne de hits répétés sur des bits proches pourrait facilement se produire).

Les éléments 32 bits seraient un choix évident. x86 peut efficacement charger/stocker des mots de passe vers/depuis des registres SIMD ainsi que des scalaires. (les opérations d'octets scalaires sont également efficaces, mais les stockages d'octets à partir de registres SIMD nécessitent toujours de multiples uops avec pextrb.)

Si vous ne rassemblez pas dans des registres SIMD, la largeur des éléments SIMD pour les registres ans / ans2 ne doit pas nécessairement correspondre à la largeur du RMW. Le RMW 32 bits a des avantages par rapport au 8 bits si vous voulez diviser un bit-index en adresse / bit-offset en scalaire, en utilisant des décalages ou des bts qui masquent implicitement le compte de décalage à 32 bits (ou 64 bits pour les décalages 64 bits). Mais les 8 bits shlx ou bts n'existent pas.

Le principal avantage de l'utilisation d'éléments SIMD 64 bits est que vous calculez un pointeur au lieu d'un simple index. Si vous pouviez restreindre votre sieveX à 32 bits, vous seriez toujours en mesure de le faire. par exemple, allouer avec mmap(..., MAP_32BIT|MAP_ANONYMOUS, ...) sous Linux. C'est en supposant que vous n'avez pas besoin de plus de 2^32 bits (512MiB) d'espace de tamisage, de sorte que vos indices de bits tiennent toujours dans des éléments de 32 bits. Si ce n'est pas le cas, vous pourriez toujours utiliser des vecteurs d'éléments 32 bits jusqu'à ce point, puis utiliser votre boucle actuelle pour la partie haute.

Si vous utilisez des éléments SIMD 32 bits sans restreindre sieveX à être un pointeur de point 32 bits, vous devriez renoncer à utiliser les calculs de pointeur SIMD et juste extraire un bit-index, ou encore diviser en SIMD en... idx/bit et extraire les deux.

(Avec des éléments 32 bits, une stratégie SIMD -> scalaire basée sur le stockage/rechargement semble encore plus attrayante, mais en C, cela dépend surtout de votre compilateur).

Si vous rassembliez manuellement dans des éléments 32 bits, vous ne pouviez pas utiliser. movhps plus. Vous deviez utiliser pinsrd / pextrd pour les 3 éléments supérieurs, et ceux-ci ne microfusent jamais / nécessitent toujours un port5 uop sur la famille SnB. (Contrairement à movhps qui est un pur magasin). Mais cela signifie que vpinsrd est toujours 2 uops avec un mode d'adressage indexé. Vous pouvez toujours utiliser vmovhps pour l'élément 2 (puis écraser le mot-clé supérieur du vecteur avec vpinsrd) ; les charges non alignées sont bon marché et il est acceptable de chevaucher l'élément suivant. Mais vous ne pouvez pas faire movhps stores, et c'est là qu'il était vraiment bon.


Il y a deux grands problèmes de performance avec votre stratégie actuelle:

Apparemment, vous l'utilisez parfois avec certains éléments de... mod1 ou mod3 étant 0ce qui entraîne un gaspillage de travail complètement inutile. [mem] |= 0 pour ces foulées.

Je pense une fois un élément dans ans ou ans2 atteint total, vous allez sortir de la boucle interne et faire ans -= sum 1 chaque fois dans la boucle interne. Vous ne voulez pas nécessairement le remettre à zéro. ans = sum (pour cet élément) pour refaire l'ORing (mise en place des bits qui étaient déjà mis), car cette mémoire sera froide en cache. Ce que nous voulons vraiment, c'est emballer les éléments restants encore utilisés dans des emplacements connus et entrer dans d'autres versions de la boucle qui ne font que 7, puis 6, puis 5 éléments au total. Ensuite, nous n'aurons plus qu'un seul vecteur.

Cela semble vraiment maladroit. Une meilleure stratégie pour un élément frappant la fin pourrait être de terminer les trois autres dans ce vecteur avec scalaire, un à la fois, puis exécuter le single restant. __m256i restant. Si les strides sont tous proches, vous obtenez probablement une bonne localité de cache.


Scalaire moins cher, ou peut-être encore SIMD mais extraire seulement un index de bit.

Diviser l'index de bits en un index de qword et un bitmask avec SIMD, puis extraire les deux séparément coûte beaucoup d'uops pour le cas scalaire-OR : tellement que vous n'êtes pas en goulot d'étranglement sur le débit de stockage de 1 par horloge, même avec toutes les optimisations dans ma réponse de dispersion/rassemblement. (Les ratés du cache peuvent parfois ralentir cela, mais moins d'uops frontaux signifie une plus grande fenêtre hors ordre pour trouver le parallélisme et garder plus d'ops mémoire en vol).

Si nous pouvons obtenir que le compilateur fasse un bon code scalaire pour diviser un bit-index, nous pourrions envisager un scalaire pur. Ou au moins extraire seulement les indices de bits et sauter le truc SIMD shift/mask.

C'est dommage que la destination de la mémoire scalaire. bts n'est pas rapide. bts [rdi], rax mettrait ce bit dans la chaîne de bits, même si c'est en dehors du dword sélectionné par [rdi]. (Ce genre de comportement fou-CISC est pourquoi il n'est pas rapide, cependant ! comme 10 uops sur Skylake).

Le scalaire pur peut ne pas être idéal, cependant. Je jouais autour de cela sur Godbolt :

#include 
#include 
#include 

// Sieve the bits in array sieveX for later use
void sieveFactors(uint64_t *sieveX64, unsigned cur1, unsigned cur2, unsigned factor1, unsigned factor2)
{
    const uint64_t totalX = 5000000;
#ifdef USE_AVX2
//...
#else
     //uint64_t cur = 58;
     //uint64_t cur2 = 142;
     //uint64_t factor = 67;
     uint32_t *sieveX = (uint32_t*)sieveX64;

    if (cur1 > cur2) {
        // TODO: if factors can be different, properly check which will end first
        std::swap(cur1, cur2);
        std::swap(factor1, factor2);
    }
    // factor1 = factor2;  // is this always true?

    while (cur2 < totalX) {
         sieveX[cur1 >> 5] |= (1U << (cur1 & 0x1f));
         sieveX[cur2 >> 5] |= (1U << (cur2 & 0x1f));
         cur1 += factor1;
         cur2 += factor2;
    }
    while (cur1 < totalX) {
         sieveX[cur1 >> 5] |= (1U << (cur1 & 0x1f));
         cur1 += factor1;
    }
#endif
}

Notez comment j'ai remplacé votre if() extérieur pour choisir entre les boucles avec le tri cur1, cur2.

GCC et clang mettent un 1 dans un registre à l'extérieur de la boucle, et utilisent shlx r9d, ecx, esi à l'intérieur de la boucle pour faire 1U << (cur1 & 0x1f) en une seule uop sans détruire le registre 1. (MSVC utilise load / BTS / store, mais c'est maladroit avec un grand nombre de mov instructions. Je ne sais pas comment dire à MSVC qu'il est autorisé à utiliser BMI2).

Si un mode d'adressage indexé pour or [mem], reg ne coûtait pas une uop supplémentaire, ce serait génial.

Le problème est que vous avez besoin d'un shr reg, 5 quelque part, et c'est destructeur. En mettant 5 dans un registre et l'utiliser pour copier+déplacer l'indice de bit serait une configuration idéale pour charger / BTS / stocker, mais les compilateurs ne connaissent pas cette optimisation il semble.

Division scalaire optimale( ?) et utilisation d'un bit-index.

   mov   ecx, 5    ; outside the loop

.loop:
    ; ESI is the bit-index.
    ; Could be pure scalar, or could come from an extract of ans directly

    shrx  edx, esi, ecx           ; EDX = ESI>>5 = dword index
    mov   eax, [rdi + rdx*4]
    bts   eax, esi                ; set esi % 32 in EAX
    mov   [rdi + rdx*4]

    more unrolled iterations

    ; add   esi, r10d               ; ans += factor if we're doing scalar

    ...
    cmp/jb .loop

Donc, étant donné un bit-index dans un registre GP, c'est 4 uops pour mettre le bit en mémoire. Remarquez que le chargement et le stockage sont tous deux avec movdonc les modes d'adressage indexés ne sont pas pénalisés sur Haswell et les versions ultérieures.

Mais le mieux que j'ai pu obtenir des compilateurs était 5, je pense, en utilisant shlx / shr /. or [mem], reg. (Avec un mode d'adressage indexé, le or est de 3 uops au lieu de 2).

Je pense que si vous êtes prêt à utiliser de l'asm écrit à la main, vous pouvez aller plus vite avec ce scalaire et abandonner complètement le SIMD. Les conflits ne sont jamais un problème de correction pour cela.

Peut-être que vous pouvez même obtenir un compilateur pour émettre quelque chose de comparable, mais même un seul uop supplémentaire par RMW déroulé est une grosse affaire.

Nous vous montrons des avis et des notes

Si vous êtes d'accord, vous avez le pouvoir de laisser un tutoriel sur ce que vous ajouteriez à ce tutoriel.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.