Indice

1. Introduccin. Demanda en la velocidad de clculo

2. Terminologa y taxonoma
2.1. Bajo nivel de paralelismo
2.2. Taxonoma de Flynn
2.3. Definicin de sistemas paralelos y distribuidos
2.4. Clasificacin de Johnson
2.5. Otras clasificaciones

3. Arquitecturas Sncronas
3.1. Procesadores vectoriales entubados
3.1.1 Principio de concurrencia entubada
3.2. Arquitecturas SIMD
3.2.1 Matriz de procesadores
3.2.2Procesadores de memoria asociativa
3.3 Arquitecturas sistlicas de propsito general

4. Arquitecturas MIMD
4.1. El problema del diseo
4.2. Categoras de la arquitectura MIMD
4.2.1 Arquitecturas de memoria distribuida
4.2.2 Arquitecturas de memoria compartida
4.3 Granuralidad
4.4 Balanceo de carga
5. Redes de ordenadores, como una plataforma de computacin por paso de
mensajes (message-passing)
5.1 Conceptos bsicos de programacin con paso de mensajes
5.2 Creacin del proceso
5.3 Paso sncrono de mensajes
5.4 Paso de mensajes Blocking y Nonblocking
5.5 Broadcast, gather y scatter
5.6 Utilizando clusters de estaciones de trabajo
5.7 PVM
5.7.1 Creain y ejecucin de procesos
5.7.2 Rutinas bsicas de mensajes

16

25

5.8 MPI
5.8.1 Creacin y ejecucin de procesos
5.8.2 Utilizando el modelo computacional SPMD
5.8.3 Las rutinas de paso de mensajes
5.8.4 Comunicacin punto a punto
5.8.5 Conclusin
5.8.6 Rutinas de tipo Blocking
5.8.7 Rutinas de tipo Nonblocking
5.8.8 Modos de comunicacin de envo
5.8.9 Comunicacin colectiva
Bibliografa

34

1. Introduccin. (Demanda en la Velocidad de Clculo)

1L

Un ordenador en paralelo no es una idea nueva, de hecho es muy vieja. Por ejemplo,
Gill escribe a cerca de la programacin en paralelo en 1958. Holland lo hace a cerca de un
ordenador capaz de ejecutar un nmero arbitrario de subprogramas de manera simultanea,
en 1959. Conway, describe el diseo de un ordenador paralelo y su programacin en 1963.
Y as sucesivamente hasta nuestros das.
Existen problemas que exigen enormes clculos repetitivos, sobre gran cantidad de
datos, para dar resultados slidos. Es el caso, de la simulacin de problemas cientficos y de
ingeniera. Los clculos deben de terminarse dentro de un perodo de tiempo razonable. Una
simulacin que tarde dos semanas, en alcanzar una solucin, es generalmente inaceptable en
un entorno de diseo. Hay problemas que tienen un tiempo preciso para su clculo (ejemplo,
predicciones meteorolgicas). Algunas como el modelado de grandes estructuras de DNA, o
la prediccin meteorolgica son prolemas denominados, de desafo elevado o grand
challange. En donde esta clase de problemas, son los que no pueden ser resueltos en una
cantidad de tiempo razonable por los ordenadores de hoy en da. Obviamente, un tiempo de
ejecucin de diez aos, es siempre poco razonable.
La prediccin del tiempo por ordenador, es un ejemplo que requiere poderosos
ordenadores. La atmsfera es modelada, al dividirla en regiones o celdas tridimensionales,
ms que utilizar complejas ecuaciones matemticas, para capturar los distintos efectos. En
esencia, las condiciones de cada celda (temperatura, presin, humedad, velocidad del viento
y direccin, etc ), son calculados en intervalos de tiempo utilizando diversas condiciones
existentes en el intervalo de tiempo anterior. La clave que hace esta simulacin significativa,
es el nmero de celdas. Los clculos de cada celda, son repetidos muchas veces para el
modelo durante el paso del tiempo.
Supongamos que consideramos una regin atmosfrica total, dividida en celdas de 1
milla cbica, con una altura de 10 millas, 10 celdas de altura. Un clculo estimado, nos
llevara a cerca de 5.108 celdas. Supongamos que cada clculo requiere 200 operaciones en
coma flotante. En un primer paso, seran necesarias 10 11 operaciones en coma flotante. Si
fusemos a pronosticar el tiempo sobre 10 das, utilizando intervalos de 10 minutos, haran
104 pasos, y 1015 operaciones en coma flotante en total. Un ordenador operando a 100
Mflops (108 operaciones en coma flotante por segundo), tardara 10 7 segundos, cerca de 100
das para desarrollar el clculo. Para desarrollar el clculo en 10 minutos, necesitaramos un
ordenador operando a 1.7 Tflops (1.7 x1012 operaciones en coma flotante por segundo).
Para finalizar, es humano buscar nuevas aplicaciones que exceden la capacidad de los
sistemas de clculo, y que requieren ms velocidad computacional que los actualmente
disponibles. Recientes aplicaciones como la inteligencia artificial, requieren considerale
velocidad computacional que los actualmente alcanzados en tiempo real.
Adems de obtener el potencial para incrementar la velocidad en un problema
existente, la utilizacin de mltiples ordenadores/procesadores a menudo permite, una
solucin ms precisa de un problema para resolverlo en una cantidad de tiempo razonable.
Una solucin multiprocesada, a menudo permitir un mayor nmero de puntos a ser
calculados en un tiempo dado, y obtener una solucin ms precisa.
Como es de suponer, no todos los problemas tienen una misma solucin en una
arquitectura paralelo en concreto. Sino que segn el tipo de problema, buscaremos una
arquitectura, que nos lo resuelva eficientemente.

2. Terminologa y taxonoma.

1A

La dificultad a la hora de definir, de manera exhaustiva, las arquitecturas paralelas, se

mezcla con el problema de realizar una taxonoma que incluya los modernos tipos de esta
clase de arquitecturas. A su vez, existe el hecho de que tienen que satisfacer cierto conjunto
de caractersticas, que siguidamente se relatan:
Excluir arquitecturas que incorporan mecanismos de bajo nivel de paralelismo, que ha
llegado a ser caracterstica comn de los ordenadores modernos.
Mantener los elementos de la taxonoma de Flynn, basada en cadenas de instrucciones y
datos.
Introduccin de los procesadores vectoriales de y otras arquitecturas, que intuitivamente
parecen merecer su inclusin dentro de las arquitecturas paralelas, y que se acomodan
difcilmente dentro de los esquemas de Flynn.
Examinemos cada uno de estas exigencias, para encontrar una definicin que
satisfaga todas aquellas, y suministre la base para realizar una clasificacin razonable.

2.1 Bajo nivel de paralelismo.

1A

Hay dos razones para excluir las mquinas que emplean solamente, el bajo nivel de
paralelismo del conjunto de arquitecturas paralelas. Primero el fracaso a la hora de adoptar
un standard ms riguroso, podra hacer de los ordenadores actuales, arquitecturas
paralelas, negando el valor del trmino. Las arquitecturas que solo tienen las caractersticas
descritas abajo, no ofrecen de manera explcita, el entorno de trabajo coherente para
desarrollar soluciones paralelas de alto nivel:
Instrucciones entubadas: Se define, a la descomposicin de la ejecucin de la
instruccin en una serie de pasos autnomos, permitiendo a cada uno de ellos, desarrollar
simultneamente un porcin del proceso de ejecucin, tal como descodificacin, clculo
efectivo de la direccin, obtencin del operando, etc.
Mltiples unidades funcionales dentro de la CPU: Para operaciones aritmticas y
booleanas que se ejecutan concurrentemente.
Separacin de la CPU, y procesadores de E/S: liberando la CPU, de las
responsabilidades del control de E/S, al utilizar procesadores de E/S dedicados.
Soluciones alcanzadas desde los simples controladores de E/S, a complejas unidades de
procesamiento de perifricos.
Aunque estas soluciones contribuyen, de manera significativa al desarrollo de la
ingeniera, su presencia no hace de un ordenador, una arquitectura paralela.

2.2 La Taxonoma de Flynn.

1A

La taxonoma de Flynn, clasifica las arquitecturas en cadenas, streams, sencillas o

