Désoptimiser un programme pour le pipeline dans Intel Sandybridge-famille de CPU

je me suis creusé la tête pendant une semaine en essayant de terminer cette mission et j'espère que quelqu'un ici pourra me guider vers le bon chemin. Permettez-moi de commencer par les instructions de l'instructeur:

votre mission est le contraire de notre première mission en laboratoire, qui était d'optimiser un programme de nombres premiers. Votre but dans cette tâche est de pessimiser le programme, c'est-à-dire de le faire fonctionner plus lentement. Ces deux sont gourmandes programmes. Ils prennent un peu de quelques secondes à courir sur nos ordinateurs de laboratoire. Vous ne pouvez pas modifier l'algorithme.

pour désoptimiser le programme, utilisez votre connaissance du fonctionnement du pipeline Intel i7. Imaginez des façons de réorganiser les voies d'instruction pour introduire la guerre, les dangers bruts et autres. Pensez à des façons de réduire l'efficacité du cache. Être diaboliquement incompétent.

la cession a donné un choix de programmes Whetstone ou Monte-Carlo. Les commentaires sur l'efficacité de cache sont surtout applicables uniquement à Whetstone, mais j'ai choisi le programme de simulation Monte-Carlo:

// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm>    // Needed for the "max" function
#include <cmath>
#include <iostream>

// A simple implementation of the Box-Muller algorithm, used to generate
// gaussian random numbers - necessary for the Monte Carlo method below
// Note that C++11 actually provides std::normal_distribution<> in 
// the <random> library, which can be used instead of this function
double gaussian_box_muller() {
  double x = 0.0;
  double y = 0.0;
  double euclid_sq = 0.0;

  // Continue generating two uniform random variables
  // until the square of their "euclidean distance" 
  // is less than unity
  do {
    x = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    y = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    euclid_sq = x*x + y*y;
  } while (euclid_sq >= 1.0);

  return x*sqrt(-2*log(euclid_sq)/euclid_sq);
}

