C fatorial com vetor em openmp

xAJSx · 30 de setembro de 2020

Boa tarde pessoal. Preciso de uma ajuda nesse exercício sobre OPENMP. Esta compilando e me trazendo valores altos de mais. Podem me ajudar para verificar se está ok? Obrigado.

/*Desenvolver um programa em OpenMP que popule aleatoriamente um vetor de
100.000.000 registros de números inteiros em uma região paralela. Em outra região
paralela, calcule para cada posição do vetor o seu fatorial. Calcule o speedup e a
eficiência obtidos com 2 e 4 threads.*/



#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#define N 5

int main() {
    int V[N], i, fatorial, fatorial_local;

    fatorial = 1;
    
    
    #pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
    {
        #pragma omp for
        for(i = 0; i < N; i++){
        fatorial = fatorial * V[i];
        }
        
        fatorial_local = 0;
        #pragma omp for
        for(i = 0; i < N; i++) fatorial = fatorial + V[i];
        
        //Região Crítica
        #pragma omp critical
        fatorial    = fatorial + fatorial_local;    
    }
    
    printf("Fatorial é: %d\n", fatorial);
    return(0);
}

V!OLADOR · 30 de setembro de 2020

Há vários sintomas visíveis: quando você entra na região em paralelo, o primeiro laço for pode estar sendo executado ao mesmo tempo no qual a variável fatorial no final está sendo atualizada, o que não faria sentido algum. O mesmo vale pro laço intermediário. Ainda que o exercício peça pra executar tarefas com várias threads, deve-se respeitar os pontos da execução que são inerentemente sequenciais. O exercício exige duas etapas, a) criar e preencher um vetor; b) manipular esse vetor (a posteriori) pra computar o fatorial de cada elemento. Como as duas etapas envolvem 100k elementos, claramente, os laços serão as partes mais lentas da execução, e portanto merecedoras de paralelismo, não todo o código.

Seria mais fácil, pelo menos a principio, usar duas áreas paralelas distintas. Uma pra cada etapa. A primeira:

#pragma omp parallel for default(none) shared(V)
for (int i = 0; i < N; i++)
{
	V[i] = /* valor aléatorio do i-ésimo elmento de V aqui */;
}

A execução volta então ao padrão, sequencial, você poderia aproveitar esse momento para, por exemplo, escrever na tela alguns elementos de V ou fazer qualquer outra coisa relevante ao exercício. E então, resolver a segunda etapa noutra área paralela:

#pragma omp parallel for default(none) shared(V)
for (int i = 0; i < N; i++)
{
	double f = factorial(V[i]);
}

No qual, chamei de f o valor do fatorial do i- ésimo elemento de V. Assumo que você possa implementar uma função pra calcular o fatorial, i.e. factorial no exemplo.

xAJSx · 1 de outubro de 2020

@V!OLADOR Olá, muito obrigado por me ajudar. Desculpe a burrice mas sou muito leigo nesse conteúdo e não entendi muito bem como implementar isso. Eu deveria excluir alguma parte do meu codigo ou somente soltar esse script dentro dele? Muito obrigado.

V!OLADOR · 1 de outubro de 2020

O que eu fiz foi uma explicação breve e uma sugestão de solução, de maneira que você possa pensar a melhor forma de resolver o exercício. Simplesmente fazê-lo por você seria um pouco antiético da minha parte. Na minha sugestão, você poderia, primeiramente, substituir o bloco inteiro

#pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
{ 
}

pelos dois que propus acima. Apenas isso não resolve o exercício. Os dois blocos propostos na minha primeira resposta estão propositalmente incompletos pra que você possa completá-los por contra própria. Tente, e caso não consiga, poste o novo código e seguimos dai em diante.

Caso ainda assim não seja possível nem mesmo implementar, pergunte mais e eu tentarei explicar mais pontos. No fim das contas o importante não é necessariamente fazer o exercício mas entender o que deve ser feito (e como).

xAJSx · 5 de outubro de 2020

Bom, estava testando aqui rapidamente e me apresentou um erro somente no "FACTORIAL".

O código está assim:

/*Desenvolver um programa em OpenMP que popule aleatoriamente um vetor de
100.000.000 registros de números inteiros em uma região paralela. Em outra região
paralela, calcule para cada posição do vetor o seu fatorial. Calcule o speedup e a
eficiência obtidos com 2 e 4 threads.*/

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#define N 100000

int main() {
    int V[N], i, fatorial, fatorial_local;
    double f;


    #pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
    {
        
	#pragma omp parallel for default(none) shared(V)
	for (int i = 0; i < N; i++)
	{
		V[i] = i*V[i-1];
	}
	
	#pragma omp parallel for default(none) shared(V)
	for (int i = 0; i < N; i++)
	{
	double f = factorial(V[i]);
	}		
          
    }
    
    printf("Fatorial é: %f\n", f);
    return(0);
}

@V!OLADOR

V!OLADOR · 5 de outubro de 2020

Esse é todo o código? porque, em caso positivo, tá visivelmente incompleto. Você deve criar a função factorial por conta própria. Ela não existe nas bibliotecas que você incluiu no projeto, stdio.h, stdlib.h e omp.h. Algo como

