Introducción a la Computación J. Aguilar, E.

Paralela Leiss

Capítulo 1.
Elementos Introductorios

1.1 Motivación
El procesamiento paralelo es un tipo de procesamiento de la información, que permite
que se ejecuten varios procesos concurrentemente [5, 10, 17, 30, 35]. El procesamiento
paralelo puede ser de diferentes tipos: i) Un tipo es ejecutar procesos independientes
simultáneamente, los cuales son controlados por el sistema operativo (usando tiempo
compartido, multiprogramación y multiprocesamiento). ii) Otro tipo es descomponer los
programas en tareas (controladas por el sistema operativo, los compiladores, los
lenguajes de programación, etc.), algunas de las cuales pueden ser ejecutadas en paralelo.
iii) Finalmente, el último tipo se basa en usar técnicas de encauzamiento para introducir
paralelismo a nivel de instrucciones, lo que implica dividirlas en pasos sucesivos que
pueden ser ejecutados en paralelo, cada uno procesando datos diferentes.

Es difícil determinar qué resulta más natural, sí el procesamiento paralelo o el

secuencial. Los enfoques paralelos resultan una necesidad, dada la constante afirmación
de que la velocidad máxima en procesamiento secuencial se alcanzará prontamente,
excepto que aparezcan avances en otras áreas que definan nuevos mecanismos de
procesamiento, los cuales pueden venir de nuevos descubrimientos en áreas tales como
computación AND, computación cuántica, etc. En los últimos años, el uso extensivo del
paralelismo ha estado ligada a varios hechos [2, 10, 13, 20]:

- La necesidad de mayor potencia de cálculo: independientemente de que la potencia

de los procesadores aumente, siempre habrá un limite que dependerá de la tecnología
del momento. Para aumentar la potencia de cálculo, además de los progresos
tecnológicos que permitan aumentar la velocidad de cálculo, se requieren nuevos
paradigmas basados en cálculo paralelo. Es decir, una manera de aumentar la
velocidad de cálculo es usar múltiples procesadores juntos. Así, un problema es
dividido en partes, cada una de las cuales es ejecutada en paralelo en diferentes
procesadores. La programación para esta forma de cálculo es conocida como
programación paralela, y las plataformas computacionales donde pueden ser
ejecutadas estas aplicaciones son los sistemas paralelos y distribuidos. La idea que se
usa es que al tener n computadores se debería tener n veces más poder de cálculo, lo
que conllevaría a que el problema pudiera resolverse en 1/n veces del tiempo
requerido por el secuencial. Por supuesto, esto bajo condiciones ideales que
raramente se consiguen en la práctica. Sin embargo, mejoras sustanciales pueden ser
alcanzadas dependiendo del problema y la cantidad de paralelismo presente en el
mismo.

1
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

- Una mejor relación costo/rendimiento: en el orden económico, es muy importante

tener máquinas con excelente relación costo/rendimiento. Normalmente, el mayor
poder de cálculo genera una explosión de costos que a veces lo hacen prohibitivo.
Una manera para lograr mayor poder de cálculo sin costos excesivos es hacer
cooperar muchos elementos de cálculo de bajo poder, y por consiguiente, de bajos
costos.
- Potencia expresiva de los modelos de procesamiento paralelo: muchos problemas
son más fáciles de modelar usando paradigmas paralelos, ya sea por la estructura que
se usa para su resolución o porque el problema es intrínsecamente paralelo. Es decir,
si desde el principio se puede pensar en los mecanismos paralelos/concurrentes para
resolver un problema, eso puede facilitar la implantación del modelo computacional.
Esto podría permitir obtener mejores soluciones para los problemas a resolver, en
tiempos razonables de ejecución. Así, este enfoque permite el surguimiento de
modelos de cálculos diferentes, a los modelos secuenciales. En pocas palabras,
además del procesamiento de paralelismo para mejorar los tiempos de ejecución se
agrega la ganancia conceptual, al poder resolver los problemas con nuevos métodos
de resolución hasta ahora imposibles de ejecutarse en máquinas secuenciales.

Así, la computación paralela está jugando un papel fundamental en el avance de todas

las ciencias, abriendo las puertas para explotar, más allá de las fronteras ya conocidas,
impresionantes poderes de cálculo que permiten modelos más realistas (pasar de la
segunda a la tercer dimensión, etc.). A pesar de que del área de computación paralela se
habla mucho, en realidad es poco lo que se conoce. Quizás el mayor problema en
computación paralela y distribuida es que no son ideas fáciles para entender e
implementar. Existen diferentes enfoques para aplicar paralelismo. Incluso, para ciertas
aplicaciones algunos enfoques pueden ser contraproducentes. Además, existen varios
tipos de arquitecturas, modelos de programación, lenguajes y compiladores, compitiendo
por conquistar el mercado. Por otro lado, actualmente los precios baratos de los PC, con
su incremento en poder de cálculo, los hacen un formidable competidor contra los
emergentes computadores paralelos. También las estaciones de trabajo, las cuales ofrecen
amigables y poderosas interfaces, son otras fuertes competidoras.

Hay muchas áreas de aplicación donde el poder de cálculo de una computadora

simple es insuficiente para obtener los resultados deseados. Las computadoras paralelas y
distribuidas pueden producir resultados más rápidos. Por ejemplo, en algunas áreas de
cálculo científico, el tiempo estimado de computación para obtener resultados
interesantes usando un computador simple, podría ser tan largo que excedería el tiempo
esperado en que el mismo puede fallar. O peor aun, en el área industrial una simulación
que tome algunas semanas para alcanzar resultados, es usualmente inaceptable en
ambientes de diseño, en los cuales los tiempos con los que cuenta el diseñador son cortos.
Además, hay ciertos problemas que tienen fechas límites especificas para calcularse (por
ejemplo, si el programa de predicción del tiempo para el día de mañana dura dos días
perdería el sentido ejecutarlo). Un punto inicial de arranque sería conocer qué áreas de
aplicación podrían beneficiarse al usar paralelismo. Indudablemente, el primer grupo
serían aquellas áreas donde el paralelismo es aparente, aunque no se pueda explotar en

2
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

máquinas secuenciales. A continuación se mencionan algunas áreas [2, 8, 9, 10, 13, 15,
16, 20, 33, 35]:

Procesamiento de imágenes: Con este término se pueden abarcar las transformaciones de

imágenes, análisis de imágenes, reconocimiento de patrones, visión por computadora,
etc. Existen dos aspectos básicos que hacen apropiado esta área para procesamiento
paralelo: el primero tiene que ver con la gran cantidad de datos que están envueltos en
el procesamiento. El segundo tiene que ver con la velocidad requerida para procesar
esas imágenes. A su vez, este segundo aspecto puede ser caracterizado por dos razones.
Primero, muchas aplicaciones de procesamiento de imágenes ocurren en ambientes
donde la tasa de procesamiento requerida tiene fuertes restricciones a nivel de tiempo.
En otras palabras, la velocidad de respuesta del sistema es crucial para el éxito de la
tarea que se esta llevando a cabo. La segunda gran razón es que el procesamiento de
imágenes usa estructuras de datos (y operaciones) intrínsecamente paralelas.

Modelado matemático: La computación juega un papel fundamental en las ciencias y las

ingenierías, permitiendo a los científicos e ingenieros construir y probar modelos con
nuevas teorías para describir fenómenos naturales o para resolver problemas de la vida
real. Estos modelos matemáticos altamente complejos son gobernados, por ejemplo, por
ecuaciones diferenciales parciales o elementos finitos cuyas soluciones pueden requerir
grandes poderes de cálculo. El modelado matemático consiste en describir entidades
(estructuras complejas, procesos químicos o biológicos, etc.) en términos de ecuaciones
que comprenden variables y constantes. Por ejemplo, para el diseño de la suspensión de
un carro su estructura puede ser aproximada por series de elementos planos (por
ejemplo, rectángulos, triángulos), cuyas propiedades mecánicas pueden ser descritas
por ecuaciones que tienen constantes (tal como la tensión del acero) y variables (tales
como la presión aplicada en ciertos puntos). Naturalmente, las variables pueden
depender en un punto dado de sus vecinas (los cuales a su vez son dependientes de sus
vecinas), tal que las ecuaciones que definen toda la estructura estén enlazadas. La idea
es aplicar sobre el modelo fuerzas externas, en forma tal que se pueda medir, por
ejemplo, su punto de ruptura. Es claro que para la estructura del carro, la exactitud de
los resultados depende de la fineza de los elementos modelados. Esto implica, que para
modelos complejos probablemente muchos miles de elementos se requieren usar. Otras
aplicaciones son en áreas tales como estudio de las interacciones de partículas en
materiales cristalinos o amorfos, cálculo de la estabilidad de partículas, física de
plasmas, mecánica cuántica, reacciones químicas, dinámica molecular, etc.

