Algoritmo de ruta más corta de todos los pares en paralelo

Un problema central en la teoría de grafos algorítmicos es el problema de la ruta más corta . En este sentido, el problema de encontrar la ruta más corta entre cada par de nodos se conoce como problema de las rutas más cortas entre todos los pares (APSP) . Como los algoritmos secuenciales para este problema suelen producir tiempos de ejecución largos, la paralelización ha demostrado ser beneficiosa en este campo. En este artículo se presentan dos algoritmos eficientes que resuelven este problema.

Otra variación del problema es el problema de las rutas más cortas de fuente única (SSSP), que también tiene enfoques paralelos: Algoritmo de ruta más corta de fuente única paralela .

Sea un grafo dirigido con el conjunto de nodos y el conjunto de aristas . Cada arista tiene un peso asignado. El objetivo del problema de los caminos más cortos entre todos los pares es encontrar el camino más corto entre todos los pares de nodos del grafo. Para que este camino sea único se requiere que el grafo no contenga ciclos con un peso negativo. ${\displaystyle G=(V,E,w)}$${\displaystyle V}$${\displaystyle E\subseteq V\times V}$${\displaystyle e\in E}$${\displaystyle w(e)}$

En el resto del artículo se supone que el gráfico se representa mediante una matriz de adyacencia . Esperamos que la salida del algoritmo sea una matriz de distancia . En , cada entrada es el peso de la ruta más corta de nodo a nodo . ${\displaystyle D}$${\displaystyle D}$${\displaystyle d_{i,j}}$${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$

El algoritmo de Floyd presentado más adelante puede manejar pesos de aristas negativos, mientras que el algoritmo de Dijkstra requiere que todas las aristas tengan un peso positivo.

El algoritmo de Dijkstra se propuso originalmente como una solución para el problema de los caminos más cortos con una sola fuente. Sin embargo, el algoritmo se puede utilizar fácilmente para resolver el problema de los caminos más cortos con todos los pares ejecutando la variante de una sola fuente con cada nodo en el papel de nodo raíz.

En pseudocódigo, una implementación de este tipo podría verse así:

1     función DijkstraSSSP( GRAMO , v ) {
 2 ... //implementación SSSP estándar aquí 
 3 return d v ;
 4 }
 5    
 6     función DijkstraAPSP( G ) {
 7         D  := | V |x| V |-Matriz
 8         para  i  de 1 a | V | {
 9 // D[v] denota la v-ésima fila de D 
 10           D [ v ] := DijkstraSSP( G , i )
 11 }
 12 }

En este ejemplo asumimos que DijkstraSSSPtoma el gráfico y el nodo raíz como entrada. El resultado de la ejecución a su vez es la distancelist . En , el -ésimo elemento almacena la distancia desde el nodo raíz hasta el nodo . Por lo tanto, la lista corresponde exactamente a la -ésima fila de la distancematrix de APSP . Por este motivo, itera sobre todos los nodos del gráfico y ejecuta con cada uno como nodo raíz mientras almacena los resultados en . ${\displaystyle G}$${\displaystyle v}$${\displaystyle d_{v}}$${\displaystyle d_{v}}$${\displaystyle i}$${\displaystyle v}$${\displaystyle i}$${\displaystyle d_{v}}$${\displaystyle v}$${\displaystyle D}$DijkstraAPSP${\displaystyle G}$DijkstraSSSP${\displaystyle D}$

El tiempo de ejecución de DijkstraSSSPes el que esperamos que se represente en el gráfico utilizando una matriz de adyacencia . Por lo tanto, tiene un tiempo de ejecución secuencial total de . ${\displaystyle O(|V|^{2})}$DijkstraAPSP${\displaystyle O(|V|^{3})}$

Se puede obtener una paralelización trivial paralelizando el bucle de DijkstraAPSPla línea 8. Sin embargo, al utilizar el método secuencial, DijkstraSSSPesto limita la cantidad de procesadores que se utilizarán según la cantidad de iteraciones ejecutadas en el bucle. Por lo tanto, para esta paralelización trivial, existe un límite superior para la cantidad de procesadores. ${\displaystyle |V|}$

Por ejemplo, supongamos que el número de procesadores es igual al número de nodos . Esto da como resultado que cada procesador se ejecute exactamente una vez en paralelo. Sin embargo, cuando solo hay procesadores disponibles, por ejemplo, cada procesador debe ejecutarse dos veces. ${\displaystyle p}$${\displaystyle |V|}$DijkstraSSSP${\displaystyle p={\frac {|V|}{2}}}$DijkstraSSSP

En total, esto produce un tiempo de ejecución de , cuando es un múltiplo de . En consecuencia, la eficiencia de esta paralelización es perfecta: el uso de procesadores reduce el tiempo de ejecución en el factor . ${\displaystyle O(|V|^{2}\cdot {\frac {|V|}{p}})}$${\displaystyle |V|}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

Otra ventaja de esta paralelización es que no se requiere comunicación entre los procesadores, pero sí que cada procesador tenga suficiente memoria local para almacenar toda la matriz de adyacencia del grafo.

Si se utilizan más de un procesador para la paralelización, es necesario que varios procesadores participen en el cálculo. Por este motivo, la paralelización se divide en dos niveles. ${\displaystyle |V|}$DijkstraSSSP

Para el primer nivel, los procesadores se dividen en particiones. Cada partición es responsable del cálculo de una sola fila de la matriz de distancias . Esto significa que cada partición tiene que evaluar una ejecución con un nodo raíz fijo. Con esta definición, cada partición tiene un tamaño de procesadores. Las particiones pueden realizar sus cálculos en paralelo, ya que los resultados de cada una son independientes entre sí. Por lo tanto, la paralelización presentada en la sección anterior corresponde a un tamaño de partición de 1 con procesadores. ${\displaystyle |V|}$${\displaystyle D}$DijkstraSSSP${\displaystyle k={\frac {p}{|V|}}}$${\displaystyle p=|V|}$

La principal dificultad es la paralelización de múltiples procesadores que se ejecutan DijkstraSSSPpara un único nodo raíz. La idea de esta paralelización es distribuir la gestión de la lista de distancias en DijkstraSSSP dentro de la partición. Por lo tanto, cada procesador de la partición es exclusivamente responsable de los elementos de . Por ejemplo, considere y : esto produce un tamaño de partición de . En este caso, el primer procesador de cada partición es responsable de , y el segundo procesador es responsable de y . Por lo tanto, la lista de distancias total es . ${\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}]}$

