Paralelização  do metodo de Gauss - Sidel

Alcides de Melo Sena, Erasmo Patrocinio Neto

Universidade Federal Rural de Pernambuco, CEP: 52171-900, Dois Irmãos, Recife – PE, Brasil.

alcidessena@hotmail.com, erasmo.patrocinio@hotmail.com

 

 

Abstract. The objective of this work is a boarding on the paralelization of themethod of Gauss - Sidel. In which we will first go to show its sequential algorithm, commenting step by step, and after that the parallel algorithm.

Palavras-chave: hypercube, method of Gauss-Siedel, pivot.

 

Resumo: O objetivo deste trabalho é uma abordagem sobre a paralelização do método de Gauss –Sidel. No qual iremos primeiramente mostrar o seu algoritmo seqüencial, comentando passo a passo, e em seguida o algoritmo paralelo.

Palavras-chave: hipercubo, método de Gauss-Siedel, pivô.

 

Considerações Gerais:

              Este trabalho faz parte da disciplina de Programação Paralela e Distribuída (PPD) da universidade Federal Rural de Pernambuco.  Tivemos como instrutor deste curso o professor Jones Oliveira de Albuquerque. Nós alunos do curso de licenciatura em computação tivemos o prazer de desenvolver este trabalho , que além de contribuir para o nosso conhecimento será material  de estudos  e de sugestões para futuros trabalhos.

Site da disciplina: http://www.cin.ufpe.br/~joa/menu_options/school/cursos/ppd/

 

1. Introdução

            O poder de processamento de uma única CPU cresceu, apesar da grande capacidade encontrada em processadores atuais, existem problemas cuja complexidade ainda é um fator proibitivo em sua solução. Alguns desses problemas de grande complexidade, porém, possuem a vantagem de poderem ser fracionados, a fim de serem paralelizados. Isso permite que pequenas partes do problema sejam processadas em CPU’s distintas e o resultado de cada um desses processamentos pode ser, posteriormente, integrado por uma central coordenadora para produzir o resultado integral do problema. A partir disso, utilizaremos como analise o algoritmo de eliminação de Gauss-Sidel para que, no processamento de dados, obter resultados de maneira rápida e eficiente.

2. Programação Paralela e Distribuida

 

            Programação paralela: consiste em executar simultaneamente várias partes de uma mesma aplicação, tornou-se possível a partir do desenvolvimento de sistemas operacionais multi tarefa.As aplicações são executadas paralelamente em um mesmo processador, em uma máquina multi-processada ou em um grupo de máquinas interligadas que se comporta como uma só máquina.

            Programação distribuída: Consiste em executar operações cooperantes  em maquinas diferentes, tornou-se possível a partir da popularização das redes de computadores. As aplicações são executadas paralelamente  em redes locais , internet os são fortemente acoplados , compartilham hardware ou se comunicam atravéz de um barramento de alta velocidade.

 

3. Método de Gauss-Sidel

 

Objetivo do Método: Eliminar os elementos aij de forma a obter um sistema equivalente com uma matriz triangular superior. Depois bastará usar substituições sucessivas para chegarmos à solução pretendida.

Seja S um sistema de equações lineares e considere a matriz ampliada de S.

1º Passo – Localizar a coluna mais à esquerda cujas entradas não sejam todas nulas.

2º Passo – Se necessário, trocar a 1ª linha com outra linha da matriz, de modo a que a 1ª entrada da coluna encontrada no 1º Passo seja não nula.

3º Passo (facultativo) – Se a 1ª entrada da coluna encontrada no 1º Passo for diferente de um, multiplicar a 1ª linha pelo inverso dessa entrada.

4º Passo – Somar múltiplos da 1ª linha às restantes linhas de modo a anular, em cada uma delas, a entrada pertencente à coluna encontrada no 1º Passo.

5º Passo –Ignorar a 1ª linha da matriz que resultou do passo anterior, e repetir os quatro passos anteriores para a matriz constituída pelas restantes linhas.

Este procedimento termina quando, entre as linhas ainda não ignoradas, só existir uma linha não nula.

Seja S um sistema de equações lineares e considere a matriz ampliada [A|B] de S.

Depois de aplicar o método de eliminação de Gauss à matriz [A|B], proceder do seguinte modo:

6º Passo – Se alguma das linhas da matriz obtida tiver pivot diferente de um, multiplicá-la pelo inverso do seu pivot.

7º Passo – Começando com a última linha não nula, ir somando múltiplos de cada linha não nula às linhas que lhe são anteriores (i.e. colocadas acima dela), de modo a anular todas as entradas que estão acima do seu pivot.

 

4. Algotimo seqüencial

Veremos logo o algoritmo seqüencial, para observarmos realmente de que maneira o   processador  esta trabalhando. Ao longo do algoritmo seqüencial iremos fazer observações e ao final teremos um exemplo pratico resolvido passo a passo.

 

 

 

 

 

