Accélérer l'accès mémoire aléatoire en utilisant prefetch

Question

J'essaye d'accélérer un seul programme en utilisant prefetches. Le but de mon programme est juste pour le test. Voici ce qu'il fait:

1. Il utilise deux tampons int de la même taille
2. Il lit un par un toutes les valeurs du premier tampon
3. Il lit la valeur à l'index dans le second tampon
4. Il résume toutes les valeurs prises à partir du second tampon
5. Il fait toutes les étapes précédentes pour de plus en plus
6. A la fin, j'imprimer le nombre de CP volontaire et involontaire U

Dans le premier temps, les valeurs dans les premières mémoires tampons contenant les valeurs de l'indice (cf. fonction createIndexBuffer dans le code ci-dessous).

Il sera plus clair dans le code de mon programme:

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 
#include <sys/time.h> 

#define BUFFER_SIZE ((unsigned long) 4096 * 100000) 


unsigned int randomUint() 
{ 
    int value = rand() % UINT_MAX; 
    return value; 
} 


unsigned int * createValueBuffer() 
{ 
    unsigned int * valueBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    valueBuffer[i] = randomUint(); 
    } 

    return (valueBuffer); 
} 


unsigned int * createIndexBuffer() 
{ 
    unsigned int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    indexBuffer[i] = i; 
    } 

    return (indexBuffer); 
} 


unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer) 
{ 
    unsigned long long sum = 0; 

    for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    unsigned int index = indexBuffer[i]; 
    sum += valueBuffer[index]; 
    } 

    return (sum); 
} 


unsigned int computeTimeInMicroSeconds() 
{ 
    unsigned int * valueBuffer = createValueBuffer(); 
    unsigned int * indexBuffer = createIndexBuffer(); 

    struct timeval startTime, endTime; 
    gettimeofday(&startTime, NULL); 

    unsigned long long sum = computeSum(indexBuffer, valueBuffer); 

    gettimeofday(&endTime, NULL); 

    printf("Sum = %llu\n", sum); 
    free(indexBuffer); 
    free(valueBuffer); 

    return ((endTime.tv_sec - startTime.tv_sec) * 1000 * 1000) + (endTime.tv_usec - startTime.tv_usec); 

} 


int main() 
{ 
    printf("sizeof buffers = %ldMb\n", BUFFER_SIZE * sizeof(unsigned int)/(1024 * 1024)); 
    unsigned int timeInMicroSeconds = computeTimeInMicroSeconds(); 
    printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds/(1000 * 1000)); 
} 

Si je lance, je reçois la sortie suivante:

$ gcc TestPrefetch.c -O3 -o TestPrefetch && ./TestPrefetch 
sizeof buffers = 1562Mb 
Sum = 439813150288855829 
Time: 201172 micro-seconds = 0.201 seconds 

rapide et rapide !!! Selon mes connaissances (je peux me tromper), l'une des raisons d'avoir un programme aussi rapide est que, lorsque j'accède séquentiellement à mes deux tampons, les données peuvent être préextraites dans le cache du CPU.

Nous pouvons le rendre plus complexe afin que les données soient (presque) préfixées dans le cache CPU. Par exemple, nous pouvons simplement changer la fonction createIndexBuffer dans:

unsigned int * createIndexBuffer() 
{ 
    unsigned int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    indexBuffer[i] = rand() % BUFFER_SIZE; 
    } 

    return (indexBuffer); 
} 

Essayons le programme une fois encore:

$ gcc TestPrefetch.c -O3 -o TestPrefetch && ./TestPrefetch 
sizeof buffers = 1562Mb 
Sum = 439835307963131237 
Time: 3730387 micro-seconds = 3.730 seconds 

Plus de 18 fois plus lent !!!

Nous arrivons maintenant à mon problème. Compte tenu de la nouvelle fonction createIndexBuffer, je voudrais accélérer la fonction computeSum utilisant prélecture

unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer) 
{ 
    unsigned long long sum = 0; 

    for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    __builtin_prefetch((char *) &indexBuffer[i + 1], 0, 0); 
    unsigned int index = indexBuffer[i]; 
    sum += valueBuffer[index]; 
    } 

    return (sum); 
} 

bien sûr, je dois aussi changer ma createIndexBuffer pour qu'il alloue un tampon ayant un élément supplémentaire

Je RELANCE mon programme: pas mieux! Comme prélecture peut être plus lent d'un « pour » itération de la boucle, je ne précharger un élément avant, mais deux éléments avant

__builtin_prefetch((char *) &indexBuffer[i + 2], 0, 0); 

pas mieux! deux boucles d'itérations? pas mieux? Trois? ** Je l'ai essayé jusqu'à 50 (!!!) mais je ne peux pas améliorer les performances de ma fonction computeSum.

Puis-je voudrais aider à comprendre pourquoi Je vous remercie beaucoup pour votre aide

Answer 1

Je crois que le code ci-dessus est automatiquement optimisée par CPU sans espace supplémentaire pour l'optimisation manuelle.

1. Le principal problème est que indexBuffer est accédé séquentiellement. Le pré-sélectionneur de matériel le détecte et pré-sélectionne automatiquement d'autres valeurs, sans avoir besoin d'appeler la pré-extraction manuellement. Ainsi, lors de l'itération #i, les valeurs indexBuffer[i+1], indexBuffer[i+2], ... sont déjà dans le cache. (En passant, il n'est pas nécessaire d'ajouter un élément artificiel à la fin du tableau: les erreurs d'accès à la mémoire sont silencieusement ignorées par les instructions de prélecture).