mltiples de instrucciones y datos. Esto se desarrolla, en las categoras que seguidamente se
enumeran:
SISD: Instruccin simple, con cadena de datos simple. Los ordenadores con ejecucin de
programas en serie, son los que diariamente utilizamos. Es decir, no emplean paralelismo
explcito.
SIMD: Instruccin simple, con cadena de datos mltiple. Se refiere a mltiples
procesadores, ejecutando una misma instruccin sobre diferentes datos.
MISD: Instruccin mltiple con cadena de datos simple. Es el mbito de procesadores
mltiples, aplicando a un nico dato, instrucciones distintas. Esta hipottica posibilidad, se
juzga como impracticable. Lo que indica, que la clasificacin de Flynn, no es particularmente
efectiva. Aunque se podra incluir aqu, todas aquellas mquinas que se aplican a la hora de
intentar descifrar cdigos de encriptado. Distintos algoritmos de desincriptacin, aplicados a
un mismo dato a descifrar.
MIMD: Instruccin mltiple, con cadena de datos mltiple. Son mltiples procesadores,
ejecutando de manera autnoma diversas instrucciones sobre distintos datos.
Aunque estas distinciones, proporcionan una manera til y abreviada, de caracterizar
las arquitecturas paralelas, son insuficientes para clasificar los distintos nuevos ordenadores.
por ejemplo, los procesadores vectoriales entubados, merecen su inclusin como mquinas
paralelas, ya que muestran una sustancial ejecucin aritmtica concurrente, y pueden
manipular cientos de elementos de un vector en paralelo. Sin embargo, difcilmente se
acomodan dentro de la taxonoma de Flynn, porque carecen de procesadores que ejecuten la
misma instruccin en lockstep y carecen de la autonoma asncrona de la categora MIMD.

2.3 Definicin de sistemas paralelos y distribuidos.

Un primer paso para dar una clasificacin satisfactoria, es articular una definicin de
arquitecturas paralelas. En esta, se debera incluir los sistemas adecuados que el esquema de
Flynn no puede manejar, y excluir las arquitecturas incorporadas solamente con bajo nivel de
paralelismo.
Los sistemas paralelos, son aquellos que tienen las siguientes caractersticas:

 Varios procesadores, situados dentro de una pequea distancia unos de otros,

Tennenbaum en la ltima edicin de Computer Networks, incluso dice cuando
estn a menos de 10 metros.
Su propsito principal, es el de realizar en comn, una tarea computacional.
Tienen una tipologa de red fija.
Mientras que los sistemas distribuidos, tiene las siguientes:
Los procesadores estn poco acoplados, con una pequea o ausente coordinacin
central.
Los procesadores pueden estar lejos, con lo que conlleva de considerables
retrasos en la comunicacin, e irreversibles links de comunicacin.
La topologa, puede cambiar mientras el sistema est en ejecucin. Esto viene
dado al agregar o quitar procesadores. Esto ltimo conlleva de fallos de links.

Los procesadores trabajan en tareas independientes.

Seguidamente se hace referencia a diversas taxonomas, que al atender a distintos
criterios, facilitan la integracin de las arquitecturas ms recientes.

2.4 Clasificacin de Johnson.

La clasificacin de Johnson, est orientada hacia los distintos tipos de acceso a memoria.
- UMA - Uniform Memory Access
Utilizan una memoria principal, sistema de ficheros, etc, de manera comn. Los
accesos de memoria, son uniformes mediante una red de interconexin. Cada
procesador tiene una cache local. En orden a guardar la coherencia entre caches de
procesador, y para que cada uno de ellos tenga una vista constante de la memoria
principal, se implanta un protocolo de coherencia Hw.
SMPS (Multiprocesadores simtricos). El requerimiento de una red de
interconexin de alto rendimiento, restringe el nmero de procesadores.
- NUMA - Non Uniform Memory Access
Son procesadores, donde cada uno de ellos, tienen su propia memoria. Sin embargo,
los procesadores pueden acceder a la memoria local de los otros procesadores.
Una tpica arquitectura NUMA, consta de dos clusters, cada uno de los cuales, son
SMPs. Los clusters estn conectados entre s.
Otras arquitecturas especficas: NUMA cahe coherente (CC-NUMA), y la
arquitectura de memoria solamente cache (COMA).
CC-NUMA: la coherencia de cache, se realiza mediante un protocolo especial.
COMA: las memorias locales, se llevan a cabo mediante caches.
- NORMA - No Remote Memory Access
En este tipo de arquitectura, un procesador no es capaz de acceder a otro
procesador. La comunicacin entre procesadores, tiene que ser realizada mediante el
intercambio explcito de mensajes entre procesadores.
6

Arquitecturas NORMA especiales:

Cluster de workstations (COW): un conjunto de ordenadores SISD,
conectados a travs de una red con cierta topologa.
Cluster de SMPs (CLUMPS): los nodos del cluster son SMP.

2. 5. Otras clasificaciones
Atendiendo al tipo y nmero de procesadores:
Sistemas masivamente paralelos (fine grain): procesadores sencillos, matriz de procesadores
hermticamente acoplados.
Parelelismo coarse-grained
Presencia o ausencia d mecanismos de control global:
- Mecanismo de control global: utilizado tanto para cargar programas como informacin en
los procesadores. Ordenadores MIMD.
-Otro extremo: cada procesador obtiene instrucciones detalladas en cada paso. Ordenadores
SIMD.
Operaciones sncronas contra asncronas.
Operaciones sncronas: un reloj comn es utilizado para sincronizar la operaciones de
distintos procesadores. Mquinas SIMD.
Por otra parte, las operaciones sncronas, pueden requerir una sobrecarga no deseada.
Sincronizacin de una red de comunicacin de datos.
Operaciones asncronas: los procesadores traan y la comunicacin de datos, no es
conducida por un reloj comn.
Interconexiones entre procesadores.
Mecanismos para el intercambio de informacin.
Arquitecturas de memoria distribuidas.
Memoria compartida global, que puede ser accedida por todos los procesadores. La
comunicacin viene va memoria global. El problema que tienen es el control de acceso a
memoria.
Arquitecturas por paso de mensajes: Aqu no existe una memoria global. La comunicacin se
realiza a travs de una red de interconexin.
Sistemas hbridos: Existe un sistema de memoria compartida, adems de una red de
interconexin.

3. Arquitecturas Sncronas

1A

Las arquitecturas paralelas sncronas, coordinan operaciones concurrentes en pasos

cerrados, lockstep, a travs de relojes globales, unidades centrales de control, o
controladores de unidades vectoriales.

3.1 Procesadores vectoriales entubados

1A,4L,2L

Fueron desarrollados al final de los aos 60, y principios de los 70, para desarrollar
directamente, clculos matriciales y vectoriales masivos. Dos ejemplos de ordenadores on
esta clase de arquitectura, fueron el STRECH de IBM, y el 6600 de CDC.
La idea principal de esta clase de arquitecturas, es que suministra una manera de
empezar una tarea, antes de que una antigua haya sido completada. As el ndice de
terminacin no es una funcin del tiempo total de procesamiento, sino ms in de como un
nuevo proceso puede ser introducido. Considerese un proceso secuencial, que sea realiado
paso a paso en un perodo de tiempo, Figura 3.1. El tiempo total requerido para completar
este proceso es N unidades, asumiendo que cada paso tarda una unidad de tiempo.
1

Figura 3.1. Un proceso secuencial de N pasos.

Para realizar este mismo proceso utilizando tcnicas pipeline, considere la siguiente
1

......

N
N
N

N
Tiempo

Figura 3.2. Ejecucin entubada, pipelined, de un proceso de N pasos.

figura, que muestra una cadena continua de jobs yendo a travs de N pasos secuenciales. En
este caso cada fila horizontal de cajas, representa el tiempo histrico de un job. Cada
columna vertical de cajas, representa la actividad en un instante de tiempo especfico. El
tiempo total de realizacin de un proceso no cambia, entre la primera y segunda figura, y
podra ser ms largo en la segunda. El ndice de productividad de las tareas en la segunda
figura es una por ciclo, como opuesto a uno cada N ciclos de la primera.

3.1.1 Principio de concurrencia entubada .

Entubamiento es una tcnica de implementacin para arquitecturas de alto
rendimiento, lo cual es invisible al programador. Sin embargo, el uso del entubamiento,
puede ser reflejado en el orden del cdigo de una mquina de alto rendimiento. considere
una mquina de alto rendimiento. Considere una estructura de computacin arbitraria para
evaluar una funcin F, sobre una cadena de valores de entrada x 1, ...,xn, para producir una
cadena de valores de salida F(x1), ..., F(xn). El desarrollo de esta estructura de clculo, puede

estar caracterizada primero, en trminos de su latencia, y segundo por su productividad. La

latencia se define, como el retraso entre el suministro de un valor de entrada x i, y la
recepcin de la salida de F, el valor F(xi). La productividad se define, como el ndice en el
cual los valores son producidos por F. En el caso ms sencillo, donde la salida i aparece al
mismo tiempo que la entrada i+1 es presentada a F, la productividad de F ser reciproca aa
su latencia.

xi+3

c(xi+2)

f(xi)=a(b(c(xi)))

b(c(xi+2))
Figura 3.3. Una estructura entubada

Mejorar el desarrollo de una estructura de computacin, significa incrementar la

