El manual para el clustering con openMosix - Arquitecturas

Las soluciones hardware fueron las primeras en aparecer, las soluciones software tuvieron que esperar hasta que el hardware diese la potencia necesaria y en el caso de los sistemas distribuidos se tuvo que esperar a que en los años 70 se desarrollaran las redes de área local. En el capítulo Sistemas operativos se explicará con detalle el software distribuido a nivel de sistema operativo.

Soluciones hardware

Como el número de estos tipos de máquinas es elevado, existen numerosas y diversas soluciones. Quizás la división más conocida y básica sea la taxonomía de Flint. Flint dividió las soluciones hardware en cuatro categorías:

• SISD: un flujo de instrucciones único trabaja sobre un flujo de datos único, a esta categoría pertenecen las CPUs simples y las superescalares.

• SIMD: un flujo de instrucciones único trabaja sobre un flujo de datos múltiple, en esta categoría tenemos los computadores matriciales.

• MISD: un flujo de instrucciones múltiple trabaja sobre un flujo de datos único, resultado teórico de la clasificación, el modelo que más se acerca son los computadores sistólicos.

• MIMD: un flujo de instrucciones múltiple trabaja sobre un flujo de datos múltiple, estos son los multiprocesadores y multicomputadores.

SISD

• Emisión de instrucciones en orden con terminación en orden: según llegan las instrucciones se ejecutan, hay que parar el proceso en cada dependencia de una instrucción con la anterior. También las instrucciones más rápidas tienen que esperar a que terminen las instrucciones más lentas para mantenerse el orden de partida.

• Emisión en orden con terminación en desorden: las instrucciones pueden acabar en cualquier orden, evitando tener que esperar a las instrucciones lentas.

• Emisión en desorden con terminación en desorden: las instrucciones se emiten y acaban en cualquier orden, este es el método que consigue mayor rendimiento. Se necesita tomar decisiones sobre qué instrucción ejecutar primero de entre un buffer de instrucciones. Esta técnica hace tiempo que la vienen usando los compiladores para conseguir mayores optimizaciones de los programas.

El problema de los ordenadores superescalares está en los llamados parones de instrucciones. Los parones de instrucciones se producen por la dependencia que puede existir en instrucciones secuenciales. Estos parones son retardos, vienen dados cuando existe una dependencia entre dos instrucciones que están intentando usar un mismo registro para escribir datos o una instrucción que debe esperar a que otra actualiza un dato para leer de él. Para eliminar los parones^2.14 podremos recurrir a:

• Renombramiento de registros, esta técnica también viene siendo usada por compiladores hace tiempo y varias arquitecturas la soportan, por ejemplo los R10000 tienen 64 registros para renombramiento.
• Adelantamiento de datos a nivel de unidades funcionales, hacemos que no tenga que esperarse que el dato se almacene en un lugar determinado para que esté disponible.
• Predicción de saltos, desde las las sencillas hasta las de nivel 2 o las de predicción por trazas del Pentium4.

• Nivel de procesador.

  Son los procesadores con planificación dinámica. El procesador lee las instrucciones secuencialmente, decide qué instrucciones pueden ser ejecutadas en un mismo ciclo de reloj y las envía a las unidades funcionales correspondientes para ejecutarse. El problema de esta solución es que carga al procesador de trabajo y el circuito electrónico para implementarlo requiere muchos transistores. Por ejemplo el procesador AMD K7 tiene un planificador con 36 entradas para las operaciones de punto flotante, con esas 36 entradas toma las decisiones oportunas para rellenar un registro de 88 entradas que son la cola que espera para que las 3 unidades de ejecución totalmente independientes del K7 las ejecuten. En este ejemplo se ve la complejidad del hardware necesario.

• Nivel de compilador. La máquina VLIW.

  Un procesador VLIW deja al compilador hacer todo el trabajo de decisión. El compilador VLIW agrupa las instrucciones en paquetes de una cierta longitud y los envía al procesador. Las decisiones se toman una sola vez en tiempo de compilación y no cada vez en tiempo de ejecución. El problema es que al tener que enviar paquetes de instrucciones fijos (y por otros trucos) se necesita enviar instrucciones NOPS^2.15 para rellenar los huecos vacíos. Como ejemplo la arquitectura MAJC de Sun dispone de cuatro unidades de ejecución totalmente independientes que no saben nada de los tipos de datos, esto quiere decir que pueden realizar cualquier tipo de operaciones por lo que cuando se ejecuta un programa de un solo tipo de operación (por ejemplo coma flotante) no se están desaprovechando las unidades que no se encargan de ese tipo (enteros). Eso permitirá a este procesador un máximo uso de su cauce.

