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

Detalles Bibliográficos
Autor Principal: Sanz, Victoria María
Otros autores o Colaboradores: De Giusti, Armando Eduardo (Director/a), Naiouf, Ricardo Marcelo (Codirector/a)
Formato: Tesis
Lengua:español
Datos de publicación: 2014
Temas:
ALGORITMOS PARALELOS
ARQUITECTURAS MULTICORE
algoritmo HDA
Acceso en línea:http://catalogo.info.unlp.edu.ar/meran/getDocument.pl?id=2549
Consultar en el Cátalogo
Descripción Física:1 archivo (3,3 MB) : il. col.
Tabla de Contenidos:
  • 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

Ejemplares similares