c++ - 多线程基准

Question

我进行了大量的数学计算来计算 twin prime 的数量。一个范围内的数字，我在线程之间分配了任务。

在这里您可以看到执行时间与线程数的关系。

我的问题是关于理由:

1. 为什么单线程和双线程的性能非常相似？

2. 为什么使用 5 或 7 线程时执行时间会下降，而使用 6 或 8 线程时执行时间会增加？ (我在几次测试中都经历过。)

3. 我用过 8 核电脑。根据经验，我可以声称 2×n(其中 n 是核心数)是一个很好的线程数吗？

4. 如果我使用 RAM 使用率较高的代码，我会期望配置文件中出现类似的趋势，还是会随着线程数量的增加而发生显着变化？

这是代码的主要部分，只是为了说明它没有使用太多 RAM。

bool is_prime(long a)
{
    if(a<2l)
        return false;
    if(a==2l)
        return true;
    for(long i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}

uint twin_range(long l1,long l2,int processDiv)
{
    uint count=0;
    for(long l=l1;l<=l2;l+=long(processDiv))
        if(is_prime(l) && is_prime(l+2))
        {
            count++;
        }
    return count;
}

规范:

$ lsb_release -a

Distributor ID: Ubuntu
Description:    Ubuntu 16.04.1 LTS
Release:    16.04
Codename:   xenial

$ lscpu

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 94
Model name:            Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
Stepping:              3
CPU MHz:               799.929
CPU max MHz:           4000.0000
CPU min MHz:           800.0000
BogoMIPS:              6815.87
Virtualisation:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

---

更新(接受答案后)

新配置文件:

改进后的代码如下。现在，工作负载被公平分配。

bool is_prime(long a)
{
    if(a<2l)
        return false;
    if(a==2l)
        return true;
    for(long i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}


void twin_range(long n_start,long n_stop,int index,int processDiv)
{
    // l1+(0,1,...,999)+0*1000
    // l1+(0,1,...,999)+1*1000
    // l1+(0,1,...,999)+2*1000
    // ...

    count=0;
    const long chunks=1000;
    long r_begin=0,k=0;
    for(long i=0;r_begin<=n_stop;i++)
    {
        r_begin=n_start+(i*processDiv+index)*chunks;
        for(k=r_begin;(k<r_begin+chunks) && (k<=n_stop);k++)
        {
            if(is_prime(k) && is_prime(k+2))
            {
                count++;
            }
        }
    }

    std::cout
        <<"Thread "<<index<<" finished."
        <<std::endl<<std::flush;
    return count;
}

Answer 1

假设您的程序将在最后一个 线程完成检查其数字范围时结束。也许有些线程比其他线程快？

is_prime() 需要多长时间才能确定一个偶数是质数？它会在第一次迭代时找到它。寻找奇数的素数至少需要两次迭代，如果 a 是素数，则可能需要最多 sqrt(a) 次迭代。 is_prime() 当它被赋予一个比偶数大的素数时会慢得多!

在您的双线程情况下，一个线程将检查 100000000、100000002、100000004 等的素数，而另一个线程将检查 100000001、100000003、100000005 等的素数。一个线程检查所有偶数，而另一个线程检查所有奇数(包括所有那些慢素数!)。

让你的线程在它们完成时打印出 ("Thread at %ld done", l1)，我想你会发现一些线程比其他线程快得多，因为方式您正在划分线程之间的域。偶数个线程会将所有偶数值赋给同一个线程，导致分区特别差，这就是为什么偶数线程比奇数慢。

这将成为一部很棒的 XKCD 式漫画。 “我们需要检查所有这些数字以找到质数!手工!” “好吧，我来查偶数，你来算数。”

这里您真正的问题是像您所做的固定域分解要求每个分区花费相同的时间才能达到最佳。

解决这个问题的方法是动态地做分区。一种常用的模式涉及请求分块工作的工作线程池。如果与线程将完成的总工作相比 block 较小，则所有线程将在相似的时间内完成工作。

对于您的问题，您可以拥有一个互斥锁保护的全局数据集 start_number, stop_number, total_twins。每个线程在将其全局值增加 chunk_size 之前将保存 start_number。然后搜索范围 [saved_start_number, saved_start_number+chunk_size)，完成后将找到的双胞胎数量添加到全局 total_twins。工作线程一直这样做，直到 start_number >= stop_number。对全局变量的访问使用互斥锁进行保护。必须调整 block 大小以限制因获取 block 的成本和互斥体上的争用而导致的低效率与空闲工作线程没有更多 block 可分配而另一个线程仍在其最后一个 block 上工作的低效率。如果您使用原子增量来请求 block ，那么 block 大小可能会小到单个值，但如果在分布式计算系统中需要网络请求，那么 block 大小将需要更大。这是其工作原理的概述。

顺便说一句，您的 is_prime() 测试很幼稚而且非常慢。如果一个数不能被 2 整除，它能被 4 整除吗？可以做得更好!