Paralelização do Solver Intervalar Linear System Solver (LSS

Paralelização do Solver Intervalar Linear System Solver (LSS) Andriele Busatto do Carmo PPGCC – PUCRS Porto Alegre – RS – Brasil [email protected]

Carlos Amaral Hölbig Curso de Ciência da Computação – UPF Passo Fundo – RS – Brasil [email protected]

Resumo Este trabalho apresenta a paralelização do solver intervalar Linear System Solver (LSS). O solver LSS foi implementado utilizando a biblioteca científica CXSC, destina-se a resolução de sistemas lineares com matrizes densas e baseia-se na implementação de métodos numéricos computacionais, que verificam automaticamente o resultado gerado nas computações realizadas. Para esta paralelização foi realizado um estudo sobre o funcionamento e as rotinas do solver LSS em sua versão seqüencial. Com base neste estudo pôde-se identificar alternativas de paralelização para este solver. Com a implementação destas alternativas de paralelização, testes de exatidão e de desempenho entre a versão paralela e a seqüencial foram realizados com o objetivo de validar o trabalho desenvolvido.

1. Introdução A resolução de sistemas lineares do tipo Ax = b é um dos assuntos mais abordados em Análise Numérica. A importância dada a estes sistemas devese às suas amplas aplicações em diversas áreas do conhecimento humano como, por exemplo, na construção de curvas e superfícies por pontos especificados, desenvolvimento de redes elétricas, programação linear geométrica, teoria dos grafos, economia, computação gráfica, tomografia computadorizada, fractais, criptografia e genética. Tais sistemas apresentam importância especial, pois podem ser resolvidos pelo Linear System Solver (LSS),

Marcelo Trindade Rebonatto Curso de Ciência da Computação – UPF Passo Fundo – RS – Brasil [email protected]

objeto de paralelização deste trabalho, sendo este implementado através da utilização da biblioteca intervalar e de alta exatidão C-XSC [3,7]. O paradigma da computação verificada, que é disponibilizado através do uso da biblioteca C-XSC e está presente no solver LSS, tem como objetivo principal dar possibilidades ao computador para que este possa identificar, de maneira rápida, se o cálculo realizado está correto ou não e se este cálculo serve para solucionar o problema em questão. Neste caso, é possível que o computador faça uma escolha entre usar um algoritmo alternativo ou repetir o mesmo processo utilizando maior precisão [1,9].

2. Solver Verificado para Resolução de Sistemas de Equações Lineares Densos O objetivo do solver LSS é de verificar a existência de uma solução de sistemas lineares com matrizes densas e computá-la para cada um dos seguintes problemas: sistema de equações lineares quadrado (m × n, com m = n), sobre-determinado (m × n, com m > n), sub-determinado (m × n, com m < n), cálculo da inversa da matriz de coeficientes do sistema de equações lineares quadrado e das pseudo-inversas da matriz de coeficientes do sistema de equações sobredeterminado e sub-determinado. Todos os algoritmos implementados foram trabalhados para os quatro tipos básicos de dados numéricos do C-XSC: real, interval, complex e complex interval. Assume-se que o coeficiente da matriz A em Ax = b é denso, isto é, em um programa C-XSC, usa-se uma matriz quadrada do tipo rmatrix,

imatrix, cmatrix ou cimatrix para armazenar A e não considera-se nenhuma estrutura especial dos elementos de A. Com relação à aplicabilidade dos algoritmos, na implementação em C-XSC, há a possibilidade dos dados da entrada apresentarem números grandes ou a inversa de A ou a solução dela também conter números grandes, podendo, neste caso, ocorrer um overflow, ocasionando a parada do algoritmo. Porém, nas aplicações práticas, isso não tem sido observado. Isto também pode ser evitado pela inclusão de manipulação de exceções em pontoflutuante oferecidas pelo C-XSC conforme a aritmética de ponto-flutuante da IEEE. Detalhes sobre o solver LSS poderão ser encontrados em [4,8].

4. Paralelização do Solver LSS A paralelização do Solver LSS apresenta-se embasada no estudo detalhado do funcionamento de sua versão seqüencial. Através deste estudo foi possível representar o fluxo do funcionamento do Solver através da construção de um fluxograma representado na Figura 1.

3. Ambiente Computacional utilizado Para a realização deste trabalho foi utilizado o cluster Colorado pertencente ao Grupo de Pesquisa de Computação Paralela e Sistemas Distribuídos (ComPaDi) da Universidade de Passo Fundo (UPF). Ele composto por seis computadores pessoais, com sistema operacional Linux e rede de intercomunicação Ethernet 100 Megabits. O cluster apresenta a seguinte estrutura: servidor de acesso ao cluster (front-end): Processador Intel Celeron 1.7 GHz, 128 Mb de memória RAM e HD de 40 Gb; um nodo com processador Pentium III 800 MHz, 128 Mb de memória RAM e HD de 40 Gb; e quatro nodos com processadores AMD Atlhon 1.16 GHz, 128 Mb de memória RAM e HD de 40 Gb. Utilizou-se ainda para o desenvolvimento da versão paralela do solver LSS a biblioteca de troca de mensagens MPI, a linguagem de programação C++ e ainda a biblioteca científica C-XSC. Sobre a biblioteca C-XSC é importante destacar que ela deve ser utilizada, em um ambiente paralelo, como uma ferramenta de apoio ao cálculo de problemas com alta exatidão e não como a ferramenta computacional principal, ou seja, deve-se resolver um determinado problema utilizando ferramentas computacionais tradicionais e, caso tenha-se problemas com a exatidão do resultado, verifica-se no problema que está sendo trabalhado quais são as áreas ou rotinas mais cruciais à exatidão e, nessas áreas, a biblioteca C-XSC deverá ser utilizada procurando obter um resultado mais exato e confiável. No restante do problema sugere-se o uso de ferramentas tradicionais com o objetivo de não ser ter uma grande perda de desempenho na solução do problema [6].

Figura 1. Funcionamento do Solver LSS O solver LSS possui diversas funções responsáveis pela realização dos cálculos matemáticos referentes à solução que deseja-se encontrar. Dentre estas funções encontra-se a LSS (global), responsável por receber os dados de entrada e distribuir às demais funções de acordo com o tipo de problema que comporta. Cada função é responsável por resolver o sistema de acordo com o seu papel dentro do solver. No caso da função SQUARE_LSS, são tratados sistemas com coeficientes quadrados, fazendo então uma chamada à função LSS (local). Já a função OVER_LSS trata sistemas lineares sobre-determinados, alocando as variáveis BIG_A, BIG_B e BIG_Y para o aumento dos problemas e inicializando BIG_A e BIG_B adequadamente. Da mesma forma a função UNDER_LSS soluciona sistemas lineares sub-determinados. Como mencionado anteriormente, a função responsável pela resolução de sistemas lineares quadrados realiza uma chamada à função LSS (local). Esta função implementa um algoritmo para sistemas lineares quadrados Ax = b, e tenta primeiramente calcular a aproximação da solução do sistema em tamanho simples através de um teste identificado no código como o trecho USE_SINGLE_R. Caso não haja sucesso, ela calcula uma aproximação da solução em tamanho duplo fazendo um teste referente ao trecho do código denominado USE_DOUBLE_R. Esta é a função central do módulo, apresentando como

parâmetros de entrada A e b. A função MINV calcula inclusões para matrizes inversas, pois trabalha com os sistemas todos adaptados para sistemas quadrados, independentemente de serem inicialmente sobre ou sub-determinados. Inicialmente deparou-se com possibilidades diversas de paralelização. Uma alternativa seria de paralelizar as funções do solver, onde cada função executaria seu programa em paralelo com as demais funções. Neste caso, teve-se a idéia de que os benefícios seriam no sentido de poder agilizar a solução de uma dada entrada chegando-se ao seu final com as soluções calculadas em conjunto. Outra alternativa seria paralelizar os cálculos internos realizados pelas funções, permitindo que os métodos utilizados por elas fossem implementados paralelamente, podendo desta forma chegar ao seu resultado com maior eficiência. Observou-se ainda como alternativa, paralelizar os métodos internos das funções do solver juntamente com a paralelização das funções, fazendo com que estas executassem seus cálculos paralelamente. Foi possível, então, detectar, através de testes realizados no solver seqüencial, que a necessidade de paralelização dava-se nos trechos do código referentes aos produtos escalares calculados dentro da função LSS (local), visto que são os principais responsáveis pelo tempo de execução do solver. Com a escolha da paralelização dos produtos escalares foram criadas mais seis bibliotecas, agora paralelas, para resolver problemas referentes a estes cálculos bastante utilizados no solver LSS. A primeira biblioteca chama-se CalculaProdutoEscalarParalelo e é responsável pelo cálculo com arredondamento do produto escalar passado como parâmetro através da função LSS (local). Assim como a função mencionada anteriormente, criou-se a função ProdutoEscalarParaleloSemArredondar, com a diferença de que retorna para a função LSS (local) o resultado do cálculo do produto escalar sem o arredondamento final (em alta exatidão – tipo de dado dotprecision). Estas duas bibliotecas trabalham com vetores e matrizes de dados do tipo real apenas. Outras quatro bibliotecas foram criadas, mas para que dados do tipo interval (intervalo de reais) fossem utilizados nos cálculos dos produtos escalares. A primeira delas chama-se IntervalarCalculaProdutoEscalarParalelo, que retorna para a função LSS (local) o cálculo do produto escalar com o arredondamento final. Da mesma forma trabalha a biblioteca IIntervalarCalculaProdutoEscalarParalelo,

apresentando uma única diferença, no que tange aos parâmetros recebidos da função LSS (local), visto que ao invés de o terceiro parâmetro ser um dado do tipo rvector, caracteriza-se por ser um dado do tipo ivector. Já a biblioteca IntervalarProdutoEscalarSemArredondar, resolve o produto escalar retornando o valor sem o arredondamento final (em alta exatidão – tipo de dado idotprecision). E, de modo semelhante à esta biblioteca trabalha a biblioteca IIntervalarProdutoEscalarSemArredondar, apresentando como diferença o tipo do dado passado como parâmetro na terceira posição, sendo ivector ao invés de rvector. Estas seis bibliotecas utilizam funções do MPI para o cálculo do produto escalar. A função utilizada no código para distribuir aos processos existentes as matrizes e os vetores foi a função MPI_SEND. E, para receber as matrizes e os vetores, a função MPI_RECEIVE. Optou-se pela utilização destas funções por poderem trabalhar com estes tipos de dados (vetores e matrizes), atendendo ao problema existente, necessitando apenas de algumas adaptações para que a integração entre a biblioteca MPI e a biblioteca C-XSC seja realizada de forma satisfatória, resolvendo o problema, conforme descrito em [2,6].

6. Testes Realizados Para a realização dos testes foram utilizados sistemas de ordem 64, 128 e 256, tanto na versão seqüencial quanto na versão paralela do solver. Os resultados obtidos estão utilizando a notação de segundos e para cada tipo diferente de teste, foram realizadas 10 repetições. O gráfico representado pela Figura 2, ilustra os testes realizados. Para a versão paralela do solver foram realizados testes com execuções em 2 e 4 processadores, com o intuito de verificar possíveis alterações no desempenho do programa. A figura 3 apresenta o speedup alcançado na paralelização. Além disso, conforme apresentado na tabela 1, foram realizados alguns testes visando mostrar a qualidade numérica obtida com a utilização do solver LSS. Nestes testes foram utilizadas matrizes de Hilbert (matrizes mal-condicionadas) de ordem 10. Para n = 10 tem-se lcm10 = 232792560. Para o sistema (lcm10H10)x = (lcm10e1) o programa (seqüencial e paralelo) calculou o resultado apresentado na Tabela 1, que é a solução exata para esse sistema malcondicionado. Maiores detalhes sobre estes testes poderão ser obtidos em [5].

Tempo de Execução 1000

Tempo (em segundos)

281,118821 226,195835 100

47,799680

104,788894

38,758424 10,626928 10

12,312183

8,606598

1,612774 1 64

128

256

Ordem do Sistema seq

np=2

de vista de exatidão os resultados obtidos foram os mesmos que na versão seqüencial) por causa do uso das técnicas da Computação Verificada e do modo como a paralelização nesta versão foi realizada, o que justificaria uma pesquisa que visasse a otimização da biblioteca C-XSC e, principalmente, um estudo sobre novas formas de paralelização para este solver como, por exemplo, a paralelização do cálculo da matriz inversa e das rotinas em precisão simples e dupla ao invés da paralelização que foi realizada baseada nos produtos escalares ótimos encontrados no solver.

