HPC02_ArquitecturasModelos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f1b06738",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Computación de Alto Desempeño</h1>\n",
    "<h1 align=\"center\">Arquitecturas de Memoria y Modelos de Programación en Computadoras Paralelas</h1>\n",
    "<h1 align=\"center\">2024</h1>\n",
    "<h1 align=\"center\">MEDELLÍN - COLOMBIA </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b32776e",
   "metadata": {},
   "source": [
    "*** \n",
    "|[![Outlook](https://img.shields.io/badge/Microsoft_Outlook-0078D4?style=plastic&logo=microsoft-outlook&logoColor=white)](mailto:calvarezh@udemedellin.edu.co)||[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/carlosalvarezh/HPC/blob/main/HPC02_ArquitecturasModelos.ipynb)\n",
    "|-:|:-|--:|\n",
    "|[![LinkedIn](https://img.shields.io/badge/linkedin-%230077B5.svg?style=plastic&logo=linkedin&logoColor=white)](https://www.linkedin.com/in/carlosalvarez5/)|[![@alvarezhenao](https://img.shields.io/twitter/url/https/twitter.com/alvarezhenao.svg?style=social&label=Follow%20%40alvarezhenao)](https://twitter.com/alvarezhenao)|[![@carlosalvarezh](https://img.shields.io/badge/github-%23121011.svg?style=plastic&logo=github&logoColor=white)](https://github.com/carlosalvarezh)|\n",
    "\n",
    "<table>\n",
    " <tr align=left><td><img align=left src=\"https://github.com/carlosalvarezh/Curso_CEC_EAFIT/blob/main/images/CCLogoColorPop1.gif?raw=true\" width=\"25\">\n",
    " <td>Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license.(c) Carlos Alberto Alvarez Henao</td>\n",
    "</table>\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b5d6c30",
   "metadata": {},
   "source": [
    "# Aviso Legal sobre estas Notas de Clase\n",
    "\n",
    "Las presentes notas de clase han sido elaboradas con fines educativos y como material de apoyo para el aprendizaje y comprensión de la computación paralela. Estas notas están basadas en información y contenidos derivados del tutorial *[\"Introduction to Parallel Computing Tutorial\"](https://hpc.llnl.gov/documentation/tutorials/introduction-parallel-computing-tutorial)* disponible en el sitio web del *Laboratorio Nacional Lawrence Livermore* (https://hpc.llnl.gov/). Este material se proporciona tal cual, sin garantías de exactitud completa o de la aplicabilidad para un fin particular.\n",
    "\n",
    "A pesar de que se ha hecho un esfuerzo por asegurar la precisión y utilidad de estas notas, los usuarios deben tener en cuenta que los conceptos, aplicaciones y técnicas de la computación paralela están en constante evolución, y se recomienda consultar múltiples fuentes y la documentación oficial más actual para obtener la información más reciente y completa.\n",
    "\n",
    "Por favor, considere que cualquier ejemplo, referencia o cita de \"Introducción a la Computación Paralela\" se proporciona con el objetivo de ilustrar los conceptos y principios básicos de la computación paralela y no debe considerarse como una guía exhaustiva o definitiva sobre el tema.\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99f6488c",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel00.jpg?raw=true\" width=\"500\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "788bf420",
   "metadata": {},
   "source": [
    "## Arquitecturas de Memoria en Computadoras Paralelas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f1b1870",
   "metadata": {},
   "source": [
    "### Memoria Compartida"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8055d35",
   "metadata": {},
   "source": [
    "#### Características Generales"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04507da4",
   "metadata": {},
   "source": [
    "- Las computadoras paralelas con memoria compartida varían ampliamente, pero generalmente tienen en común la capacidad de todos los procesadores para acceder a toda la memoria como un espacio de direcciones global.  \n",
    "\n",
    "- Varios procesadores pueden operar de manera independiente pero comparten los mismos recursos de memoria.  \n",
    "\n",
    "- Los cambios en una ubicación de memoria realizados por un procesador son visibles para todos los demás procesadores.  \n",
    "- Históricamente, las máquinas de memoria compartida han sido clasificadas como UMA y NUMA, basándose en los tiempos de acceso a la memoria."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76699d43",
   "metadata": {},
   "source": [
    "#### Acceso Uniforme a la Memoria (Uniform Memory Access , UMA)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5cd46707",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel22.gif?raw=true\" width=\"300\" />\n",
    "</p>  \n",
    "\n",
    "- Hoy en día, comúnmente representado por máquinas Multiprocesador Simétrico (SMP)  \n",
    "- Procesadores idénticos  \n",
    "- Acceso igual y tiempos de acceso a la memoria  \n",
    "- A veces llamado CC-UMA - UMA Coherente en Caché. Coherente en caché significa que si un procesador actualiza una ubicación en la memoria compartida, todos los demás procesadores conocen la actualización. La coherencia de caché se logra a nivel de hardware.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e9d77db",
   "metadata": {},
   "source": [
    "#### Acceso No Uniforme a la Memoria (Non-Uniform Memory Access, NUMA)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c04c608d",
   "metadata": {},
   "source": [
    "- A menudo se realiza mediante la conexión física de dos o más SMP (Multiprocesadores Simétricos).\n",
    "- Un SMP puede acceder directamente a la memoria de otro SMP.\n",
    "- No todos los procesadores tienen el mismo tiempo de acceso a todas las memorias.\n",
    "- El acceso a la memoria a través del enlace es más lento.\n",
    "- Si se mantiene la coherencia de caché, entonces también puede llamarse CC-NUMA - NUMA Coherente en Caché.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel23.gif?raw=true\" width=\"350\" />\n",
    "</p>  \n",
    "\n",
    "**Ventajas**\n",
    "- El espacio de direcciones global proporciona una perspectiva de programación amigable para el usuario hacia la memoria.\n",
    "- El intercambio de datos entre tareas es rápido y uniforme debido a la proximidad de la memoria a las CPU.\n",
    "\n",
    "**Desventajas**\n",
    "- La principal desventaja es la falta de escalabilidad entre la memoria y las CPU. Agregar más CPU puede aumentar geométricamente el tráfico en el camino compartido memoria-CPU y, para sistemas coherentes en caché, aumentar geométricamente el tráfico asociado con la gestión de caché/memoria.\n",
    "- Responsabilidad del programador por construcciones de sincronización que aseguren el acceso \"correcto\" de la memoria global."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7c7f7da",
   "metadata": {},
   "source": [
    "### Memoria Distribuida (Distributed Memory)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94a0987f",
   "metadata": {},
   "source": [
    "#### Características Generales"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f86a920c",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel24.gif?raw=true\" width=\"350\" />\n",
    "</p>  \n",
    "\n",
    "Al igual que los sistemas de memoria compartida, los sistemas de memoria distribuida varían ampliamente, pero comparten una característica común. Los sistemas de memoria distribuida requieren una red de comunicación para conectar la memoria entre procesadores.\n",
    "\n",
    "Los procesadores tienen su propia memoria local. Las direcciones de memoria en un procesador no se mapean a otro procesador, por lo que no existe un concepto de espacio de direcciones global en todos los procesadores.\n",
    "\n",
    "Debido a que cada procesador tiene su propia memoria local, opera de manera independiente. Los cambios que realiza en su memoria local no tienen efecto en la memoria de otros procesadores. Por lo tanto, el concepto de coherencia de caché no se aplica.\n",
    "\n",
    "Cuando un procesador necesita acceder a datos en otro procesador, generalmente es tarea del programador definir explícitamente cómo y cuándo se comunican los datos. La sincronización entre tareas también es responsabilidad del programador.\n",
    "\n",
    "La \"tela\" de red utilizada para la transferencia de datos varía ampliamente, aunque puede ser tan simple como Ethernet.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "704955fb",
   "metadata": {},
   "source": [
    "#### Ventajas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "124ec5dd",
   "metadata": {},
   "source": [
    "- La memoria es escalable con el número de procesadores. Aumente el número de procesadores y el tamaño de la memoria aumenta proporcionalmente.  \n",
    "- Cada procesador puede acceder rápidamente a su propia memoria sin interferencias y sin los costos generados al tratar de mantener la coherencia global de la caché.  \n",
    "- Efectividad en costos: puede usar procesadores y redes comerciales disponibles en el mercado."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1845ef10",
   "metadata": {},
   "source": [
    "#### Desventajas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "707304c6",
   "metadata": {},
   "source": [
    "- El programador es responsable de muchos detalles asociados con la comunicación de datos entre procesadores.  \n",
    "\n",
    "- Puede ser difícil mapear estructuras de datos existentes, basadas en memoria global, a esta organización de memoria.  \n",
    "\n",
    "- Tiempos de acceso a la memoria no uniformes: los datos que residen en un nodo remoto tardan más en accederse que los datos locales al nodo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c051a836",
   "metadata": {},
   "source": [
    "### Memoria Híbrida Distribuida-Compartida (Hybrid Distributed-Shared Memory)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7772d6c",
   "metadata": {},
   "source": [
    "#### Características Generales"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9330f5e",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel25.PNG?raw=true\" width=\"750\" />\n",
    "</p>  \n",
    "\n",
    "- Las computadoras más grandes y rápidas del mundo hoy en día emplean tanto arquitecturas de memoria compartida como distribuida.  \n",
    "\n",
    "- El componente de memoria compartida puede ser una máquina de memoria compartida y/o unidades de procesamiento gráfico (GPU).  \n",
    "\n",
    "- El componente de memoria distribuida es la interconexión de múltiples máquinas de memoria compartida/GPU, que solo conocen su propia memoria, no la memoria en otra máquina. Por lo tanto, se requieren comunicaciones de red para mover datos de una máquina a otra.  \n",
    "\n",
    "- Las tendencias actuales parecen indicar que este tipo de arquitectura de memoria continuará predominando y aumentando en el ámbito de la computación de alto rendimiento en el futuro previsible.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92165811",
   "metadata": {},
   "source": [
    "#### Ventajas y Desventajas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d2b53ea",
   "metadata": {},
   "source": [
    "Lo que es común tanto a las arquitecturas de memoria compartida como distribuida.\n",
    "\n",
    "- **Ventajas:**\n",
    "  - **Escalabilidad aumentada:** Un aspecto importante de la memoria híbrida es la capacidad de escalar más eficientemente al combinar los beneficios de ambas arquitecturas, permitiendo manejar eficazmente grandes volúmenes de datos y procesamiento intensivo.\n",
    "<p>&nbsp;</p>\n",
    "  \n",
    "- **Desventajas:**\n",
    "  - **Complejidad aumentada para el programador:** La necesidad de gestionar dos tipos diferentes de arquitecturas de memoria puede complicar significativamente el diseño y la implementación del software. Los programadores deben ser conscientes de dónde y cómo se almacenan los datos, además de manejar la comunicación entre diferentes unidades de memoria.\n",
    "\n",
    "Este enfoque híbrido ofrece un equilibrio entre el acceso rápido a memoria local en las máquinas individuales y la capacidad de trabajar en conjunto en tareas más grandes que requieren datos de múltiples fuentes, aprovechando así las fortalezas de ambos tipos de memoria para mejorar el rendimiento general y la eficiencia del sistema."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d22e6135",
   "metadata": {},
   "source": [
    "## Modelos de Programación Paralela"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df24cd38",
   "metadata": {},
   "source": [
    "### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d5c9dc4",
   "metadata": {},
   "source": [
    "Existen varios modelos de programación paralela de uso común:\n",
    "\n",
    "- Memoria Compartida (sin hilos, threads)\n",
    "- Hilos\n",
    "- Memoria Distribuida / Paso de Mensajes\n",
    "- Paralelismo de Datos\n",
    "- Híbrido\n",
    "- Programa Único Múltiples Datos (SPMD)\n",
    "- Múltiples Programas Múltiples Datos (MPMD)\n",
    "\n",
    "Los modelos de programación paralela existen como una abstracción por encima de las arquitecturas de hardware y memoria. Aunque puede no parecer evidente, estos modelos NO son específicos de un tipo particular de máquina o arquitectura de memoria. De hecho, cualquiera de estos modelos puede (teóricamente) implementarse en cualquier hardware subyacente. A continuación, se discuten dos ejemplos del pasado.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0e5433a",
   "metadata": {},
   "source": [
    "### Modelo de memoria compartida en una máquina de memoria distribuida"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7437bce",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel26.PNG?raw=true\" width=\"750\" />\n",
    "</p>  \n",
    "\n",
    "Enfoque *ALLCACHE de Kendall Square Research* (*KSR*). La memoria de la máquina estaba físicamente distribuida a través de máquinas en red, pero aparecía para el usuario como un espacio de direcciones de memoria compartida global. Genéricamente, este enfoque se conoce como \"memoria compartida virtual\"."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b57ab55a",
   "metadata": {},
   "source": [
    "### Modelo de memoria distribuida en una máquina de memoria compartida"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f1a91d3",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel27.PNG?raw=true\" width=\"750\" />\n",
    "</p>  \n",
    "\n",
    "[Interface de Paso de Mensajes](https://en.wikipedia.org/wiki/Message_Passing_Interface) (Message Passing Interface, MPI) en SGI Origin 2000. El SGI Origin 2000 empleaba el tipo de arquitectura de memoria compartida CC-NUMA, donde cada tarea tiene acceso directo al espacio de direcciones global distribuido en todas las máquinas. Sin embargo, la capacidad de enviar y recibir mensajes usando MPI, como se hace comúnmente en una red de máquinas de memoria distribuida, fue implementada y comúnmente utilizada.\n",
    "\n",
    "¿Qué modelo usar? Esto es a menudo una combinación de lo que está disponible y elección personal. No hay un modelo \"mejor\", aunque ciertamente hay implementaciones mejores de algunos modelos sobre otros.\n",
    "\n",
    "Las siguientes secciones describen cada uno de los modelos mencionados anteriormente y también discuten algunas de sus implementaciones reales."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f07372f2",
   "metadata": {},
   "source": [
    "### Modelo de Memoria Compartida (sin hilos)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "579a3c67",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel28.gif?raw=true\" width=\"200\" />\n",
    "</p>  \n",
    "\n",
    "En este modelo de programación, los procesos o tareas comparten un espacio de direcciones común, al cual leen y escriben de manera asincrónica.  \n",
    "\n",
    "Se utilizan varios mecanismos como cerrojos y semáforos para controlar el acceso a la memoria compartida, resolver contiendas y prevenir condiciones de carrera y bloqueos mutuos (deadlocks).\n",
    "Este es quizás el modelo de programación paralela más simple.\n",
    "\n",
    "Una ventaja de este modelo desde el punto de vista del programador es que la noción de \"propiedad\" de datos no existe, por lo que no es necesario especificar explícitamente la comunicación de datos entre tareas. Todos los procesos ven y tienen igual acceso a la memoria compartida. El desarrollo del programa a menudo puede ser simplificado.\n",
    "\n",
    "Una desventaja importante en términos de rendimiento es que se vuelve más difícil entender y gestionar la localidad de los datos:\n",
    "- Mantener los datos locales al proceso que trabaja en ellos conserva los accesos a la memoria, las actualizaciones de caché y el tráfico del bus que ocurre cuando múltiples procesos usan los mismos datos.\n",
    "- Desafortunadamente, controlar la localidad de los datos es difícil de entender y puede estar más allá del control del usuario promedio.\n",
    "\n",
    "***Implementaciones***\n",
    "\n",
    "- En máquinas de memoria compartida independientes, los sistemas operativos nativos, compiladores y/o hardware proporcionan soporte para la programación de memoria compartida. Por ejemplo, el estándar POSIX proporciona una API para usar memoria compartida, y UNIX ofrece segmentos de memoria compartida (shmget, shmat, shmctl, etc.).  \n",
    "\n",
    "- En máquinas de memoria distribuida, la memoria está físicamente distribuida a través de una red de máquinas, pero se hace global a través de hardware y software especializado. Hay disponibles varias implementaciones de [SHMEM](http://en.wikipedia.org/wiki/SHMEM)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b03980d",
   "metadata": {},
   "source": [
    "### El modelo de hilos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1593ba4d",
   "metadata": {},
   "source": [
    "#### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c38e0419",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel29.PNG?raw=true\" width=\"200\" />\n",
    "</p>  \n",
    "\n",
    "Este modelo de programación es un tipo de programación de memoria compartida.\n",
    "\n",
    "En el modelo de hilos de programación paralela, un único proceso \"pesado\" puede tener múltiples rutas de ejecución \"ligeras\" y concurrentes.\n",
    "\n",
    "Por ejemplo:\n",
    "- El programa principal `a.out` es programado para ejecutarse por el sistema operativo nativo. `a.out` carga y adquiere todos los recursos necesarios del sistema y del usuario para ejecutarse. Este es el proceso \"pesado\".  \n",
    "\n",
    "- `a.out` realiza algún trabajo serial, y luego crea una serie de tareas (hilos) que pueden ser programadas y ejecutadas de forma concurrente por el sistema operativo.  \n",
    "\n",
    "- Cada hilo tiene datos locales, pero también comparte todos los recursos de `a.out`. Esto ahorra la sobrecarga asociada con replicar los recursos de un programa para cada hilo (\"ligero\"). Cada hilo también se beneficia de una vista global de la memoria porque comparte el espacio de memoria de `a.out`.  \n",
    "\n",
    "- El trabajo de un hilo puede describirse mejor como una subrutina dentro del programa principal. Cualquier hilo puede ejecutar cualquier subrutina al mismo tiempo que otros hilos.  \n",
    "\n",
    "- Los hilos se comunican entre sí a través de la memoria global (actualizando ubicaciones de direcciones). Esto requiere constructos de sincronización para asegurar que más de un hilo no esté actualizando la misma dirección global al mismo tiempo.  \n",
    "\n",
    "- Los hilos pueden aparecer y desaparecer, pero `a.out` permanece presente para proporcionar los recursos compartidos necesarios hasta que la aplicación se haya completado."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d528151e",
   "metadata": {},
   "source": [
    "#### Implementaciones"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6495da10",
   "metadata": {},
   "source": [
    "Desde una perspectiva de programación, las implementaciones de hilos comúnmente comprenden:  \n",
    "\n",
    "- Una biblioteca de subrutinas que se llaman desde dentro del código fuente paralelo.  \n",
    "\n",
    "- Un conjunto de directivas de compilador incrustadas en el código fuente serial o paralelo.  \n",
    "\n",
    "En ambos casos, el programador es responsable de determinar el paralelismo (aunque los compiladores a veces pueden ayudar).\n",
    "\n",
    "- Las implementaciones con hilos no son nuevas en la computación. Históricamente, los vendedores de hardware han implementado sus propias versiones propietarias de hilos. Estas implementaciones diferían sustancialmente entre sí, lo que dificultaba a los programadores desarrollar aplicaciones con hilos portátiles.  \n",
    "\n",
    "- Los esfuerzos de estandarización no relacionados han resultado en dos implementaciones muy diferentes de hilos: [Hilos POSIX](https://en.wikipedia.org/wiki/Pthreads) y [OpenMP](https://en.wikipedia.org/wiki/OpenMP)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a12ff752",
   "metadata": {},
   "source": [
    "#### [Hilos POSIX (Pthreads):](https://hpc-tutorials.llnl.gov/posix/)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8e16a07",
   "metadata": {},
   "source": [
    "Esta es una opción poderosa para los programadores que necesitan control completo sobre la ejecución del paralelismo. Los Pthreads permiten una gran flexibilidad y control en la gestión de hilos, sincronización, y el manejo de recursos compartidos. Son ampliamente utilizados en entornos donde se necesita un ajuste fino del rendimiento y la gestión de la concurrencia.  \n",
    "\n",
    "- Especificados por el estándar IEEE POSIX 1003.1c (1995). Solo para el lenguaje C.\n",
    "- Parte de los sistemas operativos Unix/Linux\n",
    "- Basado en bibliotecas\n",
    "- Comúnmente referido como Pthreads.\n",
    "- Paralelismo muy explícito; requiere una atención significativa al detalle por parte del programador."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5c69733",
   "metadata": {},
   "source": [
    "#### [OpenMP:](https://www.openmp.org/)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3a45c5f",
   "metadata": {},
   "source": [
    "Este modelo es altamente valorado por su simplicidad y eficacia, especialmente para aquellos que están comenzando con la programación paralela o aquellos que necesitan implementar paralelismo en programas existentes con el mínimo esfuerzo. OpenMP utiliza directivas de compilador para automatizar la creación de hilos, la distribución de tareas y la sincronización, lo que facilita enormemente la tarea del programador. Además, debido a que OpenMP es soportado por muchos compiladores, garantiza un buen nivel de portabilidad entre diferentes plataformas. \n",
    "\n",
    "- Estándar de la industria, definido y respaldado conjuntamente por un grupo de importantes proveedores de hardware y software de computadoras, organizaciones e individuos.\n",
    "- Basado en directivas de compilador\n",
    "- Portátil / multiplataforma, incluyendo plataformas Unix y Windows\n",
    "- Disponible en implementaciones de C/C++ y Fortran\n",
    "- Puede ser muy fácil y simple de usar - proporciona un \"paralelismo incremental\". Puede comenzar con código serial."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84c0064a",
   "metadata": {},
   "source": [
    "Para más información y profundizar en los detalles de cada modelo de programación con hilos, aquí tienes recursos útiles:\n",
    "\n",
    "1. **Tutorial de Hilos POSIX**: Puedes encontrar un tutorial completo sobre Hilos POSIX en el sitio web del Laboratorio Nacional Lawrence Livermore (LLNL) accediendo al documento directamente a través de [este enlace a hpc.llnl.gov](https://hpc.llnl.gov/sites/default/files/2019.08.21.TAU_.pdf). Este tutorial proporcionará una guía detallada sobre cómo implementar y manejar hilos POSIX en tus proyectos de programación.\n",
    "\n",
    "2. **Tutorial de OpenMP**: Para aprender más sobre OpenMP, el Laboratorio Nacional Lawrence Livermore ofrece un tutorial completo que puedes explorar. Visita [la página de tutoriales de OpenMP del LLNL](https://hpc-tutorials.llnl.gov/openmp/) para obtener información práctica y ejemplos de cómo utilizar OpenMP en aplicaciones paralelas, tanto en C/C++ como en Fortran.\n",
    "\n",
    "Estos recursos son excelentes puntos de partida para desarrolladores interesados en la programación paralela, proporcionando tanto fundamentos teóricos como ejemplos prácticos que ayudan a entender mejor cómo implementar estos modelos en diversos entornos y plataformas."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93d31ed1",
   "metadata": {},
   "source": [
    "#### Modelo de Memoria Distribuida / Paso de Mensajes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "632964f0",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel31.gif?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "El modelo de [*Memoria Distribuida / Paso de Mensajes*](https://www.open-mpi.org/) (Distributed Memory / Message Passing Model) demuestra las siguientes características:\n",
    "- Un conjunto de tareas que utilizan su propia memoria local durante el cálculo. Múltiples tareas pueden residir en la misma máquina física y/o en un número arbitrario de máquinas.\n",
    "- Las tareas intercambian datos a través de comunicaciones enviando (*sending*) y recibiendo (*receiving*) mensajes.\n",
    "- La transferencia de datos generalmente requiere operaciones cooperativas que deben ser realizadas por cada proceso. Por ejemplo, una operación de envío debe tener una operación de recepción correspondiente.\n",
    "\n",
    "***Implementaciones:***\n",
    "\n",
    "- Desde una perspectiva de programación, las implementaciones de paso de mensajes generalmente comprenden una biblioteca de subrutinas. Las llamadas a estas subrutinas están incrustadas en el código fuente. El programador es responsable de determinar todo el paralelismo.\n",
    "- Históricamente, una variedad de bibliotecas de paso de mensajes han estado disponibles desde la década de 1980. Estas implementaciones diferían sustancialmente entre sí, lo que dificultaba a los programadores desarrollar aplicaciones portátiles.\n",
    "- En 1992, se formó el Foro MPI con el objetivo principal de establecer una interfaz estándar para las implementaciones de paso de mensajes.\n",
    "- La Parte 1 de la Interfaz de Paso de Mensajes (MPI) fue lanzada en 1994. La Parte 2 (MPI-2) se lanzó en 1996 y MPI-3 en 2012. Todas las especificaciones de MPI están disponibles en la web en http://www.mpi-forum.org/docs/.\n",
    "- MPI es el estándar industrial \"de facto\" para el paso de mensajes, reemplazando virtualmente todas las demás implementaciones de paso de mensajes utilizadas para trabajo de producción. Existen implementaciones de MPI para prácticamente todas las plataformas de computación paralela populares. No todas las implementaciones incluyen todo en MPI-1, MPI-2 o MPI-3.\n",
    "\n",
    "\n",
    "***Más Información***\n",
    "- [Tutorial de MPI](https://hpc-tutorials.llnl.gov/mpi/) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edff8ba3",
   "metadata": {},
   "source": [
    "### Modelo de Paralelismo de Datos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "665a0699",
   "metadata": {},
   "source": [
    "#### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82c9a2dd",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel32.gif?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "También puede ser referido como el modelo de Espacio de Direcciones Globales Particionado (PGAS, por sus siglas en inglés).\n",
    "\n",
    "El modelo de paralelismo de datos demuestra las siguientes características:\n",
    "- El espacio de direcciones se trata de manera global.\n",
    "- La mayor parte del trabajo paralelo se centra en realizar operaciones sobre un conjunto de datos. El conjunto de datos suele organizarse en una estructura común, como un arreglo o un cubo.\n",
    "- Un conjunto de tareas trabaja colectivamente en la misma estructura de datos; sin embargo, cada tarea trabaja en una partición diferente de la misma estructura de datos.\n",
    "- Las tareas realizan la misma operación en su partición de trabajo, por ejemplo, \"sumar 4 a cada elemento del arreglo\".\n",
    "- En arquitecturas de memoria compartida, todas las tareas pueden tener acceso a la estructura de datos a través de la memoria global.\n",
    "- En arquitecturas de memoria distribuida, la estructura de datos global puede dividirse lógica y/o físicamente entre las tareas.\n",
    "\n",
    "Implementaciones:\n",
    "\n",
    "Actualmente, hay varias implementaciones de programación paralela en diversas etapas de desarrollo, basadas en el modelo de *Paralelismo de Datos / PGAS*.\n",
    "- [***Coarray Fortran***](https://en.wikipedia.org/wiki/Coarray_Fortran): un pequeño conjunto de extensiones a [Fortran 95](https://en.wikipedia.org/wiki/Fortran_95_language_features) para programación paralela SPMD. Dependiente del compilador. \n",
    "- ***[Unified Parallel C (UPC)](https://upc.lbl.gov/):*** una extensión del lenguaje de programación C para programación paralela SPMD. Dependiente del compilador. Más información: \n",
    "- [***Global Arrays***](https://en.wikipedia.org/wiki/Global_Arrays): proporciona un entorno de programación al estilo de memoria compartida en el contexto de estructuras de datos de arreglo distribuidas. Biblioteca de dominio público con enlaces para C y Fortran77. \n",
    "- ***[X10](http://x10-lang.org/):*** un lenguaje de programación paralela basado en PGAS que está siendo desarrollado por IBM en el Centro de Investigación Thomas J. Watson. Más información: \n",
    "- ***[Chapel](http://chapel.cray.com/):*** un proyecto de lenguaje de programación paralela de código abierto liderado por Cray. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19eb4096",
   "metadata": {},
   "source": [
    "#### Modelo Híbrido"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52199753",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel33.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "Un modelo híbrido combina más de uno de los modelos de programación descritos anteriormente.\n",
    "\n",
    "Actualmente, un ejemplo común de un modelo híbrido es la combinación del modelo de paso de mensajes (MPI) con el modelo de hilos (OpenMP).\n",
    "- Los hilos realizan cálculos intensivos utilizando datos locales, en el nodo.\n",
    "- Las comunicaciones entre procesos en diferentes nodos se realizan a través de la red usando MPI.\n",
    "Este modelo híbrido se adapta bien al entorno de hardware más popular (actualmente) de máquinas multinúcleo/clúster.\n",
    "\n",
    "Otro ejemplo similar y cada vez más popular de un modelo híbrido es el uso de MPI con programación CPU-GPU (unidad de procesamiento gráfico).\n",
    "- Las tareas MPI se ejecutan en CPUs utilizando memoria local y comunicándose entre sí a través de una red.\n",
    "- Los cálculos intensivos son delegados a las GPUs en el nodo.\n",
    "- El intercambio de datos entre la memoria local del nodo y las GPUs utiliza CUDA (o algo equivalente).\n",
    "\n",
    "Otros modelos híbridos comunes incluyen:\n",
    "- MPI con Pthreads\n",
    "- MPI con aceleradores no-GPU\n",
    "\n",
    "***Ventajas del Modelo Híbrido***\n",
    "1. **Eficiencia en la utilización de recursos:** Al combinar MPI y OpenMP, por ejemplo, se puede lograr un balance entre la computación intensiva local (optimizada por los hilos) y la comunicación eficiente entre nodos (gestionada por MPI).\n",
    "2. **Escalabilidad:** El modelo híbrido permite escalar aplicaciones tanto verticalmente (dentro del mismo nodo, usando más núcleos o GPU) como horizontalmente (a través de múltiples nodos).\n",
    "3. **Flexibilidad:** Permite a los desarrolladores aprovechar lo mejor de ambos mundos — la eficiencia de memoria y la computación local de los hilos, junto con la capacidad de comunicarse eficientemente a través de nodos distantes.\n",
    "\n",
    "***Desafíos del Modelo Híbrido***\n",
    "1. **Complejidad de la programación:** Manejar dos modelos de programación diferentes puede incrementar la complejidad del desarrollo y la depuración de la aplicación.\n",
    "2. **Optimización:** Requiere un conocimiento profundo de ambas arquitecturas para optimizar el rendimiento y aprovechar al máximo ambos tipos de recursos (CPU y GPU, por ejemplo).\n",
    "3. **Gestión de recursos:** Coordinar la memoria y los cálculos entre diferentes arquitecturas (como CPU y GPU) requiere una gestión cuidadosa para evitar cuellos de botella.\n",
    "\n",
    "El empleo de modelos híbridos está en auge debido a su capacidad para adaptarse a las complejas demandas de las aplicaciones modernas que necesitan tanto un alto rendimiento de cómputo como una gran capacidad de procesamiento de datos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02d6df30",
   "metadata": {},
   "source": [
    "#### SPMD (Single Program Multiple Data) y MPMD (Multiple Program Multiple Data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b824af9",
   "metadata": {},
   "source": [
    "Ambos [SPMD](https://en.wikipedia.org/wiki/Single_program,_multiple_data) y [MPMD](https://en.wikipedia.org/wiki/Multiple_instruction,_multiple_data) son modelos de programación paralela de alto nivel que pueden construirse sobre cualquier combinación de los modelos de programación paralela previamente mencionados."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2ca068b",
   "metadata": {},
   "source": [
    "##### SPMD (Single Program Multiple Data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56bf273e",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel34.gif?raw=true\" width=\"350\" />\n",
    "</p>\n",
    "\n",
    "- **PROGRAMA ÚNICO:** Todas las tareas ejecutan su copia del mismo programa simultáneamente. Este programa puede ser de hilos, paso de mensajes, paralelismo de datos o híbrido.\n",
    "- **DATOS MÚLTIPLES:** Todas las tareas pueden utilizar diferentes datos.\n",
    "- Los programas SPMD generalmente tienen la lógica necesaria programada para permitir que diferentes tareas ramifiquen o ejecuten condicionalmente solo aquellas partes del programa que están diseñadas para ejecutar. Es decir, las tareas no necesariamente tienen que ejecutar el programa completo, tal vez solo una parte de él.\n",
    "\n",
    "El modelo SPMD, utilizando paso de mensajes o programación híbrida, es probablemente el modelo de programación paralela más comúnmente utilizado para clústeres multinodo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "439dd7c3",
   "metadata": {},
   "source": [
    "##### MPMD (Multiple Program Multiple Data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "100042f2",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel35.gif?raw=true\" width=\"350\" />\n",
    "</p>\n",
    "\n",
    "- **PROGRAMAS MÚLTIPLES:** Las tareas pueden ejecutar diferentes programas simultáneamente. Los programas pueden ser de hilos, paso de mensajes, paralelismo de datos o híbrido.\n",
    "- **DATOS MÚLTIPLES:** Todas las tareas pueden utilizar diferentes datos.\n",
    "\n",
    "Las aplicaciones MPMD no son tan comunes como las aplicaciones SPMD, pero pueden ser más adecuadas para ciertos tipos de problemas, particularmente aquellos que se prestan mejor a la descomposición funcional que a la descomposición por dominios (esto se discutirá más adelante bajo el tema de Particionamiento).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0934d956",
   "metadata": {},
   "source": [
    "##### Comparación y Uso"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aae764ab",
   "metadata": {},
   "source": [
    "**Ventajas de SPMD:**\n",
    "- **Eficiencia en el Manejo de Recursos:** Al ejecutar el mismo programa, la optimización y el manejo del código pueden ser más directos y eficientes.\n",
    "- **Simplificación del Desarrollo:** Menos variedad en los programas reduce la complejidad durante el desarrollo y la depuración.\n",
    "\n",
    "**Ventajas de MPMD:**\n",
    "- **Flexibilidad en la Ejecución:** Permite que diferentes nodos o grupos de nodos ejecuten diferentes programas según sea necesario, lo cual es útil para problemas heterogéneos.\n",
    "- **Adaptabilidad a Problemas Complejos:** Ideal para aplicaciones que necesitan diferentes funcionalidades en diferentes partes del proceso de cálculo.\n",
    "\n",
    "Ambos modelos ofrecen enfoques poderosos para la programación paralela y se eligen según los requisitos específicos y la naturaleza de los problemas a resolver."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dde33852",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "588.865px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}