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

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

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

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

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

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

Дизайн:

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

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

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

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

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

Настройка:

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

1. Downward work that's non-zero
   • Closer to the root goes sooner
2. Upward work
   • Closer to leaves goes sooner

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