Global n {Tamanho do sistema linear}

            a[1..n][1..n] {Coeficientes da equação}

            b [1..n] { Valores dos resultados de cada equação}

            marked [1..n] {Indica que fila esta o pivô}

            pivot [1..n] {Indica  a posição do elemento pivô}

            picked {O pivô escolhido}

           

Texto explicativo 3 (ênfase): Consideramos inicialmente que nenhuma linha é pivô. Cria-se então um vetor para cada linha e atribui-se zero, ou seja, quer dizer que a linha não está marcada.
 


begin

     for i ¬1 to n do

       marked [ I ]   ¬ 0

Texto explicativo 1 (sem bordas): Esta variável tmp faz a função de fator multiplicador.Texto explicativo 3 (ênfase): É neste laço que é escolhido o elemento com o maior valor em modulo para ser o foco da eliminação. Procura-se na coluna i o elemento de maior valor absoluto e que não esteja marcado, ou seja, aquele cuja linha não é pivô.      endfor

     for  i  ¬ 1 to n-1 do

       tmp   ¬ 0

        for  j  ¬  i to n do

           if  marked[ j ] = 0 and    a[j][i]  > tmp  then

            tmp   ¬    a[j][i]

                        picked  ¬ j

Texto explicativo 3 (ênfase): Marcá-se a linha para identificar que esta contém o elemento pivô, o vetor estará associado a linha e conterá o valor 1 quando for marcada.            endif

      endfor

Texto explicativo 1 (sem bordas): Indica a posição do elemento pivô na linha marcada.
 


marked [picked] ¬ 1

pivot [picked]  ¬ I

Texto explicativo 3 (ênfase): Neste FOR que é feito o trabalho de eliminação, proposto por Gauss. Neste laço como podemos observar as teorias da eliminação nos trechos 1.1 (determinação do fator multiplicador) e no 1.2 (trabalhando os elementos para a eliminação).        for j ¬ 1 to n do

              if marked[ j ] = 0 then

                 tmp ¬  a[ j ] [ I ]/a[ picked] [k]  x tmp 1.1

              for k ¬   I + 1 to n do

                      a[ j ] [ k ] - a[ picked] [k]  x tmp 1.2              

                 endfor

Texto explicativo 3 (ênfase): Foi encontrado um erro, durante a analise deste código, no trecho 1.3. O erro acontece porque o valor de K ao sair do loop logo acima é sempre 3, isto acarreta um bug. Pois, ele vai estar trabalhando duas linhas no matriz A e na matriz B não trabalhar as mesmas linhas.                b[ j ]  ¬  b[ j ] – b[ k ] x tmp 1.3

          endif

        endfor

 endfor

 

 

 


       for I ¬ 1 to n do

          if marked [ I ] = 0 then

            pivot [ I ]  ¬ N

            break

          endif

      endfor

 

end

Passo a Passo

Condições iniciais:

marked [1]=0, marked [2]=0 e marked [3]=0;

pivot [1]=? , pivot [1]=? e  pivot[3]=? ;

picked= ?

 

Sistema linear:

 

     X + 2y – 3z=5                      Matriz  A                   Matriz B

 


    -2x +y – 4z= -2                                                     1     2    -3                   5

                                                                                -2     1    -4                 -2

   x –3y + 5z = -1                                                      1    -3      5                 -1

           

 

Para i=1;        

tmp =0

                       

               J=1

              J=2

               J=3

            tmp=1

            tmp=2

            tmp=2

            Picked= 1

            Picked= 2

            Picked= 2

marked [ 2 ]= 1

pivot [ 2 ] = 1

 

J=1

tmp=1/-2 =-1/2

               k= 2

K=3

A12 = 2 – (1x –1/2) = 5/2

A13 = -3 – (-4 X –1/2) = -5

B1 = 5 – (-2 X –1/2)=4

           

J=2

Não houve interações

 

J=3

tmp=1/-2 =-1/2

               k= 2

K=3

A32 = -3 – ( 1x –1/2) = -5/2

A33 = 5- (-4 x  -1/2 )= 3

B3 = -1- (-2 X –1/2)= -2

 

Após a primeira interação de eliminações o resultdo parcial:

Matriz  A                   Matriz B

 

      0     5/2   -5                      4   

    -2      1      -4                    -2 

     0     -5/2    3                    -2

 

 

Lembrando dos valores já computados:

marked [1]=0, marked [2]=1 e marked [3]=0;

pivot [1]=? , pivot [2]=1 e  pivot[3]=? ;

picked= 2;

 

Para i=2;        

tmp=0

 

J=1

              J=2

               J=3

Não houve interação

Não houve interação

            tmp=5/2

 

 

            Picked= 3

 

marked [3] = 1

pivot [3] = 2

 

J=1

tmp= (5/2)/(-5/2) =-1

k=3

A13 = -5 – (3 x  -1) = -2

B1 = 4 – (-2 X –1)=2

 

J=2 e j=3

Não houve interações

O resultado:

Matriz  A                   Matriz B

 

      0     0   -2                        2   

    -2     1    -4                       -2 

     0  -5/2    3                       -2

 

