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

Paralelización de programas

Se ha visto que la ley de Amdahl limita el incremento de rendimiento de los programas cuando éstos se ejecutan en sistemas multiprocesadores. También que la optimización de los programas suele depender en la mayoría de los casos del conocimiento del sistema más que del algoritmo que se utilice. Comprendiendo esto puede empezarse a definir cómo debe ser el software a nivel de aplicación para explotar al máximo el paralelismo de estos sistemas. Por un lado se intentará, basándonos en la ley de Amdahl, que el aumento de rendimiento (o speedup) de los programas sea el máximo posible, esto implica que los fragmentos de código no paralelizable deben ser los mínimos posibles. Por otro lado deberán conocerse las limitaciones y características del sistema para el que programaremos.

El primer paso en el desarrollo de un programa paralelizado es, como siempre, plantear el problema mediante técnicas de divide y vencerás. Deberá localizarse lo paralelizable en el problema de manera abstracta antes de pensar en la paralelización del código, es decir que existen problemas inherentemente paralelos, como pueden ser la suma de las componentes de dos vectores según sus posiciones o la renderización de imágenes. Estos problemas se pueden resolver de manera óptima. Por otro lado, están los problemas en los que en un principio no vemos claramente la inherencia del paralelismo como pueden ser la multiplicación de matrices, compresión de la información o compilación.

Teóricamente se puede paralelizar cualquier cosa que se haya diseminado mediante técnicas de divide y vencerás, procesos, módulos rutinas, o algoritmos paralelos completamente.

Existen dos formas bien conocidas y fáciles de comprender de paralelismo:

1. El paralelismo funcional divide las aplicaciones en funciones. Se podría ver como paralelismo de código. Por ejemplo puede dividirse en: entrada, preparación del problema, solución del problema, preparación de la salida, salida y mostrar la solución. Esto permite a todos los nodos producir una cadena. Esta aproximación es como la segmentación en funciones de un procesador.

Aquí se sigue la misma idea pero a nivel de software, se dividen los procesos formando una cadena y dependiendo uno del siguiente. Aunque al principio no se logre el paralelismo, una vez que se ponen todos los nodos a trabajar (i.e. cuando hayamos ejecutado N veces lo que estemos ejecutando, siendo N el número de pasos en los que hemos dividido la aplicación) se consiguen que todos los nodos estén trabajando a la vez si todas las funciones tardan el mismo tiempo en completarse. Sino, las demás funciones tienen que esperar a que se complete la función más lenta.
La idea es exactamente la misma que trataremos en el tema Arquitecturas aunque allí se referencie con el término pipeline. Esta forma de paralelizar no es ampliamente usada puesto que es muy difícil dividir en funciones que tarden el mismo tiempo en ejecutarse. Sólo se usa en casos concretos donde se ve claramente que es una buena opción por ser fácilmente implementable.

1. El paralelismo de datos se basa en dividir los datos que se tienen que procesar. Típicamente los procesos que están usando esos datos son idénticos entre sí y lo único que hacen es dividir la cantidad de información entre los nodos y procesarla en paralelo. Esta técnica es más usada debido a que es más sencillo realizar el paralelismo.

Ejemplos pueden ser los films Final Fantasy o El señor de los anillos que fueron renderizadas en un cluster de renderización con el software Maya y Renderman. Esta forma de renderizar se basa en dividir los frames (cuadros) que se deban renderizar en una escena en concreto o todos los frames de la película entre todos los ordenadores. Para ser más exactos, primero se divide el número de frames por el número de nodos y se envía el número resultante de frames a cada nodo (suponiendo que es un cluster donde todos los nodos tienen la misma capacidad de proceso). Esta es la fase de preparación y suele ser secuencial, puesto que es una pequeña parte de la producción. Una vez hecho esto, cada nodo renderiza los frames que le fueron asignados. Esta fase puede durar semanas. Una vez se tienen todos los frames se unen en un fichero único que tiene toda la película. En este caso en particular se usa paralelismo de datos, y aunque algunas imágenes tardan más en renderizarse que otras y por lo tanto algún nodo tardará menos en acabar su trabajo que otro, lo que se hace es no elegir imágenes de forma secuencial (de la 1 a la n al nodo 1) sino paralela (1 al nodo 1, 2 al nodo 2... n+1 al nodo n+1) esto suele compensar la carga entre los nodos por lo que más o menos todos los nodos se mantienen en el máximo rendimiento (si no se comprende esto, piense en lo poco que tardaría el nodo que renderize unos títulos de crédito simples).

Por supuesto muchos problemas se pueden solucionar con cualquiera de los dos paradigmas. En el anterior ejemplo podría haberse hecho una división funcional y hacer que un nodo renderizase luces, otro pusiera texturas, otro reflejos, etc. En cambio otras soluciones son específicas o al menos mucho más efectivas con una de las dos aproximaciones. Todos los casos en los que no se tiene una idea clara de lo que pueda tardarse en una función es más paralelizable con paralelismo de datos.

