Multiprocesadores

MultiprocesadoresLos multiprocesadores son sistemas MIMD basados en varios procesadores funcionales de forma paralela e independiente. La principal caracterstica de los multiprocesadores es que la memoria est compartida, es decir, todos los procesadores comparten el mismo espacio de direccionamiento.Multiprocesadores:DefinicinEl procesamiento en paralelo es un proceso empleado para acelerar el tiempo de ejecucin de un programa dividindolo en mltiples trozos que se ejecutarn al mismo tiempo, cada uno en sus propios procesadores.La razn de ser del procesamiento en paralelo es acelerar la resolucin de un problema, la aceleracin que puede alcanzarse depende tanto del problema en s como de la arquitectura de la computadora.

Multiprocesamiento: DefinicinEl primer paso hacia la paralelizacin de las arquitecturas de los computadores, se da con la aparicin de los procesadores o sistemas vectoriales.Los procesadores vectoriales extienden el concepto de paralelismo por segmentacin al tratamiento de grandes cantidades de datos. El hecho de que los procesadores segmentados hayan venido asociados a los supercomputadores paralelos, los pone en la entrada a lo que son los sistemas paralelos.

Arquitecturas ParalelasEn relacin con la explotacin del paralelismo para su traduccin en mejora de rendimiento las aplicaciones (programas) manifiestan tres tipos:Paralelismo de Control. Paralelismo de Datos.Paralelismo de Flujo.Fuentes de Paralelismo en los ProgramasProviene del hecho de que determinadas sub-tareas de la aplicacin son independientes y en consecuencia pueden realizarse en paralelo (simultneamente).

Paralelismo de Control: Proviene del hecho de que ciertas aplicaciones trabajan con escrituras de datos muy regulares (vectores y matrices), repitiendo una misma accin sobre cada elemento de la estructura.

Paralelismo de Datos: Proviene del hecho de que ciertas aplicaciones funcionan como un flujo de datos sobre el que debe efectuarse una sucesin de operaciones en cascada (etapas).

Paralelismo de Flujo: Es la clasificacin ms extendida del paralelismo. Esta taxonoma de las arquitecturas est basada en la clasificacin atendiendo al flujo de datos e instrucciones en un sistema. Un flujo de instrucciones es el conjunto de instrucciones secuenciales que son ejecutadas por un nico procesador.Taxonoma de FlynnCon estas consideraciones Flynn clasifica los sistemas en 4 categoras:SISD (Single Instruction Single Data)SIMD (Single Instruction Multiple Data)MISD (Multiple Instruction Single Data)MIMD (Multiple Instruction Multiple Data)

DatosSimplesMltiplesInstruccionesSimplesSISDSIMDMltiplesMISDMIMDLos sistemas de este tipo se caracterizan por tener un nico flujo de instrucciones sobre un nico flujo de datos, es decir, se ejecuta una instruccin detrs de otra. Este es el concepto de arquitectura de Von Newmann donde en cualquier momento, solo se ejecuta una sola instruccin. Posee el registro nico de contador de programa. Un ejemplo de estos sistemas son las mquinas secuenciales convencionales, la mayora de computadoras, servidores y estaciones de trabajo.

SISD (Single Instruction Single Data)SISD

Estos sistemas tienen un nico flujo de instrucciones que operan sobre mltiples flujos de datos. Estos sistemas los tenemos en las mquinas vectoriales con hardware escalar y vectorial.Todos los elementos realizan una misma instruccin pero sobre una gran cantidad de datos. El funcionamiento de este tipo de sistemas es el siguiente: La unidad de control manda una misma instruccin a todas las unidades de proceso (ALUs). Las unidades de proceso operan sobre datos diferentes pero con la misma instruccin recibida.

SIMD (Single Instruction Multiple Data)Existen dos alternativas distintas que aparecen despus de realizarse esta clasificacin:Arquitectura Vectorial con segmentacin: Una CPU nica particionada en unidades funcionales independientes trabajando sobre flujos de datos concretosArquitectura Matricial (matriz de procesadores): Varias ALUs idnticas a las que el procesador de instrucciones asigna una nica instruccin pero trabajando sobre diferentes partes del programa.

SIMDSIMD

Son sistemas con mltiples instrucciones que operan sobre un nico flujo de datos. Los sistemas MISD se contemplan de dos maneras distintas:Varias instrucciones operando simultneamente sobre un nico dato.Varias instrucciones operando sobre un dato que se va convirtiendo en un resultado que ser la entrada para la siguiente etapa. Se trabaja de forma segmentada, todas las unidades de proceso pueden trabajar de forma concurrente.En este modelo, secuencias de instrucciones pasan a travs de mltiples procesadores. Diferentes operaciones son realizadas en diversos procesadores; N procesadores, cada uno con su propia unidad de control comparten una memoria comn.

MISD (Multiple Instruction Single Data)MISD

