UNIVERSIDAD NACIONAL

DANIEL ALCIDES CARRIÓN

FACULTAD DE
INGENIERIA
ESCUELA DE FORMACIÓN
PROFESIONAL DE
Curso:
Procesamiento Paralelo

Profesor:
Omar Raraz T.

Alumnos:
Lazaro Baldeon Alex

Rodríguez Romero Richard

Semestre:
VIII

CERRO DE PASCO

2009
 Queremos dedicar este trabajo que
representa el esfuerzo común del grupo
a las personas que cada día nos alientan
y nos enseñan en la ardua labor que
seguimos a nuestra familia que con su
esfuerzo han hecho posible este logro

Tipos de computación paralela.

Taxonomía
La creciente complejidad de los problemas tratados en ciertas áreas de la ciencia, la ingeniería, el
procesamiento de datos, etc., requieren una gran capacidad de cálculo. Es un hecho bien establecido que
para algunos problemas tales como los métodos numéricos, la simulación, la optimización, etc., la
computación paralela ofrece soluciones eficientes. Las aplicaciones de esta área de la computación se
extienden a diferentes disciplinas.
Así por ejemplo, los computadores paralelos y su desarrollo son de especial interés para permitir
descubrimientos relevantes en medicina, especialmente en los campos de la biología molecular o en el
análisis del genoma humano, en la física para el estudio de la superconducción, o en ingeniería para la
detección de incendios y el desarrollo de estrategias para su extinción.
La computación paralela o procesamiento en paralelo consiste en acelerar la ejecución de un programa.
simultánea, cada uno en su propia unidad de proceso. Surge así, de forma natural, la idea de la
computación paralela, que genéricamente consiste en utilizar n computadores para multiplicar,
idealmente por n la velocidad computacional obtenida de un único computador. Por supuesto, esta es una
situación ideal que muy rara vez se consigue en la práctica. Normalmente, los problemas no pueden
dividirse perfectamente en partes totalmente independientes y se necesita, por tanto, una interacción
entre ellas que ocasiona una disminución de la velocidad computacional. En este sentido se habla de
mayor o menor grado de paralelismo en la medida en que un algoritmo sea más o menos divisible en
partes independientes con igual coste computacional. Entre las interacciones hay que considerar
principalmente las dos siguientes:

a) La transferencia de datos.
b) La sincronización de los cálculos de los diferentes procesadores.

Sin embargo, dependiendo de la naturaleza del problema y de su grado de paralelismo, se pueden

conseguir grandes mejoras en el rendimiento. Hay que tener en cuenta que la computación paralela
siempre se podrá beneficiar de los progresos y avances que se consigan en los procesadores individuales.
El objetivo final de disponer de computadores paralelos más rápidos y potentes, es resolver categorías de
problemas disminuyendo significativamente el tiempo de su resolución, hecho que no sería posible con
los computadores serie actuales.

El concepto de computador paralelo, como es de esperar, no es una idea nueva. Por ejemplo, Gill ya
escribió acerca de la programación paralela en 1958, y un año después Hollandplanteó la posibilidad de
que un computador pudiera ejecutar un número arbitrario de subprogramas simultáneamente. En 1963
Conway describe el diseño de un computador paralelo y su programación, y 40 años más tarde se siguen
encontrando numerosísimos artículos con títulos y planteamientos similares a los que ya apuntaban estos
precursores del campo de la computación paralela.
Pero hasta 1981 no se presentó el primer sistema paralelo comercial de la que se tienen noticias. Fue
comercializada por BBN Computers Advanced (Bolt, Beranek and Newman Computers Advanced) y se
llamó Butteifly. Era capaz de distribuir su trabajo entre 256 procesadores, en concreto eran
microprocesadores Motorola 68000, que se conectaban a través de una red multietapa con memorias de
500 Kbytes por procesador. Se llegaron a vender alrededor de 35 máquinas, casi todas ellas a
universidades y centros de investigación.
En los últimos años el rendimiento de los computadores paralelos ha aumentado significativamente. En
la actualidad la tendencia general es que se construyan a partir de elementos diseñados para sistemas
monoprocesador, con lo que los sistemas paralelos se benefician de los avances obtenidos para los serie.
Como dato significativo, el rendimiento máximo de un computador paralelo en 1999 era de más de 2
Teraflops, unas 35 veces superior al de cinco años y unos meses antes.
Teniendo en cuenta la definición genérica de computación paralela, es inmediato comprender que la
construcción de un sistema de procesamiento paralelo puede realizarse de multitud de formas diferentes,
tanto al considerar los componentes que lo integran como al analizar las estrategias y los procedimientos
para comunicar los diversos elementos. La complejidad de las diversas posibilidades hace que se
presenten diferentes taxonomías basadas en diversos puntos de vista.
Con el fin de comprender en su conjunto las arquitecturas paralelas, seguidamente se exponen diferentes
clasificaciones que muestran tanto la complejidad de esta disciplina como las múltiples posibilidades de
las que se dispone. Debe entenderse que esta descripción se realiza anteponiendo la amplitud a la
profundidad, de manera que se presentan los conceptos generales básicos sin entrar en detalles sobre
posibles implementaciones prácticas.

En este Capítulo se introducen las arquitecturas paralelas. Con el fin de dar una idea global del ámbito en
el que se desarrollan, se presenta una clasificación que, sin pretender ser exhaustiva, muestra los
aspectos generales y las ideas fundamentales que sustentan las diversas opciones y soluciones. A lo
largo de esta clasificación quedará claramente determinado que es fundamental el comportamiento de las
redes de interconexión entre los elementos de cálculo que constituyen el sistema paralelo. En la
siguiente Sección se indican brevemente las características básicas de las mismas, presentando tres
ejemplos típicos de sistemas comerciales. Por último, se analizan los parámetros fundamentales que
caracterizan los sistemas paralelos.

1. TAXONOMíA DE LAS ARQUITECTURAS PARALELAS

Las diferentes posibilidades existentes para desarrollar sistemas paralelos hacen que una clasificación
definitiva sea complicada, y seguramente estéril. Por ello, en primer lugar se recuerdan las características
básicas del modelo secuencial, con el fin de delimitar los aspectosbásicos que son comunes o diferentes
de los sistemas paralelos. Seguidamente se muestra una clasificación clásica propuesta por Flynn, que se
basa en el flujo de instrucciones y en el flujo de datos, es decir, el mecanismo de control utilizado. Sin
embargo, existe una gran cantidad de criterios, aunque no todos mutuamente excluyentes entre sí, para
establecer una clasificación de las distintas arquitecturas paralelas. Así, tomando como base la
clasificación de Flynn se atiende a la organización del espacio de memoria, analizando las diferentes
posibilidades que permiten establecer diversas arquitecturas. A continuación, se consideran otros
criterios básicos de clasificación que diferencian unos sistemas de otros, entre los que destaca la red de
interconexión.

2. Arquitectura de los computadores secuenciales

Como es bien sabido, los computadores secuenciales, también denominados computadores serie, se
basan en la arquitectura de J. von Neumann. Este modelo tiene como elementos fundamentales una
Unidad Central de Procesamiento (CPU, acrónimo en inglés de Central Processing Unit), y una
memoria, que se caracteriza porque en ella no se distinguen datos e instrucciones . En este modelo se
considera una única secuencia de instrucciones que tratan una única secuencia de datos. Por ello se
conocen como computadores SISD, Single Instruction Stream, Single Data Stream (único flujo de
instrucciones, único flujo de datos). Una introducción detallada puede encontrarse en (Dormido, 2000).
El modelo de von Neumann presenta dos limitaciones básicas. La velocidad de ejecución de las
instrucciones y la velocidad de transferencia de información entre CPU y memoria. La primera está
relacionada con los componentes y la tecnología electrónica asociada. Sin embargo, desde el punto de
vista de la arquitectura de computadores se han desarrollado algunas estrategias para aumentar el
rendimiento. La más conocida es la segmentación (pipelining). La segmentación de instrucciones
consiste en traer a la cola de instrucciones la instrucción siguiente a la que se está ejecutando. En último
término se realiza la segmentación de ejecución, o segmentación encauzada, en la que se permite que
varias instrucciones se ejecuten simultáneamente en diferentes unidades funcionales de cálculo
(multiplicadores, sumadores, unidad de carga/almacenamiento, ...), durante las diferentes etapas en las
que se divide la ejecución de la instrucción.
 a) Modelo básico de J. von Neumann. b) Procesador con segmentación.

El rendimiento que se obtiene recurriendo a una máquina con segmentación es, por lo general, muy
superior al de la versión no segmentada. Obsérvese la Figura 2.4, en la que se muestra una segmentación
típica e ideal de un procesador RISC (Reduced Instruction Set Computer) con cinco etapas de
ejecución: IF (búsqueda de la instrucción), ID (decodificación de la instrucción y lectura de los
registros), EX (operaciones aritméticas), MEM (lectura/escritura de/en memoria) y WB (escritura en los
registros).

La gran ventaja que proporciona la segmentación radica en que es posible comenzar la ejecución de una
nueva instrucción en cada ciclo de reloj. Así, aunque la instrucción consume sus cinco ciclos (un ciclo
por etapa), el resultado real es que en cada ciclo de reloj se concluye la ejecución de una instrucción. De
esta forma, y sin considerar los riesgos de la segmentación (estructurales, datos y control), el
rendimiento obtenido es de cinco con respecto a la misma máquina no segmentada .
Sin embargo, pese a que la segmentación produce un incremento de la productividad, es decir, se obtiene
un número mayor de resultados por unidad de tiempo, el tiempo total de ejecución de la instrucción
segmentada es superior al de su equivalente no segmentada. Esto es debido a que el tiempo de ejecución
de una instrucción en la segmentación viene determinado por varios factores:

 Los cerrojos que hay que colocar en el camino de datos del procesador con el objeto de aislar la
información entre etapas.
 La duración de todas las etapas de la segmentación es similar y viene determinada por la etapa
más lenta. Ello es debido a que el paso de información de etapa a etapa se debe realizar de
forma síncrona por lo que todas las etapas deben tener la misma duración.
  Los riesgos que se producen en la segmentación y que introducen detenciones en el
encauzamiento.

Obsérvese que la instrucción no segmentada consume 260 nseg., mientras que su equivalente
segmentada emplea 325 nseg. debido a que todas las etapas duran lo que la más lenta, 60 nseg., y hay
que sumar los retardos producidos por los cerrojos en cada etapa, 5 nseg. Este caso indica que un
incremento de productividad no siempre se asocia a un incremento de velocidad de ejecución.

