Tecnologías Específicas

Computación
Ingeniería de Computadores

Descripcion y Objetivos

El problema de la clique máxima es un clásico problema de teoría de grafos que consiste en dado un grafo (podemos considerarlo no dirigido y sin bucles en un nodo para simplificar) obtener la clique máxima, donde una clique es un subgrafo completo, es decir donde todos los nodos están interconectados entre ellos por aristas.

Por ejemplo, para dos nodos, la clique es si están conectados, es decir, una arista. Para 3 nodos, un triángulo, es decir los pares de nodos unidos cada uno por una arista. Para 4 nodos, que existan las 6 aristas entre ellos, y, en general, para n nodos, las n*(n-1)/2 aristas que unen todos los posibles pares existan.

El problema es de tipo combinatorio, y por ello entra dentro de los NP-completos, es decir, para los cuales no existe un algoritmo conocido que los resuelva en un tiempo razonable, sino que precisan de un tiempo exponencial, por tanto, a partir de determinados tamaños el tiempo de procesamiento para resolver el problema es muy elevado y no permite obtener el resultado en tiempos razonables, o directamente no es posible obtenerlo.

Por tanto, es necesario reducir el tiempo de ejecución del algoritmo. La aproximación usual al problema es mediante técnicas Branch & Bound, pero además, otra posible forma de conseguirlo es paralelizar alguna sección del código, la cual tenga un peso importante en el procesamiento.

El objetivo de este trabajo fin de grado es reducir el tiempo total de ejecución de un algoritmo de obtención de cliques aplicando técnicas de paralelización, y de esta forma comprobar si dicho algoritmo puede obtener una reducción de su tiempo de ejecución que aumente su rango de aplicabilidad.

 

Metodología y Competencias

La metodología que será utilizada se puede resumir en los siguientes puntos:

- Análisis del código, para obtener la carga computacional de cada una de las funciones de las que consta, y determinar así las que contribuyen en mayor medida. Sobre estas últimas, se realizará un estudio para comprobar si son susceptibles de ser paralelizadas.

- Estudio de las posibles vías de paralelización del código. De acuerdo con las características del procesamiento, se determinará la manera más adecuada de realizar la descomposición en tareas que puedan ser realizadas concurrentemente.

-  Elección de la plataforma o plataformas hardware/software más adecuadas para realizar el procesamiento paralelo del algoritmo.

- Obtención del código paralelo, teniendo en cuenta tanto su análisis previo como las características de la plataforma elegida.

- Desarrollo del proceso de evaluación, para determinar la mejora en el rendimiento obtenida, y si ésta es suficiente para llegar al resultado deseado.

 

Las principales competencias que el alumno trabajará son: 

Ingeniería de Computadores:

[IC3] Capacidad de analizar y evaluar arquitecturas de computadores, incluyendo plataformas paralelas y distribuidas, así como desarrollar y optimizar software para las mismas.

[IC7] Capacidad para analizar, evaluar, seleccionar y configurar plataformas hardware para el desarrollo y ejecución de aplicaciones y servicios informáticos.

 

Para La Tecnología de Computación:

[CM2] Capacidad para conocer los fundamentos teóricos de los lenguajes de programación y las técnicas de procesamiento léxico, sintáctico y semántico asociadas, y saber aplicarlas para la creación, diseño y procesamiento de lenguajes.

[CM3] Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

 

 

Medios a utilizar

En principio, se plantean dos alternativas para obtener el código paralelo del algoritmo: OpenMP y CUDA, sobre dos plataformas hardware diferentes o una única que permita las dos opciones. Se trata en ambos casos de recursos disponibles en el Centro, y que podrán ser utilizados para el desarrollo del proyecto.

Medios hardware:

Servidor con las siguientes características:

- CPU: Intel(R) Xeon(R) CPU E5-2650 v2 2.60GHz, 8 procesadores,  CPU MHz: 1200.062, caché de 20480 KB

- GPU: Tesla K40m, con memoria global de 11520 MBytes, 15 multiprocesadores de 192 CUDA Cores/MP (para un total de 2880 CUDA cores), Clock rate de  745 MHz, clock rate de memoria de 3004 Mhz, y ancho del bus con memoria de 384 bits, y una caché L2 de 1572864 bytes

 

Medios software:

Las herramientas, sistema operativo, librerías, etc, serán fundamentalmente las siguientes: OpenMP, NVIDIA CUDA Toolkit 9.5, C/C++, SO Linux.

 

 

Bibliografía

- CUDA C Best Practices Guide.

http://docs.nvidia.com/cuda/cuda-c-best-practices-guide/index.html#axzz466UPSr5y

- CUDA C Programming Guide.

http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#axzz466UPSr5y

- D. Kirk, W.-M. Hwu. Programming massively parallel processors. Morgan Kaufman Publishers, 978-0-12-381472-2. 2013 2a edición

- Brassard, Bratley. Fundamentos de Algoritmia. Prentice-Hall. ISBN 13: 9788489660007

- Tutte, W.T. Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3