Подтвердить что ты не робот

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

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

Мой первый вопрос: параллельные версии алгоритмов сортировки, полезные в реальном мире, или они в основном академические? Если они полезны, где они полезны? Я лично редко использовал их в своей работе, просто потому, что я обычно привязывал все свои ядра на 100%, используя намного более крупный уровень parallelism, чем один вызов 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(), перехватывает другие задания из пула и делает их до тех пор, пока не будет завершен ожидающий. Если задача не запущена, она завершается в текущем потоке. Это означает, что ожидание не является неэффективным. Пока есть работа, все потоки будут заняты.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

  • подумайте о коде интерфейса, где вам нужно отсортировать большой динамический список строк на основе контекста.
  • Подумайте, что-то вроде barnes-hut n-body sim, где вам нужно отсортировать частицы.

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

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

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

Ответ 2

Я не эксперт, но... вот что я посмотрю:

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

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

Другие настройки:

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

Ответ 3

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

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

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

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

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

Ответ 4

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

В любом случае...

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

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

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

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

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

Ответ 5

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

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

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