C Programme pour déterminer les niveaux et la taille du cache

Réécriture complète / mise à jour pour plus de clarté (et votre santé mentale, c’est un peu trop long) … ( Old Post )

Pour une affectation, je dois trouver les niveaux (L1, L2, …) et la taille de chaque cache. Quelques indices et ce que j’ai trouvé jusqu’à présent: Je pense que l’idée est de créer des tableaux de tailles différentes et de les lire. Calendrier de ces opérations:

sizes = [1k, 4k, 256K, ...] foreach size in sizes create array of `size` start timer for i = 0 to n // just keep accessing array arr[(i * 16) % arr.length]++ // i * 16 supposed to modify every cache line ... see link record/print time 

MISE À JOUR (28 septembre 18:57 UTC + 8)

Voir aussi la source complète

Ok, maintenant, suivant le conseil de @ mah, j’aurais peut-être corrigé le problème du ratio SNR … et j’ai également trouvé une méthode pour chronométrer mon code ( wall_clock_time partir d’un code d’exemple de laboratoire)

Cependant, il semble que je reçois des résultats incorrects: je suis sur un Intel Core i3 2100: [ SPECS ]

  • L1: 2 x 32K
  • L2: 2 x 256K
  • L3: 3MB

Les résultats que j’ai obtenus, dans un graphique:

longueurMod: 1Ko à 512K

entrez la description de l'image ici

La base du 1er sumt est de 32K … raisonnable … la 2ème est de 384K … pourquoi? J’attends 256?

longueurMod: 512k à 4MB

entrez la description de l'image ici

Alors pourquoi cette gamme pourrait-elle être en désordre?


J’ai également lu des informations sur la prélecture ou les interférences provenant d’autres applications. J’ai donc fermé autant de choses que possible pendant l’exécution du script. Il apparaît systématiquement (après plusieurs exécutions) que les données de 1 Mo et plus sont toujours aussi désordonnées?

Le temps qu’il faut pour mesurer votre temps (c’est-à-dire le temps d’appeler simplement la fonction clock ()) est bien plus long (beaucoup plus souvent …) plus long que le temps nécessaire pour effectuer un arr[(i*16)&lengthMod]++ . Ce rapport signal sur bruit extrêmement faible (entre autres pièges probables) rend votre plan impraticable. Une grande partie du problème est que vous essayez de mesurer une seule itération de la boucle; l’exemple de code que vous avez lié tente de mesurer un ensemble complet d’itérations (lisez l’horloge avant de commencer la boucle; relisez-la après être sortie de la boucle; n’utilisez pas printf () dans la boucle).

Si votre boucle est suffisamment grande, vous pourrez peut-être surmonter le problème du rapport signal sur bruit.

Quant à “quel élément est incrémenté”; arr est une adresse d’un tampon de 1 Mo; arr[(i * 16) & lengthMod]++; provoque (i * 16) * lengthMod à générer un décalage à partir de cette adresse; ce décalage est l’adresse de l’int qui est incrémentée. Vous effectuez un décalage (i * 16 se transformera en i << 4), un ajout logique, puis un ajout / écriture / lecture ou un incrément simple, en fonction de votre CPU.

Edit: Comme décrit, votre code souffre d’un SNR (rapport signal sur bruit) faible en raison des vitesses relatives d’access mémoire (cache ou pas de cache) et d’appel de fonctions servant uniquement à mesurer le temps. Pour obtenir le minutage que vous obtenez actuellement, je suppose que vous avez modifié le code pour ressembler à quelque chose comme:

 int main() { int steps = 64 * 1024 * 1024; int arr[1024 * 1024]; int lengthMod = (1024 * 1024) - 1; int i; double timeTaken; clock_t start; start = clock(); for (i = 0; i < steps; i++) { arr[(i * 16) & lengthMod]++; } timeTaken = (double)(clock() - start)/CLOCKS_PER_SEC; printf("Time for %d: %.12f \n", i, timeTaken); } 

Cela déplace la mesure en dehors de la boucle afin que vous ne mesuriez pas un access unique (ce qui serait vraiment impossible), mais que vous mesuriez des access par steps .

Vous êtes libre d'augmenter le nombre de steps au besoin, ce qui aura un impact direct sur votre minutage. Étant donné que les heures que vous recevez sont trop proches les unes des autres, voire inversées (votre heure oscille entre les tailles, ce qui n’est probablement pas causé par le cache), vous pouvez essayer de modifier la valeur des steps en 256 * 1024 * 1024 ou même plus grand.

NOTE: Vous pouvez faire des steps aussi grands que possible dans un int signé (qui devrait être assez grand), puisque c'est logique et vous assure de vous envelopper dans votre tampon.

