Patrones de paralelismo de alto nivel basados en tareas

Resumen

tesis doctoral titulada "Patrones de Paralelismo de Alto Nivel Basados en Tareas", realizada por Antonio J. Dios García Martín y dirigida por Rafael Asenjo Plaza y María Ángeles González Navarro. La programación paralela es un requerimiento en la era multicore. Una aproximación prometedora para explotar las arquitecturas paralelas consiste en explotar los distintos patrones de paralelismo. En esta tesis nos centramos en los patrones de paralelismo de tipo ``pipeline'' y ``wavefront''. En cuanto a los paradigmas de programación paralela, hemos encontrado que el modelo basado en tareas se adapta perfectamente a estos dos patrones en arquitecturas de memoria compartida. Entre las razones que justifican este comportamiento cabe destacar que las tareas son más ligeras que los threads, permiten un mayor nivel de abstracción desde el punto de vista del programador lo que repercute en una mayor productividad y que los planificadores de tareas basados en {\it work-stealing\/} pueden balancear mejor la carga de trabajo. Las librerías basadas en tareas, como por ejemplo Intel Threading Building Blocks (TBB), son herramientas que ayudan a los programadores a desarrollar código paralelo de un modo productivo, gracias a constructores de alto nivel como las plantillas. TBB proporciona una plantilla para expresar paralelismo de pipeline a alto nivel pero está limitada a estructuras simples de pipeline y no soporta la posibilidad de que una etapa del pipeline genere varios elementos de salida por cada uno de entrada. En esta tesis, hemos resuelto esa limitación desarrollando un nuevo filtro para este tipo de etapas, que denominaremos etapas ``multioutput''. Experimentalmente y mediante un modelo analítico hemos comprobado que nuestro nuevo filtro aventaja a otras alternativas, principalmente gracias a que reduce el overhead relativo al uso de memoria y a la gestión de tareas al tiempo que promueve el paralelismo de grano fino lo que mejora la utilización de los recursos. En cuanto al patrón de tipo wavefront, ninguna librería basada en tareas proporciona soporte de alto nivel para una implementación productiva. Para cubrir esta necesidad, como primer paso, hemos comparado distintas implementaciones de bajo nivel de este tipo de problemas usando distintas librerías que representan el estado del arte en el modelo basado en tareas: TBB, OpenMP 3.0, Cilk y CnC. Discutimos la diferencias y particularidades de cada implementación desde el punto de vista del programador. Además realizamos distintos experimentos para identificar los factores que pueden limitar el rendimiento en cada una de las implementaciones. Encontramos que TBB provee una serie de características que permiten una implementación más eficiente y que en estos problemas, si el usuario guía al planificador, puede obtener un mejor rendimiento de la memoria cache aprovechando la característica de ``paso de tareas'' de TBB. Sin embargo, TBB no posee ninguna plantilla para implementar problemas de tipo wavefront por lo que hemos diseñado una al efecto. Para usar la nueva plantilla, el programador sólo debe proporcionar un fichero de definición indicando el patrón de dependencias y otro con el código que se ejecuta para cada celda del grid. Posteriormente, hemos incorporado varias optimizaciones a esta plantilla, de entre las cuales destacamos la gestión automática del tiling.