Hacia la paralelización automática y eficiente de la programación dinámica

Abstract

Esta memoria se enmarca en el contexto de la computación en paralelo y de la resolución de problemas de programación dinámica. Un dificultad inherente al paralelismo la encontramos en la distancia que actualmente existe entre las arquitecturas paralelas y el usuario no especializado. El desarrollo de esqueletos de programas y procedimientos generales con los que abordar la programación en paralelo, está siendo motivo de numerosos trabajos y estudios como un instrumento con que reducir esta distancia. Los objetivos de esta memoria se centran en el desarrollo de esqueletos y herramientas de alto nivel que permitan al usuario la implementación de programas paralelos de programación dinámica independientes de la arquitectura destino. La programación dinámica es una importante técnica de resolución de problemas que ha sido ampliamente utilizada en numerosos campos de la ciencia. Es un hecho establecido que la técnica conlleva un consumo de cómputo y de memoria que, en ocasiones, hacen necesario e luso de computadores paralelos para poder hacer un uso efectivo de la misma. El esqueleto permite a un usuario no experto en paralelismo obtener códigos de programación dinámica paralelos partiendo únicamente de códigos secuenciales. La base de la paralelización de estos algoritmos la encontramos en el paralelismo de segmentación o paralelismo pipeline. Un inconveniente añadido al uso de los computadores aparece con la gran variedad y diversidad de arquitecturas. Aunque la portabilidad de los programas paralelos está garantizada mediante el uso de librerías estándar, es aún una cuestión abierta la portabilidad de la eficiencia de tales programas. Un contraste decepcionante lo encontramos en el pico de rendimiento que en teoría ofrecen las arquitecturas paralelas y el rendimiento que en la práctica se obtiene. En este sentido la memoria de tesis aborda y resuelve el problema de sintonizado de aplicaciones pipeline s