faux partage et pthreads

Question

J'ai la tâche suivante pour démontrer le partage faux et écrit un programme simple:

#include <sys/times.h> 
#include <time.h> 
#include <stdio.h> 
#include <pthread.h> 

long long int tmsBegin1,tmsEnd1,tmsBegin2,tmsEnd2,tmsBegin3,tmsEnd3; 

int array[100]; 

void *heavy_loop(void *param) { 
    int index = *((int*)param); 
    int i; 
    for (i = 0; i < 100000000; i++) 
    array[index]+=3; 
} 

int main(int argc, char *argv[]) { 
    int  first_elem = 0; 
    int  bad_elem = 1; 
    int  good_elem = 32; 
    long long time1; 
    long long time2; 
    long long time3; 
    pthread_t  thread_1; 
    pthread_t  thread_2; 

    tmsBegin3 = clock(); 
    heavy_loop((void*)&first_elem); 
    heavy_loop((void*)&bad_elem); 
    tmsEnd3 = clock(); 

    tmsBegin1 = clock(); 
    pthread_create(&thread_1, NULL, heavy_loop, (void*)&first_elem); 
    pthread_create(&thread_2, NULL, heavy_loop, (void*)&bad_elem); 
    pthread_join(thread_1, NULL); 
    pthread_join(thread_2, NULL); 
    tmsEnd1 = clock(); 

    tmsBegin2 = clock(); 
    pthread_create(&thread_1, NULL, heavy_loop, (void*)&first_elem); 
    pthread_create(&thread_2, NULL, heavy_loop, (void*)&good_elem); 
    pthread_join(thread_1, NULL); 
    pthread_join(thread_2, NULL); 
    tmsEnd2 = clock(); 

    printf("%d %d %d\n", array[first_elem],array[bad_elem],array[good_elem]); 
    time1 = (tmsEnd1-tmsBegin1)*1000/CLOCKS_PER_SEC; 
    time2 = (tmsEnd2-tmsBegin2)*1000/CLOCKS_PER_SEC; 
    time3 = (tmsEnd3-tmsBegin3)*1000/CLOCKS_PER_SEC; 
    printf("%lld ms\n", time1); 
    printf("%lld ms\n", time2); 
    printf("%lld ms\n", time3); 

    return 0; 
} 

J'ai été très surpris quand j'ai vu les résultats (je cours sur mon processeur i5-430M).

• Avec un faux partage, il était de 1020 ms.
• Sans faux partage, il était de 710 ms, seulement 30% plus rapide au lieu de 300% (il a été écrit sur certains sites qu'il serait plus rapide que 300-400%).
• Sans utiliser de pthreads, il était de 580 ms.

S'il vous plaît montrez-moi mon erreur ou expliquer pourquoi cela arrive.

Answer 1

Le faux partage est le résultat de plusieurs cœurs avec des caches séparés accédant à la même région de la mémoire physique (bien que pas la même adresse - ce serait le vrai partage).

Pour comprendre le partage erroné, vous devez comprendre les caches. Dans la plupart des processeurs, chaque cœur aura son propre cache L1, qui contient les données récemment accédées. Les caches sont organisés en "lignes", qui sont des blocs alignés de données, généralement de 32 ou 64 octets (selon votre processeur). Lorsque vous lisez à partir d'une adresse qui n'est pas dans le cache, toute la ligne est lue depuis la mémoire principale (ou un cache L2) dans L1. Lorsque vous écrivez à une adresse dans le cache, la ligne contenant cette adresse est marquée "sale".

Voici où l'aspect de partage entre en jeu. Si plusieurs coeurs lisent à partir de la même ligne, ils peuvent chacun avoir une copie de la ligne dans L1. Cependant, si une copie est marquée comme sale, elle invalide la ligne dans les autres caches. Si cela ne s'est pas produit, alors les écritures faites sur un noyau pourraient ne pas être visibles pour les autres noyaux jusqu'à beaucoup plus tard. Donc, la prochaine fois que l'autre noyau va lire à partir de cette ligne, le cache manque, et il doit aller chercher la ligne à nouveau.

Faux Le partage se produit lorsque les cœurs sont en train de lire et d'écrire sur différentes adresses sur la même ligne. Même s'ils ne partagent pas de données, les caches agissent comme ils le sont puisqu'ils sont si proches.

Cet effet dépend fortement de l'architecture de votre processeur. Si vous aviez un seul processeur principal, vous ne verriez aucun effet car il n'y aurait pas de partage. Si vos lignes de cache étaient plus longues, vous verriez l'effet à la fois dans les cas "mauvais" et "bons", car ils sont toujours proches les uns des autres. Si vos cœurs ne partagent pas un cache L2 (ce que je suppose qu'ils font), vous pourriez voir une différence de 300-400% comme vous l'avez dit, car ils devraient aller jusqu'à la mémoire principale sur un cache manqué.

Vous aimerez peut-être également savoir qu'il est important que chaque thread lit et écrive à la fois (+ = au lieu de =). Certains processeurs ont écriture cachée caches, ce qui signifie que si un core écrit à une adresse qui n'est pas dans le cache, il ne manque pas et récupère la ligne de la mémoire. Comparez cela avec ré-écriture caches, qui manquent sur les écritures.

Answer 2

J'ai parcouru la fonction clock() en C.Il vous donne le nombre d'horloge CPU écoulées du début à la fin.Maintenant, lorsque vous exécutez deux threads parallèles, le nombre de cycles CPU sera (cycles d'horloge de CPU1 + horloge cycles de cpu2). Je pense que ce que vous voulez est une horloge de minuterie réelle. Pour cela, vous utilisez clock_gettime() et vous obtiendrez la sortie attendue.

J'ai exécuté votre code avec clock_gettime().Je suis arrivé ceci:

avec de faux partage 874.587381 ms

sans faux partage 331.844278 ms

de calcul séquentiel 604.160276 ms