D. Clause schedule

Une région parallèle a au moins une barrière, à sa fin, et peut avoir des barrières supplémentaires à son intérieur. À chaque barrière, les autres membres de l’équipe doivent attendre que le dernier thread arrive. Pour réduire ce temps d’attente, le travail partagé doit être distribué afin que tous les threads arrivent à la barrière en même temps. Si certains de ces travaux partagés sont contenus dans for des constructions, la schedule clause peut être utilisée à cet effet.

Lorsqu’il existe des références répétées aux mêmes objets, le choix de la planification d’une for construction peut être déterminé principalement par des caractéristiques du système de mémoire, telles que la présence et la taille des caches et si les temps d’accès à la mémoire sont uniformes ou non uniformes. Ces considérations peuvent rendre préférable que chaque thread fasse référence de manière cohérente au même ensemble d’éléments d’un tableau dans une série de boucles, même si certains threads sont affectés relativement moins de travail dans certaines boucles. Cette configuration peut être effectuée à l’aide de la static planification avec les mêmes limites pour toutes les boucles. Dans l’exemple suivant, zéro est utilisé comme limite inférieure dans la deuxième boucle, même si k elle serait plus naturelle si la planification n’était pas importante.

#pragma omp parallel
{
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    a[i] = work1(i);
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    if(i>=k) a[i] += work2(i);
}

Dans les exemples restants, il est supposé que l’accès à la mémoire n’est pas la considération dominante. Sauf indication contraire, il est supposé que tous les threads reçoivent des ressources de calcul comparables. Dans ces cas, le choix de la planification d’une for construction dépend de tous les travaux partagés qui doivent être effectués entre la barrière précédente la plus proche et l’obstacle de fermeture implicite ou la barrière la plus proche à venir, s’il existe une nowait clause. Pour chaque type de planification, un court exemple montre comment ce type de planification est susceptible d’être le meilleur choix. Une brève discussion suit chaque exemple.

La static planification est également appropriée pour le cas le plus simple, une région parallèle contenant une construction unique for , avec chaque itération nécessitant la même quantité de travail.

#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
  invariant_amount_of_work(i);
}

La static planification est caractérisée par les propriétés que chaque thread obtient approximativement le même nombre d’itérations que n’importe quel autre thread, et chaque thread peut déterminer indépendamment les itérations qui lui sont affectées. Par conséquent, aucune synchronisation n’est nécessaire pour distribuer le travail et, selon l’hypothèse que chaque itération nécessite la même quantité de travail, tous les threads doivent se terminer en même temps.

Pour une équipe de threads p , laissez le plafond(n/p) être l’entier q, qui satisfait n = p*q - r avec 0 <= r < p. Une implémentation de la static planification de cet exemple affecterait des itérations q aux premiers threads p-1 et aux itérations q-r au dernier thread. Une autre implémentation acceptable affecterait des itérations q aux premiers threads p-r et des itérations q-1 aux threads r restants. Cet exemple illustre pourquoi un programme ne doit pas s’appuyer sur les détails d’une implémentation particulière.

La dynamic planification est appropriée pour le cas d’une for construction avec les itérations nécessitant des quantités de travail variables ou même imprévisibles.

#pragma omp parallel for schedule(dynamic)
  for(i=0; i<n; i++) {
    unpredictable_amount_of_work(i);
}

La dynamic planification est caractérisée par la propriété qu’aucun thread n’attend à la barrière pendant plus longtemps qu’il n’en faut un autre pour exécuter son itération finale. Cette exigence signifie que les itérations doivent être attribuées une à la fois aux threads au fur et à mesure qu’elles deviennent disponibles, avec la synchronisation pour chaque affectation. La surcharge de synchronisation peut être réduite en spécifiant une taille de bloc minimale k supérieure à 1, afin que les threads soient affectés k à la fois jusqu’à ce que moins de k restent. Cela garantit qu’aucun thread n’attend au niveau de la barrière plus longtemps qu’il n’en faut un autre pour exécuter son segment final d’itérations k (au plus) k .

La dynamic planification peut être utile si les threads reçoivent des ressources de calcul variables, ce qui a beaucoup le même effet que les quantités de travail variables pour chaque itération. De même, la planification dynamique peut également être utile si les threads arrivent à la for construction à différents moments, même si dans certains cas, la guided planification peut être préférable.

La guided planification est appropriée pour le cas où les threads peuvent arriver à des moments variables à une for construction avec chaque itération nécessitant environ la même quantité de travail. Cette situation peut se produire si, par exemple, la for construction est précédée d’une ou plusieurs sections ou for constructions avec nowait des clauses.

#pragma omp parallel
{
  #pragma omp sections nowait
  {
    // ...
  }
  #pragma omp for schedule(guided)
  for(i=0; i<n; i++) {
    invariant_amount_of_work(i);
  }
}

Comme dynamic, la guided planification garantit qu’aucun thread n’attend à la barrière plus longtemps qu’il ne faut à un autre thread pour exécuter son itération finale, ou les itérations k finales si une taille de bloc de k est spécifiée. Parmi ces planifications, la guided planification est caractérisée par la propriété qui nécessite les synchronisations les plus rares. Pour la taille de bloc k, une implémentation classique affecte des itérations q = ceiling(n/p) au premier thread disponible, définissez n sur la plus grande de n-q et p*k, puis répétez jusqu’à ce que toutes les itérations soient affectées.

Lorsque le choix de la planification optimale n’est pas aussi clair que pour ces exemples, la runtime planification est pratique pour expérimenter différentes planifications et tailles de blocs sans avoir à modifier et à recompiler le programme. Il peut également être utile lorsque la planification optimale dépend (d’une certaine manière prévisible) des données d’entrée auxquelles le programme est appliqué.

Pour voir un exemple de compromis entre différentes planifications, envisagez de partager 1 000 itérations entre huit threads. Supposons qu’il existe une quantité de travail invariante dans chaque itération et que vous l’utilisez comme unité de temps.

Si tous les threads démarrent en même temps, la static planification entraîne l’exécution de la construction en 125 unités, sans synchronisation. Mais supposons qu’un thread soit 100 unités en retard. Ensuite, les sept threads restants attendent 100 unités à la barrière, et le temps d’exécution de la construction entière augmente à 225.

Étant donné que les planifications et guided les dynamic planifications s’assurent qu’aucun thread n’attend plusieurs unités à la barrière, le thread retardé provoque l’augmentation des temps d’exécution de la construction uniquement à 138 unités, éventuellement augmenté par des retards de synchronisation. Si ces retards ne sont pas négligeables, il devient important que le nombre de synchronisations soit de 1 000, dynamic mais seulement 41 pour guided, en supposant la taille de bloc par défaut d’une. Avec une taille de bloc de 25, dynamic et guided les deux se terminent en 150 unités, ainsi que tous les retards des synchronisations requises, qui n’ont désormais que 40 et 20, respectivement.