Comparación práctica OpenMP y MPI

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 distintostipos 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 se utiliza MPI para resolver el mismo juego como sedescribirá más
adelante.

Práctica 2. Resolución de Sudoku con OpenMP
Los códigos solución de esta práctica proporcionados por el profesor son dos,
correspondientes a las modalidades llamadas estática y dinámica, donde esta última
hace uso de la directiva task para definir tareas concurrentes, mientras que en la versión
estática, la primera que vamos a ver, hace la asignación de maneraestática, esto es, un
nodo del árbol de resolución a cada hilo de ejecución.

Asignación estática.
La experiencia consiste en realizar ejecuciones del programa variando el método de
planificación y comprobar cómo se comportan los distintos métodos según otros
parámetros como son el número de hilos de ejecución y la profundidad con la que se va
a explorar el árbol de posibles soluciones.
Asípues se han ejecutado diversas instancias indicando un número de threads de 8, 16
y 32 en un único nodo. Para cada una de estas posibilidades se ha ejecutado el programa
indicando un valor de N (profundidad) de 3, 5 y 6. Estos valores de profundidad
comportan la ejecución para 10, 11 y 35 nodos respectivamente, lo que tendrá su
importancia en el tipo de scheduling seleccionado. En este sentido,para cada
combinación se ha variado el tipo de planificación entre dynamic y static con valores de
chunk de 3, 5 y el predeterminado.
Se han realizado otras medidas ya sólo para un valor de N=6 haciendo uso de 2
procesadores y con un número de hilos de 8, 16, 32 y 64 con las planificaciones ya
indicadas. Con el fin de tener más hilos que nodos disponibles y ver cómo afecta.
Los valoresobtenidos, resaltando en negrita los tiempos menores para cada valor de
Profundidad e hilos de ejecución, y con fondo gris las ejecuciones con 2 nodos, son los
siguientes:

N=3 Nodos=10

N=5 Nodos=11

Scheduling
dynamic
dynamic,3
dynamic,5
static
static,3
static,5
Scheduling
dynamic
dynamic,3

TH=8
65,44
108,08
169,40
82,30
108,15
169,73
TH=8
70,85
87,52

TH=16
68,31107,46
170,05
68,20
108,08
169,45
TH=16
46,44
87,71

TH=32
68,04
107,85
169,92
67,77
108,02
170,76
TH=32
46,69
87,60

TH=64

TH=64

N=6 Nodos=35

dynamic,5
static
static,3
static,5
Scheduling
dynamic
dynamic
dynamic,3
dynamic,3
dynamic,5
dynamic,5
static
static
static,3
static,3
static,5
static,5

139,92
67,85
88,03
140,30
TH=8
61,76
61,15
65,4164,70
54,61
54,23
63,45
62,90
63,90
63,92
54,17
54,07

139,86
46,19
87,91
140,23
TH=16
49,60
50,02
43,28
43,32
55,19
54,55
52,98
53,46
42,84
42,80
55,56
54,43

140,46
46,86
87,44
139,76
TH=32
41,07
40,05
43,73
43,80
54,59
54,58
47,50
48,43
43,18
43,15
54,55
53,90

TH=64
39,04
42,52
54,22
39,80
43,24
55,76

Gráficamente, para una profundidad deN=3, los valores obtenidos se podrían
representar así.
Profundidad N=3
180,00
160,00

Tiempos

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

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

dynamic,3

dynamic,5

static

static,3

static,5

Planificación

Se puede observar que con el nivel de profundidad 3 introducir un valor de chunk mayor
ralentiza la resolución. Con N=3 la...