Processamento paralelo é uma técnica que vem sendo bastante utilizada na solução de problemas que envolvem um alto custo computacional. Estes problemas, em geral, envolvem tarefas grandes e complexas que, ao serem executadas por um único processador, demandam um tempo computacional alto. Para obtenção de resultados mais rápidos e, em alguns casos, até para viabilizar a solução desses problemas, um dos caminhos é dividir essas grandes tarefas em tarefas pequenas, que serão distribuídas em vários processadores para serem executadas simultaneamente. Com o advento dos clusters e o baixo custo dos computadores pessoais, o processamento paralelo ressurge como uma alternativa bastante viável nesses casos. A simulação computacional de problemas físicos passa em geral pela solução de grandes sistemas de equações lineares. Esta etapa de solução de sistemas de equações envolve um alto custo computacional em função do tamanho dos sistemas de equações envolvidos, sendo quase sempre a etapa mais crítica nas aplicações. Dentro deste contexto, este trabalho apresenta uma implementação computacional de um método numérico clássico, o Método de Gauss-Jacobi, para solução de sistemas de equações lineares.  São apresentados neste trabalho a metodologia utilizada e os resultados obtidos com o programa desenvolvido, destacando-se os ganhos obtidos com a utilização do processamento em paralelo.

Existem dois tipos de métodos para solução de sistemas de equações lineares: os métodos diretos e os métodos iterativos. Em geral os métodos iterativos são mais eficientes e, por isso, mais utilizados. Para esse trabalho, foi escolhido o método iterativo de Gauss-Jacobi em função da sua simplicidade e, sobretudo, em função das suas características que são bastante favoráveis à programação em paralelo. Dentre os diferentes tipos de paralelismo e técnicas de programação em paralelo existentes, utilizou-se, neste trabalho, o tipo de paralelismo que utiliza memória distribuída e a técnica de programação master/slave.  Esta técnica se baseia no mecanismo de troca de mensagens entre os processos e, para sua implementação, foi utilizada a biblioteca MPI (Message Passing Interface). O programa foi desenvolvido em linguagem C, sendo geradas versões para as plataformas Windows e Linux. Com relação ao hardware, utilizou-se um cluster que dispõe de sessenta computadores, com a seguinte configuração: Pentium IV 2.4Ghz com 512MB. Foram selecionados alguns casos para a avaliação de desempenho do programa. Para esta avaliação as métricas utilizadas foram: tempo de execução, speedup e eficiência.  O speedup é definido como a razão entre o tempo gasto para solucionar um problema com um único processador e o tempo gasto para solucionar o mesmo problema com p processadores idênticos e a eficiência é definida como a razão entre o speedup e o numero de processadores(p).

O custo computacional envolvido na solução de sistemas de equações lineares cresce à medida que tomamos sistemas com um número maior de equações. Em função disto, são apresentados neste trabalho os resultados obtidos para sistemas de equações lineares com 500, 1000, 2000, 3000, 5000 e 7000 equações. São apresentados, para cada caso, uma avaliação comparativa entre o tempo gasto na solução de cada sistema com a utilização de apenas um processador e tempo gasto na solução obtida com o aumento gradativo do número de processadores. Para todos os sistemas, quando se aumenta o número de processos, o valor do speedup cresce até um valor máximo e depois torna a decrescer, porém de uma forma mais lenta. À medida que aumentamos o número de processos, diminuímos o tamanho da tarefa que cada processo irá realizar e aumentamos o tráfego na rede, já que mais processos irão participar dessa comunicação. Dessa forma, há um momento em que o tempo ganho com o processamento paralelo não é suficiente para compensar o tempo gasto com a transmissão de dados entre os processos.  A qualidade do algoritmo paralelo também foi analisada através da métrica eficiência.  A eficiência do processamento paralelo cresce à medida que o número de equações do sistema torna-se maior, o que era de se esperar, já que o speedup também cresce no mesmo sentido. São apresentados neste trabalho gráficos e tabelas que ilustram as vantagens de se utilizar o processamento paralelo na solução de sistemas de equações.

Conforme observado nos resultados, o tempo gasto na solução de sistemas lineares com um número muito elevado de equações pode ser reduzido de forma bastante significativa com o uso da computação paralela. Porém, existem algumas variáveis que comprometem o processamento paralelo, como por exemplo, o tráfego de informações na rede que interliga os computadores. A tarefa a ser executada por cada processo deve justificar a sua implementação em paralelo para que o tempo de troca de informações entre os processos não seja maior do que a execução da tarefa pelo processo. Durante os testes do programa utilizando sistemas de equações lineares de vários tamanhos, observou-se que à medida que o número de processos aumenta, em geral ocorre uma redução no tempo de execução do programa. Entretanto, essa redução é limitada, pois se chega a um estágio em que o número de processadores não é compatível com o tamanho do sistema, ou seja, o tempo gasto por cada processador durante a execução do programa não compensa o tempo de comunicação na rede. Ou seja, o tempo perdido no envio e recebimento de dados entre os processadores não é compensado pelo tempo ganho com  a divisão das tarefas entre os mesmos.