Après 10 minutes de recherche dans le manuel d’instructions d’Intel et 10 autres minutes de codage, je suis arrivé à ceci (pour les processeurs à base Intel):

 void i386_cpuid_caches () { int i; for (i = 0; i < 32; i++) { // Variables to hold the contents of the 4 i386 legacy registers uint32_t eax, ebx, ecx, edx; eax = 4; // get cache info ecx = i; // cache id __asm__ ( "cpuid" // call i386 cpuid instruction : "+a" (eax) // contains the cpuid command code, 4 for cache query , "=b" (ebx) , "+c" (ecx) // contains the cache id , "=d" (edx) ); // generates output in 4 registers eax, ebx, ecx and edx // taken from http://download.intel.com/products/processor/manual/325462.pdf Vol. 2A 3-149 int cache_type = eax & 0x1F; if (cache_type == 0) // end of valid cache identifiers break; char * cache_type_string; switch (cache_type) { case 1: cache_type_string = "Data Cache"; break; case 2: cache_type_string = "Instruction Cache"; break; case 3: cache_type_string = "Unified Cache"; break; default: cache_type_string = "Unknown Type Cache"; break; } int cache_level = (eax >>= 5) & 0x7; int cache_is_self_initializing = (eax >>= 3) & 0x1; // does not need SW initialization int cache_is_fully_associative = (eax >>= 1) & 0x1; // taken from http://download.intel.com/products/processor/manual/325462.pdf 3-166 Vol. 2A // ebx contains 3 integers of 10, 10 and 12 bits respectively unsigned int cache_sets = ecx + 1; unsigned int cache_coherency_line_size = (ebx & 0xFFF) + 1; unsigned int cache_physical_line_partitions = ((ebx >>= 12) & 0x3FF) + 1; unsigned int cache_ways_of_associativity = ((ebx >>= 10) & 0x3FF) + 1; // Total cache size is the product size_t cache_total_size = cache_ways_of_associativity * cache_physical_line_partitions * cache_coherency_line_size * cache_sets; printf( "Cache ID %d:\n" "- Level: %d\n" "- Type: %s\n" "- Sets: %d\n" "- System Coherency Line Size: %d bytes\n" "- Physical Line partitions: %d\n" "- Ways of associativity: %d\n" "- Total Size: %zu bytes (%zu kb)\n" "- Is fully associative: %s\n" "- Is Self Initializing: %s\n" "\n" , i , cache_level , cache_type_ssortingng , cache_sets , cache_coherency_line_size , cache_physical_line_partitions , cache_ways_of_associativity , cache_total_size, cache_total_size >> 10 , cache_is_fully_associative ? "true" : "false" , cache_is_self_initializing ? "true" : "false" ); } } 

Référence: http://download.intel.com/products/processor/manual/325462.pdf 3-166 Vol. 2A

Ceci est beaucoup plus fiable que la mesure des latences du cache car il est pratiquement impossible de désactiver le préchargement du cache sur un processeur moderne. Si vous souhaitez des informations similaires pour une architecture de processeur différente, vous devrez consulter le manuel correspondant.

Edit: Ajout du descripteur de type de cache. Edit2: indicateur de niveau de cache ajouté. Edit3: Ajout de documentation supplémentaire.

Je sais ça! (En réalité, c’est très compliqué à cause du prélecture)

  for (times = 0; times < Max; time++) /* many times*/ for (i=0; i < ArraySize; i = i + Stride) dummy = A[i]; /* touch an item in the array */ 

Changer de foulée vous permet de tester les propriétés des caches. En regardant un graphique, vous obtiendrez vos réponses.

Regardez les diapositives 35 à 42 http://www.it.uu.se/edu/course/homepage/avdark/ht11/slides/11_Memory_and_optimization-1.pdf

Erik Hagersten est un très bon professeur (et aussi très compétent, il a été l'architecte principal au soleil à un moment donné), alors jetez un coup d'œil au rest de ses diapositives pour de plus amples explications!

Pour répondre à votre question sur les nombres étranges supérieurs à 1 Mo, c’est assez simple. Les politiques d’éviction de cache relatives à la prédiction de twig et au fait que le cache L3 est partagé entre les cœurs.

Un Core i3 a une structure de cache très intéressante. En fait, tout processeur moderne le fait. Vous devriez lire à leur sujet sur wikipedia; il y a toutes sortes de moyens pour que cela décide “bon, je n’aurai probablement pas besoin de ça …” puis il peut dire “je vais le mettre dans le cache de la victime” ou un certain nombre de choses. Les minutages de cache L1-2-3 peuvent être très complexes en fonction d’un grand nombre de facteurs et des décisions de conception sockets.

En plus de cela, toutes ces décisions et plus encore (voir articles de Wikipédia sur le sujet) doivent être synchronisées entre les caches des deux cœurs. Les méthodes pour synchroniser le cache L3 partagé avec des caches L1 et L2 distincts peuvent être laides, elles peuvent impliquer un retour en arrière et la répétition de calculs ou d’autres méthodes. Il est très peu probable que vous disposiez d’un second kernel entièrement libre et que rien ne concurrente pour l’espace de cache N3, ce qui entraînerait un problème de synchronisation.

En général, si vous travaillez sur des données, par exemple, en convolant un kernel, vous voulez vous assurer qu’il est contenu dans le cache L1 et façonner votre algorithme autour de cela. Le cache L3 n’est pas vraiment conçu pour travailler sur un dataset comme vous le faites (bien qu’il soit meilleur que la mémoire principale!)

Je jure que si j’étais celui qui devait implémenter des algorithmes de cache, je deviendrais fou.

Pour effectuer des parsings comparatives avec des progrès variables, vous pouvez essayer lat_mem_rd à partir du paquet lmbench, il est en source ouverte: http://www.bitmover.com/lmbench/lat_mem_rd.8.html

J’avais posté mon portage pour Windows sur http://habrahabr.ru/post/111876/ – c’est assez long d’être copypasté ici. Cela fait deux ans, je ne l’ai pas testé avec des processeurs modernes.

Pour les fenêtres, vous pouvez utiliser la méthode GetLogicalProcessorInformation .

Pour Linux, vous pouvez utiliser sysconf() . Vous pouvez trouver des arguments valides pour sysconf dans /usr/include/unistd.h ou /usr/include/bits/confname.h