D. A cláusula schedule

Uma região paralela tem pelo menos uma barreira, no final, e pode ter barreiras adicionais dentro dela. Em cada barreira, os outros membros da equipe devem aguardar a chegada do último thread. 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 contida em constructos for, a cláusula schedule poderá ser usada para essa finalidade.

Quando há referências repetidas aos mesmos objetos, a opção de agenda para um constructo for pode ser determinada principalmente por 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. Essas considerações podem tornar preferível que cada thread se refira de modo consistente 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 a agenda static com os mesmos limites para todos os loops. No exemplo a seguir, zero é usado como o limite inferior no segundo loop, embora k seja mais natural se a agenda não era 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, supõe-se que o acesso à memória não seja a consideração dominante. A menos que indicado de outra forma, supõem-se que todos os threads recebam recursos computacionais comparáveis. Nesses casos, a opção de agenda para um constructo for depende de todo o trabalho compartilhado a ser executado entre a barreira anterior mais próxima e a barreira de fechamento implícita ou a barreira futura mais próxima, se houver uma cláusula nowait. Para cada tipo de agenda, um breve exemplo mostra como esse tipo de agenda provavelmente será a melhor opção. Uma breve discussão segue cada exemplo.

A agenda static também é apropriada para o caso mais simples, uma região paralela que contém um só constructo for, 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);
}

A agenda static é caracterizada pelas propriedades em 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. Portanto, nenhuma sincronização é necessária para distribuir o trabalho e, supondo que cada iteração requer a mesma quantidade de trabalho, todos os threads devem ser concluídos aproximadamente ao mesmo tempo.

Para uma equipe de threads p, deixe teto(n/p) ser o inteiro q, que satisfaz n = p*q - r com 0 <= r < p. Uma implementação da agenda static 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 contar com os detalhes de uma implementação específica.

A agenda dynamic é apropriada para o caso de um constructo for com as iterações que exigem quantidades de trabalho variáveis ou até imprevisíveis.

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

A agenda dynamic é caracterizada pela propriedade que nenhum thread aguarda na barreira por mais tempo do que outro thread leva para executar sua iteração final. Esse requisito significa que as iterações devem ser atribuídas uma de cada vez a threads à medida que elas 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, de modo que os threads recebam k por vez até que restem menos de k. Isso garante que nenhum thread aguarde mais tempo na barreira do que outro thread leva para executar sua parte final de (no máximo) k iterações.

A agenda dynamic poderá ser útil se os threads receberem recursos computacionais variados, o que tem o mesmo efeito que quantidades variadas de trabalho para cada iteração. Da mesma forma, a agenda dinâmica também pode ser útil se os threads chegarem ao constructo for em horários variados, embora, em alguns desses casos, a agenda guided possa ser preferível.

A agenda guided é apropriada para o caso em que os threads podem chegar em horários variados em um constructo for com cada iteração exigindo aproximadamente a mesma quantidade de trabalho. Essa situação poderá ocorrer, por exemplo, se o constructo for for precedido por uma ou mais seções ou constructos for 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, a agenda guided garante que nenhum thread aguarde mais tempo na barreira do que outro thread leva para executar sua iteração final ou k iterações finais se um tamanho de bloco de k for especificado. Entre essas agendas, a agenda guided é caracterizada pela propriedade que exige o menor número de sincronizações. Para o tamanho da parte k, uma implementação típica atribuirá q = teto(n/p) iterações ao primeiro thread disponível, definirá n para o maior de n-q e p*k e se repetirá até que todas as iterações sejam atribuídas.

Quando a escolha da agenda ideal não é tão clara quanto para esses exemplos, a agenda runtime é conveniente para experimentar agendas e tamanhos de partes diferentes sem precisar modificar e recompilar o programa. Também pode ser útil quando a agenda ideal depende (de alguma forma previsível) dos dados de entrada aos quais o programa é aplicado.

Para ver um exemplo dos prós e contras entre agendas diferentes, considere compartilhar mil iterações entre oito threads. Suponha que haja uma quantidade invariável de trabalho em cada iteração e use-a como a unidade do tempo.

Se todos os threads forem iniciados ao mesmo tempo, a agenda static fará com que o constructo seja executado em 125 unidades, sem sincronização. Porém, suponha que um thread esteja 100 unidades atrasado na chegada. Com isso, os sete threads restantes esperam por 100 unidades na barreira e o tempo de execução de todo o constructo aumenta para 225.

Como as agendas dynamic e guided garantem que nenhum thread aguarde mais de uma unidade na barreira, o thread atrasado faz com que seus tempos de execução para o constructo aumentem apenas para 138 unidades, possivelmente aumentados por atrasos da sincronização. Se esses atrasos não forem insignificantes, será importante que o número de sincronizações seja de mil para dynamic mas apenas 41 para guided, supondo o tamanho padrão de parte de um. Com um tamanho de bloco de 25, dynamic e guided terminam em 150 unidades, mais qualquer atraso das sincronizações necessárias, que agora são de apenas 40 e 20, respectivamente.