Análogamente, la segunda limitación también admite algunas soluciones desde el punto de vista de la
arquitectura de computadores. Así, la velocidad de transferencia puede crecer aumentando el número de
líneas de datos entre ambos componentes. La técnica más usual se denomina memoria entrelazada o
intercalada (memory interleaving), y consiste en dividir la memoria en bloques, cada uno con acceso
independiente. La Figura 2.6.a muestra esta arquitectura. Así, es posible transferir información de cada
uno de ellos simultáneamente. Otra forma bien conocida de aumentar la velocidad de intercambio de
información es la memoria cache. Mediante esta estrategia se interpone una memoria rápida, de
tecnología más cara y de menor tamaño que la memoria principal, sobre la que se aplican bloques de
memoria principal. El éxito de esta estrategia se basa en la satisfacción del principio de localidad, que
debe entenderse de forma genérica como el hecho de que la instrucción siguiente a la que se está
ejecutando está en la cercanía del bloque en uso, tanto en lo referente a su ubicación en memoria
(localidad espacial), como a su probabilidad de uso inmediato (localidad temporal). La Figura 2.6.b
muestra un procesador con ambas estrategias, memoria intercalada y memoria cache.
 a) Procesador con memoria intercalada. b) Procesador con memoria entrelazada y memoria cache.

Estas mejoras, siendo importantes para los sistemas SISD, presentan limitaciones, tanto las inherentes a
la tecnología de los componentes como a las propias de las estrategias. Por ejemplo, la memoria
intercalada tiene éxito sólo si se realiza un pequeño número de operaciones sobre un arreglo de datos
grande. Los procesadores segmentados, de alta velocidad, son particularmente útiles para grandes
aplicaciones científicas y de ingeniería. Un procesador segmentado de alta velocidad, en general,
utilizará una cache para no permitir que las instrucciones con referencia a memoria tengan una latencia
muy alta. Sin embargo, los programas científicos grandes, cuya ejecución es larga, tienen con frecuencia
conjuntos de datos activos de dimensiones muy grandes que son accedidos generalmente con baja
localidad, consiguiendo un rendimiento pobre de la jerarquía de memoria. El efecto resultante es una
disminución en el rendimiento de la cache. Este problema podría superarse no haciendo uso de las
caches en estas estructuras, siempre y cuando fuese posible determinar los patrones de acceso a memoria
y segmentar estos accesos eficientemente. Evidentemente, las mejoras tanto tecnológicas como
estratégicas desarrolladas para los sistemas SISD tendrán aplicación sobre los sistemas paralelos ya que,
en último término, los sistemas paralelos se construyen con componentes individuales.
2.1 Taxonomía de Flynn

En 1966 Flynn propuso una clasificación generalista de los computadores, adoptando como criterio el
flujo de instrucciones y el flujo de datos que en ellos se desarrolla. Se entiende por flujo (stream) una
secuencia de elementos, en este caso de datos o de instrucciones. Así, la clasificación de Flynn es la
siguiente:

1. SISD (Single Instruction, Single Datu), instrucción única, datos únicos. Como ya se indicó en la
Sección anterior, en este grupo se encuadran la mayoría de los computadores serie disponibles
actualmente. Las instrucciones se ejecutan secuencialmente pero pueden estar solapadas en las etapas de
ejecución (segmentación encauzada). Un computador SISD puede tener más de una unidad de recursos
de cálculo, pero todas ellas están bajo el control de una única unidad de control. La Figura 2.9.a muestra
este modelo.

2. SIMD (Single Instruction, Multiple Data), instrucción única, datos múltiples. Este modelo se ilustra
en la Figura 2.9.b. En esta clase se sitúan los procesadores matriciales en los queexisten varias unidades
de procesamiento trabajando sobre flujos de datos distintos pero ejecutando la misma instrucción
proporcionada por una única unidad de control. Estos computadores garantizan sincronismo entre
procesadores después de cada ciclo de ejecución de las instrucciones. Como ejemplo de este tipo de
arquitectura cabe destacar el ILLIAC IV y la Connection Machine.

3. MISD (Multiple Instruction, Single Data), instrucciones múltiples, datos únicos. Este tipo de
organización se caracteriza por la existencia de varias unidades de procesamiento cada una ejecutando
una instrucción diferente pero sobre el mismo flujo de datos. En sentido estricto no se conoce ninguna
materialización real de esta categoría, ya que limita las posibilidades del hardware sin claros beneficios
sobre otros modelos. Desde un punto de vista abierto pueden considerarse como MISD las arquitecturas
superescalares y VLIW (Very Long Instruction Word), ya que con frecuencia tienen un único flujo de
datos y múltiples instrucciones, aunque estas máquinas tienen un único contador de programa. Las
arquitecturas desacopladas tienen dos flujos de instrucciones con contadores de programa
independientes, y un único flujo de datos, con lo que se acercan más al concepto estricto de MISD. Del
mismo modo, las arquitecturas sistólicas también pueden ser consideradas MISD. Estas arquitecturas
toman su nombre por analogía del corazón, que bombea rítmicamente la sangre. Se pueden considerar
como un método de diseño de computadores de propósito especial para equilibrar recursos, ancho de
banda de E/S y cálculo. Basándose en la segmentación, los datos fluyen en etapas desde memoria a un
arreglo de unidades de cálculo y vuelven a memoria.

Como puede observarse, los datos llegan a un elemento de procesamiento a intervalos regulares, en cada
elemento se modifica y pasa al elemento siguiente, y así sucesivamente hasta que vuelve a memoria.
Los arreglos sistólicos han evolucionado desde estar constituidos por muchos chips dedicados de
propósito especial, a menos chips más potentes y programables.

4. MIMD (Multiple Instruction, Multiple Data), instrucciones múltiples, datos múltiples. En esta
categoría se incluyen la mayoría de los sistemas multiprocesadores y multicomputadores, y en ellos cada
procesador es capaz de ejecutar un programa independiente de los demás procesadores Un computador
MIMD intrínsecamente implica interacciones entre variosprocesadores porque todos los flujos de
memoria se obtienen de un espacio de datos compartido por todos ellos. Si los n flujos de datos
provinieran de subespacios disjuntos dentro de las memorias compartidas, entonces se tendría un sistema
SISD múltiple o MSISD, que no es más que un conjunto de sistemas monoprocesador SISD
independientes. La Figura 2.9.d. ilustra este modelo. Como ejemplos reales de este tipo de arquitectura
cabe destacar los sistemas: Cray-2, ZBM 370/168 y UNIVAC 1100/80.
Atendiendo a esta clasificación se deduce que las arquitecturas paralelas pueden ser esencialmente de
dos tipos: SIMD y MIMD. Seguidamente, se analizan los aspectos generales de cada una de ellas.

a) Modelo SIMD:

En el modelo SIMD cada procesador ejecuta en todo momento la misma operación, pero únicamente
sobre sus propios datos. Las instrucciones del programa se envían a más de un procesador y cada uno
actúa básicamente como un procesador aritmético-lógico sin una unidad de control. Una unidad de
control independiente, separada, es la responsable de buscar las instrucciones en memoria y de
repartirlas a los distintos procesadores. Cada procesador ejecuta la misma instrucción en sincronismo
pero utilizando diferentes datos.
En un modelo SIMD, el conjunto de datos forma un arreglo y una instrucción actúa sobre todo el arreglo
en un ciclo de instrucción. De ahí que el factor determinante en el desarrollo de este modelo sea el gran
número de aplicaciones que trabajan sobre arreglos de datos. Por ejemplo, muchas de las simulaciones
de sistemas físicos (sistemas moleculares, predicción del tiempo, etc.) operan sobre grandes arreglos de
datos.
Otra área de aplicación importante de este modelo es el procesamiento de imágenes a bajo nivel, donde
los elementos de dibujo (pixels) de la imagen se almacenan en grandes arreglos. Si se tiene un sistema
en el que se realizan las mismas operaciones sobre el conjunto de datos, será relativamente simple
programarlo en un modelo de este tipo. El programa consistirá en una única secuencia de instrucciones
ejecutadas de forma independiente por la unidad de control. Cada procesador de las máquinas SIMD
dispone de una pequeña cantidad de memoria local y canales de comunicación en una disposición tal que
el número de procesadores conectados directamente sea máximo, pero sin complicar excesivamente el
cableado. Para este tipo de modelos es habitual utilizar la topología hipercubo, que se detallará en el
Capítulo 4, y que en esencia está formada por una malla multidimensional de procesadores con dos de
ellos en cada dimensión.
El ejemplo clásico de máquina SIMD es la Connection Machine (un hipercubo de dimensión 16)
fabricada por Thinking Machines Corporation en 1985, formada por 65.536 procesadores cada uno con
4 Kbytes de memoria. La máquina completa está formada por varias unidades como la mostrada en la
Figura 2.10. Las máquinas SIMD son apropiadas para el tratamiento de arreglos en bucles, pero su
mayor debilidad se encuentra en el tratamiento de las sentencias de selección, en las que cada unidad de
ejecución debe realizar una operación diferente sobre su dato, dependiendo del dato que se tenga. Las
unidades de ejecución con el dato erróneo son inhabilitadas para que las unidades adecuadas puedan
continuar. Estas situaciones se ejecutan a l / n del rendimiento, donde n es el número de selecciones a
realizar. La poca flexibilidad del modelo SIMD ha provocado que en los últimos años se encuentre
relegado a entornos muy concretos y especializados.

b) Modelo MIMD:

En el modelo MIMD cada procesador actúa de forma esencialmente independiente. Uno o varios
procesadores pueden, por ejemplo, estar transformando datos mediante un algoritmo complejo, mientras
otro está generando una salida gráfica de resultados. Esto es lo que se denomina descomposición de
control, de manera que cada procesador puede estar ejecutando un programa distinto. Mucho más
habitual es la descomposición de datos, en la que los datos del problema se reparten entre los distintos
procesadores y todos ejecutan el mismo programa sobre la
zona de datos que se le ha asociado. Esta particularización del modelo MIMD se conoce como
SPMD (Single Program, Multiple Data), programa único sobre múltiples datos. Es importante
observar la diferencia con el modelo SIMD. En un sistema SPMD todos los procesadores ejecutan el
mismo programa, pero esto no quiere decir que ejecute el mismo código simultáneamente. De este
modo, un procesador puede estar ejecutando código distinto que el ejecutado por otro procesador, debido
por ejemplo a una bifurcación condicional dependiente del resultado de una operación. Así, suponiendo
que dos procesadores llegan a una sentencia IF simultáneamente, para uno de ellos puede resultar un
valor TRUE en la condición mientras que para el otro puede ser
FALSE. En ese momento cada procesador sigue ejecutando un código diferente del mismo programa.
Sin embargo, en un sistema SIMD el código de la sentencia IF .... THEN ELSE debe ejecutarse
secuencialmente. Este modelo es, por tanto, mucho más flexible que el SIMD.
Una analogía que sirve para aclarar el funcionamiento de un modelo MIMD es considerarlo equivalente
a la división de un proyecto en grupos de trabajo. Cada grupo se ocupa únicamente de su tarea, pero
todos los grupos tienen que reunirse de vez en cuando para intercambiar conclusiones y coordinar el
trabajo posterior. El intercambio de información entre procesadores depende del sistema de que se
disponga.

