126

É possível observar em alguns casos que a separação de tarefas em múltiplas threads não dá ganho e até torna uma aplicação mais lenta que o uso em thread única. Não deveria sempre ter ganho de performance quando tem vários processadores (não necessariamente chips)?

O ganho ocorre em alguma situação quando só existe um processador (ou core) na máquina?

É possível paralelizar qualquer tarefa e obter ganho de performance?

0

8 Respostas 8

128
+50

Uma analogia pode ajudar.

Você tem um monte de cartas que precisam ser entregues a diversos endereços na cidade. Então você contrata um motoboy para entregar as suas cartas.

Considere que sinais de trânsito (semáforos, faróis) em sua cidade são perfeitos. Eles estão sempre verdes a menos que alguém esteja no cruzamento.

Adicione threads

O motoboy precisa entregar rapidamente várias cartas. Uma vez que não há mais ninguém nas ruas, todas as luz estão verdes. Mas isso poderia ser mais rápido. Melhor contratar outro piloto para a moto.

O problema é que você ainda só tem uma moto. Então agora o seu primeiro motoboy dirige a motocicleta por um tempo, e então de vez em quando ele para, abandona a moto, e o segundo contratado começa pilotá-la.

Isso fica mais rápido? Não, claro que não. Isto é mais lento. Adicionando mais threads não faz nada mais rápido. Threads não são mágicas. Se um processador é capaz de fazer um bilhão de operações por segundo, acrescentando outra thread não fará o processador executar outro bilhão de operações por segundo. Em vez disso, ele rouba recursos de outras threads. Se uma moto pode correr a 180 km/hora, pará-la para que outro piloto suba nela não irá tornar a entrega mais rápida! Claramente, em média, as cartas não estão sendo entregues mais rapidamente neste esquema, elas apenas estão sendo entregues em uma ordem diferente.

Adicione processador

OK, então o que acontece se você contratar dois pilotos e duas motos? Agora você tem dois processadores e uma thread por processador, de modo que será mais rápido, certo? Não, porque nós esquecemos sobre os semáforos. Antes, só havia uma motocicleta dirigindo em alta velocidade a qualquer momento. Agora, existem dois motoboys e duas motocicletas, o que significa que agora, por vezes, uma das motocicletas deverá esperar, já que a outra está no cruzamento. Mais uma vez, a adição de mais threads retarda o andamento já que você gasta mais tempo disputando os cruzamentos das ruas. Quanto mais processadores você adicionar, pior fica, você acaba com mais e mais tempo de espera no sinal vermelho e menos e menos tempo entregando cartas.

Adicionando mais threads pode causar escalabilidade negativa se tiver mais travamento (lock) competindo entre si. Quanto mais threads, mais disputa, e tudo fica mais lento.

Claro que você terá dois entregadores trabalhando, isto pode deixar a entrega mais rápida se eles não perderem muito tempo parados nos semáforos.

Aumente o clock

Suponha que você arrume motocicletas mais potentes - agora você tem mais processadores, mais threads e processadores mais rápidos. Agora isso sempre será mais rápido? Não. Quase sempre, não. O aumento da velocidade do processador pode fazer programas multithread ficarem mais lentos. Mais uma vez, pense sobre o tráfego total.

Suponha que você tem uma cidade com milhares de motoristas e 64 motocicletas, todos os motoboys vão se revezando entre as motos, algumas delas estão em cruzamentos bloqueando outras motocicletas. Agora você tem todas essas motos correndo mais rápido. Será que isso ajuda? Bem, na vida real, quando você está dirigindo por aí nas ruas normais, você chegará ao seu destino duas vezes mais rápido em um Porsche do que em um Honda Civic? Claro que não, a maior parte do tempo, dirigindo pela cidade, você está preso no trânsito.

Se você pode dirigir mais rápido, muitas vezes você acaba esperando mais tempo no trânsito porque você acaba dirigindo mais rápido até o congestionamento. Se todas as pessoas chegam mais rápido ao congestionamento, então o congestionamento piora.

Exemplos onde ajuda e onde não ajuda