El DijkstraSSSPalgoritmo consiste principalmente en la repetición de dos pasos: primero, se debe encontrar el nodo más cercano en la lista de distancias . Para este nodo ya se ha encontrado el camino más corto. Después, se debe ajustar la distancia de todos los vecinos de en . ${\displaystyle x}$${\displaystyle d_{v}}$${\displaystyle x}$${\displaystyle d_{v}}$

Estos pasos deben modificarse de la siguiente manera porque la paralelización se ha distribuido a lo largo de la partición: ${\displaystyle d_{v}}$

1. Encuentra el nodo con la distancia más corta en . ${\displaystyle x}$${\displaystyle d_{v}}$
   • Cada procesador posee una parte de : Cada procesador busca el mínimo local en su parte, por ejemplo utilizando una búsqueda lineal.${\displaystyle d_{v}}$${\displaystyle {\tilde {x}}}$
   • Calcule el mínimo global en realizando una operación de reducción en todos los .${\displaystyle x}$${\displaystyle d_{v}}$${\displaystyle {\tilde {x}}}$
   • Transmita el mínimo global a todos los nodos de la partición.${\displaystyle x}$
2. Ajustar la distancia de todos los vecinos de en${\displaystyle x}$${\displaystyle d_{v}}$
   • Ahora, cada procesador conoce el nodo global más cercano y su distancia. En función de esta información, ajusta los vecinos de los que se encarga el procesador correspondiente.${\displaystyle x}$${\displaystyle x}$${\displaystyle d_{v}}$

El tiempo de ejecución total de dicha iteración DijkstraSSSPrealizada por una partición de tamaño se puede derivar en función de las subtareas realizadas: ${\displaystyle k}$

• La búsqueda lineal de :${\displaystyle {\tilde {x}}}$${\displaystyle O({\frac {|V|}{k}})}$
• Operaciones de transmisión y reducción: se pueden implementar de manera eficiente, por ejemplo, utilizando árboles binomiales. Esto produce una sobrecarga de comunicación de .${\displaystyle O(\log k)}$

Para las iteraciones, esto da como resultado un tiempo de ejecución total de . Después de sustituir la definición de this, se obtiene el tiempo de ejecución total para : . ${\displaystyle |V|}$${\displaystyle O(|V|({\frac {|V|}{k}}+\log k))}$${\displaystyle k}$DijkstraAPSP${\displaystyle O({\frac {|V|^{3}}{p}}+\log p)}$

El principal beneficio de esta paralelización es que ya no es necesario que cada procesador almacene la matriz de adyacencia completa. En cambio, es suficiente que cada procesador dentro de una partición almacene solo las columnas de la matriz de adyacencia de los nodos de los que es responsable. Dado un tamaño de partición de , cada procesador solo tiene que almacenar columnas de la matriz de adyacencia. Sin embargo, una desventaja es que esta paralelización conlleva una sobrecarga de comunicación debido a las operaciones de reducción y difusión. ${\displaystyle k}$${\displaystyle {\frac {|V|}{k}}}$