Computación inteligente: Existen muchos aspectos intrínsecamente paralelos en esta área.

Quizá el más significativo es que la computación inteligente trata de imitar el
comportamiento inteligente de los humanos, lo que hace pensar que para emular la
estructura intrínsecamente paralela del cerebro se requiere este tipo de procesamiento.
En el área de las redes neuronales artificiales, el procesamiento consiste en la
interacción de un grupo de neuronas cuyos elementos van describiendo la dinámica del
sistema. Aquí parece que las neuronas pueden aprovechar un procesamiento paralelo
para hacer más eficiente su tiempo de ejecución. A nivel de la computación evolutiva
existen muchos aspectos intrínsecamente paralelos, por ejemplo, el procesamiento

3
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

paralelo de cada individuo que conforma la población bajo manipulación. Así, el

procesamiento de los individuos (a nivel de su reproducción o evaluación) es
intrínsecamente paralelo.

Manipulación de base de datos: La idea de base es reducir el tiempo de ejecución al

asignar segmentos de las base de datos a elementos de procesamiento paralelo. Esto
pasa por definir las estructuras de datos adecuadas y las operaciones transaccionales a
realizar.

Predicción del tiempo: Ésta es un buen ejemplo de una aplicación que requiere mucho
poder de cálculo. Esta aplicación podría haber sido incluida en el grupo de las
aplicaciones con modelos matemáticos complejos, pero ésta tiene un segundo elemento
clave, la rapidez con que se deben realizar sus cálculos. La atmósfera es modelada
dividiéndola en regiones o celdas de tres dimensiones, usando ecuaciones matemáticas
complejas para capturar varios efectos. Básicamente, las condiciones en cada celda
(temperatura, presión, humedad, velocidad y dirección del viento, etc.) son calculadas
en intervalos de tiempo, usando las condiciones existentes en intervalos de tiempo
previos. Los cálculos en cada celda son repetidos para modelar el paso del tiempo. La
característica clave que hace eficiente esta aplicación es el número de celdas que use.
Supongamos que la atmósfera terrestre la quisiéramos dividir en celdas de 1.6
Km*1.6Km*1.6Km, así cada 16 Km. requieren 10 celdas. Para cubrir toda la atmósfera
terrestre se requeriría aproximadamente de 5x10 8 celdas. Supongamos que cada cálculo
en un cubo requiere 200 operaciones de punto flotante. Solamente para un intervalo de
tiempo se requeriría 1011 operaciones de punto flotante. Si quisiéramos predecir el
tiempo de los próximos 10 días con intervalos de tiempo de 10 minutos, se necesitarían
103 pasos y 1014 operaciones de punto flotante. Un computador a 100 Mflop (108
operaciones de punto flotante/segundo) tomaría 10 6 segundos para ejecutar el cálculo.
Para ejecutarlo en tiempos cortos se requeriría de más de 1 teraflops (1x1012
operaciones de punto flotante por segundo).

Otras áreas que podrían aprovecharse de un procesamiento paralelo son las siguientes:
biología, ciencias aerospaciales, sismología, diseño de VLSI, robótica, previsión
(modelado socioeconómico, etc.), exploración (oceanografía, astrofísica, geología, etc.),
máquinas inteligentes (planificación, sistemas expertos, mecanismo de aprendizaje, etc.),
medicina (tomografía, síntesis de proteínas, etc.), automatización industrial, aplicaciones
militares y multimedia, investigación y diseño farmacéutico, en áreas donde se han
establecido bien los modelos de computación en dos dimensiones tal que en un futuro
próximo tiendan a tres dimensiones para mejorarlos y puedan parecerse más al mundo
real, etc. Las características genéricas de estas aplicaciones son las siguientes: requieren
enormes cálculos repetidos sobre grandes cantidades de datos para obtener resultados
válidos, y el cálculo debe terminarse en un período de ejecución razonable. Esto implica
que para atacar estos problemas se requiere de hardwares rápidos y softwares eficientes.

Durante varios años, científicos e ingenieros han estado confrontándose con máquinas
paralelas. Los usuarios han visto como un reto usar estos sistemas, algunas veces
teniendo muchos éxitos al usarlas, pero frecuentemente frustrados por las dificultades

4
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

para obtener buenos resultados. Parte de los elementos que pueden extender el uso de
estas máquinas son [22, 24, 35, 36, 37]:

- Programación familiar: programas para estas plataformas deben ser escritos en

lenguajes familiares, o variaciones fáciles de entender.
- Estabilidad de rendimiento: los rendimientos deben ser estables, tal que la tasa de
cálculo no varíe mucho entre un computador y otro.
- Portabilidad: el código debe ser fácil de mover entre máquinas.

Mucho esfuerzo se requiere en el desarrollo de software para estas plataformas, más

que en la proposición de elementos de hardware eficientes. Así, a nivel de software del
sistema es donde se concentran los grandes retos en la actualidad, tanto a nivel de
desarrollo de sistemas operativos, compiladores, como de librerías de programación.
Algo importante para orientar futuros diseños es que los usuarios aceptan más fácilmente
cambios en su software, que cambiar a nuevos productos, aun cuando sean
revolucionarios. En pocas palabras, prefieren una evolución en sus herramientas de
software a nuevos productos diferentes a los ya conocidos, por mejores que sean. Un
clásico ejemplo es a nivel de Fortran, a través de los años, los científicos han preferido
adaptar sus códigos a las extensiones que se les han ido incorporando a éste, que pasar a
nuevos lenguajes de programación.

Algunos de los actuales problemas en esta área son [2, 13, 22, 24, 34, 35, 36, 37, 40]:

- La latencia: la latencia de una máquina paralela es más grande que la de una máquina
secuencial. Esto es debido a la propia arquitectura (memoria distribuida, manejo de
copias locales que implican problemas de coherencia, etc.). La sola forma de
resolverlo es optimizando el uso de la plataforma (por ejemplo, usando esquemas de
pre-paginacion en la memoria, protocolos de coherencia global, etc.). Quizás los hilos
de ejecución pueden ser otra fuente de ayuda para reducir el problema de latencia.
- Los anchos de banda: muchas redes de interconexión se han diseñados (mallas, etc.),
algunas con terribles rendimientos y problemas de conflictos.
- La determinación de los mecanismos de control de ejecución paralela: SIMD (Single
Instruction-Multiple Data) y MIMD (Multiple Instruction-Multiple Data) han estado
compitiendo estos últimos años, pero como se ha visto SIMD puede sobrevivir para
casos específicos y MIMD es más general.
- La capacidad de acceso a los datos: los mecanismos de pase de mensajes o memoria
compartida tienen una repercusión directa en el rendimiento del sistema. En
particular, el problema de direccionamiento de memoria en cada estilo envuelve
diferentes mecanismos en hardware y software, así como específicos estilos de
programación y lenguajes.
- Los modelos de programación: muchas proposiciones se han hecho sobre cómo
pensar en programas paralelos. Los modelos van desde proposiciones de diseño con
un bajo nivel de sincronización entre instrucciones, hasta modelos que permiten que
el código secuencial se ejecute automáticamente en paralelo. Algunos lenguajes de
programación se han ido modificando (por ejemplo, HPF) para aprovechar el
rendimiento exhibido por las máquinas paralelas. Pero así como muchos idiomas y

5
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

dialectos han sobrevivido, modelos de programación, lenguajes y estilos no

convergerán en uno, ni hay razón para que así sea, ya que cada uno responde a una
necesidad diferente.
- Los Compiladores y Sistemas Operativos: una eficiente explotación de una
plataforma paralela pasa por mejores compiladores y sistemas operativos. A pesar de
que sustanciales mejoras se han hecho, aun se requieren más; en particular, para
manejar grandes cantidades de datos de manera paralela en la jerarquía de memoria,
en tareas de planificación (por ejemplo, para lazos de ejecución), entre otras.

Es razonable pensar que la naturaleza humana vislumbre nuevas aplicaciones que

excedan las capacidades de los sistemas computacionales. Por ejemplo, las actuales
aplicaciones de realidad virtual requieren considerables velocidades de cálculo para
obtener resultados interesantes en tiempo real. Esto nos refleja la necesidad permanente
de realizar estudios sobre nuevos esquemas de optimización en el ámbito computacional.

