多线程Java不会加速

Question

我在Java中实现了一个简单的并行合并排序算法.这会将数组切割成相等的部分,并将它们传递给每个线程独立排序.对数组段进行排序后,它们将由单个线程合并.由于没有共享资源,因此在对子列表进行排序时不会使用同步.合并结果数组的最后一个线程虽然等待其他线程完成.

当使用两个线程时,性能增益几乎达到66%.当我使用4个线程时,所用时间与2个线程版本没有区别.我在linux上2.6.40.6-0.fc15.i686.PAE,还有一个Intel Core i5.

我使用unix time命令对时间进行基准测试(数组被赋予统一的随机整数).在排序结束时,我正在检查数组排序是否正确(不是并行).

1个线程

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 40.73
user 40.86
sys 0.22

2个主题

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 26.90
user 49.65
sys 0.48

4个线程

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 25.13
user 76.53
sys 0.43

使用4个线程时CPU使用率约为80%至90%,使用2个线程时约为50%,使用单线程时约为25%.

当我在4个线程中运行时,我期待一些加速.我错了.

更新1

这是代码:http://pastebin.com/9hQPhCa8

更新2 我有一个英特尔酷睿i5第二代处理器.

输出cat /proc/cpuinfo | less(仅显示核心0).

processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 42
model name      : Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
stepping        : 7
cpu MHz         : 800.000
cache size      : 3072 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 2
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
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 nx rdtscp lm constant_tsc arch_perfmon pebs bts xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 x2apic popcnt xsave avx lahf_lm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid
bogomips        : 4589.60
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Answer 1

在英特尔芯12-15 XXM系列具有由于多个上下文切换2个核,以便使用多于2个线程会降低性能.

编辑:

这是对我的回答的扩展,其中我采用了Core i7体系结构特定因素,这些因素可能会影响CPU的性能和内存密集型操作(如排序).

涡轮增压技术

英特尔酷睿i7具有可变处理器频率.在高负载时,频率将受到热量的限制,从而降低了利用更多内核的性能增益.

共享L3缓存

对大型数据集(>> 8 Mb)进行排序将导致大量L3页面错误.使用太多线程可能会增加页面错误的数量,从而降低效率.我不确定mergesort是否属于这种情况.(顺便说一下:你如何测量Linux中的L3缓存未命中？)但我不确定这是一个因素.

我必须说,我很惊讶你使用i7的所有四个内核都没有得到任何性能提升.我本周末会尝试在家里进行一些测试.

Answer 2

Core i5拥有2个内核和超线程技术,因此它似乎有4个内核.这些额外的两个逻辑内核几乎不会有两个物理内核,因为您的排序算法在保持CPU忙碌方面做得很好.

既然你要求提供"可信"的来源,我将指出英特尔网站上的一篇文章,我读了一段时间:性能洞察到英特尔超线程技术.特别注意以下关于"超线程限制"的部分:

极其计算效率的应用程序.如果处理器的执行资源已经得到充分利用,那么启用Intel HT技术几乎无法获得.例如,在启用Intel HT技术的情况下,每个周期已经可以执行四条指令的代码不会提高性能,因为进程内核每个周期最多只能执行四条指令.

另请注意有关内存子系统争用的此部分:

极高的内存带宽应用.英特尔HT技术增加了运行两个线程时对内存子系统的需求.如果某个应用程序能够在禁用Intel HT技术的情况下利用所有内存带宽,则启用Intel HT技术时性能不会提高.在某些情况下,由于在这些情况下增加的内存需求和/或数据缓存效应,性能将降低.好消息是,与采用Intel HT技术的旧款Intel CPU相比,基于Nehalem核心的系统集成了内存控制器和英特尔®QuickPath互连,大大提高了可用内存带宽.结果是,由于内存带宽不足而在Nehalem核心上使用Intel HT技术降级的应用程序数量大大减少.

其他有趣的观点可以在英特尔开发多线程应用程序指南中找到.这是检测内存带宽饱和的线程应用程序的另一个片段:

随着越来越多的线程或进程共享缓存容量和内存带宽的有限资源,线程应用程序的可伸缩性可能会受到限制.随着引入更多线程,内存密集型线程应用程序会受到内存带宽饱和的影响.在这种情况下,线程应用程序将无法按预期扩展,并且可以降低性能.