Multiprocesadores Simétricos: Arquitectura, Redes de Conexión y Coherencia de Caché

1. Introducción

Los multiprocesadores simétricos (SMP) o de acceso uniforme a memoria (UMA) se caracterizan por una memoria compartida por todos los procesadores. Cualquier procesador accede a memoria en un tiempo igual o similar. Todos los procesadores y módulos de memoria se unen a una misma red de conexión.

Son multiprocesadores de pequeña o moderada escala (no más de 32 procesadores). Son la forma más extendida de arquitectura paralela (gracias a los chips multicore).

Están presentes en los servidores, móviles y computadores personales. Además, son un importante elemento constructivo para sistemas MIMD de gran escala.

2. Redes de conexión en computadores UMA

En la mayoría, la red de conexión consiste en un bus compartido. Ventajas:

• Sencillez: el bus es como el de los sistemas monoprocesadores, pero ampliando la lógica de arbitraje (porque varios procesadores pueden pretender acceder a la vez al bus).
• Bajo coste.

Inconvenientes:

• Conforme aumenta el número de procesadores aumenta la competencia por el bus que se convierte en el cuello de botella del sistema.

Otras redes de conexión, con mayor ancho de banda, usadas en multiprocesadores UMA: bus múltiple, barras cruzadas, redes multietapa.

2.1. Red de bus múltiple

• Número de conexiones: b-(n+m).
• Tolerancia a fallos.
• Lógica de arbitraje más costosa cuanto mayor es b.

2.2. Red de barras cruzadas

Red potente: pueden comunicarse, a la vez, todos los procesadores con todos los módulos de memoria (si cada procesador accede a un módulo diferente). Retardo pequeño (el de un único conmutador).

Coste muy elevado (si n grande): cada conmutador (switch) precisa lógica de arbitraje (para resolver competencia por memoria) y unidad conexión bus-bus. El número de conmutadores es proporcional a n².

2.3. Redes multietapa

Están formadas por etapas alternativas de enlaces y conmutadores. El camino entre un procesador y un módulo de memoria atraviesa varios conmutadores (uno de cada etapa).

Son redes con un coste y un ancho de banda intermedios entre la de un solo bus y la de barras cruzadas.

Un ejemplo es la red omega:

• Número de conmutadores totales = n(log₂n) /2 < n² donde hay log₂n etapas con n/2 conmutadores cada una.
• Las etapas de enlace realizan la función de baraje perfecto (dividir en dos mitades y mezclar).
• Retardo moderado (el de log₂n conmutadores).
• Conmutadores de 2 entradas x 2 salidas. Cada conmutador tiene sus propias señales de control.
• Los conmutadores son de cuatro estados: Difusión superior/ Difusión inferior/ Paso directo/ Cruce.

Ejemplo de difusión en la red omega: Difusión desde el procesador 2 a todos los módulos de memoria.

Bloqueo: la conexión simultánea entre varias parejas procesador-módulo de memoria puede ser imposible por conflictos en la red.

3. Redes de conexión en computadores UMA: clasificación

Las redes estudiadas son dinámicas porque permiten conectar procesadores con memorias temporalmente.

• De camino compartido:
  • Bus simple.
  • Bus múltiple.
• De conmutadores:
  • Barras cruzadas.
  • Redes multietapa.

4. Latencia de memoria en computadores UMA

La latencia de memoria puede llegar a ser el cuello de botella en un computador UMA. Para evitarlo hay que atender a tres problemas:

• Competencia por la memoria.
• Retardos debidos a la red de conexión.
• Conflictos en la red de conexión: competencia por el bus y bloqueo en un conmutador de una red multietapa.

Soluciones:

• Memoria entrelazada.
• Uso de cachés.
• Reducir el tráfico en la red de conexión.
• Evitar situaciones de bloqueo en la red de conexión.

5. Cachés en computadores UMA

Todos los computadores UMA poseen cachés porque sus ventajas son muy importantes:

