Calcul du speed-up

Version imprimable

20/11/2009, 19h30
uriotcea

Calcul du speed-up

Bonjour,

J'ai parallélisé un code de calcul à l'aide d'openMP. Sur ma machine mono pro j'obtient un gain de 75% grace à l'hyperthreading. C'est correct compte tenu du fait que seul les routines vraiment consomatrices on été parallélisées.

Maintenant quand j'essaye sur une machine 4x2 coeurs, j'obient un speed-up de seulement 2.5 alors que le taux d'accupation des 8 threads est de 550%.

Je n'arrive pas à comprendre pourquoi 550% me donne un gain de seulement 250% .

Si quelqu'un à de l'expérience là dessus, je suis preneur.
20/11/2009, 19h50
Mac LAK
J'ai un peu de mal avec les chiffres que tu me donnes, surtout ceux de charge CPU qui dépassent 100%... ;)

Partons sur la base d'un calcul monothread, qui est 100% : à combien arrive le processus sur la machine avec l'HT ? 75%, ou 25% du temps initial ? Idem pour la machine bi-CPU.

Sinon, le "faible" gain de performance peut s'expliquer de plusieurs manières, notamment :
- Perte de temps lors des synchronisations.
- Blocage du bus mémoire unique sur le CPU lorsque deux coeurs tentent d'accéder simultanément à la RAM.
- Blocage d'un CPU par l'autre dans le cas d'une RAM commune entre les deux procs, ou temps de copie dans le cas de RAM séparées.
- Mauvaise répartition des threads sur les coeurs / CPU.
Tu peux également aller voir cette ancienne discussion, qui pourrait t'éclairer.
21/11/2009, 10h07
uriotcea

Merci de ta réponse et le lien qui répond en partie à mes intérrogations
Pour revenir à mes valeurs de speed-up, si je normalise à 100% sur un processeur sur le bi-pro j'ai 95% d'occupation pour un speed-up de 1.7, alors que sur la machine 8 coeurs l'occupation est de 60% pour un seed-up de 2.5
23/11/2009, 00h52
Mac LAK

Données trop volumineuses et/ou trop longues à déplacer, à priori, ce qui pénalise la parallélisation... Notamment, le fait de ne pas arriver à 100% de CPU est en général symptomatique d'un bus mémoire encombré, qui met alors les threads en attente le temps qu'il se débloque.

Donnes-nous quelques chiffres : combien d'éléments sont traités par chaque thread ? Organisés comment ? Quelle taille totale ?