Com este resultado, o trabalho resume-se a substituir os valores na equação e encontrar o resultado de cada variável.

 

 

5. Algoritmo Paralelo

            Veremos agora a paralelização do algoritmo do método de Gauss-Sidel utilizando o método do modelo do hipercubo. O nível de abstração aumenta, pois é preciso imaginar que vários processadores estejam executando o mesmo algoritmo ao mesmo instante. Para este algoritmo, a principio temos que considerar que cada processador já possui as linhas pré-definidas, ou seja, n/p. E que n seja múltiplo de p.

 

Global n {Tamanho do sistema linear}

            a[1..n/p][1..n] {Coeficientes da equação}

            b [1..n/p] { Valores dos resultados de cada equação}

            marked [1..n/p] {Indica que fila esta o pivô}

            pivot [1..n/p] { ,;.,;.,;,.;,.,;.,;.,;,.;,.,;.,;.}

            picked {O pivô escolhido}

            magnitude { valor do pivô }

            winner  { Processador que controla a fila pivo }

            i,j

 

Texto explicativo 2 (ênfase): Inicialmente distribui-se para todos processadores o mesmo algoritmo para que possa ser executado em paralelo. begin

     for all Pid, where  p  ³  id  ³ 1 do

 

           

Texto explicativo 2 (ênfase): Considera-se a priori que o número de linhas n é divido pelo número de processadores p ou seja n é múltiplo de p. Cada linha inicialmente é associada a um vetor e o mesmo recebe zero como seu valor Inicial . não existe ainda linha pivô.      for i ¬1 to n/p do

       marked [ I ]   ¬ 0

     endfor

Texto explicativo 1 (sem bordas): A magnitude é uma variável que guarda o maior valor escolhido na coluna. 


 for I ¬ 1 to n – 1 do

Texto explicativo 1 (sem bordas): Cada processador contém n/p linhas             magnitude ¬ 0

        for  j  ¬  i to n/p  do

           if  marked[ j ] = 0 and   ú a[j][i] ú   > magnitude  then

Texto explicativo 2 (ênfase): Neste laço For cada processador encontra o seu campeão o qual será candidato a linha pivô disputando com os outros processadores.                   magnitude  ¬ ú a[j][i]ú

                        picked  ¬ jú

           endif

      endfor

 

winner ¬ id 

Texto explicativo 3 (ênfase): Este procedimento é utilizado para encontrar o verdadeiro campeão, ou seja, é realizado um torneio entre os processadores do qual sairá o resultado de quem contém o maior elemento.
 


MAX. TOURNAMENT  (id, magnitude, winner)

 

        If  id  = winner then marked [picked] ¬ 1 pivot  [picked] ¬ I

                for j ¬ I + 1 to n do

                     tmp.vector[j] ¬ a [picked] [j]

Texto explicativo 2 (ênfase): Este laço só é executado pelo o processador campeão, ou seja, que esteja com a linha pivô do sistema linear.                   tmp.vector[n + 1] ¬ b [picked]

               enfor

        endif

 

HYPERCUBE.BROADCAST (ID, WINNER, TEM.VECTOR [(I+1).. (n+1)] )

        for  j  ¬ 1 to n/p do

Texto explicativo 2 (ênfase): Este procedimento faz com que o processador campeão envie para os outros processadores os elementos que estão contidos na linha pivô, via rede (broadcast).                if  marked [j] = 0 then

                   tmp ¬  a[j][I]/tmp.vector[I]

                 for k ¬ I +1 to n do

                      a[j][k] ¬ a[j][k] – tmp.vector[k] x tmp

                   endfor

Texto explicativo 3 (ênfase): Os processadores , inclusive o campeão começam a fazer a eliminação de Gauss no sistema linear.             b[j] ¬ b[j] – tmp.vector[n+1] x tmp

               endif

        endfor  

  endfor

 

 

 

 

       for I ¬ 1 to n/p do

          if marked [ I ] = 0 then

            pivot [ I ]  ¬ n

            break

          endif

      endfor

  

end

 

 

MAX.TOURNAMENT ( id, value, winner)

   Referencia  id, value, winner

 

 

Texto explicativo 2 (ênfase): Cada processador calcula no hipercubo, através do ou exclusivo quais os processadores são seus parceiros de comunicação. Encontrado o parceiro este envia seus dados via rede (nº identificação e o valor). É realizada a comparação dos valores e o verdadeiro campeão é encontrado. begin

    for  i ¬ to log p –1 do

      partner ¬ id Ä  2i

        [partner]tmp.value Ü value

      [partner]tmp.winner  Ü winner

       if  tmp.value > value then

            value ¬ tmp.value

            winner ¬ tmp.winner

       endif

     endfor

end

 

 

  Com o método do hipercubo, em uma rede local ou internet, cada processador sabe quem é o seu parceiro. Utilizando o xor exclusive .

 

 

 

 

 

 

6. References

 



 

 

Bibliografia Complementar