Parallel approaches to shortest-path problems for multilevel heterogeneous computing

Resumen

Muchos problemas que surgen en las redes del mundo real requieren calcular los caminos más cortos, y sus distancias, entre uno o varios puntos de origen a uno o varios puntos de destino. Existen diferentes variantes del problema. El problema del SSSP, o Single-Source Shortest-Path, tiene como objetivo calcular los caminos más cortos y sus distancias entre un punto origen y el resto. Por otro lado, el problema del APSP, o All-Pair Shortest-Path, tiene como objetivo calcular los caminos más cortos y sus distancias entre cualquier par de puntos de la red. Algunos ejemplos de contextos donde este tipo de cómputo es necesario son los sistemas de navegación, simulaciones de tráfico, medios de transporte con horario fijo, control logístico, bases de datos espaciales, planificación de rutas en Internet, o búsquedas en la web. A pesar de la importancia del problema de cálculo de caminos más cortos, los algoritmos actuales son aún muy costosos en términos computacionales, y en muchos casos los productos comerciales implementan abortamientos heurísticos para generar soluciones aproximadas en vez de soluciones óptimas. El objetivo de paralelizar estos algoritmos implica no sólo la inmediata reducción de los tiempos de ejecución sino también su aplicación en otros planteamientos más complejos donde estos algoritmos representan una fase dentro del método global. De esta manera, estos métodos, que previamente eran sólo teóricos debido a prohibitivos tiempos de ejecución, pueden ser ahora factibles y viables gracias a esta reducción. Un ejemplo de este tipo de fases son los costosos preprocesos necesarios para ejecutar consultas en el cálculo de rutas de un mapa de carreteras. En este preproceso se obtienen valores que son almacenados para ser utilizados a posteriori en la consulta, donde se pide calcular la ruta más corta entre dos puntos del mapa. Normalmente, este preproceso tiene un coste muy alto en términos temporales, pero mientras sólo haya que ejecutarlo una vez cada mucho tiempo, podría considerarse como una tarea de coste asequible. Gracias a estos valores precomputados, que en ocasiones representan el cálculo de todas las distancias de todas las parejas de puntos de la red, la fase de consulta puede ser computada en el orden de nanosegundos. La configuración de los mapas de carreteras no cambia frecuentemente, por lo que podría ser plausible pagar el alto coste de la fase de preproceso una vez. Sin embargo, en otros contextos donde las redes tienden a cambiar con más frecuencia, o su topología es desconocida en un momento determinado, la reducción de tiempos de esta fase de preproceso se convierte en algo crucial. Además, en el contexto de los mapas de carreteras, podemos encontrar también este comportamiento dinámico si queremos tener en cuenta otros factores en tiempo real como pueden ser el estado de las carreteras o el tráfico. La aparición de los dispositivos móviles presenta un tercer desafío debido a su poca capacidad de almacenamiento que limita la cantidad de datos precomputados que podríamos almacenar. La mayoría de los métodos actuales son más rápidos cuantos más datos precomputados puedan almacenar. Sin embargo, los dispositivos móviles actuales tienen una gran capacidad de cómputo incorporando varios procesadores cuya explotación en paralelo podría aliviar la mencionada falta de almacenamiento. La computación paralela consiste en utilizar a la vez dos o más dispositivos para realizar cálculos, normalmente con el propósito de reducir los tiempos de ejecución. Aunque la paralelización de un algoritmo no reduce su tiempo asintótico, a veces es la única manera de conseguir tiempos de ejecución razonables y/o competitivos. La tendencia de los ordenadores actuales es incorporan un mayor número de procesadores en vez de un único procesador con mucha velocidad de cómputo. Esta evolución ha derivado en la creación de tipos diferentes de dispositivos de cómputo: los sistemas multi-core y los sistemas many-core. Los primeros incluyen dos o más núcleos de procesamiento, o cores, que son de propósito general dentro de un mismo chip. Sin embargo, un sistema es considerado many-core, cuando tiene más de una docena de estas unidades de procesamiento. En esta categoría podemos encontrar no sólo superordenadores con un gran número de CPUs con muchos cores, sino también los aceleradores hardware como los procesadores gráficos (GPUs) o los coprocesadores, como los dispositivos Xeon-Phi. Actualmente, los dispositivos con arquitectura many-core más representativos son las GPUs. Éstos están diseñados para ayudar a la CPU en el procesamiento de gráficos. Sin embargo, debido a sus altas capacidades computacionales han hecho que se utilicen para otro tipo de propósitos de ámbito general. Con el fin de facilitar este tipo de programación, NVIDIA desarrolló un nuevo modelo de programación, llamado CUDA, en 2007. Desde entonces muchas soluciones sofisticadas y eficientes se han desarrollado para diferentes aplicaciones y problemas. Gracias a este modelo de programación es posible desarrollar fácilmente soluciones básicas para GPUs que obtienen mejoras en el rendimiento. En contraposición, conseguir optimizar la explotación de los recursos computacionales es una tarea difícil. Se necesita conocer en profundidad muchos de los detalles relacionados con la arquitectura de estos dispositivos, y de su correspondiente gestión, para poder predecir su comportamiento. Esta responsabilidad recae de manera directa sobre los propios programadores, que han de proveer varios valores para los parámetros de ejecución de las GPUs, como por ejemplo el tamaño y forma de los bloques de hilos, o el estado/tamaño de la memoria cache de primer nivel, entre otros. Las guías de programación que ofrece CUDA sugieren el uso de determinados valores para obtener buenos rendimientos. Sin embargo, algunos estudios han demostrado que en algunos casos estas recomendaciones no siempre devuelven rendimientos óptimos, obligando a los programadores a realizar tests de prueba-y-error para encontrar los valores que se ajustan a los mejores rendimientos. Dentro de la computación paralela se encuentra la computación heterogénea, que se refiere al uso de sistemas o entornos de computación que están compuestos por unidades de procesamiento de diferente naturaleza. Algunos ejemplos típicos son los convencionales sistemas de memoria compartida o distribuida que contienen multi-core CPUs junto con dispositivos many-core como las GPUs. Una de las principales ventajas de usar este paradigma de computación, a diferencia del modelo homogéneo, es la posibilidad de asignar un tipo particular de tareas/funciones a aquellos dispositivos computacionales que mejor se ajusten a los requisitos de procesamientos de esas tareas. Otra ventaja, es la posibilidad de aprovechar cualquier unidad computacional presente dentro del sistema heterogéneo, aunque sus características no se ajusten perfectamente para la realización óptima de un trabajo específico, siempre y cuando podamos ahorrar tiempo de la ejecución global de tareas. Sin embargo, la programación de este tipo de entornos heterogéneos resulta bastante difícil comparada con la programación de entornos homogéneos. El programador debe conocer los diferentes modelos y lenguajes de programación necesarios para aprovechar los diferentes recursos computacionales, sus limitaciones y particularidades, para proveer diferentes implementaciones dependiendo de la plataforma donde se vaya a ejecutar. Además el programador ha de conocer qué tipo de tareas se ajusta mejor a qué dispositivo para obtener un mejor rendimiento y cuánto trabajo ha de asignar a cada uno. Todos estos problemas hacen que la programación sobre sistemas heterogéneos sea casi el resultado de un trabajo artesanal en el que hay que invertir mucho tiempo y esfuerzo debido a la falta de modelos de programación de propósito general que puedan lidiar con este tipo de complejidad de una manera transparente.