Quelle est la différence entre “statique” et “dynamique” dans le calendrier d'OpenMP?

D'autres depuis ont répondu à la plupart de la question, mais je voudrais rappeler à certains cas précis où une planification particulière type est plus adapté que les autres. Annexe contrôle la manière dont les itérations de boucle sont divisés entre les threads. Choisir la bonne planification peut avoir un grand impact sur la vitesse de l'application.

static annexe signifie que les itérations blocs sont cartographiés de manière statique à l'exécution de threads dans un round-robin". La bonne chose avec ordonnancement statique est que OpenMP moment de l'exécution de garanties que si vous avez deux boucles séparées avec le même nombre d'itérations et de les exécuter avec le même nombre de threads à l'aide d'ordonnancement statique, puis chaque thread recevrez exactement la même itération de la gamme(s) dans les deux parallèles régions. Ceci est particulièrement important sur les systèmes NUMA: si vous appuyez sur la mémoire dans la première boucle, il va résider sur le nœud NUMA où l'exécution du thread a été. Ensuite, dans la deuxième boucle le même thread peut accéder au même emplacement de mémoire plus rapide car il va résider sur le même nœud NUMA.

L'imaginer il y a deux nœuds NUMA: le nœud 0 et le nœud 1, par exemple, un deux-socket Intel Nehalem conseil avec 4-core, dans les deux sockets. Puis threads 0, 1, 2, et 3 se trouvent sur le nœud 0 et fils 4, 5, 6, et 7 se trouvent sur le nœud 1:

|             | core 0 | thread 0 |
| socket 0    | core 1 | thread 1 |
| NUMA node 0 | core 2 | thread 2 |
|             | core 3 | thread 3 |

|             | core 4 | thread 4 |
| socket 1    | core 5 | thread 5 |
| NUMA node 1 | core 6 | thread 6 |
|             | core 7 | thread 7 |

Chaque noyau peut accéder à la mémoire à partir de chaque nœud NUMA, mais l'accès à distance est plus lent (1.5 x 1,9 x plus lent sur Intel) que le nœud local d'accès. Vous lancez quelque chose comme ceci:

char *a = (char *)malloc(8*4096);

#pragma omp parallel for schedule(static,1) num_threads(8)
for (int i = 0; i < 8; i++)
   memset(&a[i*4096], 0, 4096);

4096 octets dans ce cas est la taille standard d'une page de la mémoire sous Linux sur x86 si énorme pages ne sont pas utilisées. Ce code permet de réinitialiser l'ensemble de la 32 Kio tableau a. Le malloc() appel juste des réserves de l'espace d'adressage virtuel mais ne fait pas de "toucher" la mémoire physique (ce qui est le comportement par défaut à moins qu'une autre version de malloc est utilisé, par exemple, celui qui efface la mémoire comme calloc() n'). Maintenant, ce tableau est contigus, mais seulement dans la mémoire virtuelle. Dans la mémoire physique de la moitié des il serait mentir dans le mémoire joint à la prise 0 et la moitié dans le mémoire joint à la prise 1. Il en est ainsi parce que les différentes parties sont remis à zéro par différents threads et les threads résident sur les différents cœurs et il ya quelque chose appelé premier contact de la politique NUMA qui signifie que les pages de mémoire sont alloués sur le nœud NUMA sur lequel le fil de cette première "touché" de la page de mémoire réside.

|             | core 0 | thread 0 | a[0]     ... a[4095]
| socket 0    | core 1 | thread 1 | a[4096]  ... a[8191]
| NUMA node 0 | core 2 | thread 2 | a[8192]  ... a[12287]
|             | core 3 | thread 3 | a[12288] ... a[16383]

|             | core 4 | thread 4 | a[16384] ... a[20479]
| socket 1    | core 5 | thread 5 | a[20480] ... a[24575]
| NUMA node 1 | core 6 | thread 6 | a[24576] ... a[28671]
|             | core 7 | thread 7 | a[28672] ... a[32768]

Maintenant permet d'exécuter une autre boucle comme ceci:

#pragma omp parallel for schedule(static,1) num_threads(8)
for (i = 0; i < 8; i++)
   memset(&a[i*4096], 1, 4096);

Chaque thread va accéder à la déjà mappé en mémoire physique, et elle aura le même mappage de fil à la mémoire de la région comme l'une lors de la première boucle. Cela signifie que les fils aura uniquement accès à la mémoire située dans leurs locaux des blocs de mémoire qui sera rapide.