productividad. Una manera de hacerlo es reducir la latencia, generalmente implementando F
con circuitos lgicos ms rpidos. Si la funcin F, consta de una secuencia de subfunciones,
por ejemplo, a, b y c, tal que F(x) = a(b(c(xi))), entonces es posible implementar F,
utilizando lgica entubada. La descomposicin de F en tres subfunciones, se ilustra en la
figura 3.1. Cada paso en el entubado, contiene alguna funcin lgica de evaluacin y entre
los pasos hay sitios, para almacenar los valores intermedios. Como la latencia de cada
subfuncin es menor que la latencia de F, la tasa en la cual los nuevos valores pueden ser
presentados en cada paso es ms grande que la tasa en la cual pueden ser presentada por un
diagrama , ver Figura 3.2.
Ejemplos de estas arquitecturas son las series CRAY. Tanto el CRAY-1, como el
CRAY-X-MP/4, aunque esta ltima tamin podra ser clasificada como una arquitectura
MIMD. Sequidamente se pasa a describir las series CRAY.
Dado una estructura entubada, no puede ser mantenido en un continuo estado de
ocupado, hay un nmero de condiciones que el diseador debera de intentar satisfacer para
mantener la productividad tan lejos como sea posible. Estas condiciones son:
1. La latencia de las etapas entubadas, debera de ser igual.
2. Los clculos en cada paso del sistema entubado, deberan ser esencialmente
secuenciales, e independiente unas de otras.
3. Un continuo flujo de valores de salida, debera ser presentado al sistema
entubado, y los valores de salida resultantes, deberan estar procesados por la
sucesin lgica en la tasa en la que estn producidas.

3.2 Las arquitecturas SIMD

1A

Las arquitecturas SIMD, emplean tpicamente una unidad de control, mltiples

elementos de procesamiento (PE), y una red de interconexin (IN) para las comunicaciones
de procesador a procesador, o de memoria a procesador.

La unidad de control transmite una nica instruccin a todos los procesadores, los
cuales ejecutan la instruccin en modo lockstep, o paso cerrado, con los datos locales.
Adems dirige todas las operaciones de procesamiento de datos que ocurren en la mquina,
y evalua las instrucciones de ramificacin encontradas en la sencilla cadena de instruccin.
La red de interconexin, permite que los resultados calculados en un procesador sean
comunicados a otro, para utilizarlo como operando en una instruccin siguiente. A los
procesadores de manera individual, se les puede permitir el permanecer de manera
inhabilitada durante la instruccin en marcha. En la figura 3.4 se muestra la estructura tpica
de esta clase de arquitecturas.
La unidad de procesamiento, es un poco ms que una ALU (unidad aritmticolgica), un conjunto de registros y una mscara de bit. La mscara de bit, determina, si el PE
actua en las operaciones sobre los datos, transmitidas por la unidad de control. La red de
interconexin, permite a los datos calculados en un procesador ser comunicados a otro
procesador para utilizarlos como operandos de la siguiente instruccin. A los procesadores
individuales les est permitido para desabilitar la instruccin actual.
Una alternativa, a la ejecucin normal de un SIMD, es tratar cada elemento de
procesamiento, como si fuese una mquina MIMD. Cada elemento de procesamiento, tiene
su propia programa independiente a ejecutar, y se establece un contador de programa local,
el registro de instruccin.

Cadena de
instruccin

Add r1,b

Unidad
de
Control

Add r1,b

Cadena de
datos

PE

PE

Add r1,b

PE

I
N

Figura 3.4 Estructura tpica de una arquitectura SIMD.

La cadena de instruccin es ejecutada como si fuese en modo SIMD tradicional,
entonces transmite las instrucciones necesarias para cada PE, para obtener, decodificar y
ejecutar las instrucciones residentes localmente. As en cada ciclo de instruccion virtual, la
unidad de control debe seguir una cadena de instrucciones que lo causa para transmitir las
operaciones.

10

Operando de esa manera, cada PE interpreta su propia cadena de instruccin local en

un estilo similar al que una mquina MIMD. Esto permite a un usuario de una mquina
SIMD, flexibilidad para resolver problemas que tiene un regusto MIMD. Puede ser ms
eficiente que el estilo de datos en paralelo de las mquinas SIMD. Esto es porque cada vez
que a travs del bucle de control cada elemento tendr una de las instrucciones virtuales para
ejecutar. Este es un sencillo, pero ilustrativo ejemplo de una emulacin de una mquina
MIMD, en una SIMD. Dentro de la arquitectura SIMD, podriamos destacar la siguiente
clasificacin:

Arquitecturas de procesadores matriciales.

Arquitecturas de procesadores con memorias asociativas.
Arquitecturas Sistlicas.

3.2.1 Arquitecturas de procesadores matriciales

1A

Estn estructurados para la ejecucin de SIMD numricos han sido empleados para
clculos cientficos a gran escala, tales como el procesamiento de imgenes, y modelizacin
de fenmenos ligados a la energa nuclear. Los procesadores matriciales fueron desarrollados
al final de los aos 60, y su primer diseo fue el ILLIAC-IV. Los operandos son por lo
general, valores en coma flotante, y su tamao tipico ronda entre los 32 y 64 bits. Han sido
utilizados varios esquemas de IN, para proporcionar las comunicaciones entre memoria y
procesador, o entre procesadores. Las topologas IN, ms populares son las de malla y
crossbar.
Una variante de las arquitecturas de matriz de procesadores, es la que utiliza un gran
nmero de procesadores de 1 bit. En la figura 3.5, se muestra un ejemplo de esta clase de
arquitecturas. En esta clase de esquemas, la matriz de procesadores est organizada en una
rejilla simtrica (tal como 64x64), y asociado con multiple planos de bits de memoria, que
corresponden a las dimensiones de la rejilla del procesador. El procesador n(Pn), situado en
la rejilla de procesadores en el puesto (x,y), opera sobre los bits de memoria en la posicin
(x,y), en todos los planos de memoria asociados. Ejemplos de esta clase de arquitectura, son
los Massively Parallel Processors (MPP), o los distributed Array Processors de ICL, son por
lo general utilizados para el procesamiento de imgenes, al mapear los pixels sobre la
estructura en planos de la memoria.

Figura 3.5 Ejemplo de matices de procesadores de 1 bit.

3.2.2 Arquitecturas con Procesadores de Memoria Asociativa

1A

11

Los ordenadores construidos alrededor de una memoria asociativa, constituyen un

grupo caracterstico de la arquitectura SIMD, que utiliza la lgica de comparacin
especial, para acceder a la informacin almacenada en paralelo de acuerdo a su
contenido. La investigacin sobre la construccin de memorias asociativas, empez
al final de la dcada de los aos 50, con el objetivo obvio, de ser capaz de buscar en
la memoria en paralelo, informacin que emparejase algn dato especfico. Los
procesadores con memoria asociativa modernos, se desarrollaron al principio de la
dcada de los aos 70, ejemplos de estos son el PEPE (Parallel Element Processing
Ensemble) de los Laboratorios Bell, desarrollados naturalmente, para aplicaciones
orientadas a bases de datos, tales como vigilancia y rastreo. La figura siguiente,
muestra las caractersticas de las unidades funcionales de un procesador con memoria
asociativa.

Controlador
del
Programa

Memoria del
Programa

Controlador
Matricial

ALU y
Registros
Especiales

Memoria Asociativa
Figura 3.6 Estructura de un procesador de memoria asociativa
Un controlador de programa, lee y ejecuta instrucciones, invocando un controlador
matricial especializado, cuando son encontradas instrucciones de la memoria asociativa. Los
registros especiales permiten al controlador de programa y a la memoria asociativa
compartir datos.
Cada palabra de memoria asociativa, generalmente tiene un nmero grande de bits
(por ejemplo 32.786), est asociada con los registros especiales y la lgica de comparacin.
Por lo tanto, un procesador asociativo con 4.096 palabras, efectivamente tiene 4.096
elementos de procesamiento.
La siguiente figura, representa una operacin de comparacin orientada a la fila, para
una arquitectura genrica de it en serie. Una parte del registro de comparacin, contiene el
valor a ser emperejado. Todos los elementos de procesamiento asociativo, comienzan en una
columna especificada de memoria, y comparan los contenidos de cuatro bits consecutivos en
12

sus filas contra el contenido del registro de comparacin, colocando un bit en el registro
para indicar si sus columnas contienen o no emparejamiento.
Registro de Comparacin

10011010

Patrn de Bsqueda
Registros Asociativos
Memoria Asociativa

Palabras

1001
0110
1000
0011

A
1
0
0
0

Mscara

1
1
1
1

Ventana de bsqueda de columna de bit

Bits por palabra

3.3 Arquitecturas sistlicas de propsito general

1A, 2A

Figura 3.7 Operacin de comparacin en una memoria asociativa

