Memoria Compartida Distribuida



Descargar 60,61 Kb.
Fecha de conversión05.08.2017
Tamaño60,61 Kb.
Memoria Compartida Distribuida
Los multiprocesadores son difíciles de construir y fáciles de programar.

Las multicomputadoras son difíciles de programar y fáciles de construir.

El objetivo de la memoria compartida distribuida es que el hardware en el que se base sea fácil de construir y fácil de programar.
Introducción

En 1986 Li y mas tarde Hudak, propusieron un mecanismo para el manejo de memoria en sistemas distribuidos llamado memoria compartida distribuida (DSM). Su propuesta fue tener una colección de estaciones de trabajo conectadas por una LAN compartiendo un solo espacio de direcciones virtuales con páginas.

La desventaja de este esquema es que exhibe un desempeño pobre, ya que las páginas andan de un lado para otro de la red.

La ventaja es que es un modelo fácil de programar y de construir.

Otro método consiste en no compartir todo el espacio de direcciones, sino solo una porción seleccionada, de hecho, solo aquellas variables o estructuras de datos que se necesitan utilizar en más de un proceso, lo cual produce un alto nivel de abstracción, pues ya no se piensa en una porción de memoria, sino en una colección de variables.

Una posible optimización consiste en repetir las variables compartidas en varias máquinas, el problema en este caso es mantener consistentes las copias.

Las lecturas se pueden hacer de manera local, sin ningún tráfico y las escrituras mediante un protocolo de actualización con varias copias.

Otr posible optimización es compartir objetos.


. Multiprocesadores basados en un bus.

CPU

CPU

CPU

Memoria

bus

Para evitar que dos o más CPU’s intenten el acceso a la memoria al mismo tiempo, se necesita algún tipo de arbitraje del bus. El CPU debe pedir permiso para conseguir el bus. La concesión puede hacerse de forma centralizada, utilizando un dispositivo de arbitraje de bus, o de forma descentralizada, donde el primer CPU que realice una solicitud en el bus ganará cualquier conflicto.

La desventaja es la sobrecarga del bus.

Una solución sería equipar a cada CPU con un caché husmeador.


CPU

Cache

CPU

Cache


CPU

Cache


Memoria

bus

Un protocolo en particular común es el de escritura a través del caché. Cuando un CPU lee por primera vez una palabra de memoria, esa palabra es llevada por el bus y guardada en el caché del CPU solicitante.

Puede suceder que una palabra en particular se oculte en dos o más CPU al mismo tiempo.



Operación de lectura.

  • Si la palabra no esta en el caché, entonces buscarla en la memoria y copiarla a su caché.

  • Si la palabra esta en el caché, tomar el dato de ahí.


Operación de escritura

  • Si ningún CPU tiene la palabra en su caché, entonces la palabra es actualizada en memoria, como si el ocultamiento no hubiera sido utilizado.

  • Si el CPU (que realiza la escritura) tiene la única copia de la palabra, se actualiza su caché y también la memoria mediante el bus.

  • Si dos o más CPU tienen la palabra, entonces se actualiza la palabra en el caché y en la memoria, y se invalidan las entradas de esa palabra en los cahés de los otros CPU. Así la palabra sólo la tendrá la memoria y un colo caché.

Una alternativa a invalidar otras entradas de caché es actualizarlas todas, pero esto puede resultar más lento.

Una ventaja de este protocolo es que es fácil de entender e implantar, la desventaja es que todas las escrituras utilizan el bus.

Existe otro tipo de protocolos como el protocolo de membresía. Una versión de este protocolo plantea lo siguiente. Se manejan bloques de caché, cada uno de los cuales puede estar en uno de los siguientes estados:


  1. INVALIDO: Este bloque de caché no contiene datos válidos.

  2. LIMPIO: La memoria está actualizada, el bloque puede estar en otros cachés.

  3. SUCIO: La memoria es incorrecta; ningún otro caché puede contener al bloque.


La memoria es correcta

A


B

C

W1

Estado inicial. La palabra W que contiene el valor w1 esta en la memoria y también está en el caché de B

W1


bus

limpio


A


B

C

W1

bus

W1

W1

limpio


La memoria es correcta

limpio

A lee la palabra W y obtiene W1. B no responde a la lectura, pero la memoria si.

A

B

C

W1

bus

W2

W1

La memoria ya no es correcta



A escribe un valor W2. B husmea en el bus, ve la escritura e invalida su entrada. La copia de A se marca como sucio.

sucio

invalido



A

B

C

W1

bus

W3

W1

La memoria ya no es correcta



A escribe W de nuevo. Esta y las escrituras posteriores por A se realizan de manera local, sin tráfico en el bus.

sucio

invalido



A

B

C

W1

bus

W3

W1

invalido

La memoria ya no es correcta


C lee o escribe W. A ve la solicitud al husmear en el bus, proporciona el valor e invalida su propia entrada. C tiene ahora la única copia válida.


