RT Dissertation/Thesis
T1 Parallel source code transformation techniques using design patterns
A1 Río Astorga, David del
AB In recent years, the traditional approaches for improving performance, such as increasingthe clock frequency, has come to a dead-end. To tackle this issue, parallel architectures,such as multi-/many-core processors, have been envisioned to increasethe performance by providing greater processing capabilities. However, programmingefficiently for this architectures demands big efforts in order to transform sequentialapplications into parallel and to optimize such applications. Compared tosequential programming, designing and implementing parallel applications for operatingon modern hardware poses a number of new challenges to developers suchas data races, deadlocks, load imbalance, etc.To pave the way, parallel design patterns provide a way to encapsulate algorithmicaspects, allowing users to implement robust, readable and portable solutionswith such high-level abstractions. Basically, these patterns instantiate parallelismwhile hiding away the complexity of concurrency mechanisms, such as thread management,synchronizations or data sharing. Nonetheless, frameworks following thisphilosophy does not share the same interface and users require understanding differentlibraries, and their capabilities, not only to decide which fits best for theirpurposes but also to properly leverage them. Furthermore, in order to parallelizethese applications, it is necessary to analyze the sequential code in order to detect theregions of code that can be parallelized that is a time consuming and complex task.Additionally, different libraries targeted to specific devices provide some algorithmsimplementations that are already parallel and highly-tuned. In these situations, it isalso necessary to analyze and determine which routine implementation is the mostsuitable for a given problem.To tackle these issues, this thesis aims at simplifying and minimizing the necessaryefforts to transform sequential applications into parallel. This way, resultingcodes will improve their performance by fully exploiting the available resourceswhile the development efforts will be considerably reduced. Basically, in this thesis,we contribute with the following. First, we propose a technique to detect potentialparallel patterns in sequential code. Second, we provide a novel generic C++ interfacefor parallel patterns which acts as a switch among existing frameworks. Third,we implement a framework that is able to transform sequential code into parallelusing the proposed pattern discovery technique and pattern interface. Finally, wepropose mechanisms that are able to select the most suitable device and routine implementationto solve a given problem based on previous performance information.The evaluation demonstrates that using the proposed techniques can minimize therefactoring and optimization time while improving the performance of the resultingapplications with respect to the original code.
AB En los últimos años, las técnicas tradicionales para mejorar el rendimiento, como esel caso del incremento de la frecuencia de reloj, han llegado a sus límites. Con elfin de seguir mejorando el rendimiento, se han desarrollado las arquitecturas paralelas,las cuales proporcionan un incremento del rendimiento al estar provistas demayores capacidades de procesamiento. Sin embargo, programar de forma eficientepara estas arquitecturas requieren de grandes esfuerzos por parte de los desarrolladores.Comparado con la programación secuencial, diseñar e implementar aplicacionesparalelas enfocadas a trabajar en estas arquitecturas presentan una grancantidad de dificultades como son las condiciones de carrera, los deadlocks o el incorrectobalanceo de la carga.En este sentido, los patrones paralelos son una forma de encapsular aspectosalgorítmicos de las aplicaciones permitiendo el desarrollo de soluciones robustas,portables y legibles gracias a las abstracciones de alto nivel. En general, estos patronesson capaces de proporcionar el paralelismo a la vez que ocultan las complejidadesderivadas de los mecanismos de control de concurrencia necesarios como elmanejo de los hilos, las sincronizaciones o la compartición de datos. No obstante,los diferentes frameworks que siguen esta filosofía no comparten una única interfazlo que conlleva que los usuarios deban conocer múltiples bibliotecas y sus capacidades,con el fin de decidir cuál de ellos es mejor para una situación concreta ycomo usarlos de forma eficiente. Además, con el fin de paralelizar aplicaciones existentes,es necesario analizar e identificar las regiones del código que pueden ser paralelizadas,lo cual es una tarea ardua y compleja. Además, algunos algoritmos ya seencuentran implementados en paralelo y optimizados para arquitecturas concretasen diversas bibliotecas. Esto da lugar a que sea necesario analizar y determinar queimplementación concreta es la más adecuada para solucionar un problema dado.Para paliar estas situaciones, está tesis busca simplificar y minimizar el esfuerzonecesario para transformar aplicaciones secuenciales en paralelas. De esta forma,los códigos resultantes serán capaces de explotar los recursos disponibles a la vezque se reduce considerablemente el esfuerzo de desarrollo necesario. En general,esta tesis contribuye con lo siguiente. En primer lugar, se propone una técnica dedetección de patrones paralelos en códigos secuenciales. En segundo lugar, se presentauna interfaz genérica de patrones paralelos para C++ que permite seleccionarla implementación de dichos patrones proporcionada por frameworks ya existentes.En tercer lugar, se introduce un framework de transformación de código secuenciala paralelo que hace uso de las técnicas de detección de patrones y la interfazpresentadas. Finalmente, se proponen mecanismos capaces de seleccionar la implementaciónmás adecuada para solucionar un problema concreto basándose en elrendimiento obtenido en ejecuciones previas. Gracias a la evaluación realizada se hapodido demostrar que uso de las técnicas presentadas pueden minimizar el tiemponecesario para transformar y optimizar el código a la vez que mejora el rendimientode las aplicaciones transformadas.
YR 2018
FD 2018-07
LK https://hdl.handle.net/10016/27740
UL https://hdl.handle.net/10016/27740
LA eng
NO Mención Internacional en el título de doctor
DS e-Archivo
RD 18 jul. 2024