Post on 04-Apr-2018
7/30/2019 33611748 Sistemas de Memoria Distribuida
1/31
LOS SISTEMAS DE MEMORIA DISTRIBUIDA OMULTICOMPUTADORES
Los sistemas de memoria distribuida o multicomputadores pueden ser de dos tipos bsicos.
El primero de ellos consta de un nico computador con ltiples CPUs comunicadas por un
bus de datos mientras que en el segundo se utilizan mltiples computadores, cada uno con su
propio procesador, enlazados por una red de interconexin ms o menos rpida. En el
primer caso, se habla de procesadores masivamente paralelos (MPPs, Massively Parallel
Processors), y en el segundo se conocen de forma genrica como clusters.
En este Captulo se presentan detalladamente los sistemas de memoria distribuida o
multi-computadores. En primer lugar se detallan las redes de interconexin caractersticas
de esta arquitectura, que como se indic en el Captulo 2 son las redes estticas, mostrando
las topologas fundamentales. Seguidamente, el inters se centra en los clusters con el fin
de que el lector sea capaz de configurar una arquitectura paralela de este tipo. Para ello, se
comienza con una serie de consideraciones generales sobre los clusters, se justifica por qu son
especialmente interesantes y se comentan algunos de los ms significativos. A continuacin
se detalla cundo es de inters el uso de un cluster y qu tipos de herramientas de
programacin se han desarrollado. En la siguiente Seccin se analizan las diferentes
alternativas de programacin sobre clusters, para centrarse posteriormente en la
7/30/2019 33611748 Sistemas de Memoria Distribuida
2/31
7/30/2019 33611748 Sistemas de Memoria Distribuida
3/31
mensaje mediante software y enviarlo a travs de la red de interconexin, mientras que el
segundo debe recibirlo (Captulo 2).
Una red esttica, tambin denominada red directa, es una red cuya topologa queda
definida de manera definitiva y estable durante la construccin de la mquina paralela.
Como se puede apreciar, el papel de la red de interconexin es tanto mi% importante
cuanto mayor sea el nmero de elementos fsicos que se deben unir y el flujo de informacin
que se desee intercambiar.
La conexin directa entre los procesadores hace que las redes estticas sean
especialmente adecuadas para la comunicacin mediante paso de mensajes y, por tanto,
para los sistemas de memoria distribuida.
En general, las redes estticas pueden presentar distintas topologas en funcin de las
conexiones punto a punto que se establezcan entre sus procesadores. Se pueden dividir en
cuatro tipos bsicos: redes unidimensionales, bidimensionales, tridimensionales e hipercubos.
Las redes unidimensionales son las ms sencillas de realizar. La idea ms inmediata es
conectar cada procesador a dos procesadores vecinos, uno a la derecha y otro a la
izquierda. La Figura 4.l.a muestra esta disposicin, conocida como red lineal, en la que
todos los procesadores salvo los extremos estn enlazados a otros dos procesadores.
La diferencia fundamental de las redes lineales con el bus radica en el hecho de que en un
momento dado puede realizarse ms de una transferencia simultneamente siempre que
sea a travs de enlaces diferentes. Por ejemplo, un procesador puede enviar un mensaje
simultneamente a un procesador situado a su izquierda y a otro a su derecha. Esta
topologa es muy simple pero presenta problemas de comunicacin cuando el nmero de
procesadores es elevado.
7/30/2019 33611748 Sistemas de Memoria Distribuida
4/31
7/30/2019 33611748 Sistemas de Memoria Distribuida
5/31
comunicaciones entre dos procesadores se establecen a travs del procesador central. En
estas redes dicho procesador es fundamental.
Como aplicacin directa de las estructuras de datos tipo rbol surgen las redes rbol. En
ellas hay un procesador en cada nodo del rbol y slo un camino de conexin entre cualquier
par de procesadores. En la Figura 4.4 se muestra una red de rboles binarios.
Las redes lineales y las redes en estrella son casos particulares de la topologaen rbol. El
camino de comunicacin se realiza de la siguiente forma: cuando un procesador enva un
mensaje lo transmite hacia arriba en el rbol hasta que encuentra el procesador destino o
llega al nodo raz del menor subrbol que contiene tanto al procesador origen como al destino.
En este caso una vez alcanzado este nodo raz, el mensaje desciende por el rbol hasta
encontrar el destino. El computador DADO utiliza una red en rbol binario.
7/30/2019 33611748 Sistemas de Memoria Distribuida
6/31
Las redes de rboles tienen la desventaja de que las comunicaciones pueden verse
comprometidas en un nodo cuando el nmero de procesadores es grande y se realizancomunicaciones entre procesadores situados en los niveles superiores. As por ejemplo, si
muchos procesadores del subrbol izquierdo requieren comunicarse con muchos procesadores
del derecho, entonces el nodo raz debe manejar todos los mensajes, con lo que la
eficacia del sistema disminuye significativamente ya que aumenta el tiempo empleado para
las comunicaciones.
Una estrategia comnmente para aliviar esta desventaja usada consiste en aumentar el
nmero de conexiones de comunicacin entre los procesadores de menor nivel, es decir,
los cercanos a la raz. Esta red, que se muestra en la Figura 4.5, es conocida como red de rbol
grueso vat tree). El computador CM-5 utiliza este tipo de red.
Las redes en rbol tienen una equivalencia dinmica, realizada de manera que los nodos
intermedios son elementos de conmutacin mientras que las hojas son procesadores.
Por ltimo, las redes bidimensionales tipo mesh surgen como una extensin de las redes
lineales. En las redes mesh bidimensionales cada procesador se conecta directamente
con otros cuatro procesadores salvo en los extremos, tal y como se muestra en la Figura
4.6.a. Cuando los procesadores forman una estructura cuadrada con igual nmero de
procesadores en cada dimensin se denomina mesh cuadrado, y si el nmero de
procesadores es diferente en las dos dimensiones se denomina mesh rectangular. Como
es natural los procesadores extremos pueden conectarse entre ellos, como se hace con los
7/30/2019 33611748 Sistemas de Memoria Distribuida
7/31
7/30/2019 33611748 Sistemas de Memoria Distribuida
8/31
Los hipercubos presentan propiedades especialmente interesantes, entre las que destacan
las siguientes:
- Dos procesadores se conectan entre s, si y slo si sus etiquetas, en binario, tienen
exactamente un bit distinto en una posicin determinada, tal y como se muestra en la
Figura 4.8.
- Un procesador de un hipercubo de dimensin d se conecta directamente a d
procesadores.
- Todo hipercubo de dimensin d puede dividirse en dos de dimensin d-1. Para ello se
selecciona la posicin de un bit y se agrupan todos los procesadores que tengan un cero en
esa posicin. Todos ellos forman una particin y el resto forma la segunda particin. La Figura
4.9 muestra las tres particiones de un hipercubo tridimensional. Las lneasgruesas
conectan los procesadores que pertenecen a una misma particin. Las etiquetas que
identifican un procesador en un hipercubo de dimensin d consta de d bits. Para
cualquier grupo de k bits fijo, los procesadores que difieren en los dems d-k bits forman un
subcubo de dimensin d-k formada por 2(&'") procesadores. Dado que con IC bits se
pueden obtener 2'" combinaciones diferentes, se tendrn 2k subcubos distintos. En la
Figura 4.10 se ilustra este hecho, para k2 y d=4. En la Figura 4.10.a se muestran los cuatro
subcubos, cada uno de ellos formado por cuatro procesadores, cuando los bits fijados son
7/30/2019 33611748 Sistemas de Memoria Distribuida
9/31
los dos ms significativos, y en la Figura 4.10.b los obtenidos cuando se fijan los dos bits menos
significativos.
Un parmetro de especial inters es la denominada distancia de Hamming, que se define
como el nmero total de posiciones de bits para los que las etiquetas de dos
procesadores son diferentes. Por ejemplo, la distancia de Hamming para los procesadores O11
y 101 es dos, y entre 111 y O00 es tres. Con todo ello, la distancia de Hamming entre
dos procesadores de etiquetas a y b es el nmero de bits a 1 que hay tras el resultado
de la operacin a@ b, donde @ es la or-exclusiva. El nmero de enlaces por el camino ms
corto entre dos procesadores viene dado por la distancia de Hamming. La Figura 4.8.e
muestra la ruta de un mensaje desde el procesador a=0101 al procesador b=1011. La
distancia de Hamming en este caso es tres, ya que a Ob = 1110. El mensaje se transmite por
las dimensiones para las que la posicin de a O b vale 1, en este caso para las imensiones
tres (bit ms significativo), dos y uno. Obsrvese que debido a que aOb tiene como mximo d
bits que valen 1, el camino ms corto entre dos procesadores de un hipercuboconsta
como mximo de d enlaces Computadores tpicos que utilizan una topologa hipercubo son
los nCUBE 2, iPSC y Cosmic Cube.
7/30/2019 33611748 Sistemas de Memoria Distribuida
10/31
Generalizando la nomenclatura de las topologas se definen las redes d-cubo k-arias. En
ellas, d es la dimensin de la red y k es el nmero de procesadores en cada dimensin.A este factor se le denomina radio. As por ejemplo, un hipercubo de dimensin d, que no es
sino un mesh d-dimensional con dos procesadores en cada dimensin, sera un d-cubo 2-ario.
Por otro lado, un anillo sera un 1-cubo pario. Ambas topologas seran los extremos de la
topologa general &cubo k-arias. Finalmente, obsrvese que en las redes &cubo k-arias el
nmero total de procesadores ser IP.
4.1 .I Especificaciones de las redes estticas
En general son cuatro los parmetros que caracterizan una red esttica: el dimetro, laconectividad, el ancho de banda de biseccin y el coste. El dimetro de la red se define
como la mxima distancia entre dos procesadores cualesquiera, entendindose por
distancia el mnimo camino entre ellos, es decir, el camino que los une con el menor nmero
de enlaces. Cuanto menor sea la distancia, ms rpidas sern las comunicaciones ya que
a mayor distancia se necesita ms tiempo de comunicacin. En este sentido, el dimetro
determina el peor de los casos.
La conectividad de una red es una medida de la multiplicidad de caminos entre dos
procesadores. Cuanto mayor sea mejores prestaciones se obtienen ya que es menor la
contencin en las comunicaciones. Como medida de la conectividad se suele tomar la
conectividad de arco, que es el menor nmero de arcos que deben eliminarse para obtener dos
redes disjuntas.
Los parmetros ms inmediatos para establecer la rapidez de las comunicaciones son: el
ancho de canal, la velocidad de canal y el ancho de banda. Se define el ancho de canal
como el nmero de bits que pueden transmitirse simultneamente por el canal que
comunica dos procesadores, que es igual al nmero de cables fsicos del enlace. La velocidad
mxima con que se puede emitir por cada cable fsico se conoce como velocidad del canal.
Con todo ello se define el ancho de banda del canal como la velocidad mxima con la que
los datos pueden enviarse entre dos enlaces de comunicacin, y es evidentemente el producto
de la velocidad del canal y el ancho de canal.
7/30/2019 33611748 Sistemas de Memoria Distribuida
11/31
Sin embargo, con este parmetro no se caracteriza toda la red. Para ello se define el ancho de
biseccin como el mnimo nmero de enlaces de comunicacin que deben eliminarse para que
la red quede dividida en dos partes iguales. Con ello, se define el ancho de banda de biseccin
como el menor volumen de comunicaciones permitidas entre dos mitades cualesquiera de
la red con igual nmero de procesadores. As, el ancho de banda de biseccin es el productodel ancho de biseccin y del ancho de banda del canal.
Por ltimo, el coste puede medirse de muy diversas formas. La mas general consiste en
medir el nmero de enlaces de comunicacin o la cantidad de cableado necesario en la
red. Por otro lado, el ancho de banda de biseccin tambin suele utilizarse como medida de
coste ya que establece el menor nmero de comunicaciones.
Una vez analizadas las redes estticas, tanto sus topologas como las propiedades que las
caracterizan, seguidamente se estudian los multicomputadores ms accesibles, los clusters.
4.2 CLUSTERS
En esta Seccin se presentan detalladamente los clusters. En primer lugar se recuerdan sus
caractersticas generales para a continuacin presentar las razones por las que los clusters
7/30/2019 33611748 Sistemas de Memoria Distribuida
12/31
7/30/2019 33611748 Sistemas de Memoria Distribuida
13/31
7/30/2019 33611748 Sistemas de Memoria Distribuida
14/31
qu CPU se tendra que utilizar si la necesidad de potencia de clculo se multiplicase
por cien? La segunda opcin, el procesamiento en paralelo, no es de implantacin tan
inmediata, pero escala mucho mejor con las necesidades del problema.
Recurdese que el procesamiento paralelo consiste en acelerar la ejecucin de un programa
mediante su descomposicin en fragmentos que puedan ejecutarse de forma paralela, cada
uno en su propia unidad de proceso. La mayora de los procesadores modernos incorporan
en su diseo unidades que trabajan de forma paralela, como los que emplean la
tecnologa del pipelining (operar a la vez sobre las distintas fases que requiere la
ejecucin de una instruccin del procesador, como en una cadena de montaje), o el
procesamiento superescalar (la ejecucin en paralelo de instrucciones independientes). Los
denominados procesadores vectoriales que forman parte de los supercomputadores
tradicionales, como el Cray C90, son capaces de operar simultneamente sobre varios
elementos de un vector. Ms recientemente toma cuerpo el concepto de paralelismo sobre un
registro, como el que implementan las extensiones mutimedia de Intel MMX.
No obstante, desde comienzos de la dcada de los 90 ha existido una tendencia creciente a
alejarse de los supercomputadores especializados paralelos (supercomputadores
vectoriales y procesadores masivamente paralelos, MPPs), debido a sus elevados costes
en hardware, mantenimiento y programacin. En este contexto los clusters constituyen
una alternativa de menor coste ampliamente utilizada y consolidada.
Entre los motivos que han hecho posible este hecho cabe destacar el gran progreso en la
disponibilidad de componentes de un alto rendimiento para PCs/estaciones de trabajo y
redes de interconexin. Gracias a estos avances, se ha logrado que un cluster sea hoy da un
sistema muy atractivo en cuanto a su relacin coste/rendimiento para el procesamiento
paralelo. Se puede decir que los clusters de computadores se han convertido en la opcin
ms sencilla y extendida encomputacin paralela. Ofrecen a cualquier institucin acadmica
una atractiva oportunidad para utilizar y ensear computacin de altas prestaciones (HPC,
High Performance Computing) sin requerir el acceso a equipamientos costosos.
Las principales caractersticas de estos sistemas, que les hacen tener algunas ventajas
sobre otros tipos de arquitecturas paralelas, son las siguientes:
Se pueden construir con un esfuerzo relativamente moderado. Son sistemas de bajo coste.
7/30/2019 33611748 Sistemas de Memoria Distribuida
15/31
Utilizan hardware convencional y accesible (el disponible en el mercado de consumo). Utilizan
un sistema de comunicacin basado en una red de rea local rpida como Myrinet o
Fast Ethernet.
Utilizan un sofiivare de libre distribucin, como Linux, y algn entorno de programacin
paralelo como pueden ser PVM (Parallel Virtual Machine) o MPI (Message Passing
ZnterjGace) . Son sistemas escalables, es decir, se pueden ajustar a las necesidades
computacionales y permitir una ejecucin eficiente teniendo en cuenta las demandas de las
aplicaciones secuenciales y paralelas.
Cada mquina de un cluster puede ser un sistema completo utilizable o aprovechable para
otros propsitos.
Reemplazar un computador defectuoso de un cluster es trivial, incluso es posible disear
el c2uster de tal forma que si un nodo falla, el resto contine trabajando. El rendimiento y los
recursos del cluster pueden crecer con el tiempo beneficindose de las ltimas tecnologas
computacionales y de redes.
Adems, debido a la estandarizacin se tiene la garanta de que los programas escritos
para un cluster funcionarn en cualquier otro con independencia del tipo de procesador de
cada nodo sin ms que recompilar el cdigo.
Pero a pesar de estas ventajas los clusters tambin presentan algunas desventajas:
1) Las redes ordinarias no estn diseadas para el procesamiento paralelo. La latencia de red
es alta y el ancho de banda relativamente bajo si se comparan con los de un sistema
SMP (Symmetric MuZtiProcessors). Adems, si el cluster no est aislado del resto de la red
de la institucin, la situacin es an peor.
2) En los sistemas operativos monoprocesador existe muy poco software para tratar un
cluster como un nico sistema. Por ejemplo, el comando ps slo lista los procesos de un
sistema Linux, no los de todo el cluster.
Indudablemente existen y han existido plataformas ms potentes, ms costosas y ms
difcilmente accesibles que los clusters de computadores. El desarrollo de software para
estas plataformas es costoso, dado que debe ser programado o comprado por un
reducido nmero de usuarios. Su vida til suele acabar cuando aparece un nuevo tipo de
supercomputador con arquitectura y procesadores superiores, lo cual obliga a iniciar de
nuevo el costoso proceso de adquirir el hardware y el sofiare.
7/30/2019 33611748 Sistemas de Memoria Distribuida
16/31
En comparacin, los clusters pueden ir incorporando computadores cada vez ms potentes
conforme vayan estando disponibles comercialmente, equilibrando la carga de trabajo
segn las prestaciones de cada computador, retirando eventualmente los computadores
ms antiguos si fuera conveniente, y utilizando siempre no slo el software previamente
existente sino tambin el nuevo software que previsiblemente ir apareciendo,desarrollado por una base de usuarios cada vez ms extensa (atrados por el bajo costo del
hardware y del software), con menor costo, menor esfuerzo y mayor utilizacin.
Por tanto, debido a la flexibilidad que ofrece este tipo de arquitectura, cada da aparecen
sistemas ms potentes y con mayor nmero de procesadores. A continuacin, se
mencionan.
algunos de los clusters ms representativos, abarcando tanto los grandes sistemas, que
poseen los grandes laboratorios, como los ms modestos.
En primer lugar, y por derecho propio, se encuentra Avulon. La Figura 4.11 muestra una
fotografa parcial de este sistema. Hasta hace relativamente poco tiempo ha sido el
cluster ms poderoso. A principios del ao 2001 ya ocupaba el sexto lugar de la
clasificacin de los clusters ms potentes. Con sus 140 procesadores DEC Alpha 21164A
(533 MHz) con 256 Mbytes, se encontraba entre los 500 supercomputadores ms
potentes del mundo, considerando todos los sistemas paralelos, no slo los clusters. Se
utiliza como supercomputador de propsito general destinado a la investigacin, y se le
encomiendan problemas que abarcan desde la astrofsica a la dinmicamolecular.
Por otro lado, COCOA, con 50 procesadores Pentium 11, se destina a problemas de
ingeniera aerospacial. El cluster Tux efecta predicciones climticas y el Chaingang realiza
clculos de qumica computacional para la fabricacin de nuevos medicamentos.
Gargleblaster tiene fines docentes y de investigacin.
7/30/2019 33611748 Sistemas de Memoria Distribuida
17/31
Collage tiene 18 procesadores, se dedica al proyecto ActiveMural, un dispositivo de
visualizacin de alta resolucin; actualmente utiliza 15 proyectores XGA y alcanza una
resolucin, que se espera incrementar, de 4.920~2.204 pixels.
hki, hermano pequeo de Avalon, slo tiene 16 procesadores Pentium Pro, donde cada
nodo est conectado directamente a otros cuatro. En la Figura 4.12 se puede observar
una fotografa del mismo. Realiz la simulacin de la interaccin gravitatoria de 9,75
millones de partculas, problema de gran inters en astrofsica y cosmologa, en tres das,
con una velocidad mantenida de alrededor de 1 Gigaflop
La industria del cine tambin saca partido a estos sistemas. La empresa californiana
Digital Domain fue la encargada de los efectos especiales de la pelcula Titanic, escrita y
dirigida por James Cameron. Para ello se cont con un sistema formado por 350
procesadores SGI, 200 procesadores DEC Alpha y 5 Terabytes de disco, conectados por redes
de 100 Mbps o superiores.
Como ltimo ejemplo de cluster hay que destacar el que se ha construido en el
Departamento de Informtica y Automtica de la UNED, llamado Smaug, con 16 procesadores
AMD K7 500 MHz y 384 Mbytes de memoria principal. La Figura 4.13 muestra una
fotografa de este cluster. Por ltimo destacar que en el Apndice A se detallan los
pasos que se deben seguir para la construccin de un cluster sencillo.
7/30/2019 33611748 Sistemas de Memoria Distribuida
18/31
4.2.3 Cundo y cmo utilizar un cluster?
La razn de ser del procesamiento paralelo es acelerar la resolucin de un problema. La
aceleracin (speedup) que puede alcanzarse depende tanto del problema en s como de
la arquitectura del computador paralelo. Las aplicaciones que se benefician de una
aceleracin ms significativa son aquellas que describen procesos intrnsecamente
paralelos. Este hecho ya fue descrito en el Captulo 2 para los sistemas paralelos en
general, y a continuacin se tratan para los clusters especficamente. En cualquier caso
debe tenerse en cuenta el hardware de la mquina ya que es preciso maximizar la relacin
entre el tiempo de clculo til y el cpe~did~ en el paso de mensajes, parmetros que
dependen de la capacidad de proceso de las CPUs y de la velocidad de la red de
7/30/2019 33611748 Sistemas de Memoria Distribuida
19/31
comunicaciones respectivamente. La clave consiste en descomponer el problema de tal
forma que cada procesador pueda operar el mayor tiempo posible sobre su fragmento de los
datos, sin tener que recurrir a los de los dems procesadores. Por ejemplo, el clculo del
rea bajo una curva por integracin numrica es un ejemplo de aplicacin completamente
paralelizable. Basta con dividir el intervalo de integracin entre todos los procesadoresdisponibles y que cada uno resuelva su fragmento sin preocuparse de qu hacen los dems. Al
final, los resultados parciales se recolectan y se suman convenientemente.
Con n procesadores es posible resolver el problema TZ veces ms rpido que haciendo uso
de uno slo (salvo por el mnimo retraso que supone el reparto de trabajo inicial y la
recoleccin de datos final), consiguiendo una aceleracin lineal con el nmero de
procesadores. La Figura 4.14 muestra la curva de aceleracin frente al nmero de
procesadores para distintos casos de aplicaciones paralelas. Si las condiciones son muy
favorables es incluso posible alcanzar laaceZeraci6n superlineal, donde el programa se
ejecuta an ms rpido que en rgimen lineal. La aparente paradoja se entiende
recordando (ver Seccin 2.5) que cada procesador cuenta con su propia memoria principal
y su memoria cache, que pueden ser utilizadas de forma ms eficiente con un subconjunto
de los datos. De hecho, es posible que el problema no se pueda resolver en un nico
procesador pero s sobre un cluster, simplemente por cuestin de tamao de los datos. En el
ejemplo de la Figura 4.14 se ha conseguido que un cluster de seis nodos haga el trabajo de
siete computadores independientes. En el extremo opuesto se encuentran los problemas
que se paralelizan muy mal, es decir, necesitan estar continuamente compartiendo datos
entre procesadores para obtener el resultado final. Las comunicaciones determinan el
avance del programa y es posible encontrar que su ejecucin en un cluster sea ms lenta
que en un nico computador. Este caso corresponde a la curva etiquetada como
Decelerucid en la Figura 4.14
7/30/2019 33611748 Sistemas de Memoria Distribuida
20/31
Los programas que se ejecutan sobre arquitecturas paralelas consisten, a menudo, en un
algoritmo bsico que se repite muchas veces y donde entre paso y paso los
procesadores intercambian informacin con sus vecinos. Por ejemplo, en el clsico juego
de la vida en dos dimensiones cada celda sobrevive en la prxima generacin si en la
actual tiene exactamente dos vecinos vivos. Si se programa el juego en un cluster y sedecide que cada procesador va a encargarse de una nica celda, cada computador en
cada paso precisa conocer el estado de sus ocho celdas vecinas, lo que supone un
intercambio de mensajes con los ocho computadores correspondientes. Otros problemas
requieren que cada procesador conozca, tras cada paso, el estado del sistema completo,
con lo que todos los datos deben propagarse a todos los computadores. Es el caso de las
simulaciones que involucran interacciones de largo alcance, como la gravitatoria o la
culombiana. Todas estas aplicaciones ofrecen un grado de paralelismo intermedio entre
el rgimen lineal y el de deceleracin. La curva de aceleracin resultante se asemeja a laetiquetada como Tipica
en la Figura 4.14. La aceleracin es prcticamente lineal cuando
el nmero de computadores en el cluster es pequeo, pero al ir aadiendo nodos el tiempo de
distribucin de los datos comienza a ser significativo y la ejecucin ya no se acelera tanto. En
el ejemplo de la Figura 4.14 es preciso utilizar nueve nodos para hacer que el programa se
ejecute aproximadamente seis veces ms rpido que en un monoprocesador; esta es una
cifra habitual en clusters reales.
Por ello, es interesante utilizar un cluster si la aplicacin es suficientemente paralela y/o
ha sido ya paralelizada (reescrita para hacer uso de procesamiento paralelo) o se est
en disposicin de hacerlo. Cada vez es posible encontrar ms paquetes de software que
han sido adaptados para su ejecucin en un cluster. Red Hat y NASA han organizado una
distribucin de Linux orientada al aprovechamiento de clusters llamada Extreme Linux que
contiene un conjunto de tales aplicaciones paralelizadas, como el generador de imgenes
POV (Persistence Of Vision).
Pero a menudo se est interesado en adaptar una aplicacin propia de clculo intensivo para
sacar provecho de un cluster, y para ello no hay ms remedio que recurrir a su
paralelizacin. Existen dos opciones para hacer que la aplicacin sea capaz de usar los
computadores de un cluster: programar explcitamente el paso de mensajes o utilizar
herramientas que lo hagan. El segundo caso abarca las herramientas de paralelizacin
automtica y los lenguajes de programacin paralelos.
7/30/2019 33611748 Sistemas de Memoria Distribuida
21/31
Desde luego, lo ms sencillo es proporcionar el cdigo fuente a un programa paralelizador y
dejar que este produzca cdigo paralelo. El problema es que estos paralelizadores suelen ser
muy caros y, lo que es peor, funcionan realmente mal. Aunque en la actualidad muchos
grupos de investigacin estn dedicando un gran esfuerzo al desarrollo y mejora de
herramientas de paralelizacin automtica, lo cierto es que por el momento no son muy tiles.En los aos 80 se disearon un gran nmero de lenguajes explcitamente paralelos, como
por ejemplo Ora3 o Parallaxis4, pero ltimamente los desarrolladores se han dado cuenta de
que los usuarios no van a usar su nuevo lenguaje, pese a lo bueno que sea, si no es
compatible con Fortran o C. Por ello, hoy en da los esfuerzos se dirigen al desarrollo de
extensiones paralelas para estos lenguajes. El ejemplo ms notable es HPF (High
Performance Fortran, Fortran de alto rendimiento). HPF es fundamentalmente Fortran 90
estndar al que se le han aadido una serie de directivas, que se introducen como
comentarios en el cdigo fuente para informar al compilador, por ejemplo, sobre cmodistribuir los datos entre los procesadores o qu bucles puede ejecutar en paralelo sin
preocuparse por las dependencias de las expresiones.
Sin embargo, habitualmente se obtiene un mayor rendimiento programando
explcitamente el paso de mensajes entre procesadores. Es posible optimizar hasta el
ltimo microsegundo utilizando la red a bajo nivel, usando sockets o el dispositivo de red
directamente, pero al precio de una programacin compleja, susceptible de errores y, lo
que es peor, no transportable. El mejor compromiso entre eficiencia, facilidad de uso y
portabilidad lo dan las bibliotecas de paso de mensajes, en las que el programador
construye explcitamente el mensaje entre dos procesadores, o las de funcin colectiva,
modelo intrnsecamente paralelo en el que un grupo de procesadores se comunica a la
vez. Entre las primeras destacan PVM (Parallel Virtual Machine, mquina paralela virtual)
y MPI (Message Passing Interface, interfaz para el paso de mensajes) y el ejemplo ms
significativo de las segundas es AFAPI (Aggregate Function APZ, API de funciones colectivas).
Todas estas bibliotecas, que se encuentran disponibles en Linux, se pueden utilizar en
cualquier arquitectura paralela a la que se hayan transportado, no solamente en clusters de
computadores.
4.3 PROGRAMACIN DE CLUSTERS
Desde hace varios aos se puede observar que ha habido un incremento sostenido en la
aceptacin y utilizacin del procesamiento paralelo. Este crecimiento se debe
7/30/2019 33611748 Sistemas de Memoria Distribuida
22/31
principalmente al diseo y utilizacin de los clusters, tal y como ya se ha detallado en las
secciones anteriores.
En cualquier aplicacin que implique procesamiento paralelo, los datos se tienen que
intercambiar entre las tareas que cooperan para resolver el problema planteado. Para
llevar a cabo esta tarea, como ya se indic en el Captulo 2, existen dos paradigmas de
programacin: la memoria compartida y el paso de mensajes.
Aunque este Captulo y el siguiente se centran en el modelo de paso de mensajes como
mecanismo de intercambio de informacin entre los distintos computadores que forman el
cluster, conviene tener presente las siguientes consideraciones sobre ambos paradigmas:
O El modelo de memoria compartida es similar al de un tabln de anuncios con acceso
restringido, donde el que tiene permiso pone una noticia con lo que le interesa, y el que
tiene permiso lee el tabln. A pesar de que este mecanismo parece sencillo, y de hecho es el
ms intuitivo que se puede emplear para compartir informacin, presenta un problema:
el control de acceso a la infomnacin. Dicho de otro modo, hay que tener la seguridad de
que la informacin que un procesador lee es semnticamente vlida, y no son datos
invlidos, debido a que uno de los procesadores que est escribiendo est operando
exactamente con los mismos datos con los que otro procesador est realizando una
operacin de lectura. Este problema tiene unos mecanismos de resolucin elaborados
(semforos, monitores, etc.). Por estas razones hoy en da la memoria compartida slo se
emplea si el grado de acoplamiento5 es tan alto que un mecanismo de paso de mensajes
puede llegar a ser muy poco eficaz.
O El modelo de paso de mensajes es un mecanismo menos intuitivo pero ms cmodo para
transmitir informacin. Un proceso enva a otro proceso un mensaje que contiene la
informacin que debe conocer. Por ello, no existe el problema que se seal
anteriormente del control de acceso a la informacin, ya que si a un proceso le llega un
mensaje, este mensaje ya es correcto salvo errores de transmisin. Por lo tanto, la
programacin y verificacin de un programa paralelo con comunicacin por paso de
mensajes es ms sencilla que empleando memoria compartida. Sin embargo, si el grado de
acoplamiento es alto, el trasiego de mensajes es desmesurado y este sistema queda tot
almente descartado. En la actualidad el modelo de paso de mensajes es el ms aceptado,
desde el punto de vista del nmero y variedad de procesadores que lo soportan, as
como por los lenguajes y sistemas software que lo utilizan.
7/30/2019 33611748 Sistemas de Memoria Distribuida
23/31
En esta Seccin se presentan las diversas opciones de programacin mediante paso de
mensajes. Para ello se introducen los conceptos fundamentales y las primitivas de
programacin bsicas. Estas primitivas permiten programar un modelo abstracto mediante un
pseudocdigo que establece de forma clara la funcionalidad de estas operaciones
fundamentales. En el Captulo 5 se presenta un software concreto de programacinmediante paso de mensajes, PVM, con sus funciones y operaciones auxiliares detalladas.
En este contexto la programacin mediante primitivas debe entenderse desde el punto
de vista conceptual y abstracto, y la programacin mediante PVM desde el punto de vista
concreto y prctico.
4.3.1 Opciones de programacin mediante paso de mensajes
La programacin por paso de mensajes en un cluster se puede realizar de tres formas
diferentes:
1) Mediante el diseo de un lenguaje especfico de programacin paralela.
2) Mediante la extensin de la sintaxis de un lenguaje secuencial de alto nivel que ya
exista para que se incluya el manejo del paso de mensajes utilizando palabras
reservadas .
3) Mediante la utilizacin de un lenguaje secuencial de alto nivel que proporcione una
biblioteca de procedimientos externos para el paso de mensajes.
En la literatura sobre computacin paralela es fcil encontrar numerosos ejemplos de los
tres enfoques anteriores. Quizs, el nico ejemplo pblico de un lenguaje especfico de
programacin paralela sea Occam, diseado para ser utilizado con un procesador de
paso de mensajes denominado Transputer. ' Los ejemplos de lenguajes con extensiones
son CC+ y Fortran M, extensiones al C++ y al Fortran respectivamente. Estos lenguajes se
pueden utilizar para programacin paralela en general.
Tambin es posible utilizar compiladores paralelizantes especiales que simplemente
convierten un programa escrito en un lenguaje de programacin secuencial, como puede
ser Fortran, a un cdigo paralelo equivalente ejecutable. Esta opcin se propuso hace aos,
pero no es muy prctica para la programacin por paso de mensajes debido a que los
lenguajes de programacin secuenciales tradicionales no tienen incorporado el concepto de
paso de mensajes.
7/30/2019 33611748 Sistemas de Memoria Distribuida
24/31
En los prximos apartados se analiza detalladamente la tercera opcin de las mencionadas
anteriormente, tomando como lenguaje de alto nivel C e incluyendo las llamadas a la
biblioteca de paso de mensajes que son las que realizan dicha tarea de forma directa entre los
procesos. En este mtodo es necesario declarar de forma explcita la siguiente informacin:
a) Qu procesos van a ser ejecutados.
b) Cundo se envan y se reciben los mensajes entre procesos concurrentes.
c) Qu informacin se transmite en los mensajes.
A continuacin, se estudian las dos operaciones bsicas que se necesitan en un sistema de
paso de mensajes:
1) La creacin de procesos independientes en diferentes procesadores.
2) El envo y la recepcin de mensajes
4.3.2 Creacin de procesos
En algunos casos, especialmente cuando se est depurando un programa sobre un nmero de
procesadores elevado, es posible ejecutar ms de un proceso en un mismo procesador.
Normalmente, este hecho no producir la mxima velocidad de ejecucin debido a que
el procesador debe compartir el tiempo entre los procesos que se le hayan asignado, sin
embargo, permitir verificar el programa de forma sencilla.
4.4 PARADIGMAS DE PROGRAMACIN PARALELA CON PASO DE MENSAJES
Las aplicaciones paralelas se pueden clasificar en algunos paradigmas de programacin
claramente establecidos. Basta con unos pocos paradigmas para, utilizndolos
repetidamente, poder desarrollar la mayora de los programas paralelos. En este
contexto, por paradigma se entiende una clase de algoritmos que tienen la misma estructura
de control. La eleccin del paradigma a utilizar depende de la disponibilidad de los
recursos computacionales paralelos que se tengan y del tipo de paralelismo inherente al
problema. Los recursos computacionales definen el grado de acoplamiento o nivel de
granularidad que puede soportar el sistema de forma eficiente. El tipo de paralelismo refleja
la estructura de la aplicacin y/o de los datos. El paralelismo debido a la estructura de la
aplicacin se denomina paralelismo funcional. En este caso, las diferentes partes de un
programa pueden realizar distintas tareas de una manera concurrente y cooperativa. Pero
el paralelismo se puede encontrar tambin en la estructura de los datos; esta clase de
7/30/2019 33611748 Sistemas de Memoria Distribuida
25/31
paralelismo permitir la ejecucin de procesos paralelos con idntico modo de operacin
pero sobre distintas partes de los datos. A este segundo tipo de paralelismo se le
denomina paralelismo estructural o a nivel de datos.
En el rea de la computacin paralela diferentes autores presentan distintas clasificaciones de
paradigmas. No todos proponen exactamente la misma, pero realizando la unin de todas
ellas se puede crear un amplio conjunto de los paradigmas que se utilizan en las aplicaciones
paralelas.
Por ejemplo, Pritchard presenta una clasificacin terica de programas paralelos y seala
tres tipos de paralelismo:
1) Descomposicin en grupos de tareas, el cual est basado en la rplica de trabajos
independientes.
2) Descomposicin georntrica, basada en la paralelizacin de las estructuras de datos.
3) Paralelismo algortmico, el cual se centra en paralelizar el flujo de datos de entrada.
Otra clasificacin fue la realizada por Hansen, quien estudi varias aplicaciones paralelas e
identific el siguiente conjunto de paradigmas:
- Segmentacin y aplicaciones basadas en anillo.
- Divide y vencers.
- Maestro/Esclavo.
- Aplicaciones de autmatas celulares basadas en el paralelismo de los datos.
Wilson tambin propone otra clasificacin donde divide los problemas segn la tcnica de
descomposicin que utilicen:
- Descomposicin geomtrica: el dominio del problema se divide en pequeos subdominios y
cada procesador ejecuta el algoritmo en la parte del subdominio que le corresponde.
- Descomposicin iterativa: algunas aplicaciones estn basadas en la ejecucin de un lazo
donde cada iteracin se puede realizar de forma independiente. Esta tcnica se
implementa a travs de una cola central de tareas ejecutables, y se corresponde con el
paradigma de descomposicin en grupos de tareas.
7/30/2019 33611748 Sistemas de Memoria Distribuida
26/31
- Descomposicin recursiva: esta estrategia comienza dividiendo el problema original en
varios subproblemas y los resuelve de forma paralela. Se corresponde con el paradigma divide
y vencers propuesto en la clasificacin anterior.
- Descomposicin especulativa: se intentan N tcnicas de solucin simultneamente, y (N
- 1) de ellas se eliminan tan pronto como una de ellas devuelve una respuesta correcta.
- Descomposicin jncional: la aplicacin se divide en distintas fases, y cada fase ejecuta una
parte diferente del algoritmo para resolver el problema.
Otra clasificacin ms reciente es la que realiza Buyya:
- MaestroBscZavo: el proceso maestro es el responsable de descomponer el problema entre
sus procesos esclavos y de, posteriormente, recoger los resultados que le envan los
esclavos para ordenarlos y obtener el resultado final.
- SPMD (Single Program Multiple Data): en este paradigma cada procesador ejecuta el
mismo cdigo pero sobre distintas partes de los datos.
- Segmentacin de datos: est basado en el paralelismo funcional donde las diferentes
partes de un programa pueden realizar distintas tareas de una manera concurrente y
cooperativa.
- Divide y vencers: el problema se divide en subproblemas que se resuelven de forma
independiente para, posteriormente, combinar sus resultados parciales y obtener el
resultado final.
- Paralelismo especulativo: consiste en utilizar diferentes algoritmos para resolver el
mismo problema. El primero que da la solucin final es el elegido.
La clasificacin ms genrica y que incluye la gran mayora de los paradigmas a los que se
ha hecho referencia con anterioridad es la que se presenta en Burkhart donde los
criterios
7/30/2019 33611748 Sistemas de Memoria Distribuida
27/31
utilizados son: propiedades del proceso (estructura, topologa y ejecucin), propiedades
de
interaccin y propiedades de los datos (divisin y localizacin).
A continuacin, siguiendo la clasificacin que propone Buyya, se comentan con mayor
detalle nicamente los dos paradigmas ms extendidos:
- Maestro/Esclavo .
- SPMD (Single Program, Multiple Data).
4.4.1 Paradigma Maestro/Esclavo
El paradigma Maestro/Esclavo es el ms utilizado en las aplicaciones paralelas y en la
mayora de los casos, como el propio nombre indica, consta de dos tipos de entidades: un
maestro y varios esclavos. El maestro es el responsable de la descomposicin del
problema en pequeas tareas, de distribuir estas tareas entre el conjunto de
procesadores esclavos y de recoger los resultados parciales obtenidos de cada procesador
esclavo para ordenarlos y obtener el resultado final del problema. Los procesadores
esclavos reciben un mensaje con la tarea a realizar, realizan la tarea y envan el resultado
al maestro. Normalmente, la comunicacin tiene lugar nicamente entre el maestro y los
esclavos. El paradigma Maestro/Esclavo puede utilizar un balance de carga esttico o un
balance de carga dinmico. En el primer caso, la distribucin de las tareas se realiza al
comienzo de la computacin, lo cual permite al maestro participar en la computacin una
vez que haya asignado una fraccin del trabajo a cada esclavo. La asignacin de tareas se
puede realizar de una sola vez o de manera cclica. La Figura 4.38 muestra una
representacin esquemtica de una estructura Maestro/Esclavo esttica.
7/30/2019 33611748 Sistemas de Memoria Distribuida
28/31
4.4.2 Paradigma SPMD (Single Program Mu/tip/e Data)
En el paradigma SPMD cada procesador ejecuta bsicamente el mismo cdigo pero sobre
distintas partes de los datos. Esto supone dividir los datos de la aplicacin entre los
procesadores disponibles. A diferencia del paradigma Maestro/Esclavo, en este modelo la
comunicacin se establece entre esclavos. A este tipo de paralelismo tambin se le
denomina paralelismo geomtrico, estructural o paralelismo a nivel de datos. La Figura
4.39 muestra un esquema de esta clase de paradigma.
Muchos problemas fsicos tienen una estructura geomtrica regular, homogeneidad que
permite distribuir los datos uniformemente entre los procesadores. Los procesadores se
comunican entre s, donde la carga de comunicacin ser proporcional al tamao de la
informacin enviada y la carga computacional ser proporcional al volumen de los
elementos. Este paradigma se puede utilizar para realizar alguna sincronizacin global
peridica entre todos los procesadores.
Normalmente, los esquemas de comunicacin son muy estructurados y extremadamente
predecibles. Los datos iniciales pueden ser generados por cada procesador o pueden ser
ledos de memoria secundaria o distribuidos por uno de los procesadores. En este ltimo
caso se puede presuponer la existencia de un procesador maestro en la fase inicial.
Las aplicaciones SPMD pueden ser muy eficientes si los datos estn bien distribuidos entre los
procesadores y el sistema es homogneo. Si los procesadores presentan distintas cargas
de trabajo o capacidades, el paradigma necesitar algn mecanismo de planificacin de
balance de carga centralizado, completamente distribuido o parcialmente distribuido para
distribuir los datos durante el tiempo de ejecucin.
7/30/2019 33611748 Sistemas de Memoria Distribuida
29/31
4.5 Evaluacin del rendimiento de un cluster.
El xito de los clusters de PCs se debe en general ms a los avances en el rendimiento de las
redes de comunicacin que a la mejora de los procesadores. Y es que, para la
granularidad tpica de las aplicaciones paralelas, sobra velocidad de CPU y falta velocidad de
red, de tal forma que el paso de mensajes acaba siendo su cuello de botella.
Aunque existen numerosos trabajos sobre evaluaciones de mquinas paralelas donde lacomunicacin se realiza a travs de paso de mensajes, una gran mayora se centra en el
estudio de sistemas MPPs, pero tambin se puede encontrar algunos sobre evaluaciones de
rendimiento de clusters. A continuacin se presentan los parmetros ms relevantes en
la evaluacin del rendimiento de un cluster donde la programacin paralela se realiza
mediante el modelo de pasode mensajes. Para el buen seguimiento y comprensin de esta
Seccin, y para que el estudio de los distintos parmetros sea exhaustivo, es conveniente
hacer una breve descripcin del protocolo de comunicacin empleado. Como base para este
estudio y para poner de manifiesto la medida de los distintos parmetros tericos se ha
tomado el cluster Smaug, diseado y construido en el Departamento de Informtica y
Automtica de la UNED.
4.5.1 Anlisis del protocolo de comunicacin
Como medio de comunicacin entre los computadores que integran Smaug se ha utilizado
tecnologa Fast Ethernet, de 100 Mbit/s, utilizando como protocolos de comunicacin la
familia TCP/IP (Transmission Control Protocol/Internet Protocol).
Las arquitecturas basadas en TCP/IP dividen las funciones propias de la red, desde el
punto de vista del encapsulamiento y desencapsulamiento de datos, en cuatro capas
claramente diferenciadas, tal y como se muestra en la Figura 4.40.
Conceptualmente, enviar un mensaje desde un programa de aplicacin en una mquina
hacia un programa de aplicacin en otra significa transferir el mensaje hacia abajo
(encapsular), recurriendo a los servicios que brindan los diferentes niveles del modelo
7/30/2019 33611748 Sistemas de Memoria Distribuida
30/31
7/30/2019 33611748 Sistemas de Memoria Distribuida
31/31
muestra un ejemplo, utilizando funciones primitivas, para medir el tiempo de ejecucin entre
el punto L, y el punto L, del cdigo.