Ускорение сверхлинейного алгоритма быстрой сортировки

Question

Я реализовал как последовательную версию, так и параллельную версию quicksort.

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

Итак, раздел генерирует два набора, один из которых содержит элементы, меньшие, чем опорный, а другой с элементами, превышающими вершину, а именно n - 1 элементов, где n - количество элементов массива, передаваемых в качестве аргумента quicksort функция. Глубина рекурсии имеет размер N -1, где N - количество элементов исходного массива, переданных как аргумент для функции quicksort.

Обс: Наборы фактически представлены двумя переменными, содержащими начальное и конечное положение части массива, которая соответствует либо элементам меньше, чем точка поворота, а элементы выше, чем точка поворота. Все разделение происходит на месте, что означает, что в процессе не создается новый массив. Разница последовательной параллели в параллельной версии создается более одного массива, где элементы разделяются поровну между ними (сортируется как последовательный случай). Для соединения элементов в параллельном случае использовалось слияние алгоритмов.

Полученное ускорение было выше теоретического, это означает, что с двумя потоками достигнутое достижение было более чем в 2 раза по сравнению с последовательной версией (точнее, 3 раза) и с 4-мя потоками ускорение было 10x.

Компьютер, на котором я запускал потоки, представляет собой машину с 4 ядрами (Phenom II X4) под управлением Ubuntu Linux 10.04, 64 бит, если я не ошибаюсь. Компилятор gcc 4.4 и флаги не были переданы для компилятора, за исключением включения библиотеки pthread для параллельной реализации;

Итак, кто-то знает, почему достигается сверхлинейное ускорение? Может кто-нибудь дать какой-нибудь указатель, пожалуйста?

Answer 1

Было бы действительно лучше использовать какой-то анализатор производительности копаться в этом более подробно, но мое первое предположение, что этот вид супер линейной скорости до обусловлена ​​тем, что вы получаете больше пространства кэша если вы добавляете потоки. Таким образом, из кэша будет считываться больше данных. Так как стоимость передачи данных действительно высока, это может легко улучшить производительность.

Вы используете Amdahl's law, чтобы оценить максимальное ускорение?

Надеюсь, это поможет.

Answer 2

Если вы видите 3-кратное ускорение с двумя потоками против одного и 10-кратное ускорение с четырьмя потоками против одного, происходит что-то подозрительное.

Закон Amdahl утверждает, что ускорение 1/(1-P + P/S), где P - часть параллельного алгоритма, S - коэффициент ускорения параллельной части. Предполагая, что S = 4 для четырех ядер (наилучший возможный результат), мы получаем, что P = 2.5, что невозможно (оно должно быть от 0 до 1 включительно).

Иными словами, если вы можете получить 10-кратное улучшение с 4 ядрами, то вы можете просто использовать одно ядро ​​для моделирования четырех ядер и по-прежнему получать улучшение в 2,5 раза (или около того).

Положите еще один способ, четыре ядра в течение одной секунды выполняют меньше операций, чем одно ядро ​​в течение десяти секунд.Таким образом, параллельная версия фактически выполняет меньшее количество операций, и, если это так, нет причин, по которым серийная версия не может также выполнять меньшее количество операций.

Возможные выводы:

• Что-то может быть не так с вашей последовательной версией. Возможно, он оптимизирован плохо.

• Что-то может быть не так с вашими параллельными версиями. Они могут быть неверными.

• Измерение может быть выполнено неправильно. Это довольно часто.

невыполнима выводы:

• Этот алгоритм масштабируется сверхлинейно.