Алгоритм PRAM (параллельный) для сортировки слиянием

Я как раз читал Многопоточная сортировка слиянием в 3-м издании «Введение в алгоритм». Однако меня смущает количество процессоров, необходимых для следующего алгоритма Merge-Sort:

MERGE-SORT(A, p, r)
1 if p < r
2 q = (p+r)/2
3 spawn MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 sync
6 MERGE(A, p, q, r)

MERGE — это стандартный алгоритм слияния. Какое количество процессоров требуется для этого алгоритма?? Хотя я предполагаю, что это должно быть O (N), но в книге утверждается, что это O (log n), почему? Обратите внимание, что я не использую многопоточную процедуру MERGE. объяснение с примером будет действительно полезно. Заранее спасибо.


algorithm mergesort
person The Sage    schedule 18.05.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Значение O(log n) — это не количество процессоров, «необходимых» для запуска алгоритма, а фактический «параллелизм», достигнутый алгоритмом. Поскольку сам MERGE не распараллелен, вы не получите всех преимуществ, если процессоры O(n), даже если они все доступны.

То есть однопоточная последовательная временная сложность сортировки слиянием составляет O(n log n). Вы можете думать о «n» как о стоимости слияния, а «log n» — как о факторе, который учитывается при рекурсивных вызовах сортировки слиянием, чтобы довести массив до стадии, на которой вы можете его объединить. Когда вы распараллеливаете рекурсию, но слияние по-прежнему является последовательным, вы сохраняете коэффициент O (log n), но коэффициент O (n) остается. Следовательно, параллелизм имеет порядок O(log n), когда у вас достаточно доступных процессоров, но вы не можете достичь O(n).

Другими словами, даже если у вас есть O(n) доступных ЦП, большинство из них очень скоро простаивают, и все меньше и меньше ЦП работает, когда начинают происходить большие MERGE.

person Antti Huima    schedule 18.05.2012
comment
Я понял, что O (log n) - это параллелизм. Но после описания этого алгоритма в книге было сказано, что этот алгоритм будет достигать линейного ускорения, и из определения, если он достигнет линейного ускорения, тогда количество процессоров равно O (log n), поскольку Tp = O (n), так что это оптимал работы. Хотя позже в книге был представлен алгоритм с Tp = O ((log n) ^ 3), где параллелизм равен O (n / (log n) ^ 2). Но мой вопрос не о параллелизме! - person The Sage; 18.05.2012
comment
Алгоритм O(lg3 n) — это алгоритм, в котором MERGE также распараллелен. Но вы сами ответили на вопрос. Поскольку вы можете исключить фактор O(log n) только за счет параллелизма, достаточно иметь O(log n) параллельных выполнений = ЦП, чтобы получить максимальную выгоду (без параллельного MERGE). - person Antti Huima; 18.05.2012
comment
Итак, с глубиной рекурсии мы используем только количество процессоров O (log n), чтобы решить ее за время Tp = O (n). Таким образом, p * Tp = O (n log n). Спасибо :) - person The Sage; 18.05.2012
comment
У меня есть еще один вопрос. В чем разница между моделью в этой книге и моделью PRAM?? - person The Sage; 18.05.2012