1.2 Historia
Grandes progresos en los sistemas computacionales se han hecho en estos últimos 55
años. La velocidad de los computadores secuenciales ha crecido en órdenes de magnitud
inimaginables debido a avances a nivel de sus diseños y en las técnicas usadas para
construirlos. También, mucho software se ha desarrollado y estandarizado (por ejemplo,
el sistema operativo UNIX). Pero a nivel de supercomputadores, desde los CRAY 1 de
1970 con sus 12.5 ns de periodos de reloj, apenas se pudo mejorar a 4 ns en 15 años. Sólo
ha sido posible mantener mejores rendimientos en las supercomputadoras, al introducir
paralelismo en la arquitectura del sistema. De esta manera, en vez de estar atados a los
constantes progresos a nivel de la tecnología de hardware como en el pasado, los
computadores de alto rendimiento están ahora más ligados a innovaciones arquitectónicas
y a nivel de software [3, 6, 13, 17, 25, 34].

En general, los avances en tecnología computacional se pueden dividir en los

realizados en la era secuencial, y los que están sucediendo ahora en la era de paralelismo
(ver figura 1.1). Además, cada una de ellas se puede dividir en 3 fases, una arquitectónica
que tiene que ver con los avances en el hardware del sistema, y dos fases de software, una
que tiene que ver con los compiladores (pasando de los lenguajes de alto nivel a los
compiladores que optimizan los programas para reducir los tiempos de ejecución) y otra
con las librerías/paquetes de aplicaciones (que liberan a los usuarios de escribir ciertas
partes de código) [3, 6, 13, 17, 25, 34]. Además, cada fase se divide en tres partes:
investigación y desarrollo (fase de mucho trabajo teórico y científico, aun sin un uso
extendido), comercialización (fase en la que las compañías del área construyen y
comercializan los productos) y expansión/consolidación (fase en la cual deja de ser un
tópico caliente de investigación, los precios empiezan a ser accesibles para los usuarios, y
los productos son fáciles de hacer a nivel industrial).

6
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Investigacion y
Desarrollo
Comercializacion

Expansion
Arquitecturas
Era
Compt. Compiladores
Secuencial
Aplicaciones

Arquitecturas
Era
Compt. Compiladores Aplicaciones
Paralela

1940
50 60 70 80 90 2000 10 20 30

Figura 1.1. Eras de la Computación

En los años 50 ocurrieron los primeros intentos de construcción de máquinas

paralelas, pero es hasta los 60-70 que se construyen las primeras. La mayoría de esas
máquinas eran máquinas vectoriales mono-procesadoras. A partir de los 70 surgieron las
máquinas vectoriales multiprocesadoras. Todas disponían de una memoria compartida,
pero eran muy caras. Además, el número de procesadores no llegaba a ser más de 16. A
continuación un breve resumen [5, 10, 16, 17, 18, 20, 26, 27, 30, 35]:

- En 1950 Von-Neumann considera analogías entre computador-cerebro y propone un

modelo de cálculo paralelo.
- Muchos computadores en los 50 usan procesamiento paralelo en operaciones
aritméticas. Por ejemplo, en 1956 Stephe Viger en la Universidad de Columbia
propone un arreglo de procesadores compartiendo la memoria, y en 1958 J. Holland
en la Univ. de Michigan escribió sobre cómo programar un arbitrario número de
subprogramas simultáneamente. Además, a Gil se debe la primera publicación
científica en el área al describir sobre cómo debería ser la programación paralela.
- En 1960 Westinghouse Electric construye Solman, una máquina paralela bit-send.
- De los 60 a los 70 hay varios proyectos. Se desarrolla Illiac IV en la Universidad de
Illinois el cual consiste de 64 procesadores. Bell Labs desarrolla PEPE para
procesamiento de senales de radares. Esta arquitectura consistía de un computador
central que controlaba el arreglo de procesamiento paralelo, ya que la aplicación
requería interacción entre diferentes hilos de procesamiento. En los 70 ICL diseño y
construyo Dap, el cual era una memoria asociativa.
- A mediados de los 70 aparece CRAY 1, cuya arquitectura era la de un vector de
instrucciones que operaba sobre un vector de 64 palabras. Además, podía realizar la
más rápida operación escalar disponible para la época. En los 80 aparecen CRAY X-
MP y Y-MP, que mejoraban a CRAY 1 al dar adicional bandas de datos de memoria,
manejar vectores espaciados eficientemente y mejorar el software del sistema.
Además, a diferencia de CRAY 1 compuesto de un simple procesador, ahora se podía
contar con 2, 4, 8 o 16 procesadores.

7
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

- En los 80 aparecieron las estaciones de trabajo que eran solamente dos veces más
lentas que los CRAY y más baratos. Además, las colas para ejecutar programas en
CRAY eran inmensas (perdiéndose mucho tiempo por eso), con tiempos de ejecución
costosísimos.
- A finales de los 80 aparecen los sistemas masivamente paralelos de INTEL, nCUBE,
Thinking Machines, etc. como una nueva tendencia diferente a los
supercomputadores vectoriales o paralelos tradicionales (CRAY, etc.).
- Actualmente, hay una gran extensión de nuevos dominios de aplicaciones, por
ejemplo, los nuevos desarrollos en Bases de Datos (Oracle en NCube, etc.). Además,
en 1994 IBM asumió un unificado enfoque al unir y conectar sus mainframes y
sistemas desktop. Así, hoy en día se presentan nuevas arquitecturas basadas en
procesadores poderosos con diferentes tecnologías de interconexión, que dan una
diversidad de facilidades a los diferentes tipos de aplicaciones.

Un hecho resaltante es que en cada década la computación paralela ha ofrecido el más

alto nivel de rendimiento, al compararla con los otros sistemas disponibles para ese
momento (ver tabla 1.1) [3, 5, 8, 10, 16, 20, 27, 30, 35]. El hardware usado para
desarrollar computadores paralelos ha cambiado durante cada década, en los 60 se usaba
la tecnología más avanzada, lo que resultaba costoso y difícil de construir. En los 70
aparecieron más facilidades para construir computadores paralelos. Ya en los 80, con el
uso de los microprocesadores y buses de comunicaciones, el hardware para
procesamiento paralelo se abarató, y muchas compañías y universidades han podido
construir el suyo. Este hecho se ha extendido durante la década de los 90. Pero un detalle
curioso es que su uso masivo ha estado frenado por falta de software eficiente para estas
plataformas.

Relativo a la Epoca
Décadas Máquinas Velocidad Tecnología Calidad del
Paralelas Pico de hardware Software
1960 PEPE, etc. Alta Alta Baja
1970 DAP, etc. Alta Media Baja
1980 Hipercubos, Alta Media/Baja Baja
etc.
1990 SP2, etc. Alta Baja Baja

Tabla 1.1 Rendimientos de las Máquinas Paralelas con respecto a la época.

1.3 Clasificaciones
Los computadores paralelos se han desarrollados estos últimos años gracias a los avances
en campos tan diversos como el arquitectónico, las tecnologías de interconexión, los
ambientes de programación (lenguajes, sistemas, etc.), como de otros más. Muchos
esquemas de clasificación se han propuesto, pero el más popular es la taxonomía de
Flynn, la cual se basa en la manera como se organiza el flujo de datos y de instrucciones.

8
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Sin embargo, existen otros criterios que se podrían usar para establecer una clasificación
a nivel de la programación paralela: el modo operacional de los procesadores, la
organización de la memoria, la granularidad de los procesadores, las características de la
arquitectura. Así, otras clasificaciones han sido propuestas basadas en otros criterios,
algunas de ellas son las de Feng, Kuck, Gajskim Treleaven, etc. Presentaremos aquí a la
de Flynn, y mencionaremos otras para tratar de mostrar las arquitecturas paralelas hasta
ahora conocidas [5, 10, 13, 16, 17, 18, 27, 30, 32, 34, 40].

1.3.1 Clasificación de Flynn

La taxonomía de Flynn es la clásica clasificación usada en computación paralela, la cual

usa ideas familiares al campo de la computación convencional para proponer una
taxonomía de arquitecturas de computadores. Esta es una de las más viejas, pero es la
más conocida hasta nuestros días. La idea central que se usa se basa en el análisis del
flujo de instrucciones y de datos, los cuales pueden ser simples o múltiples, originando la
aparición de 4 tipos de máquinas. Es decir, esta clasificación está basada en el número de
flujos de instrucciones y de datos simultáneos que pueden ser tratados por el sistema
computacional durante la ejecución de un programa. Un flujo de instrucción es una
secuencia de instrucciones transmitidas desde una unidad de control a uno o más
procesadores. Un flujo de datos es una secuencia de datos que viene desde un área de
memoria a un procesador y viceversa. Se pueden definir las variables n i y nd como el
número de flujos de instrucciones y datos, respectivamente, los cuales pueden ser
concurrentemente procesados en un computador. Según eso, las posibles categorías son:

