Я реализовал простой алгоритм сортировки параллельных слияний в Java. Это разрезает массив на равные части и передает их для сортировки независимо по каждому потоку. После сортировки сегментов массива они объединяются одним потоком. Поскольку нет общих ресурсов, поэтому синхронизация не используется при сортировке подписок. Последний поток, который объединяет массив результатов, ждет завершения остальных потоков.
Когда используются два потока, производительность достигает почти 66%. Когда я использую 4 потока, тогда время не отличается от версии 2 потоков. Я нахожусь в linux 2.6.40.6-0.fc15.i686.PAE
и Intel Core i5.
Я сравниваю время с командой unix time
(массиву присваиваются единые случайные целые числа). В конце сортировки я проверяю, правильно ли упорядочен массив (не параллельный).
$ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 40.73 user 40.86 sys 0.222 Темы
$ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 26.90 user 49.65 sys 0.484 Темы
$ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 25.13 user 76.53 sys 0.43
Использование ЦП составляет от 80% до 90% при использовании 4 потоков и около 50% при использовании 2 потоков и около 25% при использовании одного потока.
Я ожидал некоторого ускорения при запуске в 4 потоках. Я где-то не прав.
ОБНОВЛЕНИЕ 1
Вот код: http://pastebin.com/9hQPhCa8
ОБНОВЛЕНИЕ 2 У меня процессор второго поколения Intel Core 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: