Параллельный BGL содержит четыреминимальных пролетных дерева.Алгоритмы[DG98]для использования на ненаправленных, взвешенных, распределенных графиках. Графики не обязательно должны быть подключены: каждый алгоритм будет вычислять минимальный охват леса (MSF) при условии наличия несвязанного графа.
Интерфейс каждого из четырех алгоритмов аналогичен реализации алгоритма Крускаля в последовательном BGL. Каждый принимает, как минимум, график, карту веса и итератор вывода. Края MST (или MSF) будут выводиться через итератор вывода на процессе 0: другие процессы могут получать края на своих итераторах вывода, но набор может быть не полным, в зависимости от алгоритма. Параметры алгоритма задокументированы вместе, потому что они не сильно различаются. Смотрите разделВыбор алгоритма MSTСоветы по выбору алгоритма.
График должен смоделироватьГрафик списка VertexКонцепт и концепция Распределенного Графа Края. Поскольку наиболее распространенная распределенная графовая структура,распределённый список смежностей, только моделирует концепцию Распределённого графа списка Vertex, он может использоваться с этими алгоритмами только при обертывании в подходящий адаптер, такой какvertex_list_adaptor..
The output iterator through which the edges of the MSF will be
written. Must be capable of accepting edge descriptors for output.
IN: VertexIndexMapindex
A mapping from vertex descriptors to indices in the range [0,
num_vertices(g)). This must be a Readable Property Map whose
key type is a vertex descriptor and whose value type is an integral
type, typically the vertices_size_type of the graph.
Default:get(vertex_index,g)
IN/UTIL: RankMaprank_map
Stores the rank of each vertex, which is used for maintaining
union-find data structures. This must be a Read/Write Property Map
whose key type is a vertex descriptor and whose value type is an
integral type.
Default: An iterator_property_map built from an STL vector
of the vertices_size_type of the graph and the vertex index map.
IN/UTIL: ParentMapparent_map
Stores the parent (representative) of each vertex, which is used for
maintaining union-find data structures. This must be a Read/Write
Property Map whose key type is a vertex descriptor and whose value
type is also a vertex descriptor.
Default: An iterator_property_map built from an STL vector
of the vertex_descriptor of the graph and the vertex index map.
IN/UTIL: SupervertexMapsupervertex_map
Stores the supervertex index of each vertex, which is used for
maintaining the supervertex list data structures. This must be a
Read/Write Property Map whose key type is a vertex descriptor and
whose value type is an integral type.
Default: An iterator_property_map built from an STL vector
of the vertices_size_type of the graph and the vertex index map.
Плотный алгоритм распределенного минимального пролетного дерева Борувки представляет собой прямую параллелизацию последовательного алгоритма MST Борувки. Алгоритм сначала создаетсупервертексиз каждой вершины. Затем, в каждой итерации, он находит наименьший вес краевого инцидента к каждой вершине, разрушает супервертикали вдоль этих краев и удаляет все самопетли. Единственное различие между последовательными и параллельными алгоритмами заключается в том, что параллельный алгоритм выполняет операцию полного сокращения, так что все процессы имеют глобальный минимальный набор краев.
В отличие от других трех алгоритмов, этот алгоритм излучает полный список краев в минимальном лесу через итератор вывода на всех процессах. Следовательно, он может быть более полезным, чем другие, при параллелизации последовательных программ BGL.
Следующие диаграммы иллюстрируют производительность этого алгоритма на различных случайных графиках. Мы видим, что алгоритм масштабирует до 64 или 128 процессоров, в зависимости от типа графа, для плотных графов. Однако для разреженных графов производительность сужается по мере того, как число процессоров сужаетсям/н, т.е. средняя степень (что составляет 30 для этого графа). Такое поведение ожидается от алгоритма.
Сливающийся локальный алгоритм MST работает, вычисляя минимум лесов с краев, хранящихся в каждом процессе. Затем процессы сливаются их краевые списки вдоль дерева. Узлы ребенка перестают участвовать в вычислениях, но родительские узлы пересчитывают MSF из вновь приобретенных краев. В заключительном раунде корень дерева вычисляет глобальные MSF, получая кромки кандидатов от каждого другого процесса через дерево.
Этот алгоритм требуетO(log_D p)Сверхшаги BSP (гдеD- это число детей на дереве, и в настоящее время фиксируется на уровне 3). Каждый супершаг требуетO((m/p) log (m/p) + n)времени иO(m/p)связи в процессе.
Следующие диаграммы иллюстрируют производительность этого алгоритма на различных случайных графиках. Алгоритм хорошо масштабируется только для очень плотных графиков, где большая часть работы выполняется на начальной стадии, а на более поздних стадиях очень мало работы.
Этот алгоритм применяет как этапы Борувки, так и локальные этапы слияния MSF для достижения лучшей асимптотической производительности, чем любой другой алгоритм. Сначала он выполняет шаги Борувки до тех пор, пока не останутся толькоn/(log_d p)^2супервертикали, а затем завершает вычисление MSF, выполняя локальное слияние MSF на оставшихся краях и супервертикалях.
Этот алгоритм требуетlog_D p+log log_D pсупершагов BSP. Время, необходимое для каждого супершага, зависит от типа выполняемого супершага; см. Распределенная Борувка или слияние локальных алгоритмов MSFS для деталей.
Следующие диаграммы иллюстрируют производительность этого алгоритма на различных случайных графиках. Мы видим, что алгоритм масштабирует до 64 или 128 процессоров, в зависимости от типа графа, для плотных графов. Однако для разреженных графов производительность сужается по мере того, как число процессоров сужаетсям/н, т.е. средняя степень (что составляет 30 для этого графа). Такое поведение ожидается от алгоритма.
Этот алгоритм применяет как этапы Борувки, так и локальные этапы слияния MSF для достижения лучшей асимптотической производительности, чем любой другой метод. В каждой итерации алгоритм сначала выполняет этап Борувки, а затем объединяет локальные MSF, вычисленные на основе графа супервертекса.
Этот алгоритм требуетlog_D pсупершагов BSP. Время, необходимое для каждого супершага, зависит от типа выполняемого супершага; см. Распределенная Борувка или слияние локальных алгоритмов MSFS для деталей. Однако алгоритм является коммуникационно-необязательным (требующимO(n)связи в целом), когда график достаточно плотный, то естьm/n >= p.
Следующие диаграммы иллюстрируют производительность этого алгоритма на различных случайных графиках. Мы видим, что алгоритм масштабирует до 64 или 128 процессоров, в зависимости от типа графа, для плотных графов. Однако для разреженных графов производительность сужается по мере того, как число процессоров сужаетсям/н, т.е. средняя степень (что составляет 30 для этого графа). Такое поведение ожидается от алгоритма.
Дене и Готц сообщили[DG98]о смешанных результатах при оценке этих четырех алгоритмов. Ни один конкретный алгоритм не был лучше других во всех случаях. Однако асимптотически лучший алгоритмboruvka_mixed_merge, казалось, выполнялся в своих тестах хуже, чем другие алгоритмы, основанные на слиянии. Следующие диаграммы производительности иллюстрируют производительность этих четырех минимальных реализаций дерева охвата.
В целом,dense_boruvka_minimum_spanning_treeдает наиболее последовательную производительность и масштабируемость для графов, которые мы тестировали. Кроме того, он может быть более подходящим для последовательных программ, которые распараллеливаются, потому что он испускает полные списки краев MSF через итераторы вывода в каждом процессе.
Copyright (C) 2004 Попечители Университета Индианы.
Авторы: Дуглас Грегор и Эндрю Лумсдейн
[DG98]
1,2Фрэнк Дене и Сильвия Готц.Практические параллельные алгоритмы для минимальных деревьев. Symposium on Reliable Distributed Systems, pages 366-371, 1998.
Статья Parallel BGL Minimum Spanning Tree раздела может быть полезна для разработчиков на c++ и boost.