SISD (Single Instruction Stream, Single Data Stream)

Esta representa la clásica máquina de Von-Neumann, en la cual un único programa es

ejecutado usando solamente un conjunto de datos específicos a él. Está compuesto de una
memoria central donde se guardan los datos y los programas, y de un procesador (unidad
de control y unidad de procesamiento), ver figura 1.2. En este caso, n i = nd =1. En esta
plataforma sólo se puede dar un tipo de paralelismo virtual a través del paradigma de
multitareas, en el cual el tiempo del procesador es compartido entre diferentes programas.
Así, más que paralelismo lo que soporta esta plataforma es un tipo de concurrencia. Los
PC son un ejemplo de máquinas que siguen este tipo de procesamiento.
Memoria Central

Datos Instrucciones

Unidad de Unidad de Control

Comandos
Datos Procesam. (UP) (UC)

Procesador

Figura 1.2. Arquitectura tipo SISD (Máquina Von-Neumann).

9
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

SIMD (Single Instruction Stream, Multiple Data Stream)

Arreglo de elementos de procesamiento, todos los cuales ejecutan la misma instrucción al

mismo tiempo. En este caso, n i =1 y nd > 1. El enfoque de paralelismo usado aquí se
denomina paralelismo de datos. Los arreglos de procesadores son típicos ejemplos de
esta clase de arquitectura. En estas arquitecturas, un controlador recibe y decodifica
secuencias de instrucciones a ejecutar, para después enviarlas a múltiples procesadores
esclavos. El arreglo de procesadores procesa los datos que llegan a los diferentes
procesadores, usando la instrucción enviada por el controlador. Los procesadores están
conectados a través de una red. Los datos a tratar pueden estar en un espacio de memoria
que es común a todos los procesadores o en un espacio de memoria propio a cada unidad
de procesamiento (ver figura 1.3). Todos los procesadores trabajan con una perfecta
sincronización. SIMD hace un uso eficiente de la memoria, y facilita un manejo eficiente
del grado de paralelismo. La gran desventaja es el tipo de procesamiento (no es un tipo de
procesamiento que aparece frecuentemente), ya que el código debe tener una dependencia
de datos que le permita descomponerse.

Su funcionamiento es el siguiente: un simple controlador envía las instrucciones, una

a una, a un arreglo de procesadores que operan en el esquema maestro-esclavo. Es decir,
las instrucciones son difundidas desde la memoria a un conjunto de procesadores. Así,
cada procesador es simplemente una unidad aritmética-lógica y se tiene una sola unidad
de control. Todos los procesadores ejecutan cada operación recibida al mismo tiempo,
por lo cual, cada uno ejecuta la misma instrucción sobre diferentes datos. Los sistemas
modernos SIMD tienen un CPU adicional para procesamiento escalar, de tal manera de
mezclar operaciones entre el arreglo de procesadores y el procesador secuencial estándar;
esto es debido a que en la mayoría de las aplicaciones paralelas se tienen fases de código
secuencial y de código paralelo. De esta forma, la parte de código secuencial es ejecutado
en el CPU adicional. Esto también implica dos procesos diferentes para mover los datos
entre el arreglo de procesadores y el procesador secuencial: en un caso se difunden los
datos desde el procesador secuencial al arreglo de procesadores; en el otro caso, al
moverse los datos del arreglo de procesadores al procesador secuencial, los datos son
reducidos.

Para el programador pareciera que se ejecutara su programa de manera secuencial,

con la diferencia de que sus intrucciones se ejecutan de manera múltiple sobre diferentes
datos y no una sola vez (por lo que para el usuario sigue siendo una máquina secuencial
desde el punto de vista de la programación). Este tipo de plataforma computacional se ha
desarrollado debido al gran número de aplicaciones científicas y de ingeniería que se
adaptan bien a él (procesamiento de imágenes, simulación de partículas, métodos de
elementos finitos, sistemas moleculares, etc.), en las cuales se tiene una simple secuencia
de instrucciones, operando al mismo tiempo sobre un conjunto de datos. Un ejemplo de
máquina que trabaja bajo este enfoque es la CM-2.

10
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Memoria Central

Instrucciones Datos

UC UP 1 ... UP 2

Comandos

Figura 1.3. Arquitectura tipo SIMD.

MISD (Multiple Instruction Stream, Single Data Stream)

Estas son computadoras con elementos de procesamiento, cada uno ejecutando una tarea
diferente, de tal forma que todos los datos a procesar deben ser pasados a través de cada
elemento de procesamiento para su procesamiento (ver figura 1.4). En este caso, ni > 1 y
nd = 1. Implementaciones de esta arquitectura no existen realmente, excepto ciertas
realizaciones a nivel de mecanismos de procesamiento tipo encauzamiento (pipelining en
ingles) (internamente en los procesadores RISC, etc.) o sistemas de tolerancia a fallas.
Muchos autores consideran que esta clase no corresponde a un modo de funcionamiento
realista. Otros autores consideran que representan el modo de procesamiento por
encauzamiento.

La idea es descomponer las unidades de procesamiento en fases, en donde cada una

se encarga de una parte de las operaciones a realizar. De esta manera, parte de los datos
pueden ser procesados en la fase 1 mientras otros son procesados en la 2, otros en la tres,
y así sucesivamente. El flujo de información es continuo y la velocidad de procesamiento
crece con las etapas. Este tipo de clasificación de Flynn puede ser incluida dentro de la
clasificación SIMD si se asemeja el efecto de estas máquinas, al tener múltiples cadenas
de datos (los flujos) sobre las etapas de procesamiento, aunque también puede ser visto
como un modo MIMD, en la medida de que hay varias unidades y flujos de datos y cada
etapa está procesando datos diferentes.

Memoria Central
Datos Instrucciones
UC
UP
Etapa 1

Etapa 2
Datos ... ...
Etapa n
Comandos

Figura 1.4. Arquitectura tipo MISD.

11
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

MIMD (Multiple Instruction Stream, Multiple Data Stream)

Es el modelo más general de paralelismo, y debido a su flexibilidad, una gran variedad de

tipos de paralelismo pueden ser explotados. Las ideas básicas son que múltiples tareas
heterogéneas puedan ser ejecutadas al mismo tiempo, y que cada procesador opere
independientemente con ocasionales sincronizaciones con otros. Está compuesto por un
conjunto de elementos de procesamiento donde cada uno realiza una tarea, independiente
o no, con respecto a los otros procesadores. La conectividad entre los elementos no se
especifica y usualmente se explota un paralelismo funcional. La forma de programación
usualmente utilizada es del tipo concurrente, en la cual múltiples tareas, quizás diferentes
entre ellas, se pueden ejecutar simultáneamente. En este caso, n i > 1 y nd > 1. Muchos
sistemas de multiprocesadores y sistemas de múltiples computadores están en esta
categoría. Un computador MIMD es fuertemente acoplado si existe mucha interacción
entre los procesadores, de lo contrario es débilmente acoplado.

Las MIMD se pueden distinguir entre sistemas con múltiples espacios de direcciones
y sistemas con espacios de direcciones compartidos. En el primer caso, los computadores
se comunican explícitamente usando pase de mensajes entre ellos según una arquitectura
NUMA (non-uniform memory access). En el segundo caso, al usarse una memoria
centralizada, se trabaja con modelos UMA. En el primer caso se habla de MIMD a
memoria distribuida y en el otro de MIMD a memoria compartida. Por el problema de
gestión del acceso concurrente a la información compartida, se origina un cierto no
determinismo en las aplicaciones sobre estas plataformas.

1.3.2 Modelo Basado en la Organización de la Memoria

La clasificación anterior no permite distinguir la organización interna de la memoria, por

lo cual la taxonomía de Flynn deja por fuera cierta clase de máquinas. En esta sección
tratamos de dar una clasificación que cubra a estas máquinas [3, 24, 35, 37]. Para eso,
presentaremos una clasificación en la cual combinamos los modos de funcionamiento
paralelos más comunes de la taxonomía de Flynn (SIMD y MIMD), con los tipos de
organización de la memoria (Memoria Compartida (SM) y Memoria Distribuida (MD)).

SIMD-Memoria Compartida:

Se caracteriza por un control centralizado y datos centralizados. Las máquinas clásicas de

este tipo son las máquinas vectoriales mono-procesadores con encauzamiento. Su
funcionamiento es el siguiente: se realiza una única operación (por ejemplo, la adición)
sobre un conjunto de datos múltiples (por ejemplo, dos vectores escalar). Las operaciones
se realizan de manera secuencial pero bajo un modo de funcionamiento de encauzamiento
(ver figura 1.3).