Una vez analizada la fuente de paralelismo de los programas sólo falta comenzar a realizar el estudio en pseudocódigo o cualquier otro sistema parecido. Hay que conocer los límites y características del sistema para el que va a programarse. La migración o ubicación de un proceso, módulo o rutina está ligada a un coste adicional; hemos de conocer los costes de nuestros sistemas y evaluar la conveniencia de paralelizar acciones.

Un programa paralelizado no debe obtener peor tasa de eficiencia que un programa secuencial, lo cual no siempre se cumple ni es posible debido a transferencias de comunicación entre los procesos, módulos, nodos o elementos del cluster. En este apartado juega un papel importante la red de comunicación, el cual ocupa un capítulo entero. La paralelización del código está comprometida a las ventajas de los sistemas implantados, por tanto no podremos hablar en forma general de ésta. En cualquier caso se dará una visión de un sistema concreto openMosix y se hará alguna alusión a sistemas del tipo PVM.

La paralelización del software se basa en principios generales asociados a la manera de programar que utilizamos actualmente tanto por arquitectura de los computadores, funcionamiento de compiladores como lenguajes de programac ión. Uno de estos principios generales es el denominado principio de localidad, del cual existen dos tipos de localidades en nuestros programas:

• Localización temporal.

Este tipo de localización se basa en la manera en la que se puede encontrar el código de los programas y como se ejecutan estos en el tiempo. Generalmente, los programas están compuestos por un alto porcentaje de estructuras en forma de bucle que ejecutan instrucciones. Lo que implica que con tener en memoria estos bucles, tendremos acceso a la mayor parte del programa. Por otro lado normalmente procedimientos o funciones que están relacionadas suelen estar en zonas de memoria adyacentes, así como las instrucciones que se ejecutan secuencialmente.

• Localización espacial.

Este tipo de localización se basa en la manera en la que los programadores organizamos nuestros datos en estructuras, objetos, matrices, vectores. Esta manera de organizar elementos de los programas que están muy relacionados entre sí hace que a la hora de solicitar memoria para los mismos éstos sean alojados en segmentos contiguos de memoria. Cuando en un programa se pide memoria, se intenta pedir de una vez toda la memoria que vayan a usar la mayor parte de datos posible, para precisamente tener que estar pidiendo memoria continuamente. Esto produce esta localidad.

Nuestra intención principal debería ser explotar el paralelismo al máximo nivel, para esto pueden utilizarse las típicas formas que se usan para organizar la información y paralelizar al máximo posible, accesos a la misma, operaciones a realizar y demás acciones. Por ejemplo, un programa cuyo núcleo de proceso principal se encuentre en un bucle sería perfectamente paralelizable, pongamos que el bucle se realizara 15000 veces. En el caso de tener 3 nodos podemos distribuir su ejecución en 3 procedimientos que se ejecuten en estos tres nodos y que realicen bucles de 5000 iteraciones de bucle cada uno. Para que esto sea posible es necesario cumplir un objetivo que también debemos tener en cuenta siempre que programemos aplicaciones paralelas en sistemas distribuidos como clusters. Los segmentos de código, rutinas, bucles o cualquier operación sobre estructura s de datos, deben ser ortogonales, en el sentido de que no deben interferir entre sí.

Al paralelizar programas se ve que se obtiene como ventaja un incremento del rendimiento. Este incremento puede ser decremento si estamos comunicando continuamente nuestros procesos a través de una red, que generalmente suele ser el cuello de botella del sistema. Es por esto que los elementos de procesos a paralelizar deben ser lo más independientes y ortogonales posibles.

También hay que pensar que si un proceso tiene que dedicar instrucciones a la comunicación con otros procesos, este código no es paralelizable y además es código que añadimos a cada uno de los procesos, por lo que la escalabilidad disminuye drásticamente con la cantidad de información pasada entre procesos. Aquí es cuando es especialmente importante el desarrollo software pues una buena división en procesos puede evitar esta sobrecarga de comunicación.

En el caso que aquí se trata, programación de clusters o sistemas distribuidos, se llamarán elementos de proceso a los módulos, procesos, procedimientos o rutinas que se consolidan como unidades de proceso a ejecutar en los nodos, aunque haya que diferenciarlos claramente del concepto que tiene el término elemento de proceso en sistemas multiprocesad or.

Los elementos de proceso deben ser ortogonales entre sí. El problema que anula generalmente la ortogonalidad de estos elementos, esto es la dependencia de datos. Cuando surgen dependencias, ya sea de datos o de control2.11, el programa o sistema deja de ser paralelizable y pasa a ser secuencial, se necesita interconectar generalmente los elementos para obtener sus resultados o para obtener sus estados y poder continuar el programa, esto requiere como ya hemos dicho comunicación a través de la red, lo que puede llegar a ser bastante costoso.

No existe un método general para evitar las dependencias o para ortogonalizar elementos de proceso, es por esta razón por la que todavía puede ser denominado arte en lugar de ciencia a este tipo de investigaciones. En la mayoría de ocasiones se debe utilizar algoritmos que en programación normal se darían por descartados a simple vista. En otras ocasiones el sistema permite utilizar algoritmos óptimos paralelizables. De este modo, aunque el sistema sea el mejor sistema paralelo existente, si la resolución de los problemas que tienen que hacer no son paralelizables estaremos tirando tiempo y dinero. La mayoría del esfuerzo en el desarrollo de programas que resuelvan problemas de manera paralela, se gasta en:

