Subsecciones

2.3 ARQUITECTURAS

En este tema se tratarán tanto las arquitecturas hardware como software que se han desarrollado para conseguir hacer trabajo paralelo o distribuido. Estas arquitecturas fueron inventadas para superar los problemas de rendimiento y responden a distintos enfoques para conseguir sacar más rendimiento gracias al paralelismo. Algunas arquitcturas pretenden tener una mejor relación velocidad/precio y otras ser las máquinas más rápidas del mercado.

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.

2.3.1 Soluciones hardware

Las soluciones hardware han estado en el mercado de la computación desde sus inicios. Para muchas empresas la única manera de crear mejores máquinas era crear arquitecturas paralelas a partir de las que ya poseían.

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:

Se irá viendo cómo se explota el paralelismo en el hardware a varios niveles: desde lo más pequeño (procesadores) hasta lo más grande (multicomputadores).

SISD

Un procesador se dice superescalar cuando acepta varias instrucciones a la vez, por tanto se ejecutan a la vez. Todo microprocesador destinado a computadores actuales es superescalar, para que un microprocesador sea superescalar necesita tener redundancia de unidades funcionales, esto no se debe confundir con los computadores SIMD. Estas CPUs pueden realmente ejecutar N instrucciones a la vez (son superescalar es grado N) solamente si no hubiera dependencia entre los datos. Hay tres formas en las que podemos ejecutar las varias instrucciones simultáneas:

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 parones2.14 podremos recurrir a:

Usando estas técnicas eficientemente, en ausencia de dependencia de datos y otro tipo de parones, es cuando se consigue el auténtico paralelismo en computadores superescalares. Estas técnicas se suelen dar a dos niveles: Un procesador se dice segmentado cuando tiene sus funciones divididas en varias subfunciones que se realizan de forma independiente y que pueden ejecutarse simultáneamente2.16. Si todo el procesador actuara como un bloque, solo se podría ejecutar una sola instrucción a la vez que tardase M ciclos, N instrucciones tardarían N*M ciclos. En un ciclo sin parones pueden ejecutarse N instrucciones en M +(N-1)M/k ciclos siendo k el número de etapas. Por tanto cuantas más etapas más trabajo paralelo se realiza y más velocidad se obtiene.

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 [*].

Tabla: Arquitecturas. Procesador dividido en 4 etapas y sin dependencias
  Tiempo 1 Tiempo 2 Tiempo 3 Tiempo 4 Tiempo 5 Tiempo 6
Subfunción 1 Instr 1 Instr 2 Instr 3 Instr 4 Instr 5 Instr 6
Subfunción 2   Instr 1 Instr 2 Instr 3 Instr 4 Instr 5
Subfunción 3     Instr 1 Instr 2 Instr 3 Instr 4
Subfunción 4       Instr 1 Instr 2 Instr 3
Resultados         Result 1 Result 2


Si se ejecutaran a la vez tantas instrucciones como subfunciones tuviera podría realizarse una instrucción por ciclo. Como ejemplo, las 3 unidades de punto flotantes que se han visto en un ejemplo anterior del K7 están divididas en 15 etapas.

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 [*]).

Tabla: Arquitecturas. Inferioridad del procesador P4 frente a K7
Instrucción ciclos en P4 ciclos en K7
FADD 1 1
FMUL 2 1
FDIV float 23 13
FDIV double 38 17
FSQRT float 23 16
FSQRT double 38 24


Para los amantes de las mejores arquitecturas aquí se da una buena razón para inclinar la balanza hacia los de Advanced Micro Devices. La diferencia entre ciclos por instrucción sería mucho mayor al incluir en el cuadro una arquitectura PPC de Apple: éstas llegan a ser competitivas aún funcionando a 800MHz en unos tiempos donde los P4 llegan ya los 3GHz.

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

Los computadores SIMD son bastante menos frecuentes que los SISD eso se debe a que su programación es bastante más compleja. Un computador SIMD está compuesto de una serie de unidades de ejecución, unos módulos de memoria y una red de interconexión. Gracias a las conexiones cualquier elemento de proceso puede acceder a cualquier módulo de memoria. El paralelismo se consigue ejecutando la misma instrucción sobre varios datos a la vez (cada elemento de proceso un dato). Aquí es donde se complica la programación pues antes de ejecutar la instrucción debe especificar dónde se encuentra los datos en memoria y la configuración de la red de conexión en cada instante.

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

