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

StackOverflow https://stackoverflow.com/questions/8980056

题

过去一周我一直在编写一个光线追踪器，并且已经达到了足够多线程的程度。我尝试过使用 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

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

我使用 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 方法），并在最后将单个值写入其自己的像素数组。这是我所知道的唯一一部分，其中多个线程将尝试写入同一成员变量。任何地方都没有同步，因为没有两个线程可以写入像素阵列中的同一单元。

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

先感谢您。

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

  • 编译器 gcc 4.6（带 -O2 优化）
  • 乌班图 Linux 11.10
  • 开放MP 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;
}

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

有帮助吗？

解决方案

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

正如上面问题中所述，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 使用 init_threadrand(), ，然后使用得到一个随机数 threadrand() 在 OpenMP 中使用多个线程时。

其他提示

答案是，不知道你在哪台机器上运行它，也没有真正看到你的代码 computePixel 功能，这取决于。

有很多因素可能会影响代码的性能，其中想到的一件事是缓存对齐。也许你的数据结构（你确实提到了树）对于缓存来说并不理想，CPU 最终会等待来自 RAM 的数据，因为它无法将数据放入缓存中。错误的缓存行对齐可能会导致类似的情况。如果 CPU 必须等待来自 RAM 的数据，则该线程很可能会被上下文切换，而另一个线程将被运行。

您的操作系统线程调度程序是不确定的，因此， 什么时候 线程的运行不是可预测的事情，因此如果碰巧您的线程没有运行很多，或者正在争夺 CPU 核心，这也可能会减慢速度。

线程亲和力也发挥着作用。线程将被调度在特定的核心上，并且 通常情况下 将尝试将此线程保持在同一核心上。如果多个线程在单个内核上运行，它们将必须共享同一个内核。事情可能会放缓的另一个原因。出于性能原因，一旦特定线程在某个核心上运行，它通常会保留在那里，除非有充分的理由将其交换到另一个核心。

还有一些其他因素，我不记得了，但是，我建议阅读一些有关线程的内容。这是一个复杂而广泛的主题。那里有很多材料。

是否是最后写入的数据，是其他线程需要能够做的数据 computePixel ?

一种强烈的可能性是 虚假分享. 。看起来您正在按顺序计算像素，因此每个线程可能正在处理交错的像素。这通常是一件非常糟糕的事情。

可能发生的情况是，每个线程都试图在另一个线程中写入的像素值旁边写入像素值（它们都写入传感器阵列）。如果这两个输出值共享相同的 CPU 高速缓存行，则会强制 CPU 刷新处理器之间的高速缓存。这会导致 CPU 之间的刷新量过多，这是一个相对较慢的操作。

要解决此问题，您需要确保每个线程真正在独立区域上工作。现在看来你按行划分（我不肯定，因为我不知道 OMP）。这是否有效取决于您的行有多大——但每行的末尾仍然会与下一行的开头重叠（就缓存行而言）。您可能想尝试将图像分成四个块，并让每个线程处理一系列连续的行（例如 1..10 11..20 21..30 31..40）。这将大大减少共享。

不用担心读取常量数据。只要数据块没有被修改，每个线程就可以有效地读取这些信息。但是，请警惕常量数据中的任何可变数据。

我只是看了看 英特尔 i3-2310M 实际上没有 4 个核心，它有 2 个核心和超线程。尝试仅使用 2 个线程运行您的代码，看看是否有帮助。我发现一般来说，当你有大量计算时，超线程是完全没有用的，在我的笔记本电脑上，我将其关闭，并获得了更好的项目编译时间。

事实上，只需进入 BIOS 并关闭 HT——它对于开发/计算机器没有用处。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top