Análisis de estrategias de distribución dinámica de trabajo en el paradigma master worker sobre un cluster de multicore
Torres, Rocío Nahime
Análisis de estrategias de distribución dinámica de trabajo en el paradigma master worker sobre un cluster de multicore - 2014 - 152 p. : il. col. + 2 CD-ROM
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
DIF-M7071
CLUSTERS
SISTEMAS PARALELOS
PROCESAMIENTO PARALELO
N-reinas similitud de secuencias de ADN cluster multicore paradigma master worker modelo de comunicación por pasaje de mensajes modelo de comunicación híbrida
Análisis de estrategias de distribución dinámica de trabajo en el paradigma master worker sobre un cluster de multicore - 2014 - 152 p. : il. col. + 2 CD-ROM
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
DIF-M7071
CLUSTERS
SISTEMAS PARALELOS
PROCESAMIENTO PARALELO
N-reinas similitud de secuencias de ADN cluster multicore paradigma master worker modelo de comunicación por pasaje de mensajes modelo de comunicación híbrida