|
|
|
|
| LEADER |
00000nam a2200000 a 4500 |
| 003 |
AR-LpUFIB |
| 005 |
20250311170522.0 |
| 008 |
230201s2014 ag a om 000 0 spa d |
| 024 |
8 |
|
|a DIF-M8636
|b 8861
|z DIF007911
|
| 040 |
|
|
|a AR-LpUFIB
|b spa
|c AR-LpUFIB
|
| 100 |
1 |
|
|a Sanz, Victoria María
|
| 245 |
1 |
0 |
|a Análisis de rendimiento y optimización de algoritmos paralelos Best-First Search sobre multicore y cluster de multicore
|
| 260 |
|
|
|c 2014
|
| 300 |
|
|
|a 1 archivo (3,3 MB) :
|b il. col.
|
| 502 |
|
|
|a Tesis (Doctorado en Ciencias Informáticas) - Universidad Nacional de La Plata. Facultad de Informática, 2014.
|
| 505 |
0 |
|
|a 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
|
| 650 |
|
4 |
|a ALGORITMOS PARALELOS
|
| 650 |
|
4 |
|a ARQUITECTURAS MULTICORE
|
| 653 |
|
|
|a algoritmo HDA
|
| 700 |
1 |
|
|a De Giusti, Armando Eduardo ,
|e Director/a
|
| 700 |
1 |
|
|a Naiouf, Ricardo Marcelo ,
|e Codirector/a
|
| 856 |
4 |
0 |
|u http://catalogo.info.unlp.edu.ar/meran/getDocument.pl?id=2549
|
| 942 |
|
|
|c TE
|
| 952 |
|
|
|0 0
|1 0
|4 0
|6 TES_1437
|7 0
|9 83886
|a DIF
|b DIF
|d 2025-03-11
|i DIF-05202
|l 0
|o TES 14/37
|p DIF-05202
|r 2025-03-11 17:05:22
|w 2025-03-11
|y TE
|
| 952 |
|
|
|0 0
|1 0
|4 0
|7 3
|8 BD
|9 83887
|a DIF
|b DIF
|d 2025-03-11
|l 0
|r 2025-03-11 17:05:22
|u https://doi.org/10.35537/10915/44478
|w 2025-03-11
|y TE
|
| 952 |
|
|
|0 0
|1 0
|4 0
|7 3
|8 BD
|9 83888
|a DIF
|b DIF
|d 2025-03-11
|l 0
|r 2025-03-11 17:05:22
|u http://catalogo.info.unlp.edu.ar/meran/getDocument.pl?id=2549
|w 2025-03-11
|y TE
|
| 999 |
|
|
|c 57684
|d 57684
|