Desempenho multithread pode ser profundamente contraditório. Se você quer alta performance é recomendável não usar uma solução de várias threads, a menos que você tenha uma aplicação que é "intrinsecamente paralela" - ou seja, alguma aplicação que é, obviamente passível de usar vários processadores, como por exemplo, cálculo do conjunto de Mandelbrot que faz ray tracing. E então, não coloque no problema mais threads que processadores disponíveis. Portanto, para muitas aplicações, usando mais threads pioram a performance. Usando um exemplo mais simples, somar uma lista de números quaisquer pode ser paralelizada, mas achar sucessores Fibonacci não pode.

Outra forma de ver isso: Nove mulheres não farão um bebê em um mês.

Custo de administração

Suponha que você tem uma tarefa a realizar. Vamos dizer que você é um professor de matemática e você tem 20 trabalhos para corrigir. Leva 2 minutos para corrigir cada um, por isso vai demorar cerca de 40 minutos.

Agora vamos supor que você decida contratar alguns assistentes para ajudá-lo. Demora uma hora (60 minutos) para localizar 4 assistentes. Cada um de deles corrigirão 4 trabalhos e tudo será feito em 8 minutos. Você trocou 40 minutos de trabalho por 68 minutos no total, incluindo a hora extra para encontrar os assistentes. Isto não é um ganho. A sobrecarga de encontrar os assistentes é maior do que o custo de fazer o trabalho sozinho.

Agora, suponha que você tem 20.000 trabalhos para corrigir, por isso vai demorar cerca de 40.000 minutos. Agora, se você passar uma hora encontrando os mesmo 4 assistentes, isso é uma vitória. Cada um pega 5000 trabalhos e são gastos um total de 10060 minutos em vez de 40.000 minutos, uma economia de quase 5 vezes. A sobrecarga de encontrar os assistentes é basicamente irrelevante.

Paralelização não é grátis. O custo de dividir o trabalho entre as diferentes threads deve ser pequeno em comparação com a quantidade de trabalho realizado por thread.

O problema não é de processamento

Se as tarefas não usam fortemente o processador então claramente não pode haver algum aumento de velocidade, porque enquanto o processador está ocioso esperando o disco ou a rede responder, ele poderia estar fazendo o trabalho de outra thread.

Vamos supor que você tem duas tarefas ligadas ao processador (que usa processamento propriamente dito), um único processador, e uma thread ou duas threads. Ignorando o tempo de administração, no cenário de uma thread temos os seguinte:

  • Fazer 100% do trabalho da tarefa 1. Suponha que isso leva 1.000ms.
  • Fazer 100% do trabalho da tarefa 2. Suponha que isso leva 1.000ms.

Tempo total: 2 segundos. Total de tarefas feitas: 2. Mas aqui é a parte importante: o cliente que estava esperando pela tarefa 1 tem seu trabalho feito em apenas 1 segundo. O cliente que estava à espera da tarefa 2 teve que esperar 2 segundos.

Agora, se temos duas threads e uma CPU vemos o seguinte:

  • Fazer 10% do trabalho da tarefa 1, por 100ms.
  • Fazer 10% do trabalho da tarefa 2, por 100ms.
  • Fazer 10% do trabalho da tarefa 1
  • Fazer 10% do trabalho da tarefa 2 ...

Mais uma vez, o tempo total de 2 segundos, mas desta vez o cliente que estava esperando pela tarefa 1 tem seu trabalho feito em 1,9 segundos, quase 100% mais lento do que o cenário de uma thread!

E nem foi considerado o tempo para ficar trocando de tarefas que não é tão pequeno.

Então se as seguintes condições existem:

  • as tarefas são limitadas pela capacidade da CPU
  • há mais threads que CPUs
  • A tarefa é útil apenas pelo seu o resultado final e não suas partes

Então, adicionar mais threads só torna tudo mais lento.

Mas se qualquer uma das seguintes condições não forem satisfeitas, adicionar mais threads é uma boa ideia:

  • Se as tarefas não são limitadas pela CPU, adicionar mais threads permite que a CPU trabalhe quando estaria ociosa, esperando pela rede ou disco, por exemplo.
  • Se houver CPUs ociosas, adicionando mais threads permite que essas CPUs sejam agendadas para trabalhar.
  • Se os resultados parcialmente computados são úteis, adicionando mais threads melhora a situação porque há mais oportunidades para que os clientes consumam resultados já computados. No segundo cenário, por exemplo, os clientes de ambas as tarefas estão obtendo resultados parciais a cada 200 milissegundos, o que é importante.

Thread não é a única solução para tornar CPUs ociosas por fatores externos disponíveis para uso. Mas isso é outra estória.

