Download Tema 4. - Departamento de Tecnología Electrónica

Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Parte 2.- SISTEMAS PARALELOS
Tema 4.- INTRODUCCIÓN A LAS ARQUITECTURAS PARALELAS.
INDICE
La carrera en busca de las altas velocidades .......................................................................................................................... 2
Limitaciones de la tecnología ............................................................................................................................................ 2
La arquitectura de los ordenadores y las altas velocidades................................................................................................ 2
Capitulo 4.1.- PARALELISMO EN LOS GRANDES MONOPROCESADORES.............................................................. 3
Arquitectura pipe-line ........................................................................................................................................................ 3
Organización seudo-pipe-line de la memoria central..................................................................................................... 3
Las máquinas pipe-line ...................................................................................................................................................... 4
Problemas de paralelismo en los computadores pipe-line. ................................................................................................ 5
Control del flujo de informaciones. ............................................................................................................................... 5
Conflictos de paralelismo. ............................................................................................................................................. 5
Resumen acerca de las dificultades de paralelismo. ...................................................................................................... 7
Descripción general de un ordenador pipe-Iine. ............................................................................................................ 8
Gestión de la memoria central ......................................................................................................................................... 11
Bifurcación de las informaciones leídas en la memoria............................................................................................... 11
Gestión de los conflictos de acceso al nivel de los bancos de memoria. ..................................................................... 11
Gestión de las prioridades de acceso a la memoria...................................................................................................... 12
Gestión de los problemas de dependencia. .................................................................................................................. 12
Gestión de la pila de instrucciones................................................................................................................................... 15
Funcionamiento normal de la pila de instrucciones. .................................................................................................... 15
Discontinuidades en el funcionamiento de la pila........................................................................................................ 15
Gestión de una unidad aritmética: el algoritmo de Tomasulo.......................................................................................... 16
Descripción del algoritmo de Tomasulo. ..................................................................................................................... 18
El futuro de la arquitectura pipe-Iine ............................................................................................................................... 19
Capitulo 4.2.- CLASIFICACION DE LAS ARQUITECTURAS DE COMPUTADOR PROPUESTA POR FLYNN ..... 20
La arquitectura SISD ................................................................................................................................................... 20
La arquitectura SIMD .................................................................................................................................................. 21
La arquitectura MISD .................................................................................................................................................. 21
La arquitectura MIMD................................................................................................................................................. 22
Capitulo 4.3.- SUPERCOMPUTADORES VECTORIALES Y SIMD .............................................................................. 23
Supercomputadores vectoriales: .................................................................................................................................. 23
Supercomputadores SIMD – Matriciales ..................................................................................................................... 24
Configuraciones de procesadores matriciales. ............................................................................................................. 25
Capitulo 4.4.- Multiprocesadores y Ordenadores Paralelos MIMD .................................................................................... 27
Multiprocesadores de memoria compartida:.................................................................................................................... 27
Modelo UMA:.............................................................................................................................................................. 27
Modelo NUMA............................................................................................................................................................ 28
Modelo COMA ............................................................................................................................................................ 31
Multicomputadores de memoria distribuida: ................................................................................................................... 32
ETSII – Dpto. Tecnología Electrónica.
Página: 1 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
La carrera en busca de las altas velocidades
En los grandes centros de cálculo científico las necesidades en cálculo crecen extremadamente rápido.
No es raro observar que se multiplica por dos cada uno o dos años.
¡A potencia constante, sería preciso duplicar el número de máquinas cada año o cada dos años!
Tal crecimiento de las necesidades corre el riesgo de verse aún acelerado por la puesta a punto, durante los
próximos años, de modelos biológicos, ecológicos, económicos o sociológicos muy complejos, exigiendo el
procesamiento de un número elevadísimo de ecuaciones simultáneas.
Actualmente dos vías presentan interesantes perspectivas a la hora de abordar los problemas ligados a la
arquitectura de las máquinas de gran potencia:
(1) la de la arquitectura pipe-Iine, que se basa en el concepto de anticipación que permite aumentar
considerablemente la potencia de una unidad central,
(2) la de las arquitecturas paralelas que, en muy primera aproximación, consiste en hacer trabajar
simultáneamente a varios procesadores.
El aumento de potencia puede buscarse en dos niveles: en el de la tecnología, o en el de la lógica.
Limitaciones de la tecnología
Los progresos de la tecnología han causado mejoras muy importantes en cuanto a la velocidad y rendimiento de
los ordenadores, a lo largo de los primeros veinte años de informática.
Ahora bien, en la actualidad parece vacilarse en esta progresión.
Cualesquiera que sean las tecnologías empleadas, se tropezará con una limitación, muy sensible ya en los
grandes ordenadores de hoy; se trata de la velocidad de propagación de los impulsos eléctricos en los
conductores que, habida cuenta de las leyes de la relatividad, está limitada a 300.000 Kms por segundo.
Dicho de otra manera, un, impulso eléctrico recorre como máximo 30 centímetros en un nanosegundo.
Si las máquinas poseen ciclos del orden de diez nanosegundos Æ ¡lo que limita la longitud total de hilo recorrido a
alrededor de un metro!
La arquitectura de los ordenadores y las altas velocidades
Por consiguiente, es del lado de la organización lógica de las máquinas de donde puede esperarse ganar en el
terreno de las velocidades. Puesto que las limitaciones tecnológicas nos impiden ganar tiempo en la ejecución de
las operaciones elementales, la única salida consiste en encontrar la forma de ejecutar en paralelo varías
operaciones elementales.
El paralelismo puede buscarse:
(1) al nivel de las máquinas de una sola unidad central, también llamadas monoprocesadores, que ejecutan
un solo programa a la vez.
(2) al nivel de las máquinas de varias unidades centrales, también llamadas multiprocesadores, que realizan
varios programas independientes en paralelo;
(3) al nivel de máquinas paralelas, en las que varios procesos de tratamiento, dependientes unos de otros,
se desarrollan simultáneamente.
ETSII – Dpto. Tecnología Electrónica.
Página: 2 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Capitulo 4.1.- PARALELISMO EN LOS GRANDES MONOPROCESADORES
Arquitectura pipe-line
Básicamente, diremos que una unidad es del tipo pipe-line cuando le podemos exigir que se encargué de una
nueva operación cada θ nanosegundos, mientras que, de hecho, cada operación dura nθ nanosegundos.
Por tanto, en el plano de los rendimientos globales, las cosas suceden corno si la unidad ejecutase una operación
cada θ nanosegundos.
Esto es, las operaciones se empujan unas a otras de sección en sección, a semejanza del correr de un fluido en
una tubería (pipe-Iine); de ahí el nombre asignado a este tipo de operador.
Organización seudo-pipe-line de la memoria central.
¡Está claro que no se trata de realizar una memoria con estructura estrictamente pipe-Iine!, en cambio, puede
organizarse de suerte que, vista desde fuera, se comporte como tal.
La idea consiste en dividir la memoria en bloques físicos independientes, llamados bancos.
Se escoge el número de bancos superior a n (corrientemente 16 ó 32).
Después de haber sido referenciado, cada banco queda indisponible, durante todo el ciclo de memoria, nθ .
Por consiguiente, cualquier nueva referencia a este mismo banco deberá ser puesta en espera hasta que éste se
libere. Sin embargo, la memoria aceptará una nueva petición a cada batido θ , en la medida que se refiera a un
bloque libre.
ETSII – Dpto. Tecnología Electrónica.
Página: 3 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Así, bajo la hipótesis de que el número de bancos sea superior al de batidos por ciclo de memoria, y de que las
referencias sucesivas sean seleccionadas de manera a evitar conflictos de acceso a un mismo banco, la memoria
se comporta, vista desde afuera, como un operador pipe-Iine capaz de lanzar una nueva operación a cada batido.
En el plano del direccionamiento, la memoria está organizada lógicamente de forma que las direcciones sucesivas
se encuentren en bancos sucesivos, en tales condiciones, se comporta la memoria como un operador pipe-Iine
cada vez que se direccionan células consecutivas de memoria.
Las máquinas pipe-line
El concepto de máquina pipe-Iine es una generalización, al nivel del conjunto de la computadora.
En realidad, las máquinas pipe-line se alejan relativamente de este principio por varias razones:
(1) no puede definirse un solo flujo de informaciones susceptible de atravesar continuamente el ordenador.
Es preciso tener en cuenta el flujo de las instrucciones y el de los operandos, que deben frecuentemente
esperarse uno al otro;
(2) la existencia de operadores aritméticos específicos implica que los flujos de informaciones se subdividen a
lo largo de su transición por la máquina, en función del tipo de operación pedido;
(3) los operadores no son todos estrictamente pipe-Iine.
Tal es el caso de la memoria central que, como acabamos de ver, no se comporta de forma pipe-Iine más
que si las informaciones sucesivamente referenciadas han sido previamente almacenadas en bloques
distintos. De no ser así, se producen esperas;
(4) las operaciones sucesivas no siempre son independientes, pues el resultado de una operación puede ser
operando para la siguiente operación, la cual, por consiguiente, deberá esperar a que haya concluido la
primera antes de iniciar su ejecución.
En las máquinas pipe-Iine distinguiremos dos niveles de ciclos:
• el ciclo de máquina o ciclo menor, que corresponde al θ de reloj de los operadores pipe-Iine, y
• el ciclo de memoria, a veces denominado ciclo mayor.
A cada ciclo menor debería poder inicializarse una instrucción.
En realidad, debemos consignar esta condición como un límite ideal por razón de todos los incidentes de recorrido
que alteran el funcionamiento pipe-Iine.
ETSII – Dpto. Tecnología Electrónica.
Página: 4 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Problemas de paralelismo en los computadores pipe-line.
Este tipo de paralelismo exige una división de la máquina en unidades funcionales, cada una responsable
de una o varias etapas del desarrollo de uno o varios tipos de instrucciones.
El funcionamiento de una máquina así organizada no deja de plantear un cierto número de problemas, que
podemos clasificar en dos categorías:
¾
¾
el control y la bifurcación del flujo de informaciones, por un lado,
la detección y regulación de los conflictos de paralelismo, por otro.
Control del flujo de informaciones.
Se realiza asociando a cada información transferida de una unidad a otra un indicador, especificando la operación
por efectuar sobre dicha información, y designando su destino posterior.
A la salida de una unidad, un dispositivo especial decodifica los indicadores y crea las ramificaciones a
otras unidades.
Conflictos de paralelismo.
El paralelismo en las máquinas pipe-Iine está restringido por causa de dos categorías de conflicto:
(1) Conflictos de acceso.
Se encuentran de dos tipos:
a) Acceso a una unidad no pipe-line que se halla ocupada por una demanda anterior (por ejemplo, dos
accesos sucesivos a un mismo banco de memoria).
Esta impone un estado de espera a la unidad precedente, lo que puede provocar un bloqueo de las
siguientes operaciones, a menos que se intercale entre ambas unidades una cola de espera de las
informaciones en tránsito;
b) Demandas simultáneas de acceso, una simultaneidad en las peticiones de acceso implica que varias
unidades pueden acceder a una unidad común.
Será preciso, entonces, disponer, además de posibles colas de espera, de dispositivos de gestión de las
prioridades.
ETSII – Dpto. Tecnología Electrónica.
Página: 5 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
(2) Conflictos de dependencia.
Un computador pipe-Iine es capaz de ejecutar simultáneamente varias instrucciones, incluso invertir su
secuencia normal de ejecución, a condición de respetar el encadenamiento lógico del programa.
Existe dependencia entre dos instrucciones, cuando ambas se refieran al mismo registro o a la misma
palabra de memoria, si al menos una de estas referencias implica una alteración del registro o de la
palabra de memoria.
Distinguiremos tres casos:
(a) Dependencia total: la 1ª instrucción debe estar completamente ejecutada antes de lanzar la 2ª.
Ejemplo:
(b) Dependencia parcial: la 1ª instrucción debe haber sido lanzada antes de almacenar el resultado de
2ª.
Ejemplo:
(c) Falsa dependencia: dos trozos de programas son falsamente dependientes, cuando no son
dependientes más que por la utilización común de un registro de, trabajo.
Ejemplos:
Obsérvese que, si se hubiera sustituido R1 por R2 en uno o en otro grupo de las tres instrucciones, ambos
grupos habrían podido ejecutarse simultáneamente (dejando aparte posibles conflictos de acceso).
No existe dependencia más que en virtud del uso del mismo registro de trabajo R1.
En resumen, una máquina pipe-Iine tiene que detectar necesariamente todos los casos de dependencia y
efectuar los oportunos bloqueos: bloqueo de las informaciones no actualizadas, con lo que las
instrucciones correspondientes a dichas informaciones deberán esperar el desbloqueo, y bloqueo de las
propias instrucciones que no podrán sobrepasar determinados estadios de su ejecución mientras no se
haya levantado aquél.
ETSII – Dpto. Tecnología Electrónica.
Página: 6 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Resumen acerca de las dificultades de paralelismo.
Las diferentes categorías de dificultades planteadas, así como las soluciones generales que se han venido
proponiendo son consignadas en el cuadro. Las próximas páginas traen numerosos ejemplos que aclararán las
distintas partes de este cuadro.
ETSII – Dpto. Tecnología Electrónica.
Página: 7 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Descripción general de un ordenador pipe-Iine.
A continuación se describe de la manera más sucinta el funcionamiento de una máquina pipe-Iine.
ETSII – Dpto. Tecnología Electrónica.
Página: 8 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
El ejemplo del Super-Superabacus está muy inspirado en el IBM 360-91.
Muy esquemáticamente, nuestro ejemplo de ordenador está dividido en cuatro grandes unidades:
(1) la memoria central entrelazada sobre un número de bancos congruente con el número de ciclos
menores por ciclo de memoria y con el dispositivo que controla los accesos a esta memoria.
(2) la unidad de instrucción, que comporta una cola de espera para las instrucciones provenientes de la
memoria, los registros de direccionamiento, una unidad de cálculo de dirección, una unidad de
predecodificación de las instrucciones y una unidad de decodificación y de ejecución de las instrucciones
de organización de programa;
(3) y (4) una unidad para las operaciones aritméticas filas y otra para la aritmética flotante.
La unidad flotante comprende una cola de espera de las instrucciones flotantes y el decodificador asociado,
registros de espera para los operandos flotantes provenientes de la memoria, los registros aritméticos
flotantes y los operadores flotantes todos del tipo pipe-Iine.
ETSII – Dpto. Tecnología Electrónica.
Página: 9 / 32
MSA
Sistemas de Multiprocesamiento
ETSII – Dpto. Tecnología Electrónica.
INTRODUCCION ARQUITECTURAS PARALELAS
Página: 10 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Vamos a analizar sucesivamente:
¾
la gestión de los accesos a memoria,
¾
la gestión de la unidad de instrucción y
¾
la gestión de una unidad aritmética,
interesándonos especialmente por el control del flujo de informaciones y por la solución de los conflictos de
paralelismo.
Gestión de la memoria central
Supondremos que disponemos de una memoria central entrelazada sobre un número de bancos netamente
superior al cociente ciclo memoria / ciclo menor.
Comprende tres buses de acceso: un bus para las direcciones, un bus de lectura y un bus de escritura.
Por cada ciclo menor puede solicitarse una nueva referencia a memoria.
La dirección correspondiente es enviada simultáneamente a todos los bancos de memoria por intermedio del bus
de direcciones. El banco que se reconozca lanzará un ciclo de memoria excepto si hubiera conflicto de acceso.
El acceso a la memoria plantea numerosos problemas:
¾ la bifurcación de las informaciones leídas en la memoria;
¾ la gestión de los conflictos de acceso (conflictos al nivel de un banco o al nivel del conjunto de la
memoria);
¾ la gestión de los conflictos de dependencia.
Bifurcación de las informaciones leídas en la memoria.
El problema reside en dirigir toda información leída en memoria hacia su unidad de destino.
A este fin, se asocia con cada dirección un indicador que designe la unidad destinataria.
En la solución del 360-91, los indicadores están insertos en una cola de espera, cuyos elementos descienden un
peldaño por cada ciclo menor.
La duración del recorrido es igual al tiempo de acceso a memoria, de suerte que el retorno de la información
procedente de la memoria esté sincronizado con la salida fuera de la cola del indicador asociado.
Gestión de los conflictos de acceso al nivel de los bancos de memoria.
Es preciso conservar, al nivel del controlador de memoria, las direcciones de las referencias que, aunque
aceptadas por el dispositivo de gestión de prioridades, no hayan podido ser atendidas por encontrarse ocupado el
banco direccionado.
El CDC 6600 resuelve este problema por una cola de espera, toda referencia enviada mediante el bus de
direcciones resulta simultáneamente introducida en un conjunto de registros, si encuentra ocupado se introduce
nuevamente la dirección en el bus con vistas a otro intento.
ETSII – Dpto. Tecnología Electrónica.
Página: 11 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
En el 360-91 no se envían sobre el bus de direcciones más que las referencias que serán aceptadas.
El resto se almacena en un conjunto de registros tampón y se presentarán sobre el bus en el momento que el
banco direccionado quede libre.
Para detectar si una dirección puede ser aceptada, se necesita disponer de una tabla de las direcciones de
bancos ocupados que pueda ser comprobada por vía asociativa en cada ciclo menor.
Gestión de las prioridades de acceso a la memoria.
La unidad de acceso a memoria recibe demandas procedentes:
(1) de la unidad de instrucción, que pide lecturas de instrucción;
(2) de la unidad de cálculo de dirección, para las lecturas o escrituras de operandos;
(3) de los canales,
(4) además, no pueden olvidarse aquellas que vienen de la cola de las demandas de referencia a memoria
enfrentadas a conflictos tales como el de banco ocupado, etc.
Gestión de los problemas de dependencia.
Se corre el riesgo de encontrarse ante un problema de dependencia si a una petición de escritura le sigue una de
lectura en la misma dirección o viceversa.
El problema se solventa por el procedimiento expeditivo de prohibir la introducción de una referencia en lectura
(respectivamente, escritura) proveniente de la unidad central, si ya existe una referencia en escritura
(respectivamente, lectura) recirculando.
ETSII – Dpto. Tecnología Electrónica.
Página: 12 / 32
MSA
Sistemas de Multiprocesamiento
ETSII – Dpto. Tecnología Electrónica.
INTRODUCCION ARQUITECTURAS PARALELAS
Página: 13 / 32
MSA
Sistemas de Multiprocesamiento
ETSII – Dpto. Tecnología Electrónica.
INTRODUCCION ARQUITECTURAS PARALELAS
Página: 14 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Gestión de la pila de instrucciones
Al principio, la pila está vacía (en el arranque de la máquina e inmediatamente después de las discontinuidades).
Las búsquedas de instrucciones son prioritarias respecto de las búsquedas de operandos en tanto la pila esté
incompleta.
Funcionamiento normal de la pila de instrucciones.
En funcionamiento normal, la instrucción en curso de predecodificación ocupa siempre la misma posición de la
pila, que desciende un peldaño cada vez que se pasa a la decodificación de la siguiente palabra.
Se escoge la posición del registro que contiene las instrucciones en curso de predecodificación de forma que
pueda cargarse adelantadamente con un número suficiente de instrucciones para ahorrar al predecodificador toda
espera.
Además siempre es interesante conservar instrucciones ya ejecutadas.
La pila se gestiona por medio de tres registros, que contienen respectivamente:
(1) la dirección en memoria de la palabra almacenada en el primer registro de la pila.
(2) la dirección en memoria de la palabra en curso de decodificación;
(3) la dirección en memoria de la palabra almacenada en el último registro de la pila.
Discontinuidades en el funcionamiento de la pila.
Aparte de las interrupciones, que no abordaremos aquí, se distinguen cuatro casos de discontinuidades:
1) Almacenamiento en una dirección de memoria cuyo contenido está cargado en la pila.
2) Salto incondicional
Salvo que el salto incondicional sea a una instrucción cargada en la pila, ésta debe ser reinicializada.
3) Salto condicional
Mientras no se haya comprobado la condición, no es posible saber si el salto se producirá o no.
Se utilizan módulos de predicción de bifurcaciones condicionales.
4) Procesamiento de bucles de pequeña longitud
Cuando hay salto hacia atrás de menos de n posiciones, siendo n la altura de la pila de instrucciones, se
supone que es un bucle.
Se desplaza la pila de instrucciones hasta conseguir que contenga al bucle completo y se posiciona la
unidad de instrucción en modo bucle, con lo cual la pila permanece estática mientras no se salga del
bucle.
ETSII – Dpto. Tecnología Electrónica.
Página: 15 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Gestión de una unidad aritmética: el algoritmo de Tomasulo
El algoritmo de Tomasulo permite explotar de forma muy eficaz una unidad aritmética dotada de operadores
aritméticos pipe-Iine.
Esta unidad comprende:
(1) una cola de espera de instrucciones flotantes salidas de la unidad de instrucción;
(2) registros de espera para los operandos provenientes de la memoria central;
(3) una cola de espera de operandos por almacenar en memoria central,
(4) los registros aritméticos flotantes direccionables;
(5) los operadores pipe-Iine (uno para suma-sustracción, uno para multiplicación-división).
Una instrucción flotante puede verse bloqueada en tres hipótesis de conflicto:
(1) el operador correspondiente no está libre;
(2) el operando salido de la memoria no ha llegado aún a los registros tampón;
(3) uno de los registros de la operación se está utilizando como primer operando en una operación anterior
aún no concluida.
En las descripciones que siguen dedicaremos toda nuestra atención al tercer tipo de conflicto que es, con mucho,
el más interesante. A posteriori verificaremos que los algoritmos descritos resuelven también los dos primeros.
ETSII – Dpto. Tecnología Electrónica.
Página: 16 / 32
MSA
Sistemas de Multiprocesamiento
ETSII – Dpto. Tecnología Electrónica.
INTRODUCCION ARQUITECTURAS PARALELAS
Página: 17 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Descripción del algoritmo de Tomasulo.
Lo explicitaremos sobre un ejemplo sencillo:
Se supone que, para empezar, no están bloqueados los registros R1, R 2 y R3.
Fase 1: decodificación de la primera suma. El decodificador:
(1) Comprueba que hay disponible una estación tampón del sumador y la reserva; sea ES1 esta estación;
(2) prueba el dígito de bloqueo y comprueba que el contenido de R1 es válido;
(3) envía el contenido de R1 a la parte origen/destino de la estación ES1 y el contenido de R2 a la otra parte
de ES1
(4) pone a 1 el bit de bloqueo de R1 para evitar que una próxima instrucción utilice el valor actual de R1;
(5) posiciona el prefijo de R1 con la insignia indicando a la estación ES1, para significar que el resultado de la
operación procedente de ES1 debe almacenarse en R1.
Estando ya cargados los dos operandos en ES1 puede desencadenarse la ejecución de la suma.
Fase 2: decodificación de la segunda suma:
(1) comprueba qué hay una estación disponible ante el sumador; por ejemplo ES2;
(2) prueba el bit de bloqueo del registro R1 y comprueba que está a 1;
(3) en tales circunstancias, no envía el contenido del registro R1 a la posición origen/destino de la estación
tampón ES1 sino que:
(4) copia la insignia contenida en el prefijo de R1 en el prefijo asociado con el primer operando de la estación,
para indicar el origen efectivo del primer operando (que es el resultado de la primera suma caracterizada
por la estación tampón ES1)
(5) carga sobre el prefijo asociado con R1 la insignia de la estación ES2 para indicar que el resultado de esta
segunda suma debe ser almacenado en R1
(6) no modifica el bit de bloqueo de R1
El decodificador queda libre para ocuparse de la próxima instrucción.
ETSII – Dpto. Tecnología Electrónica.
Página: 18 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Fase 3: Ejecución de la primera suma.
La primera suma ha empezado a ejecutarse en cuanto que se han cargado los dos operandos sobre ES1.
Una vez obtenido el resultado, la estación ES1 pondrá a cero sus propios prefijos, al tiempo que envía al
bus común:
(1) la insignia ES1 indicativa de la estación emisora y
(2) el resultado de la suma.
La insignia en circulación sobre el bus común es distribuida a todos los registros destinatarios, que la
comparan asociativamente con el contenido de sus propios prefijos.
En nuestro ejemplo existe coincidencia entre la insignia transportada por el bus y el prefijo asociado al
primer operando de la estación tampón ES2. Por consiguiente, el resultado es muestreado en el
correspondiente registro de esta estación, mientras que el prefijo es repuesto a cero (no deje de
observarse que si no hubiera sido decodificada la segunda suma, el resultado habría sido almacenado en
el registro R1)
Fase 4. Ejecución de la segunda suma.
La estación tampón ES2, al disponer ya de los dos operandos, puede lanzar la segunda suma, cuyo
resultado se enviará sobre el bus común acompañado de la insignia ES2.
Se producirá coincidencia con el registro R1, en donde se almacenará el resultado.
El bit de bloqueo y el prefijo del registro R1 serán repuestos a cero.
Obsérvese esencialmente que el resultado de la primera suma no ha sido cargado en R1, sino
directamente en el sumador para ejecutar la segunda suma.
El futuro de la arquitectura pipe-Iine
Resulta difícil pronosticar cual será el porvenir de los potentes computadores pipe-Iine.
Las ideas de cara al futuro parecen orientarse hacia una reducción del hardware de control, dejando en manos del
software el control del aspecto pipe-Iine, actualmente muy costoso tanto en tiempo de ejecución como en cantidad
de circuitos, es decir, en precio.
ETSII – Dpto. Tecnología Electrónica
Página: 19 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Capitulo 4.2.- CLASIFICACION DE LAS ARQUITECTURAS DE COMPUTADOR
PROPUESTA POR FLYNN
Dicha clasificación divide a los computadores atendiendo a su paralelismo explícito en 4 grupos:
Flujo de Datos
Flujo de
Instrucciones
SISD
MISD
SIMD
MIMD
SISD: Flujo único de instrucciones-flujo único de datos.
SIMD: Flujo único de instrucciones-flujo múltiple de datos.
MISD: Flujo múltiple de instrucciones-flujo único de datos.
MIMD: Flujo múltiple de instrucciones-flujo múltiple de datos.
La arquitectura SISD
SISD Æ Single Instruction stream over a Single Data stream
Un único procesador interpreta una única secuencia de instrucciones para operar con los datos
almacenados en una única memoria principal.
Ordenador secuencial convencional de arquitectura Von Neuman
La memoria principal genera el flujo de instrucciones a la Unidad de Control, que tras decodificarlas e
interpretarlas, ordena su ejecución en la Unidad Operativa compuesta por la ALU y los registros internos de
trabajo.
Esquemáticamente se representa en la figura y corresponde a la mayoría de los sistemas monoprocesadores
actuales.
En el funcionamiento de los computadores SISD sólo hay una corriente de instrucciones unidireccional y
otra de datos bidireccional.
ETSII – Dpto. Tecnología Electrónica
Página: 20 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
La arquitectura SIMD
SIMD Æ Single Instruction stream over a Multiples Data stream (Multi-dimensionales)
La Unidad de Control extrae e interpreta las instrucciones y envía las correspondientes señales de control
a las Unidades Operativas encargadas de su ejecución.
Cada Unidad Operativa trabaja con un flujo de datos concreto, que se obtiene de una memoria compartida
compuesta por varios módulos.
En los computadores, con arquitectura SIMD la única Unidad de Control existente supervisa el funcionamiento del
conjunto de Unidades Operativas disponible.
La estructura corresponde a los llamados Procesadores Vectoriales y Matriciales equipados con hardware
escalar o vectorial.
La arquitectura MISD
MISD Æ Multiples Instruction stream over a Single Data stream
La estructura MISD 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.
Esta arquitectura es conocida como Matriz Sistólica para la ejecución en modo pipe-line de algoritmos
especiales (Coprocesadores / Funciones dedicadas).
Un computador MISID se asemeja a una superestructura segmentada en la que cada procesador realiza una
parte del procedimiento sobre el flujo de datos.
ETSII – Dpto. Tecnología Electrónica
Página: 21 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
La arquitectura MIMD
MIMD Æ Multiples Instruction stream over a Multiples Data stream.
Se trata de la estructura típica de un sistema multiprocesador, que puede definirse como un conjunto de
procesadores serie, cuyas unidades operativas soportan un flujo de datos y las unidades de control, un flujo de
instrucciones.
ETSII – Dpto. Tecnología Electrónica
Página: 22 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Capitulo 4.3.- SUPERCOMPUTADORES VECTORIALES Y SIMD
Supercomputadores vectoriales:
El procesador vectorial se conecta al procesador escalar para recibir las instrucciones.
Procesador Escalar
Pipeline de
Funciones
Escalares
Instrucciones Escalares
Procesador Vectorial
Instrucciones
Vectoriales
Unidad de Control
Escalar
Unidad de
Control
Vectorial
Señales de
Control
Instrucciones
Pipeline de Funciones
Vectoriales
Datos
Memoria Principal
Escalares ( Programas y Datos)
Datos
Vectoriales
Registros
Vectoriales
Pipeline de Funciones
Vectoriales
Ordenador
Host
Almacenamiento
Masivo
I/O (Usuarios)
Los programas y datos se cargan en memoria principal a través de una computadora Host.
Todas las instrucciones son en primer lugar decodificadas por la unidad de control escalar.
Si la instrucción descodificada es una operación escalar o una instrucción de control de programa, será
directamente ejecutada por el procesador escalar usando los pipeline funcionales escalares.
Si la instrucción descodificada es una operación vectorial, enviara el vector a la unidad de control vectorial.
Esta unidad de control vectorial supervisara el flujo de datos vectoriales entre la memoria principal y los pipeline
funcionales vectoriales.
Modelos de procesadores vectoriales :
Los registros vectoriales se utilizan para soportan los operadores vectoriales, los resultados intermedios y finales
La longitud de cada registro de vector es normalmente fija con componentes de 64 bits, un ejemplo es este tipo
son los CRAY. Las maquinas Fujitsu VP 2000 utilizan registro de vector reconfigurables para ajustar
dinámicamente la longitud del registro a la longitud del operando vectorial
ETSII – Dpto. Tecnología Electrónica
Página: 23 / 32
MSA
Sistemas de Multiprocesamiento
Modelo
Sistema
Familia
Convex
C 3800
Sistema
Digital
VAX 9000
Cray
Research
Y-MP y C-90
INTRODUCCION ARQUITECTURAS PARALELAS
Arquitectura Hardware Vectorial
Multiprocesador de tecnología GaAs.
8 procesadores con 500 MB.
1 GB de memoria principal
2 Gflops con operaciones concurrentes
escalar / Vectorial.
Procesamiento vectorial integrado en el
entorno VAX.
125 – 500 Mflops
Instrucciones vectoriales 63.
Registro vectorial 64x64x16
Y-MP : 2, 4, 6, 8 procesadores para
alcanzar hasta 2,67 Gflops
C-90 tiene 2 procesadores vectoriales
pipes con 16 Gflops
SO y Compilador
SO POSIX 1003.1
Compiladores de paralelismo
C Avanzado, Fortran y ADA paralelos.
SO ULTRIX
Depurador de programas vectorizados VVIEF ( VAX
Vector Instruction Emulator)
VAX Fortran
SO Berkeley BSD y UNIX/V
Compilador CF77 para vectorización automatica,
optimización escalar y procesamiento paralelo.
Supercomputadores SIMD – Matriciales
Unidad de Control
PE 0
PE 1
PE 2
PE N-1
Proc. 0
Proc. 1
Proc. 2
Proc. N-1
Mem. 0
Mem. 1
Mem. 2
Mem. N-1
Red de Interconexión
Modelo Sistema
MasPar
Computer
Corporation MP-1
Family
Arquitectura Hardware SIMD
Permite una configuración de 1024 a
16.384procesadores con 26.000
MPIS o 1.3 Gflops.
Cada PE es un procesador RISC con
16 KB de memoria local.
SO y Compilador
SO UNIX con X-Windows como interfase de usuario.
Fortran 77, MasPar Fortran y Lenguajes de aplicación
paralelo MasPar.
Depuradores, ...
Thinking
Machines
Corporation
CM-2
Active
Memory
Technology
DAP600 Family
Hasta 65.536 PEs con hasta 1Mbits
de memoria cada uno.
Pico de 28 Gflops y 5,6 Gflops
sostenidos
Hasta 4.096 PEs con hasta 1Kbits de
memoria cada uno.
Pico de 20 GIPS y 560 Mflops.
Dirigido por un VAX, Sun o Symbolics 3000
Fortran 90, C* y Compilador Lisp
ETSII – Dpto. Tecnología Electrónica
Página: 24 / 32
Dirigido por un VAX-VMS o UNIX
Fortran 77 , estándares de Fortran 90.
C, APAL sobre DAP
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Los procesadores segmentados array tienen una estructura de dos dimensiones, con múltiples cadenas de flujo
de datos para operaciones aritméticas de alto nivel, tales como producto de matrices, cálculo de la matriz inversa,
etc.
Este array tiene una estructura pipe-line de tres direcciones de flujo de datos, para la multiplicación de dos
matrices. Cada célula P efectúa una operación de producto interno aditivo.
Configuraciones de procesadores matriciales.
En la primera, cada PE se compone de una unidad lógico-aritmética (ALU) con sus registros de trabajo y una
memoria local (PEM) para guardar los datos.
La unidad de control tiene, además, su propia memoria de almacenamiento del programa que se ejecuta.
La CU decodifica las instrucciones y determina dónde han de ejecutarse.
Todos los PE ejecutan la misma función sincrónicamente.
Los operando vectoriales se envían a los PE antes de la ejecución, en paralelo. Hay un sistema de máscaras para
habilitar o deshabilitar cada uno de los PE, de forma que sólo trabajen los necesarios.
Para el intercambio de datos entre los diferentes PE, se emplea la red de interconexión controlada por la CU.
ETSII – Dpto. Tecnología Electrónica
Página: 25 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
El segundo tipo de configuración difiere del primero, en que no dispone de bloque de memoria para cada PE, sino
de un grupo de bloques de memoria (M) que son compartidos por el grupo de PE.
Por otra parte, no existe red de interconexión, pero sí red de alineamiento que conecta a los PE con las memorias.
Esta red es controlada, directamente, por la unidad de control.
ETSII – Dpto. Tecnología Electrónica
Página: 26 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Capitulo 4.4.- Multiprocesadores y Ordenadores Paralelos MIMD
Hay dos grandes clases de ordenadores paralelos :
-
Multiprocesadores de memoria compartida.
-
Multicomputadores de memoria distribuida
Las mayores diferencias entre Multiprocesadores y Multicomputadores esta en la Compartición de memoria y los
mecanismos de Comunicación Interprocesadores.
Los procesadores en un sistema multiprocesador se comunica con cada uno de los otros procesadores a través
de variables compartidas en un área de memoria común.
Cada computador en un sistema multicomputadores tiene una memoria local no compartida, la comunicación
interprocesadores se realiza a través de mensajes pasando entre los ordenadores.
Multiprocesadores de memoria compartida:
Se distinguen 3 tipos :
- Modelo UMA – Acceso a Memoria Uniforme
- Modelo NUMA – Acceso a Memoria No Uniforme
- Modelo COMA – Arquitectura de Memoria Solo-Cache.
Estos modelos se distinguen en como la memoria y los recursos periféricos son compartidos o distribuidos.
Modelo UMA:
La memoria física es uniformemente compartida por todos los procesadores.
Todos los procesadores tienen igual tiempo de acceso a todas la palabras de memoria, esta es la razón por lo que
son llamadas computadoras de acceso uniforme a memoria.
Cada procesador debe usar un cache privado.
Los periféricos son también compartidos en algún modo.
Procesadores
P1
P2
PN
Bus de interconexión
I/O
SM1
GSM
SMM
Módulos de Memoria Compartida
Modelo UMA , EL Sequent Symmetry S-81
Los multiprocesadores de memoria compartida son denominados sistemas altamente acoplados debido al alto
grado de compartición de recursos.
ETSII – Dpto. Tecnología Electrónica
Página: 27 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
La interconexión de los componentes del sistema se realiza por medio de un bus común.
La mayoría de los fabricantes de ordenadores tienen una extensión de multiprocesador (MP) de su línea de
productos uniprocesador (UP).
El modelo UMA es usado en actividades de propósito general y aplicaciones de tiempo compartido multiusuarios.
Puede ser usado para aumentar la velocidad de ejecución en programas de aplicaciones de tiempo crítico.
Para coordinar estos eventos paralelos, la sincronización y comunicación entre procesadores se realiza mediante
el uso de variables compartidas en la memoria común.
Cuando todos los procesadores tienen igual acceso a todos los dispositivos periféricos el sistema es denominado
multiprocesador simétrico. En este caso todos los procesadores son igualmente capaces de ejecutar programas
como puedan ser SO y subrutinas de servicios I/O.
En un multiprocesador asimétrico solo uno o un subconjunto de procesadores tienen capacidad de ejecución.
Un procesador maestro puede ejecutar la operación del sistema y gestionar los dispositivos I/O.
El resto de los procesadores no tienen capacidad para gestionar los dispositivos I/O y consecuentemente se
denominan procesadores agregados (APs).
Los procesadores agregados ejecutan los códigos del usuario bajo la supervisión del procesador maestro.
El Sequent Symetry S81 pertenece a una clase llamada como mini-superordenadores.
Es un multiprocesador de procesamiento transaccional compuesto por 30 microprocesadores i386 conectados a
un bus troncal común.
En 1991 se paso a i486 y en la actualidad a i586.
Software: SO DENIS
Los modelos IBM System 390 son Mainframe, algunas veces llamados casi-superordenadores.
Es un multiprocesador de procesamiento transaccional en tiempo real pero no de tiempo critico.
Los modelos IBM ES/9000 VF en los últimos modelos de mainframes con 6 procesadores con prestaciones
vectoriales, canales I/O cruzados de fibra óptica y memoria compartida.
Software de SO soportados: MVS, AIX, Fortran paralelo
Modelo NUMA
Un sistema multiprocesador NUMA es un sistema de memoria compartida que está físicamente distribuida a todos
los procesadores, esta memoria se llama memoria local.
El tiempo de acceso varía con la localización de la palabra en memoria.
El conjunto de todas estas memorias locales forman un espacio global de direcciones accesible por todos los
procesadores.
Es mas rápido acceder a una memoria local con un procesador local.
El acceso a la memoria remota por otros procesadores es mas lento, toma mas tiempo por el tiempo añadido en el
acceso a la red de interconexión.
ETSII – Dpto. Tecnología Electrónica
Página: 28 / 32
MSA
Sistemas de Multiprocesamiento
LM1
INTRODUCCION ARQUITECTURAS PARALELAS
P1
GSM
LM2
P2
Red de
Interconexión
I/O
LMN
PN
Modelo NUMA , EL BBN TC-2000 Butterfly
Además de las memorias distribuidas puedes añadir memoria global compartida a este sistema multiprocesador.
En este caso tenemos 3 modelos de acceso a memoria .... de los cuales el mas lento será el acceso a memoria
remota
CLUSTER
Un multiprocesador estructurado jerárquicamente.
Los procesadores se dividen en varios cluster, cada cluster en si mismo un multiprocesador UMA o NUMA.
Los cluster están conectados a módulos de memoria compartida global.
El sistema completo es considerado un multiprocesador NUMA.
ETSII – Dpto. Tecnología Electrónica
Página: 29 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
I/O
GSM
GSM
GSM
Red Global de Interconexión
P1
P2
ICN
PN
CSM1
P1
CSM2
P2
CSMX
PM
CLUSTER-1
CSM1
ICN
CSM2
CSMY
CLUSTER-P
Modelo NUMA Cluster jerárquico ,El sistema Cedar de la universidad den Illinois
Todos los procesadores pertenecientes al mismo cluster pueden acceder a los módulos de memoria compartida.
Todos los cluster tienen igual acceso a los módulos de memoria global, entonces el tiempo de acceso a la
memoria cluster es menor que la memoria global.
Puede incluso darse el acceso a memoria intercluster, que seria el mas lento.
El BBN TC-2000 representa un clase MPP. Æ 20 millones de MIPS.
Puede ser configurado para alcanzar los 512 procesadores M88100 interconectados por la red Batterfly
multiestados.
Esta diseñado como un NUMA para aplicaciones de tiempo real y tiempo critico.
Software : SO MAC y Fortran paralelo.
ETSII – Dpto. Tecnología Electrónica
Página: 30 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Modelo COMA
Un multiprocesador COMA consiste en un sistema que utiliza solo memoria cache.
Es un caso especial de la maquina NUMA, en el cual las memorias principales distribuidas están convertidas a
caches.
No hay jerarquía de memoria en cada procesador.
Todos los caches forman un espacio global de direcciones.
El acceso a caches remotos es asistido por el directorio de caches distribuidos.
Dependiendo de la red de interconexión usada, a veces directorios jerárquicos deben de ser usados para localizar
copias de bloques cache.
El lugar inicial de los datos no es critico porque los datos pueden moverse a donde van a ser usados.
Red de Interconexión
D
D
D
C
C
C
P
P
P
P = Procesador
C = Cache
D = Directorios de cache
Æ Los sistemas de multiprocesador son utilizados para propósito generales en aplicaciones multiusuario donde la
programación es la mayor preocupación.
El mayor defecto de los multiprocesadores es su carencia de escalabilidad.
En la construcción de sistemas MPP, los sistemas de multicomputadores de memoria distribuidas son mas
escalables pero menos programables debido a los protocolos de comunicación añadidos.
ETSII – Dpto. Tecnología Electrónica
Página: 31 / 32
MSA
Sistemas de Multiprocesamiento
INTRODUCCION ARQUITECTURAS PARALELAS
Multicomputadores de memoria distribuida:
El sistema consiste en múltiples computadores, llamadas nodos, conectadas a través de una red interconexión de
paso de mensajes.
La red de paso de mensajes proporciona conexiones estáticas punto a punto entre los nodos.
Todas las memorias locales son privadas y accesibles solo por su procesador local.
Por esta razón los multicomputadores tradicionales han sido llamadas computadoras de acceso no remoto a
memoria NORMA ( NO Remote Memory Access).
Red de Interconexión de paso de mensaje
P
P
M
M
P
M
Sin embargo, estas restricciones son gradualmente eliminadas en los futuros multicomputadores con
memorias compartidas distribuidas y redes dinámicas de interconexión.
Los modernos multicomputadores utilizan router, es el elemento físico encargado de discernir cual es el camino
mas adecuado para la transmisión de mensajes entre los nodos de una red compleja.
El router de cabecera debe tener conectados los periféricos y dispositivos I/O.
Tipos mixtos de nodos pueden combinarse en multicomputadores heterogéneos.
Las comunicaciones internodos se realizan con representaciones de datos compatibles y protocolos de paso de
mensajes.
Se distinguen 3 generaciones de multicomputadores :
1 Generación Æ Arquitectura hipercubo Æ Intercambio de mensajes controlado por software
2 Generación Æ Arquitectura conectada en malla Æ Intercambio de mensajes controlado por hardware
con Router
3 Generación Æ Chip VLSI.
Multicomputadores representativos :
Intel Paragon XP / S
- Nodos y Memoria : i860 XP – 50 MHz, 16 -128 MB por nodo, Nodos especializados de I/O.
- Red y I/O : Malla en 2-D con SCSI, Ethernet
- SO y Soporte paralelismo : OSF y Soporte de programación y visualización
- Aplicaciones : Computación estratégica, manipulación de datos en paralelo.
- Prestaciones : 5 – 300 Gflop, 2,8 – 160 GIPS
nCUBE / 2 6480
- Nodos y Memoria : Cada nodo contienen una CPU CISC 64 bits con 14 puertos DMA de 1 – 64 MB
por nodos
- Red y I/O : Red hipercubica de 13 dimensiones con 8192 nodos, memoria de 512 GB y 64 tarjetas
para dispositivos I/O.
- SO y Soporte paralelismo : Vertex y UNIX que soportan intercambio de mensajes usando routing.
- Aplicaciones : Procesamiento de Bases de Datos,
- Prestaciones : 27 Gflop y 36 Gbits de I/O que permiten construir una maquina aun mas grande.
Parsys Ltd SuperNode 1000
- Nodos y Memoria : Superndo construido con multiples T-800
- Red y I/O : Interconexión reconfigurable y expandible hasta 1024 procesadores.
- SO y Soporte paralelismo : IDRIS y compatible con UNIX
- Aplicaciones : Académicas y científicas.
- Prestaciones : 200 MIPS – 13 GIPS.
ETSII – Dpto. Tecnología Electrónica
Página: 32 / 32
MSA