Forum Programmation.c Parallelisation d'une boucle (théoriquement) trivialement parallélisable

Posté par .
Tags : aucun
7
5
nov.
2010

Bonjour,

Je dois effectuer un nombre très important de fois la boucle suivante avec un contrainte très forte sur le temps d'exécution:


for(i = 0 ; i < N ; i++){
yvar1[i] = yvar1[i] + yvar2[i] + yvar3[i];
yvar2[i] = yvar2[i] + 2.0 * yvar3[i];
}

où N est proche de 130000 et yvar* est un tableau de double.


Ce calcul est théoriquement trivialement parallélisable mais malheureusemnt je n'obtiens pas un bon speedup avec plus de deux threads. C'est probablement dû au fait que N n'est pas si grand et qu'on effectue beaucoup de lecture/écriture par rapport au nombre de calcul.




Avec le test suivant ( http://codeviewer.org/view/code:1397 )
compilé avec "cc -O3 -lpthread testPred.c -o testPred"
sur un "biprocesseur-quadricore-hyperthreadé (i.e. 16 coeurs logiques) Intel(R) Xeon(R) CPU E5530 @ 2.40GHz" j'obtiens les temps suivant:



[DEK328@PEGASE08 testParall]$ ./compile.sh && ./testPred
inplace sequential prediction : 0.440000 ms
inplace sequential prediction += : 0.356000 ms
outplace sequential prediction : 1.003000 ms
inplace parallel prediction += using 1 threads: 0.798000 ms
inplace parallel prediction += using 2 threads: 0.304000 ms
inplace parallel prediction += using 4 threads: 0.430000 ms
inplace parallel prediction += using 8 threads: 0.425000 ms
inplace parallel prediction += using 16 threads: 0.662000 ms
outplace parallel prediction using 1 threads: 0.475000 ms
outplace parallel prediction using 2 threads: 0.284000 ms
outplace parallel prediction using 4 threads: 0.414000 ms
outplace parallel prediction using 8 threads: 0.488000 ms
outplace parallel prediction using 16 threads: 0.577000 ms



On constate que dès qu'il y a plus de 2 threads, le speedup est très mauvais (même avec la version "outplace" où l'on ne devrait pas avoir de falsesharing). La meilleur combinaison mène à un temps de 0.28ms qui est malheureusement toujours trop élevé pour mes besoins.


On a constaté le même genre de mesure en utilisant d'autre langage (intel Fortran et OpenMP).


