Download Memoria Compartida Distribuida

DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Memoria Compartida Distribuida
(Distributed Shared Memory)
Diapo. No. 1
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Sistemas con varios procesadores
Sistema
Multiprocesador
Dos o más procesadores
comparten una memoria
principal común
Sistema
Multicomputadoras
Cada CPU tiene
su memoria particular
Diapo. No. 2
Dr. Roberto Gómez Cárdenas
1
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Memoria en un chip
• Se consideran chips que contienen su CPU y toda la
memoria, (chips usados en carros, juguetes y otras
aplicaciones)
• La porción del CPU del chip tiene líneas de
direcciones y datos que se conectan directamente a la
porción de memoria
• Una posible extensión del chip puede incluir varios
CPUs compartiendo directamente la misma memoria,
(chips multiprocesadores).
• Chips de este tipo son posibles de construir, pero
caros, complicados y no tan usuales.
Diapo. No. 3
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplos esquemas memoria compartida en un solo chip
CPU
:
Memoria
(a) Un simple chip de computadora
CPU2
..
CPU1
:
Memoria
:
CPU3
..
CPU4
(b) Una memoria compartida de multiprocesador hipotética
Diapo. No. 4
Dr. Roberto Gómez Cárdenas
2
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Multiprocesadores tipo bus
• Conexión entre CPU y memoria se hace a través de cables
paralelos:
– algunos transmiten las direcciones y datos que el CPU quiere leer o
escribir
– otros envian o reciben datos
– 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
Diapo. No. 5
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Lectura/escritura en un bus
• Lectura: se deja la dirección de la palabra a leer en el bus y
una señal en el bus de control indicando que se desea leer.
• Cuando la memoria encuentra la palabra buscada, pone el
contenido de esta en el bus, y envía una señal por el bus de
control para notificar que esta lista.
• Después de lo anterior el CPU lee lo que desea
• Las escrituras funcionan de la misma forma
• Varios esquemas son usados para impedir que dos o más
CPUs accesen la memoria al mismo tiempo, por ejemplo
realizar una solicitud de acceso antes de hacer el acceso
CPU
Bus
Dr. Roberto Gómez Cárdenas
CPU
CPU
Memoria
Diapo. No. 6
3
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Multiprocesadores con caché
• Desventaja bus: con tres o cuatro CPUs el bus esta sobrecargado.
• Enfoque usado para reducir lo anterior es equipar el CPU con una
caché
• La mayoría de la literatura con respecto a la caché trata
protocolos de consistencia, (asegurarse que las diferentes cachés
no tienen diferentes valores para la misma dirección)
• Ejemplo protocolo: caché husmeador
CPU
CPU
CPU
Caché
Caché
Caché
Memoria
Bus
Diapo. No. 7
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Consistencia caché
• Objetivo: evitar que diferentes cachés no
contienen diferentes valores para la misma celda
de memoria.
• Protocolo write-through (caché-husmeador)
– Cuando CPU lee una palabra de memoria:
• la palabra es depositada en el bus
• contenido es almacenado en el caché del CPU que hizo la
petición
• si la palabra se necesita después, el CPU la toma de su caché
sin hacer una petición de memoria
• fracaso lectura: la palabra solicitada no esta en la caché
• éxito lectura: la palabra solicitada se encuentra en la caché
Diapo. No. 8
Dr. Roberto Gómez Cárdenas
4
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Consistencia caché
• Protocolo write-through (caché-husmedor)
– Cuando CPU quiere escribir en palabra de memoria:
• si la palabra se encuentra en el caché del CPU que desea hacer
la escritura (éxito escritura) , la entrada en el caché es
actualizada
• también se coloca en el bus para actualizar la memoria
• todas las otras cachés ven la escritura, ya que estan husmeando
en el bus y verifican si la palabra se esta usando en su
máquina, si es el caso la invalidan.
• de esta forma cuando la escritura termina, la memoria esta
actualizada y solo una máquina tiene la palabra en su caché
Diapo. No. 9
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Resumen protocolo de consistencia
caché husmeador
Evento
Acción tomado por un caché en
repuesta a una operación de CPU
local
Fracaso Lectura Acceso dato de la memoria y guardarla en
la caché
Exito Lectura
Accesar el dato en la caché local
Fracaso Escritura Actualizar datos en memoria y guardarlos
en la caché
Exito Escritura Actualizar memoria y caché
Acción tomada por una
caché en respuesta a
una operación de CPU
remota
(Ninguna acción)
(Ninguna acción)
(Ninguna acción)
Entrada caché invalida
Diapo. No. 10
Dr. Roberto Gómez Cárdenas
5
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Alternativa a invalidar
• Alternativa para invalidar las caches es actualizar todas
• Invalidar solo requiere la dirección de la palabra a ser
invalidada.
• Actualizar requiere que se proporcione el nuevo valor
también.
• Si dos items deben transmitirse por el bus, el ancho de
banda se verá afectado.
• También será necesario más trabajo por parte del CPU
para actualizar todo
– en vez de trabajar una vez, debe trabajar dos
• El tema de validar contra actualizar pasa en todos los
protocolos de tipo caché así como en los sistemas DSM.
Diapo. No. 11
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo de membresía write once
• En general si un CPU escribe una palabra, es más
lógico que sea ese mismo CPU el que vuelva a
utilizarla y es menos probable que otro CPU la
utilice.
• Si un CPU tiene una “propiedad” temporal de la
palabra, puede evitarse el hecho de actualizarla en
escrituras subsecuentes hasta que una CPU
diferente muestre interés en dicha palabra.
• Goodman (1983) propuso un protocolo en base a
lo anterior: de una escritura
Diapo. No. 12
Dr. Roberto Gómez Cárdenas
6
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Estados de los bloques caché
• Protocolo maneja bloques caches los cuales pueden
caer en los siguientes estados:
1. Inválido - bloque de caché no contiene datos válidos
2. Limpio - memoria actualizada, bloque puede estar en otros
caches
3. Sucio - memoria incorrecta, ninguna otra caché tiene el
bloque
• Idea base: una palabra que es leída por varios CPUs
puede estar presente en todos sus cachés.
– la palabra que es escrita regularmente por una máquina es
dejada en su caché y no es escrita en memoria cada vez que
es escrita
Diapo. No. 13
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplo 1: estado inicial
Memoria
correcta
CPUs
A
B
C
W1
W1
LIMPIO
• La palabra W, que contiene el valor W1, se encuentra en
memoria y en la caché del CPU B
Diapo. No. 14
Dr. Roberto Gómez Cárdenas
7
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplo 2: lectura palabra
Memoria
correcta
A
B
W1
W1
LIMPIO
C
W1
LIMPIO
• A lee la palabra W y toma W1, B no responde
a la lectura, pero la memoria lo hace
Diapo. No. 15
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplo 3: escritura de una palabra
Memoria
correcta
A
B
W2
W1
SUCIO
C
W1
INVALIDO
• A escribe un valor W2, B husmea en el bus, ve la escritura,
invalida su entrada. La copia de A es marcada como sucia
Diapo. No. 16
Dr. Roberto Gómez Cárdenas
8
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplo 4: otra escritura
Memoria
correcta
A
B
W3
W1
SUCIO
W1
C
INVALIDO
• A escribe W de nuevo. Esta y subsecuentes escrituras de A
son realizadas localmente, sin generar tráfico en el bus
Diapo. No. 17
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplo 5: lecturo o escritura
Memoria
correcta
A
B
C
W3
W1
W3
INVALIDO
INVALIDO
W1
SUCIO
• C lee o escribe W. A detecta la petición husmeando en el bus,
proporciona el valor e invalida su propia entrada. Ahora C tiene
la única copia válida.
Diapo. No. 18
Dr. Roberto Gómez Cárdenas
9
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ultimos comentarios ejemplo
• C es el propietario de la palabra
– puede leer escribir y leer en ella sin hacer peticiones en
el bus
– tienen la responsabilidad de estar atento por peticiones
de otros CPUs y atenderlas
• La palabra se queda en un estado de sucio hasta
que es purgada de la caché
– cuando eso ocurre desaparece de todas las cachés y es
escrita de nuevo en la memoria
Diapo. No. 19
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Multiprocesadores basados en anillo
• Ejemplo Memnet: un espacio de direcciones se
divide en una parte privada y otra compartida.
• La parte privada:
– se divide en regiones cada máquina cuenta con memoria
para su pila, datos y códigos no compartidos.
• Parte compartida:
– 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)
Diapo. No. 20
Dr. Roberto Gómez Cárdenas
10
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Características anillo
• Anillo consta de 20 cables paralelos que juntos
permiten enviar 16 bits de datos y 4 bits de control
cada 100 nanosegundos.
• La interfaz de anillo, MMU, el caché y una parte de
la memoria se integran en el dispositivo Memnet.
• No existe una memoria global centralizada.
• Cada bloque de 32 bytes en el espacio compartido
de direcciones tiene una máquina de origen donde
la memoria física esta siempre reservada para él.
– máquina origen = máquina hogar
Diapo. No. 21
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Esquema del anillo Memmet
CPU
CPU
CPU
CPU
CPU
CPU
Diapo. No. 22
Dr. Roberto Gómez Cárdenas
11
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Características de los bloques
• Un bloque puede ocultarse en una máquina distinta a
su máquina de origen.
• Un bloque de solo lectura puede estar presente en
varias máquinas.
• Un bloque de solo escritura puede estar presente en
sólo una máquina.
• En ambos casos el bloque no necesita estar en su
máquina hogar.
• Todas las máquinas hogar deben garantizar un
espacio para almacenar el bloque si ninguna otra
máquina lo tiene en su cache.
Diapo. No. 23
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
El dispositivo Memnet
• Cuenta con una tabla en cada máquina.
– contiene una entrada por cada bloque del espacio de
direcciones compartido
– la tabla esta indexada por número de bloque
• La tabla indica el estado del bloque:
–
–
–
–
–
bit válido: bloque presente en caché y actualizado
bit exclusivo: bloque presente en caché es único
bit origen: el bloque pertenece a la máquina hogar
bit interrupción: forzar interrupciones
campo posición: si el bloque esta presente y es válido
nos indica en donde este ubicado
Diapo. No. 24
Dr. Roberto Gómez Cárdenas
12
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Detalle de la máquina y la tabla del
bloque
MMU Caché
Memoria
de origen
Tabla del
bloque
0
1
2
3
4
CPU
Memoria privada
CPU
Válido
Exclusivo
Origen
Interrupción
Posición
CPU
CPU
CPU
CPU
CPU
Diapo. No. 25
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo de Memnet (lectura)
• Dirección memoria se pasa al dispositivo Memnet
• Dispositivo verifica si el bloque esta presente
• Si esta presente:
– solicitud es satisfecha de inmediato
• Si no esta presente:
–
–
–
–
dispositivo espera hasta que le llegue la ficha
coloca un paquete de solicitud en el anillo
el CPU suspende sus actividades
paquete petición contiene dirección deseada y un
campo vacío de 32 bytes
Diapo. No. 26
Dr. Roberto Gómez Cárdenas
13
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo de Memnet (lectura) ...
• Si no esta presente:
– mientras paquete pasa por el anillo cada dispositivo
Memnet verifica si tiene el bloque deseado
– si lo tienen coloca el bloque en el campo vacío y
modifica el bit del encabezado del paquete para inhibir
la acción de las máquinas posteriores
– si el bit exclusivo del bloque esta activo, se limpia
– como el bloque tiene que estar en un lado, cuando el
paquete regresa al emisor, se garantiza que contiene el
bloque solicitado
– el CPU envía la solicitud guarda el bloque, satisface la
solicitud y libera el CPU
Diapo. No. 27
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
¿Y si no hay espacio?
• ¿Qué pasa si la máquina solcitante no tiene
espacio libre en su caché, para contener el bloque
remoto?
• Para hacer espacio toma al azar un bloque oculto y
lo envía a su origen
– se libera un espacio del caché
• Los bloques cuyo bit origen está activo nunca se
eligen, pues se encuentran en su origen
Diapo. No. 28
Dr. Roberto Gómez Cárdenas
14
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo Memnet (escritura)
• Es diferente al de lectura
• Se quiere escribir datos en un bloque de la
memoria compartida
• Se pueden presentar tres casos:
– Si el bloque contiene la palabra por escribir
– Si el bloque necesario esta presente pero no es la única
copia
– Si el bloque no esta presente
Diapo. No. 29
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo Memnet: escritura caso 1
• Si el bloque contiene la palabra por escribir está
presente y es la única copia en el sistema
– el bit exclusivo esta activado
• No es necesario buscar la palabra en otro lugar
• En este caso la palabra se escribe de manera local.
Diapo. No. 30
Dr. Roberto Gómez Cárdenas
15
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo Memnet: escritura caso 2
• Si el bloque necesario esta presente pero no es la
única copia.
• Se envia primero un paquete de invalidación por el
anillo
– las otras máquinas desechan sus copias de bloque en el
que se va a escribir
• Cuando el paquete regresa, el bit exlusivo del
dispotivo de la máquina se activa y se procede a
una escritura local
Diapo. No. 31
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo Memnet: escritura caso 3
• Si el bloque no esta 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 la copia
en el paquete y desecha su copia.
• Todas las máquinas posteriores solo desechan el
paquete.
• Cuando el paquete regresa al emisor, éste lo
guarda y escribe en él.
Diapo. No. 32
Dr. Roberto Gómez Cárdenas
16
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Memnet vs bus
• Similitudes
– en ambos casos las operaciones siempre regresan el
valor escrito de manera más eficiente
– un bloque puede estar ausente de un caché, presente en
varios cachés para su lectura, o presente en un caché
para escritura
• Diferencias
– los de bus están fuertemente acoplados, con
regularidad, los CPUS están en un gabinete
– los de anillo pueden estar menos acoplados,
potencialmente en escritorios dispersos en un edificio,
como máquinas en una LAN
Diapo. No. 33
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Multiprocesadores con conmutador
• En anillo o bus, el echo de añadir un CPU satura el ancho de
banda del bus o anillo
• Dos métodos para solucionar el problema:
– 1. Reducir la cantidad de comunicación
– 2. Incrementar la capacidad de comunicación
• Una forma de reducir la cantidad de comunicación es el
ocultamiento trabajo adicional en esta área:
– mejorar protocolo de ocultamiento
– optimizar el tamaño del bloque
– 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
Diapo. No. 34
Dr. Roberto Gómez Cárdenas
17
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Solución propuesta
• Cambiar la topología de la red de interconexión.
• Es posible construir el sistema como una jerarquía.
• Se continúan colocando algunos CPU en un bus,
pero se considera todo esto como unidad.
• Se construyen varias unidades y se conectan
mediante un bus entre ellas
• Si se necesita más ancho de banda, se reúne un bus,
un árbol o una cuadrícula de unidades en una
superunidad, y se separa el sistema en varias
superunidades.
Diapo. No. 35
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Solución propuesta ...
• Las superunidades se pueden conectar mediante un
bus, árbol o cuadrícula, y así en lo sucesivo.
• Un ejemplo de lo anterior es la máquina Dash,
diseño jerárquico basado en una cuadrícula de
unidades
Diapo. No. 36
Dr. Roberto Gómez Cárdenas
18
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Formando una superunidad
CPU
Memoria
Unidad
C
C
C
C
C
C
C
C
C
C
C
C
Bus entre
unidades
M
C C C C
M
C C C C
M
C C C C
M
C C C C
M
C C C C
M
C C C C
M
M
Interfaz
M
Bus entre
unidades
Bus entre superunidades
Diapo. No. 37
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
La máquina Dash
• Construida en la Universidad de Stanford en 1992.
• Se han echo muchas otras investigaciones con
trabajos parecidos.
• Un prototipo de 64 CPUs fue construido, aunque el
diseño se pensó con cuidado para construir una
versión más grande.
• Consta de 16 unidades, cada una conteniendo un bus,
cuatro CPU, 16M de memoria global y algo de
equipo de E/S (discos, etc).
• Cada CPU es capaz de “husmear” en su bus local,
pero no en los demás buses.
Diapo. No. 38
Dr. Roberto Gómez Cárdenas
19
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
La memoria en la máquina Dash
• Se cuenta con un espacio total disponible: 256M,
dividido en 16 regiones de 16M c/una:
– memoria global unidad 0 contiene direcciones de 0 a
16M
– memoria global unidad 1 contiene direcciones de 16M a
32M
• La memoria es oculta y transferida en bloques de
16 bytes, de modo que cada unidad tiene bloques
de memoria de 1M dentro de su espacio de
direcciones
Diapo. No. 39
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Los directorios
• Cada unidad tiene un directorio con un registro de
las unidades que tienen copias de sus bloques
• Cada unidad tiene 1M de bloques de memoria, por lo
que tiene 1M entradas en su directorio
• Cada entrada tiene:
– un mapa de bits, (un bit por unidad), que indica si la
unidad tiene el bloque oculto
– un campo de 2 bits que indica el estado del bloque
• DASH = Directory Architecture for Shared Memory
Diapo. No. 40
Dr. Roberto Gómez Cárdenas
20
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Listas explicitas
• Un mapa de bits no es la única forma saber que
unidad tiene que bloque.
• Otro método es organizar las entradas como lista
explícita que indique las unidades que contienen el
bloque de caché correspondiente.
• Si se comparte poco: lista requiere de pocos bits.
• Si se comparte mucho: se requieren más bits.
• Las listas tienen la desventaja de ser estructuras de
datos de longitud variable.
• Máquina Alewif del MIT usa listas.
Diapo. No. 41
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
La unidad DASH
• Unidad Dash se comunica con otras a través de una
interfaz.
• Las interfaces se conectan mediante enlaces entre
las unidades en una cuadrícula rectangular.
• El sistema de enlaces entre las unidades utiliza el
ruteo de seguimiento de túneles
– primera parte de un paquete puede adelantarse aún antes
de recibir todo el paquete
• En realidad existen dos conjuntos de enlaces entre
las unidades
– uno es para los paquetes de solicitud y otros para los de
respuesta
Diapo. No. 42
Dr. Roberto Gómez Cárdenas
21
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Memoria
global
CPU
con cache
C
Dr. Roberto Gómez C.
C
M
Arquitectura Dash
I
I
C
0
C
M
C
C
C
C
8
M
C
I
C
M
C
M
C
M
C
C
C
C
M
7
D
M
10
I
C
C
M
11
D
I
C
C
D
M
14
I
C
C
M
D
Bus entre unidades, (sin husmeador)
Bus husmeador
I
D
13
D
3
D
6
I
C
M
I
D
12
C
D
9
M
D
C
C
I
C
C
2
I
D
I
I
D
5
M
D
C
M
I
C
4
Número
de unidad
C
D
I
M
C
1
D
Directorio
I
Interfaz entre unidades
15
D
Unidad
Memoria Distribuida Compartida
Diapo. No. 43
Dr. Roberto Gómez C.
Ejemplo directorio Dash
Estado
Unidad
Bloque 0
Bit que indica si
la unidad 0 tiene
el bloque 3 de
la memoria cuyo
origen es la unidad
14 en cualquiera
de sus cachés
1
2 3
4
5 6
7 8
9 10 11 12 13 14 15
0
1
2
3
~
~
~
~
{no oculto,
limpio,
sucio}
Indica que bloque se comparte con que unidad
Diapo. No. 44
Dr. Roberto Gómez Cárdenas
22
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
El caché en la máquina DASH
• El caché es realizado en dos niveles
– caché de primer nivel
– caché de segundo nivel
• El caché de primer nivel es un subconjunto del caché
de segundo nivel.
• Cada bloque caché puede estar en los siguientes
estados:
– NO OCULTO: la única copia del bloque reside en esta
memoria
– LIMPIO: memoria actualizada, el bloque puede estar en
varias cachés
– SUCIO: memoria incorrecta, solo una caché
Diapo. No. 45
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolos DASH
• Protocolos basados en la membresía y la
invalidación.
• En cada instante cada bloque de caché tiene un
propietario único
– para bloques NO_OCULTOS o LIMPIOS la unidad de
hogar del bloque es el propietario
– para bloques SUCIOS la unidad que tiene la única
copia es el propietario
• Escribir en un bloque limpio requiere encontrar e
invalidar todas sus copias
– es aquí donde los directorios son usados
Diapo. No. 46
Dr. Roberto Gómez Cárdenas
23
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo DASH lectura
• Máquina verifica su propia caché ( o sus cachés)
• Si no tiene la palabra, una petición es realizada en
los CPUs de la unidad para ver si alguno de estos
tiene el bloque.
– la busqueda es realizada dentro de la unidad
• Si un CPU dentro de la misma unidad la tiene se
lleva a cabo una transferencia caché-caché
– Si el bloque está LIMPIO se hace una copia
– Si el bloque está SUCIO el directorio hogar es
informado que el bloque está LIMPIO y compartido
Diapo. No. 47
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo DASH lectura ...
• Si el bloque no esta presente en alguna cache de la
unidad:
– un paquete de petición es enviado a la unidad hogar del
bloque
– dirección unidad hogar puede determinarse examinando
los 4 bits de la parte alta de la dirección
• La unidad hogar puede ser la unidad que realiza la
petición
– mensaje no es enviado fisicamente
– admon directorio en unidad hogar examina sus tablas para
ver en que estado se encuentra el bloque:
• NO OCULTO o LIMPIO
• SUCIO
Diapo. No. 48
Dr. Roberto Gómez Cárdenas
24
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo DASH lectura ...
• Si edo = NO_OCULTO o LIMPIO
– el hardware lo toma de su memoria y lo envia a la unidad que lo
pidio
– actualiza su directorio, marcando al bloque como “capturado”
(cached) en la unidad que lo solicitó
• Si edo = SUCIO
– hardware directorio ve la identidad de la unidad que contiene el
bloque y le envia la solicitud
– unidad con bloque sucio lo envia a la unidad que lo solicitó y marca
su copia como limpia
• ya que ahora esta compartida
– envia una copia de regreso a la unidad hogar, de tal forma que la
memoria pueda actualizarse y cambia el estado del bloque a
LIMPIO.
Diapo. No. 49
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Resumen protocolo Dash en lectura
Estado del bloque
Caché de R
Caché vecino
NO OCULTO
LIMPIO
Utilizar bloque
Copiar bloque al
caché de R
SUCIO
Utilizar bloque
Enviar el bloque
en R y ala unidad
de origen; indicar
unidad que lo marque como LIMPIO
y ocultarlo unidad R
Memoria de la
unidad de origen
Caché de alguna
unida
Enviar bloque a R;
marcarlo como
LIMPIO y ocultarlo
sólo en la unidad R
Copiar el bloque de
la memoria a R; marcarlo como oculto
también en la unidad
de R
Enviar el bloque a
R y a la unidad de
origen (si esta
OCULTO en alguna parte); indicar
al origen que lo
marque como
LIMPIO y también
ocultarlo en la
unidad de R
Diapo. No. 50
Dr. Roberto Gómez Cárdenas
25
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo DASH escritura
• Para que realice una escritura el CPU debe estar
seguro de ser el único propietarios del bloque en el
sistema
• Si ya tiene el bloque en su cache y esta SUCIO, la
escritura se lleva a cabo inmediatamente.
• Si ya tiene el bloque y esta LIMPIO, un paquete es
enviado a la unidad hogar solicitando que todas las
copias sean invalidas.
• Si no lo tiene en su cache:
– verifica si otro CPU de su unidad lo tenga
Diapo. No. 51
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo DASH escritura
• Si el bloque lo tiene un CPU de su unidad:
– una transferencia caché-caché se lleva a cabo
– si el bloque esta LIMPIO todas las otras copias, si las hay,
deben ser invalidadas por la unidad hogar
• Si el bloque se encuentra en alguna otra unidad-hogar:
– un paquete es enviado a esta unidad
– tres casos son posibles:
• NO OCULTO: se marca SUCIO y se envia al que hizo la petición
• LIMPIO: todas las copias son invalidadas y el mismo procedimiento
que para NO-OCULTO se aplica
• SUCIO: petición es redirigida a la unidad remota que actualmente
tiene el bloque, esta unidad invalida su propia copia y satisface la
petición
Diapo. No. 52
Dr. Roberto Gómez Cárdenas
26
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Resumen protocolo Dash para escrituras
Estado del bloque
Caché de R
Caché vecino
NO OCULTO
LIMPIO
Enviar el mensaje al
origen solicitando la
proximidad exclusiva
en el edo. SUCIO; si
se otorga, usar bloque
SUCIO
Utilizar bloque
Copiar e invalidar
bloque, enviar mensaje al origen solitando la propiedad
exclusiva en estado
SUCIO
Transferencia entre
cachés a R; invalidar
la copia vecina.
Memoria de la
unidad de origen
Caché de alguna
unidad
Enviar bloque a R;
marcarlo como
SUCIO y ocultarlo
en la unidad R
Enviar bloque a R;
invalidar todas las
copias ocultas, marcarlo como SUCIO y
ocultarlo solamente en
la unidad de R
Enviar el bloque
directamente a R; y
origen (si esta
invalidar la copia
oculta; el origen lo
marca como
SUCIO y lo oculta
solamente en la
unidad de R
Diapo. No. 53
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Consistencia
• Mantener consistencia no es algo simple.
• Un simple acceso a memoria puede requerir
un gran número de paquetes a ser enviados.
• Para tener consistencia de memoria, el
acceso no es completado hasta que todos los
paquetes han sido “acknowledged”
(reconocidos)
– esto puede tener efectos en el desempeño
Diapo. No. 54
Dr. Roberto Gómez Cárdenas
27
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Los multiprocesadores NUMA
• Son una alternativa a los esquema de tipo caché.
• NUMA: Non Uniform Memory Access
• Los NUMA, al igual que un UMA (Uniform Memory
Acess) cuenta con un espacio de direcciones visible
pata todos los CPUs,
– cuando un CPU escribe en A, una lectura posterior de A,
por otro CPU, regresara un valor recien escrito por A
• La diferencia entre UMA y NUMA no radica en la
semantica sino en el desempeño.
– NUMA: acceso a memoria remota es más lento que local y
no se hace nada para remediarlo (p.e. usar caché)
Diapo. No. 55
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Características multiprocesadores NUMA
• Existe un acceso de no-uniforme de acceso a
memoria
– ya que los datos y la memoria pueden estar fisicamente
distribuidos, los mecanismos de acceso no son uniformes,
dependiendo si la información deseada es local o remota
• La conexión entre módulos locales puede ser buses,
redes de interconexión o subredes de comunicación
• La granuralidad de accesos a memoria puede ser una
palabra, una línea caché de palabras, una página o
un segmento, (bloque en este caso)
Diapo. No. 56
Dr. Roberto Gómez Cárdenas
28
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Arquitectura General NUMA
(Chow and Jhonson)
procesador
memoria
controlador de
coherencia de memoria
procesador
memoria
controlador de
coherencia de memoria
buses, red de interconexión o red de comunicación
Diapo. No. 57
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Tipos Arquitecturas NUMA
(Chow and Jhonson)
• Multiprocesador caché
– Uso de cachés locales en cada procesador son usados
para reducir latencias de acceso a memoria y tráfico de
acceso a memoria compartida
• Arquitectura DSM
– No existe memoria global física. Una memoria virtual
global es creado mapeando todas o partes de la
memoria local, en un espacio de direcciones global
compartido por todos los nodos.
Diapo. No. 58
Dr. Roberto Gómez Cárdenas
29
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Cache multiprocesador vs arquitectura DSM
Memoria Global
Arquitectura de
cache multiprocesador
Bus común
Caché locales
Procesadores
Espacio memoria virtual
Red de comunicación
Arquitectura de
memoria compartida distribuida
Memoria Local
Procesadores
Diapo. No. 59
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Diferencias tipos arquitecturas
(Chow and Jhonson)
• Diferencia clave: tiempo de retardo en acceso de
información compartida.
– tiempo acceso en DSM es mayor que el de caché
• Otra diferencia es la conexión de los módulos,
para sistemas caché es más fácil realizar un
broadcast, mientras que esto no es posible en
sistemas DSM
Diapo. No. 60
Dr. Roberto Gómez Cárdenas
30
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Ejemplos multiprocesadores NUMA
(Tanenbaum)
• Máquina Cm*
• BBN Butterfly
Diapo. No. 61
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Máquina Cm*
• Formada por varias unidades cada una con un
CPU, un MMU microprogramable, un módulo de
memoria y posiblemente algunos dispositivos de
E/S, todos conectados mediante un bus.
• No hay cachés y no se husmean los buses.
• Las unidades fueron conectadas mediante buses
entre las unidades.
• Cuando se hace una llamada a memoria, la
solicitud llega al MMU del CPU que averigua cual
memoria se necesita.
Diapo. No. 62
Dr. Roberto Gómez Cárdenas
31
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Vista simplificada de un sistema Cm*
Unidad
CPU
M
E/S
Bus local
Bus
entre
unidades
CPU
M
E/S
CPU
M
E/S
MMU microprogramado
Memoria local
Diapo. No. 63
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo de acceso
• CPU realiza una referencia a memoria, la petición se
va al MMU.
• El MMU examina los bits superiores para ver que
memoria se necesita.
• Si la dirección es local:
– MMU pone petición en el bus local
• Si la dirección es remota:
– MMU construye un paquete de petición con la dirección
(y para escritura el dato a escribir) y lo envía a la unidad
destino a travéz del bus-interunidad.
Diapo. No. 64
Dr. Roberto Gómez Cárdenas
32
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Protocolo de acceso ...
– cuando la unidad lo recibe, el MMU destino
realiza la operación y regresa el dato (lectura) o
un ack (escritura)
• Desventaja
– el CPU ejecuta un programa que reside por
completo en memoria remota:
• por cada palabra leída y escrita se envía un paquete
• lo anterior reduce el desempeño de las operaciones en
gran escala
Diapo. No. 65
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
BBN Butterfly
• Cada CPU se acopla de forma directa a una
memoria.
• Los CPUs se conectan a través de conmutadores,
cada uno con cuatro puertos de entrada y cuatro de
salida:
– los CPUs de la parte derecha son los mismos que los de la
izquierda
• Peticiones locales:
– se manejan de forma directa.
Diapo. No. 66
Dr. Roberto Gómez Cárdenas
33
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
BBN Butterfly ...
• Peticiones remotas:
– las solicitudes remotas se convierten en paquetes de
petición y son enviados a la memoria apropiada a través de
la red switcheada
• Desventaja:
– misma que el modelo anterior
– los programas ejecutados remotamente le pegan al
desempeño
• Observaciones (Cm* y Butterfky)
– ninguno de los ejemplos cuenta con memoria global
– NUMA puede ser equipado con memoria que no
pertenezca a ningún CPU
Diapo. No. 67
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Esquema de una BBN Butterlfy
CPU
Conmutadores
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
CPU
Conmutadores
Diapo. No. 68
Dr. Roberto Gómez Cárdenas
34
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Propiedades multiprocesadores NUMA
• Es posible el acceso a la memoria compartida
• El acceso a la memoria remota es más lento que el
de la memoria local
• El tiempo del acceso remoto no se oculta mediante
el uso de los cachés
– en Dash y NUMA también el acceso remoto es más
lento que el local
– el caching ayuda a lo anterior
– cache: si una palabra remota es tocada el bloque de
memoria alrededor de ella se envia al caché
– los futuros accesos son más rápidos
Diapo. No. 69
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Características software NUMA
• NUMA no cuenta con propiedad de caché a nivel
hardware.
• Es importante tomar en cuenta en que memorias
encuentran almacenadas las páginas.
• Algunas opciones son las ideas aportadas por:
– LaRowe y Ellis
– Cox y Flower
– Ramanathan y NI
Diapo. No. 70
Dr. Roberto Gómez Cárdenas
35
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
La propuesta de LaRowe y Ellis
• Cuando programa empieza, páginas pueden o no
ser manualemente colocadas en ciertos
procesadores.
• Cuando un CPU requiere acceso a una página que
no se encuentra asociada a su espacio de
direcciones:
– sistema operativo es informado y toma decisión.
– si la página es de solo lectura, la opción es duplicar la
página o asociar la página virtual en la memoria remota
lo que obliga a un acceso remoto para todas las
direcciones de dicha página
Diapo. No. 71
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
La propuesta de LaRowe y Ellis (cont)
– si la página es de lectura/escritura, la opción consiste en
mover la página al procesador que solicitó la página
• Consecuencias decisión:
– si se creo una copia local (replica o migración) y esta
no se usa demasiado, habrá un gasto considerable de
tiempo perdido por nada
– si no se realiza ninguna copia, la página se asocia de
una manera remota.
– resumiendo, sistema operativo tiene que ver si la página
será utilizada con frecuencia en el futuro, si la falla será
una falla en el desempeño.
Diapo. No. 72
Dr. Roberto Gómez Cárdenas
36
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Consecuencias de la propuesta de
LaRowe y Ellis
• Sin importar la decisión que tome, la página
asociada, de forma local o remota, y la instrucción
fallida se reestablece
• Las llamadas posteriores a esta página se hacen en
hardware, sin la intervención del software.
• Si no se toma otra decisión, una vez tomada una
mala decisión, no podra ser invertida.
Diapo. No. 73
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Algoritmos NUMA
• Para permitir la correción de errores y la adaptación
del sistema a los cambios en los patrones de
referencia, los sistemas NUMAS cuentan con un
proceso demonio, el digitalizador de páginas.
– de forma periodica el demonio reúne las estadísticas de
uso acerca de las referencias locales y remotas, que se
mantienen con ayuda del hardware.
– cada n ejecuciones el demonio evalúa las decisiones
anteriores para copíar páginas o asociarlas a memorias
remotas.
Diapo. No. 74
Dr. Roberto Gómez Cárdenas
37
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Algoritmos NUMA: congelando páginas
• Si estadísticas indican que una una página está en un
lugar incorrecto el demonio elimina la asociación de
la página para que siguiente referencia cause un falló
de página.
– lo cual permite que se tome una nueva decisión de
colocación.
– si una página se mueve con frecuencia en un corto
intervalo, el demonio puede marcar cada página como
congelada, lo que inhibe los movimientos posteriores hasta
que ocurre algún evento
Diapo. No. 75
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Algoritmos NUMA: estrategias propuestas
• Las estrategias difieren en
– algoritmo usado para invalidar las páginas.
– algoritmo usado para tomar decisiones de colocación
después de un fallo de página.
• Algoritmos de invalidación posibles:
– invalidar cualquier página para la que hayan más
referencias remotas que locales.
– en invalidar una página sólo si el contador de referencias
remotas ha sido mayor que el local durante las k-últimas
ejecuciones del demonio.
Diapo. No. 76
Dr. Roberto Gómez Cárdenas
38
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
• Algoritmos decisiones de ubicación
– cuando ocurre un fallo de página varios algoritmos son
posibles,
– algunos de los cuales siempre incluyen réplica/migración
y otros nunca incluyen réplica/migración.
– un algoritmo consiste en replicar o migrar a menos que la
página este congelada
– otros algoritmos toman en cuenta los patrones de uso
reciente, al igual que el hecho de que la página éste o no
en su máquina de origen.
• Se han comparado muchos algoritmos y se ha
concluido que no existe una política que sea la
mejor.
Diapo. No. 77
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Espectro máquinas memoria compartida
Controlado por MMU
Fuertemente acoplado
Multiprocesador con un bus
Multiprocesador con conmutador
Sequent
Firefly
Bloque
caché
Dash
Alewife
Bloque
caché
Acceso remoto en hardware
Ocultamiento controlado por el software
Controlado por el
sistema operativo
Máquina
NUMA
Cm*
Butterfly
Página
Controlado por el sistema de
tiempo de ejecución del lenguaje
DSM
basado en
páginas
DSM con
variables
compartidas
Ivy
Mirage
Página
Munin
Midway
Estructura
de datos
DSM
basado en
objetos
Linda
Orca
Objeto
Vagamente acoplado
Ocultamiento controlado por el hardware
Acceso remoto en software
Unidad de transferencia
Diapo. No. 78
Dr. Roberto Gómez Cárdenas
39
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Multiprocesadores con bus
• Compuestos de cachés a nivel hardware.
• Consistencia se mantiene husmeando el bus.
• Las máquinas de memoria compartida más
simples.
• Operan completamenten en hardware.
• Ejemplos: algunas Sequent o la estación
experimental DEC Firefly (cinco VAX en
un bus común).
Diapo. No. 79
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Multiprocesadore switcheados
• Tambien tiene un caché en hardware
• Usa directorios u otras estructuras de datos para
saber en que CPUs o unidades estan los
bloques.
• Algoritmos complejos son usados para
mantener consistencia.
– almacenados en microcódigo MMU
– cuentan casi como implementaciones en hardware
• Ejemplos: Dash de Stanford y Alewife del MIT
Diapo. No. 80
Dr. Roberto Gómez Cárdenas
40
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
El Alewife del MIT
Diapo. No. 81
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Máquinas NUMA
• Hibridos entre control a nivel hardware y
software.
• Cada CPU NUMA puede acceder cada
palabra del espacio de direcciones virtuales.
• El caché ( i.e ubicación y migración de
páginas ) es controlado por software (sistema
operativo) y no por hardware (MMUs).
• Ejemplos: Cm* y BBN Butterfly
Diapo. No. 82
Dr. Roberto Gómez Cárdenas
41
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
NUMA-Q de IBM
Diapo. No. 83
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
DSM con Paginas Distribuidas
• 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
Diapo. No. 84
Dr. Roberto Gómez Cárdenas
42
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
DSM de variable compartidas
• Máquinas que comparten solo una parte de su espacio
de direcciones.
• Usuario determina que variables se van a compartir y
cuales no.
• Enfoque cambia:
– de pretender que existe una memoria en común
– a mantener consistente un conjunto replicado de estructuras
de datos distribuidas
– se enfrenta a actualizaciones, potencialmente de todas las
páginas que usan los datos compartidos
Diapo. No. 85
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
DSM con varibales compartidas
(cont)
• En algunos casos el hardware de paginación
detecta escrituras, lo cual ayuada a mantener la
consistencia.
• En otros casos el hardware de paginación no es
usado para el manejo de consistencia.
• Ejemplos: Sistemas Munin y Midway
Diapo. No. 86
Dr. Roberto Gómez Cárdenas
43
DSM: Distributed Shared Memory
Sistemas Distribuidos
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
DSM con objetos compartidos
• A diferencia de otros sistemas, aquí los programas
no solo pueden acceder los datos compartidos.
• Tienen que pasar por metodos protegidos, lo que
ayuda a mantener la consistencia del sistema.
• Todo es hecho en software, sin ningún
soporte tipo hardware.
• Ejemplos sistemas: Orca y
Linda.
Diapo. No. 87
Memoria Distribuida Compartida
Dr. Roberto Gómez C.
Comparación seis tipos de sistemas de memoria compartida
Punto
Tiene espacio de direciones
virtuales, compartido y lineal
Operaciones posibles
Encapsulado y métodos
Es posible el acceso remoto
en hardware
Es posible una memoria no
conectada
Quien convierte los accesos a
memoria remota en mensajes
Un bus
Con conmutador
Numa
Basado en Variables
Basado
páginas compartidas en objetos
Si
Si
Si
Si
No
L/E
No
Sí
L/E
No
Sí
L/E
No
Sí
L/E
No
No
L/E
No
No
Sí
Sí
Sí
No
No
MMU
MMU
No
General
Sí
No
No
MMU Sistema Sistema de Sistema de
operativo tiempo de tiempo de
ejecución ejecución
Medio de transferencia
Bus
Bus
Bus
Red
Red
Red
La migración de datos es rea- Hardware Hardware Software Software Software
Software
lizada mediante
Unidad de transferencia
Bloque
Bloque Página Página Variable
Objeto
compartida
Diapo. No. 88
Dr. Roberto Gómez Cárdenas
44