Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore
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 planifi...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis Tesis de doctorado |
| Lenguaje: | Español |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/44478 https://doi.org/10.35537/10915/44478 |
| Aporte de: |
| id |
I19-R120-10915-44478 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Español |
| topic |
Ciencias Informáticas Best-First Search Algorithms Parallel algorithms algoritmos paralelos Clustering análisis de rendimiento multicore cluster de multicore |
| spellingShingle |
Ciencias Informáticas Best-First Search Algorithms Parallel algorithms algoritmos paralelos Clustering análisis de rendimiento multicore cluster de multicore Sanz, Victoria María Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore |
| topic_facet |
Ciencias Informáticas Best-First Search Algorithms Parallel algorithms algoritmos paralelos Clustering análisis de rendimiento multicore cluster de multicore |
| description |
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. |
| author2 |
De Giusti, Armando Eduardo |
| author_facet |
De Giusti, Armando Eduardo Sanz, Victoria María |
| format |
Tesis Tesis de doctorado |
| author |
Sanz, Victoria María |
| author_sort |
Sanz, Victoria María |
| title |
Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore |
| title_short |
Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore |
| title_full |
Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore |
| title_fullStr |
Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore |
| title_full_unstemmed |
Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore |
| title_sort |
análisis de rendimiento y optimización de algoritmos paralelos best-first search sobre multicore y cluster de multicore |
| publishDate |
2015 |
| url |
http://sedici.unlp.edu.ar/handle/10915/44478 https://doi.org/10.35537/10915/44478 |
| work_keys_str_mv |
AT sanzvictoriamaria analisisderendimientoyoptimizaciondealgoritmosparalelosbestfirstsearchsobremulticoreyclusterdemulticore |
| bdutipo_str |
Repositorios |
| _version_ |
1764820474507821056 |