Memoria conjunta
Prácticas 2 y 4.

Resolución de Sudoku con programación paralela
OpenMP y MPI.

Fecha: 19 de enero de 2014

Introducción
El presente trabajo consta de dos partes, correspondientes a las prácticas 2 y 4 de la asignatura LPP del cuarto curso del Grado en Ingeniería Informática. Dichas prácticas consisten en la implementación, ejecución y comparación de distintos tipos de paralelización del código en C para la resolución del conocido juego del Sudoku.
En la práctica 2 se emplea OpenMP. El código ha sido proporcionado por los profesores, por lo que el trabajo consiste en realizar diversas ejecuciones cambiando los parámetros de ejecución con el fin de observar las diferencias entre ellas.
En la práctica 4 …ver más…

Si además hacemos paquetes de chunk de mayor tamaño que 1, el predeterminado, se está perdiendo paralelización puesto que asignamos más cálculo a cada hilo dejando otros ociosos, por lo que el proceso es más lento.
Sólo en el caso de realizar la ejecución con 8 hilos vemos una diferencia a considerar.
La asignación estática (sin chunk) se ve penalizada frente a la dinámica debido a que hace una asignación round-robin sin tener en cuenta cuándo un hilo ha quedado ocioso.
La dinámica hace el reparto de una manera más inteligente al tener en cuenta esto último. Para N=5 la representación gráfica de los valores obtenidos es la siguiente.
Profundidad N=5
160,00
140,00

Tiempos

120,00
100,00
TH=8
TH=16
TH=32

80,00
60,00
40,00
20,00
0,00 dynamic dynamic,3

dynamic,5

static

static,3

static,5

Planificación

Ahora estamos ante un caso similar al anterior. El número de nodos que tiene en cuenta el programa es 11 al haber elegido un nivel N de 5. El incremento en el reparto en bloques de cualquiera de las políticas de asignación empeora los tiempos puesto que el número de hilos de ejecución en el caso de 16 y 32 supera ese número por los mismos motivos ya expuestos. Para la ejecución con 8 hilos en esta ocasión se obtiene una medida de tiempo ligeramente inferior con la asignación estática, lo que puede ser debido al tiempo de