Computação Paralela - Atividade 07

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

Valor: 3,0 pontos na 2ª Nota.

Data da Entrega Limite: 11/06/2022

Formato de Entrega:

1. Um .pdf com as respostas das questões subjetivas da primeira questão e a tabela da segunda questão.
2. Um arquivo chamado sequential_sorting.cpp com a resposta da implementação da primeira questão. Esse arquivo precisa ser compilável usando o compilador g++.
3. Um arquivo chamado omp_primos.cpp com a resposta da implementação da segunda questão. Esse arquivo precisa ser compilável usando o compilador g++.

A atividade é individual.

Questão 01 - 2,0 Pontos

Observe o trecho de código abaixo de um algoritmo de ordenação. O algoritmo apresenta uma dependência quadrática em termos do tamanho de X e pode ser paralelizado facilmente.

void sequential_sort(std::vector& X) {
    unsigned int i, j, count, N = X.size(); 
    std::vector tmp(N);
    
    for (i = 0; i < N; i++) { count = 0;
        for (j = 0; j < N; j++)
        if (X[j] < X[i] || X[j] == X[i] && j < i)
            count++; 
        tmp[count] = X[i];
    }
    std::copy(tmp.begin(), tmp.end(), X.begin()); 
}       
                

1. Explique, por extenso, em suas palavras, como esse algoritmo funciona.
2. Analise as dependências de dados de cada laço. Qual o laço ideal para paralelizar usando OpenMP? Considere a questão das váriaveis compartilhadas. Há algum problema?
3. Implemente uma versão paralela do algoritmo. Discuta o speedup e a eficiência.

Para implementar sua versão, você pode pegar algum exemplo simples do código no repositório do livro texto e refatorá-lo. Na pasta chapter6 há vários exemplos em OpenMP. Você pode criar uma nova pasta com a mesma estrutura e reutilizar as macros para medição de tempo e o arquivo Makefile.

Questão 02 - 1,0 Ponto

Considere o programa abaixo, que faz o calculo de todos os números primos entre 0 e um valor final informado.

#include <stdio.h> 
#include <stdlib.h>
#include <math.h> 

int primo(long int n) {
    long int i;
    for (i = 3; i < (long int)(sqrt(n) + 1); i += 2)
        if (n % i == 0)
            return 0;
    return 1;
}

int main(int argc, char *argv[]) { 
    double t_inicio, t_fim;
    long int i, n, total;

    if (argc < 2) {
        printf("Valor inválido! Entre com o valor do maior inteiro\n"); return 0;
    }
    else {
        n = strtol(argv[1], (char **)NULL, 10);
    }

    total = 0;

    for (i = 3; i <= n; i += 2)
        if (primo(i) == 1)
            total++;
    
    total += 1;

    printf("Quant. de primos entre 1 e %ld: %ld\n", n, total);
    return (0);
}      
                

Você deve paralelizar essa solução de forma que ocorra balanceamento uniforme entre as threads. Em outras palavras, a divisão de trabalho deve ser justa. Em seguida, fixe a entrada em \(N = 100.000.000\) e preencha a seguinte tabela, usando a máquina paralela.joao.marcelo.nom.br.

Execute cada experimento pelo menos três vezes, para ter certeza que os valores estão estáveis.