Encontro 4 - Otimização de Executáveis com gcc

Neste encontro abordamos as opções de otimização de executáveis oferecidas pelo compilador gcc.

Encontro 3 - Mandelbrot com parallel for

Roteiro do Encontro

1. Estudo do problema do Mandelbrot.
2. Estudo de caso para a aplicação paralela.
3. Paralelização do código com parallel for.

• Estudo do problema do Mandelbrot.
  Conjunto de Mandelbrot é um fractal, definido a partir do seguinte algoritmo sequencial.
  Onde para cada pixel da imagem irá calcular se ele pertence ou não ao conjunto de mandelbrot, se ele pertence o pixel será pintado de preto, caso contrario será branco.
  A imagem é gerada com o opencv, então para executar o algoritmo ele é necessario.
  Exemplo de imagem gerada a partir do algoritmo:
  

  

  Clique para ampliar. (Fonte: wikipédia)

• Estudo de caso para a aplicação paralela.
  Já com nosso algoritmo sequencial pronto passamos a analisar as possibilidades de paralelização, onde detectamos as seguintes características em nosso código:
• O calculo que define se um ponto pertence ou não ao conjunto é completamente independente, ou seja, para calcular um ponto não precisa esperar o resultado de outro ponto.
• Temos dois laços for aninhados. Nesses laços que estará percorrendo todos os pontos da imagem, como o calculo de todos os pontos não apresentam dependências podemos criar uma distribuição de pontos para cada thread da forma que acharmos adequada.
• Surgiram várias idéias de distribuição do trabalho, entre elas: uma linha por thread, um bloco por thread, um ponto por thread.
• Paralelização do código com parallel for.
  Decidimos então utilizar a diretiva parallel for do openmp para paralelizar, definimos a área paralela do código a área correspondente aos laços for.

Encontro 2 - Multiplicação de Matrizes

Roteiro do Encontro

• Implementação de um algoritmo para multiplicar matrizes;
• Paralelização do algoritmo;
• Coleta de dados;

Implementação do Algoritmo

     Para multiplicar as matrizes A e B, devemos verificar se o número de colunas da matriz A é igual ao número de linhas da matriz B. Este requisito é básico e não deve ser violado.

Implementamos em C o seguinte algoritmo para multiplicação de matrizes:

programa multiplica_matrizes_sequencial;
   matriz mat1, mat2, mat3;
   inteiro linha, coluna, i, acumula;
   "leia mat1";
   "leia mat2";
   "verifique se numero de colunas de mat1 é igual numero de linhas de mat2";
   para linha de 1 até "numero de linhas de mat1" faça
     para coluna de 1 até "numero de colunas de mat2" faça
       acumula=0;
       para i de 1 até "numero de colunas de mat1" faça
         acumula=acumula+mat1[linha][i]*mat2[i][coluna];
       fimpara;
       mat3[linha][coluna]=acumula;
     fimpara;
   fimpara;
   imprima mat3;
fim programa;

Paralelização do Algoritmo

Paralelizamos o primeiro laço com openMP, usando "#pragma omp for".

Coleta de Dados

Os testes foram executados no SO Ubuntu (kernel 3.2.0-24) rodando sob um computador com processador Intel Core i7 2630QM, 2.0~2.9 GHz, com 8Gb memória DDR3.

Matriz	Tempo Sequencial	Tempo 2 Threads	Tempo 4 Threads
1000x1000	15,416 s	7,554 s	4,12 s
2000x2000	2 min 14,89 s	1 min 4,846 s	36,115 s

Encontro 1 - Definição do Dia e Hora dos Encontros

Esta data marca o inicio das atividades do Grupo de Estudos para Maratonas de Programação Paralela da Unipampa.
Neste dia ficou definido que os encontros ocorrerão todas as sextas-feiras das 13:30 - 16:30 horas na sala 301 da Unipampa.
Como primeira atividade aos participantes, foi realizada uma breve introdução sobre a programação em OpenMP, enfocando alguns apectos básicos da API.

Participaram deste encontro: Arthur Lorenzon, Augusto Vargas, Henrique Gressler, Márcia Cera e Uillian Ludwig.