Demostración programación paralela I Algoritmo hill-climbing



En la introducción al paralelismo vimos cómo trabajaban y cómo controlar el funcionamiento de OpenMP y MPI. Ahora veremos cómo el uso de MPI nos permite resolver problemas que con la programación secuencial sería prácticamente imposible.

Vamos a trabajar con el algoritmo hillclimbing. Este algoritmo se emplea para hayar máximos y mínimos relativos de funciones en un intervalo. Sin embargo, gracias al paralelismo podemos obtener los extremos absolutos de ese intervalo de manera mucho más rápida que secuencialmente. En los ejemplos aquí presentados se haya el máximo; no obstante, modificar el código para hayar el mínimo es trivial.

Versión secuencial

Secuencialmente solo podemos trabajar con un punto a la vez, cuando se llegue al máximo de fracasos establecido se parará y el punto actual será el máximo calculado. Esto es muy proclive a mostrar un máximo relativo que no tiene por qué ser el absoluto:


  • Punto inicial:

    Punto inicial
    Punto inicial
  • Máximo calculado:

    Punto máximo
    Punto máximo

Versión paralela

Ahora tenemos n procesos MPI. Dividimos el intervalo donde vamos a hayar el máximo en n-1 partes iguales y cada proceso MPI hijo (rank ≠ 0) se encargará de calcular el máximo de su región. Cuantos más procesos haya más pequeñas serán las regiones, y por tanto la probabilidad de calcular el máximo absoluto de cada región será mayor. Cuando un proceso ha calculado el máximo de su región, envía un mensaje MPI (MPI_Send) al padre (rank = 0) con dicho punto. Cuando el padre ha recibido (MPI_Recv) los máximos de todos los hijos los compara para ver cuál es el mayor, obteniendo así el máximo absoluto dentro del intervalo especificado.


  • Puntos iniciales:

    Puntos iniciales
    Puntos iniciales
  • Máximos claculados en cada intervalo:

    Máximos de cada intervalo
    Máximos de cada intervalo
  • Máximo absoluto:

    Máximo absoluto
    Máximo absoluto