Cela fait une semaine que je crève le cerveau en essayant de terminer cette mission et j'espère que quelqu'un ici peut me conduire sur la bonne voie. Permettez-moi de commencer par les instructions de l'instructeur:

Votre mission est l'opposé de notre première mission de laboratoire, qui consistait à optimiser un programme de nombres premiers. Votre objectif dans cette tâche est de pessimiser le programme, c'est-à-dire de le ralentir. Ces deux programmes sont gourmands en ressources processeur. Ils prennent quelques secondes à s'exécuter sur nos PC de laboratoire. Vous ne pouvez pas modifier l'algorithme.

Pour désoptimiser le programme, utilisez vos connaissances sur le fonctionnement du pipeline Intel i7. Imaginez des façons de réorganiser les chemins d'instructions pour introduire WAR, RAW et d'autres dangers. Réfléchissez aux moyens de minimiser l'efficacité du cache. Soyez diaboliquement incompétent.

La mission a donné un choix de programmes Whetstone ou Monte-Carlo. Les commentaires sur l'efficacité du cache ne sont généralement applicables qu'à 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 d'exécution du code d'une seconde, mais je ne suis pas tout à fait sûr de ce que je peux changer pour bloquer le pipeline sans ajouter de code. Un point dans la bonne direction serait génial, j'apprécie toutes les réponses.

Mise à jour: le professeur qui a donné cette mission a publié quelques détails

Les faits saillants sont:

• Il s'agit d'un cours d'architecture du deuxième semestre dans un collège communautaire (en utilisant le manuel Hennessy et Patterson).
• les ordinateurs de laboratoire ont des processeurs Haswell
• Les étudiants ont été exposés à l' CPUIDinstruction et à la façon de déterminer la taille du cache, ainsi que les éléments intrinsèques et l' CLFLUSHinstruction.
• toutes les options du compilateur sont autorisées, tout comme l'asm en ligne.
• L'écriture de votre propre algorithme de racine carrée a été annoncée comme étant hors du commun

Les commentaires de Cowmoogun sur le fil méta indiquent qu'il n'était pas clair que les optimisations du compilateur pouvaient en faire partie, et supposaient-O0 , et qu'une augmentation de 17% du temps d'exécution était raisonnable.

Il semble donc que l'objectif du devoir était d'amener les étudiants à réorganiser le travail existant afin de 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 approfondi et appris davantage.

Gardez à l'esprit qu'il s'agit d'une question d'architecture informatique, pas d'une question sur la façon de ralentir le C ++ en général.

Lecture de fond importante: le microarch pdf d'Agner Fog , et probablement aussi ce que chaque programmeur devrait savoir sur la mémoire d' Ulrich Drepper . Voir aussi les autres liens dans lex86wiki wiki, en particulier les manuels d'optimisation d'Intel, et l' analyse de David Kanter de la microarchitecture Haswell, avec des diagrammes .

Affectation très cool; beaucoup mieux que ceux que j'ai vus où les étudiants ont été invités à optimiser du codegcc -O0 , en apprenant un tas d'astuces qui n'ont pas d'importance dans le vrai code. Dans ce cas, vous êtes invité à en apprendre davantage sur le pipeline du processeur et à l'utiliser pour guider vos efforts de désoptimisation, pas seulement les devinettes aveugles. La partie la plus amusante de celle-ci est de justifier chaque pessimisation par une "incompétence diabolique" et non par une malveillance intentionnelle.

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

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 exp/ logbibliothèque. Il n'y a pas de moyen évident d'avoir plus ou moins de parallélisme au niveau de l'instruction, et la chaîne de dépendance portée par la boucle est très courte.

J'adorerais voir une réponse qui tenterait d'obtenir un ralentissement de la réorganisation des expressions pour changer les dépendances, pour réduire l' ILP uniquement des dépendances (dangers). Je ne l'ai pas tenté.

Les processeurs de la famille Intel Sandybridge sont des conceptions agressives hors service qui dépensent beaucoup de transistors et d'énergie pour trouver le parallélisme et éviter les dangers (dépendances) qui pourraient perturber un pipeline de commande RISC classique . Habituellement, les seuls dangers traditionnels qui le ralentissent sont les "vraies" dépendances RAW qui limitent le débit par la latence.

Les dangers de WAR et WAW pour les registres ne sont pratiquement pas un problème, grâce au changement de nom des registres . (sauf pourpopcnt/lzcnt/tzcnt, qui ont une fausse dépendance de leur destination sur les processeurs Intel , même si elle estécriture seule. WAWdire être manipulé comme un danger RAW + une écriture). Pour la commande de la mémoire, les processeurs modernes utilisent les files d'attente de stockage pour retarder la validation dans le cache jusqu'à la retraite, évitant également les risques WAR et WAW .

Pourquoi le mulss ne prend-il que 3 cycles sur Haswell, différent des tableaux d'instructions d'Agner? a plus sur le changement de nom de registre et le masquage de la latence FMA dans une boucle de produit point FP.

Le nom de marque «i7» a été introduit avec Nehalem (successeur de Core2) , et certains manuels Intel disent même «Core i7» quand ils semblent signifier Nehalem, mais ils ont conservé la marque «i7» pour Sandybridge et les microarchitectures ultérieures. SnB, c'est quand la famille P6 a évolué en une nouvelle espèce, la famille SnB . À bien des égards, Nehalem a plus en commun avec Pentium III qu'avec Sandybridge (par exemple, les blocages de lecture de registre et les blocages de lecture ROB ne se produisent pas sur SnB, car cela a changé en utilisant un fichier de registre physique. Aussi un cache uop et un autre interne format uop). Le terme "architecture i7" n'est pas utile, car il est peu logique de regrouper la famille SnB avec Nehalem mais pas Core2. (Nehalem a cependant introduit l'architecture de cache L3 partagée partagée pour connecter plusieurs cœurs ensemble. Et également des GPU intégrés. Au niveau de la puce, la dénomination a plus de sens.)

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

Même les diaboliquement incompétents ont peu de chances d'ajouter un travail manifestement inutile ou une boucle infinie, et faire un gâchis avec les classes C ++ / Boost dépasse la portée de l'affectation.

• Multi-thread avec un seul compteur de boucle partagée std::atomic<uint64_t> , de sorte que le bon nombre total d'itérations se produise. Atomic uint64_t est particulièrement mauvais avec -m32 -march=i586. Pour les points bonus, faites en sorte qu'ils soient mal alignés et franchissent une limite de page avec une division inégale (pas 4: 4).
• Faux partage pour une autre variable non atomique -> Le pipeline de spéculation erronée d'ordre de mémoire s'efface, ainsi que les erreurs de cache supplémentaires.
• Au lieu d'utiliser des -variables FP, XOR l'octet de poids fort avec 0x80 pour inverser le bit de signe, provoquant des blocages de transfert de magasin .
• Temps chaque itération indépendamment, avec quelque chose de plus lourd que RDTSC. par exemple CPUID/ RDTSCou une fonction de temps qui fait un appel système. Les instructions de sérialisation sont intrinsèquement hostiles aux pipelines.
• Le changement se multiplie par des constantes pour se diviser par leur réciproque ("pour faciliter la lecture"). div est lent et pas entièrement canalisé.
• Vectorisez la multiplication / sqrt avec AVX (SIMD), mais ne parvenez pas à l'utiliser vzeroupperavant les appels à la bibliothèque exp()et aux log()fonctions mathématiques scalaires , ce qui provoque des blocages de transition AVX <-> SSE .
• Stockez la sortie RNG dans une liste chaînée ou dans des tableaux que vous parcourez dans le désordre. Idem pour le résultat de chaque itération, et somme à la fin.

Également couvert dans cette réponse, mais exclus du résumé: des suggestions qui seraient tout aussi lentes sur un processeur non canalisé, ou qui ne semblent pas être justifiables même avec une incompétence diabolique. par exemple de nombreuses idées de gimp-the-compiler qui produisent un asm évidemment différent / pire.

Multi-thread mal

Peut-être utiliser OpenMP pour des boucles multi-thread avec très peu d'itérations, avec beaucoup plus de surcharge que de gain de vitesse. Votre code monte-carlo a suffisamment de parallélisme pour obtenir une accélération, cependant, en particulier. si nous parvenons à ralentir chaque itération. (Chaque thread calcule un partiel payoff_sum, ajouté à la fin). #omp parallelsur cette boucle serait probablement une optimisation, pas une pessimisation.