W3


sucio


invalido

La palabra permanece el estado SUCIO hasta que se elimine del caché donde se encuentra en la actualidad por razones de espacio. En este momento, desaparece de todos los cachés y se escribe en la memoria. Este protocolo tiene tres propiedades importantes:



  1. La consistencia se logra haciendo que todos los cachés husmeen el bus.

  2. El protocolo se integra dentro de la unidad de administración de memoria.

  3. Todo el algoritmo se realiza en un ciclo de memoria.

La desventaja es que no funciona para multiprocesadores de mayor tamaño y nada es válido para la memoria compartida distribuida.
Multiprocesadores basados en un anillo

Ejemplo: Memnet

En Memnet, un espacio de direcciones se divide en una parte privada y una compartida.

La parte compartida se divide en bloques de 32 bytes, unidad mediante la cual se realizan las transferencias entre las máquinas.

Las máquinas Memnet están conectadas mediante un anillo de fichas modificado. El anillo consta de 20 cables paralelos, que juntos permiten enviar 16 bits de datos y 4 bits de control cada 100 nanosegundos, para una velocidad de datos de 160 Mb/seg.

CPU

Memoria Privada



Dispositivo Memnet

Interrupción

MMU


Cache

Mem. de origen

Exclusivo

Valido

Origen

Posición

Un bloque exclusivo de lectura puede estar presente en varias máquinas, uno de lectura-escritura debe estar presente en una sola máquina.

Los bits en el dispositivo Memnet indican uno o más de los siguientes estados:

VALIDO: El bloque esta presente en el caché y está actualizado.

EXCLUSIVO: La copia local es la única.

ORIGEN: Se activa si ésta es la máquina origen del bloque.

INTERRUPCION: Se utiliza para forzar interrupciones.

POSICION: Indica la localización del bloque en el caché si esta presente y es válido.


Protocolo Memnet.

Lectura.

Cuando un CPU desea leer una palabra d ela memoria compartida, la dirección de memoria por leer se transfiere al dispositivo Memnet, el cual verifica la tabla del bloque para ver si está presente. Si es así, la solicitud es satisfecha de inmediato. En caso contrario, el dispositivo Memnet espera hasta capturar la ficha que circula; después, cooca un paquete de solicitud en el anillo y suspende el CPU. El paquete de solicitud contiene la dirección deseada y un campo vacío de 32 bytes.

Cada dispositivo Memnet en el anillo verifica si tiene el bloque. De ser así, coloca el bloque en el campo vacío y modifica el encabezado del paquete para inhibir la acción de las máquinas posteriores.

Si el bit exclusivo del bloque está activo, se limpia. Cuando el paquete regresa al emisor, se garantiza que contiene al bloque solicitado. El CPU que envía la solicitud guarda el bloque, satisface la solicitud y libera al CPU.

Si la máquina solicitante no tiene espacio libre en su caché para contener el bloque recibido, entonces toma al azar un bloque oculto y lo envía a su origen, con lo que libera un espacio de caché. Los bloques cuyo bit origen están activados nunca se eligen, pues se encuentran en su origen.

Escritura.

Tenemos tres casos:



    1. Si el bloque contiene la palabra por escribir está presente y es la única copia en el sistema, (el bit exclusivo esta activado) la palabra solo se escribe de manera local.

    2. Si esta presente el bloque, pero no es la única copia, se envía primero un paquete de invalidación por el anillo para que las otras máquinas desechen sus copias del bloque por escribir. Cuando el paquete de invalidación regresa al solicitante, el bit exclusivo se activa para ese bloque y se procede a la escritura local.

    3. Si el bloque no está presente, se envía un paquete que combina una solicitud de lectura y una de invalidación. La primera máquina que tenga el bloque lo copia en el paquete y desecha su copia. Todas las máquinas posteriores solo desechan el bloque de sus cachés. Cuando el paquete regresa al emisor, éste lo guarda y escribe en él.

La ventaja de este protocolo es que se puede aplicar a multicomputadoras.
Principales Aproximaciones a DSM

Existen tres aproximaciones a la implementación de memoria compartida distribuida, las cuales involucran el uso de hardware, memoria virtual o bibliotecas de soporte. Estos no son mutuamente exclusivas necesariamente.


Basada en hardware. Por ejemplo Dash y PLUS. El conjunto de procesadores y los módulos de memoria están conectados vía una red de alta velocidad. El problema es la escalabilidad.

Basado en páginas. Poe ejemplo Ivy, Munin, Mirage, Clouds, Choices, COOL y Mether, todas implanta DSM como una región de memoria virtual que ocupa el mismo rango de dirección en el espacio de direcciones de cada proceso participante. En cada caso el kernel mantiene la consistencia de datos dentro de las regiones DSM como parte del manejo de fallo de página.



Basado en bibliotecas. Algunos lenguajes o extensiones de lenguaje tales como ORCA y Linda soportan formas de DSM.


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal