Параллельный алгоритм кратчайшего пути для всех пар - Parallel all-pairs shortest path algorithm - Wikipedia

Центральная проблема алгоритмической теория графов это проблема кратчайшего пути. Таким образом, проблема поиска кратчайшего пути между каждой парой узлов известна как все пары кратчайших путей (APSP) проблема. В качестве последовательные алгоритмы поскольку эта проблема часто приводит к длительному времени выполнения, параллелизм оказался полезным в этой области. В данной статье представлены два эффективных алгоритма решения этой проблемы.

Другой вариант проблемы - это задача с одним источником кратчайших путей (SSSP), которая также имеет параллельные подходы: Параллельный алгоритм кратчайшего пути с одним источником.

Определение проблемы

Позволять ${\displaystyle G=(V,E,w)}$ ориентированный граф с множеством узлов ${\displaystyle V}$ и набор ребер ${\displaystyle E\subseteq V\times V}$. Каждый край ${\displaystyle e\in E}$ имеет вес ${\displaystyle w(e)}$ назначенный. Задача задачи кратчайших путей всех пар - найти кратчайший путь между все пары узлов графа. Для того, чтобы этот путь был уникальным, необходимо, чтобы в графе не было циклов с отрицательным весом.

В оставшейся части статьи предполагается, что граф представлен с использованием матрица смежности. Мы ожидаем, что на выходе алгоритма будет матрица расстояний ${\displaystyle D}$. В ${\displaystyle D}$, каждая запись ${\displaystyle d-{i,j}}$ вес кратчайшего пути в ${\displaystyle G}$ из узла ${\displaystyle i}$ узел ${\displaystyle j}$.

В Алгоритм Флойда представленный позже может обрабатывать отрицательные веса ребер, тогда как Алгоритм Дейкстры требует, чтобы все ребра имели положительный вес.

Алгоритм Дейкстры

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

