Arquitecturas de Multiprocesadores: Memoria Compartida vs. Paso de Mensajes

Multiprocesadores

Lograr mayor velocidad y capacidad de cómputo se puede solucionar con el paralelismo. Contar con varias CPU que operen a velocidad normal y que en conjunto provean la potencia necesaria. Con una CPU el esquema es sencillo, pero con varias CPU necesitamos un coordinador que se encargue de repartir las tareas.

Multiprocesadores con memoria compartida:

La comunicación entre las CPU es mediante la memoria compartida, y cada CPU tiene acceso a la misma mediante un único bus físico. 2 a 10 nseg.

• Dos o más CPU comparten el acceso a la RAM.
• Los programas se ejecutan en cualquier CPU.
• Cada proceso se un espacio normal de direcciones virtuales.
• La CPU puede escribir cierto valor en una palabra de memoria y después volver a leer esa palabra y obtener un valor distinto porque quizás otra CPU lo cambió.
• Si se sincronizan correctamente una CPU escribe y la otra lee.
• Por lo general los sistemas operativos realizan tareas regulares cómo lo son:
  • Manejo de system calls
  • Administración de memoria
  • Administración de E/S
• Características particulares:
  • Sincronización de procesos
  • Administración de recursos
  • Planificación de CPU

Hardware

Cada procesador puede direccionar toda la memoria. Dependiendo del procesador y de la velocidad de acceso a la memoria los podemos clasificar en UMA o NUMA

UMA (Uniform memory access)

Los multiprocesadores más simples se basan en un sólo bus para comunicarse con la memoria. Antes de acceder al bus, se debe comprobar que el mismo no esté ocupado. A medida que aumenta la capacidad de CPU, el acceso a la memoria se torna más ineficiente. La principal limitación es el ancho de banda del bus y se tiene mucho tiempo ocioso.

Una evolución es agregar una caché a cada CPU, de ésta manera el acceso al bus compartido se reduce. Si el bloque se almacena en la caché en modo RO (read only), pueden estar en varias caché, pero si se almacena en modo RW (read write) sólo pueden residir en una caché. Aparecen mecanismos de protección para evitar datos sucios, copias limpias vs copias sucias.

Otra alternativa es asignar a cada CPU un área de memoria local que es accedida por un bus dedicado (caché + memoria privada), de ésta manera la memoria compartida sólo se usaría para escribir variables compartidas. Se reduce el uso del bus pero requiere de una asistencia activa por parte del compilador.

Otras arquitecturas:

Inclusive con el agregado de caché, un único bus limita a 16 o 32 CPU aproximadamente.

Por eso para lograr mejor performance se necesita otro esquema de interconexión, cómo por ejemplo las redes de conmutación multi-etapa, que puede verse cómo una especie de grafo dirigido de caminos que puede comunicar cada CPU con un módulo de memoria por un camino independiente. Cada nodo es un conmutador con 2 entradas y 2 salidas. Tanto los interruptores de barras cruzadas cómo las redes multietapas tienen cómo finalidad presentar circuitos que permitan la comunicación de varias CPU con varios módulos de memoria.

Los procesadore y técnicas anteriores tienen la característica de ser poco escalables y muy costosos.

NUMA (Non uniform memory access)

Permiten escalar en números de CPU. Se posee un único espacio de memoria visible por todas las CPU. El acceso a memoria remota es más lento que el acceso a memoria local ya que se requiere acceso a un bus compartido. El rendimiento es menor que en máquinas UMA pero es menos costoso.

Se puede implementar mecanismos de caché para acelerar los tiempos de acceso a la memoria. Cuando no hay caché al sistema se lo llama Nc-numa (no cache numa), cuando hay caché se lo lama cc-numa (cache coherent numa).

En el uso de cc-numa es importante mantener una coherencia en las cachés. El método más común para construir grandes procesadores basados en ésta tecnología es el multiprocesador basado en directorios que mantiene una BD que indica donde está cada línea y su estado (limpia o sucia (modificada)). Una dirección de memoria debe traducirse en nodo+línea+desplazamiento.

Chips multinúcleo:

