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

Tesis (Doctorado en Ciencias Informáticas) - Universidad Nacional de La Plata. Facultad de Informática, 2014.

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