Pueden distinguirse multiprocesadores y multicomputadores.

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).

Los sistema UMA a su vez pueden ser de dos tipos dependiendo de la red de interconexión. Así en los multiprocesadores en bus (los procesadores comparten buses de dirección, datos y control) existe un árbitro en este bus que es quien decide quien puede en cada momento acceder a los buses. El problema de esta arquitectura es que los buses se saturan con facilidad, a partir de 64 CPUs el bus es el cuello de botella y aumentar el número de CPUs no aumenta el rendimiento.
Figura: Arquitecturas. Multiprocesadores en bus
Image bus_local
Los multiprocesadores con conmutador són la solución para los problemas que conlleva el bus y, evidentemente, es una arquitectura más cara. La memoria se divide en módulos, varios procesadores pueden acceder a memoria de forma simultánea. Las CPUs y las memorias están conectadas a través de puntos de cruce. Si dos procesadores quieren acceder simultáneamente a la misma memoria, tendrán que esperar, en cualquier otro caso el acceso se hace de forma simultánea. El problema que conlleva esta arquitectura es que el número de conmutadores es alto NxM (si N es el número de procesadores y M el número de módulos de memoria) además estos conmutadores son caros pues tienen que ser de alta tecnología para que no se haga más lento el acceso a la memoria.
Figura: Arquitecturas. Multiprocesadores en conmutador
Image mimd
Para solucionar estos problemas se creó la red Omega que tiene un número menor de conmutadores. Pero en esta red, y por tener menos elementos de conmutación, ocurren más esperas que en una red de barras como la anterior, aunque menos que en una estructura en bus. Para solucionar todos estos es para lo que se creó la estructura NUMA, pero esta estructura necesita algoritmos complejos.
Figura: Arquitecturas. Red Omega
Image red_omega
Un problema que estos sistemas MIMD tienen que solventar es la coherencia de las memorias cache. Las memorias cache de cada procesador guardan los datos que este está accediendo más frecuentemente. En la ejecución normal de un procesador se leen los datos de memoria y se dejan en memoria cache, las próximas lecturas o escrituras se realizan en ella ahorrando tener que ir a memoria principal. El problema ocurre con las escritura en estos datos. Pongamos un ejemplo:
  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.
Se podría pensar que la solución sería no permitir memoria compartida o tener un mecanismo para controlar la situación en ese tipo de memoria, no obstante hay que tener en cuenta que también puede ocurrir el caso de que un proceso corriendo en el procesador 1 lea las variables propias (que pueden ser privadas), entonces se mueve al procesador 2 donde escribe en esas variables. Cuando vuelve a migrar al procesador 1 las variables que el proceso piensa que escribió (la migración es transparente al proceso) no están escritas.

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.

Entre las soluciones más implantadas en multiprocesadores con sistema de memoria basado en bus se encuentran los protocolos de snoopy: los procesadores se mantienen a la escucha de lo que ocurre en los distintos bloques de cache. Ya que el problema ocurre cuando se escribe un dato en la cache, cuando se escribe uno hay dos posibilidades: A nivel de máquina se han desarrollado otros sistemas para conseguir paralelizar todo tipo de tareas a todos los niveles. El primero de ellos son las IRQs lo que permiten al procesador estar ejecutando programas a la vez que los periféricos están ejecutando sus funciones. Este es un paralelismo a nivel de máquina que permite que se lleve la cuenta del reloj a la vez que se acepta una pulsación de una tecla a la vez que el procesador está haciendo algún proceso pesado.

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:

2.3.2 Soluciones software

Una vez que el hardware obtuvo la potencia suficiente se empezó a explotar el paralelismo a nivel de software, en el capítulo sobre sistemas operativos se verá cómo se comenzó dividiendo el tiempo de CPU entre varios procesos, esto permitía una mayor eficiencia e interacción entre usuarios y máquinas. Con la llegada de las IRQ el sistema operativo tuvo que gestionarlas, teniendo así la responsabilidad de mantener todos los periféricos trabajando a la vez el máximo tiempo posible.

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.


miKeL a.k.a.mc2 2004-09-06