El manual para el clustering con openMosix - Clusters HP (I)

Conceptos importantes: migración y balanceo)

Los clusters HP están dedicados a dar el mayor rendimiento computacional posible y existen multitud de formas de implementarlos.

Ha llevado años implementarlos, por tanto a lo largo de la historia ha habido todo tipo de ideas para intentar hacerlos lo más eficientes posible. En este documento se estudian unas cuantas de estas implementaciones (PVM, MPI, Beowulf) y se ahondará en una de ellas: openMosix.

---

La primera división en las implementaciones puede ser la división entre las

• soluciones que funcionan a nivel de aplicación y
• soluciones que funcionan a nivel de kernel.

Las que funcionan a nivel de aplicación suelen tomar forma de librería. Se tienen que realizar los programas para que aprovechen esta librería por lo tanto cualquier programa ya existente para que pueda ser usado en un cluster y mejore su rendimiento tiene que ser reescrito al menos parcialmente.

Esto tiene bastantes inconvenientes: muchas de las aplicaciones que necesitan grandes tiempos de cómputo se realizaron hace décadas en lenguaje Fortran. Este lenguaje aparte de estar relegado hoy en día a aplicaciones matemáticas o físicas, puede llegar a ser bastante difícil de comprender; por lo tanto es bastante difícil migrarlo al nuevo entorno distribuido.

Por otro lado una de las ventajas que tienen los clusters HP con respecto a los supercomputadores es que son bastante más económicos. Pero si el dinero que se ahorra en el hardware hay que invertirlo en cambiar los programas esta solución no aporta beneficios que justifiquen tal migración de equipos. Además hay que tener en cuenta que la mayor parte de las instituciones o instalaciones domésticas no tienen dinero para invertir en ese software, pero que sí disponen de ordenadores en una red (universidades por ejemplo) .

La segunda opción es que el software que se encarga del HP se encuentre en el kernel del sistema operativo. En este caso no se necesitan cambiar las aplicaciones de usuario, sino que éstas usan las llamadas estándar del kernel por lo tanto el kernel internamente es el que se encarga de distribuir el trabajo de forma transparente a dicha aplicación. Esto tiene la ventaja de que no hace falta hacer un desembolso en cambiar las aplicaciones que lo necesitan y que cualquier aplicación puede ser distribuida. Por supuesto un factor que siempre habrá que tener en cuenta es la propia programación de la aplicación.

Por otro lado esta aproximación también tiene varios inconvenientes: el kernel se vuelve mucho más complejo y es más propenso a fallos. También hay que tener en cuenta que estas soluciones son específicas de un kernel, por lo que si las aplicaciones no están pensadas para ese sistema operativo habría que portarlas. Si los sistemas operativos tienen las mismas llamadas al sistema, siguiendo un estándar POSIX, no habría grandes problemas. Otros sistemas operativos propietarios que no cumplen estos estándares no pueden disponer de estas ventajas.

Una forma de conseguir HP es migrando procesos, dividiendo las aplicaciones grandes en procesos y ejecutando cada proceso en un nodo distinto. Lo que se quiere conseguir es el máximo uso de los recursos en todo momento, especialmente los procesadores. Para conseguirlo hay dos aproximaciones:

• Asignar estáticamente cada proceso a un nodo en particular.

En esta aproximación es importantísima la política de localización. Se elige estáticamente el nodo donde el proceso vivirá toda su vida. Por tanto es muy importante elegir correctamente estos nodos. Muchas veces esta solución necesita un administrador que decida dónde debe ir cada proceso. El caso más simple es tener todos los nodos con la misma potencia de cálculo y dividir el único programa al que se quiera dedicar los recursos en un número de procesos igual al número de nodos de los que se disponen. Asíse asignaría cada proceso a uno de los nodos. Hay que tener en cuenta que esta configuración es lejana a la normal y que ya que un fallo en el algoritmo de elección de nodo puede infrautilizar mucho de los recursos la configuración manual es normal en estos algoritmos. Esto no es tan malo como pueda parecer a primera vista porque es también muy corriente en estos casos que una vez hecha la configuración inicial, los procesos estén ejecutándose durante años si es necesario.