Plusieurs questions:


  • qu'est-ce qui explique ce si mauvais speedup ?.
  • y-a-t'il une autre technique qui améliorerait les performances ? Presque toutes les options sont ouvertes (hardware, algorithmiques, langages...)
  • pourquoi est-ce que la version avec "yvar1[i] = yvar1[i] + ... " est moins performante que celle avec "yvar1[i] += ..." ? Le compilateur n'est-il pas assez intelligent pour remarquer que c'est la même chose ?
  • par ailleurs connaîtriez-vous d'autres sites/forum où l'on s'intéresse à ce genre de question ?



    Merci d'avance pour vos suggestions.

  • # Quelques commentaires

    Posté par (page perso) . Évalué à 9.

    Je suis très loin d'être un expert en optimisation, mais voici quand même quelques pistes:

    - Ton code a peut-être un problème de "pointer aliasing". A priori le compilateur n'a pas moyen d'être sûr que yvar1, yvar2 et yvar3 ne pointent pas à des endroits voisins en mémoire, et ne peut donc pas faire d'optimisations comme l'utilisation des instructions SIMD.

    -Cela m'amène au deuxième point : as-tu regardé l'assembleur généré par le compilateur? Il n'y a pas besoin d'être un expert pour le faire, et ça peut être riche en enseignements: place le code critique entre deux commentaires assembleur ( __asm__("#before") par exemple, de mémoire), compile avec le bon flag gcc et c'est parti!

    -En ce qui concerne la parallélisation par threads, vu le faible temps d'exécution de la boucle, je me demande si le coût de création des threads n'explique pas tout simplement la baisse des performances.

    Bon courage! (et n'hésite pas à faire un journal quand tu auras réussi, c'est toujours intéressant ce genre de problèmes)
    • [^] # Re: Quelques commentaires

      Posté par . Évalué à 3.

      Tout à fait d'accord avec les histoires d'aliasing : au lieu de faire de la manipulation de pointeur dans tous les sens, utilise des tableaux que tu indexes "correctement". En plus ce sera plus lisible.

      Et commme indiqué en dessous, alloue tes tableaux statiquement. Tu auras donc quelque chose comme :

      double yvar1[N];
      double yvar2[N];
      ...


      Et pour la différence entre le += et le + seulement, c'est sûrement une histoire qui ressemble à l'aliasing, mais dans le cas du multithread : le compilo va dans le cas du + générer une variable intermédiaire entre l'accès à yvar1 et l'affectation, car il ne peut pas savoir si le tableau a changé entre deux. Dans le cas du +=, il doit générer une instruction qui fait l'addition "en place" dans le registre.
  • # += pdf multiplication

    Posté par . Évalué à 4.

    « Le compilateur n'est-il pas assez intelligent pour remarquer que c'est la même chose ? »

    Ça n’est pas tout à fait la même chose :a += b + c ⇔ a = a + (b + c)

    a = a + b + c ⇔ a = (a + b) + c
    Il est possible que certains compilateurs fassent la distinction pour des raisons de précision numérique.

    Par contre je ne sais pas pourquoi ça impacterait les performances… si tu mets explicitement des parenthèses (dans les deux cas) ça change quelque chose ?

    Pour les questions d’optimisations j’avais trouvé la lecture de [http://www.agner.org/optimize/optimizing_cpp.pdf] très instructive.

    Mais j’ai constaté le même phénomène que toi, pour les « petites » (petite sur le nombre de ligne d’une itération, pas le nombre d’itération) boucles la parallélisation n’apporte aucun gain : sur-charge pour la gestion des threads (création ou réveil), mais surtout les boucles déjà optimisées qui partent en SIMD (surtout dans ton cas).

    Petite question au passage : est-ce que mettre yvar2[i] = yvar2[i] + (yvar3[i] + yvar3[i]);pour la deuxième ligne change quelque chose (avec et sans les parenthèses) ?
  • # seul ?

    Posté par (page perso) . Évalué à 1.

    Es tu seul sur cette machine ou y a t il d'autres utilisateurs qui te piquent méchamment du CPU ?
    • [^] # Re: seul ?

      Posté par . Évalué à 2.

      Lorsque les tests ont été effectués j'étais seul sur la machine.
  • # à coté

    Posté par . Évalué à 2.

    double * yvar1temp = (double *) malloc(N * sizeof(double));
    Comme N est une constante, tu gagneras en vitesse en déclarant des tableaux.
    (tu économise un lookup de pointeur)

    gettimeofday(&t, NULL);
    N'est pas thread safe
    • [^] # Re: à coté

      Posté par . Évalué à 2.

      gettimeofday(&t, NULL);
      N'est pas thread safe

      Ignore cette remarque. Faut que je me reveille. &t
  • # creation des threads + cache

    Posté par (page perso) . Évalué à 4.

    A vue de nez, je pense qu'il y a deux problèmes ici:

    La création d'un thread est coûteuse. La création de 16 threads est encore plus coûteuse. Donc pour des traitements aussi courts (dans ton cas de l'ordre de 400 us), la création des threads prend beaucoup trop de temps. Si tu utilises OpenMP, tu peux évaluer le coût de la création des threads en faisant plusieurs mesures à la suite:


    for (mesure=0; mesure<10; mesure++) {
    start = get_time();
    #pragma omp parallel for
    for(i=0; i<N;i++) {
    ...
    }
    stop = get_time();
    }


    A la première mesure, le runtime OpenMP va créer un certain nombre de threads et paralléliser la boucle. A la fin de cette boucle, les threads ne seront pas détruits, et normalement la deuxième boucle devrait aller plus vite (les threads sont réutilisés).

    Donc si dans ton application tu risques de faire plusieurs fois ce calcul, essaie de prendre en compte la création/destruction des threads.


    Le deuxième problème que je vois est lié aux caches. Quand tu alloues et initialises les tableaux yvar*, ils se retrouvent dans le cache d'un des cœurs. Quand tu lances un thread pour qu'il fasse une partie du calcul, il faut que les données qu'il traite soient envoyées dans le cache qui va bien.
    Si ce thread est 'proche' du cache où sont les données, ca se passe bien, mais si il faut faire transiter les données d'un processeur à l'autre, ca prend beaucoup de temps.
    En fixant tes threads de calcul à la main, tu devrais pouvoir maitriser un peu mieux ces transferts de données. Pour ca, tu peux utiliser hwloc ( http://www.open-mpi.org/projects/hwloc/ )
    • [^] # Re: creation des threads + cache

      Posté par . Évalué à 1.

      Effectivement en OpenMP le coût de création des threads est significatif.

      La première exécution de cette boucle coûte chère et les suivantes moins chères. Malheureusement même lors de l'appel des boucles suivantes on n'obtient pas un bon speedup pour plus de deux threads (les résultats des boucles suivantes en OpenMP sont assez proche de ceux obtenus avec les pthreads). J'essaierai de poster les temps obtenus en OpenMP dès que j'aurai de nouveau accès à la machine sur laquelle j'ai fait mes tests.

      En utilisant des pthreads je ne vois pas de différence entre un premier appel et les appels successifs. Néanmoins c'est la première fois que j'utilise ces pthreads. Est-il possible de garder ces threads "actifs" afin d'accélérer le prochain appel ?

      Je vais jeter un coup d'oeuil à hwloc. Je vous tiendrai au courant des résultats.
      • [^] # Re: creation des threads + cache

        Posté par (page perso) . Évalué à 2.

        Est-il possible de garder ces threads "actifs" afin d'accélérer le prochain appel ?

        Oui, il suffit de ne pas les tuer :) Par exemple, au lieu de faire:

        pthread_create( &(threads[i]), NULL, predictInPlace, (void*) (&dataThreads[i]));


        tu peux exécuter une fonction qui attend du travail :


        pthread_create( &(threads[i]), NULL, traiter_un_job, (void*) (&dataThreads[i]));

        void traiter_un_job(void* ptr) {
        while(1) {
        sem_wait(&truc_a_traiter);
        predicInPlace(ptr);
        sem_post(&traitement_terminee);
        }
        }


        Une fois tes threads lancés, tu peux lancer un traitement en parallèle en appelant sem_post(&truc_a_traiter); pour chaque thread que tu veux débloquer (attention, c'est fait à l'arrache, il y a des races conditions).

        Après, cette solution ressemble à ce que fait l'implémentation OpenMP, donc je pense qu'il vaut mieux laisser OpenMP gérer ce genre de cas. L'utilisation de pthreads n'apportera pas grand chose à moins de fixer les threads sur les cores qui vont bien, ce qu'OpenMP ne sait pas forcement faire.
        • [^] # Re: creation des threads + cache

          Posté par . Évalué à 1.

          +1 pour la réponse.

          Bonjour

          J'ai fait le test de l'auteur avec OPENMP, je l'ai porté en FORTRAN et utilisé un compilateur INTEL 11.1 qui est réputé comme un compilateur performant (openmp 3.0)

          Dans ce cas, je voudrais signaler que j'observe le même comportement que lui avec pthreads

          - J'ai fait attention d'exécuter le job plusieurs fois et de ne pas compter le premier appel. (les threads sont créées)

          - Pour répondre à la localisation des données, j'ai utilisé une fonction du compilateur (variable d'envirronnement KMP_AFFINITY) qui permet de choisir de balancer les threads entre processeurs ou de remplir d'abord un processeur avant d'en remplir un suivant. J'ai bien sur désactivé l'hyperthreading pour ne pas véroler les performances.

          J'ai donc une question pour vous. Pensez-vous que la vitesse du cache peut être en cause?

          ...et même une deuxième question: Avez-vous pu reproduire son problème sur vos machines?

          Amicalement.

          • [^] # Re: creation des threads + cache

            Posté par . Évalué à 1.

            Sur un quadcore
            Intel(R) Xeon(R) CPU X3350 @ 2.66GHz

            Les résultats sont assez aléatoires, même si rien d'autre de gourmand ne tourne.


            inplace sequential prediction : 0.402000 ms
            inplace sequential prediction += : 0.354000 ms
            outplace sequential prediction : 1.446000 ms
            inplace parallel prediction += using 1 threads: 2.075000 ms
            inplace parallel prediction += using 2 threads: 0.966000 ms
            inplace parallel prediction += using 4 threads: 0.837000 ms
            inplace parallel prediction += using 8 threads: 1.835000 ms
            inplace parallel prediction += using 16 threads: 0.755000 ms
            outplace parallel prediction using 1 threads: 2.175000 ms
            outplace parallel prediction using 2 threads: 1.123000 ms
            outplace parallel prediction using 4 threads: 0.774000 ms
            outplace parallel prediction using 8 threads: 0.853000 ms
            outplace parallel prediction using 16 threads: 0.771000 ms


            ou alors



            inplace sequential prediction : 0.310000 ms
            inplace sequential prediction += : 0.276000 ms
            outplace sequential prediction : 1.365000 ms
            inplace parallel prediction += using 1 threads: 2.280000 ms
            inplace parallel prediction += using 2 threads: 1.083000 ms
            inplace parallel prediction += using 4 threads: 0.632000 ms
            inplace parallel prediction += using 8 threads: 0.507000 ms
            inplace parallel prediction += using 16 threads: 0.610000 ms
            outplace parallel prediction using 1 threads: 1.108000 ms
            outplace parallel prediction using 2 threads: 1.177000 ms
            outplace parallel prediction using 4 threads: 1.319000 ms
            outplace parallel prediction using 8 threads: 0.628000 ms
            outplace parallel prediction using 16 threads: 0.724000 ms


            Je pense que les temps sont beaucoup trop court et la moindre préemption/interruption fausse le résultat.

            Du coup je me demande si c'est pas simplement un patch RT la solution
          • [^] # Re: creation des threads + cache

            Posté par (page perso) . Évalué à 3.

            Avez-vous pu reproduire son problème sur vos machines?
            Je n'ai pas teste sur une machine de calcul, uniquement sur mon portable (Core i5 M540 2.53GHz). J'ai le même genre de comportement.

            Pensez-vous que la vitesse du cache peut être en cause?
            Je pense que c'est quelque chose comme ca oui. Il est sans doute possible de paralléliser le code à peu près efficacement, mais ca risque de demander des bidouillages pas beaux pour un speedup à peine correct.

            Du coup, si on revient à la question initiale, berti nous dit:
            La meilleur combinaison mène à un temps de 0.28ms qui est malheureusement toujours trop élevé pour mes besoins.

            Pourrais-tu nous expliquer tes besoins ? Pourquoi 280us c'est trop ? Est-ce parce que ce calcul est effectué plein de fois à la suite ? Est-ce dû à des contraintes temps-réel ?
    • [^] # Re: creation des threads + cache

      Posté par . Évalué à 3.

      D'ailleurs au sujet des caches et des instructions SSE, étant donné que les données yvar1[i] et yvar2[i] ne sont pas réutilisées immédiatement, il serait bon de les envoyer directement à la mémoire pour laisser plus de place dans le cache pour les données utiles, avec la fonction _mm_stream_pd dans emmintrin.h (fonctions de bypass du cache).
  • # Google

    Posté par . Évalué à 3.

    Alors je vais probablement dire une connerie mais ce serait intéressant de voir si les fameux threads léger de go-lang sont pas plus efficace quand dans un cas comme le tiens où le problème semble venir de threads trop lourds.

    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # Spécificité processeur

    Posté par (page perso) . Évalué à 3.

    Peut-être qu'en allant beaucoup plus bas niveau, et donc en faisant de l'assembleur, il est possible gagner en vitesse.

    Par exemple, les processeurs G4 et G5 (power pc) possèdent un jeu d'instruction appelé altivec qui permet par exemple de faire des opérations sur 16 éléments à la fois.

    Il existe un peu près la même chose avec les instructions sse* il me semble.

    Envoyé depuis mon lapin.

  • # Assembleur

    Posté par (page perso) . Évalué à 1.

    Une solution est par exemple de descendre plus bas niveau et de coder cette partie en assembleur (et de garder ta boucle si l'architecture change).

    Par exemple, sur un processeur G4 ou G5 (power pc), le jeu d'instruction altivec permet de réaliser des opérations sur 16 éléments à la fois. Si c'est bien utilisé, ça peut faire des très grosses optimisations.

    Envoyé depuis mon lapin.

    • [^] # Re: Assembleur

      Posté par (page perso) . Évalué à 2.

      templeet m'a joué un tour. C'est que quand j'ai forcé l'actualisation de la page que j'ai vu apparaître mon message :'(

      Envoyé depuis mon lapin.

    • [^] # Re: Assembleur

      Posté par (page perso) . Évalué à 4.

      C'est ce à quoi on fait référence plus haut en parlant de SIMD.
      http://en.wikipedia.org/wiki/SIMD

      pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

      • [^] # Re: Assembleur

        Posté par . Évalué à 1.

        Une petite bizarrerie de gcc (4.5.1) dans le code généré (O3):


        yvar1[i] += yvar2[i] + yvar3[i];
        4007f0: f2 0f 10 09 movsd (%rcx),%xmm1
        ...
        4007f7: f2 0f 10 10 movsd (%rax),%xmm2
        4007fb: 66 0f 16 49 08 movhpd 0x8(%rcx),%xmm1
        400800: f2 0f 10 22 movsd (%rdx),%xmm4
        400804: 66 0f 16 50 08 movhpd 0x8(%rax),%xmm2
        400809: 66 0f 16 62 08 movhpd 0x8(%rdx),%xmm4
        40080e: 66 0f 28 c1 movapd %xmm1,%xmm0
        400812: 66 0f 28 ca movapd %xmm2,%xmm1
        400816: 66 0f 58 cc addpd %xmm4,%xmm1
        40081a: 66 0f 58 c1 addpd %xmm1,%xmm0
        40081e: 66 0f 13 01 movlpd %xmm0,(%rcx)
        400822: 66 0f 17 41 08 movhpd %xmm0,0x8(%rcx)


        Il utilise bien les instructions SSE.
        Par contre, si je comprend bien, il charge un couple de y1, y2,y3 dans les registres xmm1, xmm2 et xmm4.
        Puis met xmm1 dans xmm0
        Puis met xmm2 dans xmm1
        Puis additionne xmm4 + xmm1 + xmm2.

        Dites monsieur gcc, ca sert à quoi ce déplacement des registres 2 et 1 dans 1 et 0 ??

        C'est probablement pour cela que tu vois une différence (injustifiable à mon avis) entre le "+=" et les "+" .
        Il ne fait pas cette entourloupe pour pour la série de "+" .
        • [^] # Re: Assembleur

          Posté par . Évalué à 1.

          Pour information le code généré pour la version avec des "+" .
          Je ne suis pas un grand spécialiste, mais il doit être difficile de faire beaucoup mieux ?
          Le "problème" est bien a chercher dans l'overhead introduit par les threads.


          yvar1Temp[i] = yvar1[i] + yvar2[i] + yvar3[i];

          movsd (%r8),%xmm3
          movhpd 0x8(%rcx,%rbx,1),%xmm1
          movhpd 0x8(%r8),%xmm3
          movapd %xmm1,%xmm0
          addpd %xmm3,%xmm0
          movsd 0x0(%rbp),%xmm3
          movhpd 0x8(%rbp),%xmm3
          addpd %xmm3,%xmm0
          movlpd %xmm0,(%rdx,%rbx,1)
          movhpd %xmm0,0x8(%rdx,%rbx,1)
          • [^] # Re: Assembleur

            Posté par . Évalué à 1.

            Pour les quelques uns qui ont suivi : dans la version "+=" , il additionne finalement
            xmm4, xmm1 et xmm0 et non pas xmm4, xmm2 et xmm1 (ce qui de doute façon donnerait le même résultat !)
            • [^] # Re: Assembleur

              Posté par . Évalué à 1.

              ce qui de doute façon donnerait le même résultat
              -> Non, je sors.
  • # -funroll-loops

    Posté par (page perso) . Évalué à 3.

    Plutôt que d'avoir un thread par instruction, tu peux peut-être déjà regrouper plusieurs instructions par thread, non ?
    En supposant qu'une itération de boucle soit executée dans un fil, alors un -funroll-loops devrait permettre d'avoir plus de code par thread, plus d'invariants pour les optimisations, un meilleur cache, et plus de succès auprès des femmes.
    • [^] # Re: -funroll-loops

      Posté par . Évalué à 3.

      je plussote cette façon de faire.
      D'autant qu'elle est très simple, et implique aussi qu'il n'y aura que peu de changement de contexte :

      en pseudo code ca devrais un truc comme ça

      int nb_thread=n;//on va créer n thread)
      int size_tab=x;//la taille du tableau
      int size_seg=x/n;//ne pas oublier les vérifs n>x, et si x n'est pas divisible par n. Bref gérer les effets de bords.
      /* on lance les traitements*/
      while (nb_thread>0)
      {
      create_thread(mon_thread_a_moi,nb_thread,(size_seg*nb_thread),size_seg*(nb_thread+1));//on créé un "thread a moi", en lui disant d'utiliser les indiques de départ (size_seg*nb_thread), et de fin size_seg*(nb_thread+1)
      nb_thread--;
      }
      nb_thread=n;
      /* on attend qu'ils soient terminées*/
      while (nb_thread>0)
      {
      join(pid_thread(nb_thread));
      }

      void mon_thread_a_moi (int nb,int deb,int end)
      {
      while (end>=deb)
      {
      yvar1[end] = yvar1[end] + yvar2[end] + yvar3[end];
      yvar2[end] = yvar2[end] + 2.0 * yvar3[end];
      end--;
      }
      }

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.