Al principio de los aos 80, H.T.Kung de la Universidad de Carnegie Mellon,
propuso las arquitecturas sistlicas. En fisiologa, el trmino sistlico describe la contraccin
del corazn, el cual enva regularmente sangre a todas las clulas del cuerpo. De manera
similar, los procesos sistlicos de ordenador desarrollan operaciones de una manera rtmica,
incremental y repetitiva. Tal como se muestra en la figura 3.8. Aunque no hay una definicin
standard mpliamente aceptadade matrices y celdas sistlicas, paso a dar una visin general
resumida:
Matriz sistlica: una estructura similar a una rejilla, de elementos de procesamiento
especial que procesa informacin ms como un n-dimensional pipeline. Distinto a un
pipeline, sin embargo, los datos de entrada tambin como flujos de resultados
parciales a travs de la matriz. Adems, la informacin puede fluir en una
organizacin sistlica a velocidades mltiples en mltiples direcciones. Las matrices
sistlicas generalmente tienen una muy alto ndice de E/S y son tambin adaptados
para operaciones paralelas intensas.
Aplicaciones: Aritmtica de matrices, procesamiento de seales y de imgenes,
reconocimiento de lenguajes, operaciones de bases de datos relacionales,
manipulacin de estructuras de datos, y manipulacin de cadenas dde caracteres.
Matrices sistlicas de propsito especial: Tpicamente, muchas decenas o
centenares de celdas metidas en un nico chip.
Matrices sistlicas de propsito general: Una matriz de elementos de
procesamiento sistlico, que pueden ser adaptados a una variedad de aplicaciones a
travs de la reconfiguracin o de la programacin.
Matrices sistlicas programables: Una matriz de elementos sistlicos programables
que opera de manera SIMD, o MIMD. O las matrices se interconectan o cada unidad

13

de procesamiento es programable, y un programa controla el flujo de datos a travs

de los elementos.
Matrices sistlicas reconfigurables: Una matriz de elementos sistlicos que pueden
ser programados a ms bajo nivel. La tecnologa FPGA (field-programmable gate
array), permite a la matriz emular los elementos sistlicos conectados a muy bajo
nivel para cada aplicacin.
Esta clase de arquitecturas, son multiprocesadores entubados en los cuales los datos
son bombeados de manera rtmica desde la memoria, y a travs de una red de procesadores
devuelta a la memoria. Un reloj global, y los retrasos de tiempo explcito sincronizan esta
flujo de datos entubado, el cual consta de operandos obtenidos desde la memoria y los
resultados parciales son utilizados por cada procesador. Los procesadores modulares unidos
por interconexiones locales y constantes, suministran bloques bsicos construidos. Durante
cada intervalo de tiempo, estos procesadores ejecutan una secuencia corta e invariante de
instrucciones.
Las matrices sistlicas direccionan el desarrollo de requerimientos de los sistemas de
propsito especial, al alcanzar una computacin paralela significativa, y al evitar cuellos de
botella de E/S y de ancho de banda de memoria. Se obtiene un alto grado de paralelismo, a
travs de mltiples procesadores, tpicamente en forma bidimensional. Las arquitecturas
sistlicas maximizan las computaciones desarrollados sobre los datos, una vez han sido
obtenidos de la memoria o de un dispositivo externo. Por lo tano, una vez los datos entran
en la matriz sistlica, son pasados a cualquier procesador que lo necesita, sin un
almacenamiento a memoria.
Esta clase de arquitectura es adecuada para procesos con mucho tiempo de clculo,
donde se efectuan varias operaciones sobre el mismo dato. Apropiadas para problemas con
muchas repeticiones y muy especficos.
Las caractersticas de esta clase de procesadores, las podramos ver desde tres
puntos de vista, a saber: la tecnologa, el procesamiento entubado y las aplicaciones.
Hoy en da la madurez de la tecnologa VLSI/WSI permite fabricar circuitos de
hasta 1/2 illn de transistores a un costo razonable.

Memoria

Figura 3.8 Flujo de datos desde y hacia la memoria.

14

4. Arquitecturas MIMD

1A,

En la seccin anterior, se examinaron el conjunto de tcnicas que se emplean en las

arquitecturas de alto rendimiento, para mejorar la productividad con un solo procesador.
Estas tcnicas incluyen el pipeline, mltiples unidades funcionales, y una variedad de
mecanismos diseados para encontrar los suficientes requerimientos de productividad de
memoria y de latencia.
Sin embargo el conocido como cuello de botella de Von Neumann, que es el lmite
fundamental impuesto en el procesamiento secuencial por el ndice, en la cual la informacin
puede ser movida a travs del lmite entre el procesador y la memoria, limita tanto la tasa de
instrucciones que pueden ser utilizadas, como la tasa en la que los operandos pueden ser
suministrados.
La implementacin ms obvia, que surge del cambio a un estilo de arquitectura
MIMD, es que debera de haber bastantes sitios de control activos (involucrando una
multiplicidad de contadores de programa) dentro de la mquina, con lgica distribuida para
instrucciones duplicadas. Esta parece ser la direccin en la cual, los fabricantes existentes de
mquinas SIMD, se han estado moviendo, por ejemplo con la introduccin de mquinas MSIMD tales como el CRAY X-MP. Estas mquinas utilizan estructura de memoria paralela
para salvar el cuello de botella de Von Newmann, y procesadores mltiples para atacar los
problemas de procesamiento escalar.
La mayora de los cientificos, y de los usuarios de las mquinas MIMD, distinguen
entre sistemas multiprocesadores y multiordenadores. Si uno considera a un procesador
como un componente simple de un ordenador, entonces la distincin se clarifica. Un
multiprocesador, es entonces un sistema en el cual hay una sencilla replicacin de
procesadores dentro de la organizacin, lo cual hace que se altere la relacin entre el/los
procesador(es), y los otros componentes (tales como la memoria). Un multiordenador, es un
sistema en el cual el ordenador entero (procesador y memoria juntos) se replican, y de
alguna manera se aade un sistema de comunicacin de red, para permitirles el intercambio
de informacin.
En 1971, Minsky y Rapert, conjeturaron que la velocidad alcanzable por un
ordenador paralelo, es proporcional al logaritmo del nmero de los procesadores. Sin
embargo, en los ltimos aos, el desarrolllo de sistemas MIMD, ha demostrado que esta
teora era falsa.
Las arquitecturas MIMD, emplean mltiples procesadores que pueden ejecutar
cadenas de instrucciones de forma independiente, utilizando datos locales. As, los
ordenadores MIMD, suministran soluciones paralelas que requieren procesadores que
operen de manera altamente autnoma. Aunque el sw de los programas ejecutados en
arquitecturas MIMD, son ordenadores asncronos, caracterizados por el Hw. de control
descentralizado. Podramos decir, que las arquitecturas MIMD, vienen resumidas por los
siguientes cuatro caractersticas:
- Cada procesador ejecuta su propia secuencia de instrucciones.
- Cada procesador trabaja en una parte distinta del problema.
- Cada procesador comunica informacin (datos), a otras partes.
- Los procesadores pueden tener que esperar a otros procesos, para la obtencin de
datos.

15

El impulso para el desarrollo de arquitecturas MIMD, puede ser atribuido a algunos

factores interrelacionados. Los ordenadores MIMD, suministran alto nivel de paralelismo
(niveles de subprogramacin y tareas), que pueden ser explicitadas por algoritmos del tipo
divide y vencers, organizado como subclculos de gran independencia (por ejemplo,
bsqueda y ordenacin).

4.1 El problema del diseo

2L

Para entender como funcionan varias mquinas MIMD, y que nivel de desarrollo es
razonable esperar de ellas, se debe de examinar el espacio de diseo de las mquinas MIMD
ms de cerca. Por ejemplo, las dos decisiones ms importantes que deben tomarse al
principio del proceso de diseo son:
Primeramente, que poderoso debe ser cada elemento de procesamiento y
seguidamente, cuantos elementos de procesamiento deberan haber.
Existe adems, la disyuntiva de obtener la potencia de clculo P, o bin mediante un
nmero pequeo de poderosos pero caros, procesadores, o bin, con un nmero elevado de
pequeos, pero econmicos procesadores. Esto por si mismo, no da una solucin completa
al problema de suministrar un alto grado de desarrollo a travs del paralelismo masivo.
Esto eleva, el nmero de elementos de diseo fundamentales, que la arquitectura de
alto rendimiento MIMD debe considerar. Por ejemplo, supongan que un diseador tiene un
ilimitado nmero de pequeos, pero potentes elementos de computacin. Como debera
conectarlos?. Partiendo de que el nmero de conexiones que se pueden hacer a cada
elemento es finito (y probablemente bastante pequeo), es imposible conectar cada elemento
a cada uno de los otros. Existe entonces alguna estrategia de interconexin que sea
suficientemente universal, para suministrar la conectividad adecuada para la mayora de las
aplicaciones?.
Si fuese posible, construir tal sistema, qu lenguajes seran apropiados para expresar
las aplicaciones de alto nivel de paralelismo?, y debera ser responsabilidad del
programador, la expresin del paralelismo en la aplicacion?. Este es un elemento que influye
gravemente, en el diseo de lenguajes de programacin paralelos tanto como en las
arquitecturas MIMD.

4.2 Categoras de la arquitectura MIMD.

2L

Investigar dentro del diseo de sistemas paralelos, conduce a la aparicin de distintas

