Как распараллелить std::partition используя TBB

Question

У кого-нибудь есть советы по эффективному распараллеливанию std::partition с использованием TBB? Это уже сделано?

Вот что я думаю:

1. если массив маленький, std:: разбить его (последовательный) и вернуть
2. иначе обрабатывать массив как 2 чередующихся массива, используя пользовательские итераторы (чередование в блоках размером с кеш)
3. запустить задачу параллельного разбиения для каждой пары итераторов (перейдите к шагу 1)
4. поменяйте местами элементы между двумя указателями раздела / середины *
5. вернуть объединенный раздел / средний указатель

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

Есть мысли, прежде чем я попробую это?

Answer 1

Я бы отнесся к этому как к вырожденному случаю параллельной выборки. (Параллельный код для сортировки образцов можно найти здесь.) Пусть N будет количеством элементов. Вырожденная сортировка образца потребует Θ(N) временного пространства, имеет Θ(N) работы и размах Θ(P+ lg N) (критический путь). Последние два значения важны для анализа, так как ускорение ограничено работой / продолжительностью.

Я предполагаю, что вход является последовательностью произвольного доступа. Шаги:

1. Выделите временный массив, достаточно большой для хранения копии входной последовательности.
2. Разделите вход на K блоков. K является параметром настройки. Для системы с P аппаратными потоками, K=max(4*P,L) может быть хорошим, где L является константой для избежания смехотворно маленьких блоков. "4*P" позволяет некоторую балансировку нагрузки.
3. Переместите каждый блок на соответствующую позицию во временном массиве и разбейте его, используя std::partition. Блоки могут обрабатываться параллельно. Запомните смещение "середины" для каждого блока. Возможно, вы захотите написать собственную подпрограмму, которая перемещает (в смысле C++11) и разделяет блок.
4. Вычислите смещение, куда каждая часть блока должна идти в конечном результате. Смещения для первой части каждого блока могут быть выполнены с использованием суммы эксклюзивного префикса для смещений середин, начиная с шага 3. Смещения для второй части каждого блока можно вычислить аналогичным образом, используя смещение каждой средней относительно конец его блока. Промежуточные суммы в последнем случае становятся смещениями от конца окончательной выходной последовательности. Если вы не имеете дело с более чем 100 аппаратными потоками, я рекомендую использовать последовательное эксклюзивное сканирование.
5. Переместите две части каждого блока из временного массива обратно в соответствующие места в исходной последовательности. Копирование каждого блока может быть сделано параллельно.

Есть способ встроить отсканированное изображение шага 4 в шаги 3 и 5, чтобы можно было уменьшить интервал до Θ (LG N), но я сомневаюсь, что это стоит дополнительной сложности.

Если вы используете циклы tbb::rallel_for для распараллеливания шагов 3 и 5, рассмотрите возможность использования affinity_partitioner, чтобы помочь потокам на шаге 5 подобрать то, что они оставили в кэше на шаге 3.

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

Answer 2

Почему бы не параллельно что-то похожее std::partition_copy вместо? Причины:

• за std::partition свопы на месте, как в решении Адама, требуют логарифмической сложности из-за рекурсивного слияния результатов.
• в любом случае вы будете платить за параллелизм при использовании потоков и задач.
• если объекты тяжелые, разумнее поменять местами указатели
• если результаты могут быть сохранены одновременно, потоки могут работать независимо.

Это довольно просто применить parallel_for (для итераторов с произвольным доступом) или tbb::parallel_for_each (для итераторов без случайного доступа), чтобы начать обработку входного диапазона. каждая задача может хранить результаты "истина" и "ложь" независимо. Есть много способов сохранить результаты, некоторые из которых мне нравятся:

• с помощью tbb::parallel_reduce (только для итераторов с произвольным доступом), сохраняйте результаты локально в теле задачи и перемещайте и добавляйте их в join() из другого задания
• использование tbb::concurrent_vector метод grow_by() скопировать локальные результаты в кучу или просто push() каждый результат отдельно по прибытии.
• кэш-поток локальных результатов в tbb::combinable Контейнер TLS и объединить их позже

Точная семантика std::partition_copy может быть достигнуто путем копирования из временного хранилища сверху или

• (только для выходных итераторов с произвольным доступом) atomic<size_t> курсоры для синхронизации места хранения результатов (при условии, что места достаточно)

Answer 3

Ваш подход должен быть правильным, но почему бы не следовать обычному методу "разделяй и властвуй" (или parallel_for)? Для двух потоков:

1. разделить массив на две части. Превратите [начало, конец) в [начало, середина), [середина, конец).
2. запустите std::partition в обоих диапазонах параллельно.
3. объединить разделенные результаты. Это можно сделать с помощью parallel_for.

Это должно лучше использовать кеш.

Answer 4

Мне кажется, что это должно хорошо распараллелить, какие-нибудь мысли, прежде чем я попробую это?

Ну... может быть несколько

• Нет реальной причины создавать больше задач, чем у вас есть ядра. Поскольку ваш алгоритм рекурсивный, вам также нужно следить за тем, чтобы не создавать дополнительные потоки, после того как вы достигнете своего предела, потому что это будет просто ненужным усилием.
• Помните, что разделение и объединение массивов отнимает у вас вычислительную мощность, поэтому установите размер разделения таким образом, чтобы на самом деле ваши вычисления не замедлялись. Разделение массива из 10 элементов может быть заманчивым, но не даст вам того, кем вы хотите быть. Поскольку сложность std::partition линейна, скорость задачи довольно легко переоценить.

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