(Когда) являются параллельными сортами практическими и как вы пишете эффективный?

Question

Я работаю над библиотекой распараллеливания для языка программирования D. Теперь, когда я очень доволен базовыми примитивами (параллельными foreach, map, reduce и задачами/фьючерсами), я начинаю думать о некоторых параллельных алгоритмах более высокого уровня. Среди наиболее очевидных кандидатов для распараллеливания - сортировка.

Мой первый вопрос заключается в параллельных версиях алгоритмов сортировки, полезных в реальном мире, или они в основном академические? Если они полезны, где они полезны? Я лично редко использовал их в своей работе, просто потому, что я обычно привязывал все свои ядра на 100%, используя гораздо более крупный уровень параллелизма, чем один вызов sort().

Во-вторых, кажется, что быстрая сортировка почти неловко параллельна для больших массивов, но я не могу получить почти линейные ускорения, которые, я считаю, должен получить. Для быстрого сортировки единственной неотъемлемой последовательной частью является первый раздел. Я попытался распараллелить быстрый сортировать, после каждого раздела, сортировать два подмассива параллельно. В упрощенном псевдокоде:

// I tweaked this number a bunch. Anything smaller than this and the 
// overhead is smaller than the parallelization gains. 
const smallestToParallelize = 500; 

void quickSort(T)(T[] array) { 
    if(array.length < someConstant) { 
     insertionSort(array); 
     return; 
    } 

    size_t pivotPosition = partition(array); 

    if(array.length >= smallestToParallelize) { 
     // Sort left subarray in a task pool thread. 
     auto myTask = taskPool.execute(quickSort(array[0..pivotPosition])); 
     quickSort(array[pivotPosition + 1..$]); 
     myTask.workWait(); 
    } else { 
     // Regular serial quick sort. 
     quickSort(array[0..pivotPosition]); 
     quickSort(array[pivotPosition + 1..$]); 
    } 
} 

Даже для очень больших массивов, где время первого раздела занимает ничтожно, я могу получить только около 30% ускорения на двухъядерном, по сравнению с чисто серийной версией алгоритма , Я предполагаю, что узким местом является доступ к общей памяти. Любое понимание того, как устранить это узкое место или что еще может быть узким местом?

Редактировать: Мой пул задач имеет фиксированное число потоков, равное количеству ядер в системе минус 1 (так как основной поток также работает). Кроме того, тип ожидания, который я использую, - это ожидание работы, то есть, если задача запущена, но не закончена, поток, вызывающий workWait(), перехватывает другие задания из пула и делает их до тех пор, пока он не будет ждать. Если задача не запущена, она завершается в текущем потоке. Это означает, что ожидание не является неэффективным. Пока есть работа, все потоки будут заняты.

Answer 1

Имейте в виду, я не эксперт по параллельной сортировки, и люди делают исследовательскую карьеру из параллельного вида, но ...

1) они полезны в реальном мире.

, конечно, они есть, если вам нужно отсортировать что-то дорогое (например, строки или что-то еще хуже), а вы не привязки всех ядер.

• думает UI кода, в котором вам нужно сортировать большой динамический список строк на основе контекста
• думать что-то вроде Барнса-хаты п тел сим, где вам нужно, чтобы отсортировать частицы

2) Quicksort похоже, что это даст линейное ускорение, но это не так. Шаг раздела является последовательным узким местом, вы увидите это, если вы профилируете, и он будет стремиться к выходу на 2-3х на четырехъядерном ядре.

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

Если вы хотите получить хорошие ускорения в более крупной системе, вам нужно будет просмотреть параллельные сорта, основанные на проверке, есть документы на этом. bitonic sort также довольно легко распараллеливается, как и сортировка слияния. Также может быть полезной параллельная сортировка радикса, она есть в PPL (если вы не против Visual Studio 11).

Answer 2

Я не эксперт, но ... вот что я хотел бы посмотреть на:

