Análisis de estrategias de distribución dinámica de trabajo en el paradigma master worker sobre un cluster de multicore

Tesina (Licenciatura en Informática) - Universidad Nacional de La Plata. Facultad de Informática, 2014.

1. INTRODUCCIÓN -- 1.1 Procesamiento Paralelo -- 1.1.1 Concurrencia y paralelismo -- 1.1.2 Cómputo distribuido y paralelismo -- 1.2 Ventajas del procesamiento paralelo -- 1.2.1 Resolver problemas más grandes -- 1.2.2 Resolver problemas con límite de tiempo -- 1.2.3 Resolver problemas con mayor precisión -- 1.2.4 Límites en el cómputo serial -- 1.3 Limitaciones del procesamiento paralelo -- 1.4 Límites en el sistema de memoria -- 1.4.1 Mejorando la latencia de memoria mediante el uso de chaches -- 1.4.2 Impacto del ancho de banda -- 1.5 Definiciones y conceptos básicos -- 2. ARQUITECTURAS PARALELAS -- 2.1 Memoria compartida -- 2.1.1 Multicores -- 2.1.2 Modelo de comunicación -- 2.1.2.1 Hilos -- 2.1.2.2 Pthread -- 2.2 Memoria distribuida -- 2.2.1 Cluster -- 2.2.2 Modelo de comunicación -- 2.2.2.1 Operaciones send y receive -- 2.2.2.2 Costo de la comunicación -- 2.2.2.3 MPI -- 2.3 Memoria compartida distribuida -- 2.3.1 Cluster de multicores -- 2.3.2 Modelo de comunicación -- 3.DISEÑO DE APLICACIONES -- 3.1 Etapas de diseño -- 3.1.1 Etapa de particionamiento -- 3.1.2 Etapa de comunicación -- 3.1.3 Etapa de aglomeración -- 3.1.3.1 Incrementando la granularidad -- 3.1.4 Etapa de mapeo -- 3.1.4.1 Mapeo estático -- 3.1.4.1.1 Mapeos basados en el particionamiento de datos -- 3.1.4.2 Mapeo dinámico -- 3.1.4.2.1 Esquema centralizado -- 3.1.4.2.2 Esquema distribuido -- 3.2 Paradigmas de programación -- 3.2.1 Paradigma Master-Worker -- 3.2.1.1 Modelo Uno -- 3.2.1.2 Modelo Dos -- 3.2.1.3 Modelo Tres -- 4. EVALUACIÓN DE SISTEMAS PARALELOS -- 4.1 Fuentes de overhead -- 4.1.1 Interacción entre procesos -- 4.1.2 Ocio de los procesadores -- 4.1.3 Cómputo extra asociado a la paralelización -- 4.2 Métricas -- 4.2.1 Tiempo de ejecución -- 4.2.2 Desbalance de carga -- 4.2.3 Speedup -- 4.2.4 Eficiencia -- 4.2.5 Escalabilidad -- 5. PROBLEMA "N-REINAS" -- 5.1 Origen del problema -- 5.2 Descripción del problema -- 5.3 Algoritmo secuencial -- 5.4 Algoritmo paralelo -- 5.4.1 Solución con pasaje de mensajes -- 5.4.1.1 Un nivel de master -- 5.4.1.2 Dos niveles de master -- 5.4.2 Solución Hibrida -- 6. PROBLEMA "BÚSQUEDA DE SIMILITUD MÁXIMA EN SECUENCIAS DE ADN" -- 6.1 Bioinformática -- 6.1.1 ¿Qué es? -- 6.1.2 ¿Porque es importante? -- 6.2 Descripción del problema -- 6.2.1 Conceptos preliminares -- 6.2.2 Alineación de secuencias -- 6.2.3 Subsecuencias -- 6.2.4 Similitud local y global -- 6.2.5 Algoritmo Smith-Waterman -- 6.3 Algoritmo secuencial -- 6.4 Algoritmo paralelo -- 6.4.1 Solución con pasaje de mensajes -- 6.4.1.1 Un nivel de master -- 6.4.1.2 Dos niveles de master -- 6.4.2 Solución Hibrida -- 7.EXPERIMENTACIÓN -- 7.1 Arquitectura utilizada -- 7.2 N-reinas -- 7.2.1 Comparación de las tres soluciones -- 7.2.2 Análisis del comportamiento cuando crece la arquirectura -- 7.3 Búsqueda de similitud máxima entre secuencias de ADN -- 7.3.1 Comparación de las tres soluciones -- 7.3.2 Análisis del comportamiento cuando crece la arquirectura -- 8. CONCLUSIONES -- 9. APÉNDICE A - DETALLE DE LOS RESULTADOS PARA "N-REINAS" -- 10. APÉNDICE B-DETALLE DE LOS RESULTADOS PARA "BÚSQUEDA DE SIMILITUD MÁXIMA EN SECUENCIAS DE ADN" -- 11. APÉNDICE C - CÓDIGOS DEL PROBLEMA "N-REINAS" -- 12. APÉNDICE D – CÓDIGOS DEL PROBLEMA "BÚSQUEDA DE SIMILITUD MÁXIMA EN SECUENCIAS DE ADN" -- 13. ANEXO A – PHTREADS -- 14. ANEXO B – MPI -- 15. BIBLIOGRAFÍA