В псевдокоде такая реализация могла бы выглядеть так:

 1    func ДейкстраСССП (грамм,v) { 2        ... // здесь стандартная SSSP-реализация 3 возврат dv; 4    } 5     6    func DijkstraAPSP (грамм) { 7        D := |V| x |V| -Матрица 8 за я из 1 к |V| { 9           //D [v] обозначает v-ю строку D 10          D[v]: = DijkstraSSP (грамм,я) 11       } 12   }

В этом примере мы предполагаем, что DisjktraSSSP берет график ${\displaystyle G}$ и корневой узел ${\displaystyle v}$ в качестве входных данных. Результатом выполнения, в свою очередь, является список расстояний. ${\displaystyle d_{v}}$. В ${\displaystyle d_{v}}$, то ${\displaystyle i}$-й элемент хранит расстояние от корневого узла ${\displaystyle v}$ к узлу ${\displaystyle i}$.Поэтому список ${\displaystyle d_{v}}$ точно соответствует ${\displaystyle v}$-я строка матрицы расстояний APSP ${\displaystyle D}$.По этой причине, DijkstraAPSP перебирает все узлы графа ${\displaystyle G}$ и выполняет DisjktraSSSP с каждым в качестве корневого узла, сохраняя результаты в ${\displaystyle D}$.

Время выполнения DijkstraSSSP является ${\displaystyle O(|V|^{2})}$ поскольку мы ожидаем, что график будет представлен с использованием матрица смежности.Следовательно DijkstraAPSP имеет общее время последовательной работы ${\displaystyle O(|V|^{3})}$.

Распараллеливание до |V| процессоры

Тривиальное распараллеливание может быть получено распараллеливанием цикла DijkstraAPSP в соответствии8Однако при использовании последовательного DijkstraSSSP это ограничивает количество используемых процессоров числом итераций, выполняемых в цикле. Следовательно, для этого тривиального распараллеливания ${\displaystyle |V|}$ - это верхняя граница количества процессоров.

Например, пусть количество процессоров ${\displaystyle p}$ быть равным количеству узлов ${\displaystyle |V|}$. В результате каждый процессор выполняет DijkstraSSSP ровно один раз параллельно. Однако когда есть только, например, ${\displaystyle p={\frac {|V|}{2}}}$ доступных процессоров, каждый процессор должен выполнять DijkstraSSSP дважды.

В целом это дает время выполнения ${\displaystyle O(|V|^{2}\cdot {\frac {|V|}{p}})}$, когда ${\displaystyle |V|}$ кратно ${\displaystyle p}$Следовательно, эффективность этого распараллеливания идеальна: ${\displaystyle p}$ процессоры сокращают время выполнения в раз ${\displaystyle p}$.

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

Распараллеливание более чем |V| процессоры

Если больше чем ${\displaystyle |V|}$ процессоры должны использоваться для распараллеливания, требуется, чтобы несколько процессоров участвовали в DijkstraSSSP вычисление. По этой причине распараллеливание разделено на два уровня.

На первом уровне процессоры разделены на ${\displaystyle |V|}$ разделов - каждый раздел отвечает за вычисление одной строки матрицы расстояний ${\displaystyle D}$. Это означает, что каждый раздел должен оценивать один DijkstraSSSP выполнение с фиксированным корневым узлом. с этим определением каждый раздел имеет размер ${\displaystyle k={\frac {p}{|V|}}}$ процессоры. Разделы могут выполнять свои вычисления параллельно, поскольку результаты каждого из них не зависят друг от друга. Следовательно, распараллеливание, представленное в предыдущем разделе, соответствует размеру раздела 1 с ${\displaystyle p=|V|}$ процессоры.

Основная трудность заключается в распараллеливании нескольких процессоров, выполняющих DijkstraSSSP для одного корневого узла. Идея этого распараллеливания состоит в распределении управления списком расстояний. ${\displaystyle d_{v}}$ в ДейкстраСССП внутри раздела. Таким образом, каждый процессор в разделе несет исключительную ответственность за ${\displaystyle {\frac {|V|}{k}}}$ элементы ${\displaystyle d_{v}}$. Например, рассмотрим ${\displaystyle |V|=4}$ и ${\displaystyle p=8}$: это дает размер раздела ${\displaystyle k=2}$. В этом случае первый процессор каждого раздела отвечает за ${\displaystyle d_{v,1}}$, ${\displaystyle d_{v,2}}$ а второй процессор отвечает за ${\displaystyle d_{v,3}}$ и ${\displaystyle d_{v,4}}$. Таким образом, общие списки расстояний составляют ${\displaystyle d_{v}=[d_{v,1},d_{v,2},d_{v,3},d_{v,4}]}$.

В DijkstraSSSP алгоритм в основном состоит из повторения двух шагов: во-первых, ближайший узел ${\displaystyle x}$ в списке расстояний ${\displaystyle d_{v}}$ нужно найти. Для этого узла уже найден кратчайший путь, после чего расстояние до всех соседей ${\displaystyle x}$ должен быть скорректирован в ${\displaystyle d_{v}}$.

Эти шаги необходимо изменить следующим образом, поскольку для распараллеливания ${\displaystyle d_{v}}$ был распределен по разделу:

1. Найдите узел ${\displaystyle x}$ с кратчайшим расстоянием в ${\displaystyle d_{v}}$.
   • Каждому процессору принадлежит часть ${\displaystyle d_{v}}$: Каждый процессор ищет локальный минимум ${\displaystyle {\tilde {x}}}$ со своей стороны, например, используя линейный поиск.
   • Вычислить глобальный минимум ${\displaystyle x}$ в ${\displaystyle d_{v}}$ путем выполнения сокращение операции по всему ${\displaystyle {\tilde {x}}}$.
   • Трансляция глобального минимума ${\displaystyle x}$ ко всем узлам в разделе.
2. Отрегулируйте расстояние до всех соседей ${\displaystyle x}$ в ${\displaystyle d_{v}}$
   • Теперь каждый процессор знает ближайший глобальный узел ${\displaystyle x}$ и его расстояние. На основе этой информации настройте соседей ${\displaystyle x}$ в ${\displaystyle d_{v}}$ которые управляются соответствующим процессором.

Общее время выполнения такой итерации DijkstraSSSP выполняется разделом размера ${\displaystyle k}$ можно вывести на основе выполненных подзадач:

• Линейный поиск ${\displaystyle {\tilde {x}}}$: ${\displaystyle O({\frac {|V|}{k}})}$
• Операции широковещательной передачи и сокращения: они могут быть эффективно реализованы, например, с использованием бинонмиальных деревьев. Это дает накладные расходы на связь в размере ${\displaystyle O(\log k)}$.

За ${\displaystyle |V|}$-iterations это приводит к общему времени выполнения ${\displaystyle O(|V|({\frac {|V|}{k}}+\log k))}$.После подстановки определения ${\displaystyle k}$ это дает общее время выполнения для DijkstraAPSP: ${\displaystyle O({\frac {|V|^{3}}{p}}+\log p)}$.

Основное преимущество такого распараллеливания состоит в том, что больше не требуется, чтобы каждый процессор хранил всю матрицу смежности. Вместо этого достаточно, когда каждый процессор в разделе хранит только столбцы матрицы смежности узлов, за которые он отвечает. Учитывая размер раздела ${\displaystyle k}$, каждый процессор должен хранить только ${\displaystyle {\frac {|V|}{k}}}$ столбцы матрицы смежности. Обратной стороной, однако, является то, что такое распараллеливание сопряжено с накладными расходами на связь из-за операций сокращения и широковещательной передачи.

Пример

Граф, используемый в этом примере, представлен на изображении с четырьмя узлами.

Цель состоит в том, чтобы вычислить матрицу расстояний с ${\displaystyle p=8}$ По этой причине процессоры разделены на четыре раздела по два процессора в каждом. Для иллюстрации мы сфокусируемся на разделе, который отвечает за вычисление кратчайших путей от узла А ко всем остальным узлам. Назовем процессоры этого раздела p1 и p2.

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

Верхний ряд на изображении соответствует ${\displaystyle d_{A}}$ после инициализации нижний на ${\displaystyle d_{A}}$ после завершения алгоритма. Узлы распределяются таким образом, что p1 отвечает за узлы А и B, пока p2 Ответственный за C и D.Дистанционный список ${\displaystyle d_{A}}$ распределяется в соответствии с этим. Для второй итерации выполняемые подзадачи явно показаны на изображении:

1. Вычисление узла локального минимума в ${\displaystyle d_{A}}$
2. Вычисление узла глобального минимума в ${\displaystyle d_{A}}$ через операцию уменьшения
3. Трансляция узла глобального минимума в ${\displaystyle d_{A}}$
4. Пометка ближайшего глобального узла как завершенного и корректировка расстояния до его соседей

Алгоритм Флойда

Алгоритм Флойда решает проблему кратчайших путей для всех пар для ориентированных графов. С матрица смежности графа в качестве входных данных, он вычисляет более короткие пути итеративно. После |V| итераций матрица расстояний содержит все кратчайшие пути. Ниже описана последовательная версия алгоритма в псевдокоде:

 1    func Флойд_Все_Пары_SP (А) { 2        ${\displaystyle D^{(0)}}$ = А; 3        за k := 1 к п делать 4            за я := 1 к п делать 5                за j := 1 к п делать 6                    ${\displaystyle d_{i,j}^{(k)}:=\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})}$ 7     }

