Fraguela, Basilio B.Cabaleiro, José CarlosÁlvarez Martínez, Millán2024-08-222024-08-222024http://hdl.handle.net/2183/38659[Abstract]: In the multicore architectures and distributed systems available today, exploitingapplication parallelism has become a necessity to achieve high-performance levels.Being able to take advantage of all the resources of these systems through parallelprogramming is not trivial, and commonly requires great eort on the part ofthe programmer and a high level of knowledge of the technology and systems used.Although there is multiple research in the eld of parallel application development,many of the current solutions have signicant limitations in terms of their applicability,performance and/or usability. This Thesis introduces new tools to support thedevelopment of parallel applications in the form of software libraries with the aim ofreducing their development and maintenance costs. These tools provide ecient solutionsto complex problems, internally making use of advanced parallel techniquesto achieve high performance, while remaining user-friendly. The rst two proposalsare parallel skeleton libraries that aim to solve divide-and-conquer problems, especiallythose with large imbalances and high levels of recursion. The rst does itfor shared memory systems, while the second does it for hybrid distributed-sharedmemory systems. Finally, a new thread-level speculative parallelization model andits implementation in a library are presented. This strategy makes use of speculativeparallel execution techniques to allow the parallelization of almost any loop,even those with dependencies that are initially dicult to parallelize, with hardlyany modications to the original code. The language used for the implementationsis C++. This widely used language provides an excellent performance level while allowing general programming through templates and other abstractions, which areperfect for developing advanced libraries with great applicability.[Resumen]: En las arquitecturas multinúcleo y sistemas distribuidos disponibles en la actualidad,explotar el paralelismo de las aplicaciones es necesario para alcanzar altos niveles de rendimiento. Lograr aprovechar todos los recursos de estos sistemas mediante la programación paralela no es algo trivial, y comúnmente se requiere un gran esfuerzo por parte del programador y un alto conocimiento de la tecnología y de los sistemas utilizados. A pesar de que existen múltiples investigaciones en el campo de desarrollo de aplicaciones paralelas, muchas de las soluciones actuales tienen limitaciones significativas en cuanto a su aplicabilidad, rendimiento y/o usabilidad. En esta Tesis se presentan nuevas herramientas de soporte al desarrollo de aplicaciones paralelas en forma de librerías de software con el objetivo de reducir así sus costes de desarrollo y mantenimiento. Estas herramientas proporcionan soluciones eficientes a problemas complejos, haciendo uso internamente de avanzadas técnicas paralelas para alcanzar altos rendimientos, mientras se mantiene de fácil uso para el usuario.Las dos primeras propuestas son librerías paralelas basadas en esqueletos que tienen como objetivo resolver problemas de divide y vencerás, especialmente aquellos desbalanceados y con altos niveles de recursividad. La primera lo hace para sistemas de memoria compartida, mientras que la segunda lo hace para sistemas híbridos de memoria distribuida-compartida. Finalmente, se presenta un nuevo modelo de paralelización especulativa a nivel de hilos y su implementación en una librería. Esta estrategia hace uso de técnicas de ejecución paralela especulativa para permitir la paralelización de casi cualquier bucle, incluso aquellos con dependencias que los hacen inicialmente difíciles de paralelizar, sin apenas necesitar realizar modificaciones en el código original. El lenguaje empleado para las implementaciones es C++, pues es un lenguaje ampliamente utilizado que proporciona un muy buen nivel de rendimiento,al mismo tiempo que permite programación genérica mediante plantillas y otras abstracciones, las cuales son perfectas para el desarrollo de librerías avanzadas de gran aplicabilidad.[Resumo]: Nas arquitecturas multinúcleo e sistemas distribuídos dispoñibles na actualidade,explotar o paralelismo das aplicacións é necesario para alcanzar altos niveis de rendemento. Poder aproveitar todos os recursos destes sistemas a través da programación paralela non é nada trivial, e normalmente require un gran esforzo por partedo programador e un alto nivel de coñecemento da tecnoloxía e dos sistemas empregados.Aínda que existen múltiples investigacións no campo do desenvolvementode aplicacións paralelas, moitas das solucións actuais teñen limitacións significativas en canto a súa aplicabilidade, rendemento e/ou usabilidade. Esta Tese presentanovas ferramentas para apoiar o desenvolvemento de aplicacións paralelas en formade librarías de software co obxectivo de reducir os seus custos de desenvolvemento emantemento. Estas ferramentas proporcionan solucións eficientes a problemas complexos,facendo uso internamente de técnicas paralelas avanzadas para alcanzar altos rendementos, mantendo un uso amigable para o usuario. As dúas primeiras propostas son librerías paralelas baseadas en esqueletos que teñen como obxectivo resolver problemas de divide e vencerás, especialmente aqueles desbalanceados e con altos niveis de recursividade. A primeira faino para sistemas de memoria compartida, mentresque a segunda faino para sistemas híbridos de memoria distribuída-compartida.Finalmente, preséntase un novo modelo de paralelización especulativa a nivel de fíos xunto coa súa implementación nunha librería. Esta estratexia fai uso de técnicas deexecución paralela especulativa para permitir a paralelización de case calquera bucle,incluso aqueles con dependencias que os fan inicialmente difíciles de paralelizar, sen apenas necesitar de modificacións no código orixinal. A linguaxe empregada paraas implementacións é C++, pois trátase dunha linguaxe amplamente utilizada que proporciona un moi bo nivel de rendemento, ao tempo que permite programación xenérica mediante modelos e outras abstraccións, perfectos para o desenvolvemento de librarías avanzadas de gran aplicabilidade.engOs titulares dos dereitos de propiedade intelectual autorizan a visualización do contido desta tese a través de Internet, así como a súa reproducción, gravación en soporte informático ou impresión para o seu uso privado e/ou con fins de estudo e de investigación. En nengún caso se permite o uso lucrativo deste documento. Estos dereitos afectan tanto ó resumo da tese como o seu contido Los titulares de los derechos de propiedad intelectual autorizan la visualización del contenido de esta tesis a través de Internet, así como su repoducción, grabación en soporte informático o impresión para su uso privado o con fines de investigación. En ningún caso se permite el uso lucrativo de este documento. Estos derechos afectan tanto al resumen de la tesis como a su contenidoAlgorithmic skeletonsTemplate metaprogrammingDivide-and-conquerLoad balancingSpeculative parallelismAutomatic parallelizationThread-level speculationMulti-core clustersHybrid parallelismdoctoral thesisopen access