12
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

SIMD-Memoria Distribuida:

Estas máquinas se caracterizan por un control centralizado y los datos distribuidos (ver
figura 1.5). Normalmente, los procesadores de estas máquinas son de bajo poder, y la
potencia de cálculo de la máquina paralela es obtenida por el gran número de
procesadores usados. En esta arquitectura, cada procesador tiene una memoria local
pequeña y recibe las instrucciones de una unidad de control central para ejecutar la
misma instrucción, conjuntamente con el resto de procesadores, de manera sincronizada.

Mem. Mem. Mem. Mem.

Local Local Local Local
Datos Datos
...
UP UP UP UP

Comandos UC

Figura 1.5. Arquitectura tipo SIMD-Memoria Distribuida.

MIMD-Memoria Compartida:

En esta arquitectura, el conjunto de procesadores comparte la misma memoria (ver figura

1.6). Cada procesador puede ejecutar una instrucción diferente y el acceso a la memoria
se hace a través de una red de interconexión. La memoria se puede dividir en varios
bancos, y en un momento dado, un banco puede solamente ser accesado por un
procesador. Este tipo de máquina se desarrolló mucho en los años 80, pues llevar un
código secuencial para ser ejecutado en este tipo de máquina resulta muy fácil. La
complejidad de la red de interconexión aumenta rápidamente al aumentar el número de
procesadores, ya que todos deben poder accesar de manera eficaz todos los bancos de
memoria, lo que limita su uso a un número reducido de procesadores. Por poseer pocos
procesadores, se usan poderosos procesadores, de tal manera que la potencia de la
máquina paralela está dada por la potencia de los procesadores más que por el número de
ellos.

Como se dijo antes, el controlador y el proceso son replicados (cada uno se llama
nodo), mientras existe una única memoria compartida por todos los nodos. La conexión
entre los procesadores y la memoria es a través de la red de interconexión y se usa un
espacio de direcciones simples, lo cual indica que cualquier localidad de memoria es vista
como una única dirección y esta dirección es usada por cada procesador para accesar la
localidad. Una gran ventaja de este enfoque es que no hay que modificar los programas
secuenciales en cuanto al acceso a memoria. Programar en estas plataformas implica
tener los procesos y sus datos en el espacio de memoria compartida entre los
procesadores. Eso también permite la posibilidad de compartir variables y secciones de
código entre las aplicaciones. El problema de sincronización es el problema típico de
compartir recursos que también se encuentran en las máquinas secuenciales. Así, la

13
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

introducción de hilos, mecanismos de sincronización (exclusión mutua, etc.), manejo de

secciones críticas, etc., son cruciales en estas plataformas.

Uno de los problemas a resolver tiene que ver con la dificultad que tienen los
procesadores para accesar rápidamente a la memoria. Una forma de hacerlo consiste en
definir estructuras de memoria jerárquicas o distribuidas, lo que permite accesos físicos a
localidades de memoria cercanas a los procesadores (explotar la localidad de los datos).
Esto permite que se hagan más rápidos accesos que en el caso de localidades distantes de
memoria, lo que hace surgir nuevos problemas, como la coherencia de las memorias
(particularmente, de las memorias escondidas). El termino UMA (acceso uniforme a la
memoria) se usa en este caso, en oposición al acceso no-uniforme a la memoria (NUMA).

Memoria Central

Red de Interconexion
Datos Instrucc. Datos Instrucc.

UP
UP UC
...
UC Comandos
Comandos Procesador n
Procesador 1

Figura 1.6. Arquitectura tipo MIMD-Memoria Compartida.

La comunicación entre los procesadores se hace a través de la memoria, por lo que se

necesita una programación rigurosa a nivel de la organización de la memoria para evitar
conflictos de acceso a una misma localidad de memoria. El objetivo de rendimiento es
mover los datos a usar a la memoria antes de que sean requeridos y tiene que ver con el
hecho de que entre más cerca estén los datos del procesador, más rápido serán accesados.
El grave problema es a quién sacar y cuándo moverlo, de tal manera que cuando un
procesador los necesite, ya los datos estén en un sitio de acceso rápido. Como también se
dijo, la memoria puede ser dividida en módulos (bancos de memorias), cada uno con sus
canales de Entrada/Salida, de manera que cada módulo se conecte a los procesadores
usando una red de interconexión.

MIMD-Memoria Distribuida:

Este tipo de máquina se caracteriza por un control distribuido y una distribución de los
datos. Cada procesador es autónomo, con las mismas características de una máquina
secuencial. En este caso se replica la memoria, los procesadores y los controladores (ver
figura 1.7). Así, cada procesador tiene su memoria local. Los procesadores se pueden
comunicar entre ellos a través de una red de interconexión, la cual puede tener diferentes
formas. Esta arquitectura puede explotar la ventaja de las diferentes arquitecturas
presentadas (gran número de procesadores, los cuales pueden ser de gran poder). Los
procesadores se comunican por pase de mensajes. Los rendimientos de estas máquinas
están muy ligados a los rendimientos de las comunicaciones de las máquinas, y el

14
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

paralelismo a utilizar debe ser explícito, lo que hace requerir nuevos sistemas de
explotación y ambientes de programación.

Como la memoria local de cada procesador no puede ser accesada por otro
computador, la red de interconexión es usada para que los procesadores se comuniquen a
través de pase de mensajes (los mensajes incluyen datos, requerimientos, etc.). Programar
una aplicación para estos sistemas implica dividir el programa en tareas independientes,
algunas de las cuales podrán ser ejecutadas concurrentemente. En este caso se habla de
espacios de memorias locales, y la comunicación entre los procesadores se hace
explícitamente a través de pase de mensajes, usando la red de interconexión.

Red de Interconexion

Mem. Procesador ... Mem. Procesador

Computador 1 Computador n

Figura 1.7. Arquitectura tipo MIMD-Memoria Distribuida.

El componente central de esta arquitectura para un buen rendimiento, es la red de

interconexión. El tipo de configuración soportada y sus elementos varían increíblemente
(desde PC hasta procesadores RISC). Hay dos maneras para realizar las Entradas/Salidas:
cada procesador tiene su propio sistema de Entradas/Salidas, o se tiene una red de
Entradas/Salidas que se usa ya sea porque hay nodos servidores de Entradas/Salidas o las
unidades de Entradas/Salidas están directamente conectadas a la red. Entre sus ventajas
está lo fácil que crecen (tanto a nivel de tamaño de memoria, de ancho de banda, como de
poder de cálculo), que pueden emular los otros paradigmas (por ejemplo, una SIMD), y
que pueden compartir recursos y usar todos los avances en tecnología de computadores.
Su mayor desventaja es el ineficiente uso de la memoria y los problemas de
sincronización.

MIMD-Memoria Distribuida-Compartida:

Lo mejor de las dos arquitecturas anteriores se pueden combinar para diseñar una
máquina distribuida-compartida (ver figura 1.8). Es decir, se desea mantener el acceso a
la memoria uniforme sin los problemas de coherencia de memoria escondida (cache) ni
manejo de memoria virtual. Así, se logra un espacio de direcciones globales que facilita
la programación, con la facilidad de la construcción de las máquinas a memoria
distribuidas. La idea es que un procesador pueda accesar toda la memoria como si fuera
un simple espacio uniforme de memoria. Cuando un procesador necesita accesar una
localidad de memoria que está en otro procesador, ocurre un pase de mensajes que
esconde el hecho de que la memoria está distribuida, lo cual se conoce como memoria
virtualmente compartida. Por supuesto que los accesos remotos tomarán más tiempo que

15
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

los accesos locales. Para eso se agrega una capa de software al hardware de memoria
distribuida que permite a todos los procesadores acceder de manera transparente a toda la
memoria distribuida. Un acceso a una memoria no local es realizado por un envío de
mensajes generados por dicha capa, con el fin de realizar el acceso a distancia. El
programador puede usar un lenguaje de programación implícito usando la memoria
compartida o un lenguaje de programación explícito con pase de mensajes.

Nodo 0

P0 P1
.... Pn

Memoria Compartida

Red de Interconexion

Nodo 1
Nodo 2

P0 P1 .... Pn ....
P0 P1 Pn
Memoria Compartida
Memoria Compartida

Figura 1.8. Una posible arquitectura tipo MIMD-Distribuida-Compartida.

Una extensión natural a la taxonomía Flynn, en particular al modelo MIMD, es la

