1

Tengo un código en C++ que intento paralelizar con OpenMPI, consiste en buscar los números primos hasta un tope indicado:

#include <vector>
#include <cmath>
#include <iostream>
#include <omp.h>
#include <ctime> 
using namespace std;
int main() {
    unsigned t0, t1;
    t0 = clock();
    omp_set_num_threads(4);
    auto maximo = 1000000ul; //numero maximo a buscar
    // Criba secuencial
    std::vector<int> primos{ 2 }; // Añadimos el 2 al array para poder saltarnos los pares
    primos.reserve(maximo);
#pragma omp parallel for
    for (auto posible_primo = 3ul; posible_primo < maximo; posible_primo += 2) {
        /* Comprobamos si es primo buscando si en el array hay algun
        numero primo que lo divida, pero solo hasta raiz de n. */
        const auto limite = sqrt(posible_primo);

        bool es_divisible = false;
        for (auto divisor : primos) {
            if (limite < divisor)
                break;
            if (es_divisible = !(posible_primo % divisor))
                break;
        }


        if (!es_divisible) {
            primos.push_back(posible_primo);
        }
    }

    for (auto primo : primos)
        std::cout << primo << ' ';
    t1 = clock();
    double time = (double(t1 - t0) / CLOCKS_PER_SEC);
    cout << "\n\n\tExecution Time: " << time << endl;
    return 0;
}

Tengo que paralelizar el bucle exterior (el que recorre los números desde 3 hasta el límite superior), para ello he utilizado #pragma omp parallel for

Cuando ejecuto el algoritmo, tarda lo mismo que si quito la sentencia paralela.

¿Qué hago mal? tampoco se cómo hacer para evitar las condiciones de carrera en la escritura del número primo en el vector.

7
  • Fíjate en tu administrador de tareas si usa los procesadores al mismo tiempo, también verifica que compilaste con los comandos adecuados Commented el 3 oct. 2019 a las 20:06
  • Hay que tener en cuenta que crear hilos de ejecución ni es una solución mágica ni tiene coste cero. Cada hilo necesita un espacio de memoria para su pila y su montón (stack y heap), configurar eso tiene un coste determinado que a veces supera el coste de computación que se paraleliza, con lo que en ocasiones puede resultar que una tarea ¡tarde más en completarse cuando se paraleliza!. Commented el 4 oct. 2019 a las 7:33
  • @PaperBirdMaster sí, eso lo se, pero no se si el problema es que no está bien el código que he puesto para paralelizar o si es po lo que comentas, dado que calculo números grandes y el coste en tiempo es el mismo
    – XBoss
    Commented el 4 oct. 2019 a las 10:40
  • @XBoss lo que también puede estar pasando es que todos los hilos comparten el recurso std::vector<int> primos y se bloquean entre ellos. Commented el 4 oct. 2019 a las 10:44
  • 1
    Con omp no lo vas a evitar. Tienes que crear semáforos alrededor del recurso compartido. Pero no te servirá de nada, porque los datos son dependientes: para calcular un primo N, necesitas los primos anteriores a N, así que si en un hilo calculas de 0 a 99 deberás esperar a que ese tramo acabe para calcular de 100 a 299: o sea que será lo mismo que hacerlo secuencialmente. Commented el 7 oct. 2019 a las 6:43

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

Examina otras preguntas con la etiqueta o formula tu propia pregunta.