Стратегия реализовать алгоритм пересекающего дерева параллельно?
Я реализовал итеративный алгоритм, где каждое повторение включает обход дерева предзаказа (иногда называемый вниз накопление) сопровождаемый обходом дерева постпорядка (вверх накопление). Каждое посещение каждого узла включает вычисление и хранить информацию, которая будет использоваться для следующего посещения (или в последующем обходе постпорядка или в последующем повторении).
Во время обхода предзаказа каждый узел может быть обработан независимо, пока все узлы между ним и корнем были уже обработаны. После обработки каждый узел должен передать кортеж (а именно, два плавания) каждому из его детей. На обходе постпорядка каждый узел может быть обработан независимо пока весь, он - поддеревья (если таковые имеются), были уже обработаны. После обработки каждый узел должен передать единственное плавание своему родителю.
Структура деревьев статична и неизменна во время алгоритма. Однако в ходе нисходящего обхода, если два плавания, передаваемые оба, становятся нулем, все поддерево под этим узлом не должно быть обработано, и вверх, обход для этого узла может начаться. (Поддерево должно быть сохранено, потому что переданные плавания на последующих повторениях могут стать ненулевыми в этом узле, и обходы возобновились бы).
Интенсивность вычисления в каждом узле является тем же через дерево. Вычисление в каждом узле тривиально: Всего несколько сумм и умножаются/делят в списке чисел с длиной, равной числу детей в узле.
Обрабатываемые деревья являются несбалансированными: типичный узел имел бы 2 листа плюс 0-6 дополнительных дочерних узлов. Так, просто разделение дерева в ряд относительно сбалансированных поддеревьев неочевидно (для меня). Далее, деревья разработаны для потребления всей доступной RAM: чем большее дерево, которое я могу обработать, тем лучше.
Моя последовательная реализация достигает на порядке 1 000 повторений в секунду на просто моих небольших тестовых деревьях; с "реальными" деревьями я ожидаю, что это могло бы замедлиться порядком величины (или больше?). Учитывая, что алгоритм требует, чтобы по крайней мере 100 миллионов повторений (возможно до миллиарда) достигли приемлемого результата, я хотел бы параллелизировать алгоритм для использования в своих интересах нескольких ядер. У меня есть нулевой опыт с параллельным программированием.
Каков рекомендуемый шаблон для распараллеливания, учитывая природу моего алгоритма?
3 ответа
Попробуйте переписать свой алгоритм, чтобы он состоял из чистых функций . Это означает, что каждый фрагмент кода представляет собой (небольшую) статическую функцию, не зависящую от глобальных переменных или статических переменных, и что все данные обрабатываются как неизменяемые --- изменения вносятся только в копии --- и все функции только манипулируют состояние (в широком смысле слова «манипулировать»), возвращая (новые) данные.
Если каждая функция ссылочно прозрачна --- это зависит только от ее ввода (и отсутствия скрытого состояния) для вычисления ее вывода, и каждый вызов функции с одним и тем же вводом всегда дает один и тот же вывод - - тогда у вас есть хорошие возможности для распараллеливания алгоритма: поскольку ваш код никогда не изменяет глобальные переменные (или файлы, серверы и т. д.), работа, которую выполняет функция, может быть безопасно повторена (для пересчета результата функции) или полностью проигнорирована (нет будущий код зависит от побочных эффектов этой функции, поэтому полный пропуск вызова ничего не сломает). Затем, когда вы запускаете свой набор функций (например, в некоторой реализации MapReduce , hadoop и т. Д.), Цепочка функций вызовет волшебный каскад зависимостей, основанный исключительно на выходных данных. одной функции и ввода другой функции, и то, ЧТО вы пытаетесь вычислить (через чистые функции), будет полностью отделено от ПОРЯДОК, в котором вы пытаетесь его вычислить (вопрос, на который отвечает реализация планировщика для фреймворка как MapReduce).
Отличное место для изучения этого способа мышления - написать свой алгоритм на языке программирования Haskell (или что-то в этом роде, F # или Ocaml), который имеет отличную поддержку параллельного / многоядерного программирования прямо из коробки. Haskell заставляет ваш код быть чистым, поэтому, если ваш алгоритм работает, его, вероятно, легко распараллелить.
Обычный метод заключается в использовании некоего глубинного раскола. Вы начинаете с того, что несколько рабочих ожидают в очереди, а один рабочий начинает обход в корне. Рабочий с работой сначала проходит по глубине, и всякий раз, когда он находится в узле с более чем одним ребенком, он проверяет очередь простаивающих рабочих и, если она не пустая, передает поддеревку (ребенка) другому рабочему. Есть некоторые сложности при соединении, когда работник заканчивает поддерево, но в целом это может хорошо работать для различных древовидных структур (сбалансированных или несбалансированных)
.В этом ответе описывается, как я бы сделал это с параллельным языком и системой времени выполнения, над которой я работаю ежедневно, Charm ++ . Обратите внимание, что язык, используемый для последовательного кода в этой структуре, - C или C ++, поэтому вам придется приложить некоторые усилия для переноса вычислительного кода.Charm ++ имеет некоторые механизмы взаимодействия с кодом Python, хотя я менее знаком с этими аспектами. Возможно, вы могли бы сохранить код драйвера и интерфейса на Python и просто поместить тяжелый вычислительный код на C ++. Как бы то ни было, портирование последовательного кода, скорее всего, даст вам хороший следующий прирост производительности.
Дизайн:
Создайте массив параллельных объектов (в нашей среде называемый chares ) и назначьте каждому рабочий список узлов внутреннего дерева, начинающихся с некоторого корня поддерева и частично продолжающихся вниз. Любые листья, прикрепленные к этим узлам, также будут принадлежать этому chare.
Каждому параллельному объекту потребуются два асинхронных удаленно вызываемых метода, известных как методы входа , passDown (float a, float b) и passUp (int nodeID, float f ) , которые были бы точками общения между ними. passDown будет вызывать любой метод узла, используемый для выполнения вычислений предварительного порядка, а узлы, у которых есть дочерние элементы вне объекта, будут вызывать passDown для этих дочерних объектов.
Как только вся работа, направленная вниз, будет выполнена, объект вычислит работу вверх на своих листьях и будет ждать своих потомков. Вызов passUp будет вычислять как можно дальше в дереве получающих объектов, пока не попадет в родительский объект, который не получил данные от всех своих дочерних элементов. Когда корневой узел объекта завершит работу вверх, он вызовет passUp для объекта, содержащего родительский узел. Когда корень всего дерева готов, вы знаете, что итерация завершена.
Результаты выполнения:
Как только это будет реализовано, система времени выполнения выполнит параллельное выполнение за вас. Он распределяет объекты между процессорами и даже между отдельными вычислительными узлами (что значительно увеличивает потолок размера вашего дерева, поскольку доступная память может масштабироваться намного выше). Связь между процессорами и узлами выглядит так же, как внутрипроцессное взаимодействие - вызовы асинхронных методов. Среда выполнения может балансировать нагрузку на объекты, чтобы все ваши процессоры были заняты на протяжении как можно большей части каждой итерации.
Настройка:
Если вы пойдете этим путем и дойдете до точки настройки параллельной производительности, вы также можете установить приоритеты для сообщений, чтобы сократить критическую длину пути. Совершенно неожиданно предлагаемая приоритезация будет работать в следующем порядке
- Работа в нисходящем направлении, отличная от нуля
- Ближе к корню идет быстрее
- Работа наверх
- Ближе к выходу идет быстрее
Charm ++ работает с инструментом анализа производительности, известным как Проекции, чтобы лучше понять, как работает ваша программа.