np=4

Figura 2. Tempos de execução do Solver LSS Seqüencial e Paralelo

8. Referências [1] ALEFELD, G.; HERZBERGER, J. Introduction to Interval Computations. New York: Academic Press, 1983. [2] GRIMMER, M.; An MPI Extension for the Use of C– XSC in Parallel Environments. BUGHW-WRSWT 2005/3, 2005, Wuppertal. Article… Wuppertal: [s.n.], 2005. [3] HOFSCHUSTER, W.; KRÄMER, W. C-XSC 2.0: A C++ Class Library for Extended Scientific Computing. BUGHW-WRSWT 2001/1, 2001, Wuppertal. Article… Wuppertal: [s.n.], 2001.

Figura 3. Speedup obtido com o solver LSS Tabela 1. Resultados obtidos com o solver LSS para sistema com matriz de Hilbert de ordem 10

[4] HÖLBIG, C., KRÄMER, W., Selfverifing Solvers for Dense Systems of Linear Equations Realized in C–XSC, Wuppertal, Germany: BUGH, Universität Wuppertal, 2003. (Preprint BUGHW-WRSWT 2003/1). [5] HÖLBIG, C. A., MORANDI JÚNIOR, P. S., ALCALDE, B. F. K., DIVERIO, T. A., CLAUDIO, D. M., Solving Linear Systems on Cluster Computers with High Accuracy, Lyngby, Denmark: Department of Informatics and Mathematical Modelling of the Technical University of Denmark, 2005, p.89–96. (IMM-Technical report-2005-09). [6] HÖLBIG, C.A., CLAUDIO, D.M., DIVERIO, T.A., Use of C-XSC Interval Library on Cluster Computers, In: IV International Conference on Numerical Analysis and Applied Mathematics, 2006. ICNAAM – 2006 Extended Abstracts, Wiley-VCH Verlag, Weinheim, 2006, v.1, pp.151-154.

7. Conclusões Através do estudo pôde-se constatar que a verificação automática dos resultados obtida através da computação verificada é de suma importância para a área de Computação Científica, uma vez que permite que a cada operação em ponto-flutuante o erro seja estimado e avaliado. Percebeu-se através dos testes realizados que o solver LSS Paralelo, não apresentou, ainda, um bom desempenho computacional (do ponto

[7] KLATTE, R. et al. C-XSC: A C++ Class Library for Extended Scientific Computing. 1. ed. Karlsruhe: SpringerVerlag, 1993. [8] KRÄMER, W., KULISCH, U., LOHNER, R., Numerical Toolbox for Verified Computing II: Advanced Numerical Problems, Springer–Verlag, Berlin, 1996. [9] KULISCH, U., MIRANKER, W., A New Approach to Scientific Computation, Academic Press, New York, 1983.