Así por ejemplo un procesador dividido en 4 etapas sin dependencias de datos y empezando por la primera instrucción se ve como en el cuadro .

Seguidamente se muestran unos datos sobre como esta división en tantas etapas permiten a los K7 hacer las operaciones en menos ciclos por instrucción que a los Pentium4, que están divididos en menos etapas (ver cuadro ).

La solución mixta de los dos anteriores es un procesador segmentado superescalar. En este procesador entran varias instrucciones a la vez que se ejecutan en cada una de las subfunciones, así se están ejecutando a la vez M*N instrucciones siendo M y N los grados de segmentación y escalabilidad del procesador. Si en el cuadro se añadiese la capacidad de ser superescalar en cada casilla cabrían N instrucciones, así donde antes había instrucción 1 ahora habría instrucción 1 ... instrucción N. Asimismo en instrucción 2 habría instrucción N+1 ... instrucción 2N, etc.

SIMD

Aunque se han intentado construir máquinas SIMD puras no han tenido demasiado éxito, no eran suficientemente flexibles y poco eficientes para algunas operaciones (por ejemplo operaciones condicionales). Hoy en día lo que se desarrollan son extensiones vectoriales de procesadores SISD, como ejemplos tenemos AltiVec de Motorola, MMX de Intel o 3DNow de AMD.

Motorola ha apostado por añadir más hardware: 32 registros de 128 bits para operaciones vectoriales. Dos unidades de ejecución independientes (una ALU vectorial y otra para permutaciones), puede mantener una operación por ciclo siempre que encuentre los datos en la cache de nivel 1.

El MMX de Intel en cambio usa registros de 64 bits que ya existían (registros del coprocesador para punto flotante) y añadió 57 instrucciones. Con SSE anteriormente conocida como MMX2 se añadieron 8 registros nuevos de 128 bits y una unidad independiente de suma vectorial. También hay una unidad de coma flotante vectorial pero comparte parte de su pipeline con la unidad de ejecución de coma flotante corriente. Cuando se quiere hacer una operación de 128 bits, se dividen en dos y se envían a las unidades de suma y multiplicación por lo que no siempre se obtiene una instrucción por ciclo, pero permite a Intel mantener sus buses internos del procesador a 64 bits.

3DNow implementa MMX, SSE y SSE2 de la misma manera que Intel y añade sus propias instrucciones para las que no pone registros nuevos (pero tiene registros ocultos al programador, para hacer renombramiento), no permite realizar operaciones de 128 bits pero a cambio las unidades de coma flotante son totalmente independientes.

El problema de estas nuevas instrucciones es el mismo que tuvieron las máquinas SIMD: són más difíciles de programar. Hoy en día se usan mucho los lenguajes de alto nivel por lo tanto se deja la optimización y vectorización de los datos a los compiladores.

Como curiosidad, notar que el compilador de Intel, que es capaz de vectorizar aproximadamente la mitad de los bucles de un programa y que usa SSE2 para tantas operaciones en punto flotante como puede, aumenta los rendimientos por encima de los del procesador AMD K7 en instrucciones como FADD, FMUL y FSQRT. Tras ver el cuadro 2 se comprueba como realmente el AMD K7 es más potente en lo que se refiere a operaciones en coma flotante, no obstante por el momento no dispone de compilador específico en el mercado, esto lo pone en posición desfavorable frente al P4 dentro del uso del paralismo.

MIMD

Un sistema multiprocesador consta de muchos procesadores independientes unidos por algún mecanismo entre ellos y la memoria. La primera consideración que se hace al desarrollar un sistema multiprocesador es cómo conectar los procesadores entre sí y éstos a la memoria. Los procesadores deben estar conectados o al menos tener una zona de memoria común, pues están haciendo un trabajo cooperativo.

Según el tipo de acceso a memoria de todos los procesadores de la máquina MIMD se caracterizan en dos tipos, que son: UMA (acceso uniforme a memoria) y NUMA (accesso no uniforme a memoria).

• UMA significa que todos los procesadores acceden a la misma memoria a la misma velocidad, por ejemplo un sistema SMP es UMA, Por ejemplo los compatibles con x86 tienen una arquitectura con la memoria compartida, global para todos los procesadores, con un solo bus para acceder a memoria que comparten todos los procesadores.
• NUMA significa que no los procesadores no pueden acceder a toda la memoria con la misma velocidad. Habrá zonas de memoria a la que se accede más rápido y zonas a las que se accede a menos velocidad. Los procesadores tienen conexión directa con una memoria local, pero también tienen una conexión más lenta a memorias locales de otros procesadores (la memoria local no es memoria cache).

Figura: Arquitecturas. Multiprocesadores en bus

Figura: Arquitecturas. Multiprocesadores en conmutador

Figura: Arquitecturas. Red Omega

1. la CPU 1 lee de memoria la variable varGlobal.
2. la CPU 2 lee de memoria la misma variable.
3. la CPU 1 y la CPU 2 escriben en su copia local de cache un valor.
4. Cuando esos valores se actualizen en memoria (depende de si la cache es de postescritura o escritura directa) estaremos ante una condición de carrera. Además el valor escrito por un procesador no se ha propagado a los demás procesadores que están trabajando con un valor antiguo.

Para evitar estas situaciones se han desarrollado una serie de técnicas. La primera de ellas es dividir la memoria principal y dejar parte de esa memoria como memoria local. Sólo se pasarían a cache los datos de esa memoria local y esto plantea bastantes problemas (copiar datos de la memoria global a la local, perdemos eficiencia en accesos a memoria compartida) y seguramente por esta razón no es una solución amplamente usada.

Tener la cache compartida por los procesadores implicaría una velocidad de bus muy elevada, no se implementa en la práctica por sus costes económicos.

Existen las cache privadas con directorio compartido donde se guarda el estado de cada uno de los datos, gracias a esta información se implementa un algoritmo que mantiene la cache coherentes. Se implementa en sistemas con multiprocesadores con redes de conexión (no en bus). Existen varios protocolos que se diferencian en la información que guardan referida a los bloques de memoria y como se mantiene esa información.

• Directorios completos.

  El directorio tiene un bit de procesador que indica si el bloque está o no en la cache del procesador y un bit de modificado si ha sido modificado, si ha sido modificado, sólo está en ese procesador y sólo él tiene permiso para modificarlo. También hay 2 bits por cada bloque de la memoria cache, uno indica si ese bloque es válido o no y el otro indica si se puede escribir en él.

• Directorios limitados.

  Cuando el número de procesadores es muy alto, la solución anterior requiere mucha memoria, para disminuir esta necesidad se usan directorios limitados que siguiendo el mismo esquema, imponen un límite al número de procesadores. Si se solicita el bloque en más cache de las que entradas tiene el directorio se aplica un algoritmo de reemplazo. El directorio debe especificar el procesador porque ahora no sabemos como antes que bits indican que procesadores.

• Directorios encadenados.

  El directorio sólo indica el primer procesador que tiene el bloque, este procesador indica el siguiente creando una cadena, hasta encontrar el procesador que tiene el bit que indica final de cadena activado.

• Invalidar el dato de todas las demás cache cuando uno de los procesadores escribe en su cache ese mismo dato. El problema de esta solución es que puede ocurrir que un dato sea muy utilizado y se tenga que estar cogiendo de memoria constantemente pues fue invalidado.

• Actualizar los datos de los demás procesadores cuando modificamos un bloque, el problema de esta aproximación es que se puede generar mucho tráfico y el bus tiene que ser rápido.

Tras las IRQs se implantó el DMA, esto es un chip especial dentro de la placa del ordenador que permite ser programado para que un periférico haga accesos a un bloque de memoria sin intervención de la CPU, esto permite mayor autonomía de los periféricos que ejecutan más funciones sin interrumpir a la CPU, con un bus compartido no podrán acceder más de un periférico a la vez a memoria.

Los sistemas multiprocesadores actuales están consiguiendo mejores políticas de gestión por parte del sistema operativo.

Para poner un ejemplo de hacia donde se dirigen las nuevas capacidades de los procesadores para trabajar en paralelo se presenta el caso del procesador MAJC de Sun.

MAJC es capaz de, cuando está en una configuración multiprocesador y detecta que en el thread actual se ha llegado a un bucle del que se tardará en salir, producir de manera especulativa (al igual que se realizan instrucciones) un nuevo thread que se ejecuta en otro procesador ejecutando las posibles instrucciones futuras en tiempo presente, a esto lo llaman STC (computación espacio temporal).

MAJC implementa también vertical multithreading. Así cuando un thread tiene un fallo de cache y tiene que ir a memoria a por el dato se hace un cambio de contexto y se ejecuta otro thread hasta que el dato ha llegado. Esto es posible porque mucho espacio del procesador MAJC se gasta en registros y es capaz de mantener la información de estado necesaria para hacer el cambio de contexto entre dos threads en ellos, con lo que el cambio de contexto es el más rápido que puede implementarse actualmente y da tiempo a ejecutar instrucciones antes de que el dato de memoria haya llegado.