categoras de arquitecturas MIMD, cada una de las cuales con sus ventajas e inconvenientes.
La tcnica, relativamente sencilla, de replicar procesadores, y suministrarles a todos
ellos un almacenamiento comn, produce los multiprocesadores de memoria compartida.
Las arquitecturas de memoria distribuida, operan sobre el principio de que el dato que es
local a un procesador, ser situado en la memoria del mismo, reduciendo de ese modo, la
carga de la red de interconexin. En situaciones donde la localidad est ausente, o en la que
sea preferido el coste de un acceso uniforme, sern utilizados las arquitecturas con memoria
centralizada. Para muchas aplicaciones, no todos los procesadores necesitan acceso a todos
los sitios de memoria, y entonces es juiciosa sin duda una particin de la memoria.
Si no est permitida la comparticin de datos, los procesadores necesitarn
intercambiar informacin de alguna forma. Cuando el intercambio de informacin se realiza
a travs de una posicin de memoria, los procesadores que se ven envueltos, tienen que ser

16

sincronizados antes de que la transferencia sea completada. El procesador que escribe, debe
asegurarse de que el dato vlido no sea sobrescrito, y que el procesador que lo lee, debe
asegurarse de que la posicin es leda despus de que el procesador ha situado un valor all.
Esto es anlogo, a la hora de pasar un mensaje de un procesador a otro. Para asegurarse de
que los procesadores estn sincronizados, se deben de utilizar las tcnicas estandarizadas de
los sistemas operativos, tales como semforos, pero una tcnica alternativa es renunciar a la
memoria compartida, y simplemente suministrar canales de comunicacin dedicados entre
procesadores. Esto conduce, a la categora de paso de mensajes de mquinas MIMD.

4.2.1. Arquitecturas de memoria distribuida.

1L

Han sido propuestas varias topologas de red para apoyar y suministrar el desarrollo
eficiente, los programas en paralelo con distintas patrones de comunicacin entre
procesadores.
Pero antes de eso, es conveniente ver unos parmetros principales del diseo de
redes, como son el ancho de banda, la latencia de red, y el coste, este ltimo indicado por el
nmero de enlaces en la red. El ancho de banda, es el nmero de bits que pueden ser
transmitidos por unidad de tiempo, dado en bits/seg. La latencia de red, es el tiempo que se
tarda en hacer una transferencia de mensaje a travs de la red. La latencia de comunicacin,
es el tiempo total para enviar el mensaje incluyendo el software de sobrecarga, y el retardo
de la interface. Se podra utilizar tambin el trmino latencia del mensaje, como el tiempo
para enviar un mensaje de longitud cero. Esto es esencialmente, la sobrecarga software y
hardware, en enviar un mensaje (encontrar la ruta, empaquetar, desempaquetar, etc.) al cual
aadimos la actual tiempo de transmisin para enviar los datos atravs del enlace. El nmero
de enlaces en un camino entre dos nodos es una consideracin importante, ser un factor
para determinar el retraso para un mensaje. El dimetro, es el nmero mnimo de enlaces
entre dos de los nodos ms alejados en la red. Note que solamente se utilizan las rutas ms
cortas. El dimetro es utilizado para determinar el peor de los retrasos. El dimetro de la
red, da la distancia mxima que un mensaje debe recorrer, y puede ser utilizado para
encontrar el lmite ms bajo de comunicacin de algunos algoritmos paralelos. El ancho de
biseccin, de una red, es el nmero de enlaces que deben ser cortados para dividir la red en
dos partes iguales.
A continuacin se explican una serie de topologas, a saber:
Arquitecturas en topologa de anillo. Cada nodo requiere dos enlaces, uno a cada
nodo vecino, y por eso, un anillo de n nodos requiere n enlaces. Los nodos de lo extremos,
estn lo suficientemente lejos, por eso, el dimetro es de n-1. Para los anillos donde los
mensajes pueden pasar en cualquier direccin, el dimetro es de n/2. Esta clase de topologa,
es la ms apropiada para pequeos nmeros de procesadores, que ejecutan algoritmos no
dominados por la comunicacin de datos. Este ejemplo de esta arquitectura, se puede ver en
la figura 4.1.

Figura 4.1 Topologa en anillo

17

Arquitectura en topologa de malla. Una malla bidimensional se puede crear,

teniendo cada nodo en una matriz bidimensional, conectada a cada uno de sus cuatro
vecinos. El dimetro de una matriz de n x n es 2(n-1). Cuando las terminaciones libres de
una malla, circulan hacia atrs a los lados opuestos, es el caso de un toro. En la figura
siguiente, se puede observar un ejemplo de topologa en malla.
Enlaces

Ordenador /
procesador

Figura 4.2 Topologa en malla

Las comunicaciones se pueden aumentar, suministrando enlaces diagonales para
conectar nodos por filas y columnas.
Arquitecturas en topologa de rbol. Esta clase de topologas, han sido realizadas
para apoyar algoritmos de divide y vencers, para la bsqueda y ordenacin, algoritmos de
procesamiento de imgenes, etc. De todas las variedades de topologas en rbol, la ms
estudiada ha sido la de rbol binario. Al primer nodo se le llama raz. Cada nodo tiene dos
enlaces conectados a dos nodos debajo de l. En el primer nivel por debajo de la raz, hay
dos nodos, en el siguiente nivel hay cuatro nodos, y en el j-esimo nivel por debajo de la raz,
hay 2j nodos y en total, 2j+1 - 1 nodos en total en la red. Este rbol en particular, es un bol
binario completo, si cada nivel est completamente ocupado. La altura de un rbol, es el
nmero de enlaces desde la raz a las hojas ms bajas. En un rbol m-ario, cada nodo se
conecta a m nodos debajo de l. Un ejemplo de arquitectura en rbol binario, lo tenemos en
la figura 4.3.

Raz
Enlaces

Elemento de
procesamiento

Figura 4.3 Arquitectura en rbol binario.

Arquitecturas en topologa de hipercubo. En una red hypercubo de dimensiones,
cada nodo conecta a uno de los nodos de las dimensiones de la red. En realidad,
18

generalizando diramos, que est conectado. Por ejemplo, en un hipercubo de tres

dimensiones, las conexiones en la direccin de las x, direccin de las y, y la direccin de las
z, forman un cubo. Como se muestra en la figura 4.4. Cada bit corresponde a una de las
dimensiones y puede ser un 0 o un 1, para los dos nodos de la dimensin. Los nodos en un
hipercubo de tres dimensiones, tendran una direccin de tres bits.
110
100

111
101

010
110
000

001

Figura 4.4 Topologa en hipercubo de 3 dimensiones.

Dese cuenta que cada nodo conecta a los nodos cuyas direcciones difieren solo en un
bit. Esta caracteristica, puede ser extendida a los hipercubos de mayores dimensiones. Por
ejemplo, un hipercubo de cinco dimensiones, el nodo 11101, conecta a los nodos 11100,
11111, 11001, 10101 y 01101.
Una ventaja notable del hipercubo, es que el dimetro de la red es dado por el log 2n,
lo cual tiene un crecimiento razonablemente bajo al incrementar n, siendo n el nmero de
nodos.
Los nodos se comunican, al enviar mensajes en paquetes. El tamao del paquete
varia, pero el protocolo impone un mximo.

Figura 4.5 Hipercubo

de cuatro dimensiones 0100

0111

0110
0101

1110
1100

1111
1101

0010

Arquitecturas embebidas. El trmino0011

embebido, como1010
aplicado a redes
estticas,
1011
describe el mapeo de los nodos de una red en otra. Por ejemplo, un anillo puede ser
embebido por un toro, como
0000 muestra la siguiente figura. 1000
0001

1001

Figura 4.6 Anillo embebido dentro de un toro

19

Esto es importante, porque podemos tener un algoritmo que requiere solamente

comunicacin entre los vecinos ms cercanos en una red especfica.
El trmino dilacin, es utilizado para indicar la calidad de lo embebido. Es el nmero
mximo de enlaces en la red que embebe correspondiente a un enlace en la red embebida. Lo
perfecto, sera que una anillo en una malla o toro o una malla dentro de un hipercubo, tiene
una dilacin de 1.

4.2.2. Arquitecturas de memoria compartida.

1A, 1L

Las arquitecturas de memoria compartida llevan a cabo la coordinacin entre

procesadores, al suministrar una memoria compartida, global, que cada procesador puede
direccionar. Los ordenadores de memoria compartida, no tienen alguno de los problemas
que se encuentran en las arquitecturas por paso de mensajes, tales como la latencia en envos
de mensaje, al ser los datos encolados y enviados a travs de nodos intermedios. Sin
embargo, aparecen otros problemas, tales como la sincronizacin del acceso a datos y la
coherencia de cache, que deben ser resueltos.
Los procesadores coordinados con variables compartidas, requieren mecanismos de
sincronizacin atmica para prevenir, que un proceso acceda a datos antes de que otro
termine de actualizarlo.
De manera tpica, cada procesador en un entorno de memoria compartida, tiene
tambin una memoria local que es utilizada como cache. Las copias mltiples de la misma
memoria compartida, adems, pueden existir en distintas varios procesadores al mismo
tiempo. Mantener una versin consistente de tal informacin es el problema de la
consistencia de la cache.
Figura
Esquemas
de interconexin
de principales
arquitecturaalternativas
MIMD de memoria
compartida
La4.7
siguiente
figura,
ilustra algunas
para conectar
mltiples
procesadores a la memoria compartida.
P
Cache

(a) Interconexin por bus

P
Cache

P
Cache
Bus

M0

M0

M1

M1

M2

M2

(b) 2x2 crossbar switch

P0

E/S0
D

P1

E/S1
(c) 8x8 omega MIN routing, una peticin de P3 a M3.

20

M0

P0

M1

P1
P2

1
P3

P4

1
P5

P6

1
P7

000
001

M2

010

M3

101

M4

100

M5

101

M6

110

M7

111

Interconexin por bus. Los buses de tiempo compartido, ofrecen una manera
completamente sencilla, de dar a varios procesadores, acceso a una memoria compartida.
Como se muestra en la seccin (a), de la anterior figura. Solamente un procesador, puede
utilizar el bus en un momento dado. Algunas arquitecturas como la Cm*, emplean dos clases
de buses -un bus local enlaza un cluster de procesadores, y un sistema de ms alto nivel,
enlaza el servicio de procesadores dedicados con cada cluster.
Interconexiones crossbar. Utiliza un switch crossbar de n2 puntos de cruce, para
conectar n procesadores con n memorias. Como se ve, en la seccin (b) de la anterior figura.
Los procesadores pueden contender para el acceso a una localizacin de memoria, pero los
crossbars contenden, para los enlaces de comunicacin al suministrar un camino dedicado
entre cada posible par procesador/memoria.
Redes de interconexin multipiso o Multistage Interconnection Networks
(MIN). Este esquema, alcanza un compromiso entre las alternativas precio/rendimiento
ofrecidas por los buses y los crossbars. Un MIN NxN, conecta N procesadores a N
memorias al organizar multiples pisos o bancos de switches en el camino de interconexin
de la red.
Cuando N es elevado a 2, El switch en el piso y, examina el i-esimo bit, para
determinar si la entrada esta para ser conectada en la salida de arriba o de abajo.
El esquema (c) dentro de la figura anterior, muestra una red omega conectando ocho
procesadores y memorias. Donde un bit de control igual a cero, indica una conexin a la
salida superior. La extensibilidad, es una caracterstica significativa del MIN, como su
dimetro de comunicacin es proporcional a log2N. La mariposa de BBN, puede ser
configurada con 256 procesadores.

21

4.3 Granuralidad.

2L

La frecuencia relativa con la que los procesadores interactuan, y desde ahora se

sincronizan con cada uno de los otros, es otro problema de diseo importante. La frecuencia
de interaccin puede ser cuantificada como el ratio de la cantidad de clculo con la cantidad
de eventos de comunicacin. Este ndice es conocido como la granuralidad del proceso, con
un ndice pequeo correspondiente a un proceso de granuralidad pequea, y un ratio grande
correspondiente a los de basta granuraliadad. Los primeros se sincronizan con cada uno de
los otros, de una manera relativamente frecuente, mientras que los otros desarrollan
cantidades significativas de computaciones entre eventos de sincronizacin. La granuralidad
no dice nada a cerca de la cantidad de cdigo, o el tiempo de vida esperado de los procesos,
puesto que la frecuencia relativa de comunicacin no est necesariamente relacionada a
estos otros factores. Para obtener una medida especfica de la granuralidad, se debbe contar
el nmero medio de accesos de instrucciones mquina bsicas que cada proceso ejecuta
entre cada evento de sincronizacin. Los procesos de basta granuraliadad, se podra esperar
que ejecutasen miles de instrucciones entre cada evento de sincronizacin, mientras que los
otros podran ejecutar solamente uno.

4.4 Balanceo de la carga.

2L

Consideremos una arquitectura multiprocesador, en la cual una carga consistente de

m procesos en paralelo independientes, es distribuido entre n procesadores. La eficiencia del
sistema depende de forma critica, del trabajo que est repartida, igualmente entre los
procesadores, y esto puede ser ilustrado de una manera completamente simple. Si todo el
trabajo se localiza en un procesador, el sistema se desarrollar no mejor que un simple
procesador. De manera contraria, si el trabajo se divide exactamente entre los n
procesadores, el desarrollo podra crecer hasta n veces que la del simple procesador.
De hecho el problema del balanceo de carga es ms complejo que lo que esto
sugiere, ya que la carga presentada por cada proceso no es necesariamente la misma, y
adems no es generalmente conocido cuanto tiempo de procesadorser consumido por un
proceso antes de que este empiece. Este problema es ms complicado por la
multiprogramacin de un nico procesador, el cual es como responsable para m/n procesos.
Esto conduce a considerar varias cuestiones de diseo, relacionadas con el balanceo
de la carga. Primero de todo, deberan los procesadores simples dividir su tiempo entre un
nmero multiprogramado de procesos?. Segundo, debera un proceso estar estticamente
atado a un procesador, o debera ser capaz de migrar de un procesador a otro dependiendo
de la disponibilidad de los recursos de procesamiento?. La tercera, debera la creacin
dinmica de procesos estar permitida, o debera ser fija en tiempo de compilacin?.
No existe un conjunto de respuestas correctas a estas cuestiones, ya que en la
prctica cada sistema MIMD, es optimizado para un tipo particular de computacin. Sin
embargo, pueden ser definas un conjunto de reglas bsicas.
Si los procesadores no comparten su tiempo entre un nmero de procesos, la
utilizacin del sistema llega a ser relativamente pobre. Esto es porque los procesos que
interactuan ocasionalmente, necesitan sincronizarse, en un determinado punto un proceso

22

debe esperar a otro para emparejarse. Si un procesador no tiene otro trabajo para desarrollar
durante este periodo de espera, permanecer en estado ocioso.
Un problema que afecta tanto a la arquitectura como a los lenguajes de
programacin de un sistema MIMD, es si los procesos son creados dinmicamente durante
el tiempo de ejecucin, o di el nmero de procesos en paralelo es determinado de manera
esttica, en tiempo de compilacin. Los sistemas estticos, tienen la ventaja de que la
asignacin de los procesos en tiempo de compilacin de los procesos a los procesadores
puede ser desarrollado, y la utilizacin de los recursos del sistema puede ser optimizado. La
desventaja de estos sistemas, es que en ciertos tipos de algoritmos paralelos, los procesos
son creados en demanda, y entonces no pueden ser expresados naturalmente. Adems, el
nmero actual de procesadores debe ser conocido por el programador, y un cambio en este
parmetronecesitar la recompilacin de los programas. Los sistemas dinmicos, pueden ser
altamente flexibles, permitiendo a los programadores permanececer ignorantes a cerca del
paralelismo.Sin embargo, cada mquina tiene recursos finitos, y los algoritmos paralelos los
cuales generan nmeros muy grnades de procesos pueden ejecutar con relativamente poca
eficiencia.Esto es debido al hecho de que cada proceso requiere una cierta cantidad de
espacio de memoria para ejecutarse eficientemente.

5. Redes de ordenadores como una plataforma de

computacin por paso de mensajes (message-passing).

1L

Existe una manera ms econmica de obtener una potencia de clculo similar a la de

anteriores arquitecturas. Es por medio, de lo que se llaman clusters de estaciones de trabajo,
(COWS), o redes de estaciones de trabajo (NOWS). Utilizando un cluster de estaciones de
trabajo, se obtiene un nmero de ventajas significativas, y bien conocidas sobre los sistemas
de multiprocesadores diseados especialmente. A saber:
Estaciones de trabajo y pcs de alto rendimiento, dispuestos a bajo costo.
Los ltimos procesadores pueden ser incorporados dentro del sistema, tan pronto
estn disponibles.
Existe software que puede ser utilizado y modificado.
Estos clusters de estaciones de trabajo, pueden estar situados en cualquier parte del
mundo, siempre que estn conectadas a internet. La gran ventaja es que pueden ser un
conjunto heterogneo de ordenadores, tanto desde el punto de vista de su nmero, como de
su tipo. En concreto, cada vez que se realiza un proceso, las estaciones de trabajo
disponibles no tienen que ser el mismo nmero, ni tienen que ser de la misma clase.

5.1 Conceptos bsicos de programacin con paso de mensajes.

1L

Existen tres maneras de poder conseguir lo anteriormente dicho:

Diseando un lenguaje especial para la programacin en paralelo.
Extendiendo las palabras reservadas/sintaxis de un lenguaje de alto nivel
secuencial existente, a un manipulador de paso de mensajes.
23

 Utilizando un lenguaje de alto nivel secuencial, y suministrando una librera de

procedimientos externos para paso de mensajes.
Existen ejemplos de estas tres aproximaciones. Quizs el nico ejemplo de un
lenguaje de programacin en paralelo por paso de mensajes, es el occam, diseado para ser
utilizado con un procesador de paso de mensajes llamado transputer. Ejemplos de
extensiones del lenguaje incluyen, CC+ (una pequea extensin de C++), y el Fortran M, lo
mismo que el anterior pero en FORTRAN, ambos para programacin en paralelo de
propsio general.
Es posible, y aqu entrara la tercera opcin, aadir a un lenguaje de alto nivel como
C, llamadas de librera con paso de mensajes, que desarrollaran directamente, el pase de
mensaje de proceso a proceso. Hay que decir, que en este mtodo, es necesario decir de
manera explcita, que procesos tienen que ser ejecutados, cuando se pasan mensajes entre
procesos concurrentes, y que se pasa en los mensajes. Hay dos mtodos principales que son
necesarios en esta forma de un sistema de paso por mensajes:
1. Un mtodo de creacin de procesos separados, para la ejecucin en distintos
ordenadores.
2.

