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.

Grid Computing – Parte 01

Introdução

Hoje vou entrar em um assunto que não é novo, mas que é pouco explorado devido a complexidade intrínseca de implementação: Grid Computing. Lembrando dos princípios e técnicas de performance e escalabilidade, onde uma delas é procurar obter benefícios de escalabilidade com execução de operações simultaneamente em vários equipamentos (paralelismo).

A computação em grid ou distribuída pode ser vista como um tipo particular de computação distribuída, onde vários equipamentos completos e independentes (não apenas CPUs) são interconectados por uma rede (Ethernet), atuando juntos para processar grandes tarefas.

A definição de computação paralela e distribuída são muito próximas, mas é possível classificá-las independentemente por um critério básico: Em computação paralela, todos os processos têm acesso a uma memória compartilhada para trocar informações entre processos, enquanto na computação distribuída, os processos trocam mensagens entre si, normalmente por uma conexão de rede.

Tamanhos de Grid

Um Grid pode englobar computadores geograficamente próximos ou distantes, e consequentemente ter uma pequena, média ou grande escala. Um dos maiores projetos de Grid colaborativo em larga escala (mundial) foi o projeto SETI@home, da NASA, lançado em 1999, onde cada voluntário fazia o download de um programa para processamento de dados de áudio em seu computador, e quando o equipamento estava IDLE ou na proteção de tela, o programa baixava da internet automaticamente um pacote de áudio para análise, e após o processamento enviava o resultado de volta ao servidor. A capacidade de processamento deste conjunto, com aproximadamente 145 mil equipamentos ativos em 233 países era capaz de processar 668 teraFLOPS!

Onde cabe o uso de Grid

Normalmente Grids de computadores são usados na resolução de problemas matemáticos, científicos e acadêmicos, bem como em empresas para aplicações como descoberta de novos remédios, previsão monetária, análise sísmica, e processamento de retaguarda para comércio eletrônico e Web Services.

Porém, se um problema computacional pode ser adequadamente paralelizável, o uso de uma camada leve de infra-estrutura de grid pode permitir que programas stand-alone recebam partes do processo para serem executadas em várias instâncias de processamento distribuídas em múltiplos equipamentos.

Vale atenção especial na sentença “adequadamente paralelizável”, veremos que atender a esta premissa não é cabível a todos os processos de um sistema, e envolve mais de uma característica de processo, relacionadas a entrada e saída de dados e ao processamento em si. Veremos estes detalhes em profundidade no momento oportuno. Vamos ver primeiro onde ele pode ser aplicado!

Cálculo de Folha de Pagamento

Um cálculo da folha de pagamento dos funcionários de uma empresa, onde cada funcionário possui seu registro de ponto e histórico de exceções em um período. Este é um bom exemplo onde o paralelismo de um grid de processamento serve muito bem.

Em uma aplicação de cálculo de folha de instância única, um programa de cálculo de folha de pagamento é executado em um processo, onde este processo vai calcular, em sequência, a folha de pagamento de cada funcionário no período, um a um. Este programa, em uma única instância sendo executada em um único equipamento, não consegue utilizar todo o poder de processamento deste equipamento.

Logo, em um primeiro momento, podemos ganhar paralelismo alterando o programa para que ele iniciar vários jobs de processamento na mesma máquina, onde cada um deles recebe um código de funcionário diferente para calcular, onde o número de jobs iniciados indica quantos cálculos simultâneos serão feitos. O programa principal pega a lista de códigos ded funcionários a calcular, e passa o código de cada funcionário para o primeiro job livre, até que todos estejam ocupados, e cada job que termina de calcular um funcionário pega ou recebe o código do próximo da lista.

Agora sim, com um número maior de jobs, podemos usar todo o poder de processamento desta máquina, onde aumentamos o número de jobs dedicados até um ponto antes de algum limite computacional ser atingido, como tráfego de rede entre a máquina de processamento e o Banco de Dados, ou as CPUs do equipamento não atingirem 100%.

Se mesmo assim, o uso de uma máquina com jobs não seja suficiente, pois existe por exemplo um tempo curto para o fechamento da folha, e o número de funcionários cresceu com uma fusão de empresas ou absorção do quadro de funcionários de uma empresa do grupo, a solução é usar o processamento de mais de uma máquina. Neste caso, caberia bem o uso de uma infra-estrutura de Grid. Adicionando-se em cada equipamento uma ou mais instâncias de um serviço dedicado ao cálculo dos funcionários, e criando um mecanismo client-server entre o serviço que está solicitando o processamento dos funcionários e todos os jobs disponíveis e dedicados a este cálculo, vários funcionários são processados ao mesmo tempo em equipamentos diferentes, e os resultados de cada cálculo é gravado no Banco de Dados.