El gráfico utilizado en este ejemplo es el presentado en la imagen con cuatro nodos.

El objetivo es calcular la matriz de distancias con procesadores. Por este motivo, los procesadores se dividen en cuatro particiones con dos procesadores cada una. Para la ilustración, nos centramos en la partición que se encarga del cálculo de las rutas más cortas desde el nodo A hasta todos los demás nodos. Los procesadores de esta partición se denominan p1 y p2 . ${\displaystyle p=8}$

El cálculo de la lista de distancias a lo largo de las diferentes iteraciones se visualiza en la segunda imagen.

La fila superior de la imagen corresponde a la etapa posterior a la inicialización, la inferior a la etapa posterior a la finalización del algoritmo. Los nodos se distribuyen de forma que p1 es responsable de los nodos A y B , mientras que p2 es responsable de los nodos C y D. La lista de distancias se distribuye de acuerdo con esto. Para la segunda iteración, las subtareas ejecutadas se muestran explícitamente en la imagen: ${\displaystyle d_{A}}$${\displaystyle d_{A}}$${\displaystyle d_{A}}$

1. Cálculo del nodo mínimo local en${\displaystyle d_{A}}$
2. Cálculo del nodo mínimo global mediante una operación de reducción${\displaystyle d_{A}}$
3. Transmisión del nodo mínimo global en${\displaystyle d_{A}}$
4. Marcar el nodo global más cercano como "terminado" y ajustar la distancia de sus vecinos

El algoritmo Floyd-Warshall resuelve el problema de los caminos más cortos para todos los pares de grafos dirigidos. Con la matriz de adyacencia de un grafo como entrada, calcula los caminos más cortos de forma iterativa. Después de | V | iteraciones, la matriz de distancias contiene todos los caminos más cortos. A continuación se describe una versión secuencial del algoritmo en pseudocódigo:

1     función Floyd_All_Pairs_SP( A ) {
 2         = Un ;${\displaystyle D^{(0)}}$
 3         para  k  := 1 a  n  hacer 
 4             para  i  := 1 a  n  hacer 
 5                 para  j  := 1 a  n  hacer 
 6                    ${\displaystyle d_{i,j}^{(k)}:=\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})}$
 7 }

Donde A es la matriz de adyacencia , n = | V | el número de nodos y D la matriz de distancia.

La idea básica para paralelizar el algoritmo es particionar la matriz y dividir el cálculo entre los procesos. Cada proceso se asigna a una parte específica de la matriz. Una forma común de lograr esto es el mapeo de bloques 2-D . Aquí la matriz se divide en cuadrados del mismo tamaño y cada cuadrado se asigna a un proceso. Para una matriz y p procesos, cada proceso calcula una parte dimensionada de la matriz de distancia. Para los procesos, cada uno se asignaría exactamente a un elemento de la matriz. Debido a eso, la paralelización solo se escala a un máximo de procesos. A continuación, nos referimos al proceso que se asigna al cuadrado en la fila i-ésima y la columna j-ésima. ${\displaystyle n\times n}$${\displaystyle n/{\sqrt {p}}\times n/{\sqrt {p}}}$${\displaystyle p=n^{2}}$${\displaystyle n^{2}}$${\displaystyle p_{i,j}}$

Como el cálculo de las partes de la matriz de distancia depende de los resultados de otras partes, los procesos tienen que comunicarse entre sí e intercambiar datos. A continuación, nos referimos al elemento de la fila i y la columna j de la matriz de distancia después de la iteración k. Para calcular, necesitamos los elementos , y como se especifica en la línea 6 del algoritmo. está disponible para cada proceso, ya que fue calculado por sí mismo en la iteración anterior. ${\displaystyle d_{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)}}$${\displaystyle d_{i,j}^{(k-1)}}$

Además, cada proceso necesita una parte de la k-ésima fila y la k-ésima columna de la matriz. El elemento contiene un proceso en la misma fila y el elemento contiene un proceso en la misma columna que el proceso que desea calcular . Cada proceso que calculó una parte de la k-ésima fila de la matriz tiene que enviar esta parte a todos los procesos de su columna. Cada proceso que calculó una parte de la k-ésima columna de la matriz tiene que enviar esta parte a todos los procesos de su fila. Todos estos procesos tienen que realizar una operación de transmisión de uno a todos a lo largo de la fila o la columna. Las dependencias de datos se ilustran en la imagen siguiente. ${\displaystyle D^{k-1}}$${\displaystyle d_{i,k}^{(k-1)}}$${\displaystyle d_{k,j}^{(k-1)}}$${\displaystyle d_{i,j}^{(k)}}$${\displaystyle D^{k-1}}$${\displaystyle D^{k-1}}$

