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

Question

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

阅读其他类似问题,特别是有关OpenMP的问题,一个建议是gcc更好地优化串行代码.但是,运行下面的编译代码的export OMP_NUM_THREADS=1速度是以下的两倍export OMP_NUM_THREADS=4.即两次运行的编译代码相同.

运行程序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

用户时间比实际小很多,这在使用多个核心时很不寻常 - 用户应该比实际大,因为多个核心同时运行.

我使用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()的实现,它同步对自身的调用以保持线程之间随机数生成的状态.我对monte carlo采样使用了很多rand(),所以我认为这就是问题所在.我摆脱了对rand的调用,用单个值替换它们,但使用多个线程仍然比较慢.编辑:oops结果我没有正确测试,这是随机值!

现在这些已经不在了,我将讨论每次调用时所做的事情的概述computePixel,因此希望找到解决方案.

在我的光线跟踪器中,我基本上有一个场景树,其中包含所有对象.在computePixel对象进行交叉测试时会遍历此树,但是不会对此树或任何对象进行写入.computePixel本质上是多次读取场景,调用对象上的方法(所有这些都是const方法),并在最后将单个值写入其自己的像素数组.这是我所知道的唯一一部分,多个线程会尝试写入同一个成员变量.在任何地方都没有同步,因为没有两个线程可以写入像素阵列中的同一个单元.

任何人都可以建议可能存在某种争用的地方吗？要尝试的事情？

先感谢您.

编辑: 对不起,愚蠢的是不提供我的系统的更多信息.

• 编译器gcc 4.6(带-O2优化)
• Ubuntu Linux 11.10
• OpenMP 3
• 英特尔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;
}

根据建议,可能是树遍历导致减速.其他一些方面:一旦调用采样函数(光线的递归弹跳),就会涉及相当多的递归 - 这会导致这些问题吗？

Answer 1

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

正如上面问题中所述，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现在，您可以使用初始化线程的随机状态，然后在 OpenMP 中使用多个线程时init_threadrand()使用 获取随机数。threadrand()