c++ - 在 C++ 中使用 OpenMP 并行化递归函数

Question

我有以下递归程序，我想使用 OpenMP 对其进行并行化:

#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;
}

我已经尝试在 main 函数中添加一个并行区域以及在 countLatticePoints 中并行化 for 循环，但我几乎看不到并行化与顺序运行算法有任何改进。 就我可以使用的其他 OpenMP 策略而言，任何帮助/建议都将不胜感激。

Answer 1

我会采用建议路线。在尝试使用线程使您的程序更快之前，您首先要使其在单线程情况下更快。您可以进行多项改进。您正在制作大量点 vector 的拷贝，这会导致大量昂贵的内存分配。

将 point 传递给 isPointWithinSphere 作为引用。然后，不用两个循环，而是使用一个循环对 point 中的每个元素进行平方和累加。然后，在检查半径时，比较距离的平方而不是距离。这避免了 sqrt 调用并将其替换为一个简单的正方形。

countLatticePoints 也应该引用 point。不是调用 point.size()，而是每次递归时从 dimension 中减去 1，然后只检查 dimension == 1 而不是计算大小。

尽管如此，如果您仍然想要/需要引入线程，您需要根据引用传递点进行一些调整。 countLatticePoint 将需要有两个变体，其中包含 OpenMP 指令的初始调用和没有它们的递归调用。

main 中的 #pragma omp parallel 不会执行任何操作，因为只有一个代码块要执行。