Parallelisierung rekursive Funktion in C unter Verwendung von OpenMP ++

Question

Ich habe folgende rekursive Programm, das Ich mag würde unter Verwendung von OpenMP parallelisieren:

#include <iostream> 
#include <cmath> 
#include <numeric> 
#include <vector> 
#include <algorithm> 
#include <thread> 
#include <omp.h> 


// Determines if a point of dimension point.size() is within the sphere 
bool isPointWithinSphere(std::vector<int> point, const double &radius) { 

    // Since we know that the sphere is centered at the origin, we can simply 
    // find the euclidean distance (square root of the sum of squares) and check to 
    // see if it is less than or equal to the length of the radius 

    //square each element inside the point vector 
    std::transform(point.begin(), point.end(), point.begin(), [](auto &x){return std::pow(x,2);}); 

    //find the square root of the sum of squares and check if it is less than or equal to the radius 
    return std::sqrt(std::accumulate(point.begin(), point.end(), 0, std::plus<int>())) <= radius;  
} 

// Counts the number of lattice points inside the sphere(all points (x1 .... xn) such that xi is an integer) 

// The algorithm: If the radius is a floating point value, first find the floor of the radius and cast it to 
// an integer. For example, if the radius is 2.43 then the only integer points we must check are those between 
// -2 and 2. We generate these points by simulating n - nested loops using recursion and passing each point 
// in to the boolean function isPointWithinSphere(...), if the function returns true, we add one to the count 
// (we have found a lattice point on the sphere). 

int countLatticePoints(std::vector<int> point, const double radius, const int dimension, int count = 0) { 

    const int R = static_cast<int>(std::floor(radius)); 

    #pragma omp parallel for 
    for(int i = -R; i <= R; i++) { 
     point.push_back(i); 

     if(point.size() == dimension){ 
      if(isPointWithinSphere(point, radius)) count++; 
     }else count = countLatticePoints(point, radius, dimension, count); 

     point.pop_back(); 

    } 

    return count; 
} 

int main(int argc, char ** argv) { 
    std::vector<int> vec; 

    #pragma omp parallel 
    std::cout << countLatticePoints(vec, 5, 7) << std::endl; 

    return 0; 
} 

habe ich versucht, sowie Parallelisierung der for-Schleife einen parallelen Bereich innerhalb der Hauptfunktion das Hinzufügen innerhalb countLatticePoints noch sehe ich kaum eine Verbesserung durch die Parallelisierung vs den Algorithmus der Reihe nach. Jede Hilfe/Beratung wäre in Bezug auf andere OpenMP-Strategien geschätzt, die ich verwenden kann.

Answer 1

Ich nehme den Ratweg. Bevor Sie versuchen, Ihr Programm mithilfe von Threads schneller zu machen, möchten Sie es zunächst im Singlethread-Fall schneller machen. Es gibt verschiedene Verbesserungen, die Sie vornehmen können. Sie machen viele Kopien Ihrer Punktvektoren, die eine Menge teurer Speicherzuweisungen erfordern.

Übergeben Sie point in isPointWithinSphere als eine Referenz. Verwenden Sie dann anstelle von zwei Schleifen eine Schleife zum Quadrat und akkumulieren Sie jedes Element in point. Dann vergleichen Sie beim Überprüfen des Radius das Quadrat der Entfernung und nicht die Entfernung. Dies vermeidet den Aufruf sqrt und ersetzt ihn durch ein einfaches Quadrat.

countLatticePoints sollte auch point durch Bezugnahme nehmen. Anstatt point.size() aufzurufen, subtrahieren Sie 1 von dimension jedes Mal, wenn Sie recurse, dann überprüfen Sie einfach dimension == 1 statt die Größe zu berechnen.

Mit all dem, wenn Sie noch Threading einführen möchten/müssen, müssen Sie einige Anpassungen vornehmen, da Punkt für Punkt übergeben wird. countLatticePoint muss zwei Varianten haben, den ersten Aufruf, der die OpenMP-Direktive enthält, und den rekursiven, der sie nicht enthält.

Die #pragma omp parallel in main wird nichts tun, da nur ein Block Code ausgeführt werden soll.