Multi-thread mais force les deux threads à partager le même compteur de boucles (avec des atomicincréments pour que le nombre total d'itérations soit correct). Cela semble diaboliquement logique. Cela signifie utiliser une staticvariable comme compteur de boucle. Cela justifie l'utilisation des atomiccompteurs de boucles for et crée un ping-pong de ligne de cache réel (tant que les threads ne s'exécutent pas sur le même noyau physique avec hyperthreading; cela pourrait ne pas être aussi lent). Quoi qu'il en soit, c'est beaucoup plus lent que le cas non contesté pour lock inc. Et lock cmpxchg8bpour incrémenter atomiquement un concurrent uint64_tsur un système 32 bits devra réessayer dans une boucle au lieu d'avoir le matériel arbitrer un atomique inc.

Créez également un faux partage , où plusieurs threads conservent leurs données privées (par exemple, l'état RNG) dans différents octets de la même ligne de cache. (Tutoriel Intel à ce sujet, y compris les compteurs de performances à consulter) . Il y a un aspect spécifique à la microarchitecture à cela : les processeurs Intel spéculent sur le fait qu'un mauvais ordre de la mémoire ne se produit pas , et il y a un événement de performance d'effacement de la mémoire pour détecter cela, au moins sur P4 . La pénalité pourrait ne pas être aussi importante pour Haswell. Comme le souligne ce lien, une lockinstruction ed suppose que cela se produira, évitant les spéculations erronées. Une charge normale spécule que d'autres cœurs n'invalideront pas une ligne de cache entre le moment où le chargement s'exécute et le moment où il se retire dans l'ordre du programme (sauf si vous utilisezpause ). Le vrai partage sans lockinstructions ed est généralement un bug. Il serait intéressant de comparer un compteur de boucle partagée non atomique avec le cas atomique. Pour vraiment pessimiser, conservez le compteur de boucle atomique partagée et provoquez un faux partage dans la même ou une ligne de cache différente pour une autre variable.

Idées aléatoires spécifiques aux uarques:

Si vous pouvez introduire des branches imprévisibles , cela pessimisera considérablement le code. Les processeurs x86 modernes ont des pipelines assez longs, donc une erreur de prévision coûte environ 15 cycles (lors de l'exécution à partir du cache uop).

Chaînes de dépendance:

Je pense que c'était l'une des parties prévues de la mission.

Éliminez la capacité du processeur à exploiter le parallélisme au niveau des instructions en choisissant un ordre d'opérations qui a une longue chaîne de dépendances au lieu de plusieurs courtes chaînes de dépendances. Les compilateurs ne sont pas autorisés à modifier l'ordre des opérations pour les calculs de FP, sauf si vous les utilisez -ffast-math, car cela peut modifier les résultats (comme expliqué ci-dessous).

Pour vraiment rendre cela efficace, augmentez la longueur d'une chaîne de dépendances en boucle. Cependant, rien ne saute aux yeux: les boucles telles qu'elles sont écrites ont des chaînes de dépendance très courtes véhiculées par les boucles: juste un ajout de FP. (3 cycles). Plusieurs calculs peuvent avoir leurs calculs en vol à la fois, car ils peuvent commencer bien avant payoff_sum +=la fin de l'itération précédente. ( log()et expprenez de nombreuses instructions, mais pas beaucoup plus que la fenêtre hors service de Haswell pour trouver le parallélisme: taille ROB = 192 uops de domaine fusionné et taille de l'ordonnanceur = 60 uops de domaine non fusionné. Dès que l'exécution de l'itération en cours progresse suffisamment pour faire place aux instructions de la prochaine itération, toutes les parties qui ont leurs entrées prêtes (c.-à-d. Chaîne de dépôt indépendante / séparée) peuvent commencer à s'exécuter lorsque des instructions plus anciennes quittent les unités d'exécution. gratuit (par exemple parce qu'ils sont goulot d'étranglement sur la latence, pas sur le débit.).

L'état RNG sera presque certainement une chaîne de dépendance à boucle plus longue que la addps.

Utilisez des opérations de FP plus lentes / plus nombreuses (en particulier plus de division):

Divisez par 2,0 au lieu de multiplier par 0,5, etc. FP multiply est fortement canalisé dans les conceptions Intel et a un débit par 0,5c sur Haswell et versions ultérieures. FP divsd/ divpdn'est que partiellement canalisé . (Bien que Skylake ait un impressionnant débit par 4c pour divpd xmm, avec une latence de 13-14c, vs pas du tout canalisé sur Nehalem (7-22c)).

Le do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0);teste clairement une distance, il est donc clairement approprié sqrt(). : P ( sqrtest encore plus lent que div).

Comme le suggère @Paul Clayton, la réécriture d'expressions avec des équivalents associatifs / distributifs peut introduire plus de travail (tant que vous n'utilisez pas -ffast-mathpour permettre au compilateur de se ré-optimiser). (exp(T*(r-0.5*v*v))pourrait devenir exp(T*r - T*v*v/2.0). Notez que si les mathématiques sur les nombres réels sont associatives, les mathématiques en virgule flottante ne le sont pas , même sans tenir compte du débordement / NaN (ce qui explique pourquoi il -ffast-mathn'est pas activé par défaut). Voir le commentaire de Paul pour une pow()suggestion imbriquée très velue .

Si vous pouvez réduire les calculs à de très petits nombres, les opérations mathématiques FP prennent environ 120 cycles supplémentaires pour être capturées dans le microcode lorsqu'une opération sur deux nombres normaux produit un dénormal . Voir le fichier microarch d'Agner Fog pdf pour les chiffres et les détails exacts. Cela est peu probable car vous avez beaucoup de multiplications, donc le facteur d'échelle serait carré et sous-jacent jusqu'à 0,0. Je ne vois aucun moyen de justifier la mise à l'échelle nécessaire avec de l'incompétence (même diabolique), seulement de la malveillance intentionnelle.

Si vous pouvez utiliser intrinsèques ( <immintrin.h>)

Utilisez movntipour expulser vos données du cache . Diabolique: il est nouveau et peu ordonné, ce qui devrait permettre au CPU de l'exécuter plus rapidement, non? Ou voir cette question liée pour un cas où quelqu'un était en danger de faire exactement cela (pour des écritures dispersées où seuls certains des emplacements étaient chauds). clflushest probablement impossible sans méchanceté.

Utilisez des shuffles entiers entre les opérations mathématiques FP pour provoquer des retards de contournement.

Le fait de mélanger les instructions SSE et AVX sans une utilisation appropriée vzeroupperprovoque de gros décrochages dans pré-Skylake (et une pénalité différente dans Skylake ). Même sans cela, la vectorisation peut être pire que scalaire (plus de cycles passés à mélanger les données dans / hors des vecteurs que enregistrés 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 entièrement pipelinées et 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 dramatiquedouble.

exp()et log()ne disposent pas de prise en charge matérielle, de sorte que cette partie nécessiterait d'extraire les éléments vectoriels vers scalaire et d'appeler la fonction de bibliothèque séparément, puis de mélanger les résultats dans un vecteur. libm est généralement compilé pour utiliser uniquement SSE2, il utilisera donc les encodages legacy-SSE des instructions mathématiques scalaires. Si votre code utilise des vecteurs 256b et appelle expsans faire de vzeroupperpremier, alors vous bloquez. Après son retour, une instruction AVX-128, comme vmovsdconfigurer l'argument vectoriel suivant comme argument pour, expsera également bloquée. Et puis exp()se bloque à nouveau lorsqu'il exécute une instruction SSE. C'est exactement ce qui s'est passé dans cette question , provoquant un ralentissement de 10x. (Merci @ZBoson).

Voir aussi les expériences de Nathan Kurz avec la lib mathématique d'Intel contre la glibc pour ce code . La future glibc viendra avec des implémentations vectorisées de exp()et ainsi de suite.

Si le ciblage pré-IvB, ou esp. Nehalem, essayez d'obtenir gcc pour provoquer des blocages de registres partiels avec des opérations 16 bits ou 8 bits suivies par des opérations 32 bits ou 64 bits. Dans la plupart des cas, gcc utilisera movzxaprès une opération 8 ou 16 bits, mais voici un cas où gcc modifie ahpuis litax

Avec (inline) asm:

Avec (inline) asm, vous pourriez casser le cache uop: un morceau de code 32B qui ne tient pas dans trois lignes de cache 6uop force un basculement du cache uop vers les décodeurs. Un incompétent ALIGNutilisant de nombreux nops à un octet au lieu de quelques nops longs sur une branche cible à l'intérieur de la boucle interne pourrait faire l'affaire. Ou placez le rembourrage d'alignement après l'étiquette, au lieu d'avant. : P Cela n'a d'importance que si le frontend est un goulot d'étranglement, ce qui ne sera pas le cas si nous parvenons à pessimiser le reste du code.

Utilisez du code auto-modifiable pour déclencher des effacements de pipeline (aka machine-nukes).

Les blocages LCP à partir d'instructions 16 bits avec des éléments intermédiaires trop grands pour tenir sur 8 bits sont peu susceptibles d'être utiles. Le cache uop sur SnB et versions ultérieures signifie que vous ne payez la pénalité de décodage qu'une seule fois. Sur Nehalem (le premier i7), cela pourrait fonctionner pour une boucle qui ne tient pas dans le tampon de boucle 28 uop. gcc générera parfois de telles instructions, même avec -mtune=intelet quand il aurait pu utiliser une instruction 32 bits.

Un idiome commun pour le timing est alors CPUID(pour sérialiser)RDTSC . Temps chaque itération séparément avec un CPUID/ RDTSCpour vous assurer que le RDTSCn'est pas réorganisé avec des instructions antérieures, ce qui ralentira beaucoup les choses . (Dans la vraie vie, la façon intelligente de chronométrer est de chronométrer toutes les itérations ensemble, au lieu de chronométrer chacune séparément et de les additionner).

Cause de nombreux échecs de cache et autres ralentissements de mémoire

Utilisez un union { double d; char a[8]; }pour certaines de vos variables. Provoquer un blocage de transfert de magasin en effectuant un stockage étroit (ou lecture-modification-écriture) sur un seul des octets. (Cet article wiki couvre également beaucoup d'autres éléments microarchitecturaux pour les files d'attente de chargement / stockage). par exemple, inverser le signe d'un doubleXOR 0x80 en utilisant uniquement l'octet de poids fort , au lieu d'un -opérateur. Le développeur diaboliquement incompétent a peut-être entendu que FP est plus lent que l'entier, et essaie donc d'en faire autant que possible en utilisant des opérations entières. (Un très bon compilateur ciblant les mathématiques FP dans les registres SSE peut éventuellement compilerxorps avec une constante dans un autre registre xmm, mais le seul moyen pour que ce ne soit pas terrible pour x87 est que le compilateur réalise qu'il annule la valeur et remplace l'ajout suivant par une soustraction.)

Utilisez volatilesi vous compilez avec -O3et n'utilisez pas std::atomic, pour forcer le compilateur à réellement stocker / recharger partout. Les variables globales (au lieu des locales) forceront également certains magasins / rechargements, mais le faible ordre du modèle de mémoire C ++ ne nécessite pas que le compilateur se répande / recharge en mémoire tout le temps.

Remplacez les variables locales par des membres d'une grande structure, afin que vous puissiez contrôler la disposition de la mémoire.

Utilisez des tableaux dans la structure pour le remplissage (et le stockage de nombres aléatoires, pour justifier leur existence).

Choisissez votre disposition de mémoire de sorte que tout se passe sur une ligne différente dans le même "ensemble" dans le cache L1 . C'est seulement associatif à 8 voies, c'est-à-dire que chaque ensemble a 8 "voies". Les lignes de cache sont 64B.

Encore mieux, séparez les choses exactement 4096B, car les charges ont une fausse dépendance sur les magasins sur différentes pages mais avec le même décalage dans une page . Les processeurs hors service agressifs utilisent la désambiguïsation de la mémoire pour déterminer quand les chargements et les magasins peuvent être réorganisés sans changer les résultats , et la mise en œuvre d'Intel a des faux positifs qui empêchent les chargements de démarrer tôt. Probablement, ils ne vérifient que les bits en dessous du décalage de page, de sorte que la vérification peut commencer avant que le TLB ait traduit les bits élevés d'une page virtuelle en une page physique. En plus du guide d'Agner, voir une réponse de Stephen Canon , ainsi qu'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 cette option __attribute__((packed))pour vous permettre d'aligner les variables de manière à ce qu'elles s'étendent sur les limites de la ligne de cache ou même de la page. (Donc, une charge d'un a doublebesoin de données de deux lignes de cache). Les charges mal alignées n'ont pas de pénalité dans tout uarch Intel i7, sauf lors du croisement de lignes de cache et de lignes de page. Les séparations de ligne de cache prennent toujours des cycles supplémentaires . Skylake réduit considérablement la pénalité pour les charges de pages séparées, de 100 à 5 cycles. (Section 2.1.3) . Peut-être lié au fait de pouvoir parcourir deux pages en parallèle.

Un partage de page sur un atomic<uint64_t>devrait être à peu près le pire des cas , en particulier. si c'est 5 octets sur une page et 3 octets sur l'autre page, ou autre chose que 4: 4. Même les divisions au milieu sont plus efficaces pour les divisions de ligne de cache avec des vecteurs 16B sur certains uarches, IIRC. Mettez tout dans un alignas(4096) struct __attribute((packed))(pour économiser de l'espace, bien sûr), y compris un tableau de stockage pour les résultats RNG. Réalisez le désalignement en utilisant uint8_tou uint16_tpour quelque chose avant le comptoir.

Si vous pouvez faire en sorte que le compilateur utilise des modes d'adressage indexés, cela vaincra la micro-fusion uop . Peut-être en utilisant #defines pour remplacer des variables scalaires simples par my_data[constant].

Si vous pouvez introduire un niveau supplémentaire d'indirection, si les adresses de chargement / stockage ne sont pas connues tôt, cela peut pessimiser davantage.

Tableaux transversaux dans un ordre non contigu

Je pense que nous pouvons trouver une justification incompétente pour introduire un tableau en premier lieu: cela 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, pour être additionnés plus tard (avec plus d'incompétence diabolique).

Pour le "maximum aléatoire", nous pourrions avoir un thread en boucle sur le 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 à partir duquel charger un nombre aléatoire. (Il y a un peu de travail ici, mais sur le plan microarchitectural, il est utile de 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.) -speculation pipeline efface (comme discuté précédemment pour le cas de faux partage).

Pour une pessimisation maximale, bouclez sur votre tableau avec une foulée de 4096 octets (soit 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]);

Ainsi, le modèle 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 (bouclage sur des lignes, au lieu de colonnes dans une ligne de la boucle intérieure, comme suggéré par @JesperJuhl). Si l'incompétence diabolique peut justifier un tableau 2D avec des dimensions comme celle-ci, l'incompétence réelle des variétés de jardin justifie facilement une boucle avec le mauvais modèle d'accès. Cela se produit dans le vrai code dans la vraie vie.

Ajustez les limites de la 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 grand. La lecture anticipée du matériel ne fonctionne pas (aussi bien / pas du tout) sur les pages. Le préfetcher peut suivre un flux avant et un flux arrière dans chaque page (c'est ce qui se passe ici), mais n'agira que si la bande passante mémoire n'est pas déjà saturée de non-prélecture.

Cela générera également de nombreux échecs TLB, à moins que les pages ne soient fusionnées en une énorme page ( Linux le fait de manière opportuniste pour les allocations anonymes (non sauvegardées sur fichier) comme malloc/ newthat usemmap(MAP_ANONYMOUS) ).

Au lieu d'un tableau pour stocker la liste des résultats, vous pouvez utiliser une liste liée . Ensuite, chaque itération nécessiterait une charge de poursuite de pointeur (un véritable risque de dépendance RAW pour l'adresse de charge de la charge suivante). Avec un mauvais allocateur, vous pourriez réussir à disperser les noeuds de la liste dans la mémoire, en battant le cache. Avec un allocateur diaboliquement incompétent, il pourrait placer chaque nœud au début de sa propre page. (par exemple, allouer avec mmap(MAP_ANONYMOUS)directement, sans diviser les pages ni suivre la taille des objets pour prendre en charge correctement free).

Ceux-ci ne sont pas vraiment spécifiques à la microarchitecture et ont peu à voir avec le pipeline (la plupart d'entre eux seraient également un ralentissement sur un processeur non pipeliné).

Un peu hors sujet: faire en sorte que le compilateur génère un code plus mauvais / fasse plus de travail:

Utilisez C ++ 11 std::atomic<int>et std::atomic<double>pour le code le plus pessimal. Les lockinstructions MFENCE et ed sont assez lentes même sans contention d'un autre thread.

-m32rendra le code plus lent, car le code x87 sera pire que le code SSE2. La convention d'appel 32 bits basée sur la pile prend plus d'instructions et transmet même les arguments FP sur la pile à des fonctions comme exp(). atomic<uint64_t>::operator++on -m32nécessite une lock cmpxchg8Bboucle (i586). (Alors utilisez ça pour les compteurs de boucles! [Rire diabolique]).

-march=i386va également pessimiser (merci @Jesper). FP se compare à fcomsont plus lents que 686 fcomi. La pré-586 ne fournit pas de magasin atomique 64 bits (et encore moins un cmpxchg), donc toutes les atomicopérations 64 bits se compilent en appels de fonctions libgcc (qui sont probablement compilées pour i686, plutôt que d'utiliser réellement un verrou). Essayez-le sur le lien Godbolt Compiler Explorer dans le dernier paragraphe.

Utilisez long double/ sqrtl/ explpour plus de précision et de lenteur dans les ABI où sizeof ( long double) est 10 ou 16 (avec un rembourrage pour l'alignement). (IIRC, Windows 64 bits utilise l' long doubleéquivalent de 8 octets double. (Quoi qu'il en soit, le chargement / stockage d'opérandes FP 10 octets (80 bits) est de 4/7 uops, contre floatou doublene prend que 1 uop chacun pour fld m64/m32/ fst). Forcer x87 avec des long doubledéfaites auto-vectorisation même gcc -m64 -march=haswell -O3.

Si vous n'utilisez pas de atomic<uint64_t>compteurs de boucles, utilisez-les long doublepour tout, y compris les compteurs de boucles.

atomic<double>compile, mais les opérations de lecture-modification-écriture comme +=ne sont pas prises en charge pour cela (même sur 64 bits). atomic<long double>doit appeler une fonction de bibliothèque uniquement pour les charges / magasins atomiques. C'est probablement très inefficace, car l'ISA x86 ne prend pas naturellement en charge les chargements / magasins atomiques de 10 octets , et la seule façon de penser sans verrouillage ( cmpxchg16b) nécessite un mode 64 bits.

À -O0, briser une grande expression en affectant des pièces à des variables temporaires entraînera plus de stockage / rechargements. Sans volatileou quelque chose, cela n'aura pas d'importance avec les paramètres d'optimisation qu'une vraie construction de vrai code utiliserait.

Les règles chard'alias C permettent à a d'alias n'importe quoi, donc le stockage via a char*oblige le compilateur à tout stocker / recharger avant / après le magasin d'octets, même à -O3. (C'est un problème pour le code deuint8_t vectorisation automatique qui fonctionne sur un tableau de , par exemple.)

Essayez les uint16_tcompteurs de boucles pour forcer la troncature à 16 bits, probablement en utilisant une taille d'opérande de 16 bits (décrochages potentiels) et / ou des movzxinstructions supplémentaires (sûres). Le débordement signé est un comportement indéfini , donc à moins que vous n'utilisiez -fwrapvou au moins -fno-strict-overflow, les compteurs de boucle signés ne doivent pas être re-signés à chaque itération , même s'ils sont utilisés comme décalages vers des pointeurs 64 bits.

Forcer la conversion d'un entier vers floatet en arrière. Et / ou double<=> floatconversions. Les instructions ont une latence supérieure à un et scalaire int-> float ( cvtsi2ss) est mal conçu pour ne pas mettre à zéro le reste du registre xmm. (gcc insère un supplément pxorpour casser les dépendances, pour cette raison.)

Réglez fréquemment l'affinité de votre processeur avec un autre processeur (suggéré par @Egwor). raisonnement diabolique: vous ne voulez pas qu'un noyau soit surchauffé après avoir exécuté votre fil pendant longtemps, n'est-ce pas? Peut-être que le passage à un autre noyau permettra à ce noyau turbo d'atteindre une vitesse d'horloge plus élevée. (En réalité: ils sont tellement proches les uns des autres que cela est très peu probable, sauf dans un système multiprises). Maintenant, faites juste un mauvais réglage et faites-le trop souvent. Outre le temps passé dans l'état du thread de sauvegarde / restauration du système d'exploitation, le nouveau noyau possède des caches L2 / L1 froids, un cache uop et des prédicteurs de branche.

L'introduction d'appels système inutiles fréquents peut vous ralentir, quels qu'ils soient. Bien que certains, importants mais simples, gettimeofdaypuissent être implémentés dans l'espace utilisateur avec, sans transition vers le mode noyau. (glibc sous Linux le fait avec l'aide du noyau, puisque le noyau exporte du code dans le vdso).

Pour en savoir plus sur la surcharge des appels système (y compris les échecs de cache / TLB après le retour dans l'espace utilisateur, pas seulement le changement de contexte lui-même), le document FlexSC contient une excellente analyse des performances de la situation actuelle, ainsi qu'une proposition de système de traitement par lots appels provenant de processus serveur massivement multithreads.

Quelques choses que vous pouvez faire pour rendre les choses aussi mauvaises que possible:

• compiler le code de l'architecture i386. Cela empêchera l'utilisation de SSE et des instructions plus récentes et forcera l'utilisation du FPU x87.

• utilisation std::atomic variables partout. Cela les rendra très chers car le compilateur est obligé d'insérer des barrières mémoire partout. Et c'est quelque chose qu'une personne incompétente pourrait vraisemblablement faire pour "assurer la sécurité des fils".

• assurez-vous d'accéder à la mémoire de la pire façon possible pour le préfetcher (colonne majeure vs ligne majeure).

• pour rendre vos variables plus chères, vous pouvez vous assurer qu'elles ont toutes une «durée de stockage dynamique» (segment alloué) en les allouant avec newplutôt que de leur laisser une «durée de stockage automatique» (pile allouée).

• assurez-vous que toute la mémoire que vous allouez est très étrangement alignée et évitez certainement d'allouer des pages énormes, car cela serait beaucoup trop efficace TLB.

• quoi que vous fassiez, ne construisez pas votre code avec l'optimiseur de compilateurs activé. Et assurez - vous de permettre à la plupart des symboles de débogage expressifs , vous pouvez (ne sera pas rendre le code run plus lent, mais il va perdre un peu d' espace disque supplémentaire).

Remarque: Cette réponse résume simplement mes commentaires que @Peter Cordes a déjà incorporés dans sa très bonne réponse. Suggérez-lui d'obtenir votre vote positif si vous n'en avez qu'un à revendre :)

Vous pouvez utiliser long double pour le calcul. Sur x86, ce devrait être le format 80 bits. Seul l'héritage, le x87 FPU prend en charge cela.

Quelques lacunes du FPU x87:

1. Manque de SIMD, peut nécessiter plus d'instructions.
2. Basé sur la pile, problématique pour les architectures super scalaires et pipelinées.
3. Un jeu de registres séparé et assez petit peut nécessiter plus de conversion à partir d'autres registres et plus d'opérations de mémoire.
4. Sur le Core i7, il y a 3 ports pour SSE et seulement 2 pour x87, le processeur peut exécuter des instructions moins parallèles.

Réponse tardive mais je ne pense pas que nous ayons abusé des listes chaînées et du TLB.

Utilisez mmap pour allouer vos nœuds, de sorte que vous utilisez principalement le MSB de l'adresse. Cela devrait entraîner de longues chaînes de recherche TLB, une page est de 12 bits, laissant 52 bits pour la traduction, soit environ 5 niveaux qu'elle doit parcourir à chaque fois. Avec un peu de chance, ils doivent aller à la mémoire à chaque fois pour une recherche de 5 niveaux plus 1 accès à la mémoire pour accéder à votre nœud, le niveau supérieur sera probablement en cache quelque part, nous pouvons donc espérer un accès à la mémoire 5 *. Placez le nœud de manière à ce que se trouve la pire bordure de sorte que la lecture du pointeur suivant entraîne une autre recherche de traduction 3-4. Cela pourrait également détruire complètement le cache en raison de la quantité massive de recherches de traduction. De plus, la taille des tables virtuelles peut entraîner la pagination de la plupart des données utilisateur sur le disque pendant plus de temps.

Lors de la lecture à partir de la liste chaînée unique, assurez-vous de lire à chaque fois depuis le début de la liste pour retarder au maximum la lecture d'un seul numéro.