Ganho esperado

Esta escalabilidade não é infinita, mais cedo ou mais tarde algum limite computacional do conjunto vai ser atingido, e não necessariamente dobrar o número de máquinas vai dobrar a sua capacidade de processamento, afinal temos que levar em conta uma fatia de tempo do mecanismo de distribuição em trafegar os códigos para o cálculo, e que cada processo pode pedir mais informações ao mesmo tempo e de funcionários diferentes para o Banco de Dados, mas mesmo assim um processo que demorava 10 horas para ser executado em 4 jobs dentro de uma máquina, ao ser divididos em 12 jobs distribuídos em 3 máquinas pode terminar a tarefa completa por exemplo em apenas 4 horas.

Dificuldades intrínsecas

Uma das primeiras dificuldades em um Grid deste tipo é determinar o número ideal jobs dedicados por máquina a serem dedicados para um processamento distribuído. Este número é empirico, e será determinado pela natureza do processamento versus capacidade de tráfego de dados e transações do ambiente computacional. Normalmente um grid busca aproveitar o poder de processamento de um conjunto de máquinas que normalmente estão executando outros processos de outras partes da aplicação, que não consomem todo o recurso computacional da máquina. Porém, um número fixo de jobs de grid executados nesta máquina, junto com outros processos em execução, podem atingir um limite computacional deste equipamento, prejudicando os outros processos desta máquina. A engine de Grid ideal precisaria ser capaz de monitorar as máquinas envolvida, atuando sobre a quantidade de jobs dedicados durante a execução, para atingir a “crista” da onda da curva de desempenho sem esgotar os recursos das máquinas envolvidas.

Determinar quais processos aderem com eficiência à execução em Grid, como eu mencionei anteriormente, é um processo um pouco mais complexo, e envolvem muitas características do processamento, e devido à sua extensão, este tema será abordado com uma lupa em um próximo post.

Deve-se também projetar uma infra-estrutura para distribuição das mensagens de processamento de forma eficiente e o mais leve possível, garantindo ao final do processo que todas as mensagens tenham sido entregues e processadas com sucesso, e em caso de falha ou ausência de retorno — como por exemplo uma queda ou término anormal de um agente de processamento — esta infra-estrutura possa permitir por exemplo o re-envio daquela requisição a outro agente, ou notificar o programa cliente desta ocorrência para que este tome a decisão sobre o que fazer.

ERP Microsiga e Grid de Processamento ADVPL

O ERP Microsiga Protheus possui algumas rotinas que utilizam um mecanismo de processamento em Grid, onde cada máquina virtual servidora do Protheus pode ser configurada como um agente de processamento, e um serviço único é configurado como o coordenador da distribuição dos agentes para processos do Grid ADVPL. Cada funcionalidade que utiliza o Grid compartilha internamente de uma camada comum de abstração “client” do Grid, onde o programador deve implementar uma função de preparação de processo dedicado e uma função de execução de requisição, e a infra-estrutura do grid garante a inicialização dos processos, distribuição de requisições e controle de execução das requisições de um processo que se utiliza do Grid. Não conheço todas as rotinas, mas sei com certeza que o cálculo de folha de pagamento do ERP possui uma opção de processamento para usar o Grid ADVPL.

Este post é a pontinha do iceberg … a cada post deste tema vamos nos aprofundar um pouco mais nas particularidades deste paradigma, que pessoalmente eu acho muito, muito interessante ! Até o próximo post, pessoal 😉

Referências

Wikipedia contributors. Distributed computing. Wikipedia, The Free Encyclopedia. November 20, 2014, 04:59
UTC. Available at: http://en.wikipedia.org/w/index.php?title=Distributed_computing&oldid=634650954.
Accessed November 27, 2014.

Wikipedia contributors. Grid computing. Wikipedia, The Free Encyclopedia. November 23, 2014, 13:50 UTC.
Available at: http://en.wikipedia.org/w/index.php?title=Grid_computing&oldid=635101070. Accessed November
27, 2014.

Wikipedia contributors. SETI@home. Wikipedia, The Free Encyclopedia. November 26, 2014, 13:42 UTC.
Available at: http://en.wikipedia.org/w/index.php?title=SETI@home&oldid=635510528. Accessed November 27,
2014.