Apunte ac2 div.pdf

UNPAZ 2021 – LGTI – AC2 Unidad 3 – Arquitecturas De Computadoras Paralelas (Capítulo 8; “Arquitecturas De Computadoras Paralelas” Pág. 523 a 612 – Andrew Tanenbaum) Aunque las computadoras cada vez son más rápidas, se les pide más. En este sentid...

UNPAZ 2021 – LGTI – AC2 Unidad 3 – Arquitecturas De Computadoras Paralelas (Capítulo 8; “Arquitecturas De Computadoras Paralelas” Pág. 523 a 612 – Andrew Tanenbaum) Aunque las computadoras cada vez son más rápidas, se les pide más. En este sentido los astrónomos quieren simular toda la historia del Universo, desde el big bang hasta que acabe la función. A los ingenieros farmacéuticos les encantaría poder diseñar medicamentos a la medida de enfermedades específicas en sus computadoras en lugar de tener que sacrificar legiones de ratas. Los diseñadores de aviones podrían crear productos con mejor rendimiento de combustible si las computadoras pudieran efectuar todo el trabajo, sin necesidad de construir prototipos para túneles de viento. En pocas palabras, por más potencia de cómputo que tengamos al alcance, para muchos usuarios, sobre todo en las ciencias, la ingeniería y la industria, nunca es suficiente. Aunque la frecuencia de reloj es cada vez más alta, la velocidad de los circuitos no se puede incrementar indefinidamente. La velocidad de la luz ya representa un problema importante para los diseñadores de computadoras del extremo superior, y las posibilidades de lograr que los electrones y fotones se muevan a mayor velocidad no son muy halagüeñas. Los problemas de disipación de calor están convirtiendo a las supercomputadoras en acondicionadores de aire de vanguardia. Por último, aunque los transistores son cada vez más pequeños, llegará el momento en que cada transistor tendrá tan pocos átomos que los efectos de la mecánica cuántica (por ejemplo, el principio de incertidumbre de Heisenberg) podrían convertirse en un problema importante. Por ello, para poder atacar problemas cada vez más grandes, los arquitectos de computadoras están recurriendo a las computadoras paralelas. Aunque tal vez nunca sea posible construir una computadora con una sola CPU y un tiempo de ciclo de 0.001 ns, bien podría ser factible construir una con 1000 CPU, cada una de ellas con un tiempo de ciclo de 1 ns. Si bien este último diseño usa CPU más lentas que el primero, en teoría su capacidad de cómputo total es la misma. Es en esto en lo que están fincadas las esperanzas. Los FLOPS (operaciones de coma flotante por segundo) son una medida del rendimiento de una computadora, especialmente en cálculos científicos que requieren un gran uso de operaciones de coma flotante. Una computadora de escritorio, que usa un procesador Pentium4 o Athlon 64 típicamente opera a más de 3GHz, provee un desempeño computacional del rango de unos cuantos GFlops. “Los responsables de la célebre lista Top500 con los supercomputadores más potentes del mundo han publicado la tradicional edición de noviembre de esa clasificación, y hay un detalle llamativo: el más potente de todos ellos es Fugaku, un supercomputador que está basado en procesadores ARM. Con sus 442 petaflops, Fugaku vuelve a liderar una carrera que en 2021 nos traerá por fin el esperado supercomputador exascale con el que se superará una potencia de un exaflop (1.000 petaflops).”https://www.xataka.com/ordenadores/supercomputador-potente-mundo-japones-esta-basado- chips-arm-otra-revolucion-a-vista 106 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Podemos introducir paralelismo en diversos niveles. En el nivel de instrucciones, por ejemplo, el uso de filas de procesamiento y los diseños superescalares pueden elevar el desempeño en un factor de 10 respecto a los diseños puramente secuenciales. Sin embargo, para lograr un mejoramiento por un factor de cien o mil o un millón es necesario repetir CPU enteras, o al menos porciones sustanciales de ellas, y lograr que todas colaboren de forma eficiente. Aquí es donde está el reto. En esta U3 veremos los principios de diseño de computadoras paralelas y estudiaremos varios ejemplos que consisten en elementos de procesamiento y elementos de memoria. Los diseños difieren en la cantidad de cada elemento que está presente, en su constitución y en su interconexión. Algunos diseños emplean un número relativamente bajo de componentes de gran potencia, mientras que otras usan cantidades enormes de componentes más débiles. También son comunes los diseños intermedios a nivel físico y exponencial en el ambiente virtualizado. 3.1 - ASPECTOS DEL DISEÑO DE COMPUTADORAS PARALELAS Al analizar un nuevo sistema de cómputo paralelo, las tres preguntas fundamentales que debemos hacer son; 1. ¿Cuántos elementos de procesamiento hay, de qué tamaño y de qué tipo? 2. ¿Cuántos módulos de memoria hay, de qué tamaño y de qué tipo? 3. ¿Cómo se interconectan los elementos de procesamiento y de memoria? Examinemos brevemente cada uno de estos puntos. Los elementos de procesamiento pueden variar desde las ALU mínimas hasta las CPU completas, con tamaños que van desde una pequeña fracción de un chip hasta un metro cúbico de circuitos electrónicos por elemento. Como cabría esperar, cuando el elemento de procesamiento es una fracción de un chip, es posible equipar una computadora con una gran cantidad de tales elementos, quizá hasta un millón de ellos. Si el elemento de procesamiento es una computadora completa, con su propia memoria y equipo de E/S, el número de elementos es naturalmente más reducido, aunque se han instalado sistemas con casi 10,000 CPU. Cada vez se están construyendo más computadoras paralelas a partir de piezas comerciales, sobre todo CPU. Las capacidades y limitaciones de estas piezas a menudo influyen considerablemente en el diseño. Los sistemas de memoria a menudo se dividen en módulos que operan de forma independiente unos de otros, en paralelo para que muchas CPU puedan acceder a ellos al mismo tiempo. Dichos módulos pueden ser pequeños (kilobytes) o grandes (megabytes) y estar integrados a la CPU o situados en una tarjeta de circuitos distinta. Puesto que las memorias dinámicas (DRAM) grandes suelen ser mucho más lentas que las CPU, es común utilizar complejos esquemas de caché para agilizar el acceso a la memoria. Con frecuencia se usan dos, tres y hasta cuatro niveles de caché. Aunque existe cierta variación entre los diseños de CPU y de memoria, el área en la que más difieren los sistemas paralelos es en la forma en que se combinan las piezas. Los esquemas de interconexión se pueden dividir a grandes rasgos en dos categorías: estáticos y dinámicos. Los esquemas estáticos simplemente conectan todos los componentes en una configuración fija, como estrella, anillo o cuadrícula. En los esquemas de interconexión dinámica todas las piezas se conectan a una red de conmutación que puede encaminar dinámicamente mensajes entre los componentes. Los dos esquemas tienen puntos fuertes y débiles, como en breve veremos. 107 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Ver las computadoras paralelas como una colección de chips conectados entre sí de una forma u otra es básicamente una perspectiva ascendente del mundo. En un enfoque descendente la pregunta que se haría sería: “¿Qué es lo que se va a ejecutar en paralelo?” Aquí también tenemos toda una gama de posibilidades. Algunas computadoras paralelas se diseñan de modo que puedan ejecutar varios trabajos independientes al mismo tiempo. Dichos trabajos nada tienen que ver unos con otros y no se comunican. Un ejemplo típico es una computadora con entre 8 y 64 CPU creada para un gran sistema Unix de tiempo compartido que atiende a miles de usuarios remotos. Los sistemas de procesamiento de transacciones de los bancos (por ejemplo, cajeros automáticos), líneas aéreas (por ejemplo, sistemas de reservaciones) y grandes servidores de Web también pertenecen a esta categoría, lo mismo que las simulaciones independientes que se ejecutan de forma concurrente empleando diferentes conjuntos de parámetros. En una zona diferente de este espectro se encuentran las computadoras paralelas que se usan para ejecutar un solo trabajo que consiste en muchos procesos paralelos. Por ejemplo, consideremos un programa de ajedrez que analiza un tablero dado generando una lista de movimientos válidos y luego genera procesos paralelos para analizar (recursivamente) cada nuevo tablero en paralelo. Lo que se busca con el paralelismo aquí no es atender a más usuarios, sino resolver con mayor rapidez un solo problema. Pasando a otra zona del espectro, nos encontramos con máquinas en las que el paralelismo proviene del uso intensivo de filas de procesamiento o de muchas ALU que operan con el mismo flujo de instrucciones al mismo tiempo (SIMD: una instrucción múltiples datos). Las supercomputadoras numéricas con hardware especial para procesar vectores pertenecen a esta categoría. Aquí no sólo se está resolviendo un solo problema principal, sino que todas las partes de la computadora están trabajando en muy estrecha colaboración en casi el mismo aspecto del problema (por ejemplo, diferentes elementos de los mismos dos vectores se están sumando en paralelo). Aunque es difícil definirlo con exactitud, estos tres ejemplos difieren en lo que algunos llaman tamaño de grano. En los sistemas de tiempo compartido con múltiples CPU, la unidad de paralelismo es grande: todo un programa de usuario. La ejecución de programas grandes en paralelo con poca o ninguna comunicación entre los programas es paralelismo de grano grueso. El extremo opuesto, que ilustramos con el procesamiento de vectores, se llama paralelismo de grano fino. 108 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 El tamaño de grano se refiere a los algoritmos y al software, pero tiene un análogo directo en el hardware. Los sistemas con un número reducido de CPU grandes e independientes que tienen conexiones de baja velocidad entre sí se dice que están débilmente acoplados. Por ejemplo, los clústers. Lo opuesto son los sistemas fuertemente acoplados, en los que los componentes generalmente son más pequeños, más juntos e interactúan unos con otros con frecuencia a través de redes de comunicación con gran ancho de banda. Estos son los servidores corporativos “rackeables”. Observar que en una pc disponemos de un teclado, un monitor y un mouse. A nivel servidor se diponde de un sistema con Switch KVM, desde el que podemos conmutar a cada uno de los servidores conectados.. 109 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 En casi todos los casos, los problemas que tienen paralelismo de grano grueso se resuelven mejor en sistemas débilmente acoplados; así mismo, los problemas con paralelismo de grano fino se resuelven mejor en sistemas fuertemente acoplados. No obstante, es tanta la variedad de algoritmos, software y hardware, que en el mejor de los casos ésta es sólo una guía general. En las secciones que siguen examinaremos algunos de los aspectos del diseño de computadoras paralelas, comenzando con los modelos de comunicación y las redes de interconexión. Luego analizaremos cuestiones de desempeño y de software. Por último, concluiremos con una taxonomía de las arquitecturas de computadoras paralelas que determinará la organización del resto del capítulo, aunque no es la única existente. 3.1.1 Modelos de comunicación En cualquier sistema de cómputo paralelo, las CPU que trabajan en diferentes partes del mismo problema se deben comunicar entre sí para intercambiar información. La forma precisa en la que lo deben hacer es tema de muchos debates en la comunidad arquitectónica. Se han propuesto e implementado dos diseños distintos, Multiprocesadores y Multicomputadoras. En esta sección examinaremos ambos diseños. Multiprocesadores En el primer diseño, todas las CPU comparten una misma memoria física, como se ilustra en la figura 8-1 (a). Un sistema basado en memoria compartida como éste se llama multiprocesador o a veces simplemente sistema con memoria compartida. El modelo del multiprocesador se extiende al software. Todos los procesos que están ejecutándose en un multiprocesador pueden compartir un solo espacio de direcciones virtual mapeado en la memoria común. Cualquier proceso puede leer o escribir una palabra de memoria con sólo ejecutar una instrucción LOAD o STORE. No se necesita nada más. Dos procesos pueden comunicarse con sólo hacer que uno de ellos escriba datos en la memoria y que el otro los lea después. 110 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 La capacidad de dos (o más) procesos para comunicarse con sólo leer y escribir en la memoria es la razón por la que los Multiprocesadores son tan populares. Se trata de un modelo fácil de entender para los programadores que se puede aplicar a una amplia gama de problemas. Consideremos, por ejemplo, un programa que examina una imagen de mapa de bits y enumera todos los objetos que contiene. Una copia de la imagen se guarda en la memoria, como se muestra en la figura 8-l(b). Cada una de las 16 CPU ejecuta un solo proceso, al cual se ha asignado una de las 16 secciones para que la analice. Sin embargo, cada proceso tiene acceso a toda la imagen, lo cual es indispensable porque algunos objetos ocupan varias secciones. Si un proceso descubre que uno de sus objetos rebasa la frontera de su sección, simplemente sigue al objeto a la siguiente sección leyendo las palabras de esa sección. En este ejemplo, varios procesos descubrirán el mismo objeto, por lo que se requiere cierta coordinación al final para determinar cuántas, casas, árboles y aviones hay. Muchos fabricantes de computadoras venden Multiprocesadores. Como ejemplos podemos citar el Sun Enterprise 10000, el Sequent NUMA-Q, el SGI Origin 2000 y el HP/Convex Exemplar. Multicomputadoras El segundo diseño de arquitectura paralela es aquel en el que cada CPU tiene su propia memoria privada, accesible únicamente a ella y a ninguna otra CPU. Un diseño así se llama Multicomputadora o sistema de memoria distribuida, y se ilustra en la figura 8-2(a). Las Multicomputadoras suelen estar débilmente acopladas (aunque no siempre). Cada CPU de una Multicomputadora tiene su propia memoria local privada a la que puede acceder con sólo ejecutar instrucciones LOAD y STORE, pero a la que ninguna otra CPU puede acceder usando esas instrucciones. Así pues, los Multiprocesadores tienen un solo espacio de direcciones físico compartido por todas las CPU, mientras que las Multicomputadoras tienen un espacio de direcciones físico por CPU. Puesto que las CPU de una Multicomputadora no pueden comunicarse con sólo leer y escribir en la memoria común, necesitan un mecanismo de comunicación distinto. Lo que hacen es pasarse mensajes entre sí utilizando la red de interconexión. Como ejemplos de Multicomputadoras podemos mencionar al IBM SP/2, la Intel/Sandia Option Red y la Wisconsin COW. La ausencia de memoria compartida en hardware en una Multicomputadora tiene importantes implicaciones para la estructura del software. 111 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Tener un solo espacio de direcciones virtual en el que todos los procesos pueden leer y escribir con sólo ejecutar instrucciones LOAD y STORE es imposible en una Multicomputadora. Por ejemplo, si la CPU 0 (la de la esquina superior izquierda) de la figura 8-1 (b) descubre que parte de su objeto se extiende hacia la sección asignada a la CPU 1, podrá seguir leyendo la memoria para acceder a la cola del avión. Por otra parte, si la CPU 0 de la figura 8-2(b) efectúa el mismo descubrimiento, no puede leer simplemente la memoria de la CPU 1; tiene que hacer algo muy distinto para obtener los datos que necesita. En particular, la CPU 0 tiene que descubrir (de alguna manera) cuál CPU tiene los datos que necesita y enviar a esa CPU un mensaje en el que solicita una copia de los datos. Por lo regular, lo que haría entonces la CPU 0 sería bloquearse (es decir, esperar) hasta recibir una respuesta a su solicitud. Cuando el mensaje llega a la CPU 1, el software de esa CPU debe analizarlo y devolver los datos solicitados. Cuando el mensaje de respuesta llega a la CPU 0, el software se desbloquea y puede continuar su ejecución. En una Multicomputadora, la comunicación entre procesos a menudo utiliza primitivas en software como send (enviar) y receive (recibir). Esto hace que el software tenga una estructura diferente, mucho más complicada, que, en un Multiprocesador, y también implica que la división 112 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 correcta de los datos y su colocación en los lugares óptimos es una cuestión importante en una Multicomputadora. Esto es menos importante en un multiprocesador porque la colocación no afecta la corrección ni la programabilidad, aunque sí podría afectar el desempeño. En pocas palabras, programar una Multicomputadora es mucho más difícil que programar un Multiprocesador. Este es el punto de vista del S.O.. Así pues, tenemos un dilema: los Multiprocesadores son difíciles de construir, pero fáciles de programar, mientras que las Multicomputadoras son fáciles de construir, pero difíciles de programar. Esta observación ha dado pie a muchos intentos por construir sistemas híbridos que sean relativamente fáciles de construir y relativamente fáciles de programar. Tales trabajos han conducido a la revelación de que hay varias formas de implementar una memoria compartida, cada una con sus ventajas y desventajas. De hecho, gran parte de las investigaciones actuales sobre arquitecturas paralelas tiene que ver con la convergencia de las arquitecturas de Multiprocesador y Multicomputadora en formas híbridas, que combinan las ventajas de cada una. El Santo Grial aquí es encontrar diseños escalables, es decir, que sigan funcionando bien a medida que se añaden más y más CPU’s. Una estrategia para construir sistemas híbridos se basa en el hecho de que los sistemas de cómputo modernos no son monolíticos, sino que se construyen en una serie de capas: el tema de este libro. Este concepto abre la posibilidad de implementar la memoria compartida en cualquiera de varios niveles, como se muestra en la figura 8-3. 113 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 En la figura 8-3(a) vemos cómo el hardware implementa la memoria compartida como verdadero multiprocesador. En este diseño, hay una sola copia de sistema operativo con un solo conjunto de tablas, en particular la tabla de asignación de memoria. Cuando un proceso necesita más memoria, transfiere el control al sistema operativo a través de una trampa, éste busca en su tabla una página libre y hace corresponder la página con el espacio de direcciones del proceso. En lo que al sistema operativo concierne, hay una sola memoria y él lleva la contabilidad de qué proceso posee qué página en software. Hay muchas formas de implementar la memoria compartida en hardware. Por ejemplo: las arquitecturas multiprocesador de memoria compartida basadas en una arquitectura NUMA (por ejemplo, Dash Lenoski y otros 1992 y PLUS Bisiani y Ravishankar 1990) se basan en hardware especializado para proporcionar a los procesadores una visión consistente de la memoria compartida. Gestionan las instrucciones de acceso a memoria LOAD y STORE de forma que se comuniquen con la memoria remota y los módulos de caché según sea necesario para almacenar y obtener datos. Esta comunicación se realiza sobre sistemas de interconexión de alta velocidad similares a una red. El prototipo del multiprocesador Dash tiene 64 nodos; conectados mediante una arquitectura NUMA. (acceso a memoria no uniforme) Una segunda posibilidad es usar hardware de Multicomputadora y hacer que el sistema operativo simule la memoria compartida proporcionando un solo espacio de direcciones virtual paginado compartido para todo el sistema. En esta estrategia, llamada memoria compartida distribuida (DSM, Distributed Shared Memory) (Li, 1988; Li y Hudak, 1986,1989), cada página se ubica en una de las memorias de la figura 8-2(a). Cada máquina tiene su propia memoria virtual y sus propias tablas de páginas. Cuando una CPU efectúa una LOAD o STORE con una página que no tiene, ocurre una trampa al sistema operativo. Este localiza entonces la página y pide a la CPU que actualmente la tiene que anule su mapeo y envíe la página por la red de interconexión. Cuando la página llega, se mapea y la instrucción que causó el fallo se reinicia. En realidad, lo que el sistema operativo está haciendo es atender los fallos de página con la memoria remota en lugar de con el disco. Para el usuario, parece como si la máquina tuviera memoria compartida. Por ejemplo, la Memoria virtual paginada está presente en muchos sistemas, incluyendo Ivy [Li y Hudak 1989], Munin [Carter y otros 1991], Mirage [Fleisch y Popek 1989], Clouds [Dasgupta y otros 1991], Choices [Sane y otros 1990], COOL (Lea y otros 1993] y Mether [Minnich y Farber 1989], implementan DSM Distributed Shared Memory (memoria distribuida compartida), como una región de memoria virtual que ocupa el mismo rango de direcciones en el espacio de direcciones de cada proceso participante. Este tipo de implementación normalmente sólo es factible sobre una colección de computadores homogéneos con formatos de datos y de paginación comunes. 114 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Una tercera posibilidad es Middleware o lógica de intercambio de información entre aplicaciones ("interlogical") es un software que asiste a una aplicación para interactuar o comunicarse con otras aplicaciones, o paquetes de programas, redes, hardware y/o sistemas operativos. Éste simplifica el trabajo de los programadores en la compleja tarea de generar las conexiones y sincronizaciones que son necesarias en los sistemas distribuidos. De esta forma, se provee una solución que mejora la calidad de servicio, así como la seguridad, el envío de mensajes, la actualización del directorio de servicio, etc. Funciona como una capa de abstracción de software distribuida, que se sitúa entre las capas de aplicaciones y las capas inferiores (sistema operativo y red). El middleware abstrae de la complejidad y heterogeneidad de las redes de comunicaciones subyacentes, así como de los sistemas operativos y lenguajes de programación, proporcionando una API para la fácil programación y manejo de aplicaciones distribuidas. Dependiendo del problema a resolver y de las funciones necesarias, serán útiles diferentes tipos de servicios de middleware. Por lo general el middleware del lado cliente está implementado por el Sistema Operativo, el cual posee las bibliotecas que ejecutan todas las funcionalidades para la comunicación a través de la red.. Middleware trabaja con algunos lenguajes del tipo de Orca (Bal y otros 1990) y middleware como Linda (Carriero y Gelernter 1989) junto con sus derivados JavaSpaces y TSpaces (Wyckoff y otros 1998) proporcionan DSM sin necesidad de soporte hardware o de paginación, de una forma independiente de la plataforma. En este tipo de implementación, la computación se implementa mediante la comunicación entre instancias del nivel de soporte de usuario en los clientes y los servidores. Los procesos realizan llamadas a este nivel cuando acceden a datos en DSM. Las instancias de este nivel en los diferentes computadores acceden a los datos locales y se intercambian información siempre que sea necesario para el mantenimiento de la consistencia. Por ejemplo, el modelo Linda se basa en la abstracción de un espacio de tuplas (registros de datos que contienen una colección de campos) compartido. Los procesos de cualquier máquina pueden traer una tupla del espacio de tuplas compartido o enviar una tupla a ese espacio. Dado que el acceso al espacio de tuplas se controla totalmente en software (por el sistema de tiempo de ejecución Linda), no se requiere hardware especial ni apoyo del sistema operativo. Otro ejemplo de memoria compartida específica para un lenguaje implementada por el sistema de tiempo de ejecución es el modelo Orca de objetos de datos compartidos. En Orca, los procesos comparten objetos genéricos, no sólo tuplas, y pueden ejecutar métodos específicos para cada objeto con ellos. Cuando un método modifica el estado interno de un objeto, corresponde al sistema de tiempo de ejecución asegurarse de que todas las copias del objeto en todas las máquinas se actualicen simultáneamente. Una vez más, puesto que los objetos son un concepto estrictamente de software, el sistema de tiempo de ejecución puede efectuar totalmente la implementación, sin ayuda del hardware ni del sistema operativo. 115 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 3.1.2 Redes de interconexión En la figura 8-2 vimos que las Multicomputadoras deben su cohesión a las redes de interconexión. Daremos un pantallazo a las redes de interconexión para lograr comprender las arquitecturas. La razón fundamental por la que las redes de interconexión de los Multiprocesadores y las Multicomputadoras son similares es que en lo más fundamental ambas usan transferencia de mensajes. Incluso en una máquina con una sola CPU, si el procesador necesita leer o escribir una palabra, lo que normalmente hace es acertar ciertas líneas del bus y esperar una respuesta. Esta acción es fundamentalmente similar a la transferencia de mensajes: el iniciador envía una solicitud y espera una respuesta. En los Multiprocesadores grandes, la comunicación entre las CPU y la memoria remota casi siempre consiste en que la CPU envía un mensaje explícito, llamado paquete, a la memoria solicitándole ciertos datos, y la memoria devuelve un paquete de respuesta. Las redes de interconexión pueden tener hasta cinco componentes: 1. CPU. 2. Módulos de memoria. 3. Interfaces. 4. Enlaces 5. Conmutadores. Ya examinamos las CPU y las memorias con cierto detalle en otros capítulos y no lo haremos más aquí. Básicamente, se trata de los puntos finales de toda la comunicación. Las interfaces son los dispositivos que sacan los mensajes de las CPU y las memorias y los introducen en ellas. En muchos diseños, una interfaz es un chip o tarjeta que está conectada al bus local de cada CPU y puede comunicarse con ella y con la memoria local, si la hay. Es común que la interfaz incluya un procesador programable, así como algo de RAM privada. Por lo regular, la interfaz puede leer y escribir en diversas memorias, a fin de trasladar bloques de datos de un lugar a otro. Los enlaces son los canales físicos por los cuales se desplazan los bits; pueden ser eléctricos o de fibra óptica y seriales (anchura de un bit) o paralelos (anchura de más de un bit). Cada enlace tiene un ancho de banda máximo, que es el número de bits por segundo que puede transferir. Los enlaces pueden ser símplex (unidireccionales), semidúplex (en un sentido a la vez) o dúplex (en ambos sentidos a la vez). Los conmutadores son dispositivos con varios puertos de entrada y varios puertos de salida. Cuando un paquete llega a un conmutador por un puerto de entrada, ciertos bits del paquete se usan para seleccionar el puerto de salida al que se enviará el paquete. Un paquete podría tener sólo 2 o 4 bytes, pero también podría ser mucho más largo (digamos, 8 KB). Existe cierta analogía entre una red de interconexión y las calles de una ciudad. Las calles son como enlaces; cada una tiene una direccionalidad (de uno o dos sentidos), una tasa de datos máxima (límite de velocidad) y una anchura (número de carriles). Las intersecciones son como conmutadores. En cada intersección, un paquete que llega (peatón o vehículo) puede escoger cuál puerto de salida (calle) usará, dependiendo de cuál es su destino final. Al diseñar o analizar una red de interconexión, varias áreas destacan por su importancia. En primer lugar, está la cuestión de topología, es decir, la forma en que están dispuestos los componentes. En segundo lugar, está la forma en que el conmutador funciona y cómo maneja la 116 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 lucha por recursos. En tercer lugar, está el algoritmo de enrutamiento que se usa para que los mensajes lleguen a su destino de forma eficiente. A continuación, examinaremos brevemente cada uno de estos temas. Topología La topología de una red de interconexión describe la forma como están dispuestos los enlaces y los conmutadores; por ejemplo, en forma de anillo o de cuadrícula. Los diseños topológicos pueden modelarse como grafos, en los que los enlaces son aristas y los conmutadores son nodos, como se muestra en la figura 8-4. Cada nodo de una red de interconexión (o de su grafo) tiene cierto número de enlaces conectados a él. Los matemáticos llaman al número de enlaces grado del nodo; los ingenieros lo llaman abanico de salida. En general, cuanto mayor es el abanico de salida, más opciones de enrutamiento hay y mayor es la tolerancia de fallos, es decir, la capacidad para seguir funcionando, aunque falle un enlace, desviando el tráfico por otros caminos. Si cada nodo tiene k aristas y el cableado es el debido, es posible diseñar la red de modo que permanezca plenamente conectada, aunque fallen k - 1 enlaces. Otra propiedad de una red de interconexión (o su grafo) es su diámetro. Si medimos la distancia entre dos nodos por el número de aristas que es preciso recorrer para llegar de uno al otro, el título de una gráfica es la distancia entre los dos nodos que están más separados (es decir, entre los que la distancia es máxima). El diámetro de una red de interconexión se relaciona con el retraso de peor caso al enviar paquetes de una CPU a otra o de una CPU a la memoria porque cada brinco por un enlace toma una cantidad de tiempo finita. Cuanto más pequeño sea el diámetro, mejor será el desempeño de peor caso. Otra cosa importante es la distancia media entre dos nodos, la cual se relaciona con el tiempo de tránsito medio de los paquetes. Otra propiedad importante de una red de interconexión es su capacidad de transmisión, es decir, cuántos datos puede transferir por segundo. Una medida útil de esta capacidad es el ancho de banda bisectriz. Para calcular esta cantidad, primero tenemos que dividir (conceptualmente) la red en dos partes iguales (en términos del número de nodos) pero disconexas eliminando un conjunto de aristas de su grafo. Luego calculamos el ancho de banda total de las aristas que se eliminaron. Puede haber muchas formas distintas de dividir la red en dos partes iguales. El ancho de banda bisectriz es el mínimo de todas las divisiones posibles. La importancia de este número radica en que, si el ancho de banda bisectriz es, digamos, de 800 bits/s, entonces si hay mucha comunicación entre las dos mitades el rendimiento total podría estar limitado a sólo 800 bits/s, en el peor de los casos. Muchos diseñadores creen que el ancho de banda bisectriz es la métrica más importante de una red de interconexión. Muchas redes de interconexión se diseñan con el objetivo de maximizar el ancho de banda bisectriz. Las redes de interconexión se pueden caracterizar por su dimensionalidad. Para nuestros fines, la dimensionalidad está determinada por el número de opciones que hay para llegar del origen al destino. Si nunca hay opciones (es decir, sólo hay un camino de cada origen a cada destino), la red es cero-dimensional. Si hay una dimensión en la que se puede tomar una decisión, por ejemplo, ir al oriente o ir al poniente, la red es unidimensional. Si hay dos ejes, de modo que un paquete puede ir al oriente o al poniente, o bien ir al norte o al sur, la red es bidimensional, etcétera. A continuación, se muestran varias topologías. Sólo se han incluido los enlaces (líneas) y los conmutadores (puntos). Las memorias y las CPU (que no se muestran) por lo regular estarían conectadas a los conmutadores mediante interfaces. 117 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 En la figura tenemos una configuración de estrella cero-dimensional, en la que las CPU y memorias estarían conectadas a los nodos exteriores, y el nodo central sólo realizaría conmutación. Aunque su diseño es sencillo, si el sistema es grande es muy probable que el conmutador central sea un importante cuello de botella. Además, desde el punto de vista de la tolerancia de fallos, este diseño es deficiente porque un solo fallo en el conmutador central destruye por completo el sistema. En la figura tenemos otro diseño que está en el otro extremo del espectro, una interconexión total, de seis dimensiones, o sea un hexeracto. Aquí cada nodo tiene una conexión directa con todos los demás nodos. Este diseño maximiza el ancho de banda bisectriz, minimiza el diámetro y es en extremo tolerante de fallos (puede perder cualquier enlace y aun así seguir plenamente conectado). Lo malo es que el número de enlaces requeridos para k nodos es k (k -l) / 2, cifra que pronto se vuelve inmanejable cuando k es grande. Una tercera topología cero-dimensional es el árbol, que se ilustra en la. Un problema con este diseño es que el ancho de banda bisectriz es igual a la capacidad de un enlace. Puesto que normalmente hay mucho tráfico cerca de la parte alta del árbol, los nodos de arriba se convertirán en cuellos de botella. Una forma de remediar este problema es incrementar el ancho de banda bisectriz dando a los enlaces superiores mayor ancho de banda. Por ejemplo, los enlaces del nivel más bajo podrían tener una capacidad de b, el siguiente nivel podría tener una capacidad de 2b, y los enlaces del nivel superior podrían tener 4b cada uno. Un diseño así se denomina árbol grueso y se ha usado en Multicomputadoras comerciales como la (ahora difunta) CM-5 de Thinking Machines. El anillo es una topología unidimensional según nuestra definición porque cada paquete que se envía tiene la opción de ir a la derecha o ir a la izquierda. La cuadrícula o malla es un diseño bidimensional que se ha usado en muchos sistemas comerciales. Es muy regular, fácil de cambiar de escala hasta tamaños muy grandes, y tiene un diámetro que aumenta según la raíz cuadrada del número de nodos. 118 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Una variante de la cuadrícula es el doble toroide, es un diseño bidimensional reforzada que es una cuadrícula cuyas aristas están conectadas. Esta topología no sólo es más tolerante de fallos que la cuadricula, sino que su diámetro también es menor porque las esquinas opuestas ahora pueden comunicarse con sólo dos pasos. El cubo es una topología tridimensional regular. Hemos ilustrado un cubo de 2 x 2 x 2, pero en el caso general podría ser un cubo de k x k x k. El cubo tetradimensional construido a partir de dos cubos tridimensionales cuyas aristas correspondientes están conectadas. Podríamos crear un cubo pentadimensional clonando la estructura de la figura anterior y conectando los nodos correspondientes para formar un bloque de cuatro cubos. Para llegar a seis dimensiones, o sea un hexeracto, podríamos repetir el bloque de cuatro cubos e interconectar los nodos correspondientes, y así. 119 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Dependiendo de la cantidad de dimensiones un hipercubo puede tomar los siguientes nombres: Un hipercubo sin dimensión o en 0 dimensiones es un punto. Un hipercubo de 1 dimensión es un segmento de línea. Se forma a partir de unir dos puntos por medio de una recta desplazadas en un ángulo dimensional como la longitud. Un hipercubo de 2 dimensiones se llama cuadrado. Se forma a partir de unir dos segmentos por medio de dos rectas desplazadas en otro ángulo dimensional como la amplitud. Un hipercubo de 3 dimensiones se llama cubo. Se forma a partir de unir dos cuadrados por medio de cuatro rectas desplazadas en otro ángulo dimensional como la profundidad. Esta dimensión es la perceptible por el ser humano. Un hipercubo de 4 dimensiones se llama teseracto. Se forma a partir de unir dos cubos por medio de ocho rectas desplazadas en otro ángulo dimensional. De aquí en adelante, estos ángulos dimensionales no son perceptibles por el ser humano, ya que está sujeto a tres dimensiones. Un hipercubo de 5 dimensiones se llama penteracto. Un hipercubo de 6 dimensiones se llama hexeracto. Un hipercubo de 7 dimensiones se llama hepteracto. Un hipercubo de 8 dimensiones se llama octoracto. Un hipercubo de 9 dimensiones se llama eneracto. Un hipercubo de 10 dimensiones se llama decaracto. Muchas computadoras paralelas usan esta topología porque el diámetro crece linealmente con la dimensionalidad. En otras palabras, el diámetro es el logaritmo base 2 del número de nodos, de modo que, por ejemplo, un hipercubo 10-dimensional tiene 1024 nodos, pero un diámetro de sólo 10, lo que da excelentes propiedades de retraso. Observe que, en contraste, 1024 nodos dispuestos en una cuadricula de 32 x 32 tiene un diámetro de 62, más de seis veces más grande que el del hipercubo. El precio que se paga por el diámetro más pequeño es que el abanico de salida y por tanto el número de enlaces (y el costo) es mucho mayor para el hipercubo. No obstante, el hipercubo es una opción común en sistemas de alto desempeño. 120 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Conmutación Una red de interconexión consiste en conmutadores y alambres que los conectan. En la figura 8-5 vemos una red pequeña con cuatro conmutadores. Cada conmutador de este ejemplo tiene cuatro puertos de entrada y cuatro puertos de salida. Además, cada conmutador tiene algunas CPU y circuitos de interconexión (que no se muestran en su totalidad). La tarea del conmutador es aceptar paquetes que llegan por cualquier puerto de entrada y enviarlos por el puerto de salida correcto. Cada puerto de salida está conectado a un puerto de entrada que pertenece a otro conmutador por medio de un enlace serial o paralelo, que se muestra como líneas punteadas en la figura 8-5. Los enlaces seriales transfieren un bit a la vez. Los enlaces paralelos transfieren varios bits a la vez y por tanto tienen también señales para controlar el enlace. Los enlaces paralelos son más rápidos que los enlaces seriales con la misma frecuencia de reloj, pero tienen el problema del sesgo (asegurarse de que todos los bits lleguen al mismo tiempo) y son mucho más costosos. Hay varias posibles estrategias de conmutación. En una de ellas, llamada conmutación de circuitos, antes de enviar un paquete se reserva por adelantado el camino completo desde el origen hasta el destino. Se aseguran todos los puertos y buffers, de modo que cuando la transmisión se inicie esté garantizado que todos los recursos están disponibles y los bits pueden viajar a toda velocidad desde el origen, a través de todos los conmutadores, hasta el destino. La figura 8-5 ilustra la conmutación de circuitos, con un circuito reservado de la CPU 1 a la CPU 2, que se indica con la flecha negra curva. Aquí se han reservado tres puertos de entrada y tres puertos de salida. La conmutación de circuitos puede compararse con reservar la ruta de un desfile a través de una ciudad, pidiendo a la policía que bloquee todas las calles laterales con barricadas. Se requiere planificación por adelantado, pero una vez que se ha efectuado, el desfile puede avanzar a toda velocidad sin interferencia por parte de otro tráfico. La desventaja es que se requiere planificación anticipada y se prohíbe cualquier otro tráfico, aunque de momento no haya ningún integrante del desfile (paquete) a la vista. Una segunda estrategia de conmutación es la conmutación de paquetes con almacenamiento y reenvío. Aquí no es necesario reservar nada con anticipación. Más bien, el origen envía un paquete completo al primer conmutador, donde se almacena en su totalidad. a. En la figura 8-6(a), la CPU 1 es el origen, y el paquete entero, destinado a la CPU 2, se coloca primero en un buffer dentro del conmutador A. 121 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 b. Una vez que el paquete se ha acumulado cabalmente en el conmutador A, se transfiere al conmutador C, como se muestra en la figura 8 -6(b). c. Ya que el paquete entero ha llegado a C, se transfiere al conmutador D, como se muestra en la figura 8 -6(c). Por último, el paquete se envía al destino, la CPU 2. Observe que no se requiere Preparación y no se reservan recursos por adelantado Los conmutadores de almacenamiento y reenvío deben colocar los paquetes en buffers porque cuando un origen (una CPU, memoria o conmutador) presenta un paquete, cabe la posibilidad de que el puerto de salida requerido esté ocupado transmitiendo otro paquete. Si no se usaran buffers, los paquetes que llegaran y necesitaran un puerto ocupado tendrían que desecharse, y la red de interconexión sería muy poco confiable. Se usan tres estrategias de buffers. En la primera, uso de buffers en la entrada, cada puerto de entrada tiene asociados uno o más buffers en forma de cola de “primero que entra, primero que sale”. Si el paquete que está a la cabeza de la cola no puede transmitirse porque el puerto de salida que necesita está ocupado, simplemente espera. El problema con este diseño es que, si un paquete está esperando que se desocupe un puerto de salida, el paquete que viene atrás tiene que esperar, aunque esté destinado para un puerto desocupado. Esta situación se llama bloqueo de cabeza de línea, y se puede comparar a una sucesión de automóviles en una carretera de dos carriles que tiene que esperar porque el primer automóvil quiere dar vuelta a la izquierda, pero no puede hacerlo a causa del tráfico en el 122 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 otro sentido. Aunque el segundo automóvil y los que le siguen quieran seguir de frente, el automóvil que está a la cabeza los está bloqueando. El bloqueo de cabeza de línea puede eliminarse con uso de buffers en la salida. En este diseño, los buffers están asociados a los puertos de salida, no a los de entrada. A medida que llegan los bits de un paquete, se almacenan en un buffer asociado al puerto de salida correcto. Así, los paquetes destinados al puerto m no pueden bloquear a los paquetes destinados al puerto n. El número de buffers asociado a un puerto tanto de entrada como de salida es limitado. Si es preciso almacenar más paquetes de los que caben en los buffers, habrá que desechar paquetes. Una forma de mejorar esta situación es el uso de buffers comunes, en el que una sola reserva de buffers se reparte dinámicamente entre los puertos conforme se necesitan. Sin embargo, este esquema requiere una administración más compleja para llevar la contabilidad de los buffers, y también permite a una conexión con mucho tráfico acaparar todos los buffers y así bloquear otras conexiones. Además, cada conmutador necesita poder contener el paquete más grande, y probablemente varios paquetes de tamaño máximo, lo que tiende a incrementar las necesidades de memoria y reducir el tamaño máximo de paquete. Aunque la conmutación de paquetes con almacenamiento y reenvío es flexible y eficiente, tiene el problema de aumentar la latencia (retraso) de la red de interconexión. Supongamos que el tiempo requerido para que un paquete avance un tramo en la figura 8-6 es de T ns. Puesto que el paquete debe copiarse cuatro veces para que llegue de la CPU 1 a la CPU 2 (en A, en C, en D y en la CPU de destino), y ningún copiado puede iniciarse antes de que termine el anterior, la latencia de la red de interconexión es de 4T. Una solución es diseñar una red híbrida, con algunas de las propiedades de la conmutación de circuitos y algunas de la conmutación de paquetes. Por ejemplo, cada paquete podría dividirse lógicamente en unidades más pequeñas. Tan pronto como la primera unidad llega a un conmutador, se le puede transferir al siguiente conmutador, aun antes de que haya llegado la cola del paquete. Semejante estrategia difiere de la conmutación de circuitos en cuanto a que no se reservan con anticipación recursos de extremo a extremo, y puede haber competencia por los recursos (puertos y buffers). En el enrutamiento virtual de corte a través, si la primera unidad de un paquete no puede avanzar, el resto del paquete sigue llegando. En el peor de los casos, este esquema se degrada hasta convertirse en conmutación de paquetes con almacenamiento y reenvío. En una estrategia alternativa, el enrutamiento por túnel, si la primera unidad no puede avanzar, se le pide al origen que deje de transmitir, y así el paquete podría quedar tendido a lo largo de dos o tal vez aún más conmutadores. Una vez que están disponibles los recursos necesarios, el paquete puede continuar. Vale la pena señalar que ambas estrategias de enrutamiento utilizan algo análogo a las instrucciones de filas de procesamientos de una CPU. En un instante dado, cada conmutador sólo está efectuando una fracción pequeña del trabajo, pero juntos logran un mejor desempeño que el que cada uno podría lograr individualmente. Algoritmos de enrutamiento En cualquier red que no sea cero-dimensional hay que tomar decisiones acerca de la ruta que los paquetes han de seguir del origen al destino. En muchos casos existen varias rutas. La regla que determina por cuál sucesión de nodos debe viajar un paquete para ir del origen al destino se denomina algoritmo de enrutamiento. 123 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Se requieren buenos algoritmos de enrutamiento porque es común que haya varios caminos disponibles. Un buen algoritmo de enrutamiento puede distribuir la carga entre varios enlaces a fin de aprovechar al máximo el ancho de banda disponible. Además, el algoritmo de enrutamiento debe evitar los bloqueos mutuos dentro de la red de interconexión. Ocurre un bloqueo mutuo (o bloqueo mortal) cuando varios paquetes que están en tránsito al mismo tiempo se han apoderado de recursos de tal manera que ninguno de ellos puede avanzar y todos quedan bloqueados indefinidamente. En la figura 8-7 se da un ejemplo de bloqueo mutuo en una red de interconexión de conmutación de circuitos. (También puede haber bloqueos mutuos en las redes de conmutación de paquetes, pero es más fácil ilustrarlo en las de conmutación de circuitos.) Aquí cada CPU está tratando de enviar un paquete a la CPU que está en la posición diagonalmente opuesta. Cada una ha logrado reservar los puertos de entrada y de salida de su conmutador local, así como un puerto de entrada en el conmutador que sigue, pero no puede obtener el puerto de salida del segundo conmutador, por lo que tiene que esperar hasta que ese puerto se desocupe. Lo malo es que si las cuatro CPU inician este proceso simultáneamente, todas ellas se bloquearán y la red se suspenderá indefinidamente. Los algoritmos de enrutamiento se pueden clasificar como de enrutamiento de origen o de enrutamiento distribuido. En el enrutamiento de origen, el origen determina con anticipación la ruta completa que se seguirá por la red de interconexión, expresada como una lista de números de puerto que se usarán en cada conmutador del camino. Por lo regular, si la ruta pasa por k conmutadores, los primeros k bytes de cada paquete contendrán los k números de puerto de salida requeridos, un byte por puerto. Cuando el paquete llega a un puerto, el primer byte se separa y se usa para determinar el puerto de salida que se usará. El resto del paquete se encamina entonces al puerto correcto. En cada paso del camino, el paquete se acorta en un byte, y expone un nuevo número de puerto que será el siguiente en seleccionarse. En el enrutamiento distribuido, cada conmutador toma una decisión respecto al puerto al que enviará cada paquete que llegue. Si toma la misma decisión para cada paquete dirigido a un destino dado, se dice que el enrutamiento es estático. Si el conmutador toma en cuenta el tráfico actual, se dice que el enrutamiento es adaptativo. 124 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Un algoritmo de enrutamiento muy utilizado en cuadrículas rectangulares con cualquier cantidad de dimensiones y que se sabe no causa bloqueos mutuos es el enrutamiento dimensional. En este algoritmo, el paquete primero se desplaza a lo largo del eje x hasta la coordenada correcta, y luego a lo largo del eje y hasta la coordenada correcta, y así sucesivamente si hay más dimensiones. Por ejemplo, para ir de (3, 7,5) a (6, 9, 8) el paquete primero iría dex = 3ax = 6 pasando por (4, 7, 5), (5, 7 5) y (6, 7, 5). Luego viajaría por el eje y viajando a (6, 8, 5) y (6, 9, 5). Por último, el paquete viajaría por el eje z a (6, 9, 6), (6, 9, 7) y (6, 9, 8). Este algoritmo evita los ciclos que causan un bloqueo mutuo. 3.1.3 Desempeño Lo que se busca al construir una computadora paralela es que opere más rápidamente que una máquina uniprocesador. Si no logra este sencillo objetivo, no tiene razón de existir. Además, la meta debe alcanzarse con eficacia de costos. Una máquina que es dos veces más rápida que un uniprocesador, pero cuesta 50 veces más probablemente no tendrá muchas ventas. En esta sección examinaremos algunos de los aspectos de desempeño asociados a las arquitecturas de computadoras paralelas. Métricas de hardware Desde el punto de vista del hardware, las métricas de desempeño que interesan son la velocidad de la CPU y de E/S, y el desempeño de la red de interconexión. Las velocidades de la CPU y de E/S son las mismas que en el uniprocesador, de modo que los parámetros clave de interés en un sistema paralelo son los asociados a la interconexión. Dos son los elementos clave: la latencia y el ancho de banda, que examinaremos a continuación. La latencia de viaje redondo es el tiempo que una CPU tarda en enviar un paquete y recibir una respuesta. Si el paquete se envía a una memoria, la latencia mide el tiempo que toma leer o escribir una palabra o un bloque de palabras. Si el paquete se envía a otra CPU, la latencia mide el tiempo de comunicación interprocesador para paquetes de ese tamaño. Por lo regular, la latencia que interesa es la correspondiente a paquetes mínimos, que a menudo son una palabra o una línea de caché pequeña. La latencia comprende varios factores, y es diferente para las interconexiones de conmutación de circuitos, de almacenamiento y reenvío, de corte a través virtual y de enrutamiento por túnel. En el caso de la conmutación de circuitos, la latencia es la suma del tiempo de preparación y el tiempo de transmisión. Para preparar un circuito, es preciso enviar un paquete “de sondeo” que reserve los recursos e informe de los resultados de su gestión. Después, hay que armar el paquete de datos. Una vez que está listo, sus bits pueden fluir a toda velocidad, de modo que, si el tiempo de preparación total es T, el tamaño del paquete es de p bits y el ancho de banda es de b bits/s, la latencia en un sentido será T + p/b. Si el circuito es dúplex, no habrá tiempo de preparación para la respuesta, de modo que la latencia mínima para enviar un paquete de p bits y obtener una respuesta de p bits es de T + 2p/b segundos. En el caso de la conmutación de paquetes no es necesario enviar un paquete de sondeo al destino con anticipación, pero de todos modos hay cierto tiempo de preparación interno para armar el paquete, T. Aquí el tiempo de transmisión en un sentido es 7 + p/b, pero éste es sólo el tiempo requerido para que el paquete llegue al primer conmutador. Hay un retardo finito dentro del conmutador, digamos Td y luego el proceso se repite con el siguiente conmutador, etc. El retraso T se compone de un tiempo de procesamiento y un retraso de la cola de espera, mientras se 125 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 desocupa el puerto de salida. Si hay n conmutadores, la latencia total en un sentido será Ta + n(p/b + 7'.) + p/b, donde el término final se debe al copiado del último conmutador al destino. Las latencias en un sentido para el corte virtual a través y el enrutamiento por túnel en el mejor de los casos son cercanas a7 + p/b porque no se requiere un paquete de sondeo para establecer un circuito, y tampoco hay retraso de almacenamiento y reenvío. Básicamente, la latencia consiste en el tiempo de preparación inicial mientras se arma el paquete, más el tiempo que toma “sacar los bits a la calle”. En todos los casos hay que sumar el retraso de propagación, pero éste suele ser pequeño. La otra métrica de hardware es el ancho de banda. Muchos programas paralelos, sobre todo en las ciencias naturales, transfieren de aquí para allá una gran cantidad de datos, por lo que el número de bytes/s que el sistema puede transferir es crítico para el desempeño. Existen varias métricas para el ancho de banda. Ya vimos una de ellas, el ancho de banda bisectriz. Otra es el ancho de banda agregado, que se calcula por la simple suma de las capacidades de todos los enlaces. Este número proporciona la cantidad máxima de bits que pueden estar en tránsito en un momento dado. Otra métrica importante es el ancho de banda medio en la salida de cada CPU. Si cada CPU puede transmitir 1 MB/s, no sirve de mucho que la interconexión tenga un ancho de banda bisectriz de 100 GB/s. La comunicación estará limitada a la cantidad de datos que cada CPU puede enviar. En la práctica es muy difícil acercarse siquiera al ancho de banda teórico. Muchas fuentes de gasto extra reducen la capacidad. Por ejemplo, siempre hay cierto gasto extra asociado a cada paquete: para armarlo, construir su cabecera y ponerlo en marcha. El envío de 1024 paquetes de 4 bytes nunca logrará el mismo ancho de banda que el envío de un paquete de 4096 bytes. Lamentablemente, el uso de paquetes pequeños es mejor para lograr latencias bajas, puesto que los paquetes grandes bloquean demasiado tiempo las líneas y los conmutadores. Así, hay un conflicto inherente entre lograr una latencia baja y aprovechar al máximo el ancho de banda. En algunas aplicaciones, una cosa es más importante que la otra, y en otras aplicaciones es al revés. No obstante, cabe señalar que siempre es posible comprar más ancho de banda (instalando más cables o cables más anchos), pero no es posible comprar latencias más bajas. Por ello, generalmente es mejor tratar de hacer que las latencias sean lo más bajas posibles, y preocuparse por el ancho de banda después. Métricas de software Las métricas de hardware como la latencia y el ancho de banda se ocupan de lo que el hardware hace. Sin embargo, los usuarios tienen un punto de vista distinto. Ellos quieren saber qué tanto va a aumentar la rapidez de ejecución de sus programas en una computadora paralela, en comparación con un uniprocesador. Para ellos, la métrica clave es la aceleración: cuántas veces más rápidamente se ejecuta un programa en un sistema de n procesadores que en uno de un solo procesador. Por lo regular, estos resultados se presentan en gráficas como la de la figura 8-8. En ella vemos la ejecución de varios programas paralelos distintos en una Multicomputadora formada por 64 CPU Pentium Pro. Cada curva muestra la aceleración de un programa con k CPU en función de k. La línea punteada indica la aceleración perfecta, en la que el uso de k CPU hace que el programa sea k veces más rápido, para cualquier k. Pocos programas logran una aceleración perfecta, pero algunos se acercan. El problema de N cuerpos se adapta muy bien a una ejecución paralela; awari (un juego de mesa africano) obtiene resultados 126 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 razonables; pero la inversión de cierta matriz de perfilado no tarda menos de cinco veces menos por más CPU que estén disponibles. Los programas y los resultados se analizan en (Bal et al., 1998). Una parte de la razón por la que es casi imposible lograr una aceleración perfecta es que casi todos los programas tienen algún componente secuencial, como la fase de inicialización, la lectura de datos o la reunión de los resultados. Tener muchas CPU no ayuda mucho a estas actividades. Suponga que un programa se ejecuta durante T segundos en un uniprocesador, y que una fracción f de este tiempo corresponde a código secuencial y una fracción (1 –f) es potencialmente paralelizable, como se muestra en la figura 8-9(a). Si este último código se puede ejecutar en n CPU sin gasto extra, su tiempo de ejecución podrá reducirse de (1 –f )T a (1 – f) Tin en el mejor de los casos, como se muestra en la figura 8-9(b). Esto da un tiempo de ejecución total para las partes secuencial y paralela de fT + (1 – f)Tin. La aceleración no es más que el tiempo de ejecución del programa original, T, dividido entre este nuevo tiempo de ejecución: Con f = 0 podemos obtener una aceleración lineal, pero con f > 0 no es posible lograr la aceleración perfecta a causa del componente secuencial. Este resultado se conoce como ley de Amdahl. 127 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 La ley de Amdahl no es la única razón por la que es casi imposible lograr una aceleración perfecta. Las latencias de comunicación distintas de cero, los anchos de banda de comunicación finitos y las ineficiencias algorítmicas también son factores. Además, aunque se contara con 1000 CPU, no todos los programas pueden escribirse de modo que aprovechen tantas CPU, y el gasto extra de ponerlas todas en marcha puede ser considerable. Por añadidura, es común que el algoritmo mejor conocido no se pueda paralelizar bien, y sea necesario usar un algoritmo subóptimo en el caso paralelo. A pesar de todo esto, para muchas aplicaciones es altamente deseable lograr que el programa funcione con una rapidez n veces mayor, aunque se necesiten 2n CPU para ello. Después de todo, las CPU no son tan caras, y muchas compañías se conforman con una eficiencia muy por debajo del 100% en otras facetas de su operación. Cómo lograr un buen desempeño La forma más sencilla de mejorar el desempeño es agregar más CPU al sistema. Sin embargo, esta adición debe efectuarse de tal manera que se evite la creación de cuellos de botella. Un sistema en el que es posible añadir más CPU e incrementar de manera acorde la potencia de cómputo es un sistema escalable. Para ver algunas de las implicaciones de la escalabilidad, considere cuatro CPU conectadas por un bus, como se ilustra en la figura 8-10(a). Ahora imagine aumentar la escala del sistema a 16 CPU añadiendo 12 más, como se muestra en la figura 8-10(b). Si el ancho de banda del bus es de b MB/s, entonces si cuadruplicamos el número de CPU también habremos reducido el ancho de banda disponible por CPU de b/4 MB/s a b/16 MB/s. Un sistema así no es escalable. 128 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Hagamos ahora lo mismo con un sistema basado en una cuadrícula, como el que se muestra en la figura 8-10(c) y 8-10(d). Con esta topología, la adición de nuevas CPU también implica la adición de nuevos enlaces, por lo que el aumento de escala del sistema no hace que el ancho de banda por CPU se reduzca, como en el caso de un bus. De hecho, la proporción enlaces/CPU aumenta de 1.0 con 4 CPU (4 CPU, 4 enlaces) a 1.5 con 16 CPU (16 CPU, 24 enlaces), así que la adición de CPU mejora el ancho de banda colectivo por CPU. Desde luego, el ancho de banda no es la única consideración. La adición de CPU al bus no aumenta el diámetro de la red de interconexión ni la latencia en ausencia de tráfico, pero la adición de CPU a la cuadrícula sí lo hace. En el caso de una cuadrícula de n x n, el diámetro es de 2(n - 1), de modo que la latencia de peor caso (y la latencia media) aumenta aproximadamente con la raíz cuadrada del número de CPU. Si hay 400 CPU, el diámetro es de 38, mientras que si hay 1600 CPU el diámetro es de 78. Cuadruplicar el número de CPU duplica aproximadamente el diámetro y por tanto la latencia media. Idealmente, un sistema escalable debe mantener el mismo ancho de banda medio por CPU y una latencia media constante a medida que se añaden más CPU. En la práctica, es posible mantener suficiente ancho de banda por CPU, pero en todos los diseños prácticos la latencia crece al aumentar el tamaño. Lo mejor que puede hacerse es que el crecimiento sea logarítmico, como en un hipercubo. El aumento de la latencia al aumentar la escala del sistema es un problema porque la latencia a menudo es fatal para el desempeño en las aplicaciones de grano mediano y fino. Si un programa necesita datos que no están en la memoria local, a menudo su obtención implica un retraso sustancial, y cuanto mayor es el sistema, más largo es el retraso, como acabamos de ver. Este problema se presenta tanto en Multiprocesadores como en Multicomputadoras, porque en ambos casos la memoria física se divide en módulos dispersos. Una consecuencia de esta observación es que los diseñadores de sistemas a menudo hacen hasta lo imposible por reducir, o al menos ocultar, la latencia, empleando varias técnicas que mencionaremos a continuación; La primera técnica para ocultar la latencia es la repetición de datos. Si es posible mantener copias de un bloque de datos en varios lugares, será posible acelerar los accesos desde esos lugares. Una de las técnicas de repetición es el uso de cachés, en el que una o más copias de algunos bloques de datos se mantienen cerca de donde se están usando, y también cerca de donde “deben estar”. Otra estrategia consiste en mantener varias copias pares —copias que tienen la misma categoría— en contraposición a la relación asimétrica primario/secundario que se usa en las cachés. Cuando se mantienen varias copias, en cualquier forma, las cuestiones fundamentales son dónde se colocan los bloques de datos, cuándo y quién los coloca ahí. Las respuestas varían desde la colocación dinámica por demanda efectuada por hardware hasta la colocación intencional en el momento de la carga siguiendo directrices del compilador. En todos los casos, la coherencia de gestión es importante. Una segunda técnica para ocultar la latencia es la prebúsqueda. Si se puede traer un dato antes de que se necesite, el proceso de búsqueda podrá traslaparse con la ejecución normal para que cuando el dato se necesite, ya esté ahí. La prebúsqueda puede ser automática o estar bajo el control del programa. Cuando una caché carga no sólo la palabra a la que se hizo referencia, sino toda una línea de caché que contiene la palabra, está apostando a que las palabras que siguen también vayan a necesitarse pronto. La prebúsqueda también puede controlarse explícitamente. Cuando un compilador se da cuenta de que va a necesitar ciertos datos, puede incluir una instrucción explícita para obtenerlos, 129 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 y colocar esa instrucción en una posición suficientemente adelantada como para que los datos lleguen a tiempo. Esta estrategia requiere que el compilador tenga un conocimiento total de la máquina subyacente y de su temporización, así como control sobre dónde se colocan todos los datos. Tales instrucciones LOAD especulativas funcionan óptimamente cuando se sabe con seguridad que los datos se van a necesitar. Causar un fallo de página por un LOAD que está en una rama que después no se toma resulta muy costoso. Una tercera técnica que puede ocultar la latencia es el multienlace (multiíhreading). Casi todos los sistemas modernos manejan el concepto de multiprogramación, en el que varios procesos pueden ejecutarse simultáneamente (o en seudoparalelo por tiempo compartido). Si puede lograrse que la conmutación entre procesos sea lo bastante rápida (por ejemplo, si se proporciona a cada proceso su propio mapa de memoria y registros en hardware), entonces cuando un proceso se bloquea mientras espera la llegada de datos remotos el hardware puede conmutar rápidamente a otro proceso que sí pueda continuar. En el caso limitante, la CPU ejecuta la primera instrucción del enlace 1, la segunda instrucción del enlace 2, etc. De este modo, la CPU puede mantenerse ocupada, aunque los enlaces individuales tengan latencias de memoria largas. De hecho, algunas máquinas conmutan automáticamente entre los procesos de forma cíclica, después de cada instrucción, a fin de ocultar las latencias largas. Una de las primeras supercomputadoras, la CDC 6600, llevó esta idea a tal extremo que en sus anuncios se aseguraba que tenía 10 unidades de procesamiento periféricas que podían operar en paralelo. En realidad, sólo había un procesador periférico que simulaba 10 procesadores ejecutando instrucciones de cada uno por tumo circular, primero una instrucción del procesador periférico 1, luego una instrucción del procesador periférico 2, y así. Una cuarta técnica para ocultar la latencia es el uso de escrituras que no se bloquean. Normalmente, cuando se ejecuta una instrucción STORE, la CPU espera hasta que se finaliza la instrucción antes de continuar. Con escrituras que no se bloquean, se inicia la operación de memoria, pero el programa de todos modos continúa. Continuar después de un LOAD es más difícil, pero con ejecución en desorden hasta eso es posible. 3.1.4 Software Aunque este capítulo trata primordialmente las arquitecturas de computadora paralelas, es apropiado hablar un poco acerca del software también. Después de todo, sin software paralelo el hardware paralelo no sirve de mucho, y es por ello que los buenos diseñadores de hardware toman en cuenta las necesidades del software al diseñar el hardware. Si desea un tratamiento del software para computadoras paralelas, vea (Wilkinson y Alien, 1999). Existen cuatro estrategias generales para producir software para computadoras paralelas. 1. En un extremo está la adición de bibliotecas numéricas especiales a lenguajes secuenciales por lo demás normales. Por ejemplo, se podría invocar desde un programa secuencial un procedimiento de biblioteca que invierta una matriz grande o resuelva un conjunto de ecuaciones diferenciales parciales en un procesador paralelo sin que el procesador siquiera se dé cuenta de la existencia de paralelismo. El problema con este enfoque es que el paralelismo sólo puede usarse en unos cuantos procedimientos y el grueso del código seguirá siendo secuencial. 2. Una segunda estrategia es la adición de bibliotecas especiales que contienen primitivas de comunicación y control. Aquí el programador tiene la responsabilidad de crear y controlar el paralelismo dentro de un lenguaje de programación convencional, empleando estas primitivas adicionales. 130 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 3. El siguiente paso es añadir unas cuantas construcciones especiales a lenguajes de programación existentes, como la capacidad de bifurcar fácilmente nuevos procesos paralelos, ejecutar las iteraciones de un ciclo en paralelo, o efectuar operaciones aritméticas con todos los elementos de un vector al mismo tiempo. Este enfoque se ha adoptado ampliamente y se han modificado muchos lenguajes de programación para que incluyan algo de paralelismo. 4. La estrategia más extrema sería inventar un lenguaje totalmente nuevo especialmente para el procesamiento en paralelo. La ventaja obvia de inventar un nuevo lenguaje es que éste sería idóneo para la programación en paralelo, pero la desventaja igualmente obvia es que los programadores tendrían que aprender un nuevo lenguaje. Muchos de ellos tienen otras cosas que hacer con su tiempo. Casi todos los lenguajes paralelos nuevos son imperativos (con instrucciones para modificar variables de estado), pero unos cuantos son funcionales, basados en lógica u orientados a objetos. Ha habido tantas bibliotecas, extensiones y lenguajes inventados para la programación en paralelo, y abarcan una gama tan amplia de posibilidades, que es imposible clasificarlos todos de alguna forma razonable. En lugar de intentarlo, nos concentraremos en cinco cuestiones básicas que constituyen el corazón de todo el software para computadoras paralelas. A. Modelos de control. B. Granularidad del paralelismo. C. Paradigmas computacionales. D. Métodos de comunicación. E. Primitivas de sincronización. Cada una de estas cuestiones se estudiará en su oportunidad. A. Modelos de control Tal vez la decisión fundamental que el software debe tomar es si habrá un solo enlace de control o varios. En el primer modelo hay un programa y un contador de programa, pero varios conjuntos de datos. Cuando se emite una instrucción, se ejecuta con todos los conjuntos de datos simultáneamente, con diferentes elementos de procesamiento. Por ejemplo, imagine un programa meteorológico que cada hora recibe mediciones de temperatura de miles de sensores remotos que tienen que promediar para cada sensor. Cuando el programa emite la instrucción CARGAR LA TEMPERATURA PARA LA 1 A.M. EN EL REGISTRO R1 cada procesador la ejecuta utilizando sus propios datos y su propio R1. Después, cuando el programa emite la instrucción SUMAR LA TEMPERATURA PARA LAS 2 A.M. AL REGISTRO R1 una vez más, cada procesador lo hace utilizando sus propios datos. Al final del cálculo, cada procesador habrá calculado la temperatura media para un sensor distinto. 131 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Las implicaciones de este modelo de programación para el hardware son enormes. De hecho, lo que dice es que cada elemento de procesamiento es básicamente una ALU y una memoria, sin lógica propia para decodificar instrucciones. En vez de ello, una sola unidad centralizada trae instrucciones y le dice a las ALU lo que tienen que hacer a continuación. En el modelo alternativo hay varios enlaces de control, cada uno con su propio contador de programa, registros y variables locales. Cada enlace de control ejecuta su propio programa con sus propios datos, posiblemente comunicándose o sincronizándose con otros enlaces de control cada cierto tiempo. Existen muchas variaciones de esta idea básica, y juntas constituyen el modelo dominante del procesamiento en paralelo. Por esta razón, ahora nos concentraremos primordialmente en la computación en paralelo con múltiples enlaces de control. B. Granularidad del paralelismo Se puede introducir paralelismo de control en diversos niveles. En el nivel más bajo, las instrucciones de máquina individuales pueden contener paralelismo (por ejemplo, el IA-64). En este nivel, los programadores normalmente no tienen conocimiento del paralelismo; está bajo el control del compilador o del hardware. Un nivel más arriba está el paralelismo en el nivel de bloques, que permite a los programadores controlar explícitamente cuáles enunciados deben ejecutarse secuencialmente y cuáles deben ejecutarse en paralelo. Una de las formas más elegantes de expresar este tipo de paralelismo se debe a Algol 68, en el cual se usaba begin Enunciado-1; Enunciado-2; Enunciado-3 end para crear un bloque con (por ejemplo) tres enunciados arbitrarios que se debían ejecutar en sucesión. En contraste, begin Enunciado-1, Enunciado-2, Enunciado-3 end servía para ejecutar los mismos tres enunciados en paralelo. Mediante una colocación cuidadosa de signos de punto y coma, comas, paréntesis y delimitadores begin/end, se podían expresar combinaciones arbitrarias de ejecución secuencial y paralela. Se presenta un paralelismo con grano un poco más grueso cuando es posible llamar a un procedimiento y no obligar al invocador a esperar a que termine antes de continuar. No esperar implica que el invocador y el invocado se ejecutarán en paralelo. Si el invocador está en un ciclo que llama a un procedimiento en cada iteración y no espera a que termine ninguno de ellos, es posible iniciar un gran número de procedimientos en paralelo a la vez. Otra forma de paralelismo es tener un método para que un proceso cree o bifurque múltiples enlaces o procesos ligeros (hilos), todos los cuales se ejecutan dentro del espacio de direcciones del proceso. Cada enlace tiene su propio contador de programa, registros y pila, pero fuera de eso comparte el resto del espacio de direcciones (y todas las variables globales) con todos los demás enlaces. (En contraste con los enlaces, diferentes procesos no comparten un mismo espacio de direcciones.) Los enlaces se ejecutan con independencia unos de otros, posiblemente en diferentes CPU. En algunos sistemas, el sistema operativo tiene conocimiento de todos los enlaces y se encarga de planificarlos; en otros, cada proceso de usuario se encarga de su propia planificación y gestión de enlaces, sin que el sistema operativo siquiera sepa que existen enlaces. Por último, la forma más burda de paralelismo es hacer que varios procesos independientes colaboren para resolver un problema. A diferencia de los enlaces, que comparten un solo espacio de direcciones, cada proceso independiente tiene su espacio propio, por lo que los procesos deben 132 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 cooperar a cierta distancia. Esto implica que el problema tiene que dividirse en fragmentos relativamente grandes, uno para cada proceso. Sin embargo, los procesos independientes ofrecen la mayor oportunidad para aprovechar el paralelismo a gran escala, sobre todo en Multicomputadoras. C. Paradigmas computacionales Casi todos los programas paralelos, sobre todo los que implican grandes números de enlaces o procesos independientes, usan algún paradigma subyacente para estructurar su trabajo. Existen muchos de esos paradigmas. En esta sección sólo mencionaremos algunos de los más utilizados. 1. Una generalización de la idea de tener un programa paralelo que consta de un enlace de control y múltiples unidades de ejecución es el paradigma de programa único, múltiples datos (SPMD, Single Program Múltiple Data). La idea aquí es que, aunque el sistema consiste en varios procesos independientes, todos ejecutan el mismo programa, pero con diferentes conjuntos de datos. Sólo que ahora, a diferencia del ejemplo de las temperaturas, no están en coordinación, sincronizados hasta la última instrucción. En vez de ello, cada uno realiza el mismo cálculo, pero a su propio ritmo. 2. Un segundo paradigma es la fila de procesamiento (pipeline), que se ilustra en la figura con tres procesos. Los datos se alimentan al primer proceso, que los transforma y los alimenta al segundo proceso, etc. Si el flujo de datos es largo (por ejemplo, una presentación en video), todos los procesadores podrían estar ocupados al mismo tiempo. Las filas de procesamiento UNIX funcionan así y se pueden ejecutar como procesos individuales en paralelo en una Multicomputadora o un multiprocesador. 3. Otro paradigma es el cálculo de la figura llamado computo de fases, en el que el trabajo se divide en fases, por ejemplo, iteraciones de un ciclo. Durante cada fase, varios procesos trabajan en paralelo, pero cuando cada uno termina espera hasta que los demás han terminado también antes de iniciar la siguiente fase. Podemos encontrarlos como rondas de procesos. 133 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 4. Un cuarto paradigma es el de divide y vencerás, que se ilustra en la figura. En este paradigma un proceso inicia y luego se bifurca en otros procesos a los que puede delegar parte del trabajo. Una analogía en el mundo de la construcción es un contratista general que recibe un pedido, y luego subcontrata gran parte del trabajo a subcontratistas de albañilería, electricidad, plomería, pintura y otras especialidades. Estos, a su vez, podrían subcontratar parte de su trabajo a otros subcontratistas especializados. 5. Nuestro último modelo es el paradigma del trabajador repetido, a veces llamado granja de tareas, el cual se ilustra en la figura 8-11 (d). Aquí se tiene una cola de trabajo centralizada y los trabajadores sacan tareas de la cola y las llevan a cabo. Si una tarea genera nuevas tareas, éstas se añaden a la cola central. Cada vez que un trabajador termina su tarea actual, acude a la cola de tareas para obtener una nueva. Este paradigma también puede implementarse con un administrador activo en la parte superior que reparte el trabajo, en lugar de obligar a los trabajadores que lo consigan por su cuenta. D. Métodos de comunicación Cuando un programa se divide en fragmentos (digamos, procesos) que se ejecutan en paralelo, los fragmentos (procesos) a menudo necesitan comunicarse entre sí. Esta comunicación puede efectuarse de una de dos maneras: variables compartidas o transferencia explícita de mensajes. En el primer método, todos los procesos tienen acceso a la memoria lógica común y pueden comunicarse leyéndola y escribiendo en ella. Por ejemplo, un proceso puede ajustar una variable y otro proceso puede leerla. En un multiprocesador, las variables pueden compartirse entre múltiples procesos mapeando la misma página al espacio de direcciones de cada proceso. Entonces se pueden leer y escribir variables compartidas empleando instrucciones de máquina LOAD y STORE. En una Multicomputadora, aunque no tiene memoria física compartida, también es posible compartir variables lógicamente, aunque es un poco más complicado. Como vimos antes, Linda maneja el concepto de espacio de tuplas compartido, aun en una Multicomputadora, y Orca maneja el concepto de objetos compartidos cruzando fronteras de máquinas. Otra posibilidad es compartir un solo espacio de direcciones en una Multicomputadora y paginar a través de la red de interconexión. En síntesis, es posible permitir que los procesos se comuniquen a través de variables compartidas tanto en Multiprocesadores como en Multicomputadoras. La alternativa a la comunicación a través de memoria compartida es la comunicación por transferencia explícita de mensajes. En este modelo, los procesos usan primitivas como send y receive para comunicarse. Un proceso emite un send, nombrando a otro proceso como destino. Tan pronto como el segundo emite un receive, el mensaje se copia en el espacio de direcciones del receptor. Otro aspecto importante de la transferencia de mensajes es el número de receptores. El caso más simple es el de un transmisor y un receptor, llamado transferencia de mensajes punto a punto. Sin embargo, a veces es útil entregar un mensaje a todos los procesos, en lo que se conoce como difusión (broadcasting), o a un subconjunto específico de los procesos, en lo que se conoce como multidifusión (multicasting). 134 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Cabe señalar que la transferencia de mensajes es fácil de implementar en un multiprocesador con sólo copiar del transmisor al receptor. Por tanto, las cuestiones de memoria física compartida (multiprocesador versus Multicomputadora) y memoria lógica compartida (comunicación a través de variables compartidas versus transferencia explícita de mensajes) son independientes. Las cuatro combinaciones tienen sentido y pueden implementarse; se enumeran en la figura 8-12. E. Primitivas de sincronización Los procesos paralelos no sólo necesitan comunicarse; con frecuencia también necesitan sincronizar sus acciones. Un ejemplo de sincronización es cuando los procesos comparten variables lógicamente y tienen que asegurarse de que mientras un proceso está escribiendo en una estructura de datos compartida ningún otro proceso esté tratando de leerla. En otras palabras, se requiere alguna forma de exclusión mutua para evitar que varios procesos usen los mismos datos al mismo tiempo. Existen diversas primitivas de software que pueden servir para asegurar la exclusión mutua. Éstas incluyen semáforos, candados, mutexes y secciones críticas. La característica común de todas estas primitivas es que permiten a un proceso solicitar el uso exclusivo de algún recurso (variable compartida, dispositivo de E/S, etc.). Si se otorga el permiso, el proceso puede usar el recurso. Si un segundo proceso pide permiso mientras el primero todavía está usando el recurso, se le negará el permiso o se bloqueará hasta que el primer proceso haya liberado el recurso. Un segundo tipo de primitiva de sincronización que se necesita en muchos programas paralelos es alguna forma de permitir que todos los procesos se bloqueen hasta que finalice cierta fase del trabajo, como se muestra en la figura 8-11(b). Una primitiva común aquí es la barrera. Cuando un proceso llega a una barrera, se bloquea hasta que todos los procesos llegan a ella. Cuando llega el último proceso, todos los procesos se liberan simultáneamente y pueden continuar, parecido a las rondas de procesos o de fases. 135 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 3.1.5 Taxonomía de computadoras paralelas TP: en PPT Aunque podríamos hablar mucho más acerca del software para computadoras paralelas, las limitaciones de espacio nos obligan a regresar al tema principal de este capítulo, la arquitectura de las computadoras paralelas. Se han propuesto y construido muchos tipos de computadoras paralelas, por lo que es natural preguntarse si hay alguna forma de clasificarlas dentro de alguna taxonomía. Muchos investigadores lo han intentado, con regular éxito (Flynn, 1972; Gajski y Pier, 1985; Treleaven, 1985). El único esquema que se usa mucho es el de Flynn, pero hasta el de él es, en el mejor de los casos, una aproximación muy burda (figura 8-13). La clasificación de Flynn se basa en dos conceptos: flujos de instrucciones y flujos de datos. Un flujo de instrucciones corresponde a un contador de programa. Un sistema que tiene n CPU tiene n contadores de programa, y por tanto n flujos de instrucciones. Un flujo de datos consiste en un conjunto de operandos. El ejemplo de cálculo de temperaturas que se dio antes tiene varios flujos de datos, uno para cada sensor. Los flujos de instrucciones y de datos son, hasta cierto punto, independientes, por lo que existen cuatro combinaciones, las cuales se enumeran en la figura 8-13. 1. SISD es la computadora secuencial clásica de von Neumann; tiene un flujo de instrucciones, un flujo de datos y hace una cosa a la vez. La memoria principal genera el flujo de instrucciones a la Unidad de Control, que tras decodificarlas e interpretarlas, ordena sus ejecuciones en la Unidad Operativa compuesta por la ALU, y los registros internos de trabajo. El flujo de datos bidireccional comunica a la memoria principal y a la Unidad Operativa. 136 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 En el funcionamiento de los computadores SISD solo hay una corriente de instrucciones unidireccional y otra de datos bidireccional. 2. Las máquinas SIMD tienen una sola unidad de control que emite una instrucción a la vez, pero tienen múltiples ALU para ejecutarla con varios conjuntos de datos simultáneamente. La ILLIACIV (figura 2-8) es el prototipo de las máquinas SIMD. Existen máquinas SIMD modernas y se usan para cálculos científicos. En los computadores con esta arquitectura, la unidad de control existente supervisa el funcionamiento del conjunto de unidades operativas disponibles. La estructura corresponde a los llamados procesadores matriciales. La unidad de control interpreta las instrucciones y envía las correspondientes señales de control a las unidades operativas encargadas de su ejecución. La unidad de control comienza la búsqueda de una nueva instrucción, nada más iniciada la ejecución de la anterior, siendo posible de esta forma, realizar. 3. Las máquinas MISD son una categoría un tanto extraña, en la que varias instrucciones operan con un mismo dato. No se sabe a ciencia cierta si existen máquinas de este tipo, aunque algunas personas clasifican a las máquinas con filas de procesamiento como MISD. Esta estructura consta de varias unidades de control que reciben diferentes flujos de instrucciones que son ejecutadas en las correspondientes Unidades Operativas, las cuales se alimentan de un único flujo de datos. 4. Por último, tenemos las MIMD, que no son más que múltiples CPU independientes que operan como parte de un sistema mayor. Casi todos los procesadores paralelos 137 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 pertenecen a esta categoría. Tanto los Multiprocesadores como las Multicomputadoras son máquinas MIMD. Dicho conjunto de procesadores, cuyas unidades operativas soportan un flujo de datos y las unidades de control, un flujo de instrucciones. La taxonomía de Flynn termina aquí, pero la hemos extendido en la figura 8-14. Hemos dividido a SIMD en dos subgrupos. El primero es el de las supercomputadoras numéricas y otras máquinas que operan con vectores, realizando la misma operación con cada elemento del vector. El segundo es para las máquinas tipo paralelo, como la ILLIAC IV, en las que una unidad de control maestra, difunde instrucciones a muchas ALU independientes. En nuestra taxonomía, la categoría MIMD se ha dividido en; Multiprocesadores (máquinas con memoria compartida) y Multicomputadoras (máquinas que transfieren mensajes). Existen tres clases de Multiprocesadores, que se distinguen por la forma en que se implementa la memoria compartida: Acceso uniforme a la memoria (UMA, Uniform Memory Access), también llamada SMP (Symmetric Multi-Processing, "multiproceso simétrico") Acceso No Uniforme a la Memoria (NUMA, Non Uniform Memory 138 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Access) y sólo acceso a memoria caché (COMA, Cache Only Memory Access) Estas categorías existen porque en los Multiprocesadores grandes la memoria normalmente se divide en varios módulos. Las máquinas UMA (Uniform Memory Access) En un modelo de Memoria de Acceso Uniforme, la memoria física esta uniformemente compartida por todos los procesadores. Esto quiere decir que todos los procesadores tienen el mismo tiempo de acceso a todas las palabras de memoria. Cada procesador puede tener su cache privada, y los periféricos son también compartidos de alguna manera. A estos computadores se les suele llamar sistemas fuertemente acoplados dado el alto grado de compartición de los recursos. La red de interconexión toma la forma de bus común, conmutador cruzado, o una red multietapa. Cuando todos los procesadores tienen el mismo acceso a todos los periféricos, el sistema se llama multiprocesador simétrico. En este caso, todos los procesadores tienen la misma capacidad para ejecutar programas, tal como el Kernel o las rutinas de servicio de I/O. En un multiprocesador asimétrico, sólo un subconjunto de los procesadores puede ejecutar programas. A los que pueden, o al que puede ya que muchas veces es sólo uno, se le llama maestro. Al resto de procesadores se les llama procesadores adheridos (attached processors). La figura 4.3 muestra el modelo UMA de un multiprocesador. Es frecuente encontrar arquitecturas de acceso uniforme que además tienen coherencia de caché, a estos sistemas se les suele llamar CC-UMA (Cache-Coherent Uniform Memory Access). En contraste, un multiprocesador NUMA es un sistema de memoria compartida donde el tiempo de acceso varía según el lugar donde se encuentre localizado el acceso. La figura 4.4 muestra una posible configuración de tipo NUMA, donde toda la memoria es compartida pero local a cada módulo procesador. Otras posibles configuraciones incluyen los sistemas basados en agrupaciones (clusters) de sistemas como el de la figura que se comunican a través de otra red de comunicación que puede incluir una memoria compartida global. La ventaja de estos sistemas es que el acceso a la memoria local es más rápido que en los UMA, aunque un acceso a memoria no local es más lento. Lo que se intenta es que la memoria utilizada por los procesos que ejecuta cada procesador, se encuentre en la memoria de dicho procesador para que los accesos sean lo más locales posible. Aparte de esto, se puede añadir al sistema una memoria de acceso global. En este caso se dan tres posibles patrones de acceso. El más rápido es el acceso a memoria local. Le sigue el acceso a memoria global. El más lento es el acceso a la memoria del resto de módulos. 139 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 Al igual que hay sistemas de tipo CC-UMA, también existe el modelo de acceso a memoria no uniforme con coherencia de caché CC-NUMA (CacheCoherent Non-Uniform Memory Access) que consiste en memoria compartida distribuida y directorios de cache. Las máquinas COMA (Cache Only Memory Access) Un multiprocesador que sólo use caché como memoria es considerado de tipo COMA. La figura 4.5 muestra el modelo COMA de multiprocesador. En realidad, el modelo COMA es un caso especial del NUMA donde las memorias distribuidas se convierten en caches. No hay jerarquía de memoria en cada módulo procesador. Todas las caches forman un mismo espacio global de direcciones. El acceso a las caches remotas se realiza a través de los directorios distribuidos de las caches. Dependiendo de la red de interconexión empleada, se pueden utilizar jerarquías en los directorios para ayudar en la localización de copias de bloques de caché. El emplazamiento inicial de datos no es crítico puesto que el dato acabaría estando en el lugar en que se use más. La categoría MIMD comprende las Multicomputadoras que, a diferencia de los Multiprocesadores, no tienen una memoria primaria compartida en el nivel arquitectónico. En otras palabras, el sistema operativo de una CPU de Multicomputadora no puede acceder a memoria conectada a una CPU distinta con sólo ejecutar una instrucción LOAD; tiene que enviar un mensaje explícito y esperar una respuesta. La capacidad del sistema operativo para leer una palabra distante con sólo emitir una LOAD es lo que distingue a los Multiprocesadores de las Multicomputadoras. Como ya dijimos, aun en una Multicomputadora los programas de usuario podrían tener la capacidad para acceder a memoria remota usando instrucciones LOAD y STORE, pero esta ilusión es mantenida por el sistema operativo, no por el hardware. La diferencia es sutil, pero muy importante. Dado que las Multicomputadoras no tienen acceso directo a memoria remota, suele describírseles como máquinas sin acceso a memoria remota, (NORMA, NO Remóte Memory Access). Las Multicomputadoras se pueden dividir a grandes rasgos en dos categorías. La primera categoría contiene los procesadores masivamente paralelos (MPP, Massively Parallel Processors), que son supercomputadoras caras que consisten en muchas CPU acopladas estrechamente por una red de interconexión patentada de alta velocidad. La Cray T3E y la SP/2 de IBM son ejemplos muy conocidos. 140 Fabián Palacios - 2022  UNPAZ 2021 – LGTI – AC2 La otra categoría consiste en PC o estaciones de trabajo normales, tal vez montadas en anaqueles, y conectadas mediante tecnología comercial ordinaria. En el aspecto lógico no hay mucha diferencia, pero las enormes supercomputadoras que cuestan muchos millones de dólares se usan de diferente manera que las redes de PC armadas por los usuarios a una fracción del precio de un MPP. Estas máquinas “hechas en casa” reciben diversos nombres, como redes de estaciones de trabajo (NOW, Network of Workstations) y cúmulos de estaciones de trabajo (COW, Cluster of Workstations). En las secciones que siguen examinaremos con cierto detalle las principales categorías: SIMD, MIMD/Multiprocesadores y MIMD/Multicomputadoras. La meta es presentar un panorama general de cada tipo, sus subcategorías y sus principios de diseño fundamentales. Se usarán varios ejemplos como ilustración. Otras clasificaciones La clasificación de Flynn ha demostrado funcionar bastante bien para la tipificación de sistemas, y se ha venido usando desde décadas por la mayoría de los arquitectos de computadores. Sin embargo, los avances en tecnología y diferentes topologías, han llevado a