En este trabajo se realiza un análisis comparativo de las técnicas de programación paralela, en el que puede observarse cómo la evolución en el diseño de la solución a un mismo problema permite maximizar la performance de algoritmos paralelos en arquitecturas clúster de multicore. Este análisis se realiza utilizando un caso de estudio ampliamente estudiado en el área como lo es la multiplicación de matrices. Para ello, se implementaron diferentes soluciones para resolver el problema, partiendo de soluciones de alto nivel y bajo acoplamiento con la arquitectura, hasta llegar a soluciones de bajo nivel, dependientes de la arquitectura de prueba subyacente y que aprovechan las características de la misma, como por ejemplo la jerarquía de memoria. Las soluciones implementadas son una solución utilizando pasaje de mensajes, y tres soluciones híbridas teniendo en cuenta diferentes librerías de programación paralela (OpenMPI, Pthreads y OpenMP), y diferentes esquemas de descomposición de los datos. Asimismo, las pruebas de los algoritmos implementados se analizan desde distintos puntos de vista. Por un lado, escalando el tamaño del problema a resolver y por otro, escalando la cantidad de núcleos de procesamiento utilizados.

El objetivo general de esta tesis se centra en la investigación y desarrollo de algoritmos paralelos de búsqueda en grafos best-first search para arquitecturas multicore y cluster de multicore, que mejoran los existentes y se utilizan para resolver problemas de optimización combinatoria y de planificación, acompañado de un análisis de rendimiento (speedup, eficiencia, escalabilidad) de los mismos. La temática propuesta es de interés en la actualidad por la complejidad computacional de dichos algoritmos de búsqueda y las posibilidades que brindan las arquitecturas mencionadas. Los algoritmos presentados en esta tesis pueden aplicarse para resolver problemas reales como planificación de rutas óptimas, navegación automática de un robot o vehículo, alineamiento óptimo de secuencias, entre otros. Los temas de investigación derivados son múltiples y se refieren tanto a la paralelización de algoritmos sobre (a) arquitecturas de memoria compartida, como son los multicore (b) arquitecturas de memoria distribuida, como son los clusters (c) y también sobre arquitecturas híbridas, tal es el caso de los clusters de multicore. El aporte de la tesis es el desarrollo de dos algoritmos paralelos best-first-search propios, uno apto para su ejecución sobre máquinas de memoria compartida (multicore) y otro apto para máquinas de memoria distribuida (cluster), basados en el algoritmo HDA* (Hash Distributed A*), en los cuales se incluyen técnicas originales que optimizan su rendimiento. Asimismo, se presenta un análisis de rendimiento de los algoritmos desarrollados a medida que escala la carga de trabajo y la arquitectura paralela subyacente. Para finalizar, se compara la memoria consumida por ambos algoritmos y el rendimiento alcanzado cuando se los ejecuta sobre una máquina multicore; estos análisis presentan originalidad en el área. Los resultados arrojados indican que se obtendría un beneficio al convertir HDA* en una aplicación híbrida, cuando la arquitectura subyacente es un cluster de multicore, por lo que se sientan las bases para éste algoritmo híbrido.

La presente Tesina de Grado tiene como objetivo la investigación y el estudio de las plataformas de memoria compartida GPU y cluster de Multicore para la resolución de problemas con alta demanda computacional. Se presentan soluciones al problema planteado con el fin de comparar rendimiento en sus versiones secuencial, paralela con memoria compartida, paralela con pasaje de mensajes, paralela híbrida y paralela en GPU. Se analiza la bondad de las soluciones en relación al tiempo de ejecución y aceleración, y se introduce el análisis de consumo energético.