Maintenant, imaginez qu'un autre schéma de planification est utilisé pour la deuxième boucle: schedule(static,2). Ce sera "chop" itération de l'espace en blocs de deux itérations et il y aura 4 blocs au total. Ce qui va arriver, c'est que nous aurons le fil de discussion suivant à l'emplacement mémoire de la cartographie (à travers le nombre d'itération):

|             | core 0 | thread 0 | a[0]     ... a[8191]  <- OK, same memory node
| socket 0    | core 1 | thread 1 | a[8192]  ... a[16383] <- OK, same memory node
| NUMA node 0 | core 2 | thread 2 | a[16384] ... a[24575] <- Not OK, remote memory
|             | core 3 | thread 3 | a[24576] ... a[32768] <- Not OK, remote memory

|             | core 4 | thread 4 | <idle>
| socket 1    | core 5 | thread 5 | <idle>
| NUMA node 1 | core 6 | thread 6 | <idle>
|             | core 7 | thread 7 | <idle>

Deux mauvaises choses se produisent ici:

• fils 4 à 7 de rester inactif et de la moitié de calcul de la capacité est perdue;
• fils 2 et 3, l'accès non-local de la mémoire et qu'il leur faudra environ deux fois plus de temps pour terminer au cours de laquelle les threads 0 et 1 restera inactif.

Ainsi, l'un des avantages pour l'utilisation de la planification statique est qu'il améliore la localité des accès mémoire. L'inconvénient est que les mauvais choix des paramètres de planification peut ruiner la performance.

dynamic planification des travaux sur une base "premier arrivé, premier servi". Deux pistes avec le même nombre de threads peut (et probable) produire complètement différent "itération de l'espace" -> "threads" mappages comme on peut facilement le vérifier:

$ cat dyn.c
#include <stdio.h>
#include <omp.h>

int main (void)
{
  int i;

  #pragma omp parallel num_threads(8)
  {
    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[1] iter %0d, tid %0d\n", i, omp_get_thread_num());

    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[2] iter %0d, tid %0d\n", i, omp_get_thread_num());
  }

  return 0;
}

$ icc -openmp -o dyn.x dyn.c

$ OMP_NUM_THREADS=8 ./dyn.x | sort
[1] iter 0, tid 2
[1] iter 1, tid 0
[1] iter 2, tid 7
[1] iter 3, tid 3
[1] iter 4, tid 4
[1] iter 5, tid 1
[1] iter 6, tid 6
[1] iter 7, tid 5
[2] iter 0, tid 0
[2] iter 1, tid 2
[2] iter 2, tid 7
[2] iter 3, tid 3
[2] iter 4, tid 6
[2] iter 5, tid 1
[2] iter 6, tid 5
[2] iter 7, tid 4

(même comportement est observé lorsque gcc est utilisé à la place)

Si l'exemple de code à partir de la static article a été exécuté avec dynamic de la planification au lieu de cela, il y aura seulement 1/70 (1.4%) de chance que l'original de la localité serait préservé et 69/70 (98.6%) de chance que l'accès à distance allait se produire. Ce fait est souvent négligé et donc sous-optimale de ses performances.

Il y a une autre raison de choisir entre static et dynamic de la planification - l'équilibrage de la charge. Si chaque itération prend très différente de la moyenne du temps à remplir puis de travail élevée déséquilibre peut se produire dans le cas statique. Prenons comme exemple le cas où la durée d'exécution d'une itération croît linéairement avec le nombre d'itérations. Si l'itération de l'espace est divisé de manière statique entre les deux fils, la seconde va avoir trois fois plus de travail que la première, et, partant, pour les 2/3 du temps de calcul que le premier thread sera inactif. Calendrier dynamique introduit une charge supplémentaire, mais dans ce cas particulier, mènera à beaucoup mieux la distribution de charge de travail. Un type spécial de dynamic la planification est le guided où de plus en plus petites itération blocs sont donnés pour chaque tâche que le travail progresse.

Depuis précompilés code peut être exécuté sur différentes plates-formes, ce serait bien si l'utilisateur peut contrôler la planification. C'est pourquoi OpenMP offre spéciale schedule(runtime) clause. Avec runtime de planification le type est pris à partir du contenu de la variable d'environnement OMP_SCHEDULE. Ceci permet de tester les différents types de planification sans avoir à recompiler l'application et aussi permet à l'utilisateur d'affiner sa plate-forme.

La boucle schéma de partitionnement est différent. La statique planificateur aurait pour effet de diviser une boucle de N éléments en M sous-ensembles, et chaque sous-ensemble serait alors contenir strictement N/M éléments.

L'approche dynamique calcule la taille de la sous-ensembles à la volée, ce qui peut être utile si le sous-ensembles' des temps de calcul varient.

L'approche statique devrait être utilisé si le temps de calcul varient pas beaucoup.