Un mtodo de enviar y recibir mensajes.

5.2 Creacin del proceso.

1L

Primero, es necesario crear los procesos e iniciar su ejecucin. Hay dos mtodos, de
creacin de procesos, creacin de procesos estticos, y creacin de procesos dinmicos. En
la creacin de procesos estticos, todos los procesos son especificados antes de la ejecucin,
y el sistema ejecutar un nmero fijo de procesos. El programador, generalmente, especifica
explcitamente, los procesos y los programas antes de su ejecucin por accin de lneas de
comando. En la mayora de las aplicaciones, los procesos no son todos los mismos ni son
todos ellos diferentes, generalmente, hay un proceso controlador, un proceso maestro, y el
resto son esclavos o trabajadores, los cuales son esencialmente los mismos. Es el
tambin llamado modelo SPMD, (single program multiple data), los distintos procesos son
combinados dentro de un programa. Despus de que el cdigo fuente, es construido con las
sentencias de control para separar las acciones de cada proceso, el programa es compilado a
cdigo ejecutable para cada procesador. Cada procesador cargar una copia de este cdigo
en su memoria local para la ejecucin. Si los procesadores son de distintos tipos, el cdigo
fuente ha de ser compilado en cdigo ejecutable para cada procesador.
En la creacin de procesos dinmicos, los procesos pueden ser creados y su
ejecucin iniciada durante la ejecucin de otros procesos, procesos de creacin
constructores, llamadas a libreras de sistema, son utilizados para crear procesos. Los
procesos pueden ser destruidos. Los procesos de creacin y destruccin de procesos pueden
ser condicionales, y el nmero de los mismos puede variar durante la ejecucin. De manera
clara, la creacin dinmica de procesos, es una tcnica ms potente, que la creacin esttica,
pero cuando los procesos son creados, incurren en una sobrecarga significativa. El modelo
ms general, para la creacin dinmica de procesos es el modelo de MPMD, (programa
mltiple datos mltiples), en los cuales programa separado y diferente es escrito para
procesadores diferentes.

24

5.3 Paso sncrono de mensajes.

1L

El tmino sncrono, es utilizado para las rutinas que en realidad devuelven el

mensaje, cuando la transferencia de este mensaje ha sido completada. Una rutina sncrona
enviada podra esperar hasta que el mensaje completo pueda ser aceptado por el proceso
receptor antes enviado el mensaje. Una rutina receptora sncrona esper hasta que el mensaje
que es esperado llegue. Desde ahora, las rutinas sncronas desarrollan intrinsecamente dos
acciones: Transfieren informacin y sincronizan procesos. El trmino rendezvous, es
utilizado para describir el encuentro y la sincronizacin de dos procesos, a travs de
operaciones sncronas de envo/recepcin.

5.4 Paso de mesajes Blocking y Nonblocking.

1L

El trmino blocking, fue utilizado tambin para describir rutinas que no regresan
(esto es, que no permiten al proceso continuar con la siguiente instruccin hasta que la
transferencia est completada). En ese sentido, los trminos sncronos y blocking eran
sinnimos. El trmino nonblocking fue utilizado para describir rutinas, que devuelven o no el
mensaje haba sido recibido. Sin embargo, los terminos blocking y nonblocking han sido
redefinidos en sistemas tales como MPI. Generalmente, se necesita un buffer de mensajes
entre la fuente y el destino para mantener los mensajes. Aqu, el buffer de mensajes es
utilizado para mantener los mensajes que haban sido enviados anteriormente a ser aceptados
por recv().
Proceso 1

Proceso 2

.
.
.
.
.
.
.
send();
.
.
.
.
.

.
.
.
.
.
.
.
.
.
recv();
.
.

Tiempo
Suspende
el procceso
Ambos proccesos
continuan

Peticin de envo
Reconocimiento
Mensaje

(a) Cuando send(), ocurre antes de recv()

Tiempo

Ambos proccesos
continuan

Proceso 1

Proceso 2

.
.
.
.
.
.
.
send();
.
.
.
.
.

.
.
.
.
.
recv();
.
.
.
.
.
.

Peticin de envo
Mensaje

Suspende
el procceso

25

Reconocimiento

(b) Cuando recv(), ocurre antes que send()

26

5.5 Broadcast, Gather, y Scatter.

1L

El termino broadcast, es utilizado para describir el envo del mensaje a todos los
procesos que tienen que ver con un problema. El trmino multicast, es utilizado para desribir
el envo del mismo mensaje para un grupo definido de procesos. Sin embargo, esta
diferenciacin no es utilizada aqu, para simplificarlo.
Los procesos que participarn en el broadcast deben ser identificados.
Proceso 0
data

Proceso 1

Proceso n-1
data

data

Accin
buf

Cdigo

.
.
bcast();
.
.

.
.
bcast();
.
.

.
.
bcast();
.
.

La accin del broadcast, no ocurre hasta que todos los procesos han ejecutado su
rutina de broadcast, y la operacin de broadcast tendr el efecto de sincronizacin de los
procesos.
El trmino scatter, es utilizado para describir el envo de cada elemento de un array
de datos, a la raz de un proceso separado. El contenido de la i-esima componente del array
es enviado al i-esimo proceso.
Proceso 0
data

Accin

Cdigo

Proceso 1

Proceso n-1

data

data

buf

.
.
scatter()
;
.
.

.
.
scatter()
;
.
.

.
.
scatter()
;
.
.

El trmino gather, es utilizado para describir teniendo un proceso, que recoge los
valores individuales de un conjunto de procesos. Se utiliza normalmente, despus de un
clculo que ha sido hecho por estos procesos. En esencia, gather es lo opuesto a scatter. La
informacin que procede del i-esimo proceso, es recibido por el proceso raz, y situado en la
i-esima posicin del array puesto para recibir la informacin. Algunas veces la operacin
gather, puede ser combinada con una operacin especfica lgica o aritmtica. Tales
operaciones algunas veces se denominan operaciones reducidas.
27

Proceso 0
data

Proceso n-1

Proceso 1

data

data

Accin
buf
.
.
gather()
;
.
.

Cdigo

.
.
gather()
;
.
.

.
.
gather()
;
.
.

5.6 Utilizando clusters de estaciones de trabajo.

1L

Hay varios paquetes software para programacin paralela en clustrers de estaciones

de trabajo. Quizs la ms extendida y ampliamente adoptada sea PVM. PMV suministra un
entorno software para paso de mensajes, entre ordenadores homogneos o heterogneos, y
tiene una coleccin de rutinas de librera que el usuario puede emplear con programas C o
FORTRAN.
Hy libreras de paso de mensajes propietarios, tales como MPL de IBM, libreria de
paso de mensajes, para el sistema multiprocesador RSS/6000 SP-2. Para fomentar su ms
amplio uso y portabilidad, un grupo de acadmicos y patrocinadores de la industria se
juntaron para desarrollar lo que ellos esperaban fuese un standard para sistemas de paso de
mensajes. Que llamaron MPI. Existen una serie de implementaciones tales como, LAM,
MPICH, CHIMP, que son variaciones de MPI. Y UNIFY, que como se puede intuir, es un
suconjunto de MPI, y PVM.

5.7 PVM.

1L

En PVM, el programador descompone el problema en programas separados. Cada

programa escrito en C o FORTRAN, y compilado para ejecutarse en tipos especficos de
ordenadores en la red. Si la red contiene una coleccin homognea de ordenadores, los
programas solamente tienen que ser compilados una vez para ese tipo de ordenador. En una
red de ordenadores, cada estacin de trabajo tiene acceso al sistema de ficheros conteniendo
los programas compilados. Es necesario, solamante, asegurar que los programas ejecutables
existen para las estaciones de trabajo especficas que ejecutarn el programa.
PVM, permite cualquier nmero de procesos a ser creados, sin cualquier relacin al
nmero de procesadores, y situar los procesos automticamente.

5.7.1 Creacin y ejecucin de procesos.

1L

Los procesos se pueden empezar dinmicamente. Los programas PVM, son

generalmente organizados en un orden maestro-esclavo, por lo cual, el nico programa

28

maestro es ejecutado primero, y todos los dems son producidos desde este proceso master.
(Es posible producir procesos, que a su vez produzcan otros). Los procesos se identifican,
con un ID de tarea.

5.7.2 Rutinas bsicas de paso de mensajes.

1L

Todas las rutinas de envo de PVM, son nonblocking, o asncronas en terminologa

