Параллельный алгоритм поиска кратчайшего пути для всех пар

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

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

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

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

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

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

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

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

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

 1    func DijkstraSSSP(G,v) {
 2        ... //standard SSSP-implementation here
 3        return d_v;
 4    }
 5    
 6    func DijkstraAPSP(G) {
 7        D := |V|x|V|-Matrix
 8        for i from 1 to |V| {
 9           //D[v] denotes the v-th row of D
 10          D[v] := DijkstraSSP(G,i)
 11       }
 12   }

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

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

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

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

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

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

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

Распараллеливание более | В | процессоры

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

 1    func Floyd_All_Pairs_SP(A) {
 2         $D^{(0)}$  = A;
 3        for k := 1 to n do
 4            for i := 1 to n do
 5                for j := 1 to n do
 6                     $d_{i,j}^{(k)}:=\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})$ 
 7     }

Где A — матрица смежности , n = | В | количество узлов и D матрица расстояний.

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

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

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

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

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

 1    func Floyd_All_Pairs_Parallel( $D^{(0)}$ ) {
 2        for k := 1 to n do {
 3            Each process  $p_{i,j}$  that has a segment of the k-th row of  $D^{(k-1)}$ ,
              broadcasts it to the  $p_{*,j}$  processes;
 4            Each process  $p_{i,j}$  that has a segment of the k-th column of  $D^{(k-1)}$ ,
              broadcasts it to the  $p_{i,*}$  processes;
 5            Each process waits to receive the needed segments;
 6            Each process computes its part of the  $D^{(k)}$  matrix;
 7        }
 8    }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

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