多线程增加了c++中的时间

64jmpszr  于 2023-05-02  发布在  其他
关注(0)|答案(2)|浏览(123)

我试图理解为什么增加线程的数量(在一定数量之后)会增加CPU时间而不是减少它。
代码的作用摘要:我有一个主要的创建一个大的向量的基础上的一个维度。我用索引填充它(0。.dimension-1),然后对其进行混洗。然后,为了分而治之,我对这个向量进行分区,为每个线程分配一个切片。我准备了一个向量的向量的解决方案,给予每个条目的线程。每个线程在其切片的每个元素上调用一个函数,并将引用传递给其准备好的解决方案。这个函数只是改变输入中给定索引处的解的值,然后它只是增加解中的所有元素(我把它放在增加一点comp.代码如下:

#include <algorithm>
#include <random>
#include <thread>
#include <iostream>
#include <chrono>
#include <vector>
#include <numeric>

using namespace std;
template<typename T>
inline double getMs(T start, T end) {
    return double(
        std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
        .count()) /
        1000;
}

void fun(const std::vector<int>& slice, int dimension, 
    vector<int>& internal_sol) {
    int size = dimension;

    for (auto const& s : slice) {
        internal_sol[s] = 45;
        internal_sol[int(s/2)] = 45;
        if (s != 0) {
            internal_sol[s - 1] = 45;
        }
        if (s != internal_sol.size() - 1) {
            internal_sol[s + 1] = 45;
        }
        for (auto& i_s : internal_sol)
            i_s += 1;
    }

}

int main(int) {

    
    std::random_device rd;
    std::mt19937 g(rd());

    unsigned int n = std::thread::hardware_concurrency();
    std::cout << n << " concurrent threads are supported.\n";

    std::srand(unsigned(std::time(nullptr)));

    int number_stops = 50000; 
    int number_transfers = 3; 
    int number_structures = 2; 

    auto dimension = number_stops * (number_transfers + 1) * number_structures;
    std::vector<int> v(dimension);
    std::iota(std::begin(v), std::end(v), 0);
    std::shuffle(std::begin(v), std::end(v), g);

    printf("stops:\t%d\ntransfers:\t%d\nstructures:\t%d\n\n", number_stops, number_transfers, number_structures);

    for (size_t np = 2; np < 17; np++) {

        size_t sz = dimension;
        size_t part = sz / np;
        auto start = std::chrono::steady_clock::now();
        std::cout << np << " threads: ";
        std::vector<std::thread> threads(np);

        auto start_ext_sol = std::chrono::steady_clock::now();
        vector<vector<int>> external_sol; //As TAUs from velociraptor
        for (size_t i = 0; i < np; i++) {
            external_sol.emplace_back(dimension, -1);
        }
        double elapsed_ext_sol = getMs(start_ext_sol, std::chrono::steady_clock::now());

        auto paraTask = [&](size_t start, size_t end, vector<int>& ext_sol) {
            for (size_t l = start; l < end; ++l)
                fun({v[l]}, dimension, ext_sol);
            for (int i = 0;i < ext_sol.size(); i++)
                ext_sol[i] = -1;
        };

        for (size_t i = 0; i < np; i++) {
            size_t start = i * part;
            size_t length = (i + 1 == np) ? sz - i * part : part;
            threads[i] =
                std::thread(paraTask, start, start + length, std::ref(external_sol[i]));
        }
        
        // Join the threads
        for (auto&& thread : threads) thread.join();

        double elapsed = getMs(start, std::chrono::steady_clock::now());

        printf("parallel completed: %.3f sec. preparing all vectors ext_sols: %.3f sec\n",
            elapsed, elapsed_ext_sol);
    }

    return 0;
}

得到的结果是:

16 concurrent threads are supported.
stops:  50000
transfers:      3
structures:     2

2 threads: parallel completed: 6.776 sec. preparing all vectors ext_sols: 0.000 sec
3 threads: parallel completed: 5.711 sec. preparing all vectors ext_sols: 0.004 sec
4 threads: parallel completed: 5.285 sec. preparing all vectors ext_sols: 0.003 sec
5 threads: parallel completed: 4.892 sec. preparing all vectors ext_sols: 0.001 sec
6 threads: parallel completed: 4.614 sec. preparing all vectors ext_sols: 0.008 sec
7 threads: parallel completed: 4.726 sec. preparing all vectors ext_sols: 0.001 sec
8 threads: parallel completed: 4.281 sec. preparing all vectors ext_sols: 0.004 sec
9 threads: parallel completed: 4.815 sec. preparing all vectors ext_sols: 0.007 sec
10 threads: parallel completed: 4.791 sec. preparing all vectors ext_sols: 0.008 sec
11 threads: parallel completed: 5.594 sec. preparing all vectors ext_sols: 0.002 sec
12 threads: parallel completed: 5.411 sec. preparing all vectors ext_sols: 0.012 sec
13 threads: parallel completed: 5.213 sec. preparing all vectors ext_sols: 0.010 sec
14 threads: parallel completed: 6.159 sec. preparing all vectors ext_sols: 0.005 sec
15 threads: parallel completed: 8.353 sec. preparing all vectors ext_sols: 0.006 sec
16 threads: parallel completed: 6.769 sec. preparing all vectors ext_sols: 0.012 sec

正如你所看到的,时间在增加。我不明白为什么会这样。这里的维度是450。000个整数,因此大约为1。7 MB(每个整数计数4个字节)。因此,在我的理解中,我们不涉及L1缓存的维度。这是怎么回事?
以下是关于我的机器的一些细节:

  • CPU -第11代英特尔(R)酷睿(TM)i7- 11700KF@3。60GHz
  • 内存- 16 GB DDR4
  • Windows 11编译器- MS_VS 2022

这里是来自CPU-Z的内存硬件报告

PS:我也试过去掉洛普

for (auto& i_s : internal_sol)
            i_s += 1

但是同样的情况也会发生(当然是在较低的时间)

csga3l58

csga3l581#

您的观察结果与Amdahl's law一致,并考虑了使用多线程的开销。
非常粗略地说,不涉及细节,你总是有一些计算部分可以从添加更多线程中受益,称为P,一些不能从添加更多线程中受益的部分称为S,每个线程的开销为T
更多线程t减少P,但不增加S,并增加T

total time = P/t + S + T*t

即使开销很小,在某些时候它也会占主导地位,因为添加更多的线程不能使P/t小于0。在大量线程的限制下,你最终会增加时间

total time (for huge t) = 0 + S + T*t

这只是对运行时的不同组件的非常基本的分析。但是,即使对于一个可以很好地并行化(PS)和小开销(小T)的算法,也总会有一个点,添加更多线程的开销将占主导地位。
Amdahl没有考虑开销,因此他的总时间(实际上他考虑了加速,即total time (t=0) / total time)在某个点饱和。然而,真实的的线程总是带有一点开销。为了进一步研究,为了了解开销实际上来自哪里,我将尝试测量不同大小数据的时间。然后你可能会看到缓存的影响。
为了完整起见,我还应该提到Gustavson,他观察到平行部分P经常随着问题的大小而增加,而非平行部分S通常不会。例如,从一个文件中阅读一些配置需要完成一次,无论你运行100或10000次迭代的一些算法。根据P = p(N)S = constant的假设,可以得出结论,增加工作负载N可以提高硬件的利用率。当使用较小的向量时,您可能会看到这种效果,这将导致更少数量的线程增加时间,而使用较大的向量时,您可能会看到更多数量的线程增加时间。

eeq64g8w

eeq64g8w2#

下面是一个更实际、更精确/更具体的解释,说明为什么计时会随着线程的增加而增加:

*高速缓存未命中是主要的可扩展性瓶颈,特别是由于共享的L3高速缓存和DRAM(也在核之间共享);

  • 超线程没有多大帮助,所以使用8个以上的线程是无用的;
  • 创建线程绝对不是问题(可忽略的时间)。

您的i7- 11700 KF处理器具有8个内核和2个硬件线程/内核。因此,8个核中的8个可以执行线程,而没有来自硬件本身的太多可扩展性问题。使用8个以上线程会导致2个线程在同一内核上运行。这就是为什么时间减少到8个核心,然后在〉=9个线程时再次开始增加。一个核有两个线程要运行,而其他核可能只有一个线程要运行。请注意,线程可以从一个核心移动到另一个(除非您手动绑定它们),因此 * 不稳定的计时 * 超过8个线程。
超线程(Intel技术,使每个核心能够执行超过1个线程)主要是为了通过在同一个核心上并行运行2个线程来提高处理器效率。但有一个问题:硬件线程主要共享硬件资源。例如,L1和L2缓存是共享的,因此在同一个核心上拥有更多的线程也意味着 * 每个核心的空间更少 *。这也是指令解码器的情况,其需要解码两个线程的指令而不是仅1(两倍多的指令)。这就是为什么超线程不会使代码系统地运行得更快。事实上,许多代码(有点)慢,因为该高速缓存开销(e。例如,由于高速缓存颠簸而导致的更多高速缓存未命中)。使用超线程运行得更快的代码通常是那些延迟受限的代码,特别是那些受内存层次结构(例如:简单矩阵转置)。话虽如此,这并不总是正确的。例如,处理器的 line fill buffer 单元负责记录由于L1未命中而对L2的存储器访问,该单元在2个硬件线程之间共享,因此如果1已经使其饱和,则具有两个线程没有帮助。这种事情发生在你的情况下。也不是说运行具有高延迟的长链依赖指令的代码也可以从超线程(例如,超线程)中受益。例如,使用FMA划分的迭代数值配方),但这不是您的情况。最后,这就是为什么超线程在这里没有帮助。
那么问题是为什么该算法即使在8个核心上也不能扩展。@463035818_is_not_a_number主要解释了为什么可扩展性存在理论限制:预期顺序执行的指令的大部分是瓶颈。然而,代码看起来相当尴尬的并行整体,所以它并没有真正的帮助。创建和连接线程的时间(如注解中所示)在这里不是问题,因为代码运行几秒钟,而在大多数PC上(包括我的PC)创建线程的时间不超过几毫秒。
问题是你的算法受内存层次结构的约束,更具体地说,代码的可扩展性受所有内核共享的L3缓存的约束。实际上,有np向量称为external_sol[i],每个向量都需要dimension*sizeof(int),即内存中的50_000*(3+1)*2*4/1024**2 = 1.52 MiB。因此,使用8个线程,12.使用了16 MiB。每个向量都不适合处理器的L1和L2缓存(每个内核分别为80 KiB和512 KiB)。在每个线程中使用0和向量大小之间的随机整数来获取向量。这意味着获取的项不能在L1/L2缓存中存储一段时间,因为以前的值将很快被驱逐,以便读取新的值,并且shuffle没有值要读取两次。相同的缓存行可以被同一个线程读取两次,但是一个给定的缓存行很可能在它被再次读取之前就被驱逐了。这会导致线程为L3缓存中的每个值加载一个缓存行。L3缓存设计为可扩展,但此代码对L3(吞吐量)造成了严重压力。还有一个大问题:L3片是每个核2 MiB,并且L3高速缓存不是完美的,因此存在一些高速缓存未命中,导致DRAM被使用。这也是为什么你的程序在超过8个线程的情况下会变得非常慢的原因:所有向量所需的空间量对于L3来说显然太大,并且大部分读取/存储需要直接在DRAM中完成,延迟要大得多。例如,对于11个线程,您需要11*1.52 = 16.72 MiB,这比L3的宽度要多,L3的宽度应该是16 MiB。有16个线程,它甚至是24。最后但并非最不重要的是,还有另一个复杂的效应:虽然使用更多的线程,每个线程执行更少的存储器访问,但是访问在存储器中更分散,因此重用高速缓存行的概率随着线程数量的增长而下降。

我用一个低级分析器(VTune)在我的i5- 9600 KF处理器上分析了它的执行情况,我可以确认很大一部分访问是在DRAM中用5个线程执行的,而这显然不是1个线程的情况。VTune还报告缓存未命中花费了大量时间(主要是我的处理器上的L2,因为它比你的小两倍)。
请注意,随着更多的核心处于活动状态,核心的频率正在降低,因此处理器具有功率效率(如@teapot418所示)。这就是为什么你的处理器(像许多最近的处理器)不能在8个核心上执行8倍快的算法(假设目标算法在顺序上是有效的)。

相关问题