Параллельная сортировка слиянием с потоками /намного/ медленнее, чем Seq. Сортировка слиянием. Помощь

http://pastebin.com/YMS4ehRj

^ Это моя реализация параллельной сортировки слиянием. В основном, что я делаю, для каждого разделения первая половина обрабатывается потоком, тогда как вторая половина является последовательной (т.е.), скажем, у нас есть массив из 9 элементов, [0..4] обрабатывается потоком 1, [0 ..1] обрабатывается потоком 2, [5..6] обрабатывается потоком 3 (см. исходный код для уточнения).

Все остальное остается прежним, как слияние. Но проблема в том, что это работает намного медленнее, чем сортировка слиянием, даже медленнее, чем обычная пузырьковая сортировка! И я имею в виду массив из 25000 целых чисел. Я не уверен, где находится узкое место: это блокировка мьютекса? Это слияние?

Любые идеи о том, как сделать это быстрее?


c pthreads parallel-processing mergesort mutex
person Ram    schedule 24.05.2011    source источник
comment
Вы не должны использовать pastebin, срок действия которого истекает через один день, для вопросов stackoverflow — это мешает кому-либо еще узнать, как решить вашу проблему на следующей неделе (или ответить на ваш вопрос завтра).   -  person Seth Robertson    schedule 24.05.2011
comment
Вы вообще не должны использовать pastebins.   -  person R.. GitHub STOP HELPING ICE    schedule 25.05.2011
comment
Не реализуйте сортировку слиянием в рекурсивном стиле, просто выполняя одни и те же биты параллельно. Когда количество подсписков сокращается, скажем, до 1000, накладные расходы на потоковые сообщения начинают приближаться ко времени, затрачиваемому на слияния, поэтому просто выполняйте быструю сортировку на месте (или что-то еще - только что видел пост - тот же момент). Кроме того, как уже говорили другие, просто поставьте свои слияния в очередь на [no. ядер] потоков или какой-либо другой реализации threadPool. Вы можете синхронизировать слияния с обратными вызовами. Если вы сделаете это, «плиточная сортировка слиянием» на 4/8-ядерном процессоре будет сортировать 1000000 целых чисел примерно в шесть раз быстрее, чем однопоточная быстрая сортировка.   -  person Martin James    schedule 25.05.2011

Ответы (3)


arrow_upward
2
arrow_downward

Вы создаете большое количество потоков, каждый из которых выполняет очень мало работы. Чтобы отсортировать 25 000 целых чисел, вы создаете около 12 500 потоков, которые порождают другие потоки и объединяют их результаты, и около 12 500 потоков, которые сортируют только два целых числа каждый.

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

Чтобы избежать этого, убедитесь, что каждый поток выполняет разумный объем работы. Например, если один поток обнаружит, что ему нужно отсортировать только ‹10000 чисел, он может просто отсортировать их самостоятельно с помощью обычной сортировки слиянием вместо того, чтобы создавать новые потоки.

person sth    schedule 24.05.2011

arrow_upward
1
arrow_downward

Учитывая, что в вашей системе конечное число ядер, зачем вам создавать больше потоков, чем ядер?

Кроме того, неясно, зачем вообще нужен мьютекс. Насколько я могу судить по быстрому сканированию, программе не нужно совместно использовать потоки[lthreadcnt] за пределами локальной функции. Просто используйте локальную переменную, и вы должны быть золотыми.

person Seth Robertson    schedule 24.05.2011
comment
Хорошая мысль. Я был поглощен этим коробочным мышлением, потому что я работаю над этим уже около 5 часов. O.o И вы делаете замечание о создании огромного количества потоков (~ 12500). Таким образом, последовательное разделение, но параллельное слияние будет быстрее? - person Ram; 24.05.2011
comment
Ну, вы могли бы сделать параллельное разделение с ограничением рекурсии (хорошо для 2 и 4 ядер, не очень хорошо для 6 или 8), но последовательное разделение, вероятно, было бы намного эффективнее. Вы также не выполняете ввод-вывод, поэтому большое количество потоков не сделает ничего более эффективным. Это может выйти далеко за рамки того, чего вы хотите, но если вы можете разделить массивы на границах строк кэша, вы, вероятно, также получите выигрыш в производительности, поскольку конкуренция обходится дорого. Однако с меньшим количеством потоков, просматривающих большие объемы данных, это менее важно. - person Seth Robertson; 24.05.2011

arrow_upward
1
arrow_downward

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

Поскольку большая часть ваших вычислений выполняется в функции merge, другим предложением является использование слияния по принципу «разделяй и властвуй» вместо простого слияния. Преимущество двоякое: время выполнения меньше, и легко создавать потоки для запуска параллельного слияния. Вы можете получить представление о том, как реализовать параллельное слияние здесь: http://drdobbs.com/high-performance-computing/229204454. У них также есть статья о параллельной сортировке слиянием, которая может быть вам полезна: http://drdobbs.com/high-performance-computing/229400239

person pad    schedule 24.05.2011