• Se reduce la competencia por memoria compartida.
• Si las cachés son locales a los procesadores, se reduce el tráfico en la red de conexión.

6. Coherencia de caché

La existencia de memorias caché locales a los procesadores puede dar lugar fácilmente a inconsistencias cuyas causas son:

• Los datos compartidos modificables: Dos procesadores P_i y P_j leen una variable compartida. Después P_i la modifica. Si P_j vuelve a leerla, tomará el dato de su caché y por tanto tomará un dato obsoleto.
• La migración de procesos: Un procesador P ejecuta un proceso que pone a 0 una variable privada Z situada en la memoria caché. Después el proceso migra a otro procesador Q que pone Z a 1. Finalmente, la ejecución del proceso retorna a P que lee el valor de Z obsoleto.
• La actividad de entrada/salida: Un procesador, P, modifica la variable Z en su caché, pero no en memoria principal (política write-back). El procesador de E/S lee Z. Como el procesador de E/S toma Z de memoria principal, el valor que lee es incorrecto. El procesador de E/S escribe en Z. Si, después, el procesador P lee Z, tomará el valor de su caché y será un valor obsoleto.

"Hay coherencia caché cuando el valor obtenido por una instrucción de lectura de una variable V es el último valor escrito en V". Problema: en un MIMD, "último" no está bien definido.

La ejecución de un código en un sistema de memoria con coherencia caché debe aparentar ser, a efectos de los accesos al sistema de memoria, como una ejecución sin cachés.

Concepto de ejecución (a efectos de coherencia caché)

Conjunto de operaciones de lectura y escritura (de la ejecución de un código) más una relación de orden. Dicho orden en el conjunto de todas las operaciones es un orden parcial (salvo si solo hay un proceso).

Cada operación la representaremos mediante --> (op_n, proceso, variable, valor) donde op puede ser r (lectura) o w (escritura) y n es el número de orden de la operación en el proceso.

Ejecución con coherencia caché

Una ejecución tiene coherencia caché cuando para toda variable, V, se puede establecer una ordenación total de las operaciones que acceden a esa variable de forma que la lectura lea la última escritura y se respete el orden de las operaciones en cada proceso.

Noción de coherencia caché

El sistema de memoria de un computador tiene coherencia caché si se cumplen las dos condiciones siguientes:

• Propagación de escrituras: en cualquier ejecución en el computador toda escritura de una variable llega a ser visible a todos los procesos.
• Serialización de escrituras: no es posible en el computador ninguna ejecución sin coherencia caché.

6.1. Métodos de coherencia caché

• Estáticos:
  • No se permiten varias copias de un dato en varias cachés.
  • Una solución consiste en distinguir las siguientes clases de información (lo hace el compilador):
    • Soportable en caché: Información de sólo lectura (no crea problemas de coherencia) y datos privados (solo crean problemas si hay migración de procesos). Para evitarlos, cuando un proceso abandona un procesador se limpia su caché (y se copian en memoria principal los bloques modificados).
    • No soportable en caché: Datos compartidos modificables (solo se almacenan en memoria principal).
  • Inconvenientes:
    • Información no soportable en caché => más accesos a memoria principal y a la red de conexión.
    • Limpiar cachés => se pierde tiempo y tasa de aciertos en caché.
  • Organización de caché compartida:
    • Política de escritura directa (write through).
    • La memoria principal siempre está actualizada.
    • Problemas: todos los accesos atraviesan la red de conexión o competencia por caché.
    • Organización para un número pequeño de procesadores.
  • Cachés compartidas para los datos compartidos modificables y cachés privadas para el resto: se mantiene la coherencia y el tiempo medio de acceso a los datos compartidos modificables es menor que sin cachés compartidas.
