В теории графов минимального остовного дерева (MST)из графика с участием а также это дерево подграф из который содержит все его вершины и имеет минимальный вес.
MST - это полезные и универсальные инструменты, используемые в самых разных практических и теоретических областях. Например, компания, которая хочет поставлять в несколько магазинов определенный продукт с одного склада, может использовать MST, исходящий на складе, для расчета кратчайших путей к каждому магазину компании. В этом случае магазины и склад представлены в виде вершин, а дороги между ними - в виде ребер. На каждом ребре обозначена длина соответствующего дорожного соединения.
Если не весит по ребрам, каждое остовное дерево имеет одинаковое количество ребер и, следовательно, одинаковый вес. В случае взвешенного по рёбрам остовное дерево, сумма весов рёбер которого является наименьшей среди всех остовных деревьев, называется минимальным остовным деревом (MST). Это не обязательно уникально. В более общем смысле, графы, которые не обязательно связаны, имеют минимальные остовные леса , которые состоят из объединения MST для каждого компонента связности .
Поскольку поиск MST является широко распространенной проблемой в теории графов, существует множество последовательных алгоритмов для ее решения. Среди них алгоритмы Прима , Крускала и Борувки , каждый из которых использует разные свойства MST. Все они работают одинаково - это подмножествоитеративно растет до тех пор, пока не будет обнаружен действительный MST. Однако, поскольку практические проблемы часто бывают довольно большими (дорожные сети иногда имеют миллиарды ребер), производительность является ключевым фактором. Один из вариантов его улучшения - распараллеливание известных алгоритмов MST . [1]
Алгоритм Прима
Этот алгоритм использует свойство сокращения MST. Ниже представлена простая реализация высокоуровневого псевдокода:
где случайная вершина в повторить раз найти самый легкий край ул но вернуть T
Каждое ребро наблюдается ровно дважды, а именно при проверке каждой из его конечных точек. Каждая вершина проверяется ровно один раз, всегокроме выбора самого светлого края на каждой итерации цикла. Этот выбор часто выполняется с использованием очереди приоритетов (PQ). Для каждого ребра не более одного уменьшения Клавиша операция ( амортизируется в), и каждая итерация цикла выполняет одну операцию deleteMin (). Таким образом , с помощью чисел Фибоначчи осыпает общее время выполнения алгоритма Прима является асимптотически в.
Важно отметить, что цикл по своей сути является последовательным и не может быть должным образом распараллелен. Это так, поскольку самый светлый край с одной конечной точкой в и дальше в может измениться с добавлением краев к . Таким образом, невозможно выполнить два выбора наиболее светлого края одновременно. Однако попытки распараллеливания все же есть .
Одна из возможных идей - использовать процессоры для поддержки доступа PQ в на машине EREW-PRAM , [2] таким образом снижая общее время работы до.
Алгоритм Крускала
Алгоритм MST Крускала использует свойство цикла MST. Ниже представлено высокоуровневое представление псевдокода.
лес с каждой вершиной в собственном поддереве foreach в порядке возрастания веса, если а также в разных поддеревьях вернуть T
Поддеревья хранятся в структурах данных union-find , поэтому проверка того, находятся ли две вершины в одном поддереве, возможна в амортизированной где - обратная функция Аккермана . Таким образом, общее время выполнения алгоритма составляет. Здесь обозначает однозначную обратную функцию Аккермана, для которой любой реалистичный ввод дает целое число меньше пяти.
Подход 1: Распараллеливание этапа сортировки
Как и в алгоритме Прима, в подходе Крускала есть компоненты, которые нельзя распараллелить в его классическом варианте. Например, определение того, находятся ли две вершины в одном поддереве, трудно распараллелить, поскольку две операции объединения могут одновременно пытаться объединить одни и те же поддеревья. На самом деле единственная возможность распараллеливания - это этап сортировки. Поскольку в оптимальном случае сортировка линейна на процессоров, общее время работы можно сократить до .
Подход 2: Фильтр-Краскал
Другой подход - изменить исходный алгоритм, увеличив более агрессивно. Эта идея была представлена Осиповым и соавт. [3] [4] Основная идея Filter-Kruskal состоит в том, чтобы разделить ребра аналогично быстрой сортировке и отфильтровать ребра, которые соединяют вершины, принадлежащие одному дереву, чтобы снизить стоимость сортировки. Ниже представлено высокоуровневое представление псевдокода.
filterKruskal (): если KruskalThreshold: вернуть краскал ( )pivot = chooseRandom ( ) , раздел ( , вращаться) filterKruskal ( ) фильтр( ) filterKruskal ( ) возврат раздел ( , вращаться): для каждого : если вес ( ) вращаться: еще возврат ( , )фильтр( ): для каждого : if find-set (u) найти-набор (v): возвращаться
Filter-Kruskal лучше подходит для распараллеливания, поскольку сортировка, разбиение и фильтрация имеют интуитивно простое распараллеливание, когда границы просто разделяются между ядрами.
Алгоритм Борувки
Основная идея алгоритма Борувки - сжатие ребер . Край сокращается путем первого удаления из графа, а затем перенаправляя каждое ребро к . Эти новые кромки сохраняют свой прежний вес. Если цель состоит не только в определении веса MST, но и в том, какие ребра он включает, необходимо отметить, между какими парами вершин было сжато ребро. Представление псевдокода высокого уровня представлено ниже.
пока для самый легкий для договор вернуть T
Возможно, что стягивания приводят к множеству ребер между парой вершин. Интуитивно понятный способ выбора самого легкого из них невозможен в. Однако, если все сокращения, имеющие общую вершину, выполняются параллельно, это выполнимо. Рекурсия останавливается, когда остается только одна вершина, что означает, что алгоритму требуется не более итераций, что приводит к общему времени выполнения в .
Распараллеливание
Одно возможное распараллеливание этого алгоритма [5] [6] [7] дает полилогарифмическую временную сложность, т.е. и существует постоянная чтобы . Здесь обозначает время выполнения для графика с края вершины на машине с процессоры. Основная идея заключается в следующем:
пока найти самые светлые падающие ребра присвоить каждой вершине соответствующий подграф // заключить контракт на каждый подграф //
Затем MST состоит из всех найденных самых светлых ребер.
Это распараллеливание использует представление графа массива смежности для . Он состоит из трех массивов - длины для вершин, длины для конечных точек каждого из края и длины для веса кромок. Теперь о вершине другой конец каждого края, инцидентный можно найти в записях между а также . Вес-я кромка в можно найти в . Тогда-я кромка в находится между вершинами а также если и только если а также .
Поиск самого легкого края инцидента
Сначала края распределяются между каждым из процессоры. В-й процессор получает края, хранящиеся между а также . Кроме того, каждому процессору необходимо знать, какой вершине принадлежат эти ребра (поскольку сохраняет только одну из конечных точек края) и сохраняет это в массиве . Получить эту информацию можно в с использованием бинарный поиск или в с помощью линейного поиска. На практике последний подход иногда оказывается быстрее, хотя асимптотически он хуже.
Теперь каждый процессор определяет самое светлое ребро, инцидентное каждой из его вершин.
найти( , ) для если если
Здесь возникает проблема: некоторые вершины обрабатываются более чем одним процессором. Возможное решение этой проблемы состоит в том, что у каждого процессора есть свой собственныймассив, который позже объединяется с другими, используя сокращение. Каждый процессор имеет не более двух вершин, которые также обрабатываются другими процессорами, и каждое сокращение выполняется за. Таким образом, общее время выполнения этого шага составляет.
Назначение подграфов вершинам
Обратите внимание на граф, состоящий исключительно из ребер, собранных на предыдущем шаге. Эти ребра направлены от вершины, к которой они наиболее легкое инцидентное ребро. Полученный граф распадается на несколько слабосвязных компонент. Цель этого шага - присвоить каждой вершине компонент, частью которого она является. Обратите внимание, что каждая вершина имеет ровно одно исходящее ребро, и поэтому каждый компонент является псевдодеревом - деревом с единственным дополнительным ребром, которое проходит параллельно самому светлому ребру в компоненте, но в противоположном направлении. Следующий код преобразует это дополнительное ребро в цикл:
параллельно для всех если
Теперь каждый компонент слабой связности представляет собой ориентированное дерево, корень которого имеет петлю . Этот корень выбран как представитель каждого компонента. Следующий код использует удвоение для присвоения каждой вершине своего представителя:
пока для всех
Теперь каждый подграф - это звезда . С некоторыми продвинутыми техниками этот шаг требует время.
Сужение подграфов
На этом шаге каждый подграф сжимается до одной вершины.
количество подграфов найти биективную функцию звездный корень
Найти биективную функцию можно в используя префиксную сумму. Поскольку теперь у нас есть новый набор вершин и ребер, массив смежности должен быть перестроен, что можно сделать с помощью Integerort на в время.
Сложность
Каждая итерация теперь требует времени и, как и в последовательном случае, есть взаимодействия, в результате чего общее время выполнения . Если эффективность алгоритма в и это относительно эффективно. Если тогда это абсолютно работоспособно.
Дальнейшие алгоритмы
Существует несколько других параллельных алгоритмов, которые решают проблему поиска MST. При линейном количестве процессоров этого можно добиться за. [8] [9] Бадер и Конг представили MST-алгоритм, который был в пять раз быстрее на восьми ядрах, чем оптимальный последовательный алгоритм. [10]
Еще одна проблема - это модель внешней памяти - есть предложенный алгоритм Дементьева и др. который, как утверждается, всего в два-пять раз медленнее, чем алгоритм, использующий только внутреннюю память [11]
Рекомендации
- ^ Сандерс; Дицфельбингер; Мартин; Мельхорн; Курт; Питер (10.06.2014). Algorithmen und Datenstrukturen Die Grundwerkzeuge . Springer Vieweg. ISBN 978-3-642-05472-3.
- ^ Бродал, Герт Стёльтинг; Träff, Джеспер Ларссон; Заролиагис, Христос Д. (1998), «Очередь с параллельным приоритетом с постоянными временными операциями», Журнал параллельных и распределенных вычислений , 49 (1): 4–21, CiteSeerX 10.1.1.48.3272 , doi : 10.1006 / jpdc.1998.1425
- ^ Осипов, Виталий; Сандерс, Питер; Синглер, Йоханнес (2009), «Алгоритм минимального остовного дерева с фильтром Краскала», Труды одиннадцатого семинара по разработке алгоритмов и экспериментам (ALENEX). Общество промышленной и прикладной математики : 52–61, CiteSeerX 10.1.1.218.2574
- ^ Сандерс, Питер. «Сценарий разработки алгоритмов» (PDF) . Домашняя страница набора для разработки алгоритмов . Проверено 25 февраля 2019 .
- ^ Сандерс, Питер. «Скрипт параллельных алгоритмов» (PDF) . Домашняя страница набора параллельных алгоритмов . Проверено 25 февраля 2019 .
- ^ Заде, Реза. «Распределенные алгоритмы и оптимизация» (PDF) . Распределенные алгоритмы и оптимизация Домашняя страница Стэнфордского университета . Проверено 25 февраля 2019 .
- ^ Чун, Солнце; Кондон, Энн (1996). «Параллельная реализация алгоритма минимального остовного дерева Бувки». Труды Международной конференции по параллельной обработке : 302–308. DOI : 10.1109 / IPPS.1996.508073 . ISBN 0-8186-7255-2.
- ^ Чонг, Ка Вонг; Хан, Ицзе; Lam, Так В (2001), "Параллельные потоки и оптимальные параллельные минимальное остовное Алгоритм дерево", Журнал Ассоциации вычислительной техники , 48 (2): 297-323, CiteSeerX 10.1.1.32.1554 , DOI : 10,1145 / 375827,375847 , MR 1868718
- ^ Петти, Сет; Рамачандрану, Виджая (2002), "Рандомизированное времени работы алгоритма оптимальной параллельной для нахождения минимального остовного леса" (PDF) , SIAM журнал по вычислениям , 31 (6): 1879-1895, DOI : 10,1137 / S0097539700371065 , MR 1954882
- ^ Бадер, Дэвид А .; Конг, Гоцзин (2006), «Быстрые алгоритмы с общей памятью для вычисления минимального остовного леса разреженных графов», Журнал параллельных и распределенных вычислений , 66 (11): 1366–1378, doi : 10.1016 / j.jpdc.2006.06. 001
- ^ Дементьев, Роман; Сандерс, Питер; Шультес, Доминик; Сибейн, Джоп Ф. (2004), "Разработка алгоритма минимального остовного дерева внешней памяти", Proc. 18-й Всемирный компьютерный конгресс IFIP, 3-я Международная конференция TC1 по теоретической информатике (TCS2004) (PDF) , стр. 195–208.