多线程基准

Question

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

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

我的问题是关于以下理由的：

为什么单线程和双线程的性能非常相似？
为什么5线程或7线程时执行时间会下降，而6线程或8线程时执行时间会增加？（我在几次测试中都经历过。）
我用过8核电脑。根据经验，我可以声称 2×n（其中 n 是核心数）是一个很好的线程数吗？
如果我使用 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

8 个线程的工作速度不会超过 7 个，因为你有 8 个 CPU（显然只处理一个线程 - 编辑：感谢@Algridas - 来自你的应用程序）并且您的 main() 需要一个线程运行 on.

Answer 2

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

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

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

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

这将成为一部很棒的 XKCD 式漫画。 "We need to check all these numbers to find primes! By hand!" "Ok, I'll check the evens, you do the odds."

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

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

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

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

多线程基准

Multi-threading benchmark

c++

performance

multithreading

threadpool