Grid Computing – Parte 02

Neste tópico, vamos aprofundar um pouco na questão do paralelismo, nas formas de consegui-lo e os requisitos necessários para uma rotina ser quebrada em tarefas para aderir ao processamento em paralelo.

O paradigma do paralelismo

Como já vimos em posts anteriores sobre escalabilidade e performance, podemos ganhar ambos quebrando um grande processo ou tarefa em partes menores, e verificando se algumas destas partes podem ser executadas em paralelo. O interesse nessa área cresceu devido às limitações físicas que impedem o aumento da frequência (Clock) dos processadores. Porém, existe um grau de complexidade intrínseco no desenvolvimento de aplicações paralelas, em comparação com a codificação de um programa de processamento sequencial, pois sua implementação precisa prever e lidar com situações como a condição de corrida (race condition), onde a comunicação e a sincronização de diferentes sub-tarefas é uma das maiores barreiras para atingir desempenho em programas paralelos.

A abordagem científica e acadêmica destas dependências costuma utilizar um vocabulário complexo, vamos abordar de forma mais simples e direta. Uma determinada tarefa computacional complexa realizada por um algoritmo possui uma sequência chamada de ‘caminho crítico’. Este termo também é usado em Gerência de Projetos e Análise e Desenvolvimento de Sistemas. Na prática, nenhum pograma poderá rodar mais rápido do que a maior cadeia ou sequência de processos depententes. Entretanto, a maioria dos algoritmos não consiste de somente uma cadeia de processos dependentes, geralmente há oportunidades de executar cálculos independentes em paralelo.

Determinando tarefas paralelizáveis

As premissas gerais de etapas ou tarefas menores de processos que são paralelizáveis estão enumeradas abaixo, vamos abordar cada uma em mais detalhes ao decorrer do artigo. Vamos chamar de tarefa uma etapa do processo que desejamos avaliar sua aderência ao processamento paralelo.

1) Não pode haver dependências de valores

Os valores de entrada das tarefas não podem depender dos valores de entrada ou de saída de nenhuma outra tarefa. Por exemplo, um laço de execução que calcula um rendimento de um investimento em uma poupança não é paralelizável, pois o cálculo do rendimento de cada mês será executado com o saldo final do mês anterior.

2) Não pode haver condição de corrida

Nenhuma das tarefas deve alocar um recurso comum às demais tarefas em modo exclusivo. Isto caracteriza uma condição de corrida (race condition), e o tratamento disso implica na serialização da tarefa. Por exemplo, várias tarefas de processamento de notas fiscais de saída concorrentes, onde uma etapa de processamento envolve bloquear em modo exclusivo um registro do cadastro do produto para uma atualização de saldo ou um acumulador estatístico daquele produto vai eliminar o paralelismo de duas tarefas ou mais tarefas que forem ao mesmo tempo atualizar este produto, pois a primeira que conseguir o bloqueio exclusivo fará a atualização, enquanto as outras duas ficam esperando a liberação deste registro, jogando uma parte do ganho obtido com o paralelismo no lixo. Caso o acumulador em questão tiver que ser acessado por todas as tarefas, a coisa fica pior

Para este tipo de caso, deve ser verificado se compensa criar uma fila e/ou lista re requisições, e um processo único dedicado para estas requisições. Com apenas uma fila de requisições, esta pode tornar-se o caminho crítico deste processo. Tudo depende da velocidade que entram novos elementos nesta lista, e da velocidade que são realizados os processos dela, em relação às tarefas feitas em paralelo.

Por exemplo, se você têm 200 tarefas a realizar, onde cada uma demora em média 10 segundos, um processamento sequencial destas tarefas demoraria 2000 segundos ( 33 minutos aproximadamente). Porém, utilizando 10 processos simultâneos, cada processo executaria umas 20 requisições, onde o tempo e custo da infraestrutura de distribuição não será considerado, esse bloco de 20 requisições de 10 segundos cada demoraria 200 segundos, apresentando um ganho de 10 vezes, afinal cada um dos dez processos dedicados terminaria as suas atividades em 200 segundos, isso reduziria o tempo para 3 minutos e meio.

Porém, se destes 10 segundos, 1 segundo precisa ser dedicado ao acesso exclusivo de um recurso comum a todas as tarefas, cada acesso de uma tarefa colocaria as outras 9 em espera, a primeira tarefa em espera perderia 1 segundo, a segunda perderia 2, e assim sucessivamente, prejudicando bastante o tempo total para a finalização de todas as tarefas.

Para contornar isso, criamos uma fila e um processo dedicado a processar estas requisições, então cada tarefa demoraria 9 segundos, pois no momento que ela precisasse fazer o acesso exclusivo ao recurso, ela acrescentaria esta requisição na fila de um processo dedicado. Logo, cada um dos 10 processos dedicados ao processamento geral de tarefas executaria 20 requisições de 9 segundos, somando 180 segundos. No total de 200 requisições, cada uma colocaria em uma fila uma requisição de 1 segundo, logo o processo dedicado para processar a fila demoraria 200 segundos. Neste ponto, o processo da fila passou a ser o caminho critico, pois as tarefas distribuídas já terminaram, mas a fila ainda não está vazia. Mesmo assim, houve um ganho considerável em adotar esta medida.

Sabe-se neste ponto que, quanto mais processos em paralelo forem colocados para as tarefas de 9 segundos, , mais rápido estas tarefas serão executadas, mas a fila de tarefas sequenciais terá um tempo fixo de processamento, logo não será eficiente colocar mais de 10 processos dedicados, pois isto não vai diminuir o tempo da fila.

3) Considere o custo implícito na distribuição das tarefas

Quando o paralelismo das tarefas será executada em computadores distribuídos, deve-se levar em conta a latência na transferência dos parâmetros e do retorno das tarefas entre a aplicação que solicitou o processamento e o agente alocado para o processo. No exemplo anterior, desconsideramos o tempo de latência, mas sabe-se que o ganho escalar com o aumento de paralelismo não segue uma progressão geométrica.

Ao usar um mecanismo de distribuição de tarefas para múltiplos computadores, devemos levar em conta a latência de rede para trafegar os parâmetros de cada tarefa, isto dente a ser proporcional à quantidade de dados necessários, e pode acabar sendo um fator limitante do número de processos paralelos que você poderá usar simultaneamente, afinal não adianta deixar 50 processos dedicados se a banda de rede bater 100 % de uso com 35 processos, você começa a perder tempo para passar para cada processo o que ele tem que fazer.

Se o seu processo for muito curto, e a quantidade de dados trafegados for grande, o tempo gasto com a distribuição e controle destes processos pode consumir com a eficiência do paralelismo… neste caso estas tarefas poderiam ser executadas mais rápidas sequencialmente por um processo único, ou ainda poderiam ser distribuídas entre threads ou serviços na mesma máquina, usando recursos mais leves de comunicação entre processos na mesma máquina (como memória compartilhada por exemplo). Estas variantes serão abordadas em um próximo post.

Conclusão

No princípio isso pode parecer um monstro de duas cabeças, e quando você chega mais perto, parecem sete … Mas não entre em pânico, vamos nos aprofundar neste tema em doses homeopáticas, e depois de alguns exemplos de processos didáticos devidamente explicados, eu garanto que vai ficar mais fácil.

Até o próximo post, pessoal 😉

Referências

COMPUTAÇÃO PARALELA. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2014. Disponível em: <http://pt.wikipedia.org/w/index.php?title=Computa%C3%A7%C3%A3o_paralela&oldid=38961464>. Acesso em: 30 nov. 2014.

CONDIÇÃO DE CORRIDA. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2014. Disponível em: <http://pt.wikipedia.org/w/index.php?title=Condi%C3%A7%C3%A3o_de_corrida&oldid=40376481>. Acesso em: 30 nov. 2014.

CHEDE, CESAR TAURION. Grid Computing, um novo paradigma computacional. Rio de Janeiro: Brasport, 2004.

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s