c) Comparación de los sistemas SIMD y MIMD

Evidentemente los sistemas SIMD necesitan menos hardware que los MIMD, ya que sólo requieren una
unidad de control, y además necesitan menos memoria ya que sólo es necesario almaeenar una copia del
programa en ejecución. Los sistemas MIMD almacenan una copia del programa en cada procesador, y
con ello el software asociado al programa, como por ejemplo el sistema operativo. Por otro lado, los
sistemas SIMD necesitan menos tiempo de inicio para las comunicaciones entre procesadores, debido a
que son transferencias entre registros del procesador origen y destino. Recuérdese que estas
transferencias son las más rápidas posibles (véase por ejemplo (Dormido, 2000)). Evidentemente, la
desventaja de los sistemas SIMD es que no pueden ejecutar diferentes instrucciones en el mismo ciclo de
reloj. Además, aunque en un principio puede parecer que los sistemas MIMD tienen un coste muy
superior a los SIMD, esto en general no es cierto. Debido a que los sistemas MIMD pueden construirse
con procesadores de propósito general, pueden beneficiarse de las ventajas económicas de una
distribución para el mercado y el consumo en general, mientras que las arquitecturas SIMD pueden
considerarse en este sentido específicas, con lo que su coste de producción suele ser mayor de lo que
cabría esperar. De hecho, la unidad de control de un sistema SIMD debe ser diseñada específicamente.
Con todo ello y debido a la economía de escala, las arquitecturas MIMD suelen tener un coste menor que
un sistema SIMD y ofrecen mayores rendimientos y posibilidades. Incluso para las aplicaciones en las
que se requiere sincronismo entre los procesadores, característica típica de los sistemas SIMD, se han
desarrollado arquitecturas MIMD que incorporan la posibilidad de trabajar en modo SIMD mediante la
inclusión del hardware adecuado. Algunos ejemplos de este tipo de sistemas son el DADO y el CM-5.
Atendiendo a todas estas consideraciones puede observarse que los sistemas MIMD son más generales y
eficaces. Por ello, en este texto se tratarán fundamentalmente los sistemas MIMD.

2.2 Organización del espacio de direcciones de memoria

El intercambio de información entre procesadores depende del sistema de almacenamiento que se

disponga. Atendiendo a este criterio se obtiene una nueva clasificación de las arquitecturas paralelas en:

 Sistemas de memoria compartida o multiprocesadores.

 Sistemas de memoria distribuida o multicomputadores.

En esta Sección se introducen de forma general ambas arquitecturas, comparando seguidamente sus
características.

a) Sistemas de memoria compartida o multiprocesadores.

Los procesadores de los sistemas con memoria compartida se caracterizan por compartir físicamente la
memoria, es decir, todos acceden al mismo espacio de direcciones. Un valor escrito en memoria por un
procesador puede ser leído directamente por cualquier otro. En principio, en esta arquitectura la memoria
es igualmente accesible por todos los procesadores a través de la red de interconexión. La Figura 2.11
muestra el esquema básico de la arquitectura de memoria compartida. Así se desarrollaron los primeros
computadores de esta arquitectura, tales como el NYU Ultracomputer.

En este contexto, en el que la red de interconexión es determinante para la eficacia del sistema, son
fundamentales dos parámetros que caracterizan los sistemas paralelos: la latencia de red y el ancho de
banda. Ambos determinan la velocidad en la transferencia de datos entre elementos básicos del sistema
paralelo. El primero se define como el tiempo que se tarda en enviar un mensaje a través de la red de
interconexión del sistema paralelo, mientras que, en este contexto, se define el ancho de banda como el
número de bits que se pueden enviar por unidad de tiempo.
Para garantizar la eficacia de esta arquitectura es fundamental que el ancho de banda sea elevado, ya que
en cada ciclo de instrucción cada procesador puede necesitar acceder a la memoria a través de la red de
interconexión. Este acceso a memoria puede ser lento debido a que las solicitudes de lectura o de
escritura pueden tener que pasar por varias etapas en la red. En la arquitectura de memoria compartida se
satisface que la latencia de red es baja, y el ancho de banda alto, sólo si no se encuentran varios
procesadores tratando de acceder al medio utilizado para la transmisión de datos simultáneamente. Por
este hecho y otros problemas relacionados con el mismo, el número de procesadores en este tipo de
sistemas suele ser pequeño y la arquitectura más común para la comunicación es la de bus, en la cual
todos los procesadores y módulos de memoria se conectan a un único bus, tal como muestra la Figura
2.12. En esta arquitectura el tiempo de acceso a memoria es el mismo para cualquier palabra, por lo que
se denomina arquitectura de acceso uniforme, UMA (Uniform Memory Access).
La mayoría de los sistemas de memoria compartida incorporan una memoria cache local en cada
procesador, y del mismo modo que en los computadores secuenciales, sirve para aumentar el ancho de
banda entre el procesador y la memoria local. Análogamente puede existir una memoria cache para la
memoria global. Cuando se utilizan memorias cache es fundamental asegurar la coherencia de la
información en la memoria cache, de modo que cuando un procesador modifique el valor de una variable
compartida los demás procesadores no consideren su valor anterior, ya que es incorrecto desde ese
momento. Sin embargo, existe otro factor que limita a la arquitectura UMA: la escalabilidad. La
escalabilidad es un factor fundamental de los sistemas paralelos. De forma genérica puede entenderse
como la capacidad del sistema para mejorar la potencia de cálculo cuando el número de nodos2
aumenta. En el caso ideal sería lineal, de manera que al tener dos nodos se dispondría del doble de
potencia de cálculo, con cuatro el cuádruple, con cien nodos cien veces más. Sin embargo, debido a
factores como los tiempos de comunicación, la escalabilidad no suele ser lineal y además, como se verá
en capítulos posteriores, llega a saturarse. La saturación indica que por muchos nodos más que se
incorporen, no se consigue ninguna mejora. Actualmente, los sistemas de acceso uniforme a memoria se
utilizan para la construcción de arquitecturas multiprocesador de bus compartido con un reducido
número de procesadores. Por tanto, este tipo de memoria compartida no es adecuada para sistemas
escalables debido a los problemas de acceso a la memoria remota que presentan. Entre los sistemas
implementados destaca el Encore Multimax de Encore Computer Corporation que representa la
tecnología de los años 80 y el Power Challenge que es representativo de los 90.

El sistema Encore Multimax es una arquitectura multiprocesador que presenta como característica
principal el uso de lo que se denominaba el Nanobus, que fue una de las primeras aplicaciones
comerciales del bus en espera. En este, los buses de datos y de direcciones se encuentran separados. El
bus de direcciones se utiliza en la primera fase de lectura y de escritura sobre la memoria. En el caso de
escritura se usa conjuntamente con el bus de datos mientras que en el caso de la lectura el bus de datos
puede ser usado por una unidad de memoria para transferir el resultado de una lectura anterior. Para
controlar estas operaciones se utilizan dos sistemas de lógica de arbitraje que cooperan entre sí para
asignar el bus de datos y el de direcciones entre 20 procesadores y 16 bancos de memoria. Se utiliza un
arbitraje centralizado, si bien es posible forzar a la unidad de arbitraje para que niegue el acceso al bus
de direcciones a otros dispositivos si un procesador no consigue el bus durante varios ciclos de reloj. El
árbitro del bus de datos está formado por un árbitro centralizado y un control de acceso distribuido. La
principal diferencia entre el arbitraje del bus de datos y el de direcciones reside en la política de arbitraje
utilizada y a quién va dirigida. La política de arbitraje del bus de datos sólo la usan los controladores de
memoria puesto que el procesador puede obtener acceso al bus de datos de una manera implícita cuando
el bus de direcciones está asignado a esos datos, siempre que se trate de una escritura en memoria. Bajo
estas condiciones el controlador de concesión de memoria ignorará su línea de concesión. Esta situación
se detectará observando un campo especial del bus de direcciones. El árbitro del bus de datos aplicará
una política de arbitraje fija entre los distintos controladores de memoria. La prioridad asignada a un
controlador de memoria dependerá de su posición física en el Nanobus. Esta política puede llevar a que
los controladores de menor prioridad no puedan acceder al bus. Para evitar esta situación el control de
acceso distribuido puede activar una línea especial en el bus para expulsar al resto de controladores del
ciclo de arbitraje. Esta arquitectura utiliza una cache de 256 Kbytes con un controlador del tipo snoopy3
para cada procesador. El controlador implementa una política de actualización de memoria de escritura
directa y una política de coherencia de cache basada en escritura por invalidación, que se analizarán en el
Capítulo 3. Por otro lado, el sistema Power Challenge utiliza un bus central que conecta las CPUs del
sistema con la memoria principal. Este bus, denominado POWER path-2, es un bus de 256 bits y tiene
un ancho de banda de 1,2Gbytes/s. Cada CPU tiene asociada una cache de datos y otra de instrucciones.

Este sistema utiliza procesadores RISC del tipo MIPS R8000 con un rendimiento de 300 Megaflops.
Aunque el ciclo de reloj de este procesador es dos veces menor que el de su predecesor el R4400 su
rendimiento es 4 veces superior. También tiene una cache especial denominada Streaming Cache de 16
Mbytes, con la que se pretende reducir el tráfico del bus lo máximo posible. Los sistemas Power
Challenge pueden ser acoplados mediante canales HiPPI para formar un cluster de memoria distribuida
y usar PVM o MPI para el intercambio de datos. Esta combinación de Power Challenge se denomina
SGI Power Challenge Array. Un sistema como el descrito, llega a alcanzar una velocidad de 26,7
Gigaflops con 128 procesadores. En general, los sistemas UMA presentan una . escalabilidad limitada
incluso cuando incorporan mecanismos de memoria cache. Normalmente, en la actualidad su número
máximo de procesadores está entre 16 y 32. Algunos sistemas como el Sun El0000 logran escalar hasta
64 procesadores con arquitectura UMA. En este sistema se emplea un bus denominado Gigaplane-XB.
Es un bus híbrido, es decir, compartido en direcciones y con crossbar en datos, y soporta un ancho de
banda cercano a los 13 Gbytes. Estas prestaciones facilitan que el sistema logre escalar hasta 64
procesadores.

