Procesamiento paralelo PDF

Preview

Summary

Un procesador en paralelo es el método mediante el cual una serie de tareas e instrucciones se ejecutan de forma simultánea....

Description

UNIVERSIDAD TÉCNICA DEL NORTE FACULTAD DE INGENIERÍA EN CIENCIAS APLICADAS CARRERA DE INGENIERIA EN SOFTWARE

MATERIA: Arquitectura de Computadoras DOCENTE: Ing. Carpio Pineda. INTEGRANTES: Vaca Alexis Valencia Ulises Velasco Brayan Véliz Alexander Villalva Klever Villota Jefferson Vinueza Kevin Yépez Diego Zamora Edison FECHA: 20/08/2020

Procesamiento paralelo cap.18 Cap. 18.1 Organización con varios procesadores Tipos de sistemas de paralelos La taxonomía introducida primeramente por Flynn [FLYN72] es todavía la forma más común de clasificar a los sistemas según sus capacidades de procesamiento paralelo. Flynn propuso las siguientes categorías o clases de computadores: •

•

•

•

Una secuencia de instrucciones y una secuencia de datos (SISD,Single Instruction Single Data): un único procesador interpreta una única secuencia de instrucciones para operar con los datos almacenados en una única memoria. Los computadores monoprocesador caen dentro de esta categoría. Una secuencia de instrucciones y múltiples secuencias de datos (SIMD,de Single Instruction Multiple Data): una única instrucción maquina controla paso a paso la ejecución simultanea y sincronizada de un cierto numero de elementos de proceso. Cada elemento de proceso tiene una memoria asociada, de forma que cada instrucción es ejecutada por cada procesador con un conjunto de datos diferentes. Los procesadores vectoriales y los matriciales pertenecen a esta categoría. Múltiples secuencias de instrucciones y una secuencia de datos (MISD): se transmite una secuencia de datos a un conjunto de procesadores, cada uno de los cuales ejecuta una secuencia de instrucciones diferentes. Esta estructura nunca ha sido implementada. Múltiples secuencias de instrucciones y múltiples secuencias de datos (MIMD): un conjunto de procesadores ejecuta simultáneamente secuencias de instrucciones diferentes con conjuntos de datos diferentes. Los SMP, los clusters y los sistemas NUMA son ejemplos de esta categoría.

En la organización MIMD los procesadores son de uso general; cada uno es capaz de procesar todas las instrucciones necesarias para realizar las transformaciones apropiadas de los datos. Los computadores MIMD se pueden subdividir además según la forma que tienen los procesadores para comunicarse. Si los procesadores comparten una memoria común, entonces cada procesador accede a los programas y datos

almacenados en la memoria compartida, y los procesadores se comunican unos con otros a través de esta memoria. La forma más común de este tipo de sistemas se conoce como multiprocesador simétrico (SMP). En un SMP, varios procesadores comparten una única memoria mediante un bus compartido y otro tipo de mecanismo de interconexión. Una característica distintiva de estos sistemas es que el tiempo de acceso a memoria principal es aproximadamente el mismo para cualquier procesador. Un desarrollo mas reciente es la organización con acceso no uniforme a memoria (NUMA). Como el propio nombre indica, el tiempo de acceso a zonas de memoria diferentes puede diferir en un computador NUMA. Un conjunto de computadores monoprocesador independientes o de SMP pueden interconectarse para formar un cluster. La comunicación entre los computadores se realiza bien mediante conexiones fijas o mediante algún tipo de red. Organizaciones paralelas En el mapa se puede observar como se manejan las organizaciones de computadores.

En el siguiente grafico se muestra la estructura de un SISD en el cual se dispone de una unidad de control (UC) que proporciona una secuencia de instrucciones (SI) a una unidad de proceso (UP). La unidad de proceso actúa sobre una única secuencia de datos (SD) captados desde la unidad de memoria (UM).

En el siguiente grafico se muestra una maquina SIMD, también existe una sola unidad de control, que proporciona una única secuencia de instrucciones a cada elemento de proceso. Cada elemento de proceso puede tener su propia memoria dedicada o puede ser una memoria compartida.

En los siguientes gráficos se muestra un computador MIMD en el cual hay múltiples unidades de control, y cada una proporciona una secuencia de instrucciones separada a su propio elemento de proceso. El MIMD puede ser un multiprocesador de memoria compartida o un multicomputador de memoria distribuida.

Cap.18.2 MULTIPROCESADORES SIMETRICOS Con el pasar del tiempo los fabricantes de microprocesadores han introducido los sistemas SMP. Este término se refiere a la arquitectura hardware del computador y también al comportamiento del sistema operativo que utiliza dicha arquitectura. El sistema operativo de un SMP planifica la distribución de procesos o hilos (threads) entre todos los procesadores. Este sistema tiene las siguientes ventajas: 1. Prestaciones. _ Si el trabajo de un computador puede organizarse de forma que partes de este se pueda realizar al mismo tiempo, entonces un sistema con varios procesadores proporcionará mejor rendimiento que un solo procesador. 2. Disponibilidad. _ en un multiprocesador simétrico, debido a que todos los procesadores pueden realizar las mismas funciones, un fallo en un procesador no hará que el computador se detenga. 3. Crecimiento Incremental. _ se pueden aumentar las prestaciones del sistema añadiendo más procesadores. 4. Escalado. _ los fabricantes pueden ofrecer productos con precios y prestaciones diferentes dependiendo del número de procesadores que contenga el sistema. Organización Cada procesador es autonomo.Cada procesador tiene acceso a una memoria principal.Tambien es posible que los procesadores intercambien señales directamente.La memoria a menudo se organiza de forma que sean posibles los accesos simultáneos a bloques de memoria separados.

Bus de Tiempo Compartido La organización más común de los computadores personales y servicios es el bus de tiempo compartido. El bus de tiempo compartido es el mecanismo mas simple para construir un sistema multiprocesador. El bus consta de líneas de control, dirección y datos. La organización del bus presenta varias características atractivas: Simplicidad. _ es la aproximación mas simple para organizar el multiprocesador. Flexibilidad. _ es generalmente sencillo expandir el sistema conectando más procesadores al bus. Fiabilidad. _ el fallo de cualquiera de los dispositivos no provocaría el fallo de todo el sistema.

-

Consideraciones de Diseño en un Sistema Operativo de Multiprocesador • •

• •

Procesos Concurrentes Simultáneos. _ permite que varios procesadores puedan ejecutar simultáneamente el mismo código. Planificación. _ puede realizarla cualquier procesador, por lo que puede evitarse los conflictos. El planificador debe asignar los procesos preparados a los procesadores disponibles. Sincronización. _asegura la exclusión mutua y la ordenación de eventos. Fiabilidad y Tolerancia a fallos. _ el sistema operativo debería ser posible una degradación cuando se produce un fallo en un procesador. El planificador debe reconocer la pérdida de un procesador y reestructurar las tables de gestión.

UN MICROPROCESADOR SIMETRICO (SMP) COMO GRAN COMPUTADOR La mayoría de las estaciones de trabajo de tipo SMP utilizan una estrategia de interconexión basada en un bus, la familia de grandes computadores denominada z990. Esta familia incluye computadores con un módulo de memoria principal hasta sistemas con 48 procesadores y 8 módulos de memoria. Los componentes claves de la configuración son los siguientes: •

Chip con dos núcleos de procesamiento (dual-core): cada microprocesador incluye dos procesadores idénticos denominados procesadores centrales.

•

•

• •

•

Cache L2: cada cache L2 contiene 32 Mbytes. Se organizan en grupos de cinco, de forma que cada grupo recibe accesos de 8 microprocesadores duales y proporciona acceso a todo el espacio de memoria principal. Elemento de control de Sistema (SCE): se encarga de la resolución de la comunicación en el sistema y tiene un papel central en el mantenimiento en la coherencia de caché. Control de almacenamiento principal (MSC). _ interconecta los cachés L2 y la memoria principal. Módulos de memoria. _ cada módulo dispone de 32 GB de memoria. Los módulos de memoria se conectan al MSC a través de interfaces de memoria síncronos (SMI). Adaptador de bus de memoria (MBA). _ proporciona una interfaz a diversos canales.

Características del SMP z990 1. Interconexión conmutada. _ en los PC de tipo SMP es común utilizar una organización basada en un único bus compartido. Con esta organización el bus pasa a ser el cuello de la botella que afecta las presentaciones cuando se amplía el sistema. El z990 se enfrenta a este problema en dos formas. En primer lugar, la memoria principal se distribuye en cuatro módulos, cada uno con su propio controlador. El tráfico de cargas desde memoria se reduce, gracias a los caminos dependientes que hay a las áreas distintas en las que se ha dividido la memoria. En segundo lugar, la conexión entre los procesadores y un modulo de memoria no se lleva a cabo a través de un bus sino mediante enlaces punto a punto. Cada procesador tiene un enlace a cada una de las cachés L2, y cada caché L2 tiene un enlace a cada uno de los módulos de memoria. 2. Cachés L2 compartidas. _ En una de las primeras versiones de sus grandes SMP, conocida como generación 3 (G3), las Máquina de Negocios Internacionales (IBM) utilizaban cachés L2 especificas para procesador. En las versiones más recientes (G4, G5, y serie z990) se utilizan cachés L2 compartidas. Dos consideraciones van causando este cambio. -

