多线程基准测试

4

我进行了大量的数学计算,以计算在一个范围内双胞胎素数(twin prime)的数量,并将任务分配给多个线程。

下面是关于执行时间与线程数之间关系的概述。

我的问题涉及以下方面:

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

  2. 为什么当使用5或7个线程时,执行时间会下降,而使用6或8个线程时,执行时间会增加?(在多次测试中我都有这种经验。)

  3. 我使用的是一台8核电脑。我能否声称2×n(其中n是核数)是一个好的线程数规则?

  4. 如果我使用大量RAM的代码,我是否可以期望在此性能概览中看到类似的趋势,或者随着线程数量的增加它是否会发生显著变化?

multithreading benchmark

这是代码的主要部分,仅用于展示它不会占用太多的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

更新(接受答案后)

新个人资料:

Multi-threading performance

改进后的代码如下。现在,工作负载被公平分配。
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;
}

@PaulEvans,我本来以为8个线程的代码比7个线程的代码运行得更快。也许是因为我们应该再算上另一个进程的线程数。我认为你是对的。但是5个线程的代码有一个明显的下降,我找不到任何理由解释这种情况。 - ar2015
@AlgirdasPreidžius,在其他运行中,趋势是相同的。5个线程比4个和6个线程快得多,并且在16个线程时也会饱和。我同意应该多次运行它。但我将在几个小时后才能得出结果。 - ar2015
@ar2015 我怀疑没有人会相信缩短的链接足够安全,以至于点击它。请发布完整的链接(最好作为超链接)。 - Algirdas Preidžius
这是完整的代码 - ar2015
thread_pool.push_back(std::thread(twin_range,range_from + i * range_part,range_from + (i + 1) * range_part - 1));,并获得了预期的执行时间分布(直到8线程标记时它变得更低)。 - Algirdas Preidžius
显示剩余11条评论
2个回答

2
考虑到程序在检查其数字范围的最后一个线程结束时结束。也许一些线程比其他线程快?
当确定偶数是素数时,is_prime()需要多长时间?它将在第一次迭代中找到这个问题。确定奇数的质性至少需要两次迭代,如果a是质数,则可能需要多达sqrt(a)次迭代。当is_prime()给定一个大质数而不是一个偶数时,速度会慢得多!
在您的两个线程示例中,一个线程将检查100000000、100000002、100000004等数字的质性,而另一个线程将检查100000001、100000003、100000005等数字的质性。一个线程检查所有偶数,而另一个线程检查所有奇数(包括那些缓慢的质数!)。
当线程完成时,请让线程打印出("Thread at %ld done", l1),我认为您会发现某些线程比其他线程快得多,这是由于您在线程之间划分域的方式所致。偶数个线程将将所有偶数值分配给同一个或几个线程,导致特别差劲的分区,这就是为什么您的偶数线程数量比奇数更慢的原因。
您的真正问题在于固定的域分解需要每个分区花费相同的时间才能达到最佳状态。
解决这个问题的方法是动态地分区。一个常用的模式涉及使用工作线程池请求工作块。如果与总工作量相比,块很小,则所有线程将在类似的时间内完成其工作。
对于您的问题,您可以拥有一个受互斥保护的全局数据集start_number、stop_number、total_twins。每个线程将在将其全局值增加块大小之前保存start_number。然后,它搜索范围[saved_start_number,saved_start_number+chunk_size),并在完成时将找到的双数添加到全局total_twins。工作线程一直这样做,直到start_number >= stop_number。访问全局变量使用互斥锁进行保护。必须调整块大小,以限制从获取块和互斥锁争用的成本中的低效率,而另一个线程仍在处理其最后一个块时,空闲的工作线程没有更多的块可供分配的低效率。如果使用原子增量请求块,则块大小可能只需要一个单个值,但如果需要在分布式计算系统中进行网络请求,则块大小需要大得多。这就是它的概述。

顺便说一下,你的is_prime()测试太过简单且非常缓慢。如果一个数不能被2整除,那么它能被4整除吗?我们可以做得更好!


非常感谢。我已经修复了代码并且对新的配置文件没有更多疑问了。 - ar2015

0

由于你有8个CPU(显然只处理一个线程 - 编辑:感谢@Algridas - 来自你的应用程序),因此8个线程不会比7个更快,而且你的main()需要一个线程来运行。


而你的 main() 需要一个线程来运行。另外还有其他应用程序在操作系统计算机上。 :) - Algirdas Preidžius
谢谢。你对其他问题有什么看法? - ar2015
我曾经问过类似的问题,他显然在其他应用程序与你的同时运行方面有一些观点。 - Paul Evans
当主线程加入工作线程时,它将会阻塞等待被加入的线程完成。由于主线程被阻塞,它将不会被调度运行。因此,主线程不会“占用”CPU。如果线程在其他线程运行时进行忙等待,那么情况就不同了,但是join方法并不是以忙等待的方式实现的,因为那样会很糟糕。 - TrentP

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接