Стратегия реализации алгоритма обхода дерева параллельно?

Question

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

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

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

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

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

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

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

Answer 1

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

Если каждая функция относительно прозрачна --- это зависит только от ее входа (и без скрытого состояния) для вычисления ее выхода, и каждый вызов функции с одним и тем же входом всегда дает один и тот же вывод-- - тогда у вас есть все возможности для распараллеливания алгоритма: поскольку ваш код никогда не изменяет глобальные переменные (или файлы, серверы и т. д.), работу, которую выполняет функция, можно безопасно повторить (пересчитать результат функции) или полностью игнорировать (нет будущий код зависит от побочных эффектов этой функции, поэтому полное пропуск вызова ничего не сломает). Затем при запуске набора функций (например, в некоторых реализациях MapReduce , hadoop и т. Д.) Цепочка функций вызовет магический каскад зависимостей, основанный исключительно на выходных данных. одной функции и ввод другой функции, и то, ЧТО вы пытаетесь вычислить (с помощью чистых функций), будет полностью отделено от ЗАКАЗА, в котором вы пытаетесь его вычислить (вопрос, на который ответила реализация планировщика для фреймворка как MapReduce).

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

Answer 2

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

Конструкция:

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

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

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

Результаты выполнения:

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

Настройка:

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

1. Нисходящая работа, которая не равна нулю
   • Ближе к руту идет раньше
2. Работа наверх
   • Ближе к листьям идет раньше

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

Answer 3

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