Я работаю над библиотекой распараллеливания для языка программирования D. Теперь, когда я довольно доволен базовыми примитивами (параллельный foreach, map, Reduce и tasks / futures), я начинаю думать о некоторых параллельных алгоритмах более высокого уровня. Среди наиболее очевидных кандидатов на распараллеливание - сортировка.
Мой первый вопрос: являются ли параллельные версии алгоритмов сортировки полезными в реальном мире, или они в основном академические? Если они полезны, где они полезны? Лично я редко использовал бы их в своей работе, просто потому что я обычно привязывал все свои ядра на 100%, используя гораздо более детальный уровень параллелизма, чем один вызов sort ().
Во-вторых, кажется, что быстрая сортировка почти смущающе параллельна для больших массивов, но я не могу получить почти линейные ускорения, которые, я полагаю, мне следовало бы получить. Для быстрой сортировки единственной неотъемлемой последовательной частью является первый раздел. Я попытался распараллелить быструю сортировку, отсортировав после каждого раздела два подмассива параллельно. В упрощенном псевдокоде:
// I tweaked this number a bunch. Anything smaller than this and the
// overhead is smaller than the parallelization gains.
const smallestToParallelize = 500;
void quickSort(T)(T[] array) {
if(array.length < someConstant) {
insertionSort(array);
return;
}
size_t pivotPosition = partition(array);
if(array.length >= smallestToParallelize) {
// Sort left subarray in a task pool thread.
auto myTask = taskPool.execute(quickSort(array[0..pivotPosition]));
quickSort(array[pivotPosition + 1..$]);
myTask.workWait();
} else {
// Regular serial quick sort.
quickSort(array[0..pivotPosition]);
quickSort(array[pivotPosition + 1..$]);
}
}
Даже для очень больших массивов, где время, которое занимает первый раздел, ничтожно мало, я могу получить только около 30% ускорения на двухъядерном процессоре по сравнению с чисто последовательной версией алгоритма. Я предполагаю, что узким местом является доступ к общей памяти. Любое понимание того, как устранить это узкое место или что еще может быть узким местом?
Изменить: Мой пул задач имеет фиксированное количество потоков, равное количеству ядер в системе минус 1 (поскольку основной поток также работает). Кроме того, тип ожидания, который я использую, - это ожидание работы, то есть, если задача запущена, но не завершена, поток, вызывающий workWait(), крадет другие задания из пула и выполняет их до тех пор, пока не будет выполнено ожидание. Если задача не запущена, она завершается в текущем потоке. Это означает, что ожидание не является неэффективным. Пока есть работа, все потоки будут заняты.