En el cambio de la versión G3 a la G4, IBM paso a utilizar microprocesadores con el doble de velocidad. El análisis de las cargas de trabajo típicas mostraba un nivel elevado de instrucciones y datos compartidos por los procesadores.

Estas consideraciones llevaron al equipo de diseño de la versión G4 a considerar el uso de una más caché L2 compartidas por varios procesadores. Si, de hecho, varios procesadores comparten un elevado volumen de datos, una caché compartida puede incrementar el rendimiento en lugar de disminuirlo, ya que los datos compartidos que se encuentran en la caché compartida se obtienen más rápidamente que si se debería acceder a ellos a través del bus.

Cap. 18.3. COHERENCIA DE CACHÉ Y PROTOCOLO MESI COHERENCIA DE CACHE En los sistemas multiprocesadores actuales es muy común disponer de uno o dos niveles de caches asociados a cada procesador. El problema de coherencia de la cache, consiste en que pueden existir varias copias del mismo dato simultáneamente en caches diferentes, y si los procesadores utilizan sus copias, puede producir una visión inconsciente de la memoria. Si dos caches contienen una misma línea, y la línea se actualiza en una de las caches, la otra cace tendrá un valor no valido y las lecturas de las líneas continuas producirán resultados no válidos. El objetivo de un protocolo de memoria cache es situar las variables utilizadas recientemente en la cache apropiada y mantenerlas ahí para las distintas lecturas y escrituras, y a su vez se mantiene la consistencia entre las variables compartidas que se pudieran encontrar en varias caches a la vez. Algunas implementaciones adoptan una estrategia que implica tanto elementos de software como de hardware. SOLUCIONES DE SOFTWARE Intentan evitar la necesidad de circuitería y lógica hardware adicional dejando que el compilador y el sistema operativo se encarguen del problema. Los mecanismos de coherencia basados en el compilador realizan un análisis del código para determinar qué datos crean problemas al pasar a la cache, después el sistema operativo o el hardware impiden que se pasen a la cache los datos marcados como no almacenables en la cache. SOLUCIONES DE HARDWARE Se denominan protocolos de coherencia de cache. Estas soluciones permiten reconocer dinámicamente en el momento de la ejecución las situaciones de inconsistencia potenciales. Puesto que el problema se considera solo en el momento en que aparece. También difieren en una serie de aspectos, que incluyen el lugar donde se ubica la información de estado de líneas de datos, como se organiza esta información, donde se impone la coherencia, y los mecanismos para imponerla. PROTOCOLOS DE DIRECTORIOS Recogen y mantienen la información acerca de donde residen las copias de las copias. Normalmente hay un controlador centralizado que es parte del controlador de la memoria principal; y un directorio que se almacena en la memoria principal. Este directorio contiene información de estado global en relación de los contenidos de las diferentes caches locales.

PROTOCOLOS DE SONDEOS (SNOOPY PROTOCOLS) Distribuyen la responsabilidad de mantener la coherencia de cache entre todos los controladores de cache del multiprocesador. Una cache debe reconocer cuando una línea de las que contiene esta compartida con otras cache. Se adaptan bien a los multiprocesadores basados en un bus, puesto que el bus compartido proporciona una forma sencilla para la difusión y el sondeo, no obstante, puesto que uno de los objetivos de utilizar caches locales es de evitar los accesos al bus, hay que cuidar el incremento en el tráfico del bus que requiere la difusión y el sondeo no anule los beneficios de las caches locales. PROTOCOLO MESI Con el protocolo MESI la cache de datos incluye 2 bits de estado en la marca, puesto que cada línea puede estar en uno de estos 4 estados: • • • •

Modificado: la línea de cache ha sido modificada (es distinta a su valor en memoria principal) y está disponible en una sola cache. Exclusivo: la línea de cache tiene el mismo contenido que en memoria principal y no está presente en ninguna otra cache. Compartido: la línea de cache tiene el mismo contenido que en memoria principal y puede estar presente en otra cache. No-Valido: la línea de cache no contiene datos válidos.

Cap. 18.4. Procesamiento Multihebra. El apartado más importante de un procesador es su velocidad, la cual se mide en MHZ sin embargo, otro apartado fundamental es la cantidad promedio de instrucciones que se ejecutan entre cada ciclo. Procesamiento multihebras explicito e implícito Las explicitas pueden darse a nivel de usuario estas multihebras explicitas son las que se entrelazan con otras otro proceso que se esté ejecutando en paralelo. Las multihebras implícitas son aquellas que se entrelazan con otras del mismo proceso.

