Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 08:53, 15 February 2019

Revision as of 14:55, 27 April 2019

Line 126:

As the calculation of the parts of the distance matrix is dependent on results from other parts the processes have to communicate between each other and exchange data. In the following we refer with <math>d^{(k)}_{i,j}</math> to the element of the i-th row and j-th column of the distance matrix after the k-th iteration. To calculate <math>d^{(k)}_{i,j}</math> we need the elements <math>d^{(k-1)}_{i,j}</math>, <math>d^{(k-1)}_{i,k}</math> and <math>d^{(k-1)}_{k,j}</math> as specified in line 6 of the algorithm. <math>d^{(k-1)}_{i,j}</math> is available to each processe as it was calculated by itself in the previous iteration.

Additionally each process needs a part of the k-th row and the k-th column of the <math>D^{k-1}</math> matrix. The <math>d^{(k-1)}_{i,k}</math> element holds a process in the same columnrow and the <math>d^{(k-1)}_{k,j}</math> element holds a process in the same rowcolumn as the process that wants to compute <math>d^{(k)}_{i,j}</math>. Each process that calculated a part of the k-th row in the <math>D^{k-1}</math> matrix has to send this part to all processes in its column. Each process that calculated a part of the k-th column in the <math>D^{k-1}</math> matrix has to send this part to all processes in its row. All this processes have to do a one-to-all-broadcast operation along the row or the column. The data dependencies are illustrated in the image below.

For the 2-D block mapping we have to modify the algorithm as follows: