Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore

Resumen

Contenido

Capítulo 1: Introducción
1.1 Motivación
1.2 Objetivos y contribuciones 
1.3 Publicaciones derivadas

Capítulo 2: Algoritmos Secuenciales de Búsqueda
2.1 Construcción del espacio de estados del problema 
2.2 Algoritmos de búsqueda 
2.2.1 Propiedades y complejidad algorítmica
2.2.2 Algoritmos de búsqueda no informada
2.2.2.1 Estrategia Depth-First 
2.2.2.2 Estrategia Breadth-First 
2.2.2.3 Iterative Deepening Depth-First 
2.2.2.4 Búsqueda de costo uniforme 
2.2.3 Algoritmos de búsqueda informada 
2.2.3.1 A* 
2.2.3.2 Iterative Deepening A* (IDA*)
2.2.3.3 Frontier Search A*
2.3 Discusión y conclusiones

Capítulo 3: Caracterización del Caso de Estudio 
3.1 Definición del problema 
3.2 Solubilidad
3.2.1 Algoritmo para la detección de solubilidad 
3.3 Funciones heurísticas para el problema del Puzzle 
3.3.1 Suma de las Distancias de Manhattan (SDM)
3.3.2 Conflictos Lineales
3.3.3 Últimos Movimientos (“Last Moves”) 
3.3.4 Fichas de las Esquinas del Puzzle (“Corner Tiles”)
3.4 Discusión y conclusiones

Capítulo 4: Arquitecturas Paralelas y Herramientas de Programación
4.1 Clasificación de arquitecturas paralelas 
4.2 Arquitectura tipo Cluster
4.3 Evolución hacia la arquitectura multicore
4.4 Bibliotecas para el desarrollo de aplicaciones paralelas 
4.4.1 MPI 
4.4.2 Pthreads
4.5 Discusión y conclusiones 
Capítulo 5: Algoritmos Paralelos Best-First Search 
5.1 Análisis de rendimiento. Causas de degradación de rendimiento de un sistema paralelo
5.1.1 Métricas: Speedup y Eficiencia 
5.1.2 Escalabilidad
5.1.3 Métricas para Algoritmos de Búsqueda Paralela Best-First
5.2 Estrategia Centralizada: A* Paralelo con Estructuras de Datos Globales
5.3 Estrategia Distribuida: A* Paralelo con Estructuras de Datos Locales
5.4 Algoritmos para la Detección de Terminación de Aplicaciones con Cómputo Distribuido
5.4.1 Modelo del sistema 
5.4.2 Algoritmo de terminación de Dijkstra 
5.4.3 Algoritmo de terminación de Mattern de los 4 contadores
5.5 Importancia de la Biblioteca de Gestión de Memoria Dinámica
5.6 Discusión y conclusiones

Capítulo 6: Implementaciones 
6.1 Algoritmo secuencial A* 
6.2 Algoritmos Paralelos 
6.2.1 HDA* para memoria distribuida 
6.2.1.1 Síntesis 
6.2.1.2 Variables 
6.2.1.3 Procesamiento 
6.2.1.4 Ineficiencias para arquitecturas de memoria compartida 
6.2.2 HDA* para memoria compartida 
6.2.2.1 Síntesis
6.2.2.2 Variables compartidas por los threads
6.2.2.3 Variables Locales al thread
6.2.2.4 Procesamiento 
6.2.2.5 Consideraciones sobre Mutex lock, Spin lock y Semáforos 
6.2.2.6 Gestión de memoria dinámica con Jemalloc 
6.3 Discusión y conclusiones

Capítulo 7: Resultados
7.1 A* secuencial 
7.1.1 Efecto de la heurística 
7.1.2 Efecto de la biblioteca de gestión de memoria dinámica 
7.1.3 Efecto de la técnica “Memory pool”
7.2 HDA* para memoria compartida (HDA* Pthreads)
7.2.1 Efecto en el rendimiento de la espera pasiva y espera activa 
7.2.2 Efecto en el rendimiento de la técnica Memory Pool 
7.2.3 Efecto en el rendimiento de los parámetros LNPI y LNPT 
7.2.3.1 Límite de Nodos Procesados Por Iteración (LNPI) 
7.2.3.2 Límite de Nodos Por Transferencia (LNPT)
7.2.4 Desvío Estándar del Tiempo de Ejecución 
7.2.5 Análisis de rendimiento
7.2.5.1 Factores de overhead 
7.3 HDA* para memoria distribuida (HDA* MPI) 
7.3.1 Comportamiento sobre multicore 
7.3.1.1 Impacto de los parámetros LNPI y LNPT sobre el rendimiento 
7.3.1.1.1 Límite de Nodos Procesados Por Iteración (LNPI) 
7.3.1.1.2 Límite de Nodos Por Transferencia (LNPT)
7.3.1.2 Desvío Estándar del Tiempo de Ejecución
7.3.1.3 Análisis de rendimiento 
7.3.1.3.1 Factores de Overhead
7.3.2 Comportamiento sobre cluster de multicore
7.3.2.1 Impacto de los parámetros LNPI y LNPT sobre el rendimiento 
7.3.2.1.1 Límite de Nodos Procesados Por Iteración (LNPI)
7.3.2.1.2 Límite de Nodos Por Transferencia (LNPT)
7.3.2.2 Desvío Estándar del Tiempo de Ejecución
7.3.2.3 Análisis de Rendimiento 
7.3.2.3.1 Factores de Overhead 
7.4 Comparación del consumo de memoria de HDA* Pthreads y HDA* MPI sobre máquina multicore
7.5 Comparación del rendimiento de HDA* Pthreads y HDA* MPI sobre máquina multicore 
7.6 Discusión y conclusiones

Capítulo 8: Algoritmo Paralelo HDA* Híbrido
8.1 Aplicaciones Paralelas Híbridas
8.2 Algoritmo HDA* Híbrido 
8.2.1 Síntesis
8.2.2 Esquema de comunicación vía mensajes
8.2.3 Esquema de comunicación vía variables compartidas
8.2.4 Detección de terminación local y Detección de terminación global
8.2.5 Variables globales a los threads de un proceso 
8.2.6 Variables locales a cada thread de un proceso
8.2.7 Procesamiento
8.3 Discusión y conclusiones

Capítulo 9: Conclusiones y Líneas de Trabajo Futuro 

Apéndice A: Correctitud del Algoritmo de Verificación de Solubilidad para el N2-1 Puzzle 
A.1 Configuraciones legales e ilegales 
A.2 Fórmula de solubilidad
A.2.1 Proposición para N par 
A.2.2 Proposición para N impar
A.3 Conclusiones

Apéndice B: Función de Zobrist

Apéndice C: Configuraciones Utilizadas del 15-Puzzle 

Bibliografía