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

Question

http://pastebin.com/YMS4ehRj

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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