Multicomputadores:

Ya se vió en el tema de introducción cómo aparecieron y evolucionaron estos sistemas. Es una arquitectura MIMD donde cada uno de los procesadores puede tener a su vez varios procesadores. En este apartado lo que antes era un procesador ahora será un ordenador entero. Cada uno tiene acceso directo a su memoria local. Entonces es la misma arquitectura que en multiprocesadores pero escalada. También aquí se puede tener una arquitectura en bus u otro tipo, podrán aplicarse exactamente las mismas explicaciones sobre arquitecturas de las que hablamos en multiprocesadores, solo se varía el esquema levemente:

• Bus: por ejemplo una red de ordenadores conectados a través de una LAN se adapta a este esquema. Las velocidades de transmisión son menores que en un sistema multiprocesador en base a buses y las latencias son mayores. Básicamente igual que su homólogo en multiprocesadores, excepto que esta arquitectura es NUMA (pues un ordenador accede a su memoria local mucho más rápidamente que a la memoria de otro ordenador), se usan algoritmos complejos para las operaciones con memoria.

• Conmutadores: ahora los conmutadores son los propios nodos, pues tienen la capacidad de conectarse a sus nodos vecinos (tienen tarjetas de red) se pueden dar en dos arquitecturas diferentes:
  1. Transputers: los ordenadores forman una retícula 2D. Cada nodo solo tiene que conectar con (como mucho) 4 nodos más en cualquier caso, esto es perfecto para escalar el cluster sin tener que añadir tarjetas de red a los nodos ya existentes. Nótese que no hay simetría pues los nodos en los bordes se conectan con menos nodos.
  2. Hipercubos: los ordenadores forman una retícula 3D. Es difícil de visualizar a partir del orden 4. Cada nodo se conecta a N nodos siendo N el grado del hipercubo. Es una configuración simétrica.

Soluciones software

Los sistemas operativos tienen la responsabilidad de utilizar eficientemente los mecanismos que le da el hardware para hacer trabajos paralelamente. Así por ejemplo en multiprocesadores es el sistema operativo quien tiene que distribuir los procesos por los procesadores de una forma que todos los procesadores estén ocupados. El kernel tiene que tener en cuenta que un proceso se ejecuta más eficientemente en un procesador donde se ejecutó recientemente, pues el procesador tiene en su cache datos de ese procesador, también tiene que tener en cuenta si todos los procesadores tienen acceso a entrada/salida o no. Por ejemplo Windows NT ha elegido una forma muy sencilla que es usar N-1 procesadores para los N-1 procesos más prioritarios y el último para el resto, el rendimiento de este esquema es más que discutible, pero desde luego es simple.

La evolución de las soluciones software ha seguido la misma que las soluciones hardware: hasta que el hardware no las soportaba las soluciones software no se hacían realmente eficientes. Así tradicionalmente todos los recursos de una máquina los ha gestionado el núcleo y éste se ha ido adaptando a las nuevas posibilidades, aunque siempre ha habido hardware de un nivel más alto que controlaba su propio funcionamiento, como grandes sistemas gestores de bases de datos.

Con la llegada de los multicomputadores, se plantearon nuevos retos, pero esta vez en vez de ser superados por los diseñadores de sistemas operativos, se vió como un problema de las aplicaciones. Quizás esto fue así porque cuando aparecieron las primeras redes no eran algo barato ni tan común, por eso se consideraba tan puntero el sistema operativo Unix al soportarlas. Tampoco se disponía de hardware barato y potente. Por lo tanto aunque el núcleo daba funcionalidades básicas (creación de procesos, comunicación, manejo de red) todo el problema se dejaba al espacio de usuario. Afortunadamente esta aproximación está cambiando y ya existen varios sistemas de ficheros enfocados a tener un sistema de ficheros único en todo el cluster, pero aún queda mucho por hacer.

Hoy en día una red es muy barata y están muy extendidas por lo tanto las aplicaciones que funcionan sobre ellas se han extendido en todas las áreas del software. Al principio estas aplicaciones eran muy básicas, eran poco más que los protocolos que implementaban (que para la época implementar el protocolo era un logro suficiente), poco a poco se fueron haciendo más complejas. Por aquel entonces Sun hacía mucho desarrollo e implementó algo que hasta la fecha está siendo muy utilizado: RPC. Este sistema permite una comunicación de dos máquinas, una de las máquinas ejecuta unos procedimientos de la otra máquina.