Tree Design for Parallel Traversal

Question

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

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

Answer 1

Предположим, что дерево с (большим) числом узлов T и что дерево является статическим.

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

Интересной проблемой является знание того, через треугольники. Я предполагаю, что объемы коммуникации через корни треугольного дерева примерно такие же, как и связь для каждого листа в треугольнике.

В итоге мы получаем треугольники T/K. Предположим, что они пронумерованы в соответствии с префиксом ходьбы дерева, поэтому самый левый треугольник равен нулю, его родительский 1, и т. Д.

Вы можете распространять на узел n все треугольники, число которых по модулю N равно n.

Вы можете немного оптимизировать. Вы можете отправить самые левые треугольники P = (T/K)/N на узел 0, следующий P на узел 1, ... Предположительно, это минимизирует связь между границами треугольника, так как каждый узел владеет как большой непрерывный кусок возможно, дерево. Это также поможет, если количество связей между треугольными корнями значительно больше, чем через листья. В конце концов, вы можете отправлять большие резюме вверх и вниз по дереву.

Вы по-прежнему хотите обрабатывать куски размером K, потому что вы хотите распределить работу таким образом, чтобы средние значения равномерно распределялись по всем узлам.

Один стандартный трюк, используемый в параллельных вычислениях, является прямой репликацией всего данных. То есть вы можете отправить все дерево на каждый вычислительный узел, если он не является ginormous. Затем каждый узел может решить, какую часть дерева он хочет обработать в соответствии с вышеуказанными правилами, но он может избежать связи, когда ему нужно посмотреть на часть дерева, которое оно не имеет.