Эффективность параллельного
метода быстрой сортировки, как и в последовательном
варианте, во многом зависит от правильности выбора значений ведущих элементов.
Определение общего правила для выбора этих значений представляется
затруднительным. Сложность такого выбора может быть снижена, если выполнить
упорядочение локальных блоков процессоров перед началом сортировки и обеспечить однородное распределение
сортируемых данных между процессорами вычислительной
системы.
Оценим трудоемкость алгоритма быстрой сортировки по частям:
-Время выполнения параллельного алгоритма, связанное непосредственно
с вычислениями:
[2(n/p)(log₂p) + (n/p)log₂ (n/p)]*t, где t- время
выполнения базовой операции перестановки.
-Длительность выполнения операции
сбора данных определяется при помощи следующего выражения:
(α+w/β)(log₂p)^2 + (α+w(n/2p)/β)(log₂p), где α -
латентность, β - пропускная способность сети, а w – размер элемента набора в
байтах
Таким образом, общее время выполнения параллельного
алгоритма составляет:
[2(n/p)(log₂p) + (n/p)log₂(n/p)]*t + (α+w/β)(log₂p)^2 +
(α+w(n/2p)/β)(log₂p).
