La programación y computación en Paralelo - 3ra Parte

avatar


binary2.png
Imagen de Pixabay


Para ver cómo el paralelismo puede ayudarle a resolver problemas, lo mejor es ver algunos ejemplos. En este post, trataremos de discutir brevemente el llamado problema de los n-cuerpos o The n-body problem.


El problema clásico de los n-cuerpos es el problema de predecir los movimientos individuales de un grupo de objetos que interactúan entre sí por gravitación. A continuación se presenta un enunciado más preciso de dicho problema:


nBody.png
El problema de los n-cuerpos. Elaborado en Inkscape por @abdulmath


Mientras que el problema clásico de los n-cuerpos estaba motivado por el deseo de comprender el movimiento del Sol, la Luna, los planetas y las estrellas visibles, hoy en día se utiliza para comprender la dinámica de los sistemas estelares de los cúmulos globulares. En este caso, la habitual mecánica de Newton, que rige el movimiento de los cuerpos, debe ser sustituida por la teoría de la relatividad general de Einstein, lo que dificulta aún más el problema. Por lo tanto, nos abstendremos de tratar esta versión del problema y nos centraremos en la versión clásica, tal y como se ha introducido anteriormente, y en la forma de resolverlo en un computación paralela.


Entonces,

¿cómo podemos resolver un determinado problema clásico de n cuerpos?

Primeramente mostremos una descripción de la forma qe esperamos la solución del problema. El problema clásico de n-cuerpos asume la mecánica clásica de Newton, que todos hemos aprendido en la escuela. Usando esta mecánica, una instancia dada del problema de n cuerpos se describe como un sistema particular de 6n ecuaciones diferenciales que, para cada uno de los n cuerpos, definen su ubicación (x(t), y(t), z(t)) y su momento (mvx(t), mvy(t), mvz(t)) en un instante t.


La solución de este sistema es la descripción buscada de la evolución del sistema de n cuerpos. Por lo tanto, la resolución de un determinado problema clásico de n-cuerpos se reduce a solución del sistema asociado de ecuaciones diferenciales asociadas que finalmente se transforman en un sistema de ecuaciones lineales.


Hoy en día sabemos que

  • si n = 2, el problema clásico de n cuerpos siempre tiene solución analítica, simplemente porque el sistema de ecuaciones asociado tiene solución analítica.
  • si n > 2, existen soluciones analíticas sólo para ciertas configuraciones iniciales de n cuerpos.
  • En general, sin embargo, los problemas de n cuerpos no pueden resolverse analíticamente.


solar-system.png
Imagen de Pixabay


En general, el problema de n cuerpos debe resolverse numéricamente, utilizando métodos numéricos adecuados para resolver sistemas de ecuaciones diferenciales.

¿Podemos conseguirlo siempre?


Los métodos numéricos integran numéricamente las ecuaciones diferenciales del movimiento. Para obtener la solución, estos métodos requieren un tiempo que crece proporcionalmente a n2 . Podemos decir que los métodos tienen una complejidad temporal del orden O(n2). A primera vista, esto parece bastante prometedor; sin embargo, hay un gran factor oculto en este O(n2). Debido a este factor, sólo las instancias del problema de problema de n cuerpos con valores pequeños de n pueden resolverse con estos métodos numéricos.


Para extender la resolubilidad paraa valores grandes de n, hay que encontrar métodos con menor complejidad temporal de tiempo. Uno de ellos es el método de Barnes-Hut con una complejidad temporal O(nlog(n)). Pero, de nuevo, sólo se pueden resolver las instancias con valores limitados (aunque grndes) de n. Así

Para valores grandes de n, los métodos numéricos se vuelven prohibitivos en términos de tiempo.


galaxy.png
Imagen de Pixabay


Por desgracia, los valores de n suelen ser muy grandes en la práctica. En realidad, son demasiado grandes para que los métodos numéricos mencionados tengan algún valor práctico.

¿Qué podemos hacer en esta situación?


Pues bien, en este punto entra en escena la computación paralela. Los métodos numéricos que utilizamos para resolver sistemas de ecuaciones diferenciales asociados al problema de los n-cuerpos suelen estar programados para ordenadores de un solo procesador. Pero si tenemos a nuestra disposición un compuatador paralelo con muchos procesadores, es natural considerar el uso de todos ellos para que colaboren y así resolver conjuntamente los sistemas de ecuaciones diferenciales. Sin embargo, para conseguirlo, debemos responder a varias preguntas no triviales:

  1. ¿Cómo podemos dividir un método numérico dado en subtareas?
  2. ¿Qué subtareas debe realizar cada procesador?
  3. ¿Cómo debe colaborar cada procesador con otros procesadores? Y luego, por supuesto,
  4. ¿Cómo codificaremos todas estas respuestas en forma de programa paralelo, un programa capaz de ejecutarse en el ordenador paralelo y explotar sus recursos.


Las preguntas anteriores no son fáciles, sin duda, pero se han diseñado algoritmos paralelos para los métodos numéricos mencionados, y se han escrito programas paralelos que implementan los algoritmos para diferentes computadores paralelos.


Por ejemplo, J. Dubinsky y colaboradores diseñaron un algoritmo Barnes-Hut paralelo y un programa paralelo que divide el sistema de n cuerpos en volúmenes rectangulares independientes, cada uno de los cuales se asigna a un procesador de un computador paralelo. El programa paralelo fue capaz de simular la evolución de sistemas de n cuerpos consistentes con n = 640.000 hasta n = 1.000.000 de cuerpos. Resultó que, para tales sistemas, el número óptimo de unidades de procesamiento era de 64. Con ese número, los procesadores estaban mejor equilibrados en cuanto a carga y la comunicación entre entre ellos era mínima.



waves.png
Imagen de Pixabay


Si quedastes fascinado con este apasionante tema de la computación y programación en paralelo, no te pierdasd la proxíma publicación sobre este tema, si deseas ampliar más te invito a leer las siguientes referencias:

  • Atallah, M., Blanton, M. (eds.): Algorithms and Theory of Computation Handbook, Chapman and Hall, Boca Raton (2010).
  • Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J.: Parallel Programming in OpenMP. Morgan Kaufmann, Burlington (2000).
  • Foster, I.: Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison-Wesley Longman Publishing Co., Inc, Boston (1995).


Hive.png
cervantes.png



0
0
0.000
1 comments