• Asignar dinámicamente procesos a los nodos.

Los procesos una vez iniciados en un nodo pueden migrar a otro nodo dinámicamente. En estos casos aunque es importante la política de localización para minimizar el gasto de recursos, también es importantísima la política de migración. Por supuesto también se pueden ubicar los procesos manualmente, con la ventaja de que se pueden ubicar en cualquier momento durante la vida del proceso. Si la política de migración es correcta y los procesos tienen una vida larga y se ha dividido correctamente la aplicación, debería haber al comienzo de la ejecución de los procesos un periodo de reordenación de los procesos, con varias migraciones, una vez el sistema llegara a una condición estable, no deberían producirse apenas migraciones hasta que los procesos finalizaran. Igual que ocurre en el caso anterior, esta configuración es lejana a la habitual, pero al contrario del caso anterior, aquíno es necesaria la configuración manual (si el algoritmo de migración es suficientemente bueno). Cuando se desbalancea el sistema éste se encarga de que se vuelva a balancear, de tal forma de que se aprovechen los recursos al máximo.

Sobre el balanceo ya se ha hablado en la sección anterior, como se puede comprender el correcto balanceo es muy complejo, se puede balancear con respecto a una variable (por ejemplo el procesador), pero hacerlo con respecto a todo el sistema en conjunto es algo demasiado complejo y el tiempo de cómputo para hacer las elecciones correctas sería muy grande. Por tanto estos algoritmos intentan tener un fundamento matemático fuerte que intenta minimizar el tiempo de cómputo. Muchos de estos sistemas usan fundamentos estadísticos, como por ejemplo openMosix.

Como ya se verá con más detalle, openMosix intenta maximizar el uso de todos los recursos. Intentar solamente balancear respecto al procesador puede dar lugar a decisiones bastante malas, porque se pueden enviar muchos procesos que no hagan mucho uso del procesador a uno de los nodos, si estos procesos están haciendo entrada/salida y son procesos grandes, es muy posible que el nodo empiece a hacer trashing pues se quedará sin memoria, con lo que los procesos no podrán ejecutar su función.

En el cuadro se aprecian las posibles formas que existen para clusters. Se muestra este cuadro para que se pueda comprender la cantidad de decisiones que se tienen que hacer cuando se implementa un cluster de este tipo y asíse comprenderá mejor por qué hay tantas implementaciones y tan dispares.


Tabla: Clusters HP. Aspectos de implementación|| || Tema || Problemas que genera || || Sin requisa de procesos || Mayor latencia para procesos de alta prioridad || || Con requisa de procesos || Sobrecarga, implementación compleja || || Balanceo estático || Mal balanceo de carga || || Balanceo dinámico || Sobrecarga, implementación compelja || || Nivel de aplicación || Sobrecarga, falta de información || || Nivel de kernel || Dificultad de implementación || || Nodos dedicados || Infrautilizción de recursos || || Nodos comparten espacio || Se encesita una plítica eficiente de localización || || Nodos comparten tiempo || Sobrecarga cambio de contexto || || Scheduling independiente || Pérdida de rendimiento || || Scheduling de grupo || Implementación compleja || || Con carga externa, quedarse || Pérdida de rendimiento en trabajos locales || || Ante carga externa, mgrar || Sobrecarga de migración, límites de migración || ||

Ya hemos explicado el balanceo estático frente a balanceo dinámico y el nivel de aplicación frente al nivel de sistema que serán conceptos que necesitemos en las próximas secciones, ahora vamos a explicar las demás características.

Requisa se refiere a poder parar el proceso y coger sus recursos (básicamente los registros del procesador y memoria). La requisa de los procesos puede existir o no. Con requisa no queremos decir hacer requisa de los procesos para migrarlos después, sino simplemente poder hacer requisa de un proceso en cualquier momento. Cuando un sistema es multitarea normalmente se implementa algún sistema de requisa para poder parar procesos y hacer que otros procesos tomen el procesador para dar la sensación al usuario de que todos los procesos se están ejecutando concurrentemente.

Si no se implementa requisa, un proceso de baja prioridad puede tomar el procesador y otro proceso de alta prioridad no podrá tomarlo hasta que el proceso de baja prioridad lo ceda a otros procesos. Este esquema puede ser injusto con las prioridades y un error en un programa, puede llegar a dejar sin funcionar la máquina pues nunca devolvería el control, pero tampoco haría ningún trabajo útil. Además para sistemas que necesitan tiempo real, simplemente es inaceptable que procesos de baja prioridad estén dejando a los procesos de tiempo real sin tiempo de procesador y quizás con esta latencia extra se esté haciendo que el sistema no pueda cumplir sus operaciones en tiempo real, haciendo que el sistema sea inútil. Hoy en día la requisa se implementa al menos a un nivel elemental en casi todos los sistemas que necesiten hacer funcionar más de un proceso (por no decir todos). Algunos sistemas lo que hacen es no esperar a que cumpla un temporizador y realizar la requisa sino a esperar que el proceso haga alguna llamada al sistema para aprovechar, tomar el procesador y cederlo a otro proceso. Esta aproximación sigue teniendo el problema de que si un proceso maligno o mal programado no hace llamadas a sistema porque haya quedado en un bucle, nunca se ejecutará nada en ese ambiente.

Si se implementa la requisa hay que tener en cuenta que la implementación más simple que se puede dar (que es la que usan buena parte de los sistemas) necesita un temporizador que marque cuando se acabó el tiempo del proceso y requisar ese proceso para asignar a otro proceso. Esto impone una sobre carga pues hay que tratar una interrupción, actualizar unas variables para saber cuanto tiempo lleva un proceso trabajando.

Hay una implementación más compleja que trata de que siempre que haya un proceso de una prioridad mayor al que se está ejecutando se quite el procesador al proceso y se dé el procesador al proceso con mayor prioridad. Estos suelen ser sistemas en tiempo real que también (ya que se ponen) pueden tener otras exigencias como unos tiempos mínimos de latencia para ciertos procesos. Para conseguir esto, el kernel no solamente tiene que requisar procesos de baja prioridad en favor de los procesos de tiempo real sino que tiene que ser capaz de requisar su propio código. Esto suele significar que casi cualquier porción del código del kernel se puede ejecutar entre dos instrucciones de este mismo código. Esto presenta muchísimos problemas a la hora de programar, hay que tener mucho más cuidado con evitar condiciones de carrera dentro del propio kernel que antes por ser código no requisable no se podían dar. Por tanto implementar requisa, puede hacer que un sistema sea tiempo real pero complica tremendamente el núcleo del sistema.

Las siguientes tres líneas en el cuadro tratan sobre los recursos del cluster, estos son los nodos. Existen tres modos en los que se puede dedicar los nodos del cluster, estos modos son:

• Modo dedicado.

En este modo que es el más simple de todos, solamente un trabajo está siendo ejecutado en el cluster en un tiempo dado, y como mucho un proceso de este trabajo que se está ejecutando es asignado a un nodo en cualquier momento en el que se siga ejecutando el trabajo. Este trabajo no liberará el cluster hasta que acabe completamente aunque solamente quede un proceso ejecutándose en un único nodo. Todos los recursos se dedican a este trabajo, como se puede comprender fácilmente esta forma de uso de un cluster puede llevar a una pérdida importante de potencia sobre todo si no todos los nodos acaban el trabajo al mismo tiempo.

• Modo de división en el espacio.

En este modo, varios trabajos pueden estar ejecutándose en particiones disjuntas del cluster que no son más que grupos de nodos. Otra vez como mucho un proceso puede estar asignado a un cluster en un momento dado. Las particiones están dedicadas a un trabajo, la interconexión y el sistema de entrada/salida puede estar compartidos por todos los trabajos, consiguiendo un mejor aprovechamiento de los recursos. Los grupos de nodos son estáticos y los programas necesitan un número específico de nodos para poder ejecutarse, esto lleva a dos conclusiones:

1. 1. Puede existir trabajos para los que no haya una división lo suficientemente grande por lo que non podrían ser ejecutados
   2. Puede tener un trabajo que solamente aproveche alguno de los nodos desperdiciando una división de gran cantidad de nodos. Para evitar este segundo punto se tienen que usar técnicas para elegir inteligentemente los nodos donde se ejecuten los trabajos, intentando minimizar el número de nodos ociosos.

