Стратегия параллельной реализации алгоритма пересечения деревьев?

Question

Я реализовал итерационный алгоритм, где каждая итерация включает в себя обход дерева предзаказов (иногда называемый вниз накоплением), за которым следует обход дерева после заказа (вверх накопление). Каждое посещение каждого узла включает в себя вычисление и хранение информации, которая будет использоваться для следующего посещения (либо в последующем последующем обходе, либо в последующей итерации).

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

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

Интенсивность вычислений на каждом узле одинакова по дереву. Вычисление на каждом узле тривиально: всего несколько сумм и умножение/деление на список чисел с длиной, равной числу детей в узле.

Обработанные деревья неуравновешены: типичный узел будет иметь 2 листа плюс 0-6 дополнительных дочерних узлов. Таким образом, простое разбиение дерева на множество относительно сбалансированных поддеревьев неочевидно (для меня). Кроме того, деревья предназначены для использования всей доступной оперативной памяти: большее дерево, которое я могу обработать, тем лучше.

Моя серийная реализация достигает порядка 1000 итераций в секунду только на моих маленьких тестовых деревьях; с «реальными» деревьями, я ожидаю, что он может замедляться на порядок (или больше?). Учитывая, что для достижения приемлемого результата для алгоритма требуется не менее 100 миллионов итераций (возможно, до миллиарда), я хотел бы распараллелить алгоритм, чтобы воспользоваться преимуществами нескольких ядер. У меня нет опыта параллельного программирования.

Каков рекомендуемый шаблон для распараллеливания с учетом характера моего алгоритма?

Answer 1

Попробуйте переписать алгоритм, который будет состоять из pure functions. Это означает, что каждая часть кода представляет собой (небольшую) статическую функцию, не зависящую от глобальных переменных или статических переменных, и что все данные обрабатываются как неизменные - изменения производятся только для копий --- и все функции управляются только (в свободном смысле слова «манипулировать»), возвращая (новые) данные.

Если каждая функция referentially transparent --- она ​​зависит только от ее ввода (и не скрытого состояния), чтобы вычислить ее выход, и каждый вызов функции с одним и тем же входом всегда дает тот же результат - тогда вы находитесь в Хорошая позиция для параллелизации алгоритма: поскольку ваш код никогда не мутирует глобальные переменные (или файлы, серверы и т. д.) работа, которую функция выполняет, может быть безопасно повторена (для пересчета результата функции) или полностью игнорируется (будущий код не зависит от побочных эффектов этой функции, поэтому пропуская вызов полностью не сломает ничего). Затем, когда вы запускаете свой набор функций (например, при некоторой реализации MapReduce, hadoop и т. Д.), Цепочка функций вызовет магический каскад зависимостей, основанный исключительно на выходе одной функции и на входе другой функции, а WHAT вы пытаетесь вычислить (через чистые функции), будет полностью отделен от ORDER, в котором вы пытаетесь его вычислить (вопрос, на который отвечает реализация планировщика для такой структуры, как MapReduce).

Отличное место для изучения этого способа мышления - написать свой алгоритм на языке программирования Haskell (или что-то F # или Ocaml), которое отлично поддерживает параллельное/многоядерное программирование, из коробки. Haskell заставляет ваш код быть чистым, поэтому, если ваш алгоритм работает, он, вероятно, легко распараллеливается.

Answer 2

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

Answer 3

В этом ответе описывается, как я буду делать это с помощью параллельного языка и системы времени выполнения, с которой я работаю изо дня в день, Charm++. Обратите внимание, что язык, используемый для последовательного кода в этой структуре, является C или C++, поэтому вам придется приложить некоторые усилия для переноса вычислительного кода. У Charm ++ есть некоторые механизмы для взаимодействия с кодом Python, хотя я менее знаком с этими аспектами. Возможно, вы могли сохранить код драйвера и интерфейса в Python и просто поместить тяжелый вычислительный код в C++. Несмотря на это, усилия по портированию последовательного кода, вероятно, принесут вам хороший следующий прирост производительности.

Дизайн:

Создать массив параллельных объектов (так называемый chares в нашей среде), и назначить каждому из рабочего списка интерьерных дерева узлов, начиная с некоторого поддерева корня и простирающихся partways вниз. Любые листья, прикрепленные к этим узлам, также относятся к этой чаре.

Каждый параллельный объект будет нуждаться в двух асинхронных дистанционно Invocable методов, известных как методов ввода, passDown(float a, float b) и passUp(int nodeID, float f), которые были бы точки связи между ними. passDown будет вызывать любой метод узла, который будет использоваться для вычисления предварительного заказа, а узлы, у которых есть дочерние объекты, будут вызывать passDown для этих объектов-потомков.

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

Время воспроизведения результатов:

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

Tuning:

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

1. Downward работы, что это ненулевая
   • Ближе к корню идет быстрее
2. Восходящий работы
   • ближе к листьям идет рано

Charm ++ работает с инструментом анализа производительности, известным как Projections, чтобы получить более полное представление о том, как работает ваша программа.