Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 06:25, 2 April 2018

Revision as of 17:19, 2 April 2018

Line 6:

{{no footnotes|date=March 2018}}

A central problem in [[graph theory]] is the [[shortest path problem]]. Hereby, the problem of finding the shortest path between every pair of nodes is known as ''All'all-Pairpair-Shortestshortest-Pathspaths (APSP)''' problem. As [[sequential algorithmsalgorithm]]s for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article two efficient algorithms solving this problem are introduced.

== Problem definition==

Let <math>G=(V,E,w)</math> be a directed Graph with the set of nodes <math>V</math> and the set of edges <math>E\subseteq V\times V</math>. Each edge <math>e \in E</math> has a weight <math>w(e)</math> assigned. The goal of the all-pair-shortest-paths problem is to find the shortest path between '''all''' pairs of nodes of the graph. For this path to be unique it is required that the graph does not contain cycles with a negative weight.

The goal of the All-Pair-Shortest-Paths problem is to find the shortest path between '''all''' pairs of nodes of the graph. For this path to be unique it is required that the graph does not contain cycles with a negative weight.

In the remainder of the article it is assumed that the graph is represented using an [[adjacency matrix]]. We expect the output of the algorithm to be a distancematrix <math>D</math>. In <math>D</math>, every entry <math>d-{i,j}</math> is the weight of the shortest path in <math>G</math> from node <math>i</math> to node <math>j</math>.

The [[Floyd algorithm]] presented later can handle negative edge weights, wheraswhereas the [[Dijkstra algorithm]] requires all edges to have a positive weight.

== Dijkstra algorithm ==

The [[Dijkstra algorithm]] originally was propsoedproposed as a solver for the Singlesingle-Sourcesource-shortest-paths problem. However, the algorithm can easily be used for solving the All-Pair-Shortest-Paths problem by executing the Single-Source varaint with each node int the role of the root node.

However, the algorithm can easily be used for solving the All-Pair-Shortest-Paths problem by executing the Single-Source varaint with each node int the role of the root node.

In pseudocode such an implementation could look as follows:

Line 56 ⟶ 55:

Another benefit of this parallelization is that no communication between the processors is required. However, it is required that every processor has enough local memory to store the entire adjacency matrix of the graph.

===Parallelization for more than <math>|''V''|</math> processors===

[[File:Apsp dijkstra graph.png|thumb]][[File:Apsp dijkstra distancelist.png|thumb]]

If more than <math>|V|</math> processors shall be used for the parallelization, it is required that multiple processors take part of the <code>DijkstraSSSP</code> computation. For this reason, the parallelization is split across into two levels.

For this reason, the parallelization is split across into two levels.

For the first level the processors are split into <math>|V|</math> partitions.

Each partition is responsible for the computation of a single row of the distancematrix <math>D</math>. This means each partition has to evalaute one <code>DijkstraSSSP</code> execution with a fixed root node.

With this definition each partition has a size of <math>k=\frac{p}{|V|}</math> processors. The partitions can perform their computations in parallel as the results of each are independent of eachothereach other. Therefore, the parallelization presented in the previous section corresponds to a partition size of 1 with <math>p=|V|</math> processors.

Therefore, the parallelization presented in the previous section corresponds to a partition size of 1 with <math>p=|V|</math> processors.

The main difficulty is the parallelization of multiple processors executing <code>DijkstraSSSP</code> for a single root node. The idea for this parallelization is to distribute the management of the distancelist <math>d_v</math> in DijkstraSSSP within the partition. Each processor in the partition therefore is exclusively responsible for <math>\frac{|V|}{k}</math> elements of <math>d_v</math>. For example consider <math>|V|=4</math> and <math>p=8</math>: this yields a partition size of <math>k=2</math>. In this case, the first processor of each partition is responsible for <math>d_{v,1}</math>, <math>d_{v,2}</math> and the second processor is responsible for <math>d_{v,3}</math> and <math>d_{v,4}</math>. Hereby, the total distance lists is <math>d_v = [d_{v,1},d_{v,2},d_{v,3},d_{v,4}]</math>.

The main difficulty is the parallelization of multiple processors executing <code>DijkstraSSSP</code> for a single root node.

The idea for this parallelization is to distribute the management of the distancelist <math>d_v</math> in DijkstraSSSP within the partition.

Each processor in the partition therefore is exclusively responsible for <math>\frac{|V|}{k}</math> elements of <math>d_v</math>.

For example consider <math>|V|=4</math> and <math>p=8</math>: this yields a partition size of <math>k=2</math>.

In this case, the first processor of each partition is responsible for <math>d_{v,1}</math>, <math>d_{v,2}</math> and the second processor is responsible for <math>d_{v,3}</math> and <math>d_{v,4}</math>.

Hereby, the total distance lists is <math>d_v = [d_{v,1},d_{v,2},d_{v,3},d_{v,4}]</math>.

The <code>DijkstraSSSP</code> algorithm mainly consists of the repetition of two steps: First, the nearest node <math>x</math> in the distancelist <math>d_v</math> has to be found. For this node the shortest path already has been found.

First, the nearest node <math>x</math> in the distancelist <math>d_v</math> has to be found. For this node the shortest path already has been found.

Afterwards the distance of all neighbors of <math>x</math> has to be adjusted in <math>d_v</math>.

Line 169 ⟶ 160:

For the whole algorithm we have the following runtime:

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

====Pipelined 2-D block mapping====

Line 178 ⟶ 169:

The overall runtime for the pipelined version of the algorithm is:

: <math>T = O\left( \frac{n^3 /} p\right) + O(n)</math>

== References ==

Line 188 ⟶ 179:

* Foster, I.: ''Designing and Building Parallel Programs'' (Online).

* Bindell, Fall: ''Parallel All-Pairs Shortest Paths'' Applications of Parallel Computers, 2011.

[[Category:Graph algorithms]]