Para el mapeo de bloques 2-D tenemos que modificar el algoritmo de la siguiente manera:

1     función Floyd_All_Pairs_Parallel( ) {${\displaystyle D^{(0)}}$
 2         para  k  := 1 a  n  hacer {
 3 Cada proceso que tiene un segmento de la k-ésima fila de ,${\displaystyle p_{i,j}}$${\displaystyle D^{(k-1)}}$
              lo transmite a los procesos;${\displaystyle p_{*,j}}$
 4 Cada proceso que tiene un segmento de la k-ésima columna de ,${\displaystyle p_{i,j}}$${\displaystyle D^{(k-1)}}$
              lo transmite a los procesos;${\displaystyle p_{i,*}}$
 5 Cada proceso espera recibir los segmentos necesarios;
 6 Cada proceso calcula su parte de la matriz;${\displaystyle D^{(k)}}$
 7 }
 8 }

En la línea 5 del algoritmo tenemos un paso de sincronización para asegurar que todos los procesos tengan los datos necesarios para calcular la siguiente iteración. Para mejorar el tiempo de ejecución del algoritmo podemos eliminar el paso de sincronización sin afectar la corrección del algoritmo. Para lograr que cada proceso comience el cálculo tan pronto como tenga los datos necesarios para calcular su parte de la matriz. Esta versión del algoritmo se llama mapeo de bloques 2-D segmentado .

El tiempo de ejecución del algoritmo secuencial está determinado por el bucle for triplemente anidado. El cálculo en la línea 6 se puede realizar en tiempo constante ( ). Por lo tanto, el tiempo de ejecución del algoritmo secuencial es . ${\displaystyle O(1)}$${\displaystyle O(n^{3})}$

El tiempo de ejecución del algoritmo paralelizado consta de dos partes: el tiempo de cálculo y la parte de comunicación y transferencia de datos entre los procesos.

Como no hay ningún cálculo adicional en el algoritmo y el cálculo se divide equitativamente entre los p procesos, tenemos un tiempo de ejecución de para la parte computacional. ${\displaystyle O(n^{3}/p)}$

En cada iteración del algoritmo se realiza una operación de difusión de uno a todos a lo largo de la fila y la columna de los procesos. Se difunden elementos. Después se realiza un paso de sincronización. El tiempo que tardan estas operaciones depende en gran medida de la arquitectura del sistema paralelo utilizado. Por lo tanto, el tiempo necesario para la comunicación y la transferencia de datos en el algoritmo es . ${\displaystyle n/{\sqrt {p}}}$${\displaystyle T_{\text{comm}}=n(T_{\text{synch}}+T_{\text{broadcast}})}$

Para todo el algoritmo tenemos el siguiente tiempo de ejecución:

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

Para el tiempo de ejecución de la transferencia de datos entre los procesos en la versión segmentada del algoritmo, asumimos que un proceso puede transferir k elementos a un proceso vecino en el tiempo. En cada paso hay elementos de una fila o una columna que se envían a un proceso vecino. Tal paso lleva tiempo. Después de los pasos, los datos relevantes de la primera fila y columna llegan al proceso (en el tiempo). ${\displaystyle O(k)}$${\displaystyle n/{\sqrt {p}}}$${\displaystyle O(n/{\sqrt {p}})}$${\displaystyle {\sqrt {p}}}$${\displaystyle p_{{\sqrt {p}},{\sqrt {p}}}}$${\displaystyle O(n)}$

Los valores de las filas y columnas sucesivas se siguen con el tiempo en un modo segmentado. El proceso finaliza su último cálculo después de O( ) + O( ). Por lo tanto, el tiempo adicional necesario para la comunicación en la versión segmentada es . ${\displaystyle O(n^{2}/p)}$${\displaystyle p_{{\sqrt {p}},{\sqrt {p}}}}$${\displaystyle n^{3}/p}$${\displaystyle n}$${\displaystyle O(n)}$

El tiempo de ejecución total para la versión canalizada del algoritmo es:

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

• Grama, A.: Introducción a la computación paralela . Pearson Educación, 2003.
• Kumar, V.: Escalabilidad de algoritmos paralelos para el problema de la ruta más corta entre pares ^{[ enlace roto ‍ ]} . Journal of Parallel and Distributed Programming 13, 1991.
• Foster, I.: Diseño y construcción de programas paralelos (en línea).
• Bindell, Fall: Aplicaciones de computadoras paralelas en caminos más cortos de todos los pares paralelos , 2011.