HPC01_ConceptosAlgoritmosParalelos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f1b06738",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Computación de Alto Desempeño</h1>\n",
    "<h1 align=\"center\">Conceptos de Computación Paralela</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/HPC01_ConceptosAlgoritmosParalelos.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": "8cfe65cd",
   "metadata": {},
   "source": [
    "## Cómputo paralelo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01d927aa",
   "metadata": {},
   "source": [
    "### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a4177d2",
   "metadata": {},
   "source": [
    "En la era moderna, el modelo convencional de cómputo serial, donde un algoritmo descompone un problema en instrucciones ejecutadas secuencialmente, ha demostrado ser ineficiente para manejar tareas complejas y voluminosas. Esto se debe a la limitación de ejecutar una sola instrucción a la vez, lo que resulta en una subutilización significativa de los recursos de hardware.\n",
    "\n",
    "El cómputo paralelo surge como una solución eficaz a este problema. Utiliza múltiples elementos de procesamiento de manera simultánea para resolver un problema, descomponiéndolo en partes que pueden ser procesadas al mismo tiempo. Esto no solo acelera el tiempo de ejecución, sino que también maximiza la utilización del hardware disponible.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel01.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "Imagina que tienes un gran problema que resolver y estás solo. Necesitas calcular la raíz cuadrada de ocho números diferentes. ¿A qué te dedicas? Bueno, no tienes muchas opciones. Comienzas con el primer número y calculas el resultado. Luego sigues con los demás.\n",
    "\n",
    "¿Qué pasa si tienes tres amigos buenos en matemáticas dispuestos a ayudarte? Cada uno de ellos calculará la raíz cuadrada de dos números y tu trabajo será más fácil porque la carga de trabajo se distribuye equitativamente entre tus amigos. Esto significa que su problema se resolverá más rápido.\n",
    "\n",
    "Bien, ¿está todo claro? En estos ejemplos, cada amigo representa un núcleo de la CPU. En el primer ejemplo, usted resuelve toda la tarea de forma secuencial. Esto se llama computación en serie . En el segundo ejemplo, como estás trabajando con cuatro núcleos en total, estás usando computación paralela . La computación paralela implica el uso de procesos paralelos o procesos que se dividen entre múltiples núcleos en un procesador."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efcb4a94",
   "metadata": {},
   "source": [
    "### Cómputo Serial"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc2a400e",
   "metadata": {},
   "source": [
    "Tradicionalmente, el software ha sido escrito para el cómputo serial:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel02.gif?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- Un problema se descompone en una serie discreta de instrucciones.\n",
    "- Las instrucciones se ejecutan secuencialmente, una tras otra.\n",
    "- Se ejecuta en un solo procesador.\n",
    "- Solo una instrucción puede ejecutarse en cualquier momento dado.\n",
    "\n",
    "por ejemplo: Ejemplo de cómputo serial en el procesamiento de nóminas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel03.gif?raw=true\" width=\"500\" />\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e13b6bea",
   "metadata": {},
   "source": [
    "### Cómputo Paralelo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2dcedba",
   "metadata": {},
   "source": [
    "En el sentido más simple, el cómputo paralelo es el uso simultáneo de múltiples recursos computacionales para resolver un problema computacional:\n",
    "\n",
    "- Un problema se divide en partes discretas que pueden resolverse de manera concurrente.\n",
    "- Cada parte se desglosa aún más en una serie de instrucciones.\n",
    "- Las instrucciones de cada parte se ejecutan simultáneamente en diferentes procesadores.\n",
    "- Se emplea un mecanismo general de control y coordinación.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel04.gif?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "Por ejemplo: Ejemplo de cómputo paralelo en el procesamiento de nóminas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel05.gif?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "El problema computacional debería poder:\n",
    "- Descomponerse en piezas discretas de trabajo que puedan resolverse simultáneamente;\n",
    "- Ejecutar múltiples instrucciones del programa en cualquier momento;\n",
    "- Resolverse en menos tiempo con múltiples recursos computacionales que con un solo recurso computacional.\n",
    "\n",
    "Los recursos computacionales son típicamente:\n",
    "- Una única computadora con múltiples procesadores/núcleos (su computador personal).\n",
    "- Un número arbitrario de dichas computadoras conectadas por una red (computadores de una sala de cómputo, de una oficina, o un esquema tipo [Beowulf](https://en.wikipedia.org/wiki/Beowulf_cluster)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdfd8563",
   "metadata": {},
   "source": [
    "### Computadoras Paralelas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e521b367",
   "metadata": {},
   "source": [
    "Prácticamente todas las computadoras independientes actuales son paralelas desde una perspectiva de hardware:\n",
    "- Múltiples unidades funcionales (caché L1, caché L2, ramificación, precarga, decodificación, procesamiento de punto flotante, procesamiento gráfico (GPU), entero, etc.)\n",
    "- Múltiples unidades de ejecución/núcleos\n",
    "- Múltiples hilos de hardware\n",
    "Las redes conectan múltiples computadoras independientes (nodos) para formar clústeres de computadoras paralelas más grandes.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel07.gif?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "Por ejemplo, el gráfico a continuación muestra un clúster típico de computadoras paralelas:\n",
    "- Cada nodo de cómputo es en sí mismo una computadora paralela de múltiples procesadores\n",
    "- Múltiples nodos de cómputo están interconectados con una red Infiniband\n",
    "- Nodos de propósito especial, también de múltiples procesadores, se utilizan para otros fines\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel08.gif?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "La mayoría de las grandes computadoras paralelas del mundo (supercomputadoras) son clústeres de hardware producidos por un puñado de proveedores (en su mayoría) bien conocidos. [Top500.org](https://www.top500.org/statistics/list/)\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel09.PNG?raw=true\" width=\"250\" />\n",
    "</p>\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel10.PNG?raw=true\" width=\"250\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8284cfdf",
   "metadata": {},
   "source": [
    "## Conceptos y Terminología"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98899dae",
   "metadata": {},
   "source": [
    "### Arquitectura de Computadoras von Neumann"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f74f4958",
   "metadata": {},
   "source": [
    "- Nombrada en honor al matemático húngaro [John von Neumann](https://en.wikipedia.org/wiki/John_von_Neumann), quien fue el primero en formular los requisitos generales para una computadora electrónica en sus trabajos de 1945.\n",
    "- También conocida como \"computadora de programa almacenado\" - tanto las instrucciones del programa como los datos se mantienen en memoria electrónica. Difiere de las computadoras anteriores que se programaban mediante \"cableado fijo\".\n",
    "- Desde entonces, prácticamente todas las computadoras han seguido este diseño básico:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel11.gif?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- Compuesta de cuatro componentes principales:\n",
    "    - Memoria\n",
    "    - Unidad de Control\n",
    "    - Unidad de Lógica Aritmética\n",
    "    - Entrada/Salida\n",
    "- Se utiliza memoria de acceso aleatorio de lectura/escritura para almacenar tanto las instrucciones del programa como los datos.\n",
    "- Las instrucciones del programa son datos codificados que le indican a la computadora qué hacer.\n",
    "- Los datos son simplemente información que será utilizada por el programa.\n",
    "- La unidad de control recupera instrucciones/datos de la memoria, decodifica las instrucciones y luego coordina secuencialmente las operaciones para realizar la tarea programada.\n",
    "- La Unidad Aritmética realiza operaciones aritméticas básicas.\n",
    "- Entrada/Salida es la interfaz con el operador humano.\n",
    "Las computadoras paralelas aún siguen este diseño básico, solo que multiplicado en unidades. La arquitectura básica y fundamental permanece igual."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fc9ee77",
   "metadata": {},
   "source": [
    "### Taxonomía Clásica de Flynn"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "845a9f1c",
   "metadata": {},
   "source": [
    "Existen numerosas formas de clasificar las computadoras paralelas. Ejemplos de estas están disponibles en las referencias.\n",
    "Una de las clasificaciones más utilizadas, vigente desde 1966, es la llamada [Taxonomía de Flynn](https://en.wikipedia.org/wiki/Flynn%27s_taxonomy).\n",
    "La taxonomía de Flynn distingue las arquitecturas de computadoras multiprocesador según cómo se pueden clasificar a lo largo de las dos dimensiones independientes de Flujo de Instrucciones y Flujo de Datos. Cada una de estas dimensiones puede tener solo uno de dos estados posibles: Único o Múltiple.\n",
    "La matriz a continuación define las 4 posibles clasificaciones según [Flynn](https://en.wikipedia.org/wiki/Michael_J._Flynn):\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel12.gif?raw=true\" width=\"250\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11fe109b",
   "metadata": {},
   "source": [
    "#### Instrucción Única, Dato Único (SISD)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6816793",
   "metadata": {},
   "source": [
    "- Una computadora serial (no paralela)\n",
    "- Instrucción Única: Solo un flujo de instrucciones es procesado por la CPU durante cada ciclo de reloj.\n",
    "- Dato Único: Solo un flujo de datos se utiliza como entrada durante cada ciclo de reloj.\n",
    "- Ejecución determinista.\n",
    "- Este es el tipo más antiguo de computadora.\n",
    "- Ejemplos: mainframes de generaciones anteriores, minicomputadoras, estaciones de trabajo y PCs con un único procesador/núcleo.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel13.gif?raw=true\" width=\"250\" />\n",
    "</p>\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel14.gif?raw=true\" width=\"100\" />\n",
    "</p>\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel15.PNG?raw=true\" width=\"750\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c24ff196",
   "metadata": {},
   "source": [
    "#### Instrucción Única, Datos Múltiples (Single Instruction, Multiple Data, SIMD)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bfacb57",
   "metadata": {},
   "source": [
    "- Un tipo de computadora paralela\n",
    "- ***Instrucción Única:*** Todas las unidades de procesamiento ejecutan la misma instrucción en cualquier ciclo de reloj dado.  \n",
    "- ***Datos Múltiples:*** Cada unidad de procesamiento puede operar sobre un elemento de datos diferente.  \n",
    "- Mejor adecuado para problemas especializados caracterizados por un alto grado de regularidad, como el procesamiento de gráficos/imagen.  \n",
    "- Ejecución sincrónica (en paso bloqueado) y determinista.  \n",
    "- ***Dos variedades:*** Arreglos de Procesadores y Tubos de Vector.  \n",
    "\n",
    "***Ejemplos:***\n",
    "- ***Arreglos de Procesadores:*** Thinking Machines CM-2, MasPar MP-1 & MP-2, ILLIAC IV.\n",
    "- ***Canales de Vectores:*** IBM 9000, Cray X-MP, Y-MP & C90, Fujitsu VP, NEC SX-2, Hitachi S820, ETA10.\n",
    "La mayoría de las computadoras modernas, especialmente aquellas con unidades de procesamiento gráfico (GPUs), emplean instrucciones y unidades de ejecución SIMD.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel16.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel17.PNG?raw=true\" width=\"750\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25694e28",
   "metadata": {},
   "source": [
    "#### Instrucción Múltiple, Dato Único (Multiple Instruction, Single Data, MISD)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8915bfcd",
   "metadata": {},
   "source": [
    "- Un tipo de computadora paralela\n",
    "- ***Instrucción Múltiple:*** Cada unidad de procesamiento opera sobre los datos de manera independiente mediante flujos de instrucciones separados.\n",
    "- ***Dato Único:*** Un único flujo de datos se introduce en múltiples unidades de procesamiento.\n",
    "- Pocos (si acaso alguno) ejemplos reales de esta clase de computadora paralela han existido.\n",
    "- Algunos usos concebibles podrían ser:\n",
    "  - múltiples filtros de frecuencia operando sobre un único flujo de señal\n",
    "  - múltiples algoritmos de criptografía intentando descifrar un único mensaje codificado.\n",
    "  \n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel18.PNG?raw=true\" width=\"750\" />\n",
    "</p>  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "091703bf",
   "metadata": {},
   "source": [
    "#### Instrucción Múltiple, Datos Múltiples (Multiple Instruction, Multiple Data, MIMD)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d3d6a3f",
   "metadata": {},
   "source": [
    "- Un tipo de computadora paralela\n",
    "- Instrucción Múltiple: Cada procesador puede estar ejecutando un flujo de instrucciones diferente.\n",
    "- Datos Múltiples: Cada procesador puede estar trabajando con un flujo de datos diferente.\n",
    "- La ejecución puede ser sincrónica o asincrónica, determinista o no determinista.\n",
    "- Actualmente, es el tipo más común de computadora paralela; la mayoría de las supercomputadoras modernas entran en esta categoría.\n",
    "\n",
    "- ***Ejemplos:*** la mayoría de las supercomputadoras actuales, clústeres de computadoras paralelas en red y \"grids\", computadoras SMP (Symmetric Multi-Processing) de múltiples procesadores, PCs de múltiples núcleos.\n",
    "\n",
    "***Nota:*** Muchas arquitecturas MIMD también incluyen subcomponentes de ejecución SIMD.\n",
    "\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel19.PNG?raw=true\" width=\"750\" />\n",
    "</p>  \n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel20.PNG?raw=true\" width=\"750\" />\n",
    "</p>  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1be90c4",
   "metadata": {},
   "source": [
    "### Terminología General de Cómputo Paralelo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7256ffc5",
   "metadata": {},
   "source": [
    "Como todo lo demás, el cómputo paralelo tiene su propio argot. A continuación, se enumeran algunos de los términos más comúnmente asociados con el cómputo paralelo. La mayoría de estos serán discutidos con más detalle más adelante.\n",
    "\n",
    "- **CPU:** Las CPU contemporáneas consisten en uno o más núcleos: una unidad de ejecución distinta con su propio flujo de instrucciones. Los núcleos dentro de una CPU pueden estar organizados en uno o más sockets, cada uno con su propia memoria distinta. Cuando una CPU consta de dos o más sockets, usualmente la infraestructura de hardware soporta el compartir memoria a través de los sockets.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Nodo (Node):** Un \"computador en una caja\" autónomo. Usualmente compuesto por múltiples CPU/procesadores/núcleos, memoria, interfaces de red, etc. Los nodos están interconectados para formar una supercomputadora.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Tarea (Task):** Una sección de trabajo computacional lógicamente discreta. Una tarea es típicamente un programa o un conjunto de instrucciones tipo programa que es ejecutado por un procesador. Un programa paralelo consta de múltiples tareas corriendo en múltiples procesadores.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Tubería de Procesamiento (Pipelining):** División de una tarea en pasos realizados por diferentes unidades procesadoras, con entradas fluyendo a través, muy parecido a una línea de montaje; un tipo de cómputo paralelo.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Memoria Compartida (Shared Memory):** Describe una arquitectura de computadora donde todos los procesadores tienen acceso directo a una memoria física común. En un sentido de programación, describe un modelo donde las tareas paralelas tienen la misma \"imagen\" de memoria y pueden direccionar y acceder directamente a las mismas ubicaciones de memoria lógica, independientemente de donde la memoria física exista realmente.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Procesador Simétrico Múltiple (Symmetric Multi-Processor, SMP):** Arquitectura de hardware de memoria compartida donde múltiples procesadores comparten un único espacio de direcciones y tienen igual acceso a todos los recursos: memoria, disco, etc.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Memoria Distribuida (Distributed Memory):** En hardware, se refiere al acceso a memoria basado en red para memoria física que no es común. Como modelo de programación, las tareas solo pueden \"ver\" lógicamente la memoria local de la máquina y deben usar comunicaciones para acceder a la memoria en otras máquinas donde otras tareas están ejecutando.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Comunicaciones:** Las tareas paralelas típicamente necesitan intercambiar datos. Esto puede lograrse de varias maneras, como a través de un bus de memoria compartido o sobre una red.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Sincronización:** La coordinación de tareas paralelas en tiempo real, muy a menudo asociada con comunicaciones. La sincronización usualmente implica la espera por parte de al menos una tarea, y por lo tanto puede causar un aumento en el tiempo de ejecución en reloj de una aplicación paralela.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Granularidad Computacional (Computational Granularity):** En cómputo paralelo, la granularidad es una medida cuantitativa o cualitativa de la relación de cálculo a comunicación.\n",
    "\n",
    "  - **Gruesa:** cantidades relativamente grandes de trabajo computacional se realizan entre eventos de comunicación.\n",
    "  - **Fina:** cantidades relativamente pequeñas de trabajo computacional se realizan entre eventos de comunicación.\n",
    "  \n",
    "  \n",
    "La siguiente tabla resume las características principales de la granularidad gruesa y fina en el contexto del cómputo paralelo:\n",
    "\n",
    "| Característica            | Granularidad Gruesa                                       | Granularidad Fina                                         |\n",
    "|---------------------------|-----------------------------------------------------------|-----------------------------------------------------------|\n",
    "| **Tamaño de la Tarea**    | Grandes, abarcan mucho trabajo computacional.             | Pequeñas, abarcan menos trabajo computacional.            |\n",
    "| **Comunicación**          | Menor frecuencia de comunicación entre tareas.            | Mayor frecuencia de comunicación entre tareas.            |\n",
    "| **Sincronización**        | Menor necesidad de sincronización frecuente.              | Mayor necesidad de sincronización frecuente.              |\n",
    "| **Overhead**              | Menor overhead de comunicación y sincronización.          | Mayor overhead debido a la comunicación y sincronización. |\n",
    "| **Balance de Carga**      | Potencial desbalance de carga entre procesadores.         | Facilita un balance de carga más uniforme.                |\n",
    "| **Escalabilidad**         | Mejor escalabilidad en problemas con independencia.       | Escalabilidad limitada por la comunicación intensiva.     |\n",
    "| **Ejemplo de Aplicación** | Procesamiento de imágenes completas en paralelo.          | Cálculos de interacción de partículas en física.          |\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Aceleración Observada (speedup):** Es uno de los indicadores más simples y ampliamente usados para el rendimiento de un programa paralelo. Determina la aceleración observada de un código que ha sido paralelizado, definida como:\n",
    "\n",
    "$$\\frac{\\text{tiempo de ejecución en serie}}{\\text{tiempo de ejecución paralelo}}$$\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel30.png?raw=true\" width=\"350\" />\n",
    "</p>  \n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Sobrecarga Paralela (Overhead):** Tiempo de ejecución requerido que es único para tareas paralelas, en contraposición al que se hace para trabajo útil. La sobrecarga paralela puede incluir factores como:\n",
    "\n",
    "  - Tiempo de inicio de tarea\n",
    "  - Sincronizaciones\n",
    "  - Comunicaciones de datos\n",
    "  - Sobrecarga de software impuesta por lenguajes paralelos, bibliotecas, sistema operativo, etc.\n",
    "  - Tiempo de terminación de tarea\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Masivamente Paralelo:** Se refiere al hardware que comprende un sistema paralelo dado: tener muchos elementos de procesamiento. El significado de \"muchos\" sigue aumentando, pero actualmente, las computadoras paralelas más grandes están compuestas por elementos de procesamiento que se cuentan por cientos de miles hasta millones.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Paralelo Embarazosamente (Embarrassingly):** Resolver muchas tareas similares, pero independientes, simultáneamente; poca o ninguna necesidad de coordinación entre las tareas.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Escalabilidad:** Se refiere a la capacidad de un sistema paralelo (hardware y/o software) para demostrar un aumento proporcional en la aceleración paralela con la adición de más recursos. Factores que contribuyen a la escalabilidad incluyen:\n",
    "\n",
    "  - Hardware: particularmente anchos de banda de memoria-CPU y propiedades de comunicación de red.\n",
    "  - Algoritmo de aplicación.\n",
    "  - Relacionados con la sobrecarga paralela.\n",
    "  - Características de su aplicación específica."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69f2a814",
   "metadata": {},
   "source": [
    "### Beneficios Potenciales, Límites y Costos de la Programación Paralela"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43c750fd",
   "metadata": {},
   "source": [
    "#### Ley de Amdahl"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8af6757",
   "metadata": {},
   "source": [
    "La [Ley de Amdahl](https://en.wikipedia.org/wiki/Amdahl%27s_law) establece que la aceleración potencial del programa está definida por la fracción de código ($P$) que puede ser paralelizado:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos2/blob/main/images/Parallel21.PNG?raw=true\" width=\"750\" />\n",
    "</p>  \n",
    "\n",
    "$$\\text{speedup}=\\frac{1}{1-P}$$\n",
    "\n",
    "- Si ninguna parte del código puede ser paralelizado, $P = 0$ y el $speedup = 1$ (sin aceleración).\n",
    "- Si todo el código es paralelizado, $P = 1$ y el speedup (aceleración) es infinito (en teoría).\n",
    "- Si el $50\\%$ del código puede ser paralelizado, $speedup_{max}=2$, lo que significa que el código se ejecutará dos veces más rápido.\n",
    "\n",
    "Introduciendo el número de procesadores que realizan la fracción paralela del trabajo, la relación se puede modelar por:\n",
    "\n",
    "$$\\text{speedup}=\\frac{1}{\\frac{P}{N}+S}$$\n",
    "\n",
    "donde $P$ = fracción paralela, $N$ = número de procesadores y $S$ = fracción serial.\n",
    "Pronto se hace evidente que hay límites para la escalabilidad del paralelismo. Por ejemplo:\n",
    "\n",
    "```\n",
    "                         aceleración\n",
    "              -------------------------------------\n",
    "        N     P = .50   P = .90   P = .95   P = .99\n",
    "      -----   -------   -------   -------   -------\n",
    "         10      1.82      5.26      6.89      9.17\n",
    "        100      1.98      9.17     16.80     50.25    \n",
    "      1,000      1.99      9.91     19.62     90.99\n",
    "     10,000      1.99      9.91     19.96     99.02\n",
    "    100,000      1.99      9.99     19.99     99.90\n",
    "```\n",
    "- ***Cita \"famosa\":*** *¡Puedes pasar una vida intentando paralelizar el 95% de tu código, y nunca lograrás más de 20 veces de aceleración sin importar cuántos procesadores utilices!* \n",
    "\n",
    "Sin embargo, ciertos problemas demuestran un aumento en el rendimiento al incrementar el tamaño del problema. Por ejemplo:\n",
    "\n",
    "```\n",
    "        Cálculos de Malla 2D\n",
    "        Fracción Paralela        85 segundos 85%   \n",
    "        Fracción Serial          15 segundos   15%   \n",
    "        \n",
    "```\n",
    "\n",
    "Podemos aumentar el tamaño del problema duplicando las dimensiones de la malla y dividiendo a la mitad el paso de tiempo. Esto resulta en cuatro veces la cantidad de puntos de la malla y el doble de número de pasos de tiempo. Los tiempos entonces se ven así:  \n",
    "\n",
    "```\n",
    "        Cálculos de Malla 2D \n",
    "        Fracción Paralela         680 segundos 97.84%   \n",
    "        Fracción Serial           15 segundos    2.16%   \n",
    "```\n",
    "\n",
    "Problemas que aumentan el porcentaje de tiempo paralelo con su tamaño son más escalables que problemas con un porcentaje fijo de tiempo paralelo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ce4b2eb",
   "metadata": {},
   "source": [
    "#### Complejidad"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06e0a10a",
   "metadata": {},
   "source": [
    "En general, las aplicaciones paralelas son más complejas que las aplicaciones seriales correspondientes. No solo se tienen múltiples flujos de instrucciones ejecutándose al mismo tiempo, sino que también se tiene el flujo de datos entre ellos.\n",
    "Los costos de la complejidad se miden en tiempo de programador en prácticamente todos los aspectos del ciclo de desarrollo de software:\n",
    "- Diseño\n",
    "- Codificación\n",
    "- Depuración\n",
    "- Afinación\n",
    "- Mantenimiento  \n",
    "\n",
    "Adherirse a las \"buenas\" prácticas de desarrollo de software es esencial al desarrollar aplicaciones paralelas."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8e62acc",
   "metadata": {},
   "source": [
    "#### Portabilidad"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7015a718",
   "metadata": {},
   "source": [
    "Gracias a la estandarización en varias APIs, como MPI, OpenMP y los hilos POSIX, los problemas de portabilidad con programas paralelos no son tan graves como en años pasados. Sin embargo,\n",
    "todos los problemas habituales de portabilidad asociados con programas seriales se aplican a programas paralelos. Por ejemplo, si se utilizan \"mejoras\" de un proveedor a Fortran, C o C++, la portabilidad será un problema.  \n",
    "\n",
    "A pesar de que existen estándares para varias APIs, las implementaciones difieren en varios detalles, a veces hasta el punto de requerir modificaciones del código para efectuar la portabilidad.  \n",
    "\n",
    "Los sistemas operativos pueden jugar un papel clave en los problemas de portabilidad del código.\n",
    "Las arquitecturas de hardware son característicamente muy variables y pueden afectar la portabilidad."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4d13ff4",
   "metadata": {},
   "source": [
    "#### Requisitos de Recursos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a86929ab",
   "metadata": {},
   "source": [
    "La intención principal de la programación paralela es disminuir el tiempo de ejecución en reloj de pared, sin embargo, para lograr esto, se requiere más tiempo de CPU. Por ejemplo, un código paralelo que se ejecuta en 1 hora en 8 procesadores en realidad utiliza 8 horas de tiempo de CPU.  \n",
    "\n",
    "La cantidad de memoria requerida puede ser mayor para códigos paralelos que para códigos seriales, debido a la necesidad de replicar datos y por los sobrecargos asociados con bibliotecas de soporte paralelo y subsistemas.  \n",
    "\n",
    "Para programas paralelos de corta duración, en realidad puede haber una disminución en el rendimiento en comparación con una implementación serial similar. Los costos de sobrecarga asociados con la configuración del entorno paralelo, la creación de tareas, las comunicaciones y la terminación de tareas pueden constituir una parte significativa del tiempo total de ejecución para ejecuciones cortas."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6619a827",
   "metadata": {},
   "source": [
    "#### Escalabilidad"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1102d3c1",
   "metadata": {},
   "source": [
    "Dos tipos de escalabilidad basados en el tiempo hasta la solución: escalabilidad fuerte y escalabilidad débil.  \n",
    "\n",
    "- ***Escalabilidad Fuerte (Amdahl):***\n",
    "  - El tamaño total del problema permanece fijo a medida que se agregan más procesadores.\n",
    "  - El objetivo es ejecutar el mismo tamaño de problema más rápido.\n",
    "  - La escalabilidad perfecta significa que el problema se resuelve en tiempo $1/P$ (en comparación con serial).  \n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Escalabilidad Débil (Gustafson):***\n",
    "  - El tamaño del problema por procesador se mantiene fijo a medida que se agregan más procesadores. El tamaño total del problema es proporcional al número de procesadores utilizados.\n",
    "  - El objetivo es ejecutar un problema más grande en la misma cantidad de tiempo.\n",
    "  - La escalabilidad perfecta significa que el problema $Px$ se ejecuta en el mismo tiempo que una ejecución de un solo procesador.  \n",
    "\n",
    "La capacidad de rendimiento de un programa paralelo para escalar es el resultado de una serie de factores interrelacionados. Simplemente agregar más procesadores rara vez es la respuesta.  \n",
    "\n",
    "El algoritmo puede tener límites inherentes a la escalabilidad. En algún punto, agregar más recursos causa una disminución en el rendimiento. Esta es una situación común con muchas aplicaciones paralelas.  \n",
    "\n",
    "Los factores de hardware juegan un papel significativo en la escalabilidad. Ejemplos:\n",
    "- Ancho de banda del bus memoria-CPU en una máquina SMP\n",
    "- Ancho de banda de la red de comunicaciones\n",
    "- Cantidad de memoria disponible en una máquina dada o un conjunto de máquinas\n",
    "- Velocidad del reloj del procesador  \n",
    "\n",
    "Las bibliotecas de soporte paralelo y el software de subsistemas pueden limitar la escalabilidad independientemente de su aplicación."
   ]
  },
  {
   "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
}