Los sistemas de
Memoria Compartida Distribuida (MCD), son sistemas que, mediante software,
emulan semántica de memoria compartida sobre hardware que ofrece soporte solo
para comunicación mediante paso de mensajes. Este modelo permite utilizar una
red de estaciones de trabajo de bajo costo como una maquina paralela con
grandes capacidades de procesamiento y amplia escalabilidad, siendo a la vez
fácil de programar.
El objetivo
principal de estos sistemas es permitir que un multicomputador pueda ejecutar
programas escritos para un multiprocesador con memoria compartida
Cada uno de los
nodos en un sistema de MCD aporta una parte de su memoria local para construir
un espacio global de direcciones virtuales que será empleado por los procesos
paralelos que se ejecuten en el sistema. El software de MCD se encarga de
interceptar las referencias a memoria que hacen los procesos, y satisfacerlas,
ya sea local o remotamente.
4.1 CONFIGURACIONES DE MEMORIA COMPARTIDA DISTRIBUIDA
COMPUTACIÓN PARALELA
Un computador
paralelo es un conjunto de procesadores capaces de cooperar en la solución de
un problema.
El problema se
divide en partes. Cada parte se compone de un conjunto de instrucciones. Las
instrucciones de cada parte se ejecutan simultáneamente en diferentes CPUs.
Técnicas computacionales que descomponen un problema en sus tareas y pistas que
pueden ser computadas en diferentes máquinas o elementos de proceso al mismo
tiempo.
Por qué utilizar
computación paralela?
Reducir el tiempo
de procesamiento
Resolver problemas
de gran embergadura.
Proveer
concurrencia.
Utilizar recursos
remotos de cómputo cuando los locales son escasos.
Reducción de
costos usando múltiples recursos”baratos” en lugar de costosas
supercomputadoras.
Ampliar los
límites de memoria para resolver problemas grandes.
El mayor problema
de la computación paralela radica en la complejidad de sincronizar unas tareas
con otras, ya sea mediante secciones críticas, semáforos o paso de mensajes,
para garantizar la exclusión mutua en las zonas del código en las que sea
necesario.
La computación
paralela está penetrando en todos los niveles de la computación, desde
computadoras masivamente paralelas usados en las ciencias de larga escala
computacional, hasta servidores múltiples procesadores que soportan
procesamiento de transacciones. Los principales problemas originados en cada
uno de las áreas básicas de la informática (por ejemplo, algoritmos, sistemas,
lenguajes, arquitecturas, etc.) se vuelven aún más complejos dentro del
contexto de computación paralela.
DE CIRCUITOS, BASADOS EN BUS, ANILLO O CON
CONMUTADOR
Existen varias
formas de implantar físicamente memoria compartida distribuida, a continuación
se describen cada una de ellas.
Memoria basada en
circuitos: Existe una
única área de memoria y cada micro tiene su propio bus de datos y direcciones
(en caso de no tenerlo se vuelve un esquema centralizado)
MCD basada en bus: En este esquema los micros comparten un bus
de datos y direcciones por lo que es más barato de implementar, se necesita
tener una memoria caché grande y sumamente rápida.
Multiprocesadores tipo bus
Conexión entre CPU
y memoria se hace a través de cables paralelos:
o algunos transmiten
las direcciones y datos que el CPU quiere leer o escribir
o otros envían o
reciben datos
o el resto para
controlar las transferencias.
Dicha colección de
cables se conoce con el nombre de bus.
Buses pueden ser
parte del chip, pero en la mayoría de los sistemas los buses son externos y son
usados para conectar circuitos impresos.
Una forma simple
de construir multiprocesadores es conectarlos en un bus con más de un CPU
MCD basada en
anillos: Es más
tolerante a fallos, no hay coordinador central y se privilegia el uso de la
memoria más cercana.
Multiprocesadores basados en anillo.
Ejemplo Memnet: un
espacio de direcciones se divide en una parte privada y otra compartida.
La parte privada:
o se divide en
regiones cada máquina cuenta con memoria para su pila, datos y códigos no
compartidos.
Parte compartida:
o común a todas las
máquinas y se guarda de forma consistente mediante un protocolo de hardware
parecido a los de bus se divide en bloques de 32 bytes, (unidad transferencia)
MCD basada en
conmutador: Varios
micros se conectan entre sí en forma de bus formando un grupo, los grupos están
interconectados entre sí a través de un conmutador. Cuando se realiza una
operación de memoria se intenta realizar dentro del grupo, de lo contrario pasa
al conmutador para que lo redirecciones a otro grupo.
Multiprocesadores con conmutador.
En anillo o bus,
el hecho de añadir un CPU satura el ancho de banda del bus o anillo
Dos métodos para
solucionar el problema:
o 1. Reducir la
cantidad de comunicación
o 2. Incrementar la
capacidad de comunicación
Una forma de
reducir la cantidad de comunicación es el ocultamiento trabajo adicional en
esta área:
o mejorar protocolo
de ocultamiento
o optimizar el
tamaño del bloque
o incrementar la
localidad de las referencias a memoria.
Sin embargo
siempre se querrá añadir más CPUs y no habrá más ancho de banda en el bus.
4.2 MODELOS DE
CONSISTENCIA
Un modelo de consistencia de memoria especifica las
garantías de consistencia que un sistema MCD realiza sobre los valores que los
procesos leen desde los objetos, dado que en realidad acceden sobre una réplica
de cada objeto y que múltiples procesos pueden actualizar los objetos.
La duplicidad de los bloques compartidos aumenta el
rendimiento, pero produce un problema de consistencia entre las diferentes
copias de la página en caso de una escritura.
Si cada escritura es necesario actualizar todas las
copias el envió de las paginas por red provoca que el tiempo de espera aumente
demasiado convirtiendo el método en impracticable.
CARACTERISTICAS DE CONSISTENCIA
• Mantener consistencia no es algo simple.
• Un simple acceso a memoria puede requerir un gran
número de paquetes a ser enviados.
MODELOS DE
CONSISTENCIAS, DEL MAS FUERTE AL MAS DEBIL.
ESTRICTA, CASUAL, SECUENCIAL, DEBIL, DE
LIBERACION Y DE ENTRADA
CONSISTENCIA ESTRICTA: El modelo de consistencia más restrictivo es
llamado consistencia estricta y es definido por la siguiente condición
cualquier lectura sobre un ítem de dato X retorna un valor correspondiente con
la más reciente escritura sobre X.
CONSISTENCIA CASUAL: Es un debilitamiento de la consistencia
secuencial. Se hace una diferenciación entre eventos que están potencialmente
relacionados en forma casual y aquellos que no.
La condición a cumplir para que unos datos sean
casualmente consistentes es:
Escrituras que están potencialmente relacionados en
forma casual deben ser vistas por todos los procesos en el mismo orden.
Esta secuencia es permitida con un almacenamiento
casualmente consistente o con un almacenamiento consistente en forma estricta.
El modelo de consistencia causal (Hutto and Ahamad,
1990) es un debilitamiento de la consistencia secuencial. Se hace una
diferenciación entre eventos que están potencialmente relacionados en forma
causal y aquellos que no. Las operaciones que no están causalmente relacionadas
se dicen concurrentes.
La condición a cumplir para que unos datos sean
causalmente consistentes es:
Escrituras que están potencialmente relacionadas en
forma causal deben ser vistas por todos los procesos en el mismo orden.
Escrituras concurrentes pueden ser vistas en un orden diferente sobre
diferentes máquinas.
Esta secuencia es permitida con un almacenamiento
causalmente consistente, pero no con un almacenamiento secuencialmente
consistente o con un almacenamiento consistente en forma estricta.
CONSISTENCIA SECUENCIAL: La consistencia secuencial es una forma ligeramente
más débil de la consistencia estricta. Satisface la siguiente condición:
El resultado de una ejecución es el mismo si las
operaciones (lectura y escritura) de todos los procesos sobre el dato fueron ejecutadas
en algún orden secuencial y las operaciones de cada proceso individual aparecen
en esta operaciones de cada proceso individual aparecen en esta secuencia en el
orden especificado por su programa
a) Un dato almacenado secuencialmente consistente.
b) Un dato almacenado que no es secuencialmente
consistente.
CONSISTENCIA DÉBIL: Los accesos a
variables de sincronización asociadas con los datos almacenados son
secuencialmente consistentes.
Propiedades
No se permite operación sobre una variable de sincronización
hasta que todas las escrituras previas de hayan completado. No se permiten
operaciones de escritura o lectura sobre ítems de datos hasta que no se hayan
completado operaciones previas sobre variables de sincronización.
CONSISTENCIA LIBERACIÓN (RELEASE): El modelo de
consistencia release, RC, se basa en el supuesto de que los accesos a variables
compartidas se protegen en secciones críticas empleando primitivas de
sincronización, como por ejemplo locks. En tal caso, todo acceso esta precedido
por una operación adquiere y seguido por una operación release. Es
responsabilidad del programador que esta propiedad se cumpla en todos los
programas.
Puesto que ningún otro proceso, ni local ni remoto,
puede acceder a las variables que han sido modificadas mientras se encuentren
protegidas en la sección critica, la actualización de cualquier modificación
puede postergarse hasta el momento en que se lleva a cabo la operación reléase.
La operación release no se da por completada hasta
que la actualización haya sido propagada a todos aquellos procesadores en donde
haya replicas. Con RC, la propagación de un conjunto de modificaciones a
memoria compartida se lleva a cabo con un costo fijo.
Propagación de Actualizaciones bajo RC y LRC de
código sin proteger. En consecuencia obtuvo un valor inconsistente para la
variable leída.
4.3 MCD EN BASE A PÁGINAS.
Cada CPU cuenta
con su propia memoria y no pueden referenciar memoria remota directamente.
Cuando dirección CPU se encuentra en una página que
reside en una máquina remota:
Se notifica al
sistema operativo
Sistema solicita
dicha página con un mensaje.
Tanto ubicación como acceso son realizados a nivel
software.
Ejemplos: IVY y Mirage
El esquema de MCD propone un espacio de direcciones
de memoria virtual que integre la memoria de todas las computadoras del
sistema, y su uso mediante paginación. Las páginas quedan restringidas a estar
necesariamente en un único ordenador. Cuando un programa intenta acceder a una
posición virtual de memoria, se comprueba si esa página se encuentra de forma
local. Si no se encuentra, se provoca un fallo de página, y el sistema
operativo solicita la página al resto de computadoras.
El sistema funciona de forma análoga al sistema de
memoria virtual tradicional, pero en este caso los fallos de página se propagan
al resto de ordenadores, hasta que la petición llega al ordenador que tiene la
página virtual solicitada en su memoria local. A primera vista este sistema
parece más eficiente que el acceso a la memoria virtual en disco, pero en la
realidad ha mostrado ser un sistema demasiado lento en ciertas aplicaciones, ya
que provoca un tráfico de páginas excesivo.
Una mejora dirigida a mejorar el rendimiento
sugiere dividir el espacio de direcciones en una zona local y privada y una
zona de memoria compartida, que se usará únicamente por procesos que necesiten
compartir datos. Esta abstracción se acerca a la idea de programación mediante
la declaración explícita de datos públicos y privados, y minimiza el envío de información,
ya que sólo se enviarán los datos que realmente vayan a compartirse.
Hay dos razones principales para la replicación de datos:
Confiabilidad
Continuidad de trabajo ante caída de la réplica, mayor cantidad de
copias mejor protección contra la corrupción de datos.
Rendimiento
El SD escala en número
Escala en área geográfica (disminuye el tiempo de acceso al dato)
Consulta simultánea de los mismos datos.
GRANULARIDAD.
Se refiere a la especificidad a
la que se define un nivel de detalle en una tabla, es decir, si hablamos de una
jerarquía la granularidad empieza por la parte más alta de la jerarquía, siendo
la granularidad mínima, el nivel más bajo.
MODELOS DE CONSISTENCIA.
Es esencialmente un contrato entre procesos y el almacenamiento de
datos.
Es decir: si los procesos acuerdan obedecer ciertas reglas, el
almacenamiento promete trabajar correctamente.
Normalmente un proceso que realiza una operación de lectura espera que
esa operación devuelva un valor que refleje el resultado de la última operación
de escritura sobre el dato.
Los modelos de consistencia se presentan divididos en dos conjuntos:
Modelos de consistencia centrados en los datos.
Modelos de consistencia centrados en el cliente.
4.4 MCD EN BASE A
VARIABLES.
Munin:
Consistencia de
liberación.
Protocolos múltiples.
Directorios.
Sincronización.
Midway:
Consistencia de entrada.
Implantación.
La compartición falsa se produce cuando dos
procesos se pelean el acceso a la misma página de memoria, ya que contiene
variables que requieren los dos, pero estas no son las mismas. Esto pasa por un
mal diseño del tamaño de las páginas y por la poca relación existente entre
variables de la misma página.
En los MCD basados en variables se busca evitar la
compartición falsa ejecutando un programa en cada CPU que se comunica con una
central, la que le provee de variables compartidas, administrando este
cualquier tipo de variable, poniendo variables grandes en varias páginas o en
la misma página muchas variables del mismo tipo, en este protocolo es muy importante
declarar las variables compartidas.
En los MCD basados en objetos se busca el acceso a
datos por medio de la encapsulación de la información. Y repartida a través de
la red, estos objetos serán definidos por el Programador y las CPU´s cambiaran
los estados según procedan con los accesos.
MCD BASADA EN
VARIABLES COMPARTIDAS
El problema del false sharing puede eliminarse si
se utiliza una granularidad más tan fin tan fina, como las entidades que
usualmente se comparten en los programas paralelos:
Las variables. De
ser así, el problema ahora consiste en cómo mantener registro de las variables
replicadas. Además, es probable que sea más conveniente utilizar una
política de actualización y no de invalidación, puesto que en la implementación
debe ser posible identificar escrituras a variables individuales.
Nace como respuesta a la creciente popularización
de los lenguajes orientados por objetos.
Los datos se organizan y son transportados en
unidades de objetos, no unidades de páginas.
Es un modelo de programación de DSM de alto nivel.
Una alternativa al uso de páginas es tomar el
objeto como base de la transferencia de memoria. Aunque el control de la
memoria resulta más complejo, el resultado es al mismo tiempo modular y
flexible, y la sincronización y el acceso se pueden integrar limpiamente. Otra
de las restricciones de este modelo es que todos los accesos a los objetos
compartidos han de realizarse mediante llamadas a los métodos de los objetos,
con lo que no se admiten programas no modulares y se consideran incompatibles.
Un ejemplo de un
sistema de MCD que utiliza una granularidad a nivel de variable compartida es
Munin, una de las primeras implementaciones de MCD. Munin permite la ubicación
de variables individuales en páginas diferentes, de modo que se pueda utilizar
el hardware de paginación para identificar los accesos a las variables
compartidas.