разбиение матрицы с двумерным блочным отображением

Где А это матрица смежности, п = |V| количество узлов и D матрица расстояний. Для более подробного описания последовательного алгоритма ищите Алгоритм Флойда-Уоршолла.

Распараллеливание

Основная идея распараллеливания алгоритма - разделить матрицу и разделить вычисления между процессами. Каждому процессу назначена определенная часть матрицы. Обычный способ добиться этого - 2-D блочное отображение. Здесь матрица разбивается на квадраты одинакового размера, и каждый квадрат назначается процессу. Для ${\displaystyle n\times n}$-матрица и п обрабатывает каждый процесс вычисляет ${\displaystyle n/{\sqrt {p}}\times n/{\sqrt {p}}}$ размерная часть матрицы расстояний. За ${\displaystyle p=n^{2}}$ каждому процессу будет назначен ровно один элемент матрицы. Из-за этого распараллеливание масштабируется только до максимума ${\displaystyle n^{2}}$ процессы. В дальнейшем мы будем ссылаться на ${\displaystyle p_{i,j}}$ процессу, который назначен квадрату в i-й строке и j-м столбце.

Поскольку вычисление частей матрицы расстояний зависит от результатов других частей, процессы должны взаимодействовать друг с другом и обмениваться данными. В дальнейшем мы будем ссылаться на ${\displaystyle d_{i,j}^{(k)}}$ элементу i-й строки и j-го столбца матрицы расстояний после k-й итерации. Вычислять ${\displaystyle d_{i,j}^{(k)}}$ нам нужны элементы ${\displaystyle d_{i,j}^{(k-1)}}$, ${\displaystyle d_{i,k}^{(k-1)}}$ и ${\displaystyle d_{k,j}^{(k-1)}}$ как указано в строке 6 алгоритма. ${\displaystyle d_{i,j}^{(k-1)}}$ доступен каждому процессу, поскольку он был рассчитан сам по себе на предыдущей итерации.