arquitectura MPMD (múltiples programas, múltiples datos), en la cual en vez de
instrucciones, son múltiples programas los que son ejecutados en diferentes sitios,
pudiendo ser algunos de ellos copias de otros. Otro modelo es la estructura SPMD
(Single Program, Multiple Data), que es un tipo derivado del modelo SIMD, pero a
diferencia de éste, es completamente asíncrono, donde se tiene una sola copia de un
programa, que es ejecutada sobre diferentes datos. En este caso, quizás diferentes
ramificaciones del programa se ejecutan en cada sitio, donde cada uno hace algo distinto
del mismo programa. Este caso es interesante, por ejemplo, cuando los datos no son
regulares.

1.3.3 Modelo Basado en la Coordinación

Hay dos métodos generales de coordinación en computación paralela: síncrono o

asíncrono [13, 18, 25, 26, 28, 29, 34, 39]. En el primer caso se obliga a que todas las
operaciones sean ejecutadas al mismo tiempo y se trata de hacer cumplir las
dependencias, en los órdenes de ejecución de las tareas para los diferentes programas. En
el segundo no existe tal restricción. A continuación presentaremos una clasificación
basado en esto.

16
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Arquitecturas síncronas:

Dentro de los computadores sincrónicos se pueden nombrar: vectores/arreglos, máquinas

SIMD y sistólicas. A continuación un listado de las máquinas síncronas:

a) Computador secuencial: Basado en la máquina de Von-Neumann, las instrucciones

son ejecutadas secuencialmente pero pueden ser encauzadas. Esta arquitectura incluye
una Unidad de Control, una Unidad Aritmética Lógica y una memoria (ver figura
1.2).

b) Arquitecturas encauzadas: El encauzamiento divide las operaciones a ejecutar en

pasos, los cuales son ejecutados unos detrás de otros. La entrada de una fase es la
salida de la precedente (en clasificación Flynn pertenecen a las arquitecturas MISD,
ya que la misma data es procesada por un flujo de sucesivas instrucciones
elementales). Así, el encauzamiento se basa en la descomposición de la operación (F)
en un conjunto de k operaciones (fases) Fi, tal que F= F1, … Fk. La idea de la
descomposición de F es que va realizando en secuencia el procesamiento de los datos
de entrada, tal que cada dato que llega a la entrada de F i, éste lo procesa y envía el
resultado al siguiente Fi+1. A cada unidad de procesamiento que procesa una parte de
los datos (un Fi), se le llama una fase, y todos los datos deben transitar las k etapas en
un orden especifico.

Para clarificar este concepto, consideremos la adición de dos números de puntos

flotantes en cuatro fases. Si se quisiera hacer la adición de n pares de números,
asumiendo que la suma entre ellos es lógicamente independiente, se podría planificar
la ejecución de las diferentes fases (F1, F2, F3, F4) de las n instrucciones (I1, ..., In)
para hacer ese cálculo, de la siguiente forma:

Relo Fase Ejecutada

j
1 F1 de I1
2 F1 de I2 F2 de I1
3 F1 de I3 F2 de I2 F3 de I1
4 F1 de I4 F2 de I3 F3 de I2 F4 de I1 I1
termina
...
n F1 de In F2 de In-1 F3 de In-2 F4 de In-3 In-3
termina
n+1 F2 de In F3 de In-1 F4 de In-2 In-2
termina
n+2 F3 de In F4 de In-1 In-1
termina
n+3 F4 de In In termina

Como se ve, se necesitan n+3 ciclos de reloj para terminar de ejecutar las n
instrucciones. En general, se necesitan n+k-1 ciclos de reloj para ejecutar n

17
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

instrucciones en k fases. Si se compara con el rendimiento de máquinas sin

encauzamiento, en este último caso se necesitarían kn ciclos de reloj para ejecutar n
instrucciones en k fases.

Ejemplo 1.1: Se quiere calcular f (x, y)  3x  . Los posibles subprocesos son añadir
yla raíz cuadrada del resultado final. Además,
x+y, multiplicar ese resultado por 3 y hallar
se tiene una gran cantidad de información a la cual se le debe dar ese procesamiento. A
cada subproceso se le asigna una unidad funcional y la salida de una unidad funcional se
conecta a la entrada de la otra de acuerdo al orden en que se deben hacer los cálculos. En
el momento 1, x1 y y1 son sumados en la unidad 1 dando z 1. En el momento 2 el resultado
de la suma de x1 y y1 (z1) se multiplica por 3 en la unidad 2, dando w1, y en paralelo, en
la unidad 1 x2 e y2 son sumados (z2). Este proceso sigue, y en un momento dado las tres
unidades están procesando diferentes xi, yi, zi y wi.

Aplicacion
Flujo de Flujo de
Entrada Salida

F0 F1 F2
datoi+4 F2(F1(F0(datoi)))

Tiempo
P0 P1 P2

T0
dato0 F0(dato0)
T1 F0(dato1) F1(F0(dato0))
dato1

T2 dato2 F0(dato2) F1(F0(dato1)) F2(F1(F0(dato0)))

T3 dato3 F0(dato3) F1(F0(dato2)) F2(F1(F0(dato1)))

T4 dato4 F0(dato4) F1(F0(dato3)) F2(F1(F0(dato2)))

Figura 1.9. Encauzamiento.

El uso de encauzamiento no acelera la ejecución de un solo dato, pero si de un

conjunto de datos. Sin encauzamiento, el tratamiento de datos seria T = n tn, donde
tn es el tiempo de procesamiento de cada uno de los n elementos, mientras que con
encauzamiento seria Te=(k+n-1)Timax, donde Timax = maxi(Ti) y Ti es la duracion de
cada fase. Si no se cumple que T e < T, no tendría sentido aplicar encauzamiento. El
tiempo (n-1)Timax es la latencia del encauzamiento, a partir del cual se producen
resultados cada Timax unidades de tiempo.

Discusión: Si suponemos que un encauzamiento ideal corresponde al hecho de que

cada fi necesita el mismo tiempo de cálculo T i = T/k (k siendo el número de fases), tal
que Ti max = max i(T i)= T/k, entonces la aceleración (ver en el capítulo 5 la expresión
de aceleración) seria:

k/(1+(k-1)/n)

18
 Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Para n=1 el factor de aceleración sería 1 (lo que confirma que no se puede
acelerar una operación escalar). Si n>>k entonces el factor de aceleración tiende a k y
el paralelismo será máximo. Así, el paralelismo máximo es determinado por el
número de etapas, tal que a más etapas es más importante las aceleraciones que se
pueden obtener. El termino (k-1)/n es el responsable de la degradación, ya que
corresponde al número de pasos iniciales del encauzamiento.

Entre los problemas de esta arquitectura, tenemos:

- Existe una latencia lineal asociada al sistema, que consiste en el tiempo entre cada
comienzo de procesamiento y cuando se obtiene el primer resultado.
- Cada problema debe definir su propia organización del encauzamiento (ya que el
tipo de subprocesos y el número de unidades requerido puede variar).

Una ventaja sería:

- Como el encauzamiento se basa en un procesamiento secuencial, no se requiere

cambios desde el punto de vista de la programación.

x=e*2p y=f*2p

1 comparar

2 sumar

3 normalizar

z=x+y

encauzado serial paralelo

x ,y x ,y x2,y2 x ,y
1 1 3 3
x ,y 1 1 1
1 1 1
1 1 x ,y 2 2 2 2
1 2 2
2 1 3 3 3 3
x3,y3 x ,y
3 1
2 1 2 2
3 2
2
3
3
x3,y3 1
2
3

Figura 1.10. Comparación entre procesamiento serial, encauzado y paralelo.

c) SIMD: varias unidades de procesamiento son supervisadas por la misma unidad de

control. Todos reciben la misma instrucción (o programa, si es una estructura SPMD)
de la unidad de control, pero trabajan sobre diferentes datos. Como cada unidad de
control ejecuta la misma instrucción al mismo tiempo, las operaciones operan
sincrónicamente (ver figuras 1.3 y 1.5).

d) Máquinas sistólicas: es un multiprocesador encauzado en el cual los datos son

distribuidos desde la memoria a los arreglos de vectores, y cada línea del arreglo (el
conjunto de arreglos) ejecuta la misma operación. Así que puede verse como una

19
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

mezcla de una máquina SIMD y encauzada. La eficiencia de este enfoque depende de

la regularidad de los datos y las fases, y se adapta bien para paralelismo de grano fino.
Este esquema se basa en el paradigma de programación basado en el paralelismo de
datos. La idea es que la data es impulsada/bombeada a través de estructuras de
cálculos paralelos de una manera regular similar.
b2,2
b2,1 b1,2
b2,0
b1,1 b0,2
b1,0 b0,1
b0,0 .
. .