de PVM. Mientras PVM recibe las rutinas, puede estar o blocking (sncronos) o
nonblocking. PVM, utiliza una etiqueta de mensaje (msgtag) adjuntos a un mensaje para
diferenciar estre tipos de mensajes a ser enviados. Si la informacin a ser enviada se
compone de varios tipos, la informacin ha de ser empaquetada dentro de un buffer, antes de
enviarse la informacin. Los procesos receptores deben desempaquetar su mensaje recibido
al formato en el cual ha sido empaquetado. El desempaquetado debe ser en el mismo orden
que el empaquetado. Muchas rutinas en PVM, devuelven informacin de si ha habido exito
o no en la llamada. Es buena prctica en la pogramacin, comprobar despus de tales
llamadas, si ha habido xito.
En PVM, las operaciones de broadcast, scatter, y gather, se realizan despus de que
se ha formado un grupo de procesos. Existe una llamada de librera, que realiza la formacin
de este grupo. La operacin de multicast, en PVM, no es una operacion de grupo.
Generalmente se utiliza para enviar los contenidos del buffer de envo de un conjunto de
procesos que estn definidos en un identificador de matriz.

5.8 MPI.

1L

MPI tiene un gran nmero de rutinas, sobre 120, y cada vez ms. Un factor
importante en el desarrollo de MPI, es el deseo de hacer del paso de mensajes, portable, y
fcil de usar. Algunos cambios fueron realizados, para corregir deficiencias tcnicas en los
sistemas de paso de mensajes iniciales, tales como PVM.
El gran nmero de funciones, incluso en la versin, es debido al deseo de incorporar
caractersticas que los programadores de aplicaciones puedan utilizar para escribir cdigo
eficiente. Sin embargo, los programas pueden ser escritos utilizando muy pocas llamadas, del
subconjunto de funciones disponibles. Como en PVM, las llamadas de funciones estn
disponibles tanto para C como para FORTRAN.

5.8.1 Creacin de y ejecucin procesos.

1L

Una diferencia significativa con PVM, es que el proceso de creacin puede ser
solamente esttico. Esto significa, que todos los procesos deben ser definidos antes de la
ejecucin, empezados juntos. La llamada que tiene PVM, para realizar la ejecucin de uno
o varios identicos, y que se soporta en las ltimas versiones de MPI, no debe ser utilizada,
porque se produce una sobrecarga de la creacin de procesos dinmicos.
Un programa puede ser escrito y ejecutado para varios procesadores. Este es el
modelo de computacin SPMD.

29

Inicialmente, los procesos son inscritos en un universo llamado

MPI_COMM_WORLD, y a cada uno de ellos se le facilita un nico rango, un nmero que
va de 0 a n-1, en donde n es nmero de procesos. En terminologa MPI,
MPI_COMM_WORLD, es un comunicador que define el alcance de una operacin de
comunicacin, y los procesos tienen rangos asociados con el comunicador.

5.8.2 Utilizando el modelo computacional SPMD.

1L

Este modelo es ideal, donde cada proceso realmente ejecutar el mismo cdigo. El
modelo SPMD, no excluye el modelo maestro-esclavo, solo que tanto el cdigo maestro
como el del esclavo deben estar en el cdigo del mismo programa.
El modelo SPMD sera ineficiente en los requerimientos de memoria, si cada uno de
los procesadores fuese a ejecutar cdigo completamente diferente, pero afortunadamente
esto es inverosimil que sea requerido. Una ventaja de este modelo, es que los argumentos de
la lnea de comandos, pueden ser pasados a cada proceso.

5.8.3 Las rutinas de paso de mansajes.

1L

Los comunicadores son utilizados en MPI, para todas las comuncaciones por paso de
mensajes colectivas y punto a punto. Un comunicador es un dominio de comunicacin que
define un conjunto de procesos, a los que se les permite comunicar entre ellos mismos. De
esta manera, el dominio de comunicacin de la librera puede ser separado de un programa
de usuario. Cada proceso tiene un rango dentro del comunicador, un entero de 0 a n-1,
donde hay n procesos. Existen dos tipos de comunicadores disponiles, un intracomunicador,
para comunicar dentro de un grupo, y un intercomunicador para comunicaciones entre
grupos. Un grupo se usa para definir una coleccin de procesos para estos propuestos. Un
proceso tiene un nico rango en un grupo, y un proceso podra ser un miembro de ms de
un grupo.

5.8.4 Comunicacin punto a punto.

1L

El estilo de empaquetar y desempaquetar de PVM, es generalmente evitado por el

uso de un tipo de dato de MPI definido en los parmetros junto con la fuente y el destino del
mensaje. El tipo de datos puede ser uno de una lista de tipos de datos standard o uno que el
usuario haya creado. Para eliminar la necesidad de empaquetar y desempaquetar, los tipos
declarados tienen la ventaja que puede ser reutilizado. No son requeridos tampoco, el envo
y recepcin de buffers.

5.8.5 Conclusin.

1L

Los conceptos de conclusin local, y global son utilizados para describir las
variaciones. Una rutina es localmente completa, si ha completado todas sus partes en la
operacin. Para que una rutina sea globlmente completa, todas las rutinas deben estar
localmente completas para la operacin que es globlmente completa.

5.8.6 Rutinas de tipo blocking.

1L

30

En MPI, las rutinas de bloqueo, (send, recv), regresan cuando estn loclmente
completas. La condicin de completitud local, para una rutina de envo es que la localizacin
utilizada para mantener el mensaje, pueda ser utilizada nuevamente o alterada, sin afectar al
mensaje que ha sido enviado. Un bloqueo de envo, enviar el mensaje, y regresar. Esto no
significa que el mensaje ha sido recibido, solo que el proceso es lire de reanudar sin afectar
de manera adversa al mensaje. Una rutina para recibir del tipo blocking, tambin volver
cuando sea localmente completa, lo cual en este caso significa, que el mensaje ha sido
recibido en la localizacin de destino y esta puede ser leida.

5.8.7 Rutinas de tipo Nonblocking.

1L

Una rutina nonlocking, devuelve inmediatamente, es decir, permite que se ejecute la

prxima instruccin, sea o no completada localmente. Esta clase de rutinas, suministran la
habilidad de poder solapar la comunicacin y el clculo, lo cual es esencial cuando los
retrados de comunicacin son altos.

5.8.8 Modos de Comunicacin de envo.

1L

Las rutinas de envo en MPI, pueden tener uno de los cuatro modos de comunicacin
que definen el protocolo de envo/recepcin. Los modos son standard, buffered, sncrono, y
listo.
En el modo de envo standard, no se asume que la correspondiente rutina de de
recepcin ha empezado. La cantidad del buffering, sihay, es dependiente de la
implementacin y no definido por MPI. Si se suministra uffering, el envo podra ser
completado antes de que la recepcin sea alcanzada.
En el modo buffered, el envo debe comenzar y regresar antes de una recepcin del
emparejamiento. Es necesario suministrar el espacio de buffer especfico en la aplicacin. El
espacio del buffer es suministrado por el sistema va MPI.
En el modo sncrono, el envo y la recepcin pueden empezar antes uno que el otro,
pero pueden ser completados solamente a la vez.
En el modo ready, un envo puede empezar solamente, si la recepcin del matchinh
ha sido ya alcanzada, de otro modo se alcanzar un error. Debe ser utilizado con cuidado
para evitar operaciones erroneas.

5.8.9 Comunicacin colectiva.

1L

La comunicacin colectiva tal como el broadcast a un conjunto de procesos, es

opuesta a la comunicacin punto a punto. MPI suministra rutinas de broadcast, y un rango
de rutinas del tipo scatter y gather. El comunicador define la coleccin de procesos que
participarn en la operacin.

31

Bibliografa
Artculos
1A. Survey of Parallel Computer Architectures. Febrero 1990. Pag. 5 -16.
2A. General-Purpose Systolic Arrays. Noviemre 1993. Pag.20 31.

Otros Artculos de Inters

Framework for Supporting heterogeneous-instruction-set architectures. Junio 1993.

Pag39 - 56.
Distributed Heterogeneous Supercomputing Management System. Junio 1993. Pag. 7886.
SIMD Parallel Processors: The Future Again?. Diciembre 1996. Pag. 152-151.
Shared Memory Consistency Models: A Tutorial. Diciembre 1996. Pag. 66-76.
TradMarks: Shared Memory Computing on Networks of Workstations. Febrero 1996.
Pag. 18-28.
Architectural parallelism used in low-and intermediate-level vision. Febrero 1992. Pag.
68-73.
Trends in Shared Memory Multiprocessing. Diciembre 1997. Pag. 44-50.
Billion-Transistor Architectures. Septiembre 1997. Pag. 46-48
Challenges and Trends in Processor Design. Enero 1998. Pag 39.
Increasing Work Pushing the Clock. enero 1998. Pag. 40-41.
An Efficient , Protected Message Interface. Noviembre 1998. Pag.69-75.

Libros
1L. Barry Wilkinson y Michael Allen. Parallel Programming. Techniques and
Aplications using networked workstations and Parallel Computers..
2L. R. N. Ibbett y N. P. Topham Architecture of High performance Computers.
Volumenes I y II.

Otros Libros de Inters

R. Michael Hord. Parallel Supercomputing in SIMD Architectures.

Harold S. Stone. High-Performance Computer Architecture.

32