Sin embargo, algunas mejoras pueden realizarse dotando a cada procesador de una memoria local, en la
que se almacena el código que se está ejecutando en el procesador y aquellos datos que no tengan que
ser compartidos por los otros procesadores y, por tanto, son locales a ese procesador. Mediante esta
estrategia se evitan accesos a memoria a través de la red de interconexión relacionados con búsquedas
de código y datos locales, lo que mejora la eficacia del sistema. Esta modificación de la arquitectura es
conocida como memoria compartida con acceso no uniforme a memoria y se ilustra en la Figura 2.13.a.
Teniendo en cuenta este esquema y considerando el tiempo que un procesador necesita para acceder a
memoria local y global, las memorias compartidas se clasifican en memorias de acceso uniforme, UMA,
y no uniforme, NUMA. En las primeras, el tiempo de acceso a memoria es el mismo para cualquier
palabra, mientras que en las segundas difiere de una a otra Los sistemas de memoria compartida de
acceso no uniforme son también conocidos como sistemas de memoria compartida distribuida, DSM
(Distributed Shared Memory). La idea de distribuir la memoria compartida puede llevarse al límite
eliminando completamente el bloque de memoria compartida común, la global, tal y como se muestra en
la Figura 2.13.b, siempre y cuando los tiempos de acceso a las memorias locales sean muy inferiores al
tiempo de acceso por la red de interconexión. En este diseño los accesos de un procesador a las
memorias locales de los otros se realizan mediante el control de un hardware específico. Obviamente
esta arquitectura es NUMA.
Los primeros sistemas paralelos tipo UMA se desarrollaron a principios de la década de los 60, entre los
que destacan Burroghs 5500, CDC 3600 y el ZBM System/360 Model 50, mientras que el primer
sistema NUMA, el CMU C.mmp, no surgió hasta principios de los 70. Fue a principios de los 90 cuando
estos sistemas comenzaron a desarrollarse extraordinariamente, apareciendo el primer sistema comercial,
el KSR-I, que incorporaba 32 procesadores en anillo.
 a) Arquitectura de memoria compartida con acceso no uniforme a memoria.
b) Memoria compartida con acceso no uniforme a memoria sólo con memoria local.

El sistema KSR-1 es especialmente importante porque fue el primero que mantenía coherencia por
hardware. Este tipo de sistemas, cuyo esquema se muestra en la Figura 2.14, se denominan ccNUMA
(NUMA con coherencia hardware), y también son conocidos como multiprocesadores simétricos
escalables, S-SMP (Scalable Symmetric Multi-Processors) . Posteriormente se desarrollaron
prototipos como el Standford DASH a partir de los que se comercializaron sistemas como el SGZ
Origin 2000, a mediados de los 90. La Figura 2.15 muestra la estructura de este sistema. En la
actualidad la mayoría de los sistemas desarrollados con arquitecturas de memoria compartida son
NUMA, como por ejemplo los sistemas TC-2000, Standford Dash y el Blue Mountain de SGZ, que
está considerado como uno de los más potentes del mundo. La escalabilidad de esta arquitectura es muy
superior a la UMA. No es extraño encontrar sistemas con 512 nodos, e incluso existen con 2.048 nodos.

Arquitectura ccNUMA.
 a) Nodo. b) Red de interconexión

En general, el esquema de la arquitectura NUMA no requiere del empleo de mecanismos especiales que
aseguren que todos los nodos tienen un conocimiento coherente del espacio de direcciones global. Es
posible manejar un espacio común de direcciones y que sea el programador el encargado de manipular el
contenido de esas direcciones de memoria evitando cualquier falta de coherencia. Esta es la
aproximación empleada, por ejemplo, en el Cray T3E. Evidentemente, en las arquitecturas NUMA la
red de interconexión juega un papel fundamental. Es necesario señalar que, dado que cada procesador ve
un espacio común de direcciones a nivel lógico pero que realmente está distribuido a nivel físico, cada
uno de los accesos a posiciones de memoria que se encuentran fuera del rango mantenido por el nodo
local se convertirá en accesos remotos. La comunicación entre nodos se realiza a través de peticiones de
bloques de forma transparente al programador. Para que el sistema sea eficaz, la latencia de la red de
interconexión no debe incrementar los tiempos de los accesos remotos excesivamente ya que, aunque el
número de accesos remotos fuese muy inferior al de accesos locales, un coste elevado en cada fallo
afectaría de forma drástica al rendimiento global del sistema. Por otro lado, dependiendo de cómo se
comparta la información garantizando la coherencia en memoria, la arquitectura NUMA puede
clasificarse en dos grupos: ccNUMA y COMA (Cache-Only Memory Access). En los sistemas
ccNUMA cada nodo contiene una porción de la memoria total del sistema. Las variables compartidas se
reparten directamente por el programador o por la máquina haciendo uso del sistema operativo, de
manera que sólo existe una única copia de cada variable en la memoria principal. La coherencia se
mantiene normalmente mediante directorios. Esta estrategia fue desarrollada con anterioridad a otras
como las basadas en el protocolo snoopy. En general, cada nodo puede constar de uno o varios
procesadores con sus caches, una memoria principal y un directorio. Las variables compartidas están
almacenadas en un único nodo denominado home, que se encarga de que el resto del sistema mantenga
una visión coherente de la variable compartida. Así, al cambiar su valor, este nodo es el encargado de
actualizar o invalidar el resto de copias que existan a lo largo del sistema.
En algunos casos, los procesadores no incluyen memoria local sino que sólo poseen cache. A esta
modificación se le denomina acceso único a memoria cache, COMA. Un ejemplo de este tipo es el
sistema KSR-I.
La idea básica de la arquitectura COMA es emplear la memoria local de cada nodo del multiprocesador
como si fuese una cache del resto del sistema, transfiriendo los datos de cada nodo en función de las
necesidades del código en ejecución. Esta idea es análoga a la de cache de un sistema monoprocesador,
de modo que la memoria local de un nodo actúa como cache y el conjunto de la memoria local de los
otros nodos sería el equivalente a la memoria principal. Si un procesador tiene que acceder
repetidamente a una posición de memoria que se encuentra en un nodo remoto se puede copiar la
posición de memoria remota en la memoria local, y en los siguientes accesos no habrá que realizar un
acceso remoto para acceder al dato.
Los esquemas de coherencia de cache más utilizados en esta arquitectura son los de directorios o de
directorios distribuidos. La ventaja fundamental de los sistemas COMA es que son capaces de tratar los
fallos de acceso remoto distribuyendo automáticamente por el sistema los datos que está utilizando la
aplicación. La principal desventaja es la complejidad para mantener la coherencia de las copias de las
variables a lo largo de todo el sistema, ya que no existe una única copia segura, como sucede en el caso
ccNUMA.
Existen algunos prototipos del modelo COMA como el StanFord Flash o I-ACOMA entre otros, y
sistemas como el KSR-I y el KSR-2 podrían ser incluidos dentro de esta categoría. Evidentemente el
concepto genérico de memoria compartida puede aplicarse tanto a sistemas SIMD como MIMD, aunque
por las razones explicadas en la Sección anterior el interés se centra en los MIMD. A la combinación de
MIMD y memoria compartida se le denomina multiprocesadores simétricos (SMP, Symmetric
Multiprocessors). Los sistemas SMP suelen tener de 2 a 64 procesadores, y se les suele conocer como
la arquitectura que comparte todo, es decir, todos los procesadores utilizan conjuntamente la totalidad
de los recursos que tenga disponible el sistema (bus, memoria, módulos de entrada y salida, etc.). Por
otro lado, en los sistemas SIMD únicamente se ejecuta una copia del sistema operativo. Debido a ello,
esta forma de paralelismo es mejor aprovechada por un sistema operativo multihebra (MultiThreaded) ,
como por ejemplo Windows NT, utilizando un procesador para cada hebra. Las aplicaciones del usuario
en un sistema SMP también pueden utilizar un sistema de programación de alto nivel como las hebras
(Threads), o un estándar de memoria compartida como OpenMP, o incluso alguna biblioteca de bajo
nivel como SVr4 IPC shm (Standar UNIX System V Release 4 para Comunicación entre Procesos
usando Memoria Compartida) para aprovechar dicho paralelismo.
Un ejemplo característico de arquitectura ccNUMA es el sistema HP-Convex Exemplar SPP S2000
scalable parallel processor. Está constituido por elementos denominados hipernodos, que son a su vez
multiprocesadores simétricos, SMPs, de hasta 16 procesadores PA-RISC 8000 con 16 Gbytes de
memoria. El rendimiento del sistema es de 5,76 Gigaflops. Cada procesador posee una memoria cache
externa de 2 Mbytes, un megabyte de datos y otro de instrucciones, y se direcciona haciendo uso de 32
bits. Un sistema formado por un solo hipernodo se denomina de clase S mientras, que un sistema de
varios hipernodos se denomina de clase X.
La memoria está físicamente distribuida entre los hipernodos pero es compartida virtualmente, es decir,
un procesador de un hipernodo puede direccionar cualquier posición de memoria del sistema como si se
tratara de un espacio de direcciones global único. Esta estructura facilita notablemente la programación
del sistema.
La comunicación entre los procesadores de un hipernodo se realiza a través de una red crossbar no-
bloqueante capaz de mantener un ancho de banda de 960 Mbytes. Los hipernodos están conectados entre
sí a través de lo que se denomina CTI (Coherent Toroidal Interconnect), que es una red a modo de
toro. Cada anillo es unidireccional, por lo tanto el acceso remoto no depende de la distancia entre
hipernodos. Por otro lado, un ejemplo típico de arquitectura COMA es el KSRl (Kendall Square
Research). Durante sus seis años de desarrollo pasó de ser una arquitectura compuesta por 8 nodos con
un rendimiento de 320 Mflops, 256 Mbytes de memoria y 210 Gbytes de disco a una arquitectura de
1.088 nodos con un rendimiento de 43 Gflops, 34 Gbytes de memoria y 15 Tbytes de disco. En este
sistema el espacio de direccionamiento está formado por una colección de caches y por un controlador
denominado ALLCACHE, que realiza el control de la coherencia de la cache basándose en un esquema
de directorios distribuidos. El sistema está constituido por módulos de procesamiento formados por 32
nodos APDR (ALLCACHE processor, router and directory - ALLCACHE procesador, enrutador y
directorio) con 1 Gbyte de memoria cache. A su vez, cada APDR contiene una unidad de coma flotante
de 64 bits y una unidad de procesamiento de enteros de 64 bits. El esquema de directorios distribuido
seimplementa con el uso de una matriz en la cual cada fila representa una subpágina y cada columna
representa una cache local. Un elemento de la matriz está vacío si la correspondiente memoria cache
local no contiene ninguna copia de una subpágina. Para evitar mantener una matriz prácticamente vacía
(sparse matrix) se guardan sólo las celdas que no se encuentran vacías.
Los estados de estas celdas pueden ser cuatro:

- EO (Exclusive Owner): Propietario exclusivo. Es la única copia válida en toda la máquina.

- C (Copy): Copiar. Al menos dos copias válidas de la subpágina están en el sistema.
- NO (Not Exclusive Owner): Propietario no exclusivo. Cuando varias copias de la subpágina
existen y una de ellas se marca como de propiedad no exclusiva.
- I (Invalid): Inválido. Aunque existe una copia de la subpágina en la cache local, esta es no
válida y no se puede usar.

b) Sistemas de memoria distribuida o multicomputadores

En los sistemas de memoria distribuida cada procesador dispone de su propia memoria, denominada
local o privada, independiente del resto y accesible sólo por su procesador. La comunicación se realiza
por paso de mensajes, es decir, para que un dato que reside en la memoria de un procesador pase a la de
otro, el primero debe construir un mensaje por software, enviarlo a través de una red de interconexión y
el segundo debe recibirlo. Como puede observarse es un mecanismo más complejo que con memoria
compartida. La Figura 2.17.a muestra el esquema básico de la arquitectura distribuida. Esta arquitectura
es también conocida como arquitectura de memoria privada o arquitectura de paso de mensajes.
La misión de la red de interconexión es facilitar el paso de mensajes entre los procesadores nodo. El
concepto de paso de mensajes parece ser la estrategia dominante en los sistemas con gran número de
procesadores (mayor que 100), y es especialmente útil en entornos donde la ejecución de los programas
puede dividirse en pequeños subprogramas independientes. La latencia de red puede ser alta, pero para
analizar el ancho de banda es necesario atender a otro factor de eficiencia de los sistemas paralelos
conocido como granularidad del computador paralelo. En general, se entiende por granularidad del
computador paralelo el cociente entre el tiempo requerido para realizar una operación básica de
comunicación y el tiempo requerido para realizar una operación básica de cálculo de los procesos.
Para un tiempo dado de operación básica de cálculo ofrece una medida del número y del tamaño de los
paquetes de información utilizados en las comunicaciones.
En los sistemas de paso de mensajes para lograr un uso adecuado del ancho de banda es necesario
realizar un cuidadoso reparto de los datos sobre los procesadores con el fin de disminuir la
granularidad de las comunicaciones. Por disminuir la granularidad de las comunicaciones se entiende
minimizar el número de mensajes y maximizar su tamaño. Evidentemente, aunque el concepto genérico
puede aplicarse a sistemas SIMD, también es aplicable a sistemas MIMD. A la combinación de sistema
MIMD con arquitectura de paso de mensajes se le conoce como multicomputadores.

a) Esquema de la arquitectura distribuida. b) Ejemplo del IBM SP-2.

Los sistemas con memoria distribuida o multicomputadores pueden, a su vez, ser un único computador
con múltiples CPUs comunicadas por un bus de datos o bien múltiples computadores, cada uno con su
propio procesador, enlazados por una red de interconexión más o menos rápida.
En el primer caso se habla de procesadores masivamente paralelos (MPPs, Massively Parallel
Processors), como los Fujitsu VPP, ZBM SP2 o SGZ T3E; y en el segundo se conocen de forma
genérica como cluster. Un cluster, a nivel básico, es una colección de estaciones de trabajo o PCs
interconectados mediante algún sistema de red de comunicaciones. En la literatura existente de
arquitecturas paralelas se utilizan numerosos nombres para referirse a un cluster, entre los que dest acan:

O Redes de estaciones de trabajo (NOWs, Network of Workstations).

O Redes de PCs (NOPCs, Network of PCs).
O Cluster de estaciones de trabajo (COWs, Cluster of Workstations).
O Cluster de PCs (COPCs, Cluster of PCs).

Realizando una clasificación estricta, los clusters pueden ser de dos tipos dependiendo de si cada
computador del cluster está o no exclusivamente dedicado a él. Si es así, se habla de un cluster de clase
Beowulf. En cualquier otro caso se suele definir al cluster como NOW. En muchas ocasiones los
términos cluster y Beowulf se confunden y se utilizan indistintamente. El término Beowulflo utilizó la
NASA para dar nombre a un proyecto que pretendía construir un ordenador capaz de alcanzar el
gigaflops a partir de componentes asequibles. Y lo consiguieron, el Beowulf original de 1994, con 16
procesadores 486 DX4 ejecutando Linux, fue capaz de alcanzar 1,25 Gigaflops. El término no se debe a
razones técnicas. Beowulfera un guerrero escandinavo del siglo VI cuyas aventuras se relatan en el
primer texto conocido en lengua inglesa (similar al Cantar del
Mío Cid en la lengua española). Las características más relevantes de los sistemas Beowulf son las
siguientes:

- Un sistema Beowulfes un conjunto de nodos minimalistas4 conectados por un medio de

comunicación barato, en el que la topología de la red se ha diseñado para resolver un tipo de
problema específico.
- Cada nodo de un Beowulf se dedica exclusivamente a procesos del supercomputador.
- En una red de estaciones de trabajo (NOWs) suele existir un switch central para realizar las
comunicaciones, mientras que en un Beowulf el mecanismo es más rudimentario: conexiones
placa a placa por cable RJ-45 cruzado.
- La programación de un Beowulf es fuertemente dependiente de la arquitectura y siempre se
realiza por paso de mensajes.
- Para programar un Beowulf en primer lugar se diseña el modelo de paralelismo, se observan
cómo son las comunicaciones entre los nodos y se implementan físicamente.
- De esta forma se evita el hardware innecesario a cambio de una fuerte dependencia entre el
software y la topología de la red. En caso de que cambie el problema hay que recablear el
sistema.

b) Comparación de los sistemas de memoria compartida y distribuida:

Las arquitecturas NUMA y distribuida son similares en la distribución de memoria. La principal

diferencia radica en el hecho de que la NUMA requiere un hardware específico para la lectura y
escritura en las memorias de los otros procesadores, mientras que en la memoria distribuida se realizan
los accesos remotos mediante mensajes.
Como puede observarse, es inmediato construir una arquitectura distribuida con n procesadores a partir
de una arquitectura de memoria compartida con el mismo número de procesadores. Para ello basta con
dividir el espacio de direcciones de la memoria compartida en n partes disjuntas y asignar una a cada
procesador para su uso exclusivo. Los mensajes entre procesadores se realizan de manera que el
procesador origen escribe en el bloque de memoria asignado al procesador destino.
Por otro lado, construir un sistema de memoria compartida a partir de uno de memoria distribuida es
sencillo aunque su programación no es tan elemental, ya que para acceder a la memoria de otro
procesador es necesario enviar y recibir mensajes. La Figura 2.18 muestra diversas realizaciones de
arquitecturas UMA en la que los nodos son procesadores o computadores. Otra ventaja de los sistemas
de memoria compartida es la rapidez con la que los procesadores pueden acceder a grandes estructuras
de datos.
Sin embargo, las arquitecturas compartidas presentan algunas desventajas que deben tenerse en cuenta.
En muchos casos, las aplicaciones desarrolladas según el esquema de memoria compartida suelen
ofrecer peores prestaciones que las basadas en paso de mensajes. La explicación a estos resultados hay
que buscarla en el menor control que tiene el programador sobre la localización de los datos. Esto
conduce a pérdidas de rendimiento por diversos factores como son: la contención de memoria, el acceso
a memorias no locales, el coste temporal debido al soporte de coherencia de cache, especialmente
cuando dos procesadores acceden en paralelo a celdas de memoria correspondientes a una misma línea
cache y alguno de ellos la modifica, con lo que el dato se comparte con valores falsos. Este último
problema, conocido como false sharing (compartidos falsamente) es un inconveniente de especial
relevancia.
Las características de las arquitecturas NUMA hacen que estos sistemas sean altamente escalables, sin
embargo son muy sensibles al reparto de datos que se realiza en la memoria local ya que el acceso a
estas memorias es mucho más rápido que el acceso a la memoria remota. El diseño de este tipo de
máquinas se asemeja al diseño de multicomputadores de memoria distribuida, si bien la principal
diferencia con estas arquitecturas radica en la forma de organizar la memoria y el acceso a la misma. En
un sistema multicomputador cada memoria local utiliza un único espacio de direccionamiento y este
direccionamiento se realiza localmente en cada memoria local. Por tanto, un procesador no puede
acceder directamente a la memoria local de otro. Esta propiedad determina el software de estos sistemas.
Así, el mecanismo más común de comunicación en multicomputadores de memoria distribuida se basa
en el paradigma de paso de mensajes, mientras que las arquitecturas NUMA se programan basándose en
un único espacio global de direccionamiento (memoria compartida) para toda la arquitectura.
Actualmente estas dos arquitecturas se suelen entremezclar, como por ejemplo en el CRAY T3E.
También es común
la implementación del acceso a las memorias locales de otros procesadores usando el paso de mensajes a
pesar de tratarse de máquinas NUMA.
El problema de la coherencia de caché no es tal en las arquitecturas de memoria distribuida, puesto que
el paso de mensajes explícitamente maneja de forma independiente distintas copias de las estructuras de
datos usadas. Sin embargo, es fundamental en los sistemas de memoria compartida, en los que el
acceso múltiple a las estructuras de datos globales se realiza usando copias de los mismos en las
memorias.
Desde el punto de vista de la programación, los sistemas de memoria compartida suelen ser más
sencillos que los de memoria distribuida. En los primeros basta en general con establecer algunas
directivas de compilación en el código secuencia1 paila obtener el código paralelo, mientras que en las
segundas deben programarse explícitamente todas las comunicaciones.
Además, los sistemas de memoria compartida son significativamente más caros que los de memoria
distribuida, debido de nuevo a razones de economía de escala.
3 RESUMEN DE LA CLASIFICACIÓN DE LAS ARQUITECTURAS
PARALELAS

En primer lugar según la clasificación de Flynn basada en el flujo de instrucciones y el flujo de datos que
se desarrolla en los procesadores, los sistemas paralelos pueden dividirse en sistemas SIMD (Single
Instruction, Multiple Data) y MIMD (Multiple Instruction, Multiple Data), ya que los SISD (Single
Instruction, Single Data) no son paralelos y los MISD (Multiple Instruction, Single Data) no tienen
interés práctico en general. Teniendo en cuenta el criterio basado en la organización del espacio de
direcciones de memoria, los sistemas MIMD se dividen en sistemas de memoria compartida o memoria
distribuida. A la combinación de MIMD y memoria compartida se le denomina multiprocesadores
simétricos (SMP, Symmetric Multiprocessors), mientras que a la combinación de sistema MIMD con
arquitectura de paso de mensajes se le conoce como
multicomputadores. Estos últimos pueden ser procesadores masivamente paralelos (MPPs,
Massively Parallel Processors) constituidos por único computador con múltiples CPUs comunicadas
por un bus de datos o cluster formados por múltiples computadores, cada uno con su propio procesador,
enlazados por una red de interconexión más o menos rápida. Por último, los clusters pueden ser de dos
tipos dependiendo de si cada computador del cluster está o no exclusivamente dedicado a él. Si es así, se
habla de un cluster de clase Beowulf y si no se denominan NOWs.

4 OTROS CRITERIOS DE CLASIFICACIÓN

La anterior clasificación, siendo muy completa e ilustrativa, no puede considerarse definitiva. De hecho,
atendiendo a otros factores o desde otros puntos de vista, se pueden realizar taxonomías diferentes. Así
por ejemplo, tanto las arquitecturas de memoria compartida como las de memoria distribuida pueden
construirse a partir de procesadores y unidades de memoria mediante redes de interconexión. Estas redes
son de una variedad muy amplia, y pueden ser clasificadas en dos clases: estáticas y dinámicas.
Las redes estáticas, también denominadas directas, se caracterizan porque la comunicación se realiza
punto a punto entre los procesadores. Estas redes se aplican normalmente a las arquitecturas de paso de
mensajes, y serán analizadas en detalle en el Capítulo 4, dedicado a las arquitecturas distribuidas.
Las redes dinámicas, sin embargo, se construyen con switches, hubs o enlaces de comunicación, que se
conectan dinámicamente para establecer caminos entre los procesadores y los bancos de memoria. Estas
redes, también denominadas indirectas, suelen ser utilizadas para los sistemas de memoria compartida.
Por esta razón serán analizadas en el Capítulo 3, dedicado a este tipo de sistemas.
Desde otro punto de vista, los sistemas paralelos se clasifican según la potencia y el número de los
procesadores que los constituyen. A este factor se le denomina granularidad de procesador. Si son
pocos procesadores pero muy potentes se dice que son computadores de grano grueso (coarse-grain),
mientras que si son muchos pero menos potentes se denominan de grano fino (fine-grain).
Así por ejemplo, los computadores Cray Y-MP son de grano grueso ya que constan de 8 a 16
procesadores cada uno de varios Gigaflops. Los computadores MasPar MP-1 contienen más de 16.384
procesadores de cuatro bits, siendo evidentemente de grano fino. Entre ellos se establecen los de grado
medio, como por ejemplo las computadoras nCUBE 2 y Paragon XP/S que tienen algunos miles de
procesadores cada uno del tipo de las estaciones de trabajo. De nuevo debido a razones de economía de
escala, los computadores de grano grueso son mucho más caros que los d grano fino y medio, ya que los
procesadores de los primeros no se fabrican a nivel industrial, y su tecnología de fabricación es
considerablemente más costosa. Como ya se indicó anteriormente, se entiende por granularidad del
computador paralelo al cociente entre el tiempo requerido para realizar una operación básica de
comunicación y el tiempo requerido para realizar una operación básica de cálculo de los procesos.
Cuando este cociente es pequeño estos computadores se pueden utilizar con algoritmos que necesiten
comunicaciones frecuentemente, y análogamente si es grande serán adecuados para algoritmos que no
necesiten muchas comunicaciones. Atendiendo a este criterio, multicomputadores comerciales como el
nCUBE 2 y el Paragon XP/S serían de granogrueso, mientras que multiprocesadores como el TC-2000
o el KSR-I serían de grano fino.

2.5 REDES DE INTERCONEXIÓN

La importancia de las redes de conexión en los sistemas paralelos es evidente, ya que en esencia un
computador paralelo se constituye con un conjunto de elementos que cooperan entre sí utilizando un
medio para el intercambio de información. Independientemente de que el sistema paralelo pertenezca a
uno u otro grupo de la clasificación anterior, el rendimiento de la red de interconexión será un factor
fundamental para la eficiencia del sistema.
En general, se entiende que la red de interconexión es eficaz u óptima cuando la capacidad de cálculo del
sistema está equilibrada con respecto a la capacidad de transmisión de la red de interconexión. Cuando la
capacidad de cálculo se incrementa, las características de la red deben mejorarse en sintonía con ella. Las
mejoras en las capacidades de la red de interconexión se han desarrollado a la par que en la tecnología
VLSI. Sin embargo, existen algunas limitaciones específicas para el desarrollo de las redes de
interconexión. En primer lugar el coste es mayor, por lo que en el caso ideal, en el que se dispondría de
enlaces individualizados entre todos los elementos de cálculo, resultaría muy costoso. Además, existen
limitaciones físicas, como los retrasos inherentes a todo sistema de comunicación. Por todo ello, al
diseñar un sistema paralelo es fundamental analizar detenidamente la red de interconexión. Además, los
avances en los elementos de cálculo hacen que, cada vez más, la red de interconexión se convierta en el
factor limitante de la velocidad de los sistemas paralelos. La red puede limitar el rendimiento del sistema
debido a dos factores básicos. El primero es porque el tiempo de acceso sea demasiado elevado, y el
segundo se debe a que la cantidad de información que se puede tratar sin desbordarse sea demasiado
baja. En ambos casos, el rendimiento en la transmisión de información entre los elementos de cálculo
disminuirá y con ello la eficacia del sistema. Los factores de la red de interconexión que más influyen en
el rendimiento del sistema son fundamentalmente cuatro: la topología, el mecanismo de conmutación,
el control de flujo y el algoritmo de encaminamiento.

Respecto a la topologia, existe gran variedad, que va desde las estructuras sencillas de bajo coste y poco
escalables, hasta los grafos más complejos. Entre las primeras se encuentran las redes de medio
compartido cuyo máximo exponente es el bus, mientras que de las segundas existe una enorme variedad
de posibilidades, clasificadas en redes directas e indirectas, tal y como se indicó en la Sección anterior.
Este aspecto será detenidamente analizado en los capítulos 3 y 4.
Respecto al mecanismo de conmutación, el hecho fundamental es que en la actualidad se emplea
conmutación de paquetes, aunque bien es cierto que en un principio se utilizaron técnicas de
conmutación de circuitos, consistentes en abrir y reservar un camino físico (un hilo de cobre o cable)
entre el par origen-destino. Esta técnica sólo es eficaz si la cantidad de información a enviar es elevada
y/o la fluctuación en el ritmo de transferencia es muy baja, que es la situación contraria a la habitual en
un sistema multiprocesador. En la conmutación de paquetes no se reserva el medio, sino que la
información se transmite en forma de paquetes siguiendo bien un camino establecido previamente o bien
buscando su propia ruta al nodo destino. Aunque esta técnica implica la incorporación de arbitrajes para
gestionar los fenómenos de contención, permite aumentar significativamente el nivel de ocupación de la
red.
El tercer factor es el control de flujo empleado. En los primeros multiprocesadores se utilizó la técnica
de control de flujo store-and-forwards, bien establecida en las redes de área local. En esta estrategia
cada paquete se almacena completamente en los nodos intermedios antes de ser reenviado al siguiente
nodo de la ruta en busca del nodo destino. Por ello, la distancia topológica de la red multiplica la latencia
de los mensajes, con lo que es absolutamente inapropiado para los sistemas paralelos. En 1979,
Kermani y KZeinrock introdujeron la técnica de control de flujo virtual cut-through6 (control de flujo
segmentado). En ella cada unidad mínima de información intercambiable entre routers, denominada
phit, puede ser reenviada al siguiente router, sin haber recibido todo el paquete. Para realizar esta
estrategia es necesario que los encaminadores tengan cierta capacidad de almacenamiento, pero a cambio
la distancia topológica se suma a la latencia, en vez de multiplicarla, con lo que el rendimiento del
sistema mejora significativamente. Cuando la unidad mínima sobre la que se realiza el control de flujo,
denominada pit, es menor que el paquete, el control de flujo es denominado wormhole. Cada flit puede
estar formado por uno o varios phits. Con wormhole se reduce la capacidad de almacenamiento
necesaria en cada encaminador a un único flit. Por estas razones el wormhole es el mecanismo de control
de flujo más utilizado en la práctica.

El cuarto factor es el algoritmo de encarninamiento, es decir, el método utilizado para elegir el camino
entre cada origen y destino. La primera idea es sencilla y consiste en fijar una ruta predeterminada. Este
tipo es denominado encaminamiento determinista. En él, los encaminadores son sencillos, rápidos y de
bajo coste. Su principal desventaja es que puede provocar grandes desbalanceos en los niveles de
ocupación de los recursos en numerosas situaciones de tráfico.
Como alternativa apareció el encaminamiento adaptativo en el que la elección del camino depende de
los nodos origen y destino y, además, del estado de la red en el momento de la transmisión. Los
encaminadores adaptativos son mucho más complejos, con lo que aumenta su coste y disminuye su
rapidez.
Teniendo en cuenta todos los factores fundamentales en una red de interconexión, pueden realizarse
encaminadores mediante combinaciones de las estrategias elaboradas para cada uno de ellos. Sin
embargo, existen algunas limitaciones que impiden el rendimiento eficaz de algunas de ellas. La más
importante es el interbloqueo, o deadlock, que se produce en la transmisión de los paquetes. Es debido
fundamentalmente al tipo de topología, control de flujo y encaminamiento elegido y tiene como
consecuencia la inutilización del subsistema de interconexión. Otros hechos a tener en cuenta son la
inanición7, o starvation, que para evitarse puede requerir una asignación de recursos equitativa, y el
livelock, efecto relacionado con la utilización de encaminamiento no mínimo, es decir, con que la
transmisión de los paquetes por la red no se realice por el camin más corto. Con el fin de obtener una
visión completa de sistemas reales seguidamente se presentan las características básicas de algunos
encaminadores actuales.

2.5.1 Características básicas de algunos encaminadores

Se muestra las propiedades de las redes de interconexión anteriormente descritas para diversos
prototipos y computadores comerciales. Como se puede observar, desde el empleo inicial de enlaces de
un bit, como en el caso del nCUBE/2, se ha llegado a enlaces de 20 bits como en el Origin.
Análogamente se observa que las mejoras en el desarrollo producen una reducción en la duración del
ciclo.

Seguidamente se muestran las características fundamentales para algunos computadores bien conocidos.

Cray T3E