Oui tu dois avoir raison, mais le code est top complex pour que je puisse te montrer l'ensemble. Il doit y avoir quelques choses comme une centaine de directive openMP. Voici un example du code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
 
      ALLOCATE(EEx(nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEy(nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEz(nx2p1,ny2p1,nz2p1))
 
      DO l=1,nx2p1
       DO m=1,ny2p1
        DO n=1,nz2p1
          EEx(l,n,m)=0
          EEy(l,n,m)=0
          EEz(l,n,m)=0
          ENDDO
        ENDDO
       ENDDO
      ENDDO
 
      debut=omp_get_wtime()
 
      DO i=1,nx2
 
       i1=i+1
       DO j=1,ny2
        j1=j+1
        DO k=1,nz2
         k1=k+1
         km1=k-1
         kp2=k+2
         IF(tabNijk.GT.0.01)THEN
          DO l=1,nx2p1
           IF(partinx(l))THEN
            IF((i-l).GE.0) THEN
             il=i1-l
             ux=tabNijk
            ELSE
             il=l-i
             ux=-tabNijk
            ENDIF
            DO m=iborneminf(l),ibornemsup(l)
             IF(partinxy(l,m))THEN
              IF((j-m).GE.0) THEN
               jm=j1-m
               uy=tabNijk
              ELSE
               jm=m-j
               uy=-tabNijk
              ENDIF
              iljm=il+jm
              IF (iljm.NE.2) THEN
               DO n=iborneninf(l,m),ibornensup(l,m)
                IF(partinxyz(l,m,n))THEN
                 IF((k-n).GE.0) THEN
                  kn=k1-n
                  uz=tabNijk
                 ELSE
                  kn=n-k
                  uz=-tabNijk
                 ENDIF
                 IF ((kn.GE.1).AND.(kn.LE.nz2)) THEN
                   EEx(l,m,n)=EEx(l,m,n)+ux*TabEx(il,jm,kn)
                   EEy(l,m,n)=EEy(l,m,n)+uy*TabEy(il,jm,kn)
                   EEz(l,m,n)=EEz(l,m,n)+uz*TabEz(il,jm,kn)
                 ENDIF
                ENDIF
               ENDDO
              ELSE
               DO n=1,k
                IF(partinxyz(l,m,n))THEN
                 kn=k1-n
                 IF ((kn.GE.1).AND.(kn.LE.nz2)) THEN
                   EEx(nn,l,m,n)=EEx(l,m,n)+ux*TabEx(il,jm,kn)
                   EEy(nn,l,m,n)=EEy(l,m,n)+uy*TabEy(il,jm,kn)
              EEz(nn,l,m,n)=EEz(l,m,n)+tabNijk*TabEz(il,jm,kn)
                 ENDIF
                ENDIF
               ENDDO
               DO n=k1,nz2p1
                IF(partinxyz(l,m,n))THEN
                 kn=n-k
                 IF ((kn.GE.1).AND.(kn.LE.nz2)) THEN
                   EEx(l,m,n)=EEx(l,m,n)+ux*TabEx(il,jm,kn)
                   EEy(l,m,n)=EEy(l,m,n)+uy*TabEy(il,jm,kn)
              EEz(l,m,n)=EEz(l,m,n)-tabNijk*TabEz(il,jm,kn)
                 ENDIF
                ENDIF
               ENDDO
              ENDIF
             ENDIF
            ENDDO
           ENDIF
          ENDDO
         ENDIF
        ENDDO
       ENDDO
      ENDDO
 
      print *,omp_get_wtime()-debut

Que j'ai parallélisé comme ca:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
      ALLOCATE(EEEx(NbrT,nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEEy(NbrT,nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEEz(NbrT,nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEx(nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEy(nx2p1,ny2p1,nz2p1))
      ALLOCATE(EEz(nx2p1,ny2p1,nz2p1))
 
      DO l=1,nx2p1
       DO m=1,ny2p1
        DO n=1,nz2p1
          EEx(l,n,m)=0
          EEy(l,n,m)=0
          EEz(l,n,m)=0
 
          DO nn=1,NbrT
            EEEx(nn,l,m,n)=0
            EEEy(nn,l,m,n)=0
            EEEz(nn,l,m,n)=0
          ENDDO
        ENDDO
       ENDDO
      ENDDO
 
 
       debut=omp_get_wtime()
 
 
!$OMP PARALLEL DO PRIVATE(i1,j1,k1,km1,kp2,tabNijk,il,ux,jm,uy,iljm,
!$OMP& kn,uz) IF(NbrT.NE.1)
      DO i=1,nx2
 
       nn=omp_get_thread_num()+1
 
       i1=i+1
       DO j=1,ny2
        j1=j+1
        DO k=1,nz2
         k1=k+1
         km1=k-1
         kp2=k+2
         IF(tabNijk.GT.0.01)THEN
          DO l=1,nx2p1
           IF(partinx(l))THEN
            IF((i-l).GE.0) THEN
             il=i1-l
             ux=tabNijk
            ELSE
             il=l-i
             ux=-tabNijk
            ENDIF
            DO m=iborneminf(l),ibornemsup(l)
             IF(partinxy(l,m))THEN
              IF((j-m).GE.0) THEN
               jm=j1-m
               uy=tabNijk
              ELSE
               jm=m-j
               uy=-tabNijk
              ENDIF
              iljm=il+jm
              IF (iljm.NE.2) THEN
               DO n=iborneninf(l,m),ibornensup(l,m)
                IF(partinxyz(l,m,n))THEN
                 IF((k-n).GE.0) THEN
                  kn=k1-n
                  uz=tabNijk
                 ELSE
                  kn=n-k
                  uz=-tabNijk
                 ENDIF
                 IF ((kn.GE.1).AND.(kn.LE.nz2)) THEN
                   EEEx(nn,l,m,n)=EEEx(nn,l,m,n)+ux*TabEx(il,jm,kn)
                   EEEy(nn,l,m,n)=EEEy(nn,l,m,n)+uy*TabEy(il,jm,kn)
                   EEEz(nn,l,m,n)=EEEz(nn,l,m,n)+uz*TabEz(il,jm,kn)
                 ENDIF
                ENDIF
               ENDDO
              ELSE
               DO n=1,k
                IF(partinxyz(l,m,n))THEN
                 kn=k1-n
                 IF ((kn.GE.1).AND.(kn.LE.nz2)) THEN
                   EEEx(nn,l,m,n)=EEEx(nn,l,m,n)+ux*TabEx(il,jm,kn)
                   EEEy(nn,l,m,n)=EEEy(nn,l,m,n)+uy*TabEy(il,jm,kn)
              EEEz(nn,l,m,n)=EEEz(nn,l,m,n)+tabNijk*TabEz(il,jm,kn)
                 ENDIF
                ENDIF
               ENDDO
               DO n=k1,nz2p1
                IF(partinxyz(l,m,n))THEN
                 kn=n-k
                 IF ((kn.GE.1).AND.(kn.LE.nz2)) THEN
                   EEEx(nn,l,m,n)=EEEx(nn,l,m,n)+ux*TabEx(il,jm,kn)
                   EEEy(nn,l,m,n)=EEEy(nn,l,m,n)+uy*TabEy(il,jm,kn)
              EEEz(nn,l,m,n)=EEEz(nn,l,m,n)-tabNijk*TabEz(il,jm,kn)
                 ENDIF
                ENDIF
               ENDDO
              ENDIF
             ENDIF
            ENDDO
           ENDIF
          ENDDO
         ENDIF
        ENDDO
       ENDDO
      ENDDO
 
      print *,omp_get_wtime()-debut
      DO l=1,nx2p1
       DO m=1,ny2p1
        DO n=1,nz2p1
          DO nn=1,NbrT
            EEx(l,n,m)=EEx(l,m,n)+EEEx(nn,l,m,n)
            EEy(l,n,m)=EEy(l,m,n)+EEEy(nn,l,m,n)
            EEz(l,n,m)=EEz(l,m,n)+EEEz(nn,l,m,n)
          ENDDO
        ENDDO
       ENDDO
      ENDDO
 
      DEALLOCATE(EEEx)
      DEALLOCATE(EEEy)
      DEALLOCATE(EEEz)

Donc ici j'ai du créer des tableau temporaire EEEx, EEEy,EEEz parce que faire une commande REDUCTION(+:EEx,EEy,EEz) fait planter le code. Je pense que c'est due à la taille limite du stack.
Enfin j'ai un speed-up de 1.7 sur 2 processeurs pour un taux d'occupation de 100%

Je ne sais pas si c'est la meilleur méthode dans cette example.

23/11/2009, 10h09
Mac LAK

Le souci des frameworks comme OpenMP, c'est qu'ils ne permettent pas forcément d'optimiser ce genre de choses réellement : la solution courante à ce type de problème, c'est de lancer un thread de plus que le nombre de cœurs (voire un thread de plus par coeur) afin d'occuper un peu plus le CPU pendant les blocage du bus mémoire.

De plus, je ne sais pas ce qu'il se passe réellement côté affinité des threads, mais la "meilleure" solution consiste à bloquer un thread par cœur + un "flottant" (ou un deuxième lui aussi fixé si besoin). Je mets "meilleure" entre guillemets, parce que la BONNE solution consiste à revoir sa parallélisation afin de diminuer la taille des données traitées, quitte à séparer l'algo en deux passes : c'est beaucoup plus coûteux en temps CPU, mais cela permet une parallélisation efficace => au final, on gagne du temps réel, même si l'on augmente la charge CPU et que l'on plombe grave les perfs en monothread.

Dans ton cas particulier, je ne sais par exemple pas quelle est la taille des données fourguées à chaque thread, ni quel est l'algo implémenté. Mais souvent, lorsque l'on a un gain de performance très modeste par rapport à ce que l'on attendait, une refonte de l'algo et/ou de l'organisation des données est impérative.
23/11/2009, 10h16
uriotcea

Je vais essayé de voir si je peux changer quelques points dans quelques uns des algos, mais compte tenu de la complexité du code ma priorité restera de toute facon de m'assurer que le code fonctionne toujours correctement en mode séquentiel. Le code restant trés délicat à modifier sans casser quelquechose quelquepart sans pour autant s'en apercevoir immédiatement, j'ai une trés fortre contrainte sur la sécurité.

Merci de ton aide
23/11/2009, 19h42
uriotcea

J'ai remplacé dans l'example précédent, la duplication de mes tableaux par une directivement "REDUCTION(+:EEx,EEy,EEz)" et là miracle j'ai un speed-up de 6 sur 8 cores. Je pensais avoir ecrit quelquechose d'équivalent. En fait mon example présentait un speed-up de 1,7 sur mon bi-pro, 2,5 sur un 8 processeurs linux et un incroyable 0.25 sur un 8 pro windows.
Pas facile à optimiser, openMP !
24/11/2009, 11h38
Mac LAK

Citation:

Envoyé par uriotcea

Pas facile à optimiser, openMP !

C'est le souci de tous les frameworks (et la raison pour laquelle je n'aime pas forcément les utiliser) : on ne sait pas ce qu'ils font derrière... ;) L'utilisation d'un framework encourage à ne pas regarder comment fonctionne le matériel derrière, et c'est une erreur fatale que l'on voit hélas trop souvent sur les programmes Java ou interprétés, qui se retrouvent à se trainer comme des tortues asthmatiques. Or, dans le cas du parallélisme, connaître des choses comme l'unicité du bus mémoire, la taille des caches L1/L2 ou l'affinité processeur ne sont PAS optionnelles, du moins pas si l'on veut des performances décentes.

Je pense qu'il faut bien considérer les choses comme elles doivent l'être : OpenMP est très bien pour threader rapidement quelque chose d'assez léger, ou rendre asynchrone des tâches qui nécessiteraient un worker thread un peu lourd à mettre en place manuellement.

Mais dans le cadre d'un calcul intensif, ou d'un processus parallèle permanent (ex : système de scheduling / distribution), il est souvent bien plus efficace de s'y mettre "à la main" pour être certain du travail fait derrière, et garder un contrôle réel sur les threads lancés... Ou alors, maîtriser parfaitement OpenMP, ce qui n'est à priori pas si courant / évident que ça.

Dans tous les cas, il faut savoir un peu ce qu'il se passe sous le capot, sinon, on peut tourner en rond indéfiniment et ne réussir sa parallélisation que par erreur / hasard.
24/11/2009, 12h26
uriotcea

Oui, ca parait évident ce que tu indiques. Mais il faut tout de même considéré que j'ai preque terminé de parallélisé un code de plus de 40.000 lignes fait de fortran,c et C++, sans même forcément tout saisir de ce qu'il fait exactement, grâce à la simplicité d'implémentation de openMP. Exact, il faut faire trés attention, mais quelques semaines de travails au regards des mois qu'il m'aurait fallu si j'avais tout fait à la main.
J'avais commencé, à la main avec pthread, c'est complexe et ca double facilement les lignes de codes.