Многопоточная 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

Загрузка ЦП составляет около 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:

Answer 1

Серия intel core i5-xxM имеет 2 ядра, поэтому использование более 2 потоков снизит производительность из-за большего переключения контекста.

Редактировать:

Вот расширение моего ответа, в котором я рассмотрю Архитектура Core i7 -специфичные факторы, которые могут повлиять на производительность процессора и объемные операции, такие как сортировка.

Технология Turbo Boost

Intel Core i7 имеет переменную частоту процессора.При высоких нагрузках частота будет ограничена теплом, что приведет к снижению производительности при использовании большего количества ядер.

Общий кэш L3

Сортировка больших наборов данных (>> 8Mb) приведет к большому количеству ошибок страницы L3.Использование слишком большого количества потоков может увеличить количество ошибок страниц, снижая эффективность.Я не уверен, так ли это для сортировки.(Кстати: как вы измеряете ошибки кэша L3 в Linux?) Однако я не уверен, что это является фактором.

Я должен сказать, что удивлен, что вы не получаете никакого повышения производительности от использования всехчетыре ядра i7.Я попробую провести несколько тестов дома в эти выходные.

Answer 2

Core i5 имеет 2 ядра и технологию гиперпоточности, поэтому кажется, что он имеет 4 ядра. Эти дополнительные два логических ядра не помогут почти так же, как два физических ядра, так как ваш алгоритм сортировки хорошо справляется с нагрузкой на процессор.

Поскольку вы запросили «заслуживающий доверия» источник, я укажу на статью на веб-сайте Intel, которую я читал некоторое время назад: производительность-понимание-технология-гиперпоточность-технология . В частности, обратите внимание на следующий раздел «Ограничения гиперпоточности»:

Чрезвычайно вычислительные приложения. Если выполнение процессора ресурсы уже хорошо использованы, то мало что может быть получен благодаря использованию технологии Intel HT. Например, код, который уже может выполнять четыре инструкции за цикл не увеличится производительность при работе с включенной технологией Intel HT, так как ядро процесса может выполнять не более четырех инструкций в цикл.

Также обратите внимание на этот раздел о конфликте подсистемы памяти:

Приложения с чрезвычайно высокой пропускной способностью памяти. Технология Intel HT увеличивает потребность в подсистеме памяти при запуске двух потоки. Если приложение способно использовать всю память пропускная способность с отключенной технологией Intel HT, затем производительность не будет увеличиваться, если включена технология Intel HT. Это возможно в некоторых обстоятельствах производительность будет ухудшаться из-за требования к памяти и / или эффекты кэширования данных в этих случаях. Хорошей новостью является то, что системы на базе ядра Nehalem со встроенным контроллеры памяти и Intel® QuickPath Interconnects значительно увеличить доступную пропускную способность памяти по сравнению со старыми процессорами Intel с технологией Intel HT. Результатом является то, что число приложения, которые будут испытывать деградацию при использовании Intel HT Технология на ядре Nehalem из-за недостатка пропускной способности памяти сильно уменьшено.

Другие интересные моменты можно найти в Руководстве Intel по разработке многопоточных приложений . Вот еще один фрагмент из приложений-определения пропускной способности-памяти-насыщения-в-многопоточности :

Поскольку все большее число потоков или процессов разделяют ограниченные ресурсы кэш-памяти и пропускной способности памяти, масштабируемость потоковое приложение может стать ограниченным. Память интенсивного многопоточные приложения могут страдать от насыщения пропускной способности памяти, как больше тем введено. В таких случаях резьбовое приложение не будет масштабироваться, как ожидается, и производительность может снизиться.

Answer 3

Другой возможной проблемой может быть ложный обмен.

http://en.wikipedia.org/wiki/False_sharing

http://drdobbs.com/go-parallel/article/showArticle.jhtml?articleID=217500206

Это будет зависеть от того, как часто сортировка слиянием обращается к элементам в строках граничного кэша. Вероятно, это было бы гораздо более заметно для наборов данных, размер которых меньше килобайта или около того.

Answer 4

Я получаю ожидаемый результат на двухъядерном i7 с опцией -server JVM, 100000000 дюймов и 2 Гб памяти Xmx:

1 поток: 23 секунды
2 потока: 14 секунд
4 потока: 10 секунд

И я также удалил ручную сборку мусора и выполнил сортировку последовательно в том же экземпляре JVM, предварительно выполнив сортировку разминки.

Как отмечает Мистер Смит, микробенчмаркинг (точка доступа JVM) несколько сложен, и я мог бы добавить, что для ядер 4+ сортировка слиянием может быть выполнена вдвое меньше, чем в одном потоке, как сейчас, поэтому бенчмарк не совсем соответствует многопоточному подходу.

Возможно, вы также захотите проверить этот вопрос.

Answer 5

Я попробовал это на i7, и даже с 4 ядрами не было улучшения от 2 - 4 потоков. Я подозреваю, что проблема в том, что ваши данные не помещаются в кеш, поэтому вы тестируете пропускную способность одной шины памяти.

Answer 6

Для сравнения попробуйте использовать сортировку слиянием с Java 7 и инфраструктуру fork fork.Вот пример того, как это сделать здесь .Это покажет вам, если это проблема с вашей реализацией или ограничение машины.

Answer 7

Интересно, потому что я пытаюсь распараллелить сортировку слиянием. Перепробовал два разных подхода к работе, но не набрал скорость. Мой подход к параллелизации сортировки слиянием состоит в том, чтобы сделать слияние параллельным. а отдельные слияния на разных ядрах? В этом случае рекурсия обрезается, а количество потоков влияет на ускорение. Снова ускорение не может превысить серийную скорость. Эта техника появилась в книге Моргана Кауфмана «Структурно-параллельное программирование».

Параллельная сортировка слиянием

Answer 8

Мне недавно пришлось сделать апплет, сравнивающий сортировку пузырьков, сортировку слиянием и битовую сортировку на архитектуре i7.Я использовал первый приведенный здесь код для слияния, и у меня возникла та же проблема: 8 потоков были не лучше 4. Затем я прочитал материал SMT (Intel Hyperthreading) и выяснил проблему и решение:

Удалите следующие строки в методе слияния:

if (Runtime.getRuntime (). FreeMemory () <((n1 + n2) * 4)) Runtime.getRuntime ().gc (); </p>

Этот код освобождает память от уровней L1 и L2 физических ядер, но в этих килобайтах у нас есть буферы для двух логических потоков (не только одного), поэтому один поток стираетбуфер родственного потока в этом физическом ядре.

После удаления этого , если , я увидел улучшение 1.25 между 4 и 8 потоками, которые обеспечивает SMT.Если кто-то может попробовать это на i5, это было бы здорово.