Прежде всего, я слышал, что, как правило, алгоритмы, которые смотрят на маленькие кусочки проблема с самого начала имеет тенденцию работать лучше, чем параллельные алгоритмы.

Посмотрите на свою реализацию, попробуйте сделать параллельный/последовательный коммутатор другим способом: разбить массив и отсортировать его параллельно, пока у вас нет N сегментов, а затем выполните серийный номер. Если вы более или менее захватываете новый поток для каждого параллельного случая, тогда N должен быть ~ вашим основным счетом. OTOH, если ваш пул потоков имеет фиксированный размер и действует как очередь короткоживущих делегатов, тогда я бы использовал N ~ 2+ раз больше вашего основного счета (так что ядра не сидят без дела, потому что один раздел заканчивается быстрее).

Другие твики:

• не показывать myTask.wait(); на местном уровне, а скорее имеют функцию-оболочку, которая ждет всех задач.
• Сделайте отдельную последовательную реализацию функции, которая позволяет избежать проверки глубины.

Answer 3

«Мой первый вопрос: параллельные версии алгоритмов сортировки, полезных в реальном мире» - зависит от размера набора данных, над которым вы работаете в реальной работе. Для небольших наборов данных ответ отрицательный. Для больших наборов данных это зависит не только от размера набора данных, но и от конкретной архитектуры системы.

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

Те же соображения применимы к чипам, которые имеют несколько кэшей L2 и архитектуры NUMA (неравномерный доступ к памяти). Таким образом, чем больше ядер, которые вы хотите распределить по сортировке, тем меньше должна быть увеличена минимальная константа ToParallelize.

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

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

Answer 4

Я не знаю, если ответы здесь применимы больше или, если мои предложения применимы к D.

Во всяком случае ...

Предполагая, что D позволяет, всегда есть возможность предоставления prefetch намекает на кеши. Ядро, о котором идет речь, запрашивает, чтобы данные, которые он скоро (не сразу), были загружены в определенный уровень кеша. В идеальном случае данные будут извлечены к моменту начала работы ядра. Скорее всего, процесс предварительной выборки будет более или менее на пути, который, по крайней мере, приведет к меньшему количеству состояний ожидания, чем если бы данные были получены «холодно».«

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

Код и данные должны быть организованы в соответствии с концепцией линий кэша (выборки единиц по 64 байта каждый), который является наименьшим размером в кеше. в том, что для двух ядер работа должна быть организована таким образом, чтобы система памяти работала вдвое меньше на ядро ​​(при условии 100% -ной масштабируемости), как и раньше, когда работало только одно ядро, а работа не была организована. Для четырех ядер четверть так много и т. д. Это довольно сложная задача, но отнюдь не невозможная, она просто зависит ds о том, насколько вы изобретательны в процессе реструктуризации работы. Как всегда, есть решения, которые невозможно понять ... пока кто-то это сделает!

Я не знаю, как WYSIWYG D сравнивается с C - который я использую, но в целом я думаю, что процесс разработки масштабируемых приложений улучшается тем, насколько разработчик может влиять на компилятор в его фактическом генерации машинного кода. Для интерпретируемых языков у переводчика будет так много работы с памятью, что вы рискуете не понимать отличий от общего «фонового шума».

Я как-то написал многопоточную оболочку, которая на 70% быстрее работала на двух ядрах по сравнению с одним и 100% на трех ядрах по сравнению с одним. Четыре ядра протекали медленнее, чем три. Поэтому я знаю дилеммы, с которыми вы сталкиваетесь.

Answer 5

Я хотел бы указать вам на Внешнюю сортировку [1], которая сталкивается с аналогичными проблемами. Обычно этот класс алгоритмов используется в основном для работы с большими объемами данных, но их основной задачей является то, что они разбивают большие куски на более мелкие и несвязанные проблемы, поэтому очень удобно работать параллельно. Вы «только» должны сшить частичные результаты впоследствии, что не совсем так же параллельно (но относительно дешево по сравнению с фактической сортировкой).

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

[1] http://en.wikipedia.org/wiki/External_sorting