une routine de dessin de mandelbrot de c à sse2

Je veux réécrire une telle routine simple en code SSE2 (de préférence dans nasm) et je ne sais pas trop comment le faire, deux choses pas claires (comment exprimer des calculs (boucle interne et ceux de la boucle externe aussi) et comment appeler fonction de code c “SetPixelInDibInt (i, j, palette [n]);” depuis le code asm lié statiquement

void DrawMandelbrotD(double ox, double oy, double lx, int N_ITER) { double ly = lx * double(CLIENT_Y)/double(CLIENT_X); double dx = lx / CLIENT_X; double dy = ly / CLIENT_Y; double ax = ox - lx * 0.5 + dx * 0.5; double ay = oy - ly * 0.5 + dy * 0.5; static double re, im, re_n, im_n, c_re, c_im, rere, imim, int n; for(int j=0; j<CLIENT_Y; j+=1) { for(int i=0; i<CLIENT_X; i+=1) { c_re = ax + i * dx; c_im = ay + j * dy; re = c_re; im = c_im; rere=re*re; imim=im*im; n=1; for(int k=0;k 4.0 ) break; n++; } SetPixelInDibInt(i ,j, palette[n]); } } } 

Quelqu’un pourrait-il aider, j’aimerais ne pas voir d’autres implémentations de code, mais simplement une traduction nasm-sse de celles ci-dessus – ce serait très utile dans mon cas – quelqu’un pourrait-il aider avec cela?

Intel a une implémentation complète à titre d’exemple AVX. Voir ci-dessous.

Ce qui rend Mandelbrot difficile, c’est que la condition de départ anticipé de chaque sharepoint l’ensemble (pixel) est différente. Vous pouvez conserver une paire ou un quadrilatère de pixels en itérant jusqu’à ce que la magnitude dépasse 2.0 (ou si vous atteignez un maximum d’itérations). Autrement, il faudrait rechercher quels points de pixels se trouvaient dans quel élément vectoriel.

Quoi qu’il en soit, une mise en œuvre simpliste permettant d’opérer sur un vecteur de 2 (ou 4 avec AVX) à la fois verrait son débit limité par la latence des chaînes de dépendance. Vous devez créer plusieurs chaînes de dépendance en parallèle pour que les deux unités FMA de Haswell soient alimentées. Vous devez donc dupliquer vos variables et entrelacer des opérations pour deux itérations de la boucle externe à l’intérieur de la boucle interne.

Garder la trace des pixels en cours de calcul serait un peu délicat. Je pense que l’utilisation d’un ensemble de registres pour une rangée de pixels et d’un autre ensemble de registres pour une autre rangée pourrait nécessiter moins de temps système. (Vous pouvez donc toujours déplacer 4 pixels vers la droite plutôt que de vérifier si l’autre chaîne dep traite déjà ce vecteur.)

Je soupçonne que la vérification de la condition de sortie de la boucle toutes les 4 itérations environ pourrait être gagnante. Obtenir du code pour créer une twig basée sur une comparaison vectorielle compacte est légèrement plus coûteux que dans le cas scalaire. L’ajout de FP supplémentaire requirejs est également coûteux. (Haswell peut effectuer deux FMA par cycle, (latence = 5). L’unité d’ajout de FP unique est un port identique à l’un des unités FMA. Les deux unités mul FP sont sur les mêmes ports que ceux qui peuvent exécuter FMA.)

La condition de boucle peut être vérifiée avec une comparaison de paquets pour générer un masque de zéros et des uns, et un (V)PTEST de ce registre avec lui-même pour voir si tout est à zéro. (edit: movmskps then test+jcc moins d’ops, mais peut-être une latence plus élevée.) Ensuite, évidemment, je ou jne selon le cas, selon que vous avez effectué une comparaison de PF laissant des zéros quand vous devez sortir ou des zéros quand vous ne devriez pas. NAN ne devrait pas être possible, mais il n’y a aucune raison de ne pas choisir votre comparaison de telle sorte qu’un NAN aura pour résultat que la condition de sortie est vraie.

 const __mm256d const_four = _mm256_set1_pd(4.0); // outside the loop __m256i cmp_result = _mm256_cmp_pd(mag_squared, const_four, _CMP_LE_OQ); // vcmppd. result is non-zero if at least one element < 4.0 if (_mm256_testz_si256(cmp_result, cmp_result)) break; 

Il pourrait être possible d’utiliser PTEST directement sur un double compressé, avec un masque AND de masquage de bits qui sélectionnera les bits qui seront définis si la valeur de FP est> 4.0. Comme peut-être quelques bits dans l'exposant? Peut-être utile d'envisager. J'ai trouvé un post sur le forum , mais je ne l'ai pas essayé.

Hmm, oh merde, cela n'enregistre pas WHEN la condition de boucle a échoué, pour chaque élément de vecteur séparément, dans le but de colorer les points en dehors du jeu de Mandelbrot. Peut-être, testez n'importe quel élément touchant la condition (au lieu de tout), enregistrez le résultat, puis définissez cet élément (et c pour cet élément) sur 0.0 afin qu'il ne déclenche plus la condition de sortie. Ou peut-être que la planification des pixels en éléments vectoriels est la solution. Ce code peut très bien fonctionner sur un processeur hyperthreaded, car il y aura beaucoup de prédictions erronées sur les twigs, chaque élément entraînant séparément la condition de début de session.

Cela risque de gaspiller une grande partie de votre débit. Etant donné que 4 UOP par cycle sont réalisables, mais que seulement 2 d'entre eux peuvent être FP mul / add / FMA, il y a de la place pour une quantité importante de code entier pour programmer des points en éléments vectoriels. (Sur Sandybridge / Ivybrideg, sans FMA, le débit en PF est plus faible. Cependant, seuls 3 ports peuvent gérer des opérations sur les entiers, dont 2 sont les ports pour les unités FP mul et FP add.)

Etant donné que vous ne devez lire aucune donnée source, il n'y a qu'un stream d'access en mémoire pour chaque chaîne dep, et il s'agit d'un stream en écriture. (Et sa bande passante est faible, car la plupart des points nécessitent de nombreuses itérations avant que vous ne puissiez écrire une valeur de pixel unique.) Le nombre de stream de prélecture de matériel n'est donc pas un facteur limitant pour le nombre de chaînes dep à exécuter en parallèle. . La latence des erreurs de cache doit être masquée par les tampons d'écriture.

Je peux écrire du code si quelqu'un est toujours intéressé par cela (postez juste un commentaire). Je me suis arrêté au stade de la conception de haut niveau car c'est une vieille question, cependant.

==============

J'ai également constaté qu'Intel utilisait déjà le jeu Mandelbrot comme exemple pour l'un de leurs tutoriels AVX . Ils utilisent la méthode mask-off-vector-elements pour la condition de boucle. (en utilisant le masque généré directement par vcmpps à AND). Leurs résultats indiquent qu'AVX (simple précision) accélère 7 fois plus vite que le flottant scalaire. Il semble donc qu'il ne soit pas courant que les pixels voisins atteignent la condition de début d'affichage avec un nombre très différent d'itérations. (au moins pour le zoom / panoramique avec lequel ils ont testé.)

Ils ont simplement laissé les résultats de la PF continuer à s'accumuler pour les éléments qui échouent à la condition de départ précoce. Ils arrêtent simplement d'incrémenter le compteur pour cet élément. Espérons que la plupart des systèmes configurent par défaut le mot de contrôle de manière à ce qu'il supprime les dénormaux, si ceux-ci prennent encore des cycles supplémentaires.

Cependant, leur code est stupide: ils suivent le nombre d’itérations de chaque élément vectoriel avec un vecteur à virgule flottante, puis le convertissent en int à la fin avant utilisation. Il serait plus rapide, et sans occuper une unité d’exécution de PF, d’utiliser des entiers condensés pour cela. Oh, je sais pourquoi ils font cela: AVX (sans AVX2) ne prend pas en charge les opérations vectorielles à nombres entiers de 256 bits. Ils auraient pu utiliser des compteurs de boucle int 16 bits emballés, mais cela pourrait déborder. (Et ils devraient compresser le masque de 256b à 128b).

Ils testent également tous les éléments> 4.0 avec movmskps , puis au lieu d'utiliser ptest . Je suppose que le test / jcc peut effectuer une macro-fusion et s’exécuter sur une unité d’exécution différente de celle utilisée pour les opérations vectorielles FP; il n’est donc peut-être pas plus lent. Oh, et bien sûr, AVX (sans AVX2) n’a pas de PTEST PTEST . De plus, PTEST est PTEST 2 uops, donc movmskps + test / jcc est inférieur à uops que ptest + jcc . ( PTEST est 1 uop de domaine fusionné sur SnB, mais 2 uops non fusionnés pour les ports d’exécution. Sur IvB / HSW, 2 uops même dans le domaine fondu.) Il semble donc que movmskps est le moyen optimal, à moins que vous ne puissiez en tirer parti. du bit AND ET qui fait partie de PTEST , ou besoin de tester plus que le bit haut de chaque élément. Si une twig est imprévisible, ptest peut avoir un temps de latence inférieur, et donc en valoir la peine en détectant plus tôt un cycle erroné.