El manual para el clustering con openMosix - Paralelismo (II)

Límites en el hardware

Para lograrlo deben solucionar de la manera más apropiada posible retardos por dependencias^2.7. Generalmente esto se soluciona con renombramiento de registros (fase que puede o no hacer el compilador), lanzamiento de instrucciones fuera de orden, unidades superescalares y supervectoriales y algunas otras técnicas que se describirán sin ahondar en el capítulo dedicado a arquitecturas.

La granularidad del hardware es la instrucción máquina (o en lenguaje ensamblador). Esta unidad es la más fina que puede tratar. Existen gran variedad de mejoras de rendimiento a los límites que se imponen por el programa, estas mejoras se van incorporando en los procesadores de última generación. El problema es que esta solución puede resultar en muchos casos demasiado cara, sobretodo por la dificultad o tiempos de implementación. Además siempre se necesita cierta ayuda de parte del software, principalmente el compilador. Así aunque el Pentium4 tenga nuevas instrucciones vectoriales SSEII, no son prácticamente usadas por los compiladores actuales y el rendimiento de un P4 es bastante inferior al esperado. En cambio usando el compilador especialmente desarrollado por Intel, los mismos programas aprovechan las instrucciones vectoriales del procesador mucho mejor con lo que se consiguen programas mucho más rápidos.

Hoy en día es difícil ver programar en ensamblador para procesadores que no estén dedicados a tareas como dispositivos empotrados o de tiempo real, e incluso en estos este lenguaje se hace más raro cada dia. Por lo tanto las optimizaciones de uso de las nuevas capacidades de los procesadores tienen que venir de parte del compilador que es quien se encarga de trabajar a nivel más bajo que el programador.

Límites del software

Así pues a las fases de análisis, diseño e implementación hay que añadir una fase de paralelización, en la que se deberá tener en cuenta las necesidades del programa y del problema a resolver, así como de los medios de los que se disponen para poder hacer que el programa aumente el rendimiento a medida que aumenta la capacidad de procesamiento de sistema.

Existen otras muchas limitaciones además de la ley de Amdahl que afectan al desarrollo de aplicaciones paralelas, comenzando por el sistema elegido para paralelizar aplicaciones, hasta la granularidad del paralelismo (que a este nivel siempre será denominado paralelismo de grano grueso). Muchos de estos métodos son brevemente referenciados en el tema de sistemas distribuidos, otros son de una granularidad algo más fina, relativos a compiladores que preparán el código paralelizado para sistemas especiales.

Para ilustrar esto con un caso pueden suponerse dos compiladores diferentes para un mismo lenguaje. Un compilador inteligente frente a uno que no lo es tanto ante una misma entrada: un programa con una secuencia de divisiones con coma flotante, después unas sumas del mismo tipo y por último unas operaciones con enteros, todas sin dependencias entre sícurre que:

• El compilador relajado no las reordena con lo que si el procesador no tiene ordenación de instrucciones hará que las instrucciones de enteros, que seguramente tardan solamente 1 o 2, ciclos tengan que esperar a las instrucciones de división en coma flotante, operaciones que pueden tardar más de 30 ciclos. Mientras se hacen las divisiones en coma flotante no se están usando las unidades de suma de flotantes ni las de operaciones con enteros. Estos componentes del procesador permanecen ociosos mientras otros se usan intensivamente.
• En cambio el compilador inteligente primero podría ejecutar las instrucciones que más tiempo tardarán en ejecutarse, y después ejecutaría las instrucciones que usan otras unidades para que el procesador pueda estar procesando de forma paralela todos los datos, aprovechando al máximo su hardware. Por supuesto que esta misma operación (primero las operaciones que más tardan) si se realiza sobre las mismas unidades hace que el retardo medio de finalizar una instrucción aumente por lo que el compilador debe hacer las elecciones correctas si está intentando realizar una ordenación óptima.

Granularidad del paralelismo

1. Sistemas de granularidad fina.
   1. bucles
   2. sentencias
   En general se hace a nivel de instrucciones en ensamblador. Generalmente son explotados por sistemas hardware muy caros con los nodos o procesadores fuertemente acoplados. Es la granularidad más pequeña y basa prácticamente todo su funcionamiento en propiedades del hardware. El hardware puede ser suficientemente inteligente para que el programador no tenga que hacer mucho por soportar esta granularidad, por ejemplo el hardware puede aportar reordenamiento de instrucciones.

