D. De planningscomponent

Een parallelle regio heeft ten minste één barrière, aan het einde ervan, en kan er extra barrières in hebben. Bij elke barrière moeten de andere leden van het team wachten tot de laatste thread aankomt. Om deze wachttijd te minimaliseren, moet gedeeld werk worden gedistribueerd, zodat alle threads ongeveer op hetzelfde moment bij de barrière aankomen. Als een deel van dat gedeelde werk deel for uitmaakt van constructies, kan de schedule component voor dit doel worden gebruikt.

Wanneer er herhaalde verwijzingen naar dezelfde objecten zijn, kan de keuze van de planning voor een for constructie voornamelijk worden bepaald door kenmerken van het geheugensysteem, zoals de aanwezigheid en grootte van caches en of geheugentoegangstijden uniform of niet-uniform zijn. Dergelijke overwegingen kunnen ervoor zorgen dat elke thread consistent verwijst naar dezelfde set elementen van een matrix in een reeks lussen, zelfs als aan sommige threads relatief minder werk in sommige lussen wordt toegewezen. Deze installatie kan worden uitgevoerd met behulp van het static schema met dezelfde grenzen voor alle lussen. In het volgende voorbeeld wordt nul gebruikt als de ondergrens in de tweede lus, ook al k zou het natuurlijker zijn als de planning niet belangrijk was.

#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);
}

In de overige voorbeelden wordt ervan uitgegaan dat geheugentoegang niet de dominante overweging is. Tenzij anders vermeld, wordt ervan uitgegaan dat alle threads vergelijkbare rekenbronnen ontvangen. In deze gevallen is de keuze van de planning voor een for constructie afhankelijk van alle gedeelde werkzaamheden die moeten worden uitgevoerd tussen de dichtstbijzijnde voorafgaande barrière en ofwel de impliciete sluitingsbarrière of de dichtstbijzijnde aanstaande barrière, als er een nowait component is. Voor elk soort planning ziet u in een kort voorbeeld hoe dat soort planning waarschijnlijk de beste keuze is. Een korte discussie volgt elk voorbeeld.

Het static schema is ook geschikt voor het eenvoudigste geval, een parallelle regio met één for constructie, waarbij elke iteratie dezelfde hoeveelheid werk vereist.

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

Het static schema wordt gekenmerkt door de eigenschappen die elke thread ongeveer hetzelfde aantal iteraties krijgt als elke andere thread, en elke thread kan onafhankelijk de iteraties bepalen die eraan zijn toegewezen. Er is dus geen synchronisatie vereist om het werk te distribueren en, onder de veronderstelling dat elke iteratie dezelfde hoeveelheid werk vereist, moeten alle threads ongeveer op hetzelfde moment worden voltooid.

Voor een team van p threads laat u plafond(n/p) het gehele getal q zijn, dat voldoet aan n = p*q - r met 0 <= r < p. Een implementatie van het static schema voor dit voorbeeld zou q-iteraties toewijzen aan de eerste p-1-threads en q-r-iteraties aan de laatste thread. Een andere acceptabele implementatie zou q-iteraties toewijzen aan de eerste p-r-threads en q-1-iteraties aan de resterende r-threads. In dit voorbeeld ziet u waarom een programma niet moet vertrouwen op de details van een bepaalde implementatie.

De dynamic planning is geschikt voor het geval van een for constructie met de iteraties waarvoor verschillende of zelfs onvoorspelbare hoeveelheden werk nodig zijn.

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

Het dynamic schema wordt gekenmerkt door de eigenschap die niet langer in de barrière wacht dan een andere thread nodig heeft om de uiteindelijke iteratie uit te voeren. Deze vereiste betekent dat iteraties één voor één aan threads moeten worden toegewezen zodra deze beschikbaar zijn, met synchronisatie voor elke toewijzing. De synchronisatieoverhead kan worden verminderd door een minimale segmentgrootte k groter dan 1 op te geven, zodat threads tegelijk worden toegewezen totdat er minder dan k overblijft. Dit garandeert dat er geen thread langer op de barrière wacht dan een andere thread nodig heeft om de uiteindelijke segment van (maximaal) k iteraties uit te voeren.

De dynamic planning kan handig zijn als de threads verschillende rekenresources ontvangen, die veel hetzelfde effect hebben als verschillende hoeveelheden werk voor elke iteratie. Op dezelfde manier kan de dynamische planning ook nuttig zijn als de threads op verschillende tijdstippen bij de for constructie aankomen, hoewel in sommige van deze gevallen de guided planning de voorkeur kan hebben.

Het guided schema is geschikt voor het geval waarin de threads op verschillende tijdstippen bij een for constructie kunnen aankomen waarbij elke iteratie ongeveer dezelfde hoeveelheid werk vereist. Deze situatie kan zich voordoen als de for constructie bijvoorbeeld wordt voorafgegaan door een of meer secties of for constructies met nowait componenten.

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

Het schema garandeert dat dynamicer geen thread langer op de barrière wacht dan een andere thread nodig heeft om de uiteindelijke iteratie uit te voeren, of definitieve k-iteraties als er een segmentgrootte van guided is opgegeven. Onder dergelijke planningen wordt de guided planning gekenmerkt door de eigenschap waarvoor het de minste synchronisaties vereist. Voor segmentgrootte k wijst een typische implementatie q = ceiling(n/p) iteraties toe aan de eerste beschikbare thread, stelt u n in op de groter van n-q en p*k en herhaalt u deze totdat alle iteraties zijn toegewezen.

Wanneer de keuze van de optimale planning niet zo duidelijk is als voor deze voorbeelden, is het runtime schema handig om te experimenteren met verschillende planningen en segmentgrootten zonder het programma te hoeven wijzigen en opnieuw te compileren. Het kan ook handig zijn wanneer de optimale planning afhankelijk is (op een voorspelbare manier) van de invoergegevens waarop het programma wordt toegepast.

Als u een voorbeeld wilt zien van de afwegingen tussen verschillende planningen, kunt u overwegen om 1000 iteraties tussen acht threads te delen. Stel dat er in elke iteratie een invariante hoeveelheid werk is en dat als tijdseenheid gebruikt.

Als alle threads op hetzelfde moment beginnen, zorgt de planning ervoor dat de static constructie in 125 eenheden wordt uitgevoerd, zonder synchronisatie. Maar stel dat één thread 100 eenheden te laat is bij aankomst. Vervolgens wachten de resterende zeven threads op 100 eenheden bij de barrière en de uitvoeringstijd voor de hele constructie neemt toe tot 225.

Omdat zowel de als dynamicguided de planning ervoor zorgen dat er geen thread wacht op meer dan één eenheid in de barrière, zorgt de vertraagde thread ervoor dat de uitvoeringstijden van de constructie slechts tot 138 eenheden toenemen, mogelijk verhoogd door vertragingen van synchronisatie. Als dergelijke vertragingen niet te verwaarlozen zijn, wordt het belangrijk dat het aantal synchronisaties 1000 is voor dynamic maar slechts 41, guidedervan uitgaande van de standaard chunkgrootte van één. Met een segmentgrootte van 25, dynamic en guided beide eindigen in 150 eenheden, plus eventuele vertragingen van de vereiste synchronisaties, die nu respectievelijk slechts 40 en 20 zijn.