El Cray T3E es el exponente de la segunda generación de una familia de sistemas multiprocesador que
comenzó con el Cray T3D. La red de interconexión en ambos sistemas es un toro 3-D. Cada unidad de
proceso está formada por un DEC Alpha 21164, 2 Gbytes de memoria, un router de comunicación y un
módulo de control. Cada procesador es capaz de procesar instrucciones por periodo de reloj, llegando a
tener un pico de hasta 600 Mflops para procesadores de 300 Mhz y 900 Mflops para procesadores de
450Mhz. Este procesador soporta aritmética de 32 y 64 bits. Puede estar compuesto por 16 a 2.048
unidades de proceso conectados mediante una red bidireccional en toro tridimensional, lo que implica un
gran ancho de banda. El sistema cuando se configura con un número de procesadores no superior a 128
se refrigera por aire. Si se aumenta el número de unidades de proceso la refrigeración es por líquido.
El sistema de memoria está compartido a nivel lógico y físicamente distribuido, con lo que todos los
procesadores tienen su propia memoria local y además pueden acceder a la memoria de los otros
procesadores sin necesidad de utilizar un protocolo de paso de mensajes. Este multiprocesador se puede
programar utilizando un modelo de paso de mensajes (MPI o PVM), o recurriendo a un modelo de
programación de memoria compartida (HPF). El T3E aumenta la capacidad de memoria del
microprocesador DEC 21164 con un conjunto de registros externos (Eregistros).
Estos registros se utilizan como fuente o destino para las comunicaciones remotas.
Todas las comunicaciones remotas y las sincronizaciones se realizan usando estos registros y la
memoria. La memoria cache posee dos niveles. El primero es una cache con 8 Kbytes para datos y 8
Kbytes para instrucciones, y la segunda cache es de 96 Kbytes siendo utilizada tanto para instrucciones
como para datos.
En este sistema, muchas características del encaminador y de la red son las mismas que las usadas en la
primera generación de estas arquitecturas, pero otras son completamente diferentes. El objetivo principal
en su desarrollo fue conseguir tolerar la latencia de la comunicación para un rango de cargas mayor que
los contemplados en la primera generación.
Para ello se hizo uso de canales de comunicación multiplexados con una mayor capacidad real. El
encaminador opera a 75 MHz y durante un único ciclo de reloj se envían 5 phits. Los canales de
comunicación son de 14 bits de ancho con lo que la unidad mínima de información que puede manejar el
router es de 70 bits. Con ello cadaflit puede transportar una palabra de 8 bytes más 6 bits de información
adicional. En este sistema el control de flujo empleado en la comunicación es wormhole. La red de
comunicación posee un ancho de banda de hasta 600 MBytes en cada dirección. Para asegurar una
conexión con un gran ancho de banda y a su vez escalable entre los nodos del sistema y los diferentes
dispositivos de entrada y salida (ya sean redes, discos ...) el CRAY T3E utiliza un canal GigaRing
escalable. Cada canal del GigaRing esta conectado al sistema Torus y a su subsistema de 1/0 a través de
múltiples puertos, en caso de que una ruta no sea disponible los canales y el sistema pueden ser
reconfigurados para tomar rutas alternativas, esto facilita el mantenimiento físico del sistema. La Figura
2.20 muestra el esquema de este encaminador.
En el encaminador del Cray T3D el mecanismo de encaminamiento también es diferente.
Dispone de un canal virtual adicional completamente adaptativo, con cuatro canales virtuales
deterministas. Con ellos se evita el deadlock en la red de interconexión. Los canales deterministas
emplean un mecanismo de encaminamiento en orden de dirección. Dos de los canales virtuales
deterministas son empleados exclusivamente por el tráfico de peticiones y los otros dos por el de
respuestas, evitando de esta manera el interbloqueo. El tamaño de los paquetes que puedemanejar este
router es de hasta 10 flits y la capacidad de almacenamiento temporal por canal sonde 22 flits para los
canales adaptativos y de 12 flits para los canales deterministas.

Myrinet

Myrinet es una red de interconexión ideada para NOWs (Network Of Workstations) de una red LAN
con características particulares para su utilización en NOWs. Así p (virtual cut-through). Consta de dos
elementos básicos: de red y los conmutadores. Ambos elementos se pueden combinar de diversas formas
diferentes topologías irregulares. Un ejemplo de red con por control de flujo es segmentado
obteniéndose Myrinet. La Se trata ejemplo, en las interfaces interfaz de red incorpora un pequeño
procesador específico denominado Owai encargado de controlar el flujo de información entre el host y
la red. La Figura 2.22 muestra su esquema. Está situado en el bus de entrada/salida del host. La interfaz
dispone de una memoria para almacenar los mensajes a procesar y el código a ejecutar por el LANai. El
software que controla y facilita el acceso a Myrinet está repartido entre el sistema operativo del host, el
controlador del dispositivo y el programa de control de la interfaz. El programa de control de la interfaz
se denomina MCP (Myrinet Control Program) y es ejecutado por el procesador LANai. El MCP es
cargado inicialmente por el controlador de dispositivo. El MCP interactúa concurrentemente con la red y
el host. Las tareas típicas del MCP son el cálculo y chequeo del CRC8, control del DMA’, recepción y
envío de paquetes, control de encaminamiento del paquete y control en la transferencia de mensajes
entre la memoria del computador y los buffers de envío y recepción. Los conmutadores están
implementados mediante crossbars. Pueden llegar a tener hasta 16 puertos y tiempos de paso en torno a
los 550 nseg. La anchura de los canales de comunicación es de 9 bits, 8 de ellos de datos y una línea
dedicada para el envío de comandos. Los canales de comunicación son multiplexados.
2.6 PARÁMETROS CARACTERíSTICOS DE LOS SISTEMAS
PARALELOS

Resulta evidente la necesidad de caracterizar los sistemas de cálculo dado que siempre será necesario
evaluar los beneficios de un sistema, tanto individualmente como para su comparación con los demás.
Así por ejemplo, para los dispositivos secuenciales el hardware se caracteriza por la capacidad del
microprocesador, de la memoria, etc., y el software mediante el análisis del coste de los algoritmos.
Todas las caracterizaciones tienen como fin último evaluar el tiempo de ejecución. Desde el punto de
vista del hardware, cuanto más rápido sea éste menor será el tiempo de ejecución de los algoritmos. Por
otro lado, en general, los métodos de análisis de los algoritmos proporcionan información del coste de
los mismos caracterizándolos en función de las operaciones más significativas, de manera que la
comparación entre ellos se realiza de forma inmediata e independientemente del hardware utilizado.
Cuando no es posible un análisis analítico, se realizan medidas temporales normalizadas con el mismo
hardware. Como puede observarse, la influencia del software y del hardware puede estudiarse de forma
independiente. Sin embargo, caracterizar los sistemas paralelos no es tarea fácil. El tiempo de ejecución
de un algoritmo paralelo depende en general de la arquitectura empleada y del número de procesadores.
Por ello el análisis de un algoritmo paralelo no puede evaluarse independientemente de la arquitectura
paralela empleada. Con el fin de caracterizar y evaluar las prestaciones de las arquitecturas paralelas
pueden establecerse un conjunto de parámetros significativos. En esta Sección se presentan aquellos que
son generales a todas las arquitecturas, como son el tiempo de ejecución (run time), la eficiencia, ... Sin
embargo, existen otros parámetros específicos para algún tipo determinado de arquitectura, como por
ejemplo para las arquitecturas paralelas con redes de interconexión estáticas. Esta clase de parámetros
serán detallados en los capítulos dedicados a sus arquitecturas.
En los sistemas serie el tiempo de ejecución, t,, viene dado por el tiempo transcurrido entre que
comienza el algoritmo hasta que finaliza en el procesador secuencial. Análogamente se define el tiempo
de ejecución paralelo, tp , como el tiempo transcurrido desde que comienza el cálculo paralelo hasta
que finaliza la ejecución en todos los procesadores del sistema paralelo.
La primera pregunta que cabe realizarse al considerar un sistema paralelo es cuánto mejora al sistema
serie o secuencial. Para caracterizar esta propiedad se define el speedup, Sup, como el cociente entre el
tiempo que necesita un único procesador y el tiempo que requiere un sistema paralelo con p
procesadores idénticos. Más precisamente el speedup se define como el tiempo de ejecución serie, t, ,
del mejor algoritmo para resolver el problema dado, dividido por el tiempo utilizado por el sistema
paralelo con p procesadores idénticos e iguales al utilizado en el sistema secuencial. En teoría el
speedup será menor o igual que p, pero nunca mayor. Si fuese así entonces algún procesador acabaría
antes de t s / p , pero eso significaría que el procesador serie podría resolver el problema en un tiempo
menor a ts, lo cual contradice su definición. En la práctica en algunas ocasiones puede observarse que el
speedup es mayor que p, hecho conocido como speedup superlineal. Esto suele deberse a que la
paralelización ofrece posibilidades que dejan en desventaja al algoritmo secuencial. Por ejemplo,
supóngase un algoritmo secuencial de clasificación mixto, que utiliza, por ejemplo, una mezcla
polifásica para ordenar en memoria secundaria y un quicksort para ordenar en memoria primaria (ver
por ejemplo (Hernández, 2000)]). Sin embargo, al paralelizar el algoritmo, los datos pueden distribuirse
entre las memorias de los procesadores de manera que la necesidad de clasificar en memoria secundaria
disminuirá e incluso desaparecerá, con lo que al ser una tarea costosa el algoritmo paralelo parece
mejorar al secuencial en más de p. Evidentemente, en estos casos la comparación no es válida, puesto
que los algoritmos secuencial y paralelo no están en igualdad de condiciones. De hecho, aportando
memoria suficiente al sistema secuencial podría utilizarse sólo un algoritmo quicksort secuencial. En
principio un speedup de p sólo puede darse en el caso ideal, en el que todos los procesadores pueden
ocupar el 100% de su tiempo en resolver el problema. Sin embargo los sistemas paralelos requieren
comunicarse para transmitir los datos entre los procesadores, para lo que se necesita un cierto tiempo.
Un parámetro que caracteriza este hecho es la eficiencia, E, que es una medida del tiempo que un
procesador emplea de forma útil. Se define como el cociente entre el speedup y el número de
procesadores:

y su valor estará entre O y 1. En el caso ideal, Sup = p y entonces E = 1.

En los sistemas paralelos el coste viene determinado por el producto del tiempo de ejecución paralelo y
el número de procesadores, tp x p , que viene a expresar el tiempo total empleado por todos los
procesadores. Obsérvese que en términos de eficiencia:

Es decir, la eficiencia es el cociente entre el coste secuencial y el paralelo.

Se entiende que un sistema paralelo tiene coste óptimo cuando el coste del sistema paralelo es
proporcional al tiempo de ejecución serie del algoritmo secuencial más rápido. En términos de
eficiencia, los sistemas paralelos de coste óptimo tienen una eficiencia del orden de 1, ya que es el
cociente entre coste secuencia1 y paralelo. Es decir, como tp x p = ts E = 1 . El tiempo de ejecución
paralelo puede ser diferente para un mismo problema dependiendo de cómo se divida la tarea entre los
procesadores. Por ejemplo, la multiplicación de una matriz cuadrada de dimensión n por un vector en
una arquitectura hipercubo con p procesadores es más rápida si la matriz se divide en p bloques
cuadrados que en p rodajas de nip filas cada una. Por ello, la manera en que se aplican los datos sobre
los procesadores es un factor importante en el diseño de los algoritmos paralelos.

