Balanceamento de carga e desempenho paralelo

Resumo

Balancear a carga de trabalho de um aplicativo entre threads é uma atividade crítica para um bom desempenho. O principal objetivo de se fazer balanceamento de carga é diminuir o tempo ocioso das threads. Compartilhar a carga de trabalho de forma igualitária entre todas as threads, com a mínima perda durante o processo de distribuição de trabalho resulta em menos ciclos de processador desperdiçados com threads ociosas que não contribuem para o trabalho, e, portanto, proporciona um melhor desempenho. No entanto, alcançar o balanceamento de carga perfeito não é algo trivial e depende do paralelismo dentro do aplicativo, da carga de trabalho, do número de threads, da política de balanceamento e da implementação das threads.

Este artigo faz parte da série "Guia Intel para desenvolvimento de aplicativos multithreaded (em inglês)", que fornece diretrizes para o desenvolvimento de aplicativos multithreaded eficientes baseados em plataformas Intel®.

Histórico

Um núcleo ocioso durante a computação de dados é um recurso desperdiçado que aumenta o tempo total de execução do aplicativo multithread, uma vez que a execução paralela efetiva poderia estar acontecendo naquele núcleo, isso. Esse tempo ocioso pode ser o resultado de diferentes causas, como uma busca na memória ou de um dispositivo de I/O. Embora nem sempre seja possível evitar que núcleos fiquem ociosos, existem medidas que podem ser utilizadas pelos programadores para reduzir esse tempo ocioso, como operações de I/O sobrepostas, pré-busca de memória, e reordenação dos padrões de acesso a dados para uma utilização melhor do cache.

Da mesma forma, threads ociosas também são recursos desperdiçados na execução de atividades multithreaded. A atribuição de quantidades desbalanceadas de trabalho às threads resulta numa condição conhecida como "desequilíbrio de cargas." Quanto maior o desequilíbrio de cargas, mais as threads permanecerão ociosas e, portanto, maior será o tempo necessário para se completar o trabalho. Quanto mais equilibrada for a distribuição das tarefas computacionais entre as threads disponíveis, menor será o tempo de execução total.

Como um exemplo, considere um conjunto de doze tarefas independentes com o seguinte conjunto de tempos de execução: {10, 6, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1}. Supondo-se que quatro threads estejam disponíveis para executar esse conjunto de tarefas, um método simples de atribuição de tarefas seria programar cada thread com três tarefas, distribuídas em ordem. Dessa forma, à thread 0 seria atribuída o trabalho de 20 unidades de tempo (10 +6 +4), à thread 1, 8 unidades de tempo (4 +2 +2), à thread 2, 5 unidades de tempo (2 +2 +1), e a thread 3 executaria as três tarefas em apenas 3 unidades de tempo (1 +1 +1). A Figura 1 (a) ilustra essa distribuição de trabalho e mostra que o tempo de execução geral para as doze tarefas seria de 20 unidades de tempo (tempo sendo executado de cima para baixo).

Figura 1. Exemplos de distribuição de tarefas entre as quatro threads.


Uma melhor distribuição do trabalho teria sido: Thread 0: {10}, Thread 1: {4, 2, 1, 1}, Thread 2: {6, 1, 1}, e Thread 3: {4, 2, 2, 2}, como mostrado na Figura 1 (b). Essa programação levaria apenas 10 unidades de tempo para ser completada e apenas duas das quatro threads ficariam ociosas em 2 unidades de tempo cada.

Recomendações

Quando todas as tarefas tiverem o mesmo tamanho, uma solução fácil e que resulta numa distribuição balanceada é a distribuição simples e estática dessas tarefas entre as threads disponíveis, dividindo-se o número total de tarefas em grupos aproximadamente iguais e distribuindo-os entre as threads. No caso geral, no entanto, mesmo quando os tamanhos de todas a tarefas são conhecidos previamente, encontrar um modo ótimo e balanceado de atribuir tarefas às threads é um problema difícil de resolver. Por outro lado, quando os tamanhos das tarefas individuais não são os mesmos, a melhor solução pode ser uma divisão mais dinâmica de tarefas para atribuir às threads.

A distribuição de trabalho iterativo da OpenMP* tipicamente assume como padrão a atribuição estática de iterações para threads (ou então, a distribuição pode ser especificada). Quando a carga de trabalho varia entre as iterações e o padrão torna-se imprevisível, a distribuição dinâmica de iterações para as threads pode balancear melhor a carga. Duas alternativas de atribuição, dinâmica e guiada, são especificadas pela cláusula schedule. Na atribuição dinâmica, blocos de iterações são atribuídos às threads. Quando a atribuição é concluída, as threads solicitam um novo bloco de iterações. O argumento opcional da cláusula schedule define um tamanho fixo para os blocos de iteração da distribuição dinâmica.

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