Aproximaciones al procesamiento multihebra explicito El procesador trata cada hebra separadamente y puede utilizar técnicas como la predicción de saltos, el renombramiento de registros u otras técnicas super escalares para optimizar la ejecución de una hebra. Lo que aprovecha es un paralelismo entre hebras que, sumado al paralelismo entre instrucciones, puede proporcionar una mejora de prestaciones considerables. Se debe considerar 4 aspectos fundamentales: • • • •

Multihebra enlazada Multihebra con bloqueo Multihebra simultánea Multiprocesador monochip

Casos de Procesamiento Escalar de una hebra

Escalar multihebra con entrelazado

Escalar multihebra con bloqueo

Cap. 18.5 CLUSTERS Se define un clúster como un grupo de computadores completos interconectados que trabajan conjuntamente como un único recurso de cómputo, creándose la ilusión de que se trata de una sola máquina. El termino de computador completo hace referencia a un sistema que puede funcionar por sí solo independientemente del clúster. En literatura, cada computador del clúster se denomina nodo. Beneficios: •

•

• •

Escalabilidad absoluta: Un clúster puede tener decenas de máquinas, que incluso superan las prestaciones de computadores independientes más potentes. Escalabilidad incremental: Su configuración permite añadir nuevos sistemas al clúster en ampliaciones sucesivas, sin tener que sustituir el sistema de que dispone. Alta disponibilidad: Dado que cada computador es autónomo, el fallo de uno no significa la pérdida del servicio. Mejor relación precio-prestaciones: Al Es posible configurar un clúster con mayor o igual potencia de computo que in computador independiente mayor, a menos costo.

Configuraciones de Clusters

La figura (a) muestra un clúster de dos nodos en el que la interconexión se realiza mediante un enlace de alta velocidad que puede utilizarse para intercambiar mensajes que coordinan la actividad del clúster.

La figura (b) es un clúster con disco compartido, el subsistema de disco común es un RAID. El uso del RAID es común en los clúster para que la elevada disponibilidad que se consigue no se vea comprometida por un disco compartido. Métodos de configuración de clusters: beneficios y limitaciones. Método de configuración del clúster

Descripción

Beneficios

Espera Pasiva

Un servidor secundario sustituye al servidor primario en caso de que falle

Fácil de implementar

Secundario activo

El servidor secundario también se utiliza para tareas de procesamiento

Coste reducido porque los servidores secundarios pueden utilizarse para el procesamiento Alta disponibilidad

Servidores separados

Servidores conectados a discos

Servidores compartiendo discos

Cada servidor tiene su propio disco. Los datos se copian desde el servidor primario al secundario Los servidores se conectan a los mismos discos, pero cada servidor tiene sus propios discos. SI falla un servidor, otro servidor accede a sus discos. Los servidores comparten simultáneamente el acceso a los discos

Penalización reducida en la red y en el servidor debido a la eliminación de las operaciones de copia. Penalización baja en la red y en el servidor. Riesgo reducido de fallo del sistema debido a un fallo de disco

Limitaciones Alto coste debido a que el servidor secundario no está disponible para otras tareas de procesamiento Aumenta la complejidad

Penalización elevada en la red y el servidor debido a las operaciones de copia Usualmente se necesitan discos espejo o tecnología RAID para afrontar el riesgo de fallo de disco Se necesita software de control de acceso exclusivo. Usualmente se utiliza con discos espejo o tecnología RAID

Consideraciones en el diseño del sistema operativo. •

• •

Gestión de fallos. La forma que se actúa frente a un fallo depende del tipo de configuración del clúster. Dos alternativas son los clusters de alta disponibilidad y clusters tolerantes a fallos. Equilibrado de carga. Un clúster necesita una capacidad efectiva para equilibrar la carga, para satisfacer el requisito de la escalabilidad incremental. Computación paralela. Algunos casos, para utilizar eficientemente un clúster requiere ejecutar en paralelo el software correspondiente. Enumerando tres aproximaciones al problema son: la paralelización mediante el compilador, paralelización realizada por el programados, o computación paramétrica.

• •

Arquitectura de los clusters En cada computador se instala una capa software intermedia (middleware) que permite el funcionamiento de todos los computadores como un único clúster. Los servicios y funciones que se espera de la capa de middleware son:

Los computadores se conectan a través de una red de área local de alta velocidad. Cada computador puede trabajar de forma independiente, con un software intermedio permite trabajar como un clúster. Incluyendo software para permitir una ejecución eficiente de los programas que se ejecuten en paralelo. Clusters Frente a Sistemas SMP Un SMP tiene como ventajas que son plataformas estables que consumen menos energía y espacio físico, también resulta más fácil la gestión y configuración. El clúster como ventajas tiene que es superior al SMP en términos de escalabilidad absoluta e incremental, y además en términos de disponibilidad, ya que todos los componentes del sistema pueden hacerse altamente redundantes. Cap. 18.6. Acceso no uniforme a memoria. Las altern...