Кроме того, каждому процессу требуется часть k-й строки и k-го столбца таблицы. ${\displaystyle D^{k-1}}$ матрица. В ${\displaystyle d_{i,k}^{(k-1)}}$ элемент содержит процесс в той же строке, а ${\displaystyle d_{k,j}^{(k-1)}}$ element содержит процесс в том же столбце, что и процесс, который хочет вычислить ${\displaystyle d_{i,j}^{(k)}}$. Каждый процесс, который вычислил часть k-й строки в ${\displaystyle D^{k-1}}$ матрица должна отправить эту часть всем процессам в своем столбце. Каждый процесс, который вычислил часть k-го столбца в ${\displaystyle D^{k-1}}$ матрица должна отправить эту часть всем процессам в своей строке. Все эти процессы должны выполнять операцию широковещательной рассылки по строке или столбцу. Зависимости данных показаны на изображении ниже.

Для двумерного блочного отображения мы должны изменить алгоритм следующим образом:

 1    func Floyd_All_Pairs_Parallel (${\displaystyle D^{(0)}}$) { 2      за k := 1 к п делать{3 Каждый процесс ${\displaystyle p_{i,j}}$ имеющий отрезок k-й строки ${\displaystyle D^{(k-1)}}$, передает его ${\displaystyle p_{*,j}}$ процессы; 4 Каждый процесс ${\displaystyle p_{i,j}}$ имеющий сегмент k-го столбца ${\displaystyle D^{(k-1)}}$, передает его ${\displaystyle p_{i,*}}$ процессы; 5 Каждый процесс ожидает получения необходимых сегментов; 6 Каждый процесс вычисляет свою часть ${\displaystyle D^{(k)}}$ матрица; 7} 8}

зависимости данных в алгоритме Флойда

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

Время выполнения

Время выполнения последовательного алгоритма определяется тройным вложенным циклом for. Вычисление в строке 6 может быть выполнено за постоянное время (${\displaystyle O(1)}$). Следовательно, время выполнения последовательного алгоритма равно ${\displaystyle O(n^{3})}$.

2-D блочное отображение

Время выполнения распараллеленного алгоритма состоит из двух частей. Время на вычисления и часть на связь и передачу данных между процессами.

Поскольку в алгоритме нет дополнительных вычислений, и вычисление делится поровну между п процессов, у нас есть время выполнения ${\displaystyle O(n^{3}/p)}$ для вычислительной части.

На каждой итерации алгоритма выполняется операция широковещательной рассылки «один ко всем» по строке и столбцу процессов. Есть ${\displaystyle n/{\sqrt {p}}}$ элементы трансляции. После этого выполняется этап синхронизации. Сколько времени займут эти операции, сильно зависит от архитектуры используемой параллельной системы. Следовательно, время, необходимое для связи и передачи данных в алгоритме, равно ${\displaystyle T_{\text{comm}}=n(T_{\text{synch}}+T_{\text{broadcast}})}$.

Для всего алгоритма у нас есть следующая среда выполнения:

${\displaystyle T=O\left({\frac {n^{3}}{p}}\right)+n(T_{\text{synch}}+T_{\text{broadcast}})}$

Конвейерное двухмерное отображение блоков

Во время выполнения передачи данных между процессами в конвейерной версии алгоритма мы предполагаем, что процесс может передавать k элементы к соседнему процессу в ${\displaystyle O(k)}$ время. На каждом шагу есть ${\displaystyle n/{\sqrt {p}}}$ элементы строки или столбца отправляются в соседний процесс. Такой шаг требует ${\displaystyle O(n/{\sqrt {p}})}$ время. После ${\displaystyle {\sqrt {p}}}$ шаги соответствующие данные первой строки и столбца поступают в процесс ${\displaystyle p_{{\sqrt {p}},{\sqrt {p}}}}$ (в ${\displaystyle O(n)}$ время).

Значения последовательных строк и столбцов следуют после времени ${\displaystyle O(n^{2}/p)}$ в конвейерном режиме. Процесс ${\displaystyle p_{{\sqrt {p}},{\sqrt {p}}}}$ завершает свое последнее вычисление после O (${\displaystyle n^{3}/p}$) + O (${\displaystyle n}$) время. Следовательно, дополнительное время, необходимое для обмена данными в конвейерной версии, равно ${\displaystyle O(n)}$.

Общее время выполнения конвейерной версии алгоритма составляет:

${\displaystyle T=O\left({\frac {n^{3}}{p}}\right)+O(n)}$

Рекомендации

Библиография

• Грама, А .: Введение в параллельные вычисления. Pearson Education, 2003 г.
• Кумар, В .: Масштабируемость параллельных алгоритмов для задачи кратчайшего пути для всех пар. Журнал параллельного и распределенного программирования 13, 1991.
• Фостер, И .: Проектирование и создание параллельных программ (В сети).
• Бинделл, Падение: Параллельные кратчайшие пути для всех пар Приложения параллельных компьютеров, 2011.