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