Computação Paralela - Atividade 14

Leia com atenção as instruções abaixo.

Valor: 2,0 pontos na 3ª Nota.

Data da Entrega Limite: 16/07/2022

Formato de Entrega:

1. Arquivos atv14_questao01.c ou atv14_questao01.cpp e atv14_questao01_resultados.txt.
2. Arquivos atv14_questao02_serial.c, atv14_questao02_linemajor.c e atv14_questao_02_resultados.txt

A atividade é individual.

Nesta atividade, vamos tratar de um problema serial e com o OpenMP. Na próxima, integramos o que foi feito nesta com o MPI.

Questão 01 - 1,0 Ponto

Considere o código a seguir para multiplicação de matrizes:

double **mtxMul (double **c, double **a, double **b, int n) {
   for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++) {
            c[i][j] = 0.0;
            for (int k = 0; k < n; k++)
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
        }
   return c;
}
                    

Considere as duas possibilidades de paralelismo com OpenMP:

1. Apenas o laço for mais externo é paralelizado.
2. A diretiva collapse(2) é aplicada ao laço mais externo.

Complete o trecho de código acima para gerar um programa funcional e execute as duas versões possíveis da paralelização do laço para matrizes quadradas de ordem 2000. Anote o tempo de execução através do campo real do comando time. Para ter uma noção mais exata, execute cada versão pelo menos 3 vezes e capture a média. Forneça um arquivo atv14_questao01.c ou atv14_questao01.cpp com o código da solução e um arquivo atv14_questao01_resultados.txt com uma tabela mostrando o tempo de execução para 8 e 16 threads na máquina paralela para cada uma das opções de paralelismo.

Questão 02 - 1,0 Ponto

A primeira etapa desta atividade consiste em usar a função da questão anterior e criar uma versão serial atv14_questao02_serial.c que atenda os seguintes requisitos:

1. O programa deve receber como parâmetro a ordem da matriz.
2. Em seguida deve gerar duas matrizes double quadradas e preênche-las com o valor 1.0.
3. Realizar a multiplicação usando a função questão anterior, guardando o resultado em outra matriz.
4. Medir o tempo de execução.

Nós usamos o valor 1.0 para facilitar a depuração, pois a matriz resultante fica com todos seus valores iguais a ordem da matriz após a multiplicação. Para medir o tempo de execução, vamos usar a função time, aplicada antes e depois da chamada da função de multiplicação, apenas para variar em relação ao comando que mede o tempo fora do programa.

Após a primeira versão, você deve criar o arquivo atv14_questao02_linemajor.c e representar a matriz como um vetor linear com ordem de linha. Para entender essa organização, considere o exemplo abaixo:

// Organização de memória inicial
a[0][0]=0;
a[0][1]=1;
a[0][2]=2;

a[1][0]=3;
a[1][1]=4;
a[1][2]=5;

a[2][0]=6;
a[2][1]=7;
a[2][2]=8;

// Organização de memória linear
a[0] = 0; a[1] = 1; a[2] = 2;
a[3] = 3; a[4] = 4; a[5] = 5;
a[6] = 6; a[7] = 7; a[8] = 8;
                    

Em outras palavras, as linhas da matriz são representadas de forma contínua na memória, sendo a posição inicial indicada pelo vetor. Como vimos essa opção melhora o uso da cache. O seu programa atv14_questao02_linemajor.c deve atender os mesmos requisitos da versão anterior, mas agora usando a nova organização de memória. Você obviamente deve adaptar a função de multiplicação e realizar aritmética entre os índices i e j da versão versão inicial para corresponder as posições adequadas do vetor, que tem apenas um índice.

Ao final, faça a comparação (atv14_questao_02_resultados.txt) entre as duas versões, de acordo com a tabela abaixo, na qual N é o tamanho da matriz.

# N     Tempo mtxMult       Tempo mtxMult_linemajor
64      ...                 ...
256     ...                 ...
1024    ...                 ...
2048    ...                 ...
            

Na próxima atividade, iremos adaptar esse algoritmo para o MPI.