Este tipo de computadora es paralela al igual que las SIMD, la diferencia con estos sistemas es que MIMD es asncrono. No tiene un reloj central. Cada procesador en un sistema MIMD puede ejecutar su propia secuencia de instrucciones y tener sus propios datos. Esta caracterstica es la ms general y poderosa de esta clasificacin.

MIMD (Multiple Instruction Multiple Data)SPMD (Single Program, Multiple Data): Mltiples procesadores autnomos ejecutan simultneamente el mismo programa en diferentes datos. Tambin se conoce como Proceso nico, mltiples datos.MPMD (Mltiple Program, Mltiple Data): Mltiples procesadores autnomos simultneamente operan al menos 2 programas independientes. Tpicamente estos sistemas captan un nodo a ser el host o manager, que ejecutan un programa que cultiva datos fuera a todos los dems nodos, los cuales ejecutan un segundo programa.

Divisin de la arquitectura MIMDMIMD

ClasificacinPuede verse como un computador paralelo compuesto por varios procesadores interconectados que pueden compartir un mismo sistema de memoria. Los procesadores se pueden configurar para que ejecute cada uno una parte de un programa o varios programas al mismo tiempo. Dado que los multiprocesadores comparten los diferentes mdulos de memoria, pudiendo acceder varios procesadores a un mismo mdulo, los multiprocesadores tambin se les llama sistemas de memoria compartida.

Multiprocesadores

Dependiendo de la forma en que los procesadores comparten la memoria, se puede hacer una subdivisin de los multiprocesadores:

Uniform Memory Access (UMA)Cache-only Memory Architecture (COMA)Non Uniform Memory Access (NUMA) En sistemas con acceso a memoria uniforme, cada procesador tiene acceso directo a una sola memoria compartida. Todas las ubicaciones de la memoria son equidistantes a cada procesador, todos los procesadores tienen el mismo tiempo de acceso a todas las palabras de la memoria. La mayora de los sistemas UMA incorpora cach para eliminar las disputas de la memoria pero este mecanismo no se ve desde las aplicaciones.

Uniform Memory Access (UMA)Dado el alto grado de comparticin de los recursos y el alto nivel de interaccin entre procesadores, lo que hace que un procesador dependa de lo que hace otro.El sistema de interconexin debe ser rpido y puede ser de uno de los siguientes tipos:Bus comnRed crossbarRed multietapa

Modelo de la subdivisin UMA

Sistemas con acceso a memoria solo en caches, no tiene memoria compartida fsica, pero el cache solo constituye la memoria de las mquinas. Se provee un solo espacio fsico de direcciones pero los tiempos de acceso varan dependientemente si la ubicacin de la memoria requerida est en el cache local o en uno remoto. El software de aplicacin ignorara la arquitectura del sistema ya que la mquina se comporta en forma muy parecida a una mquina UMA con cache.

Cache-only Memory Architecture (COMA)Cache-only Memory Architecture (COMA)

Sistemas con acceso a memoria no uniforme, tienen una memoria fsica compartida distribuida. Cada particin de esta memoria se une directamente a un nodo pero se puede acceder a ella por procesadores en otros nodos va la red de interconexin. As, los tiempos de accesos a la memoria difieren dependiendo de si la ubicacin requerida es local al nodo o remota a este. Non Uniform Memory Access (NUMA)

Otro modelo NUMA que nace como la mezcla del modelo UMA explicado anteriormente y el modelo NUMA anterior, Es el cluster jerrquico en el que se combinan las memorias locales y las globales obteniendo una cierta escalabilidad del sistema.Los procesadores aparecen distribuidos en clusters (1 sistema UMA o un 1 sistema NUMA). Estos clusters estn conectados a la memoria global compartida. La ventaja de estos sistemas con respecto a los sistemas UMA, es que el acceso a memoria local es mucho ms rpido.

Cluster JerrquicoEs la organizacin ms comn en los computadores personales y servidores.El bus consta de lneas de direccin de datos, y control para implementar:El protocolo de transferencia de datos con la memoria.El arbitraje del acceso al bus cuando ms de un procesador compite por utilizarlo.Los procesadores utilizan cachs locales para:Reducir el tiempo medio de acceso a memoria, como en un monoprocesador.Disminuir la utilizacin del bus compartido.

Conexin por bus compartidoConexin por bus Compartido

Cada procesador (Pi) y cada mdulo de memoria (Mi) tiene su propio bus. Existe un conmutador (S) en los puntos de interseccin que permite conectar un bus de memoria con un bus de procesador.Para evitar conflictos cuando ms de un procesador pretende acceder al mismo mdulo de memoria se establece un orden de prioridad.Se trata de una red sin bloqueo con una conectividad completa pero de alta complejidad.

Conexin por Conmutadores (crossbar)Conexin por Conmutadores (crossbar)