a0,2 a0,1 a0,0 c0,0 c0,1 c0,2

a1,2 a1,1 a1,0 . c1,0 c1,1 c1,2

ciclo de
retrazo

a2,2 a2,1 a2,0 . . c2,0 c2,1 c2,2

Figura 1.11. Arreglo Sistólico en Multiplicación de Matrices.

En el ejemplo de esta figura se siguen los siguientes principios:

- El flujo de datos va solo en una dirección a través del arreglo.

- Cada elemento del arreglo ejecuta la misma operación.

En ese ejemplo, cada nodo (o procesador) tiene cuatro vecinos y el arreglo tiene la
forma de una malla. Los datos entran a cada nodo por dos de sus extremos (superior y
lado izquierdo) y se mueven a través del arreglo, donde cada procesador es visitado
por cada uno de los datos y pueden así ejecutar las operaciones para las cuales fueron
programados. De esta manera, el poder de cálculo del arreglo es aumentado ya que
actúa como un encauzamiento generalizado en dos dimensiones. Las operaciones en
cada procesador son muy simples y el movimiento de los datos a través de la malla es
sincronizado. En el caso particular de la multiplicación de matrices, cada procesador
multiplica los dos valores que le llegan y lo suma a un valor local que tiene
almacenado.

Arquitecturas asíncronas:

El ejemplo clásico son las máquinas MIMD donde cada procesador puede operar
independientemente de los otros. Los intercambios de información son hechos a través de
la memoria (SM) o enviando mensajes (DM).

Otra clasificación consiste en cómo se comunican los procesadores. Hasta los años
70, las arquitecturas tenían una memoria compartida por varios procesadores. Esto

20
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

generaba problemas de acceso a memoria. Varias soluciones se han dado: dividir la

memoria en bancos, introducir organizaciones jerárquicas de la memoria (memorias
“cache” (escondidas)), usar eficientemente las redes de interconexión, etc. Como se ha
dicho antes, otro tipo de máquina consiste en usar memorias descentralizadas donde los
procesadores tengan una conexión limitada (a un cierto número de procesadores).

1.4 Comunicación
Las máquinas paralelas se caracterizan por replicar algunos de sus componentes:
unidades de procesamiento, unidades de control, etc. Además, es muy raro que la
descomposición que uno haga de una aplicación en tareas, conlleve a que estas sean
completamente independientes entre ellas. En este caso se habla de dependencia de
tiempo, es decir, un procesador P1 debe culminar la ejecución de la tarea T1 antes que
otro procesador P2 pueda comenzar la ejecución de la tarea T2. Normalmente, ellas
deben comunicarse información para cumplir sus trabajos, ya sea:

- Compartiendo recursos: datos en la memoria compartida, etc.

- Por la transmisión de la información: envío de mensajes, etc.

En el primer caso se necesita conectar directamente los recursos compartidos (por

ejemplo, la memoria compartida) a los diferentes procesadores. Estos recursos a su vez se
pueden organizar de manera paralela (por ejemplo, partir la memoria compartida en
bancos). En el segundo caso se deben interconectar los procesadores entre ellos, para
poder intercambiar información. Así, en ambos casos se requiere de redes de
comunicación. Entre más grande es el número de componentes, más importante es la red
de interconexión. El problema en el diseño de redes de comunicación radica en la
densidad de comunicación que se requiere que ella soporte.

1.4.1 Pase de Mensajes

Supongamos que tenemos un conjunto de procesos con su propia memoria y datos. Los
datos son intercambiados entre los procesadores por medio de mensajes. El mensaje es
originado en un sitio (el procesador que envía), transmitido a través de la red de
interconexión, y recibido en otro lugar (el procesador receptor). Cualquier computador
puede actuar como receptor o puede enviar mensajes en un momento dado. Para el
sistema de pase de mensajes la red es un servidor, y de acuerdo a la ubicación del que
envía y del que recibe la operación de comunicación puede hacerse más rápida o no.
Muchos trabajos se han hecho sobre los sistemas de pase de mensajes para proveer redes
de interconexión con topologías eficientes, o librerías con rutinas optimizadas que
esconden los detalles de comunicación (PVM, MPI, etc.) [3, 21, 22, 37]. Básicamente, en
un sistema de pase de mensajes cada procesador debe:

- Conocer su dirección y la del resto de los procesadores de la red.

- Poder crear y enviar mensajes.

21
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

- Poder recibir mensajes, remover los datos del mensaje y manipularlos.

Además, las dos operaciones esenciales son:

Rutina de enviar: usada para transmitir un mensaje al nodo destino. Un mensaje es un

conjunto de bytes usualmente con la siguiente información: tamaño, nodo destino y dato.
La operación de envío se puede describir genéricamente como:

Enviar (buzón, tamaño, destinatario, tipo)

- Buzón, dirección en memoria donde está el inicio de la información a enviar.

- Tamaño: tamaño del mensaje a enviar. Así, la información a enviar se encuentra
desde la dirección inicial indicada antes, más el tamaño indicado aquí.
- Destinatario: a quien se enviara.
- Tipo: tipo de mensaje, para clasificar los mensajes desde el punto de vista de la
aplicación.

Rutina de recepción: es usada para recibir mensajes. Normalmente, cada nodo tiene una
cola de los mensajes a enviar y otra cola de los mensajes recibidos. Con una llamada a
esta rutina se elimina uno de los mensajes de la cola de recepción. La recepción puede ser
descrita como:

Recibir(buzón, tamaño, expedidor, tipo)

- Buzón, dirección en memoria donde está el inicio de la información a recibir.

- Tamaño: tamaño del mensaje a recibir. Así, la información a recibir se encuentra
desde la dirección inicial indicada antes, más el tamaño indicado aquí.
- Expedidor: de quien se recibe.
- Tipo: tipo de mensaje para clasificar los mensajes desde el punto de vista de la
aplicación.

En la ausencia de estas operaciones, no puede haber comunicación.

A este nivel se presentan nuevos problemas: por ejemplo, ¿Qué pasa si hay una
instrucción de recepción y aun no se tienen datos? Normalmente, el proceso que recibe se
debe bloquear (esperar) ya que debe tener una razón para recibir esos datos. Otra forma
es que no se bloquee, pero cada cierto tiempo revisa si llegó un mensaje, o a través de una
interrupción del sistema se avisa que llegó un mensaje. Otras capacidades que tiene este
sistema son las operaciones de difusión de mensajes (transmitir un valor a un conjunto de
sitios), las operaciones de reducción (por ejemplo, calcular la suma global de un conjunto
de valores que se encuentran dispersos en diferentes sitios) y las operaciones de
sincronización (una instrucción de ejecución no se puede pasar hasta que ella sea
alcanzada por el resto de procesos-o un grupo de ellos). En la realidad, las
implementaciones de las operaciones de reducción y sincronización son muy semejantes.
Diferentes paradigmas pueden usarse con los sistemas de pase de mensajes, por ejemplo,

22
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

en una máquina SPMD se usan mensajes para repartir los datos y comunicar resultados
parciales.

El envío de un mensaje involucra a un proceso emisor que realiza la operación de

envío y a un proceso destinatario que realiza la operación de recepción. Si las dos
operaciones se hacen al mismo tiempo se llama comunicación síncrona o rendez-vous. Es
parecido a las comunicaciones telefónicas en la cual los dos interlocutores deben estar
presentes al mismo tiempo. Si ambas operaciones se hacen en cualquier instante de
tiempo, se habla de comunicación asíncrona. Este caso es parecido cuando enviamos una
carta por correo a un destinatario dado. El destinatario puede haber estado esperando por
ella desde hace tiempo, o recogerla un tiempo más tarde cuando desee.

La comunicación síncrona se realiza cuando los dos procesos están listos para
comunicarse, lo que puede implicar tiempos de espera largos, pero permite asegurarle al
emisor que el mensaje llegará al destinatario. En el otro caso (asíncrono), el emisor envía
el mensaje cuando está listo para hacerlo, mientras que su recepción por parte del
destinatario se hará más tarde. Su ventaja es que el emisor no debe esperar, él envía y
sigue su ejecución. El receptor quizás deberá esperar, si el mensaje aun no ha llegado
cuando él llama la rutina de recepción, aunque como se dijo antes, existen otros modos de
operación para él. Este modo tiene tiempos de espera menores, pero el emisor nunca sabe
si el receptor recibe el mensaje.

Una extensión al modo de comunicación asíncrono son los modos de comunicación

