Les processeurs Intel peuvent émettre deux opérations de points flottants, mais une charge par cycle, de sorte que les accès à la mémoire sont la contrainte la plus serrée. Dans cet esprit, j'ai d'abord visé à utiliser des charges emballées pour réduire le nombre d'instructions de charge et utiliser des arithmétiques emballés simplement parce que c'était pratique. Depuis depuis que je me suis rendu compte que la bande passante de la mémoire saturation peut être la plus grosse problème et que tous les messages avec les instructions SSE auraient pu être une optimisation prématurée si le point était de rendre le code rapide plutôt que d'apprendre à vous vectoriser.

SSE

Le moins de charges possibles sans hypothèse sur les indices dans B nécessite déroulant la boucle quatre fois. Une charge de 128 bits obtient quatre indices de B , deux charges de 128 bits reçoivent une paire de doubles adjacents à partir de C et de collecte a requis indépendants Charges 64 bits. C'est un étage de 7 cycles pour quatre itérations pour le code de série. (Assez pour saturer ma largeur de bande de mémoire si l'accès à A ne cache pas bien). J'ai laissé de côté des choses ennuyeuses comme la manipulation d'un certain nombre d'itérations qui ne sont pas un multiple de 4. xxx

obtenir les indices de sortie est la partie la plus compliquée. MOVDQA Charges 128 bits de données entier à partir d'une adresse alignée de 16 octets (NEHALEM a des pénalités de latence pour mélanger les instructions "entier" et "Flott" SSE). PunPCKHQDQ Déplace High 64 bits à BIX 64 bits, mais en iteuse, contrairement au plus simplement nommé movhlpd . Les changements 32 bits sont effectués dans les registres à usage général. MOVHPD Charge un double dans la partie supérieure d'un registre XMM sans déranger la partie inférieure - Ceci est utilisé pour charger les éléments de A directement dans des registres emballés.

Ce code distinctement plus rapide que le code ci-dessus, qui est à son tour plus rapide que le code simple, et sur chaque modèle d'accès, mais le cas simple b [i] = i où la boucle naïve est réellement le plus rapide. J'ai aussi essayé quelques choses comme une fonction autour de somme (A (B (:)), c (:)) dans Fortran qui s'est finalement équivalent à la simple boucle.

J'ai testé sur un Q6600 (65 nm noyau 2 à 2,4 GHz) avec 4 Go de mémoire DDR2-667, en 4 modules. Test de la bande passante de la mémoire donne environ 5333 mb / s, il semble donc que je ne vois qu'un seul canal. Je compile avec le GCC de Debian 4.3.2-1.1, -O3 -FFAST-MATH -SSE2 -FTREE -FTREE-Vectorize -Std = gnu99.

Pour tester Je laisse n Soyez un million, initialiser les tableaux de sorte que a [b [i]] et c [i] égal 1.0 / (i + 1) , avec quelques modèles différents d'indices. On attribue A avec un million d'éléments et définies b à une permutation aléatoire, une autre allouate a avec des éléments de 10 m et utilise tous les 10, et le dernier Allocates A avec des éléments 10M et définit B [i + 1] en ajoutant un nombre aléatoire de 1 à 9 à B [i] . Je time à jour combien de temps un appel prend avec GetTimeoDay , effacer les caches en appelant clflush sur les tableaux et mesurant 1000 essais de chaque fonction. J'ai tracé des distributions d'exécution lissées en utilisant du code de la courgette de critère (en particulier, l'estimateur de densité de noyau dans le package ).

bande passante

maintenant, pour la note importante sur la bande passante. 5333 Mo / s avec une horloge de 2,4 GHz comporte un peu plus de deux octets par cycle. Mes données sont suffisamment longues que rien ne devrait être cachéable et multiplier le temps d'exécution de ma boucle (16 + 2 * 16 + 4 * 64) octets chargé par itération Si tout ce que tout manque, me donne presque exactement la bande passante ~ 53333Mb / s Mon système a . Il devrait être assez facile de saturer cette bande passante sans SSE. Même en supposant que a a été complètement mis en cache, il suffit de lire B et c pour une itéération déplace 12 octets de données et que la naïf peut commencer une nouvelle itération. Toujours troisième cycle avec pipelining.

supposer que quelque chose de moins que la mise en cache complète sur A rend l'arithmétique et l'instruction comptent encore moins d'un goulot d'étranglement. Je ne serais pas surpris si la majeure partie de l'accélération de mon code vient de délivrer moins de charges à B et c aussi plus d'espace est libre de suivre et de spéculer au-dessus de la cache de cache. a .

Le matériel plus large peut faire plus de différence. Un système NEHALEM qui exécute trois canaux de DDR3-1333 aurait besoin de déplacer 3 * 10667 / 2.66 = 12,6 octets par cycle pour la cuve de bande de mémoire saturée. Ce serait impossible pour un seul thread si a s'adapte au cache - mais à 64 octets, une ligne cache manque sur le vecteur addition rapide - une des quatre charges de ma boucle manquantes dans les caches monte la bande passante moyenne requise à 16 octets / cycle.