A atribuição guiada atribui inicialmente grandes blocos de iterações para as threads. O número de iterações atribuídas às threads é reduzido conforme as iterações ainda não atribuídas diminuem. Devido ao padrão de atribuição, a atribuição guiada tende a gerar menos sobrecarga do que a atribuição dinâmica. O argumento opcional da cláusula schedule define o número mínimo de iterações em um bloco a ser atribuído às threads de forma guiada.

#pragma omp parallel for schedule(guided, 8)
  for (i = 0; i < n; i++)
  {
    uneven_amount_of_work(i);
  }


Um caso especial é quando a carga de trabalho entre as iterações é continuamente crescente (ou decrescente). Por exemplo, o número de elementos por linha em uma matriz triangular inferior aumenta de forma regular. Para tais casos, definir um tamanho de bloco relativamente pequeno (para criar um número maior de blocos / tarefas) com atribuição estática pode fornecer um equilíbrio de carga adequado, sem a sobrecargas requerida pelas atribuições dinâmica ou guiada.

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


Quando a escolha do tipo de atribuição não é aparente, o uso de atribuição runtime (em tempo de execução) permite a alteração do tamanho do bloco e do tipo de atribuição à vontade, sem a necessidade de recompilação do programa.

Ao usar o algoritmo parallel_for do Intel® Threading Building Blocks (Intel® TBB), o programador divide a iteração em pequenas tarefas, que são atribuídas às threads. Se o tempo de computação de algumas iterações for maior que o de outras iterações, o distribuidor do Intel TBB é capaz de “roubar” dinamicamente algumas tarefas dessas threads, a fim de alcançar um melhor equilíbrio de carga entre elas.

Modelos explícitos de threading (por exemplo, threads Windows*, pthreads* e threads Java*) não possuem nenhum meio de distribuir automaticamente um conjunto de tarefas independentes em threads. Quando necessário, essa capacidade precisa ser programada no aplicativo. A atribuição estática de tarefas é um processo simples. Para atribuição dinâmica, dois métodos são facilmente implementados: Produtor-Consumidor (Producer / Consumer) e Chefe-Trabalhador (Boss / Worker). No primeiro caso, uma thread (Produtor) coloca tarefas em uma estrutura de fila compartilhada, enquanto as threads Consumidoras removem as tarefas a serem processadas, conforme a necessidade. Embora não seja estritamente necessário, o modelo Produtor-Consumidor é frequentemente utilizado quando existe algum pré-processamento a ser feito antes das tarefas serem disponibilizadas às threads Consumidoras.

No modelo Chefe-Trabalhador, as threads Trabalhadoras comunicam-se com a thread Chefe sempre que for necessário mais trabalho, de forma a receberem as atribuições diretamente.. Nas situações em que o delineamento de uma tarefa é muito simples, como um conjunto de índices para uma matriz de dados a ser processada, um contador global com sincronização apropriada pode ser utilizado, ao invés de uma thread Chefe específica. Em outras palavras, threads Trabalhadoras acessam o valor atual do contador e ajustam (possivelmente incrementando) o contador para a próxima thread, solicitando trabalho adicional.

Independentemente do modelo de atribuição de tarefas utilizado, deve-se considerar a utilização do número e do tipo correto de threads, a fim de garantir que as threads encarregadas de realizar as computações necessárias não fiquem ociosas. Por exemplo, se as threads Consumidoras ficarem inativas em alguns momentos, poderá ser necessário reduzir o no número de Consumidores ou criar uma thread Produtora adicional. A solução apropriada dependerá dos algoritmos, assim como do número e do tamanho das tarefas a serem atribuídas.

Diretrizes de uso

Qualquer método de atribuição de tarefas dinâmico implicará em alguma sobrecarga, resultante da distribuiçãode tarefas. O agrupamento de pequenas tarefas independentes em uma só unidade de trabalho pode reduzir essa sobrecarga. Da mesma forma, se estiver usando cláusulas de atribuição da OpenMP, defina um tamanho de bloco diferente do predefinido, que indicará o número mínimo de iterações em uma tarefa. A melhor escolha da quantidade de trabalho que compõe uma tarefa estará baseada na própria computação a ser feita e também no número de threads e outros recursos disponíveis em tempo de execução.

Recursos adicionais

Intel® Developer Zone Parallel Programming Community

Clay Breshears, The Art of Concurrency, O'Reilly Media, Inc., 2009.

Barbara Chapman, Gabriele Jost, and Ruud van der Post, Using OpenMP: Portable Shared Memory Parallel Programming, The MIT Press, 2007.

Intel® Threading Building Blocks

Intel Threading Building Blocks for Open Source

James Reinders, Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism, O'Reilly Media, Inc. Sebastopol, CA, 2007.

M. Ben-Ari, Principles of Concurrent and Distributed Programming, Second Edition, Addison-Wesley, 2006.

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.