• Estudio completo del problema.

En el cual se evalúe las maneras de atacar el problema, se dividan las distintas secciones de éste y se tenga en cuenta las implicaciones. Se corresponde con la parte de análisis del programa

• Estudio de la paralelización del problema.

En la cual se busca la ortogonalización del problema para que este pueda ser fácilmente paralelizable. Se evalúan todas las posibles vías de paralelización y se eligen las que más se adecuen al sistema concreto sobre el que se vaya a ejecutar.

• Estudio del sistema.

Tanto a nivel práctico como teórico. Por ejemplo en el caso de PVM basta con conocer el modelo de programación, su sintaxis y el cluster sobre el que se va a ejecutar, la carga que puede aceptar cada nodo, dispositivos y recursos de cada nodo, etc.
En el caso de openMosix se debe conocer el estado del cluster, las maneras actuales de poder comunicar procesos en el sistema, creación de entorno adecuado. Cada sistema debe ser explotado de una manera diferente.

• Estudio de la paralelización del código.

Este apartado depende completamente de los dos anteriores, es decir, sólo se puede hacer correctamente en el caso que se hayan cumplido los dos apartados anteriores, corresponde con la fase de diseño del programa. Es en esta parte del desarrollo en la que muchas veces se deben cambiar algoritmos adecuados por otros que lo son menos para que sean más fácilmente paralelizables en un sistema concreto y se obtenga mejor rendimiento del mismo.

• Pruebas del sistema.

Muchos programas desarrollados mediante el paradigma de programación paralela hacen uso de un modelo de programación poco ortodoxa, que los hace difíciles de probar y de depurar al mismo tiempo. Por ejemplo, cuando se ejecuta el gdb sobre un programa que lanza otros programas y se comunica con estos mismos, la depuración se hace un tanto más difícil. Otra consecuencia de la programación poco ortodoxa es que en muchas ocasiones el programa no se comporta de la manera o con la eficiencia con la que habíamos supuesto contaría en un principio2.12.

Ejemplos de problemas paralelizables

Generalmente los programas convencionales no cuentan con ninguna manera de paralelizar su código. Es decir, sería genial poder contar con algún ejemplo de programa que comprima de formato DVD a DivX en paralelo y poder comprimir una película en un cluster como openMosix, o poder ejecutar programas de compresión en varios nodos a la vez. La realidad es otra. La mayoría de los programas son pensados y implementados de manera secuencial. Si bien existen muchos campos donde el desarrollo de programas que hagan uso de una manera u otra de paralelismo, está creciendo cada vez más. Actualmente, entre estos campos contamos con:

• granjas de compilación
• granjas de renderización
• procesos matemáticos
  • multiplicación de matrices
  • suma de vectores por componentes
  • multiplicación de matrices o vectores por escalares o funciones escalares.
  • integrales definidas (creando intervalos más pequeños como elementos de proceso)
• compresión
• aplicación a nuevos paradigmas inherentemente paralelos
  • redes neuronales
  • algoritmos genéticos

En el campo científico es en el que más se están haciendo desarrollos de este tipo de programas ya que es el campo en el que generalmente es más fácil encontrarse problemas a paralelizar por la naturaleza de estos. Actualmente otras nuevas vías de desarrollo están siendo bastante utilizadas.

Existen programas de renderizado como MAYA o 3D Studio que utilizan paralelismo en forma de threads para poder hacer uso de sistemas multiprocesador, de modo que el tiempo de renderizado se reduzca considerablemente. Es una lástima que ninguno de estos sistemas haga uso de soluciones libres que permitan abaratar el coste del sistema, por ejemplo un MAYA para Linux (que existe) que utilice un cluster Beowulf, PVM, MPI u openMosix permitiendo abaratar gastos a la empresa que lo utiliza y al mismo tiempo, reducir tiempos de renderizado. Para aprovechar varios nodos se usa un programa especial llamado Renderman el cual decide a que nodo enviar las imágenes a ser renderizadas. Este programa es una solución particular que se desarrolló para Toy Story (cluster de máquinas SUN) y que sólo funciona para el problema de las granjas de renderización.

Existen también múltiples entornos de trabajo distribuidos en empresas que utilizan de una manera muy superficial paralelización de los problemas, ya que la mayoría están dominados por paradigma cliente-servidor que impera en el mercado.

En el campo científico es ampliamente utilizado. Un ejemplo real es el de estudio oceanográfico realizado por el instituto nacional de oceanografía española2.13, en este estudio, se utilizaban matrices descomunales para poder controlar el movimiento de las partículas comprendidas en una región de líquido, que tenía en cuenta viscosidad, temperatura, presión, viento en la capa superficial del liquido, y otras muchas variables. Este ejemplo es el típico en el cual PVM y openMosix podrían ser utilizados conjuntamente.

El ejemplo de código paralelizable más típico y simple es la multiplicación de una matriz.