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.
| Identifer | oai:union.ndltd.org:SEDICI/oai:sedici.unlp.edu.ar:10915/44478 |
| Date | January 2015 |
| Creators | Sanz, Victoria María |
| Contributors | De Giusti, Armando Eduardo, Naiouf, Marcelo |
| Source Sets | Universidad Nacional de La Plata, Sedici |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis, Tesis de doctorado |
| Rights | http://creativecommons.org/licenses/by-nc/2.5/ar/, Creative Commons Attribution-NonCommercial 2.5 Argentina (CC BY-NC 2.5) |
Page generated in 0.2918 seconds