Representan una alternativa intermedia de conexin entre el bus y el crossbar. Es de menor complejidad que el crossbar pero mayor que el bus simple. La conectividad es mayor que la del bus simple pero menor que la del crossbar. Se compone de varias etapas alternativas de conmutadores simples y redes de interconexin.

Conexin por red Multietapa

Se puede ver como un computador paralelo en el cual cada procesador tiene su propia memoria local. La memoria del sistema se encuentra distribuida entre todos los procesadores y cada procesador slo puede direccionar su memoria local; para acceder a las memorias de los dems procesadores debe hacerlo por paso de mensajes. Este acceso local y privado a la memoria es lo que diferencia los multicomputadores de los multiprocesadores.Dado que la memoria est distribuida entre los diferentes elementos de proceso, a estos sistemas se les llama distribuidos aunque no hay que olvidar que pueden haber sistemas que tengan la memoria distribuida pero compartida y por lo tanto no ser multicomputadores.

Multiprocesadores de Memoria Distribuida

Multiprocesadores de memoria distribuida

Hay dos formas de procesar la informacin, una es mediante la ejecucin en serie de una lista de comandos y la otra es la ejecucin de un comando demandado por los datos disponibles. La primera forma empez con la arquitectura de Von Newmann donde un programa almacenaba las rdenes a ejecutar, han convertido esta sencilla arquitectura en los multiprocesadores para permitir paralelismo.La segunda forma de ver el procesamiento desde el punto de vista del paralelizacin las instrucciones se ejecutan en el momento tienen los datos necesarios para ello, y naturalmente se debera poder ejecutar todas las instrucciones demandadas en un mismo tiempo.Mquinas de Flujo de Datos

Mquinas con mltiples elementos de proceso supervisados por una unidad de control capaces de llevar a cabo una nica instruccin sobre mltiples datos y corresponden a la clase SIMD de la taxonoma de Flynn.La idea de utilizacin de los procesadores matriciales es explotar el paralelismo en los datos de un problema ms que paralelizar la secuencia de ejecucin de las instrucciones. El problema se paraleliza dividiendo los datos en particiones sobre las que se pueden realizar las mismas operaciones. Un tipo de datos altamente particionable es el formado por vectores y matrices, por eso a estos procesadores se les llama matriciales.

Procesadores Matriciales

Un procesador vectorial es un diseo de CPU capaz de ejecutar operaciones matemticas sobre mltiples datos de forma simultnea, en contraste con los procesadores escalares, capaces de manejar slo un dato cada vez.Los procesadores vectoriales son muy comunes en el rea de la computacin cientfica.En la arquitectura de procesadores vectoriales se encuentran:Los procesadores vectoriales memoria-memoria son capaz de extraer dos vectores de memoria y operar sobre ellos. El inconveniente sera el cuello de botella que supondra los accesos a memoria.Los procesadores vectoriales registro-registro disponen de uno o ms bancos de registros vectoriales que hagan de memoria intermedia.

Procesadores VectorialesProcesadores Vectorial:memoria-memoria

Proceso Vectorial: registro-registro

Son otro tipo de mquinas que se suelen considerar MISD. En un array sistlico hay un gran nmero de elementos de proceso idnticos con una limitada memoria local. Los elementos de proceso colocados en forma de matriz (array) de manera que slo estn permitidas las conexiones con los elementos de proceso vecinos. El adjetivo sistlico viene precisamente del hecho de que todos los procesadores vienen sincronizados por un nico reloj que hace de corazn que hace moverse a la mquina.

Arrays sistlicosHay formas de explotar el paralelismo: Paralelizacin de cdigo que se consigue con las mquinas de tipo MIMD.Paralelizacin de los datos conseguidas con arquitecturas SIMD y MISD. En ocasiones es necesario utilizar tanto el paralelismo de control como el de datos.Los procesadores que tienen caractersticas MIMD y SIMD a un tiempo, pueden resolver de forma efectiva un elevado rango de problemas.

Arquitecturas hbridasLas arquitecturas especficas son muchas veces conocidas tambin con el nombre de arquitecturas VLSI ya que muchas veces llevan consigo la elaboracin de circuitos especficos con una alta escala de integracin.Un ejemplo de arquitectura de propsito especfico son las redes neuronales y los procesadores basados en lgica difusa.

Arquitecturas EspecficasEl problema de la coherencia cach en multiprocesadores surge por las operaciones de escritura. Ejemplo: secuencia de operaciones de acceso a memoria (1,2,3,4,5) realizadas por tres procesadores P1, P2, P3 sobre la posicin de memoria u.Cach con poltica write-through.Cach con poltica writeback.Problema de coherencia cach

Existen dos formas de abordar el problema de la coherencia cach.Software, lo que implica la realizacin de compiladores que eviten la incoherencia entre datos de cach compartidos.Hardware, que mantengan de forma continua la coherencia en el sistema, siendo adems transparente al programador.

Solucin de la coherencia cach