Aunque el concepto tamaño del problema se entiende de forma intuitiva, es necesario precisarlo. Una
manera inicial de establecerlo sería en función del tamaño de los datos de entrada del problema, como
por ejemplo la dimensión de las matrices, la cantidad de datos a ordenar, etc. Sin embargo, este
planteamiento presenta la desventaja de que la interpretación del tamaño del problema es diferente para
distintos problemas. Por ejemplo, el duplicar el tamaño de una matriz implica un aumento en el tiempo
de ejecución para la suma de matrices que sería la mitad que si se multiplicaran. Una medida adecuada
del tamaño del problema debería ser tal que al duplicar el tamaño del problema, se necesitara el doble de
cálculo computacional para resolverlo.

Por ello se define el tamaño del problema en función del número total de operaciones básicas que deben
realizarse para resolverlo. En concreto el tamaño del problema, tam, se define como el número de etapas
computacionales básicas del mejor algoritmo secuencial. En general el
tamaño del problema se normaliza de manera que se considera que un paso computacional básico''
requiere de una unidad de tiempo. Con ello, el tamaño del problema será igual al tiempo de ejecución
serie del mejor algoritmo secuencial.
Como ya se indicó anteriormente, los sistemas reales no ofrecen una eficiencia de uno, entre otras
razones debido, por ejemplo, a la necesidad de transmitir información entre los procesadores, con lo que
se requiere un tiempo para las comunicaciones. Lógicamente la eficiencia podrá disminuir debido a otros
factores adicionales. De este modo se define la función overhead, to, como el tiempo total empleado por
todos los procesadores que excede al tiempo requerido por el algoritmo secuencial que resuelve el
mismo problema en un único procesador.
Recuérdese que la suma del tiempo que emplean todos los procesadores, es decir, el coste, viene dado
por ptp , y el tiempo de cálculo útil está determinado por tam. Atendiendo a la definición anterior,
entonces el resto es overhead. Así:
Como puede observarse, la función overhead depende tanto del tamaño como del número de
procesadores, to = to (tam,p) . Obsérvese que si el tamaño del problema permanece constante y el
número de procesadores aumenta entonces el overhead aumenta. Como ya ha sido indicado una de las
principales causas de overhead es la comunicación entre procesadores. Si cada procesador necesita un
tiempo t,,, para sus comunicaciones, entonces el conjunto de los procesadores contribuirán al overhead
enp t,,, .
Un segundo factor fundamental que afecta al overhead es el balance de carga. En muchas aplicaciones
paralelas, como la búsqueda o la optimización, es extraordinariamente difícil predecir el tamaño de las
tareas asignadas a cada procesador, de manera que se realice una división de las mismas para que todos
mantengan la carga computacional uniforme. Cuando no es uniforme, es decir, hay desbalanceo en la
carga, entonces algunos procesadores terminarán permaneciendo inactivos mientras otros todavía están
calculando.

Frecuentemente todos los procesadores o algunos de ellos necesitan algún sincronismo durante la
ejecución del programa, de forma que si no están todos en la misma situación en todo instante entonces
algunos de ellos deberán esperar a que otros terminen. Todo el tiempo de inactividad de los procesadores
contribuye al overhead.
Una tercera fuente de overhead es debida a la necesidad de utilizar algoritmos distintos para el caso
paralelo y secuencial. Esto ocurre cuando el mejor algoritmo secuencial para resolver el problema es
muy difícil de paralelizar. Entonces es necesario paralelizar otro de menor eficacia y con coste
computacional mayor. Pero este mayor coste computacional puede encontrarse incluso cuando los
algoritmos secuenciales y paralelos son iguales. Por ejemplo, la transformada rápida de Fourier
paralelizada requiere más cálculos porque los resultados obtenidos en el algoritmo secuencial son
reutilizables, mientras que en el paralelo no, ya que son obtenidos por diferentes procesadores.
En función del overhead pueden establecerse un gran número de parámetros. Por ejemplo, despejando
tp de la Ecuación 2.2 se obtiene:

y teniendo en cuenta que el speedup vendrá dado por:

y teniendo en cuenta que el speedup vendrá dado por:

La interpretación de esta expresión es importante. Obsérvese que si el tamaño del problema se mantiene
constante y el número de procesadores aumenta, el overhead aumenta y la eficiencia disminuye. Si el
tamaño del problema aumenta y el número de procesadores se mantiene constante entonces la eficiencia
aumenta, ya que tp depende del tamaño y to crece más lentamente que el tamaño para un p fijo. Como
puede observarse, para estos sistemas paralelos cuando el tamaño del problema crece se puede mantener
la eficiencia aumentando el número de procesadores. Sin embargo no todos lo hacen del mismo modo.
Por ejemplo, algunos sistemas requieren que el tamaño crezca exponencialmente cuando aumenta p. Sin
embargo otros sólo necesitan un crecimiento lineal. Los primeros son sistemas poco escalables ya que
para mantener buenos speedups cuando aumenta p es necesario que el tamaño del problema crezca
enormemente, mientras que los segundos son altamente escalables. Como puede observarse en la
Ecuación 2.4 la eficiencia puede mantenerse en un valor determinado si el cociente to tam es I
constante. Teniendo esto en cuenta, para formalizar el concepto de escalabilidad se introduce una
métrica que permite establecer cuantitativamente el grado de escalabilidad del sistema. Así, para un
valor determinado de la eficiencia, despejando en la Ecuación 2.4 se obtiene:

y K = E/(l- E) será constante para una eficiencia dada. Así:

Esta función se conoce como función de isoeficiencia, e indica la facilidad que un sistema tiene para
mantener la eficiencia constante y, por tanto, la capacidad de obtener speedups crecientes
proporcionalmente con el aumento de procesadores. Un valor pequeño de la función de
isoeficiencia indica que el sistema es altamente escalable mientras que un valor grande señala que es
poco escalable. Sin embargo, existe un límite inferior para esta función. Para un problema dado con un
número determinado de unidades de trabajo, tam, el número máximo de procesadores que pueden ser
utilizados con coste óptimo es tam, ya que más procesadores estarían inactivos.
Del mismo modo, si el tamaño del problema crece con una rapidez menor del O(p>" cuando el número
de procesadores crece, entonces el número de procesadores será mayor que el tamaño del problema, y
los que estén por encima de este valor estarán inactivos. Incluso para un sistema paralelo ideal sin coste
en las comunicaciones ni overhead alguno la eficiencia disminuirá debido a los procesadores inactivos.
No debe olvidarse que la función de isoeficiencia sólo se define para los sistemas paralelos que son
escalables en alguna medida, ya que para los sistemas no escalables no es posible mantener constante la
eficiencia al aumentar el número de procesadores, sin entrar siquiera a considerar el crecimiento del
tamaño.

Por tanto, para mantener la eficiencia el tamaño del problema debe crecer asintóticamente al menos tan
rápido como @(p) , por ello SZ(p)12 es el límite inferior asintótico de la función de isoeficiencia.

La función de isoeficiencia engloba las características del sistema paralelo completo, es decir, tanto de la
arquitectura paralela como del programa. Una vez realizado el análisis de esta función pueden analizarse
las características del programa paralelo sobre un número pequeño de procesadores y predecir el
comportamiento sobre un número mayor, con lo que puede estimarse si conviene o no aumentarlos. Pero
además es capaz de caracterizar el paralelismo inherente en un programa paralelo, y también es
fundamental para analizar el comportamiento de un sistema paralelo ante cambios en los parámetros del
hardware, como la velocidad de los procesadores o la velocidad de las comunicaciones.
Otra relación de interés es la que se establece entre el tamaño del problema y la función overhead.
Recuérdese que un sistema paralelo es de coste óptimo si el producto entre el número de procesadores y
el tiempo de ejecución paralelo es proporcional al tiempo de ejecución del mejor algoritmo secuencia1
en un único procesador, es decir:

Remplazando:
Como puede observarse de los anteriores razonamientos, la función overhead es el parámetro crítico que
caracteriza a los sistemas paralelos, ya que para una función overead determinada, el tiempo de
ejecución paralelo, el speedup, la eficiencia y el coste pueden expresarse en función del número de
procesadores y del tamaño del problema.
Por último, son de interés dos parámetros que determinan valores mínimos. El primero de ellos es el
tiempo mínimo de ejecución, tFin, que indica cuál es el menor tiempo de ejecución posible de un
algoritmo paralelo, considerando que el número de procesadores es variable.
Suponiendo que la función tp (tam,p) es diferenciable, el tiempo mínimo de ejecución puede obtenerse
derivando respecto a p:

2.7 CONCLUSIONES

En este Capítulo se han presentado los aspectos básicos de la computación paralela. En primer lugar se
han indicado los conceptos fundamentales, como paralelización, grado de paralelismo, etc., y se ha
mostrado una perspectiva histórica de computación paralela, tanto de los requerimientos
computacionales como del rendimiento de los sistemas realizados.
Seguidamente se ha presentado una clasificación que muestra los aspectos generales y las ideas
fundamentales que sustentan las diversas opciones y soluciones, sin pretender ser exhaustiva.
Partiendo de los computadores secuenciales se presenta la taxonomía de Flynn, ya clásica, como punto
de partida para profundizar en las características de las diversas opciones existentes para realizar
arquitecturas paralelas. A continuación se profundiza en el aspecto más relevante y diferenciador: la
organización del espacio de direcciones de memoria. Con ello se analiza la división de las arquitecturas
en sus dos tipos básicos: Sistemas de memoria compartida o multiprocesadores y Sistemas de
memoria distribuida o multicomputadores. Se presentan los
aspectos fundamentales de cada uno de ellos, los parámetros característicos y los prototipos y sistemas
comerciales más significativos. Dentro de cada uno de ellos se analizan las diferentes estrategias,
llegando a matizar cada categoría y realizando una clasificación clara de cada una de ellas.
A continuación se presentan otros criterios de clasificación, como son la granularidad de procesador, y
especialmente las redes de interconexión utilizadas. Se analizan detalladamente los factores que influyen
en las redes de interconexión y se muestran las características básicas de algunos de los encaminadores
bien conocidos. Por último se analizan los parámetros característicos de los sistemas paralelos en
general, mediante los cuales se pueden realizar las caracterizaciones y las comparaciones necesarias para
determinar la eficacia de un sistema paralelo para resolver un problema determinado.
Una vez presentados los aspectos fundamentales de las arquitecturas paralelas en el siguiente Capítulo se
presentan con profundidad los sistemas de memoria compartida o multiprocesadores, profundizando en
sus características y estrategias.