D. Clausola schedule

Un'area parallela ha almeno una barriera, alla sua fine, e potrebbe avere ulteriori barriere al suo interno. A ogni barriera, gli altri membri del team devono attendere l'arrivo dell'ultimo thread. Per ridurre al minimo questo tempo di attesa, il lavoro condiviso deve essere distribuito in modo che tutti i thread arrivino alla barriera contemporaneamente. Se alcuni dei lavori condivisi sono contenuti in for costrutti, la schedule clausola può essere usata a questo scopo.

Quando sono presenti riferimenti ripetuti agli stessi oggetti, la scelta della pianificazione per un for costrutto può essere determinata principalmente dalle caratteristiche del sistema di memoria, ad esempio la presenza e le dimensioni delle cache e se i tempi di accesso alla memoria sono uniformi o non uniformi. Tali considerazioni possono rendere preferibile che ogni thread faccia riferimento costantemente allo stesso set di elementi di una matrice in una serie di cicli, anche se alcuni thread vengono assegnati relativamente meno lavoro in alcuni cicli. Questa configurazione può essere eseguita usando la static pianificazione con gli stessi limiti per tutti i cicli. Nell'esempio seguente, zero viene usato come limite inferiore nel secondo ciclo, anche se k sarebbe più naturale se la pianificazione non fosse 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);
}

Negli esempi rimanenti si presuppone che l'accesso alla memoria non sia la considerazione dominante. Se non diversamente specificato, si presuppone che tutti i thread ricevano risorse di calcolo confrontabili. In questi casi, la scelta della pianificazione per un for costrutto dipende da tutto il lavoro condiviso che deve essere eseguito tra la barriera precedente più vicina e la barriera di chiusura implicita o la barriera successiva più vicina, se è presente una nowait clausola . Per ogni tipo di pianificazione, un breve esempio mostra come il tipo di pianificazione sia probabilmente la scelta migliore. Una breve discussione segue ogni esempio.

La static pianificazione è appropriata anche per il caso più semplice, un'area parallela contenente un singolo for costrutto, con ogni iterazione che richiede la stessa quantità di lavoro.

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

La static pianificazione è caratterizzata dalle proprietà che ogni thread ottiene approssimativamente lo stesso numero di iterazioni di qualsiasi altro thread e ogni thread può determinare in modo indipendente le iterazioni assegnate. Pertanto, non è necessaria alcuna sincronizzazione per distribuire il lavoro e, presupponendo che ogni iterazione richieda la stessa quantità di lavoro, tutti i thread devono terminare contemporaneamente.

Per un team di thread p , lasciar ceiling(n/p) essere il numero intero q, che soddisfa n = p*q - r con 0 <= r < p. Un'implementazione della static pianificazione per questo esempio assegnerebbe le iterazioni q ai primi thread p-1 e le iterazioni q-r all'ultimo thread. Un'altra implementazione accettabile assegnerebbe le iterazioni q ai primi thread p-r e le iterazioni q-1 ai thread r rimanenti. In questo esempio viene illustrato il motivo per cui un programma non deve basarsi sui dettagli di una particolare implementazione.

La dynamic pianificazione è appropriata per il caso di un for costrutto con le iterazioni che richiedono un numero variabile, o anche imprevedibile, di lavoro.

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

La dynamic pianificazione è caratterizzata dalla proprietà che nessun thread attende la barriera per più tempo rispetto all'esecuzione dell'iterazione finale da parte di un altro thread. Questo requisito significa che le iterazioni devono essere assegnate una alla volta ai thread non appena diventano disponibili, con la sincronizzazione per ogni assegnazione. Il sovraccarico di sincronizzazione può essere ridotto specificando una dimensione minima di blocco k maggiore di 1, in modo che i thread vengano assegnati k alla volta fino a quando non rimangono meno di k . Ciò garantisce che nessun thread attenda più a lungo della barriera che richiede un altro thread per eseguire il blocco finale di iterazioni k (al massimo).

La dynamic pianificazione può essere utile se i thread ricevono risorse di calcolo variabili, che hanno lo stesso effetto di quantità variabili di lavoro per ogni iterazione. Analogamente, la pianificazione dinamica può essere utile anche se i thread arrivano al for costrutto in momenti diversi, anche se in alcuni di questi casi la guided pianificazione può essere preferibile.

La guided pianificazione è appropriata per il caso in cui i thread possono arrivare a diverse ore in un for costrutto con ogni iterazione che richiede circa la stessa quantità di lavoro. Questa situazione può verificarsi se, ad esempio, il for costrutto è preceduto da una o più sezioni o for costrutti con nowait clausole.

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

Come dynamic, la guided pianificazione garantisce che nessun thread attenda più a lungo della barriera rispetto a un altro thread per eseguire l'iterazione finale o le iterazioni k finali se viene specificata una dimensione di blocco di k. Tra queste pianificazioni, la guided pianificazione è caratterizzata dalla proprietà che richiede le sincronizzazioni più poche. Per le dimensioni di blocco k, un'implementazione tipica assegnerà q = ceiling(n/p) iterazioni al primo thread disponibile, impostare n sul più grande di n-q e p*k e ripetere fino a quando non vengono assegnate tutte le iterazioni.

Quando la scelta della pianificazione ottimale non è chiara come per questi esempi, la runtime pianificazione è utile per sperimentare diverse pianificazioni e dimensioni blocchi senza dover modificare e ricompilare il programma. Può essere utile anche quando la pianificazione ottimale dipende (in modo prevedibile) dai dati di input a cui viene applicato il programma.

Per un esempio di compromessi tra pianificazioni diverse, è consigliabile condividere 1000 iterazioni tra otto thread. Si supponga che sia presente una quantità di lavoro invariante in ogni iterazione e che venga usata come unità di tempo.

Se tutti i thread vengono avviati contemporaneamente, la pianificazione causerà l'esecuzione del static costrutto in 125 unità, senza sincronizzazione. Si supponga tuttavia che un thread sia di 100 unità in ritardo nell'arrivo. Quindi i sette thread rimanenti attendono 100 unità alla barriera e il tempo di esecuzione per l'intero costrutto aumenta a 225.

Poiché entrambe le dynamic pianificazioni e guided assicurano che nessun thread attenda più di un'unità nella barriera, il thread ritardato determina l'aumento dei tempi di esecuzione del costrutto solo a 138 unità, possibilmente incrementati da ritardi dalla sincronizzazione. Se tali ritardi non sono trascurabili, diventa importante che il numero di sincronizzazioni sia 1000 per dynamic ma solo 41 per guided, presupponendo la dimensione predefinita del blocco di uno. Con una dimensione di blocco pari a 25, dynamic e guided entrambe terminano in 150 unità, più eventuali ritardi delle sincronizzazioni richieste, che ora numerano solo 40 e 20, rispettivamente.