Programación Paralela con MPI
Felipe Acevedo
Niklas Tampier
Contexto:
Se desea implementar una solución de la forma Single Program Multiple Data (SPMD) utilizando la biblioteca MPI (con la implementación MPICH)la que nos permite ejecutar un mismo programa en múltiples computadores.
Problema a solucionar:
Descubrir el texto plano asociado a un texto cifrado utilizando el algoritmo DES y salt conocida. la cantidad de combinaciones que se puede realizar con un diccionario de tamaño n y un texto de m caracteres, es:
Combinaciones de texto plano = n^m
n = Tamaño de diccionario utilizable
m = cantidad de caracteres a resolver.
Para descubrir el texto cifrado se utiliza fuerza bruta, es decir, se pretende comparar todas las posibles combinaciones (cifrandolas) con el texto cifrado conocido, dado que el tiempo de ejecución de estas comparaciones es demasiado grande (aumenta de forma exponencial en función de la cantidad de caracteres del texto) para ejecutar el programa en un solo computador, se requiere de una arquitectura de múltiples computadores. Para esto se utiliza una descomposición del dominio del problema. Cada Raspberry PI probará una porción de las alternativas posibles.
Arquitectura:
Se utilizan 4 Raspberry Pi conectadas por Ethernet a un router formando un micro-cluster.
Cada Raspberry ejecuta el mismo programa corriendo el comando mpiexec en la Raspberry “maestra”, a la cual se le asigna por defecto ID = 0. este programa se ejecuta en función de la ID de cada Raspberry pi, las cuales son asignadas por la implementación de MPI, con esto se logra que cada Raspberry pi ejecute el mismo código pero analizando una porción distinta. (Ver Código fuente)
Resultados:
Para medir los resultados obtenidos se comparan los tiempos en que demora la ejecución en una Raspberry Pi con el tiempo en “n” Raspberry Pi, desde que el programa se ejecuta hasta el acierto con el texto cifrado.
Conclusión:
Con la experiencia realizada se aprecia que se puede lograr un gran aumento de rendimiento al utilizar una arquitectura distribuida en SPMD, sin perder demasiado tiempo en desarrollo o complicar en demasía el código. Ademas, sin una explicación evidente, se observa que el aumento en cantidad de procesadores (Raspberry pis) , disminuye el tiempo en proporciones mayores a las esperadas, como se observa en el gráfico 1, la línea azul (resultados reales) va por sobre la línea roja (relación lineal teórica).