2. Sistemas de granularidad media.
   1. módulos
   2. rutinas
   3. tareas o procesos
   Dentro de estos sistemas se incluyen varios de los que se describirán más adelante, como pueden ser RPC, openMosix y otros, si bien estos mismos están entre el paralelismo de grano grueso y el paralelismo de grano medio. El paralelismo de grano medio en general es explotado por el programador o el compilador.
   Dentro de él también se encuentran diversas librerías como pueden ser PVM o MPI. El hardware normalmente también se prepara para poder aprovechar este tipo de paralelismo, por ejemplo, los procesadores pueden disponer de instrucciones especiales para ayudar en el cambio de una tarea a otra que realiza el sistema operativo.

3. Sistemas de granularidad gruesa.
   1. trabajos o programas
   2. módulos o procesos
   El paralelismo de grano grueso es el que explota el programador mediante programas que no tienen por qué requerir la utilización de ninguna librería externa, sino solamente el uso de conocimientos de programación para paralelizar un algoritmo. Se basa principalmente en cualquier tipo de medio que utilice el programador para crear un programa, que solucione un problema de manera paralela, sin tener por que hacer uso más que de su habilidad de programador y de un buen algoritmo. Son los más limitados al carecer de métodos específicos para comunicación entre nodos o procesadores, se dan en sistemas muy débilmente acoplados.

Una vez vistos los tipos de granularidades existentes podemos catalogar algunos de los sistemas que vamos a tratar a lo largo de este documento. Para empezar cabe señalar que mayormente se tratará del estudio de sistemas distribuidos y clusters, esto implica que el sistema está compuesto por diversas máquinas con un sistema operativo que puede hacer el sistema más acoplado o no. El software de cluster en el que se particulariza es openMosix, como se explicará con mucho más detalle. La granularidad de openMosix está en los procesos, es decir, podemos paralelizar procesos y hacer que estos se ejecuten en nodos distintos. De hecho openMosix se encarga de balancear la carga de los nodos de modo que la carga global del sistema permanezca homogéneamente distribuida. Este tipo de granularidad es del tipo medio, si bien puede ser confundida con la de grano grueso (el límite siempre esta bastante difuso). Otros sistemas como pueden ser RPC, MPI, PVM o clusters Beowulf se acercan más al paralelismo de grano grueso.

El problema de la transparencia

1. Modelo de programación explícita.

   En el que se requiere una biblioteca de funciones especiales que se encargan tanto de realizar la comunicación como los métodos de migración y demás factores que en un principio^2.8 no debe afectar al programador, el cual debe abstraerse de esta capa. Este tipo de modelo es el que utiliza RPC, MPI o PVM. Requiere un conocimiento especial de dichas bibliotecas, lo que limita la velocidad de desarrollo del software y además lo hace más costoso debido al tiempo que se debe gastar en el conocimiento de las funciones.

2. Modelo de programación implícita.

   Es un modelo quizá más atractivo. Basa todo su funcionamiento en que el programador sepa lo mínimo del sistema para paralelizar sus procesos. Generalmente este modelo lo explotan los compiladores especiales de un sistema particular.

   Por otro lado se suele depender de macros o funciones especiales que delimitan la granularidad de los procesos a migrar. Un caso especial de este tipo es openMosix: la programación y migración de procesos en openMosix no requiere de conocimiento del usuario respecto al cluster de máquinas. Lo ideal para obtener transparencia en la programación será programar de manera completamente implícita y que al mismo tiempo el sistema implantado fuese lo menos intrusivo posible en lo que se refiere a comportamiento con el usuario final.

Para que un sistema fuese realmente transparente y al mismo tiempo suficientemente eficiente, en lo que se refiere a programación paralela, el programador debería conocer a fondo la programación del sistema, i.e. las habituales llamadas de creación de memoria, librerías estándar, o basadas en las estándar, llamadas a sistema y demás herramientas habituales de la programación. Por otro lado, el compilador o el sistema se deberían encargar de efectuar todas aquellas tareas que de manera habitual se hacen en los sistemas que actualmente existen, es decir, la comunicación entre procesos, la localización de dichos procesos, rutinas o tareas, la paralelización del código del programa y demás tareas. Así el programador no tendría que preocuparse de los detalles y se podrían hacer desarrollos más rápidos y baratos.