O uso de threads gera um risco de condição de corrida.

O crédito desta resposta é essencialmente do Eric Lippert nas respostas:

Coloquei no GitHub para referência futura.

8
  • 15
    Estou experimentando a comunidade aqui. Esse é o tipo de conteúdo legal que devemos trazer do SO? Se discorda, deixe um comentário ou discuta o assunto no meta.br.stackoverflow.com
    – Maniero
    Commented 14/01/2014 às 14:49
  • 7
    Essa foi uma das melhores analogias que eu vi na vida. +1 Commented 4/02/2014 às 17:18
  • 3
    Muito boa compilação! Commented 18/04/2014 às 2:05
  • 2
    Não entendi essa parte: Agora você tem dois processadores e uma thread por processador, de modo que vai ser mais rápido, certo? Não, porque nós esquecemos sobre os semáforos. Isso seria para caso as duas threads forem síncronas? Uma dependendo do resultado da outra? E se cada uma delas puder fazer o trabalho dela independente da outra, não terá esse problema?
    – Math
    Commented 2/12/2014 às 15:25
  • 3
    Exato. E muitos casos exigem threads síncronas. A maioria dos problemas exigem cruzamentos. Quando você pode garantir uma avenida sem semáforos (tarefas independentes) aí não há problema de pegar semáforos. Poderá ainda ter os outros problemas se não tomar o cuidado necessário.
    – Maniero
    Commented 2/12/2014 às 15:34
41

Vamos por partes:

Não deveria sempre ter ganho de performance quando tem vários processadores (não necessariamente chips)?

Não, pois é necessário processamento adicional para criar, finalizar e gerenciar a troca de processos. Se as threads executam por pouco tempo, esse "custo" adicional afeta negativamente o desempenho geral.

O ganho ocorre em alguma situação quando só existe um processador (ou core) na máquina?

Sim, pois existem diversos fatores que podem causar o bloqueio de uma thread. Por exemplo, numa requisição de rede, é melhor que a thread solicitante fique bloqueada até a placa de rede receber uma resposta, permitindo assim que outros processamentos sejam executados, mesmo que não haja a possibilitada de paralelismo.

É possível paralelizar qualquer tarefa e obter ganho de performance?

Não, certos algoritmos são sequenciais por natureza. Um exemplo simples que me vem à mente é o cálculo do Número de Fibonacci, cujo valor depende do cálculo de números anteriores.

Ainda que threads diferentes fossem criadas para calcular este número, cada uma delas teria que aguardar o encerramento do cálculo das duas threads anteriormente criadas. Este é apenas um caso para exemplificar que existem situações onde o paralelismo não é eficiente. A ideia é que alguns tipos de processamento de dados básicos não podem ser subdivididos.

1
  • 2
    Estou fazendo uma resposta e ia usar o exemplo de Fibonacci. Nem vou usar agora :)
    – Maniero
    Commented 14/01/2014 às 14:08
21

Existem obstáculos que podem tornar uma aplicação multi-threaded menos eficiente que uma com um único thread, como por exemplo a memória compartilhada (ou não).

Se dois threads compartilham a mesma região de memória, o acesso concorrente a ela pode trazer problemas. A solução - isolar trechos do programa em seções críticas - acaba por ter um alto custo, se não me engano da ordem de 10.000 ciclos do processador (equivalente a um acesso ao disco). Se o seu algoritmo possui muitos trechos que exigem um acesso exclusivo a um recurso [de memória ou outros], esse lock pode acabar tendo um custo que anule os benefícios da paralelização.

Se por outro lado cada thread controlar uma região de memória separada, o overhead da comunicação entre os diferentes threads também tem de ser levado em conta. Falando pela experiência, é possível que a solução paralelizada acabe pior que a sequencial (mesmo em ambientes multi-processador, como supercomputadores) simplesmente porque o tempo que os threads gastam trocando informações entre si (por soquetes, pipes, etc) supera a redução de tempo proporcionada pela paralelização.

Some-se a isso as considerações dadas nas demais respostas (overhead do sistema de threading em si, bloqueio e dependência entre um thread e outro, etc), e a resposta é não, nem sempre haverá ganho de performance.

18

Nem sempre a paralelização de tarefas dará ganho de performance.

Na situação mais simples: um único processador (chip), com um único núcleo (core), sem tecnologia de hiper-threading. Todo o código é executado em um mesmo lugar, e mesmo que o processor faça algum otimização de ir executando um pedaço do código enquanto aguarda o resultado de outro pedaço. Mesmo assim, sempre haverá um pedaço do código que dependerá de uma decisão (um 'if'). E também haverá um processamento extra (mais código sendo executado) para controlar o status de cada thread, o que exige mais processamento.

Mesmo que exista mais de um core ou mais de um processador, sempre haverá a necessidade de gerenciar o que cada thread está fazendo, e dependendo do código, haverá a espera por uma decisão, uma entrada do usuário, o resultado de outro processamento qualquer...

Também deve ser considerada a competição de recursos: se todas as threads precisam acessar a memória, o disco rígido, a placa de rede, poderá ocorrer (facilmente) que uma thread tenha que esperar o recurso responder, já que a velocidade do processador é muito superior à velocidade que estes dispositivos fornecem dados para que ele prossiga.

Os maiores ganhos de paralelização ocorrerão em tarefas que tenham um processamento intensivo, independente de operações do usuário, e independente do resultado de outros processamentos. Por exemplo, se você tiver 8 núcleos disponíveis em seu equipamento, criar 7 threads para fazer a compactação de 7 arquivos pequenos diferentes trará algum ganho. Se os mesmos arquivos forem grandes (e não couberem na memória), logo o gargalo do disco rígido impactará a performance do seu paralelismo.

18

Não, há várias questões que interferem o desempenho sendo elas:

  • Em um programa multithreads para que uma thread entre em funcionamento é necessário fazer uma troca de contexto (o que consome tempo do processador além da memoria).
  • Em um programa com uma quantidade muito grande de threads será necessário múltiplas trocas de contexto o que pode fazer com que o processador gaste uma fatia de tempo maior trocando contextos do que realizado operações.
  • O ganho de performance estará sempre limitado ao tempo de execução sequencial (vide Lei de Amdahl)
  • Não é possível paralelizar qualquer tipo de aplicação poia há operações que são essencialmente sequenciais fazer a media de determinados valores de um conjunto de dados e verificar quais que estão acima/abaixo desta média, note que não é possível iniciar a verificação de quais estão acima/abaixo da média a que o último número do conjunto de dados seja somado e a soma seja dividida. Logo há partes significativas sequenciais.
16

É bom ter cuidado em não confundir paralelismo com concorrência.

Paralelismo diz respeito a duas tarefas que rodam ao mesmo tempo. Exemplo: duas tarefas rodando ao mesmo tempo, uma em cada CPU.

Concorrência diz respeito a duas tarefas que podem rodar independente uma da outra. Exemplo: duas tarefas rodando em apenas uma CPU.

Nem todos os problemas podem ter soluções que usem tarefas paralelas ou concorrentes, e dos problemas que têm, nem todos têm uma melhora de desempenho. Alguns problemas podem ter soluções eficientes com concorrência mas que perdem performance se você tentar adicionar paralelismo causando disputa de recursos do sistema, e o inverso também pode ocorrer.

2
  • 1
    Concordo. duas tarefas podem ser paralelas E concorrentes entre si, mas não necessariamente.
    – Maniero
    Commented 14/01/2014 às 14:13
  • 2
    @downvoter: se importa de comentar?
    – elias
    Commented 15/04/2014 às 20:28
12

Não. O paralelismo pode fazer com seu programa execute seu papel em menor tempo, mas de forma alguma existe essa garantia.

Alias, pode até mesmo ocorrer o contrário. Além da coordenação de múltiplas threads por parte do programa não ser uma tarefa simples (o que pode acarretar em ainda mais código a ser executado), ainda existe um overhead por parte do sistema operacional para criar/destruir as threads.

11

Segundo a lei de Amdhal, o speed up máximo de uma tarefa que corra em diversos CPUs, depende da proporção de código que pode ser paralelizada.

Ou seja se o algoritmo for altamente paralelizável, aumentar CPUs e threads deverá ter um ganho maior, se o algoritmo não for paralelizável (ou seja, se houver muito controlo de fluxo/dados) então o ganho é nulo ou pode haver mesmo perda de desempenho.

inserir a descrição da imagem aqui

1
  • Bom complemento
    – Maniero
    Commented 7/06/2017 às 10:06

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .