(Когда) параллельные виды практичны и как Вы пишете эффективный?
Я работаю над библиотекой распараллеливания для языка программирования D. Теперь, когда я довольно доволен основными примитивами (найдите что-либо подобное foreach, карте, уменьшите и задачи/фьючерсы), я начинаю думать о некоторых высокоуровневых параллельных алгоритмах. Среди более очевидных кандидатов на распараллеливание сортирует.
Мой первый вопрос, параллелизированные версии сортировки алгоритмов, полезных в реальном мире, или действительно ли они являются главным образом академическими? Если они полезны, где они полезны? Я лично редко использовал бы их в своей работе, просто потому что я обычно привязываю все свои ядра в 100% с помощью намного более грубого гранулярного уровня параллелизма, чем единственный вид () вызов.
Во-вторых, кажется, что быстрая сортировка почти смущающе параллельна для больших массивов, все же я не могу получить почти линейные ускорения, я полагаю, что должен добираться. Для быстрой сортировки единственная по сути последовательная часть является первым разделом. Я пытался параллелизировать быструю сортировку, после каждого раздела, сортируя эти два подмассива параллельно. В упрощенном псевдокоде:
// 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() крадет другие задания от пула и делает их до того, на котором он ожидает, сделан. Если задача не запускается, она завершается в текущем потоке. Это означает, что ожидание не неэффективно. Пока существует работа, которая будет сделана, все потоки будут заставлены напряженно трудиться.
3 ответа
Имейте в виду, что я не эксперт по параллельной сортировке, и люди делают исследовательскую карьеру параллельной сортировкой, но ...
1) они они пригодятся в реальном мире.
Конечно, они есть, если вам нужно отсортировать что-то дорогое (например, строки или что-то еще хуже), и вы не привязываете все ядра.
- подумайте о коде пользовательского интерфейса, в котором вам нужно отсортировать большой динамический список строк на основе контекста
- подумайте о чем-то вроде симулятора n-body хижины сарая, в котором вам нужно отсортировать частицы
2) Быстрая сортировка выглядит так даст линейное ускорение, но это не так. Шаг разделения - это последовательное узкое место, вы увидите это, если профилируете, и он будет иметь тенденцию ограничиваться в 2-3 раза на четырехъядерном процессоре.
Если вы хотите получить хорошее ускорение в системе меньшего размера, вам необходимо убедиться, что накладные расходы на каждую задачу действительно малы, и в идеале вам нужно убедиться, что у вас не слишком много запущенных потоков, т. Е. Не намного больше, чем 2 на двухъядерном. Пул потоков, вероятно, неправильная абстракция.
Если вы хотите получить хорошее ускорение в более крупной системе, вам нужно взглянуть на параллельные сортировки на основе сканирования, по этому поводу есть статьи. bitonic sort также довольно легко распараллелить, как и сортировку слиянием. Также может быть полезна параллельная сортировка по основанию, она есть в PPL (если вы не против Visual Studio 11).
Я не эксперт , но ... вот что я бы посмотрел:
Прежде всего, я слышал что, как показывает опыт, алгоритмы, которые с самого начала рассматривают мелкие части проблемы, как правило, лучше работают как параллельные алгоритмы.
Рассматривая вашу реализацию, попробуйте переключить параллельный / последовательный режим в другую сторону: разделите массив и выполните параллельную сортировку до тех пор, пока у вас не будет N сегментов, а затем перейдите в последовательный режим. Если вы более или менее захватываете новый поток для каждого параллельного случая, тогда N должно быть ~ вашим числом ядер. OTOH, если ваш пул потоков имеет фиксированный размер и действует как очередь недолговечных делегатов, тогда я бы использовал N ~ 2+ раз больше вашего количества ядер (чтобы ядра не простаивали, потому что один раздел завершился быстрее).
Другие настройки:
- пропустить
myTask.wait ();на локальном уровне и вместо этого иметь функцию-оболочку, которая ожидает выполнения всех задач. - Сделайте отдельную последовательную реализацию функции, которая избегает проверки глубины.
«Мой первый вопрос: полезны ли распараллеленные версии алгоритмов сортировки в реальном мире?» - зависит от размера набора данных, с которым вы работаете в реальной работе. Для небольших наборов данных ответ отрицательный. Для больших наборов данных это зависит не только от размера набора данных, но и от конкретной архитектуры системы.
Одним из ограничивающих факторов, препятствующих ожидаемому увеличению производительности, является структура кэш-памяти системы. Если данные могут поместиться в кэш L1 ядра, то сортировка по нескольким ядрам мало что дает, поскольку вы получаете штраф в виде промаха кэша L1 между каждой итерацией алгоритма сортировки.
Те же рассуждения применимы к микросхемам, которые имеют несколько кэшей L2 и архитектуру NUMA (неравномерный доступ к памяти). Таким образом, чем больше ядер вы хотите распределить по сортировке, тем больше потребуется константа smallestToParallelize.
Другой ограничивающий фактор, который вы определили, - это доступ к разделяемой памяти или конкуренция по шине памяти. Поскольку шина памяти может удовлетворить только определенное количество обращений к памяти в секунду; наличие дополнительных ядер, которые по сути ничего не делают, кроме чтения и записи в основную память, сильно нагружает систему памяти.
Последний фактор, на который я должен обратить внимание, - это сам пул потоков, поскольку он может быть не таким эффективным, как вы думаете.Поскольку у вас есть потоки, которые крадут и генерируют работу из общей очереди, эта очередь требует методов синхронизации; и в зависимости от того, как они реализованы, они могут вызывать очень длинные последовательные секции в вашем коде.