将程序拆分为 4 个线程比单个线程慢

过去一周我一直在编写一个光线追踪器，并且已经达到了足够多线程的程度。我尝试过使用 OpenMP 来并行化它，但是使用更多线程运行它实际上比使用一个线程运行它要慢。

阅读其他类似的问题，尤其是有关 OpenMP 的问题，一个建议是 gcc 可以更好地优化串行代码。但是运行下面的编译代码export OMP_NUM_THREADS=1速度是原来的两倍export OMP_NUM_THREADS=4。 IE。两次运行时编译的代码相同。

运行程序time:

> export OMP_NUM_THREADS=1; time ./raytracer
real    0m34.344s
user    0m34.310s
sys     0m0.008s


> export OMP_NUM_THREADS=4; time ./raytracer
real    0m53.189s
user    0m20.677s
sys     0m0.096s

用户时间比实际时间少很多，这在使用多核时是不常见的 -user应该大于real因为多个核心同时运行。

我使用 OpenMP 并行化的代码

void Raytracer::render( Camera& cam ) {

    // let the camera know to use this raytracer for probing the scene
    cam.setSamplingFunc(getSamplingFunction());

    int i, j;

    #pragma omp parallel private(i, j)
    {

        // Construct a ray for each pixel.
        #pragma omp for schedule(dynamic, 4)
        for (i = 0; i < cam.height(); ++i) {
            for (j = 0; j < cam.width(); ++j) {
                cam.computePixel(i, j);
            }
        }
    }
}

读书时这个问题我以为我已经找到答案了。它讨论了 gclib rand() 的实现，同步调用自身以保留线程之间随机数生成的状态。我经常使用 rand() 进行蒙特卡罗采样，所以我认为这就是问题所在。我摆脱了对 rand 的调用，用单个值替换它们，但使用多个线程仍然较慢。编辑：哎呀事实证明我没有正确测试这个，这是随机值！

现在这些都已经解决了，我将概述每次调用时所做的事情computePixel，所以希望能找到解决方案。

在我的光线追踪器中，我基本上有一个场景树，其中包含所有对象。这棵树在这段时间内被遍历了很多次computePixel然而，当测试对象的交集时，不会对此树或任何对象进行写入。computePixel本质上是多次读取场景，调用对象上的方法（所有这些都是 const 方法），并在最后将单个值写入其自己的像素数组。这是我所知道的唯一部分，其中多个线程将尝试写入同一成员变量。任何地方都没有同步，因为没有两个线程可以写入像素阵列中的同一单元。

谁能建议可能发生某种争论的地方？值得尝试的事情？

先感谢您。

EDIT:抱歉，我很愚蠢，没有提供有关我的系统的更多信息。

• 编译器 gcc 4.6（带 -O2 优化）
• 乌班图 Linux 11.10
• OpenMP 3
• Intel i3-2310M 四核 2.1Ghz（目前在我的笔记本电脑上）

计算像素的代码：

class Camera {

    // constructors destructors
    private:
        // this is the array that is being written to, but not read from.
        Colour* _sensor; // allocated using new at construction.
}

void Camera::computePixel(int i, int j) const {

    Colour col;

    // simple code to construct appropriate ray for the pixel
    Ray3D ray(/* params */);
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col;
}

从建议来看，可能是树遍历导致速度减慢。其他一些方面：一旦调用采样函数，就会涉及相当多的递归（光线的递归弹跳）——这会导致这些问题吗？

感谢大家的建议，但经过进一步分析并消除其他影响因素后，随机数生成did原来是罪魁祸首。

正如上面问题中所述，rand() 需要跟踪其从一次调用到下一次调用的状态。如果多个线程试图修改此状态，则会导致竞争条件，因此 glibc 中的默认实现是锁定每个通话，使函数成为线程安全的。这对于性能来说是很糟糕的。

不幸的是，我在 stackoverflow 上看到的这个问题的解决方案都是本地的，即处理问题在调用 rand() 的范围内。相反，我提出了一种“快速而肮脏”的解决方案，任何人都可以在他们的程序中使用它来为每个线程实现独立的随机数生成，而不需要同步。

我已经测试了代码，它有效 - 没有锁定，并且调用 threadrand 没有明显的减慢。欢迎指出任何明显的错误。

线程兰德.h

#ifndef _THREAD_RAND_H_
#define _THREAD_RAND_H_

// max number of thread states to store
const int maxThreadNum = 100;

void init_threadrand();

// requires openmp, for thread number
int threadrand();

#endif // _THREAD_RAND_H_

threadrand.cpp

#include "threadrand.h"
#include <cstdlib>
#include <boost/scoped_ptr.hpp>
#include <omp.h>

// can be replaced with array of ordinary pointers, but need to
// explicitly delete previous pointer allocations, and do null checks.
//
// Importantly, the double indirection tries to avoid putting all the
// thread states on the same cache line, which would cause cache invalidations
// to occur on other cores every time rand_r would modify the state.
// (i.e. false sharing)
// A better implementation would be to store each state in a structure
// that is the size of a cache line
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum];

// reinitialize the array of thread state pointers, with random
// seed values.
void init_threadrand() {
    for (int i = 0; i < maxThreadNum; ++i) {
        randThreadStates[i].reset(new unsigned int(std::rand()));
    }
}

// requires openmp, for thread number, to index into array of states.
int threadrand() {
    int i = omp_get_thread_num();
    return rand_r(randThreadStates[i].get());
}

现在您可以初始化线程的随机状态main using init_threadrand()，然后使用得到一个随机数threadrand()在 OpenMP 中使用多个线程时。