Ce que vous avez vraiment besoin de faire est de précharger valueBuffer à la place:

__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + 1]], 0, 0); 

2. Mais l'ajout ci-dessus ligne de code ne sera pas aider non plus dans ce scénario simple. Le coût d'accès à la mémoire est de plusieurs centaines de cycles, tandis que l'instruction d'ajout est d'environ 1 cycle. Votre code passe déjà 99% du temps dans les accès mémoire. Ajout de prefetch manuel rendra ce cycle un plus rapide et pas mieux.

La prélecture manuelle fonctionnerait vraiment bien si vos maths étaient beaucoup plus lourdes (essayez-les), comme utiliser une expression avec un grand nombre de divisions non optimisées (20-30 cycles chacune) ou appeler une fonction mathématique (log, péché).

3. Mais même cela ne garantit pas pour vous aider. La dépendance entre les itérations de boucle est très faible, ce n'est que via la variable sum. Cela permet au processeur d'exécuter des instructions de manière spéculative: il peut commencer à aller chercher valueBuffer[i+1] simultanément tout en exécutant des opérations mathématiques pour valueBuffer[i].

Answer 2

Désolé. Ce que je vous ai donné n'était pas la bonne version de mon code. La version correcte est, ce que vous avez dit:

__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0); 

Cependant, même avec la bonne version, il est malheureusement pas mieux

Answer 3

J'adapté mon programme pour tenter votre suggestion en utilisant la fonction sin.

Mon programme adapté est la suivante:

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 
#include <sys/time.h> 
#include <math.h> 

#define BUFFER_SIZE ((unsigned long) 4096 * 50000) 


unsigned int randomUint() 
{ 
    int value = rand() % UINT_MAX; 
    return value; 
} 


unsigned int * createValueBuffer() 
{ 
    unsigned int * valueBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    valueBuffer[i] = randomUint(); 
    } 

    return (valueBuffer); 
} 


unsigned int * createIndexBuffer(unsigned short prefetchStep) 
{ 
    unsigned int * indexBuffer = (unsigned int *) malloc((BUFFER_SIZE + prefetchStep) * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    indexBuffer[i] = rand() % BUFFER_SIZE; 
    } 

    return (indexBuffer); 
} 


double computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer, unsigned short prefetchStep) 
{ 
    double sum = 0; 

    for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    __builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0); 
    unsigned int index = indexBuffer[i]; 
    sum += sin(valueBuffer[index]); 
    } 

    return (sum); 
} 


unsigned int computeTimeInMicroSeconds(unsigned short prefetchStep) 
{ 
    unsigned int * valueBuffer = createValueBuffer(); 
    unsigned int * indexBuffer = createIndexBuffer(prefetchStep); 

    struct timeval startTime, endTime; 
    gettimeofday(&startTime, NULL); 

    double sum = computeSum(indexBuffer, valueBuffer, prefetchStep); 

    gettimeofday(&endTime, NULL); 

    printf("prefetchStep = %d, Sum = %f - ", prefetchStep, sum); 
    free(indexBuffer); 
    free(valueBuffer); 

    return ((endTime.tv_sec - startTime.tv_sec) * 1000 * 1000) + (endTime.tv_usec - startTime.tv_usec); 

} 


int main() 
{ 
    printf("sizeof buffers = %ldMb\n", BUFFER_SIZE * sizeof(unsigned int)/(1024 * 1024)); 
    for (unsigned short prefetchStep = 0 ; prefetchStep < 250 ; prefetchStep++) 
    { 
    unsigned int timeInMicroSeconds = computeTimeInMicroSeconds(prefetchStep); 
    printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds/(1000 * 1000)); 
    } 
} 

La sortie est:

$ gcc TestPrefetch.c -O3 -o TestPrefetch -lm && taskset -c 7 ./TestPrefetch 
sizeof buffers = 781Mb 
prefetchStep = 0, Sum = -1107.523504 - Time: 20895326 micro-seconds = 20.895 seconds 
prefetchStep = 1, Sum = 13456.262424 - Time: 12706720 micro-seconds = 12.707 seconds 
prefetchStep = 2, Sum = -20179.289469 - Time: 12136174 micro-seconds = 12.136 seconds 
prefetchStep = 3, Sum = 12068.302534 - Time: 11233803 micro-seconds = 11.234 seconds 
prefetchStep = 4, Sum = 21071.238160 - Time: 10855348 micro-seconds = 10.855 seconds 
prefetchStep = 5, Sum = -22648.280105 - Time: 10517861 micro-seconds = 10.518 seconds 
prefetchStep = 6, Sum = 22665.381676 - Time: 9205809 micro-seconds = 9.206 seconds 
prefetchStep = 7, Sum = 2461.741268 - Time: 11391088 micro-seconds = 11.391 seconds 
... 

donc ici, il fonctionne mieux! Honnêtement, j'étais presque sûr que ça ne vaudrait pas mieux parce que le coût de la fonction mathématique est plus élevé comparé à l'accès mémoire.

Si quelqu'un pouvait me donner plus d'informations sur la raison pour laquelle il vaut mieux maintenant, je vous serais reconnaissant

Merci beaucoup

Answer 4

prélecture va chercher normalement une ligne complète de cache. C'est typically 64 bytes. Ainsi, l'exemple aléatoire récupère toujours 64 octets pour un int de 4 octets. 16 fois les données dont vous avez réellement besoin, ce qui correspond très bien avec le ralentissement d'un facteur de 18. Donc, le code est simplement limité par le débit de la mémoire et non la latence.