c++ - 在一个简单的例子中解释并行代码执行和进一步的性能提升

Question

尝试使用 c++11 线程进行多线程编程，我想确保将算​​法分解为与数据无关的部分并并行处理它们应该会减少整体运行时间。

假设任务是在整数数组中找到最大值，并行化非常简单 - 每个线程在特定数据 block 上找到局部最大值，然后在找到所有局部最大值时结束，我们应该从局部最大值中找到最终的最大值——所以运行时间应该减少 3-4 倍，有 4 个硬件线程(在我的电脑上是 4 个)

代码

void max_el(
    std::vector<int>& v,
    std::vector<int>::value_type& max, 
    const int& n_threads=1,
    const unsigned int& tid = 0)
{
    max = v[tid];
    for (size_t i = tid, end = v.size(); i < end; i += n_threads)
    {
        if (v[i] > max)
        {
            max = v[i];
        }
    }
}

void max_el_concurrent(std::vector<int>& v)
{
    int n_threads = std::thread::hardware_concurrency();
    std::cout << n_threads << " threads" << std::endl;
    std::vector<std::thread> workers(n_threads);
    std::vector<int> res(n_threads);

    for (size_t i = 0; i < n_threads; ++i)
    {
        workers[i] = std::thread(max_el, std::ref(v), std::ref(res[i]), n_threads, i);
    }

    for (auto& worker: workers)
    {
        worker.join();
    }


    std::vector<int>::value_type final_max;
    max_el(std::ref(res), std::ref(final_max));
    std::cout << final_max << std::endl;
}


void max_el_sequential(std::vector<int>& v)
{
    std::vector<int>::value_type max;
    std::cout << "sequential" << std::endl;
    max_el(v, max);
    std::cout << max << std::endl;
}


template< class Func, class Container >
void profile(Func func, Container cont)
{
    high_resolution_clock::time_point start, now;
    double runtime = 0.0f;

    start = high_resolution_clock::now();
    func(cont);
    now = high_resolution_clock::now();
    runtime = duration<double>(now - start).count();
    std::cout << "runing time = " << runtime << " sec" << std::endl;
}


#define NUM_ELEMENTS 100000000

int main()
{
    std::vector<int> v;
    v.reserve(NUM_ELEMENTS + 100);
    //  filling
    std::cout << "data is ready, running ... " << std::endl;
    profile(max_el_sequential, v);  // 0.506731 sec

    profile(max_el_concurrent, v);  // 0.26108 sec why only ~2 times faster !?

    return 0;
} 

尽管 std::thread::hardware_concurrency 返回 4 与顺序算法相比，此代码的执行仅显示 2 倍的性能提升。

考虑到 /proc/cpu/info 显示 2 cpus 每个都有 2 cores 以及没有任何锁的事实/unlock，代码中的 I/O 或线程通信开销，我希望理论工作正常并且至少 x3，x4 运行时间减少，但是这并没有发生在实践中...

那么为什么会有这样的行为呢？

那里到底发生了什么？

Answer 1

在我的系统(Core i7-5820k)上，您的应用程序似乎是内存限制。

我得到的加速是 2.9(有 12 个线程)。

在我的系统上，最大 DRAM 带宽为 45GB/s:

应用程序的单线程运行速度约为 16GB/s:

12 个线程:45GB/s:

(3..11 个线程的结果和总体执行时间相同)

在此循环中跨越连续内存的方式效率不高:

    for (size_t i = tid, end = v.size(); i < end; i += n_threads)

内存以连续 block 的形式读入 L2 缓存，因此并行执行此操作会造成浪费；使用 64 字节缓存行和 4 字节 int 这将在每个线程中加载整个数组，最多 16 个线程。这对 L2 缓存来说也是非常浪费的，因为实际上只使用了每个缓存行的一小部分(我们假设线程没有完全同步并且事件区域之间的距离很快超过了 L2 大小)。

---

补充说明:

• 不要对 I/O 计时(包括 std::cout)，这会影响结果。
• 尽量不要从不同的线程写入相邻的内存(就像您对 res vector 所做的那样)，否则您的应用程序将受到 false sharing 的影响。 .您希望在不同线程写入的内存之间保持至少 64 字节的距离。作为快速修复，将局部最大值收集到一个局部变量中，并在最后只写入一次max。

然而，在这种特殊情况下，修复这两个问题对整体性能没有显着影响。

最后，您的 CPU (Core i5-5200) 是一个 2 核超线程处理器。根据 Intel 的说法，超线程的加速比为 on average 30% .这意味着您应该期望最大加速为 2.6 (2 + 2*0.3) 而不是 4.0。