Lamentablemente dicho sistema no existe. La explotación de los sistemas distribuidos de momento requiere un gran conocimiento del sistema en el que se trabaja por parte del programador. De hecho, las optimizaciones de los algoritmos se basan en gran medida no en cómo de bueno es el modelo del algoritmo, sino en las capacidades especiales de cada sistema.

Es decir, cada sistema especial como puede ser Beowulf, PVM u openMosix tienen puntos fuertes y puntos débiles en lo que se refiere a la programación, y es mediante el conocimiento de estas características de la manera que se pueden optimizar programas paralelos. Un ejemplo de esto puede encontrarse en aplicaciones que requieren comunicación entre procesos. El caso de openMosix, como se verá más detalladamente, es el caso de uno de los sistemas que poco a poco ha pretendido ser un sistema lo mas transparente posible y que basa toda su granularidad del paralelismo en el proceso. Las aplicaciones diseñadas para ejecutarse en openMosix contienen procesos que se ejecutan de manera independiente y que de una manera u otra se deben comunicar de manera transparente con otros procesos. Estos procesos pueden estar en el nodo local donde se ejecutaron o en otros nodos, lo cual complica la cosa, ya que la relación que une a un proceso con otro puede ser un pipe con nombre y sin embargo estar los procesos en dos nodos distintos.

Imagínese el típico caso de la multiplicación de una matriz. Se supone que el caso ideal para openMosix sería utilizar memoria compartida para las matrices y dejar que el sistema haga todo de la manera más efectiva posible. Sin embargo openMosix no implementa en las versiones actuales^2.9 un manejo eficiente de la memoria compartida y por tanto se deben buscar otros mecanismos de programación para aprovechar al máximo la utilización del sistema.

Otro posible ejemplo sería el de PVM. Supóngase el caso de determinadas tareas con uso de CPU intensiva que se sitúan en unos nodos concretos antes de empezar su ejecución. Supóngase también que el tiempo de ejecución de dichas tareas es en muchos casos aleatorio, y por tanto, el sistema tendrá muchos nodos altamente cargados y otros poco cargados. Como PVM no posee de la capacidad de balanceo automático de carga que tiene openMosix se estará desaprovechando la capacidad de cómputo del cluster en general y la tarea que se le encomendó tendrá que esperar hasta que el último de los nodos acabe con ella, mientras los demás nodos están ociosos y no pueden ayudar en su finalización. En cualquier caso la transparencia en los sistemas distribuidos y clusters que más se utilizan actualmente requiere de un conocimiento exhaustivo por parte del programador, lo que en muchos casos requiere un coste adicional^2.10.

Por otro lado está el problema de la intrusión en el código. En este caso se supondrá el caso ideal de haber conseguido un sistema realmente transparente a los ojos del programador, lo que implicaría que la mayoría de las aplicaciones necesitarían de una compilación especial o un compilador especial para el sistema en concreto, lo que hará las aplicaciones normales incompatibles con nuestro sistema, teniendo que compilar todas las aplicaciones de nuevo. En un principio se podría pensar que en el caso de el sistema operativo linux esto no sería problema más que para las distribuciones (aparte de algún programa de más bajo nivel que habría que rehacer).

El problema real está en lo intrusivo que puede llegar a ser un sistema de estas características, cuando los servicios distribuidos que se proveerían solamente serían apreciados por una pequeña parte de los usuarios del sistema operativo, seguramente por esto se crearía más antipatía que simpatía a estos cambios en el kernel.

Uno de estos casos ha sido el de Amnon Barak. Amnon Barak es el líder del proyecto Mosix. En una de las primeras implementaciones trató de hacer un sistema como el que se ha descrito, con el resultado de tener que implementar aproximadamente el 60% del kernel, más la reimplementación de las librerías necesarias para ejecutar los programas más habituales; esto sin tener en cuenta que todos los programas que eran afectados por dichas librerías debían de ser recompilados para poder ser utilizados. De esta manera se puede hacer notar que por el momento el tener un sistema transparente en lo que se refiere a la programación supone tener un sistema altamente intrusivo.