También puede ocurrir que un trabajo muy largo tome los recursos del cluster evitando que otros trabajos más rápidos acaben, esto consigue aumentar la latencia.

• Modo de división en el tiempo.

En cada nodo pueden estar ejecutándose varios procesos a la vez por lo que se solucionan los problemas anteriores. Este es el modo más usado normalmente puesto que no tiene tantas restricciones como el otro y se puede intentar hacer un equilibrado de carga eligiendo correctamente los procesos.

Los dos siguientes puntos de la tabla tratan sobre scheduling, esta planifiación solo se da cuando el modo que se ha elegido es el modo de división en el tiempo.

Hay dos tipos de scheduling en cuanto a clusters se refiere:

• Scheduling independiente.

Es el caso más sencillo y más implementado, se usa un sistema operativo en cada nodo del cluster para hacer scheduling de los distintos procesos en un nodo tradicional, esto también es llamado scheduling local. Sin embargo, el rendimiento de los trabajos paralelos que esté llevando a cabo el cluster puede verse degradado en gran medida.
Cuando uno de los procesos del trabajo paralelo quiera hacer cualquier tipo de interacción con otro proceso por ejemplo sincronizarse con él, este proceso puede que no esté ejecutándose en esos momentos y puede que aún se tarde un tiempo (dependiente normalmente de su prioridad) hasta que se le ejecute por otro cuanto de tiempo. Esto quiere decir que el primer proceso tendrá que esperar y cuando el segundo proceso esté listo para interactuar quizás el primer proceso esté en swap y tenga que esperar a ser elegido otra vez para funcionar.

• Scheduling de grupo.

En este tipo se hace scheduling sobre todos los procesos del trabajo a la vez. Cuando uno de los procesos está activo, todos los procesos están activos. Estudios4.17 han demostrado que este tipo de scheduling puede aumentar el rendimiento en uno o dos puntos de magnitud. Los nodos del cluster no están perféctamente sincronizados. De hecho, la mayoría de los clusters son sistemas asíncronos, que no usan el mismo reloj.
Cuando decimos, a todos los procesos se le hace scheduling a la vez, no quiere decir que sea exáctamene a la vez. Según ese mismo estudio, según aumenta la diferencia entre que se elige para ejecutarse el primer proceso y el último, se pierda rendimiento (se tarda más en acabar el trabajo). Para conseguir buenos rendimientos se tiene que o bien, permitir a los procesos funcionar por mucho tiempo de forma continuada o bien que la diferencia entre que un proceso se ejecuta y el ultimo se ejecuta es muy pequeña.
Pero como se puede comprender, hacer scheduling en un cluster grande, siendo el scheduling una operación crítica y que tiene que estar optimizada al máximo es una operación bastante compleja de lograr, además se necesita la información de los nodos para poder tomar buenas decisiones, lo que acaba necesitando redes rápidas.

Las dos últimas filas tratan de que deben hacer los procesos cuando se encuentran que en su nodo local hay otros procesos que provienen de otros nodos. Estos pueden venir por alguna política de migración o porque se esté ejecutando el scheduler de grupo del que hemos hablado en el punto anterior. Los trabajos locales podrían tener prioridad sobre trabajos externos, por ejemplo los procesos de usuario interactivos donde no queremos que se degrade el rendimiento deben mantener mayor prioridad. Hay dos formas de tratar esta situación:

• El trabajo externo migra: si el proceso migra, existe el coste de migración pero el proceso puede ir a un nodo donde se ejecute de forma más eficiente.
• El trabajo externo se mantiene en el cluster: si el proceso se mantiene en el nodo donde se encuentra se evita la sobrecarga que conlleva la migración, para no afectar a los procesos de ese nodo se les da muy poca prioridad o por ejemplo se hace un grupo de procesos especial que son los extenso que disponen de menos CPU. El problema es que seguramente se ralenticen los procesos tanto locales como los externos, sobre todo si es un proceso que necesita frecuentar sincronizaciones, comunicación y acceso a Entrada/Salida.

Con una buenas decisiones en este apartado se puede solucionar los problemas expuestos.