// Pricing a European vanilla call option with a Monte Carlo method
double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(S_cur - K, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

// Pricing a European vanilla put option with a Monte Carlo method
double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(K - S_cur, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

int main(int argc, char **argv) {
  // First we create the parameter list                                                                               
  int num_sims = 10000000;   // Number of simulated asset paths                                                       
  double S = 100.0;  // Option price                                                                                  
  double K = 100.0;  // Strike price                                                                                  
  double r = 0.05;   // Risk-free rate (5%)                                                                           
  double v = 0.2;    // Volatility of the underlying (20%)                                                            
  double T = 1.0;    // One year until expiry                                                                         

  // Then we calculate the call/put values via Monte Carlo                                                                          
  double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
  double put = monte_carlo_put_price(num_sims, S, K, r, v, T);

  // Finally we output the parameters and prices                                                                      
  std::cout << "Number of Paths: " << num_sims << std::endl;
  std::cout << "Underlying:      " << S << std::endl;
  std::cout << "Strike:          " << K << std::endl;
  std::cout << "Risk-Free Rate:  " << r << std::endl;
  std::cout << "Volatility:      " << v << std::endl;
  std::cout << "Maturity:        " << T << std::endl;

  std::cout << "Call Price:      " << call << std::endl;
  std::cout << "Put Price:       " << put << std::endl;

  return 0;
}

les modifications que j'ai apportées ont semblé augmenter le temps de fonctionnement du code d'une seconde, mais je ne suis pas entièrement sûr de ce que je peux changer pour retarder le pipeline sans ajouter de code. Un point à droite direction serait génial, j'apprécie toutes les réponses.


mise à Jour: le professeur qui a donné cette mission posté quelques détails

Les points forts sont:

  • c'est un cours d'architecture du second semestre dans un collège communautaire (en utilisant le manuel de Hennessy et Patterson).
  • les ordinateurs de laboratoire ont des processeurs Haswell
  • les élèves ont été exposés à l'instruction CPUID et à la façon de déterminer la taille du cache, ainsi qu'à l'instruction CLFLUSH .
  • toutes les options du compilateur sont permises, et il en est de même pour l'ASM en ligne.
  • L'écriture de votre propre algorithme de racine carrée a été annoncé comme étant en dehors de la pale

les commentaires de Cowmoogun sur le meta thread indiquent que les optimisations des compilateurs n'étaient pas claires, et supposaient -O0 , et qu'une augmentation de 17% du temps d'exécution était raisonnable.

donc cela ressemble au but de le devoir était d'amener les élèves à réorganiser le travail existant pour réduire le parallélisme au niveau de l'enseignement ou des choses comme ça, mais ce n'est pas une mauvaise chose que les gens aient creusé plus profondément et appris plus.


gardez à l'esprit qu'il s'agit d'une question d'architecture informatique, Pas d'une question sur comment faire ralentir C++ en général.

295
demandé sur Community 0000-00-00 00:00:00
la source

1 ответов

un élément Important de la lecture: Agner de la Brume microarch pdf , et probablement aussi Ulrich Drepper Ce que Chaque Programmeur Doit Savoir à Propos de la Mémoire . Voir aussi les autres liens dans le wiki tag, en particulier les manuels d'optimisation D'Intel, et L'analyse de David Kanter de la microarchitecture Haswell, avec les diagrammes .

très cool devoir; beaucoup mieux que ceux que j'ai vu où étudiants ont été invités à optimiser un certain code pour gcc -O0 , l'apprentissage d'un tas d'astuces qui n'ont pas d'importance dans le code réel. Dans ce cas, on vous demande d'en apprendre davantage sur le pipeline CPU et de vous en servir pour guider vos efforts de dés-optimisation, et non pas simplement de deviner à l'aveuglette. la partie la plus amusante de celle-ci est de justifier chaque pessimisme par une" incompétence diabolique", et non par une malice intentionnelle.


problèmes avec le libellé de l'affectation et le code :

les options spécifiques à uarch pour ce code sont limitées. Il n'utilise pas de tableaux, et une grande partie du coût est des appels aux fonctions de bibliothèque exp / log . Il n'y a pas de façon évidente d'avoir plus ou moins de parallélisme d'instruction, et la chaîne de dépendance en boucle est très courte.

j'aimerais voir une réponse qui tente d'obtenir un ralentissement en réorganisant les expressions pour changer les dépendances, pour réduire ILP juste des dépendances (dangers). Je n'ai pas essayé.

Intel Sandybridge-les CPU de la famille sont des conceptions agressives hors-service qui dépensent beaucoup de transistors et de puissance pour trouver le parallélisme et éviter les risques (dépendances) qui poseraient problème un RISC classique dans l'ordre pipeline . Habituellement, les seuls risques traditionnels qui ralentissent le processus sont les "vraies" dépendances brutes qui limitent le débit par la latence.

WAR et WAW dangers pour les registres sont à peu près pas un problème, merci de vous inscrire renommer . (sauf pour popcnt / lzcnt / tzcnt , qui ont une fausse dépendance de leur destination sur les processeurs Intel , même si c'est en écriture seule. c'est-à-dire WAW étant manipulé comme un danger brut + une écriture). Pour la commande de mémoire, les CPU modernes utilisent magasins Files d'attente pour retarder commettre dans la cache jusqu'à la retraite, en évitant également la guerre et les risques WAW .

la marque de commerce" i7 "a été introduite avec Nehalem (successeur de Core2), et certains manuels Intel disent même "Core i7" quand ils semblent vouloir dire Nehalem, mais ils ont conservé la marque "i7 pour Sandybridge et plus tard microarchitectures. SnB est quand la famille P6 a évolué en une nouvelle espèce, la famille SnB . À bien des égards, Nehalem a plus de points communs avec Pentium III qu'avec Sandybridge (par exemple, les stands de lecture de registre et les stands de lecture ROB-read ne se produisent pas sur SnB, parce qu'il a changé en utilisant un fichier de registre physique. Aussi un cache uop et un format uop interne différent). le terme" architecture i7 "n'est pas utile , parce qu'il n'a pas de sens de grouper les SnB-famille avec Nehalem mais pas Core2. (Nehalem a introduit l'architecture de cache L3 inclusive partagée pour connecter plusieurs noyaux ensemble, cependant. Et aussi des GPU intégrés. Donc au niveau de la puce, le nom a plus de sens.)


résumé des bonnes idées que l'incompétence diabolique peut justifier

même les diaboliquement incompétents sont peu susceptibles d'ajouter un travail évidemment inutile ou une boucle infinie, et faire un le désordre avec les classes C++/Boost dépasse la portée de la tâche.

  • multi-thread avec un seul partagé std::atomic<uint64_t> compteur de boucle, de sorte que le bon nombre total d'itérations se produisent. L'uint64_t atomique est particulièrement mauvais avec -m32 -march=i586 . Pour les points bonus, faites en sorte qu'il soit désaligné, et le franchissement d'une limite de page avec une Division inégale (pas 4:4).
  • False sharing for une autre variable non-atomique- > erreur d'ordre de mémoire-le pipeline de spéculation efface, ainsi que des erreurs de cache supplémentaires.
  • au lieu d'utiliser - sur les variables FP, XOR Le high byte avec 0x80 pour retourner le bit de signe, provoquant stalles de transfert de magasin .
  • Chronomètre chaque itération indépendamment, avec quelque chose de plus lourd que RDTSC . par exemple CPUID / RDTSC ou une fonction de temps qui fait un appel système. Les instructions de sérialisation sont par nature inamicales.
  • Changement multiplie par des constantes d'divise par leur réciproque ("pour la facilité de lecture"). div est lent et pas complètement pipeliné.
  • Vectorisent le multiply/sqrt avec AVX (SIMD), mais n'utilisent pas vzeroupper avant les appels à scalar math-library exp() et log() fonctions, provoquant AVX<->décrochages de transition SSE .
  • stocke la sortie RNG dans une liste liée, ou dans des tableaux que vous traversez hors de l'ordre. Idem pour le résultat de chaque itération, et somme à la fin.

également couvert dans cette réponse, mais exclu du résumé: suggestions qui seraient tout aussi lents sur un CPU Non pipeliné, ou qui ne semblent pas être justifiables, même avec une incompétence diabolique. par exemple, de nombreuses idées de gimp-the-compilateur qui produisent évidemment différent / pire asm.


multi-thread badly

peut-être utiliser des boucles OpenMP à multi-thread avec très peu d'itérations, avec beaucoup plus de dépassement que le gain de vitesse. Votre code monte-carlo a assez de parallélisme pour obtenir une accélération. si nous réussissons à ralentir chaque itération. (Chaque fil calcule un payoff_sum partiel, ajouté à la fin). #omp parallel sur cette boucle serait probablement une optimisation, pas un pessimization.

Multi-thread, mais la force les deux threads partagent le même compteur de boucle (avec atomic incréments de sorte que le nombre total d'itérations est correct). Cela semble diaboliquement logique. Cela signifie utiliser une variable static comme compteur de boucle. Cela justifie l'utilisation de atomic pour les compteurs de boucle, et crée le ping-pong de cache-ligne (tant que les threads ne fonctionnent pas sur le même noyau physique avec l'hyperthreading, ce qui risquerait de ne pas être comme lent). Quoi qu'il en soit, c'est beaucoup plus lent que le cas non contesté pour lock inc . Et lock cmpxchg8b atomiquement incrémenter un prétendu uint64_t sur un système 32 bits devrez recommencer en boucle au lieu d'avoir le matériel arbitrer atomique inc .

crée aussi faux partage , où plusieurs threads conservent leurs données privées (e.g. RNG state) dans différents octets de la même ligne de cache. (tutoriel Intel à ce sujet, y compris les compteurs de perf à regarder) . il y a un aspect spécifique à la microarchitecture de ce : les CPUs Intel spéculent sur le mauvais ordre de la mémoire pas et il y a un machine à commande de mémoire-événement perf clair pour le détecter, au moins sur P4 . La pénalité pourrait ne pas être aussi grande sur Haswell. En tant que link fait remarquer qu'une instruction lock de suppose que cela va se produire, en évitant les fausses spéculations. Une charge normale suppose que les autres noyaux n'invalident pas une ligne de cache entre le moment où la charge s'exécute et le moment où elle se retire dans l'ordre du programme ( sauf si vous utilisez pause ). Un vrai partage sans instructions lock ed est généralement un bug. Il serait intéressant de comparer un compteur à boucle partagée non atomique avec le cas atomique. Vraiment pessimize, garder le compteur de boucle atomique partagée, et provoque un faux partage dans la même ligne de cache ou une ligne différente pour une autre variable.


Aléatoire uarch des idées spécifiques:

si vous pouvez introduire n'importe quelles branches imprévisibles , cela pessimisera le code considérablement. Les CPU x86 modernes ont des pipelines assez longs, de sorte qu'une erreur d'interprétation coûte ~15 cycles (en courant depuis le cache uop).


chaînes de dépendances:

je pense que c'était l'une des pièces de la cession.

contrecarre la capacité du CPU à exploiter le parallélisme d'instruction En choisissant un ordre d'opérations qui a une chaîne de dépendance longue au lieu de chaînes de dépendance courtes et multiples. Les compilateurs ne sont pas autorisés à changer l'ordre des opérations pour les calculs FP sauf si vous utilisez -ffast-math , parce que cela peut changer les résultats (voir ci-dessous).

pour vraiment rendre cela efficace, augmentez la longueur d'une chaîne de dépendances portée en boucle. Rien n'est aussi évident: les boucles telles qu'elles sont écrites ont des chaînes de dépendances très courtes: juste un FP add. (3 cycles). Plusieurs itérations peuvent avoir leurs calculs en vol à la fois, car ils peuvent commencer bien avant le payoff_sum += à la fin de l'itération précédente. ( log() et exp prendre beaucoup d'instructions, mais pas beaucoup plus que la fenêtre de Haswell pour trouver le parallélisme: ROB size=192 UOPs domaine fusionné, et scheduler size=60 uops domaine non fusionné . Dès que l'exécution de l'itération en cours progresse suffisamment loin pour faire place aux instructions de la prochaine itération à émettre, toute partie de celui-ci qui ont leurs entrées prêtes (c.-à-d. indépendant/séparée chaîne dep) peut commencer à exécuter lorsque les anciennes instructions laissent les unités d'exécution libres (par exemple parce qu'ils sont bloqués sur la latence, pas sur le débit.).

l'état de RNG sera presque certainement une chaîne de dépendance plus longue portée que le addps .


Utilisation lent, plus FP opérations (esp. plus de division):

Diviser par 2.0 au lieu de multiplier par 0,5, et ainsi de suite. FP multiplie est fortement pipeliné dans les conceptions Intel, et a un pour 0,5 C le débit sur Haswell et plus tard. FP divsd / divpd n'est que partiellement canalisée . (Bien que Skylake ait un débit impressionnant de un par 4C pour divpd xmm , avec une latence de 13-14c, vs pas pipeliné du tout sur Nehalem (7-22c)).

le do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); est clairement un test pour une distance, donc clairement il serait approprié de sqrt() il. : P ( sqrt est encore plus lent que div ).

comme le suggère @Paul Clayton, réécrire les expressions avec des équivalents associatifs/distributifs peuvent introduire plus de travail (tant que vous n'utilisez pas -ffast-math pour permettre au compilateur de re-optimiser). (exp(T*(r-0.5*v*v)) pourrait devenir exp(T*r - T*v*v/2.0) . Notez que si les maths sur les nombres réels sont associatives, les maths à virgule flottante est pas , même sans tenir compte de débordement/NaN (ce qui explique pourquoi -ffast-math n'est pas activé par défaut). Voir le commentaire de Paul pour une chevelure imbriqué pow() suggestion.

si vous pouvez réduire les calculs à de très petits nombres, alors FP mathématiques ops prendre ~120 cycles supplémentaires pour piéger au microcode quand une opération sur deux nombres normaux produit un denormal . Consultez le fichier PDF microarch d'Agner Fog pour les nombres exacts et les détails. C'est peu probable puisque vous avez beaucoup de multiplier, de sorte que le facteur d'échelle serait au carré et dépassement bas tout le chemin à 0.0. Je ne vois pas de moyen de justifier l'échelle nécessaire avec incompétence (même diabolique), seulement malice intentionnel.


si vous pouvez utiliser intrinsics ( <immintrin.h> )

utilisez movnti pour supprimer vos données de cache . Diabolique: c'est nouveau et faiblement commandé, donc ça devrait laisser le CPU le faire plus vite, Non? Ou voir cette question liée pour un cas où quelqu'un était en danger de faire exactement cela (pour dispersés écrit où seuls certains endroits étaient chauds). clflush est probablement impossible sans malice.

utilisez des battements d'entiers entre les opérations de mathématiques FP pour causer des retards de contournement.

le mélange des instructions SSE et AVX sans l'utilisation appropriée de vzeroupper provoque de grands décrochages dans le pré-Skylake (et une pénalité différente dans Skylake ). Même sans ça, vectoriser mal peut être pire que scalar (plus de cycles passés mélangeant des données dans/hors des vecteurs que sauvé en faisant les opérations add/sub/mul/div/sqrt pour 4 itérations Monte-Carlo à la fois, avec 256b vecteurs). les unités d'exécution add/sub/mul sont complètement pipelinées et de pleine largeur, mais div et sqrt sur les vecteurs 256b ne sont pas aussi rapides que sur les vecteurs 128b (ou scalaires), donc l'accélération n'est pas dramatique pour double .

exp() et log() n'ont pas de matériel support, de sorte que cette partie nécessite l'extraction des éléments vectoriels vers scalar et l'appel de la fonction de bibliothèque séparément, puis mélangeant les résultats de nouveau dans un vecteur. libm est généralement compilé pour n'utiliser que SSE2, donc utilisera les encodages legacy-SSE des instructions de maths scalaires. Si votre code utilise des vecteurs 256b et appelle exp sans faire d'abord un vzeroupper , alors vous décrochez. Après le retour, une instruction AVX-128 comme vmovsd pour configurer l'élément vecteur suivant comme arg pour exp va également décrocher. Et puis exp() va décrocher à nouveau quand il exécute une instruction SSE. C'est exactement ce qui s'est passé dans cette question , provoquant un 10x ralentissement. (Merci @ZBoson).

Voir aussi Nathan de Kurz expériences avec d'Intel math lib vs glibc pour ce code . Future glibc viendra avec mises en œuvre vectorisées de exp() et ainsi sur.


Si le ciblage de pré-IvB, ou esp. Nehalem, essayez de faire en sorte que gcc cause des décrochages de registre partiel avec des opérations de 16bit ou 8bit suivies par des opérations de 32bit ou 64bit. Dans la plupart des cas, gcc utilisera movzx après une opération de 8 ou 16 bits, mais voici un cas où gcc modifie ah et lit alors ax


avec) asm:

avec (inline) asm, vous pouvez casser le cache uop: un morceau de code 32B qui ne rentre pas dans trois lignes de cache 6uop force un commutateur du cache uop vers les décodeurs. Un ALIGN incompétent utilisant de nombreux nop s à un seul octet au lieu d'un couple long nop s sur une cible de branche à l'intérieur de la boucle interne pourrait faire l'affaire. Ou mettez le rembourrage d'alignement après l'étiquette, au lieu d'avant. Cela n'a D'importance que si le front est un goulot d'étranglement, ce qui ce ne sera pas le cas si nous réussissons à pessimiser le reste du code.

utiliser le code d'auto-modification pour déclencher les dégagements de pipeline (alias machine-nukes).

les décrochages LCP à partir d'instructions 16bit avec des instantanés trop grands pour s'insérer en 8 bits sont peu susceptibles d'être utiles. Le cache uop sur SnB et plus tard signifie que vous ne payez la pénalité de décodage qu'une seule fois. Sur Nehalem (le premier i7), il pourrait fonctionner pour une boucle qui ne rentre pas dans la boucle 28 uop tampon. gcc générera parfois de telles instructions, même avec -mtune=intel et quand il aurait pu utiliser une instruction 32bit.


un idiome courant pour le timing est CPUID (pour sérialiser) puis RDTSC . Chronomètre chaque itération séparément avec un CPUID / RDTSC pour s'assurer que le RDTSC n'est pas réordonné avec des instructions plus tôt, ce qui ralentira les choses vers le bas un lot . (Dans la vie réelle, la façon intelligente de chronométrer est de chronométrer toutes les itérations ensemble, au lieu de chronométrer chaque itération séparément et de les additionner).


Causer beaucoup de défauts de cache et de la mémoire d'autres ralentissements

utilisez un union { double d; char a[8]; } pour certaines de vos variables. Cause un magasin de transfert de décrochage en faisant un étroit magasin (ou de Lecture-modification-Écriture) à l'une de octet. (Cet article du wiki couvre aussi beaucoup d'autres choses de microarchitecture pour les files d'attente de charge/magasin). par exemple inversez le signe d'un double en utilisant XOR 0x80 sur le seul octet haut , au lieu d'un opérateur - . Le développeur diaboliquement incompétent peut avoir entendu que FP est plus lent que integer, et donc essayer de faire autant que possible en utilisant integer ops. (Un très bon compilateur ciblant FP math dans les registres SSE peut éventuellement compiler ceci à un xorps avec une constante dans un autre registre xmm, mais le seul moyen que ce ne soit pas terrible pour x87 est que le compilateur réalise qu'il nie la valeur et remplace l'add suivant par une soustraction.)


utilisez volatile si vous compilez avec -O3 et que vous n'utilisez pas std::atomic , pour forcer le compilateur à stocker/recharger partout. Des variables globales (au lieu de locales) forceront également certains magasins/ recharges, mais la faible commande du modèle mémoire C++ ne nécessite pas que le compilateur renverse/recharge en mémoire tout le temps.

remplacez les variateurs locaux avec les membres d'une grande structure, de sorte que vous pouvez contrôler la disposition de la mémoire.

utilise des tableaux dans la structure pour capitonner (et stocker des nombres aléatoires, pour justifier leur existence).

Choisissez votre disposition de la mémoire afin de tout va dans une ligne différente dans le même "set" dans le cache L1 . C'est seulement 8-way associative, c.-à-d. chaque ensemble a 8 "ways". Les lignes de Cache sont 64B.

encore mieux, mettre les choses exactement 4096B de côté, depuis charges ont une fausse dépendance sur les magasins à des pages différentes, mais avec le même offset dans une page . désambiguïsation mémoire pour comprendre quand les charges et les stocks peuvent être réorganisés sans changer les résultats , et L'implémentation D'Intel a des faux positifs qui empêchent les charges de commencer tôt. Il est probable qu'ils ne vérifient que les bits sous le décalage de la page, de sorte que la vérification peut commencer avant que le TLB n'ait traduit les bits élevés d'une page virtuelle vers une page physique. En plus du guide D'Agner, voir une réponse de Stephen Canon , et aussi une section vers la fin de la réponse de @Krazy Glew sur la même question. (Andy Glew était l'un des architectes de La microarchitecture P6 originale d'Intel.)

utilisez __attribute__((packed)) pour vous permettre de mal aligner les variables afin qu'elles couvrent les limites des lignes de cache ou même des pages. (Ainsi, une charge d'un double nécessite des données provenant de deux lignes de cache). Les charges mal alignées n'ont pas de pénalité dans les uarch Intel i7, sauf lors du passage de lignes de cache et de lignes de page. Cache-ligne se sépare encore de prendre un supplément de cycles . Skylake réduit considérablement la pénalité pour les charges fractionnées de page, de 100 à 5 cycles. (Section 2.1.3) . Peut-être lié à être en mesure de faire deux promenades de page en parallèle.

Une page-split atomic<uint64_t> devrait être à peu près le pire des cas , esp. si c'est 5 bytes dans une page et 3 bytes dans l'autre page, ou autre chose que 4:4. Même les fentes au milieu sont plus efficaces pour les fentes de ligne de cache avec des vecteurs 16B sur certains uarches, IIRC. Tout mettre dans un alignas(4096) struct __attribute((packed)) (pour sauver espace, bien sûr), y compris un tableau pour le stockage des résultats RNG. Obtenir le mauvais alignement en utilisant uint8_t ou uint16_t pour quelque chose devant le comptoir.

si vous pouvez obtenir le compilateur d'utiliser des modes d'adressage indexés, cela va vaincre UOP micro-fusion . Peut-être en utilisant #define pour remplacer les variables scalaires simples par my_data[constant] .

Si vous pouvez introduire un niveau supplémentaire d'indirection, ainsi, les adresses de chargement et de stockage ne sont pas connues en avance, ce qui peut être encore plus pessimiste.


tableaux de Traverse en ordre non contigu

je pense que nous pouvons trouver une justification incompétente pour introduire un tableau en premier lieu: il nous permet de séparer la génération de nombres aléatoires de l'utilisation de nombres aléatoires. Les résultats de chaque itération pourraient également être stockés dans un tableau, à résumer plus tard (avec une incompétence plus diabolique).

pour "aléatoire maximum", nous pourrions avoir un thread bouclant au-dessus du tableau aléatoire en y écrivant de nouveaux nombres aléatoires. Le thread consommant les nombres aléatoires pourrait générer un index aléatoire pour charger un nombre aléatoire à partir. (Il y a du travail à faire ici, mais sur le plan microarchitectural, cela aide à connaître les adresses de chargement tôt afin que toute latence de charge possible puisse être résolue avant que les données chargées ne soient nécessaires.) Avoir un lecteur et un rédacteur sur différents noyaux causera le pipeline d'erreur de commande de mémoire s'efface (comme discuté précédemment pour le cas du faux partage).

pour un maximum de pessimisation, boucle sur votre tableau avec une foulée de 4096 octets (c.-à-d. 512 doubles). par exemple

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

donc le schéma d'accès est 0, 4096, 8192,...,

8, 4104, 8200, ...

16, 4112, 8208, ...

C'est ce que vous obtiendriez pour accéder à un tableau 2D comme double rng_array[MAX_ROWS][512] dans le mauvais ordre (boucle sur des lignes, au lieu de colonnes dans une ligne dans la boucle intérieure, comme suggéré par @JesperJuhl). Si l'incompétence diabolique peut justifier un tableau 2D avec des dimensions comme celle-là, l'incompétence du monde réel de la variété de jardin justifie facilement la boucle avec le mauvais modèle d'accès. Cela se produit en vrai code dans la vie réelle.

ajuster les limites de boucle si nécessaire pour utiliser de nombreuses pages différentes au lieu de réutiliser les mêmes quelques pages, si le tableau n'est pas si grande que cela. La préfetching du matériel ne fonctionne pas (aussi bien/pas du tout) à travers les pages. Le préfetcher peut suivre un flux avant et un flux arrière à l'intérieur de chaque page (ce qui est ce qui se passe ici), mais n'agira que si la bande passante de la mémoire n'est pas déjà saturée de non-préfetch.

cela générera aussi beaucoup de manques TLB, à moins que les pages soient fusionnées dans une page d'accueil ( Linux fait cela de façon opportuniste pour anonymous (pas de) allocations comme malloc / new qui utilisent mmap(MAP_ANONYMOUS) 1519990920").

au Lieu d'un tableau pour stocker la liste de résultats, vous pouvez utiliser un liste . Ensuite, chaque itération nécessiterait une charge de chasse à l'aiguille (un risque de dépendance réel brut pour l'adresse de charge de la charge suivante). Avec un mauvais allocator, vous pourriez réussir à disperser les noeuds de liste autour de la mémoire, défaisant le cache. Avec un allocateur diaboliquement incompétent, il pourrait mettre chaque nœud au début de sa propre page. (par exemple, attribuer directement avec mmap(MAP_ANONYMOUS) , sans fractionner les pages ou suivre les tailles des objets pour supporter correctement free ).


ce ne sont pas vraiment spécifiques à la microarchitecture, et ont peu à voir avec le pipeline (la plupart de ceux-ci seraient également un ralentissement sur un CPU Non-pipeliné).

un peu hors-sujet: faire que le compilateur génère du code pire / faire plus de travail:

utilisez C++11 std::atomic<int> et std::atomic<double> pour le code le plus pessimiste. Les instructions "MFENCEs" et lock ed sont assez lentes, même si elles ne sont pas contestées par un autre fil.

-m32 va rendre le code plus lent, parce que le code x87 sera pire que le code SSE2. La convention d'appel 32bit basée sur la pile prend plus d'instructions, et passe même FP args sur la pile à des fonctions comme exp() .

380
répondu
la source

Autres questions sur c++ optimization x86 cpu-architecture intel