Tecnologías Específicas

Computación
Ingeniería de Computadores

Descripcion y Objetivos

Los procesadores de las tarjetas gráficas actuales están formados por miles de elementos de proceso o núcleos, lo que les permite tener una elevadísima capacidad computacional. Es por ello que, además de ser utilizados mayoritariamente en el contexto de aplicaciones gráficas, también se están usando como aceleradores de aplicaciones de propósito general.

Este elevado número de núcleos en un solo chip se consigue dedicando la mayor parte del silicio del chip al cálculo, dejando menos espacio para las cachés y el control, como ocurre con los procesadores convencionales. Estos núcleos son lógicamente más sencillos, ya que no implementan técnicas sofisticadas de predicción de saltos, prebúsqueda, planificación dinámica, etc. A pesar de ello, son capaces de realizar las operaciones requeridas en muchas aplicaciones de propósito general.

Para explotar la gran capacidad de cálculo de este tipo de procesadores, es necesario que los programas se diseñen teniendo en cuenta las características particulares de estos procesadores. Sin embargo, su arquitectura está orientada a aplicaciones gráficas, lo que complica la programación si se realiza con lenguajes y herramientas orientados a este tipo de aplicaciones.

Para facilitar la programación de aplicaciones de propósito general, los fabricantes de estos procesadores han proporcionado múltiples recursos, en términos de librerías, directivas y lenguajes, que abstraen la arquitectura y permiten al programador centrarse en extraer el paralelismo intrínseco de las aplicaciones. No se trata de una tarea fácil y requiere, por un lado, el conocimiento en detalle de la aplicación y, por otro lado, conocimientos y habilidades de computación paralela.

Desafortunadamente, en muchos planes de estudio de los grados en Ingeniería Informática no se incluyen asignaturas obligatorias dedicadas a la programación paralela, lo cual supone un déficit importante en la formación de los alumnos que cursan dichos grados. Y lo es dado que actualmente la computación paralela supone la única vía de mejorar el rendimiento de gran cantidad de aplicaciones.

Es interesante pues que, a través del Trabajo Fin de Grado, se dé la oportunidad al alumno de conseguir habilidades en computación paralela. Hay múltiples entornos y aplicaciones que se pueden utilizar para ello. Aprovechando la popularidad de los procesadores gráficos y la accesibilidad a los mismos, este Trabajo Fin de Grado se centra en ellos.

La aplicación elegida para poner en práctica los conocimientos y habilidades adquiridas en programación paralela, es Data Encryption Standard (DES). DES es un algoritmo de cifrado simétrico que permuta cada cadena de 64 bits en otra en la que interviene una clave secreta de 56 bits, de forma que la recuperación de la cadena inicial es computacionalmente muy costosa sin ayuda de la clave.

En su diseño se abordaron todas las debilidades conocidas de algoritmos anteriores y, de hecho, todos los estudios publicados confirman que es un algoritmo fiable para la encriptación de datos y sólo el tamaño de su clave hace aconsejable el uso de versiones extendidas de DES, como 3DES o DES-X.

El funcionamiento de DES se basa en repetir varias veces procesos sencillos de sustitución o permutación y puede ser interesante estudiar hasta qué punto la computación paralela permite acelerar alguna etapa del algoritmo.  

En definitiva, el objetivo principal de este TFG se puede decir que es doble: por un lado adquirir conocimientos en computación paralela que permitan al alumno abordar con garantías el diseño de programas paralelos, y por otro lado, y poniendo en práctica las habilidades y destrezas logradas, obtener una versión paralela del algoritmo secuencial de cifrado Data Encryption Standard (DES) que mejore su rendimiento.

 

 

Metodología y Competencias

Teniendo presente los dos objetivos anteriormente indicados, se realizarán diversas tareas que permitan avanzar conjuntamente hacia su consecución. Se resumen a continuación esas tareas, indicando también una estimación temporal para cada una de ellas, asumiendo una dedicación 12 horas y media semanales, durante 6 meses:

- Revisión de bibliografía básica de computación paralela. Se trata de consultar la documentación que será proporcionada al alumno para adquirir o reforzar los conocimientos necesarios sobre computación paralela. Duración 1 mes.

- Estudio de la plataforma hardware y la herramienta de programación. Con esta tarea se trata de conocer con detalle las características del procesador gráfico y la forma de obtener código para él usando CUDA. Duración 1 mes.

- Aprendizaje del algoritmo DES y análisis del mismo. Para poder paralelizar el código DES hay que conocerlo con detalle y analizar las posibilidades de su paralelización. Duración 1 mes.

- Creación del código CUDA del algoritmo DES. Se trata de obtener código paralelo para ejecutar en la plataforma CPU+GPU, buscando que sea lo más eficaz posible. Duración 1 mes.

- Evaluación de prestaciones. Se realizarán diversas pruebas para comprobar el comportamiento del nuevo código para DES, y también para comparar su rendimiento con el de la versión secuencial. Duración 1 mes.

- Documentación de los resultados. Se elaborará la memoria del TFG, incluyendo toda la información que sea necesaria de acuerdo con la normativa y las características del trabajo. Dedicación: 1 mes.

 

Competencias

Analizada la carga computacional de la aplicación a nivel funcional, aquellas funciones/tareas que sean susceptibles de ser paralelizadas y con un importante peso en el rendimiento en términos de tiempo de ejecución serán descompuestas en subtareas independientes, que posteriormente serán asignadas a los procesos para su realización. En la fase de descomposición de tareas previsiblemente se aplicará la estrategia divide y vencerás, analizando si se hace desde los datos o desde las operaciones. Para la asignación de tareas se estudiará tanto la vía estática como dinámica, buscando un buen balanceo de la carga y una eficiente comunicación. Finalmente, con todo ello, se realizará la implementación teniendo en cuenta las características particulares de la plataforma hardware/software que será utilizada, y se buscará el mejor rendimiento posible en dicha plataforma.

De acuerdo con lo anterior, un alumno que trabaje la competencia CM3 de la Tecnología Específica de Computación estará en una buena disposición para abordar con éxito este TFG.

[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.

 

El uso de una plataforma basada en GPU requiere, por sus especiales características, un conocimiento más avanzado, que en otro tipo de plataformas, sobre el sistema de memoria, el procesador y el modelo de ejecución, para poder obtener una implementación del algoritmo que permita alcanzar un buen rendimiento del código desarrollado.

En este sentido, también se trabajará la competencia IC3 de la Tecnología de 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. Se analizará y evaluará la arquitectura de las GPUs para saber cómo obtener código óptimo, utilizando el toolkit disponible para este tipo de procesadores.

 

 

 

Medios a utilizar

Medios

Si no dispone de ellos, se pondrán a disposición del alumno todos los medios necesarios para la realización de este trabajo, y que básicamente son:

- Ordenador compuesto por CPU y GPU.
- Sistema operativo Linux Ubuntu
- NVIDIA CUDA Toolkit
- C, C++

 

 

Bibliografía

- S. Pacheco. An Introduction to Parallel Programming. Morgan Kaufmann, 2011.
- D. Kirk, W.-M. Hwu. Programming massively parallel processors. Morgan Kaufman Publishers. 2013 2ª edición
- A. García, S. Orts, J.M. Cecilia, J. García. Programación de GPUs usando CUDA. Ra-Ma.    2020 1ª edición
- C. Paar, J. Pelzl. Understanding Crytography, Springer, 2010

- 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