D. A cláusula de calendário

Uma região paralela tem pelo menos uma barreira, na sua extremidade, e pode ter barreiras adicionais dentro dela. Em cada barreira, os outros membros da equipe devem esperar o último fio chegar. Para minimizar esse tempo de espera, o trabalho compartilhado deve ser distribuído para que todos os threads cheguem à barreira aproximadamente ao mesmo tempo. Se parte desse trabalho compartilhado estiver contido em for construções, a schedule cláusula pode ser usada para esse fim.

Quando há referências repetidas aos mesmos objetos, a escolha do cronograma para uma for construção pode ser determinada principalmente pelas características do sistema de memória, como a presença e o tamanho dos caches e se os tempos de acesso à memória são uniformes ou não uniformes. Tais considerações podem tornar preferível que cada thread se refira consistentemente ao mesmo conjunto de elementos de uma matriz em uma série de loops, mesmo que alguns threads recebam relativamente menos trabalho em alguns dos loops. Essa configuração pode ser feita usando o static agendamento com os mesmos limites para todos os loops. No exemplo a seguir, zero é usado como o limite inferior no segundo loop, mesmo que k fosse mais natural se o cronograma não 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);
}

Nos exemplos restantes, assume-se que o acesso à memória não é a consideração dominante. Salvo indicação em contrário, presume-se que todos os threads recebem recursos computacionais comparáveis. Nesses casos, a escolha do cronograma para uma for construção depende de todo o trabalho compartilhado que deve ser executado entre a barreira anterior mais próxima e a barreira de fechamento implícita ou a próxima barreira mais próxima, se houver uma nowait cláusula. Para cada tipo de horário, um pequeno exemplo mostra como esse tipo de horário provavelmente será a melhor escolha. Segue-se uma breve discussão após cada exemplo.

O static cronograma também é apropriado para o caso mais simples, uma região paralela contendo uma única for construção, com cada iteração exigindo a mesma quantidade de trabalho.

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

O static cronograma é caracterizado pelas propriedades de que cada thread obtém aproximadamente o mesmo número de iterações que qualquer outro thread, e cada thread pode determinar independentemente as iterações atribuídas a ele. Assim, nenhuma sincronização é necessária para distribuir o trabalho e, sob a suposição de que cada iteração requer a mesma quantidade de trabalho, todos os threads devem terminar aproximadamente ao mesmo tempo.

Para uma equipe de segmentos p , deixe teto (n/p) ser o inteiro q, que satisfaz n = p*q - r com 0 <= r < p. Uma implementação do static cronograma para este exemplo atribuiria iterações q aos primeiros threads p-1 e iterações q-r ao último thread. Outra implementação aceitável atribuiria iterações q aos primeiros threads p-r e iterações q-1 aos threads r restantes. Este exemplo ilustra por que um programa não deve confiar nos detalhes de uma implementação específica.

O dynamic cronograma é apropriado para o caso de uma for construção com as iterações exigindo quantidades variáveis, ou mesmo imprevisíveis, de trabalho.

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

O dynamic cronograma é caracterizado pela propriedade de que nenhum thread espera na barreira por mais tempo do que leva outro thread para executar sua iteração final. Esse requisito significa que as iterações devem ser atribuídas uma de cada vez aos threads à medida que ficam disponíveis, com sincronização para cada atribuição. A sobrecarga de sincronização pode ser reduzida especificando um tamanho mínimo de bloco k maior que 1, para que os threads sejam atribuídos k de cada vez até que menos do que k permaneça. Isso garante que nenhum thread espere na barreira mais do que leva outro thread para executar seu bloco final de (no máximo) k iterações.

O dynamic cronograma pode ser útil se os threads receberem recursos computacionais variáveis, o que tem o mesmo efeito que quantidades variáveis de trabalho para cada iteração. Da mesma forma, o cronograma dinâmico também pode ser útil se os threads chegarem à for construção em momentos variados, embora em alguns desses casos o guided cronograma possa ser preferível.

O guided cronograma é apropriado para o caso em que os threads podem chegar em momentos diferentes numa for estrutura, com cada iteração exigindo aproximadamente a mesma quantidade de trabalho. Esta situação pode acontecer se, por exemplo, a for estrutura for precedida por uma ou mais seções ou for estruturas com cláusulas nowait.

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

Como dynamic, o guided cronograma garante que nenhuma tarefa espere na barreira mais do que o tempo que leva para outra tarefa executar a sua última iteração, ou as suas últimas k iterações se um tamanho de bloco de k for especificado. Entre esses horários, o guided cronograma é caracterizado pela propriedade que requer o menor número de sincronizações. Para o tamanho do bloco k, uma implementação típica atribuirá iterações q = ceiling(n/p) ao primeiro thread disponível, definirá n para o maior de n-q e p*k e repetirá até que todas as iterações sejam atribuídas.

Quando a escolha do cronograma ideal não é tão clara quanto para esses exemplos, o runtime cronograma é conveniente para experimentar diferentes horários e tamanhos de blocos sem ter que modificar e recompilar o programa. Também pode ser útil quando o cronograma ideal depende (de alguma forma previsível) dos dados de entrada aos quais o programa é aplicado.

Para ver um exemplo das compensações entre diferentes cronogramas, considere distribuir 1000 iterações entre oito threads. Suponha que haja uma quantidade invariante de trabalho em cada iteração e use isso como a unidade de tempo.

Se todas as threads começarem ao mesmo tempo, o agendamento static fará com que a estrutura seja executada em 125 unidades, sem sincronização. Mas suponha que um fio está 100 unidades atrasado na chegada. Em seguida, os sete threads restantes esperam por 100 unidades na barreira, e o tempo de execução para toda a construção aumenta para 225.

Como tanto os agendamentos dynamic quanto guided garantem que nenhum thread aguarde mais de uma unidade na barreira, o thread atrasado faz com que os seus tempos de execução para o construto aumentem apenas para 138 unidades, possivelmente aumentados por atrasos de sincronização. Se tais atrasos não forem desprezíveis, torna-se importante que o número de sincronizações seja 1000 para dynamic , mas apenas 41 para guided, assumindo o tamanho de bloco padrão de um. Com um tamanho de bloco de 25, dynamic e guided ambos terminam em 150 unidades, além de quaisquer atrasos das sincronizações necessárias, que agora são apenas 40 e 20, respectivamente.