double factorial(const int n)
{
	if (n == 0) return 1; 

	return n*factorial(n - 1); 
}

main()
{
	/* o resto do programa */
}

Mas depois de criar um método pra calcular o fatorial, é ainda pouco provável que esteja correto. Dois problemas graves existem. Primeiro a questão pede pra preencher o vetor V com valores aleatórios. Mas isso

V[i] = i*V[i-1];

não apenas não é aleatório, pelo contrario, gera sempre os mesmo números, como também tem um erro: quando i = 0, ou seja no primeiro passo, i - 1 está fora do intervalo de N elementos. O intervalo de V é (0, N - 1). Caso queira uma solução simples pra gerar números aleatórios você poderia utilizar a função rand, conhece?

Outro problema, a seguinte construção está ruim:

    #pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
    {
        
	#pragma omp parallel for default(none) shared(V)
	
	#pragma omp parallel for default(none) shared(V)
    }

Veja, você abriu um bloco em paralelo com a primeira pragma, usando omp parallel e logo em seguida abriu mais duas zonas paralelas dentro da primeira. O numero de threads que a sua CPU pode executar simultaneamente é fixa. Você está sobrecarregando as threads e a performance do código vai ser horrível, se funcionar (não vai porque a logica tampouco está correta). Reveja minha primeira resposta, na qual propus duas zonas paralelas independentes, ou seja,

/* executando sequencialmente aqui com 1 thread */

#pragma omp parallel for default(none) shared(V)
for (int i = 0; i < N; i++)
{
	/* executando em paralelo aqui com varias threads */
}

/* executando sequencialmente aqui com 1 thread novamente */

#pragma omp parallel for default(none) shared(V)
for (int i = 0; i < N; i++)
{
	/* executando em paralelo aqui com varias threads novamente */

}

/* executando sequencialmente aqui com 1 thread novamente */

Na primeira zona em paralelo você cria N elementos aleatórios e armazena em V, na segunda você calcula o fatorial de cada um deles. A maneira que você tentou pode funcionar com algumas modificações mas seria necessário introduzir conceitos mais complicados e não é necessário pro objetivo que você deseja atingir.

xAJSx · 5 de outubro de 2020

@V!OLADOR Como eu faço para calcular o fatorial de cada elemento no vetor? Meu codigo está assim, ele está compilando e trazendo como resultado "0":

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#define N 100000


        double factorial(const int n)
        {
	if (n == 0) return 1; 

	return n*factorial(n - 1); 
        }

int main()
{
	int V[N], i, fatorial, fatorial_local;
    double f;


    #pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
    {
        
    	#pragma omp parallel for default(none) shared(V)
    	for (int i = 0; i < N; i++)
    	{
        V[i]  = rand();
    	}
	
    }
    
    	#pragma omp parallel for default(none) shared(V)
    	for (int i = 0; i < N; i++)
    	{
    	
    	double f = fatorial * V[i];
    	}		
    
    
    
    printf("Fatorial é: %f\n", f);
    return(0);
}

V!OLADOR · 6 de outubro de 2020

Ok, ainda há vários erros mas não relacionados com paralelismo e, sim, C básico.

Quando eu sugeri usar a função rand, estava subentendido que você deveria consultar a documentação dessa função antes de usá-la. Basta um google em "como usar C rand". Você precisa inicializar o gerador de números aleatórios produzidos por rand, antes de chamá-la pela primeira vez, e isso é efeito com a função srand. Então, chame srand antes do primeiro laço for, mas não apenas copie e cole "srand" aleatoriamente no código, procure ler como usá-la.

Por coincidência debatemos noutro tópico, semana passada, como rand e srand funcionam. Dê uma olhadinha lá: Ler tamanho da entrada para criar vetores

Esse trecho, continua errado:

    #pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
    {
        
    	#pragma omp parallel for default(none) shared(V)
    	for (int i = 0; i < N; i++)
    	{
        V[i]  = rand();
    	}
	
    }

Por sinal, o mesmo erro de antes, você continua abrindo mais de uma zona paralela, com uma dentro da outra, sem necessidade. Releia minha ultima resposta e remova o bloco mais externo:

#pragma omp parallel shared(V, fatorial) private(i, fatorial_local)
{
}

E, por fim, esse trecho não tem lógica:

    double f;

/* ... */
        #pragma omp parallel for default(none) shared(V)
        for (int i = 0; i < N; i++)
    	{
    	
    	double f = fatorial * V[i];
    	}		
    
    
    
    printf("Fatorial é: %f\n", f);

Você está apenas copiando e colando os exemplos que digitei anteriormente mas sem pensar. Por que declarar f dentro do for se já foi declarado no inicio do programa? qual dos dois você quer escrever com o printf? se você não sabe, pois a maquina tampouco vai saber. O que o compilador está escrevendo na tela é o primeiro f, que nunca foi utilizado. Além disso, você tem N fatoriais pra escrever na tela, então, mantendo printf fora do laço for, você só vai escrever efetivamente o ultimo fatorial, N - 1. Mova o printf pra dentro do laço for.

Pra usar a função factorial, você precisa chamá-la pra cada um dos i elementos de V,