• Dinámicos:
  • Se permite que haya varias copias de un dato en varias cachés y se utilizan protocolos que garantizan que todas las ejecuciones tienen coherencia caché.
  • Política de actualización de memoria:
    • Write-through o escritura directa (política impaciente).
    • Write-back o postescritura (política perezosa).
  • Política de coherencia caché:
    • Difusión en escritura (política impaciente): Cuando se escribe en una caché se actualizan también todas las copias del mismo dato que haya en otras cachés.
    • Invalidación en escritura (política perezosa): Cuando se escribe en una caché se invalidan todas las copias del mismo dato que haya en otras cachés y en memoria principal.

6.2. Protocolos más usados

• De espionaje (snooping):
  • Los más usados.
  • Típicos de arquitecturas con red de bus simple y cachés locales a los procesadores.
• Basados en directorio:
  • Propios de redes más complejas que la de un solo bus.

6.3. Comparación de políticas de actualización de memoria

• Write-through: Mayor tráfico en la red (todas las escrituras lo generan) => se usa menos.
• Write-back: tras una escritura, la copia de memoria principal queda obsoleta. Algunas lecturas solicitadas por un procesador han de redirigirse a la caché de otro procesador (la que tiene copia actualizada del dato). Controladores de caché más complejos.
• Difusión en escritura: puede reducir la latencia en el acceso a memoria ya que es más probable encontrar el dato actualizado en la caché. Sin embargo, la difusión de datos privados o de datos compartidos modificables poco accedidos genera tráfico innecesario en la red. Las difusiones pueden saturar la red.
• Invalidación en escritura: se usa más en las máquinas comerciales. Se genera menos tráfico en la red. Si un mismo procesador realiza varias escrituras en un dato antes que otro procesador modifique ese dato, solo la primera escritura produce tráfico en la red.

6.4. Métodos dinámicos: protocolos de espionaje

Todo controlador de caché espía el bus: observa las operaciones realizadas por otros procesadores que puedan afectar a la coherencia caché. Los procesadores difunden en el bus cualquier operación que pueda afectar a dicha coherencia.

6.4.1. Ejemplo

Política de escritura: write-through, write-no-allocate (escritura directa y no ubicar en fallos de escritura). Política de coherencia caché: invalidación.

Estados posibles de un bloque:

• Valid-exclusive: la copia de caché es idéntica a la de memoria y es la única copia.
• Shared: hay varias copias del bloque y todas son consistentes.
• Dirty: es la única copia actualizada (la de memoria principal es obsoleta).

• Fallo de lectura -->se emite un Read-Blk.
  • Si hay copias en estado shared o valid-exclusive, una caché (su controlador) envía la copia y todas las cachés con copia del bloque quedan en estado shared.
  • Si hay una caché con una copia dirty, suministra la copia y todas las cachés con copia del bloque quedan en estado shared porque la memoria principal también se actualiza.
  • Si no hay ninguna copia en cachés, la memoria suministra la copia que queda en estado valid-exclusive.
• Acierto de escritura:
  • Si la copia está en estado shared, la caché difunde una operación Update-Blk (con la dirección y el valor del dato): todas las copias existentes, incluida la de memoria principal, se actualizan y permanecen en estado shared.
  • En otro caso, solo se escribe en caché y el bloque queda en estado dirty (no se genera tráfico en el bus).
• Fallo de escritura: La caché difunde un comando de escritura, Write-Blk, en el bus (con la dirección y el valor del dato):
  • Si no hay copias en caché, se actualiza la copia de memoria principal y el bloque actualizado se envía a la caché donde queda en estado valid-exclusive.
  • Si hay copias en estado shared, todas ellas, incluida la de memoria principal, se actualizan y el bloque actualizado se envía a la caché: todas las copias quedan en estado shared.
  • Si hay una copia dirty o valid-exclusive, se actualiza, así como la copia de memoria principal y el bloque actualizado se envía a la caché: las dos copias quedan en estado shared.
• Reemplazo: si el bloque reemplazado está en estado dirty, se actualiza la memoria principal (en otro caso no hay que hacer nada).

6.4.2. Conclusiones

Funcionan bien para un número de procesadores pequeño: Si el número de procesadores es elevado también lo será el tráfico en el bus y en las cachés, que pueden llegar a saturarse.

Para soportar un número elevado de procesadores se suele recurrir a:

• Computadores MIMD de memoria distribuida.
• Red de conexión con más ancho de banda que la de un solo bus.
• Protocolos de coherencia caché basados en directorio (los comandos de coherencia no se envían a todas las cachés sino solo a aquellas que tienen una copia del bloque).

7. Sincronización

Entre procesos (o hebras) cooperantes pueden aparecer dos clases de restricciones de sincronización:

• Relación de precedencia (dependencia de datos).
• Exclusión mutua entre dos fragmentos de código (acceso a un mismo recurso).

En un MIMD no hay sincronización hardware de los procesadores, luego no podemos especular sobre el orden. Si queremos sincronización debemos incluirla en el código.

7.1. Bloqueo y cerradura

Conceptualmente, un mecanismo de bloqueo puede resolver la exclusión mutua. Se requieren dos operaciones, LOCK y UNLOCK, sobre una variable llave, K (1 si está cerrada y 0 abierta).

LOCK debe ser indivisible (dos operaciones LOCK no pueden solaparse). Una forma eficiente de conseguirlo es que el hardware proporcione instrucciones indivisibles del tipo leer-modificar- escribir.

Con dos variables llave solucionamos el problema productor-consumidor.

¿Cuándo debe una hebra volver a intentar la ejecución de LOCK si está la llave echada?

• Continuamente: espera activa(busy-wait) o cierre continuo(spin-lock).
• Intercalando pausas entre los accesos.
• La hebra pasa a estado de espera y, en su lugar, el procesador ejecuta otra hebra.

Test&set y bloqueo

Es una instrucción indivisible del tipo leer-modificar-escribir. La operación LOCK(K) puede implementarse así: repeat test&set(R,K) until R=0. La operación UNLOCK(K) es simplemente: K←0

Problema con LOCK implementado con test&set es que en cada iteración del bucle de espera se produce una escritura en caché y tráfico en el bus para mantener la coherencia caché (por ejemplo, un mensaje de invalidación de otras copias del bloque). Es decir, se genera mucho tráfico en el bus. Sería muy deseable que los intentos fallidos de completar una instrucción del tipo leer-modificar- escribir no generasen escrituras en memoria. Esto puede conseguirse con un par de instrucciones especiales:

• Load-locked (LL): carga en un registro el contenido de una posición de memoria.
• Store-conditional (SC): Si, desde que se ejecutó LL, ningún procesador ha modificado la posición de memoria, almacena el valor de un registro en ella y devuelve un uno (en un flag o un registro). En otro caso, no realiza la escritura y devuelve un cero.

Varios procesadores pueden ejecutar LL a la vez, pero solo uno puede ejecutar SC en cada momento (el primero que coloca la operación en el bus).

El número de instrucciones entre LL y SC debe ser pequeño para que la probabilidad de éxito de SC no sea reducida.

Otras instrucciones indivisibles del tipo leer-modificar-escribir

• Swap (registro, variable_compartida): intercambia los valores de la variable compartida y del registro.
• Fetch&add(registro, variable_compartida, valor_entero): sobre la misma variable compartida, varios procesadores pueden ejecutar a la vez un fetch&add cada uno.

7.2. Sincronización mediante barreras

La barrera consiste en un punto de ejecución en cada proceso. Cuando un proceso llega a la barrera debe esperar hasta que todos los procesos llegan a la barrera y así todos pueden continuar.

Se pueden implementar con la combinación de:

• Un contador compartido del número de procesos que han alcanzado la barrera (que se incrementa atómicamente).
• Una variable compartida (bandera, flag) que es puesta a 1 por el último proceso que llega a la barrera.