A medida que la tecnología avanza, los transistores se hacen más pequeños y aparece la posibilidad de agregar más de uno a un chip.

Al tener más transistores se pueden:
- Agregar más memoria caché (pero la tasa de aciertos no se incrementa demasiado),

-Agregar más velocidad de clock a una CPU (sigue existiendo un único hilo de ejecución)

-Agregar más CPU al mismo chip, los que podrían compartir la caché y la memoria principal (se logra paralelismo)

Es importante que el software se diseñe teniendo en cuenta los aspectos del hardware para aprovecharlo al máximo.

Software

Existen diversas metodologías posibles para la administración en esquemas multiprocesadores desde el lado del software.

Cada CPU con su SO.

• Se comparte el código de SO.
• Copia privada de los datos del SO para cada CPU.
• Cada CPU atrapa las SysCalls de sus procesos.
• Cada CPU cuenta con su propio conjunto de procesos (desbalance en la carga de trabajo)
• No se puede compartir páginas (Pasaje de mensajes, memoria desperdiciada)
• Caché de disco, cada CPU tiene su propia copia (inconsistencia de la información)

Maestro-Esclavo

• Única copia del SO y de su información.
• Todas las SysCalls se redirigen a una CPU, la cual pueden ejecutar procesos si ‘le sobra tiempo’.
• Resuelve los problemas del modelo anterior. Se mantiene una única cola de listos, cuando una CPU está libre pide un proceso al master, y se puede asignar las páginas entre todos los procesos de manera dinámica.
• El problema es que con muchas CPU hay un cuello de botella en el maestro. Por ej. si el 10% del tiempo se atienden syscalls, con 10 CPU el master se saturaría y con 11 estaría sobrecargado.

SMP - Multiprocesadores Simétricos

• Soluciona el inconveniente de saturación de una única CPU.
• Una única copia del SO en memoria y cualquier CPU puede ejecutarlo.
• Equilibrio entre procesos y memoria, ya que sólo hay un único conjunto de tablas del SO.
• No hay cuello de botella, ya que no hay una CPU master.

Problemas:

• 2 o más CPU ejecutando código en un mismo instante de tiempo.
• 2 CPU seleccionando el mismo proceso para ejecutar, o seleccionan la misma página de la memoria libre.

Posibles soluciones:

• Utilizar locks para las estructuras del SO: Considerar a todo el SO cómo una gran sección crítica de manera que cualquier CPU pueda ejecutar el SO pero sólo una a la vez. Se comportaría cómo el modelo maestro-esclavo. Este modelo es poco utilizado debido a la mala performance que provee.
• Locks por estructura: existen varias secciones críticas independientes cada una protegida por su propio mutex. Mejora el rendimiento pero es difícil determinar cada sección crítica. Ciertas estructuras pueden pertenecer a más de una sección crítica, lo cual ante bloqueos podría generar deadlocks. Es el esquema que generalmente se utiliza.

Sincronización de multiprocesadores:

Es necesario que las CPU de un multiprocesador se encuentren sincronizadas (acceso a regiones críticas, estructuras, etc.)

En entornos uniprocesador basta con deshabilitar las interrupciones mientras se ejecuta la sección crítica, en cambio en sistemas multiprocesadores, se deshabilitan las interrupciones de una CPU pero podría generarlas otra. Surge la necesidad de contar con un protocolo de mutex apropiado para garantizar la exclusión mutua.

Multicomputadora con paso de mensajes:

Varios pares de CPU-memoria se conectan a una interconexión de alta velocidad mandando mensajes, y cada memoria es local para una sola CPU y puede ser usada sólo por esa CPU. Son más sencillas de fabricar pero más difíciles de programar. Se los conoce cómo fuertemente acoplado ya que una tarea se inicia y deseablemente debe terminar de ejecutarse en la misma CPU. 10 a 50 μseg

Sistemas distribuidos:

Conecta sistemas de cómputos completos a través de una red. Cada sistema tiene su propia memoria y se comunican mediante el paso de mensajes. Se los conoce cómo sistemas débilmente acoplados. 10 a 100 mseg