Не удается получить никакого ускорения от распараллеливания Quicksort с помощью Pthreads

Question

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

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

Мне разрешено использовать до 16 процессоров на сервере, на котором я его запускаю.

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

Все имеет смысл для меня, и сортировка работает отлично, но большее количество потоков делает ее очень медленной.

Я попытался установить минимальное количество элементов на раздел для запуска потока (например, 50000).

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

Код, который я использовал ниже.

http://pastebin.com/UaGsjcq2

Кто-нибудь знает, что я могу делать неправильно?

Answer 1

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

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

Answer 2

Я просто взгляну на ваш код.И я получил замечание.Почему вы используете блокировку?Если я понимаю, что вы делаете, что-то вроде:

quickSort(array)
{
    left, right = partition(array);
    newThread(quickSort(left));
    newThread(quickSort(right));
}

Вам не нужно блокировать.Обычно каждый вызов быстрой сортировки не обращается к другой части массива.Таким образом, обмен не связан.

Answer 3

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

Answer 4

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

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

Наконец, 16 процессоров на сервере реальны или виртуальные машины? И предназначены ли они исключительно для вашего процесса?