# Plantilla Oficial — Informe Técnico de Ingeniería (Paper Formato IEEE) **Asignatura:** TEL-420 · Sistemas Paralelos **Docente:** Ing. Elias Cassal Baldiviezo **Carrera:** Ingeniería Informática — Facultad de Ciencias Integradas de Yacuiba / F.I.R.N.T. **Universidad:** Universidad Autónoma "Juan Misael Saracho" (UAJMS) --- > **Instrucciones para el equipo:** > 1. Longitud máxima: **10 páginas**, formato a dos columnas estilo IEEE (interlineado simple, tipografía Times New Roman o equivalente 10 pt). > 2. Se entrega compilado en formato **PDF** dentro de la carpeta `docs/` del repositorio oficial de GitHub del equipo. > 3. El informe debe reflejar con rigor ingenieril el problema real abordado, la arquitectura de hardware empleada (estaciones Dell OptiPlex 7010 con 32 GB RAM), el modelo matemático, la paralelización y las mediciones de aceleración. --- ```text ======================================================================================== [TÍTULO DEL PROYECTO: CONCISO, TÉCNICO Y CONTEXTUALIZADO AL PROBLEMA REGIONAL] ======================================================================================== Primer Autor (Estudiante 1) Segundo Autor (Estudiante 2) Tercer Autor (Estudiante 3) Carrera de Ingeniería Informática Carrera de Ingeniería Informática Carrera de Ingeniería Informática UAJMS — Yacuiba, Bolivia UAJMS — Yacuiba, Bolivia UAJMS — Yacuiba, Bolivia correo.est1@uajms.edu.bo correo.est2@uajms.edu.bo correo.est3@uajms.edu.bo ``` --- ## Resumen *El resumen debe sintetizar en un único párrafo de entre 150 y 250 palabras: (1) el problema regional específico analizado en Yacuiba/Gran Chaco/Tarija, (2) el modelo computacional y matemático implementado, (3) el paradigma paralelo adoptado (memoria compartida con OpenMP, memoria distribuida con OpenMPI o solución híbrida/acelerada), (4) la infraestructura física y virtual utilizada (Dell OptiPlex 7010, Docker/Slurm), y (5) los resultados cuantitativos clave alcanzados (tiempo secuencial $T_1$, tiempo paralelo $T_p$, Speedup $S_p$ y Eficiencia $E_p$).* **Palabras clave:** Computación Paralela, Sistemas Distribuidos, OpenMP, OpenMPI, Speedup, Ley de Amdahl, Gran Chaco, Docker. ## Abstract *English translation of the abstract. Concise, professional, and mathematically precise summary covering the regional problem, algorithm, parallel implementation, benchmarking platform, and speedup achievements.* **Keywords:** Parallel Computing, Distributed Systems, OpenMP, OpenMPI, Speedup, Amdahl's Law, Benchmarking, HPC. --- ## 1. Introducción y Contextualización Regional ### 1.1 Contexto y Relevancia Territorial - Describa la problemática territorial o productiva seleccionada en Yacuiba, el departamento de Tarija o la cuenca del Chaco boliviano: - *Línea 1:* Monitoreo y dispersión hidrológica/ambiental en la cuenca del Río Pilcomayo. - *Línea 2:* Análisis geoespacial de focos de calor e incendios forestales mediante teledetección (Sentinel/Landsat). - *Línea 3:* Logística y optimización de redes de transporte transfronterizo (Yacuiba-Pocitos-Salvador Mazza). - *Línea 4:* Simulación agroclimática estocástica (Monte Carlo) de estrés hídrico en cultivos de la región. - *Línea 5:* Visión por computador distribuida para sanidad vegetal y fitopatología agrícola. - Justifique cuantitativamente la demanda computacional: demuestre por qué una solución secuencial convencional resulta insuficiente o inviable temporalmente para las dimensiones de datos o resolución requeridas. ### 1.2 Objetivos de Ingeniería - **Objetivo General:** Diseñar, implementar, desplegar y evaluar una solución paralela de alto rendimiento para el problema formulado. - **Objetivos Específicos:** 1. Formalizar el algoritmo de referencia y verificar su corrección matemática de forma secuencial ($T_1$). 2. Implementar la descomposición de datos y balanceo de carga bajo OpenMP / MPI / esquema híbrido. 3. Contenerizar la infraestructura del clúster (Docker/Compose o Slurm) en las PCs Dell OptiPlex 7010 (Core i7, 32 GB RAM). 4. Realizar un estudio de escalabilidad fuerte y débil validando las leyes de Amdahl y Gustafson. --- ## 2. Marco Teórico y Estado del Arte ### 2.1 Taxonomía de Flynn y Modelo Computacional - Clasificación de la arquitectura bajo la Taxonomía de Flynn (SISD, SIMD, MIMD, MISD). - Modelo de memoria implementado: - *Memoria Compartida (UMA / NUMA):* Coherencia de caché, espacio de direccionamiento común, sincronización mediante hilos. - *Memoria Distribuida (NORMA):* Nodos autónomos, comunicación por paso de mensajes (Message Passing), ausencia de memoria global. - *Arquitectura Híbrida:* Procesos MPI entre nodos y paralelismo de hilos OpenMP dentro de cada nodo. ### 2.2 Redes de Interconexión y Modelo LogP - Topología de red: características del enlace Ethernet Gigabit o interconexión de laboratorio. - Formalización del tiempo de comunicación: $$T_{comm} = \alpha + \beta \cdot m$$ donde $\alpha$ es la latencia de inicio (startup latency), $\beta = 1/B$ es el tiempo de transferencia por byte y $m$ es el tamaño del mensaje. - Impacto de la contención y patrones de comunicación (punto a punto vs. colectivas broadcast/reduction/scatter). --- ## 3. Diseño de la Arquitectura e Infraestructura ### 3.1 Especificación del Hardware de Laboratorio - **Equipo Anfitrión:** Dell OptiPlex 7010 / Torre de laboratorio. - **Procesador:** Intel Core i7 (especificar modelo exacto, número de núcleos físicos y núcleos lógicos / hyperthreading). - **Memoria RAM:** 32 GB DDR4/DDR5. - **Sistema Operativo:** Ubuntu Server 22.04 LTS / Ubuntu Desktop / WSL2 (Kernel Linux). ### 3.2 Topología Virtual y Contenerización - Modalidad seleccionada (Opción A: Clúster Docker/Apptainer multinodo con SSH sin contraseña; Opción B: Clúster Slurm virtualizado con Docker Compose). - Diagrama de arquitectura: ```text [Host Dell OptiPlex (32 GB RAM)] ├── [Nodo Maestro / Controller: 1 Contenedor / VM (8 GB RAM)] │ └── Slurmctld / OpenMPI Master / SSH Server ├── [Nodo Worker 1: 1 Contenedor / VM (8 GB RAM)] │ └── Slurmd / OpenMPI Worker / GCC Runtime └── [Nodo Worker 2: 1 Contenedor / VM (8 GB RAM)] └── Slurmd / OpenMPI Worker / GCC Runtime ``` - Configuración de red interna (bridge, DNS estático de nodos, claves criptográficas SSH compartidas). --- ## 4. Implementación Algorítmica Paralela ### 4.1 Algoritmo Secuencial Base - Descripción formal del algoritmo base y análisis de complejidad asintótica temporal $\mathcal{O}(f(n))$ y espacial $\mathcal{O}(g(n))$. - Verificación de exactitud del resultado secuencial como línea base de verdad. ### 4.2 Estrategia de Descomposición y Particionamiento - Tipo de paralelismo: paralelismo de datos (Data Parallelism) o descomposición funcional (Task Parallelism). - Particionamiento: estático en bloques (*block distribution*), cíclico (*round-robin*), o dinámico guiado (*work stealing*). - Tratamiento de condiciones de frontera: intercambio de halos (*ghost cells* / *halo exchange*) en problemas 2D si aplica. ### 4.3 Primitivas de Paralelización y Sincronización - **En OpenMP:** - Directivas utilizadas (`#pragma omp parallel for`, `reduction`, etc.). - Ámbito de variables (`private`, `shared`, `firstprivate`). - Estrategia de sincronización y mitigación de *false sharing* (alineamiento de caché, variables locales). - **En MPI:** - Comunicador: uso de `MPI_COMM_WORLD` o creación de subcomunicadores. - Comunicaciones punto a punto: uso de primitivas bloqueantes (`MPI_Send` / `MPI_Recv`) frente a no bloqueantes (`MPI_Isend` / `MPI_Irecv` con `MPI_Wait`) para solapar cómputo con comunicación. - Comunicaciones colectivas optimizadas: `MPI_Bcast`, `MPI_Scatter`, `MPI_Gather`, `MPI_Reduce` / `MPI_Allreduce`. --- ## 5. Resultados Experimentales y Análisis de Rendimiento ### 5.1 Metodología de Experimentación - Parámetros de prueba: - Hilos evaluados: $p \in \{1, 2, 4, 8, 16\}$. - Nodos/procesos evaluados: $N \in \{1, 2, 3, 4\}$. - Tamaños de problema evaluados: $N_{pequeño}$, $N_{mediano}$, $N_{masivo}$. - Condiciones de medición: mediciones repetidas ($k \ge 5$ iteraciones descartando fase de calentamiento), cálculo de media aritmética y desviación estándar. ### 5.2 Mediciones de Tiempo y Aceleración *Tabla 1. Tiempos de ejecución y métricas de aceleración.* | Tamaño del Problema ($N$) | Configuración ($p$ hilos / nodos) | Tiempo Promedio $T_p$ (s) | Speedup $S_p = \frac{T_1}{T_p}$ | Eficiencia $E_p = \frac{S_p}{p}$ | |---|---|---|---|---| | Mediano ($N=10^6$) | 1 (Secuencial) | | 1.00 | 100.0 % | | Mediano ($N=10^6$) | 2 | | | | | Mediano ($N=10^6$) | 4 | | | | | Mediano ($N=10^6$) | 8 | | | | | Masivo ($N=10^7$) | 1 (Secuencial) | | 1.00 | 100.0 % | | Masivo ($N=10^7$) | 2 | | | | | Masivo ($N=10^7$) | 4 | | | | | Masivo ($N=10^7$) | 8 | | | | ### 5.3 Curvas de Rendimiento y Análisis Teórico - **Gráfica de Speedup:** Representación de la curva empírica frente al Speedup Ideal Lineal ($S_p = p$) y frente a la cota teórica calculada con la **Ley de Amdahl**: $$S(p) = \frac{1}{(1 - f) + \frac{f}{p}}$$ donde $f$ es la fracción paralelizable estimada experimentalmente. - **Gráfica de Eficiencia:** Análisis de degradación de $E_p$ a medida que crece $p$. - **Escalabilidad Débil:** Evaluación bajo la **Ley de Gustafson**: $$S(p) = p - \alpha(p - 1)$$ al escalar proporcionalmente el tamaño de los datos con el número de núcleos. - **Cuellos de Botella Identificados:** Discusión sobre saturación del ancho de banda de memoria (*Memory Wall*), latencia de paso de mensajes por la red Ethernet y sobrecargas de sincronización. --- ## 6. Conclusiones e Impacto Social / Productivo - Síntesis de los logros técnicos demostrados en términos de escalabilidad y reducción de tiempo de cómputo. - Reflexión crítica sobre las limitaciones encontradas en la infraestructura del laboratorio. - Impacto real de la herramienta para la toma de decisiones en el contexto del Gran Chaco (sector productivo, prevención de riesgos ambientales o gestión pública regional). --- ## 7. Referencias Bibliográficas (Formato IEEE) 1. M. J. Quinn, *Parallel Programming in C with MPI and OpenMP*, New York: McGraw-Hill, 2004. 2. A. Grama, A. Gupta, G. Karypis, and V. Kumar, *Introduction to Parallel Computing*, 2nd ed., Boston: Addison-Wesley, 2003. 3. OpenMP Architecture Review Board, *OpenMP Application Programming Interface Version 5.2*, Nov. 2021. [En línea]. Disponible en: https://www.openmp.org/specifications/ 4. Message Passing Interface Forum, *MPI: A Message-Passing Interface Standard Version 4.0*, Jun. 2021. 5. J. L. Hennessy and D. A. Patterson, *Computer Architecture: A Quantitative Approach*, 6th ed., Cambridge, MA: Morgan Kaufmann, 2017.