Лучший вид для многопоточных приложений

Question

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

Answer 1

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

Причина:

Сортировка слиянием разделяет проблему на отдельные меньшие задачи (меньшие массивы), а затем объединяет их.Это можно сделать в отдельных темах.

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

Answer 2

Каждый алгоритм «разделяй и властвуй» можно легко распараллелить. Сортировка слиянием и быстрая сортировка выполняются по одной и той же базовой схеме, которая может выполняться параллельно:

procedure DivideAndConquer(X)
  if X is a base case then
    Process base case X
    return

  Divide X into [Y0 … Yn[
  for Y ∈ [Y0 … Yn[ in parallel do
    DivideAndConquer(Y)

  Merge [Y0 … Yn[ back into X

В чем они отличаются, так это в быстрой сортировке, деление является сложным, а объединение - тривиальным (без операции). В случае слияния все наоборот: деление тривиально, а слияние затруднено.

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

С другой стороны, если вы будете следовать приведенной выше схеме, у вас возникнет проблема: самое первое деление и самое последнее объединение будут использовать только один процессор, а все остальные процессоры будут простаивать. Таким образом, имеет смысл распараллелить и эти операции. И здесь мы видим, что распараллеливание шага разделения в быстрой сортировке намного сложнее, чем распараллеливание шага объединения в сортировке слиянием.

Answer 3

Предполагая приличный выбор, это не так уж и отличается.

Подзадачи тривиальны для распараллеливания;они используют (в основном) раздельную память и не нуждаются в синхронизации, поэтому фактическое различие заключается в узких местах: начальный раздел быстрой сортировки по сравнению с окончательным объединением в сортировке слиянием.Пренебрежение их распараллеливанием приведет к плохим ускорениям для многих ядер или нескольких элементов (это становится заметно быстрее, чем вы думаете!).

Оба алгоритма могут эффективно распараллеливаться.См. этот документ MCSTL для некоторых экспериментальных результатов и деталей реализации.MCSTL был основой для того, что сейчас является параллельным режимом GNU C ++ std-lib.

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

Answer 4

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

Answer 5

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

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

В дополнение к этому, у любого рода есть серьезная проблема ложного обмена. Работа нескольких потоков с одними и теми же данными может (несмотря на время связи) быть медленнее, поскольку ЦП вынужден обмениваться данными и обновлять данные между несколькими ядрами. Если ваш алгоритм не сможет правильно выровнять данные, передача его различным потокам замедлит его.