con bloqueo o sin bloqueo. En el modo con bloqueo, al llamar la rutina de envío y de
recepción, estas operaciones se terminan cuando efectivamente se han realizado. La
operación de envío se termina cuando el mensaje sale del emisor, lo que no significa que
el mismo mensaje ya llegó al destinatario. En el caso de la rutina de recepción, ésta se
termina cuando el mensaje llega y es copiado en el buzón de recepción. En el modo sin
bloqueo se trata de disminuir el tiempo de espera de las primitivas, así, en ambos casos
las rutinas de envío y recepción requieren de una capa de software subyacente que se
encarga de enviar y recibir el mensaje cuando esté disponible, y de permitir que el
programa pueda continuar su ejecución. Este modo es interesante en los sistemas donde
se permite comunicación, y hacer cálculos, simultáneamente, lo que puede permitir
esconder los tiempos de comunicación. La dificultad de las operaciones sin bloqueo es
que el programador debe verificar que las operaciones se terminen en los tiempos
deseados. Además, debe también verificar si las dependencias existentes fueron
respetadas (ya que la noción de tiempo no es global).

Un último modo de comunicación es por interrupción, el cual es sólo válido en el

modo asíncrono. Es basado en un tipo de programación por evento, tal que cada vez que
llega un mensaje sobre un sitio se genera una interrupción a nivel de la aplicación.
También puede ser declarada en una aplicación a través de una instrucción
IRecibir(buzón, tamaño, expedidor, tipo, procedimiento), la cual solicita al sistema
operativo de llamar al procedimiento indicado cuando el mensaje llegue. Eso es una
declaración de interrupción, y cuando llega un mensaje su ejecución se interrumpe, el
mensaje se coloca en el buzón, y el control es pasado al procedimiento de interrupción.

23
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Al terminarse ese procedimiento el programa retoma su ejecución normal. Este esquema

es poco utilizado.

En general, existe un conjunto de primitivas de comunicación que ofrecen soluciones

a ciertos tipos de esquemas de comunicación, usados frecuentemente (al llamarse a una
de ellas, se ejecuta una serie de instrucciones predeterminadas). Las clásicas son las
siguientes [1, 4, 10, 11, 13, 15, 17, 20, 30, 33]:

- Transferencia: consiste en el envío de un mensaje de un procesador cualquiera a otro.

- Sincronización: el procedimiento asegura que todos los procesos lleguen a un punto
dado en sus ejecuciones, llamado punto de sincronización.
- Difusión: consiste en el envío del mismo mensaje desde un procesador especifico a
todos los otros.
- Distribución: es una difusión personalizada, es decir, el envío de un mensaje distinto
desde un emisor especifico a cada uno de los procesadores.
- Agrupamiento: consiste en la operación inversa de distribución. Así, un procesador
especifico recibe los mensajes distintos desde cada uno de los otros procesadores.
- Comunicación total: la idea es la siguiente, hay n personas y cada una conoce un
chisme, ellas empiezan a comunicarse para transmitirse el chisme hasta que todas
sepan todos los chismes. Así, cada uno de los n procesadores posee su propia
información, y al final del algoritmo, todos los procesadores conocen todas las n
informaciones diferentes.
- Transposición: es el caso en que cada procesador simultáneamente realiza una
distribución.
- Reducción: consiste en sintetizar en un dado procesador un dato d a partir de n datos
di enviados por los n procesadores. Normalmente, se usa una operación conmutativa y
asociativa, llamada operador de reducción, para realizar este proceso.

24
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

1.4.2 Exclusión Mutua

En las máquinas a memoria compartida, la forma de comunicarse dos procesadores es a

través de la memoria compartida entre ellos. Esto implica que se debe controlar el acceso
a la memoria para que dos o más procesos no accesen al mismo tiempo la misma
dirección de memoria y se creen así situaciones de inconsistencia (por ejemplo, datos
modificados simultáneamente por dos procesos distintos). La situación en la que dos
procesadores tratan de leer o escribir al mismo tiempo en la misma localidad de memoria
es conocida como condición de competencia. Una manera de resolver este problema es
usando un mecanismo ya conocido en los sistemas operativos, para máquinas
secuenciales, para compartir recursos y memorias en ambientes de multiprogramación, la
exclusión mutua, de tal forma de garantizar que cuando un proceso usa un espacio de
memoria nadie más lo esté usando. La parte de los procesos en la que se tiene acceso a la
memoria compartida se llama sección crítica, por lo cual se deben establecer los
mecanismo para que dos procesos dados no accesen al mismo tiempo su sección crítica
(así se evitará la condición de competencia).

Se han desarrollado muchos mecanismos, a nivel de lenguajes de programación y

sistemas operativos, para resolver este problema [1, 9, 11, 17, 37, 40]: desactivación de
interrupciones, alternancia estricta entre los procesos que requieren acceso, contadores de
eventos, monitores, semáforos, etc. Quizás los semáforos han sido los más usados en las
máquinas a memoria compartida, y la idea básica es que un semáforo puede tener un
valor 0 o mayor (si no hay procesos esperando) o un valor negativo igual al número de
procesos en espera. Existen dos operaciones atómicas que cada proceso puede realizar:

- La operación DOWN verifica si el valor del semáforo es mayor que 0, en cuyo caso lo
disminuye y continua. En caso contrario, se va a dormir (esperar o bloquearse).
- La operación UP incrementa el valor del semáforo correspondiente, y si uno o más
procesos dormían por ese semáforo (no pudieron completar la operación DOWN), el
sistema elige alguno de ellos (por ejemplo, en forma aleatoria), y le permite
desbloquearse y continuar (terminar su ejecución de la operación DOWN).

Usando esos mecanismos se puede controlar el acceso a las secciones críticas

fácilmente.

1.4.3 Redes de Interconexión

Las máquinas paralelas pueden clasificarse tomando en cuenta la conexión: si es directa

entre los procesadores (normalmente la red de interconexión es estática) o a través de
bancos de memorias compartidos (en este caso, la red de interconexión es generalmente
dinámica) [13, 17, 18, 25, 34]. Así, se identifican dos tipos de máquinas paralelas, cuyo
rol de la red de interconexión en cada caso es diferente. En el caso de la memoria
compartida, con uno o varios bancos de memoria, la red es usada para enlazar los bancos
de memoria con los procesadores; en el caso de la memoria distribuida, la red es usada
para enlazar los procesadores entre ellos.

25
Introducción a la Computación J. Aguilar, E.
Paralela Leiss

Memoria Compartida:

En las primeras computadoras a memoria compartida, todos los procesadores podían

acceder a toda la memoria. Por supuesto, esto generaba cuellos de botellas para acceder la
memoria. El siguiente paso fue dividir la memoria en bancos de memoria, lo que requería
una red de interconexión entre los procesadores y los bancos de memoria. Así, diferentes
procesadores podían acceder diferentes bancos al mismo tiempo. Pero si el número de
bancos y de procesadores es grande, resulta costoso desde el punto de vista tecnológico,
el conectar directamente todos los bancos con los procesadores. Una solución es usar
redes del tipo por etapas, lo que obliga que para cada acceso a memoria, se debe recorrer
una secuencia de enlaces. Si el número de procesadores y bancos crece, este tipo de redes
es inmanejable (muchas conexiones y latencia inaceptable), por lo que se propuso la
definición de redes parciales, donde cada procesador sólo se conecta a ciertos bancos (ya
no hay un espacio global de direccionamiento y dos procesadores pueden no tener bancos
en común).

Memoria Distribuida:

Otra forma es conectar a los procesadores directamente entre ellos (la memoria esta
distribuida entre los procesadores), teniéndose así una máquina a memoria distribuida sin
espacio de direcciones globales.

Las principales diferencias entre las redes de máquinas a memoria compartida y a

memoria distribuida son:

- Ancho de Banda: es la cantidad de información transmitida por unidad de tiempo, es

decir, es el número de bits que pueden ser transmitidos por unidad de tiempo. En las
máquinas a memoria compartida se deben transmitir un número de datos suficientes
para alimentar a los diferentes procesadores, por lo que debe ser grande el ancho de
banda; mientras que en las máquinas a memoria distribuida es de órdenes de
magnitud más pequeña.
- Latencia de la red: es el tiempo que necesita la red para realizar el servicio pedido, es
decir, es el tiempo para realizar una transferencia a través de la red. En las máquinas a
memoria compartida debe ser pequeño, por lo que se deben tener caminos cortos y
rápidos de comunicación entre los procesadores y los bancos. En las máquinas a
memoria distribuida es menos crítico, y se pueden tener caminos largos.
- Información a transmitir: clásicamente, en las máquinas a memoria compartida se
pueden transmitir datos, instrucciones, direcciones de memoria; mientras que en las
máquinas a memoria distribuida se transmiten datos.

26