Algoritmos en paralelo para una variante del problema bin packing Proyecto : 5402-1440-2601 MSc. Geovanni Figueroa M. MSc. Ernesto Carrera R. Instituto Tecnol´ogico de Costa Rica Vicerrector´ıa de Investigaci´on y Extensi´on Direcci´on de Proyectos 23 de junio de 2011

´Indice general 1. Descripci´ on del problema 1.1. Introducci´on . . . . . . . . . 1.2. Planteamiento del problema 1.3. Complejidad del problema . 1.3.1. Espacio factible . . . 1.4. Objetivos del proyecto . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1 1 2 2 4 6

2. Programaci´ on paralela 2.1. Dise˜ no de algoritmos en paralelo . . . . . . . . . . . . . . . 2.1.1. Descomposici´on y dependencia de tareas . . . . . . . 2.1.2. Granularidad y concurrencia . . . . . . . . . . . . . 2.2. T´ecnicas de descomposici´on . . . . . . . . . . . . . . . . . . 2.2.1. Descomposici´on recursiva . . . . . . . . . . . . . . . 2.2.2. Descomposici´on de datos . . . . . . . . . . . . . . . 2.2.3. Descomposici´on exploratoria . . . . . . . . . . . . . 2.2.4. Descomposici´on h´ıbrida . . . . . . . . . . . . . . . . 2.3. Modelos de programaci´on paralela . . . . . . . . . . . . . . 2.3.1. MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2. Posix Threads . . . . . . . . . . . . . . . . . . . . . 2.3.3. OpenMP . . . . . . . . . . . . . . . . . . . . . . . . 2.4. M´etricas para evaluar el desempe˜ no de un sistema paralelo 2.4.1. Speedup . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2. Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3. Escalabilidad . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

8 8 9 9 9 10 10 10 10 10 10 11 11 12 12 13 13

3. An´ alisis de resultados 3.1. Algoritmos . . . . . . . 3.2. Experimentos . . . . . . 3.3. Discusi´on de resultados 3.4. Conclusiones . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

14 14 18 31 31

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

A. Instancias de prueba 32 A.1. Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A.2. Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 A.3. Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1

A.4. Problema 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2

´Indice de figuras 1.1. Soluciones para todas las posibles matrices de distribuci´on. . . . . . . . . . . . . . . 3.1. Tiempos en determin´ıstico 8 × 4 × c. . 3.2. Speedup en determin´ıstico 8 × 4 × c . 3.3. Eficiencia en determin´ıstico 8 × 4 × c . 3.4. Tiempos en heur´ıstico 8 × 5 × c. . . . 3.5. Speedup en heur´ıstico 8 × 5 × c . . . . 3.6. Eficiencia en heur´ıstico 8 × 5 × c . . . 3.7. Tiempos en determin´ıstico n × 3 × 10. 3.8. Speedup en determin´ıstico n × 3 × 10 . 3.9. Eficiencia en determin´ıstico n × 3 × 10 3.10. Tiempos en heur´ıstico n × 3 × 10. . . . 3.11. Speedup en heur´ıstico n × 3 × 10 . . . 3.12. Eficiencia en heur´ıstico n × 3 × 10 . . 3.13. Tiempos en determin´ıstico 8 × m × 8. 3.14. Speedup en determin´ıstico 8 × m × 8 . 3.15. Eficiencia en determin´ıstico 8 × m × 8 3.16. Tiempos en heur´ıstico 8 × m × 8. . . . 3.17. Speedup en heur´ıstico 8 × m × 8 . . . 3.18. Eficiencia en heur´ıstico 8 × m × 8 . . .

. . . . . . . . . . . . . . . . . .

3

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

5 19 20 20 21 22 22 23 24 24 25 26 26 27 28 28 29 30 30

´Indice de cuadros 1.1. 1.2. 1.3. 1.4. 1.5.

Matriz para representar una soluci´on al problema. Una soluci´on factible al problema ejemplo. . . . . . Tripletas con suma 6. . . . . . . . . . . . . . . . . Una distribuci´on ´optima al problema ejemplo. . . . Otra distribuci´on ´optima al problema ejemplo. . .

4

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 4 4 5 6

Resumen En este informe se resumen los resultados obtenidos en la investigaci´ on realizada sobre una variante del problema bin packing. El objetivo fue dise˜ nar e implementar algoritmos determin´ısticos y heur´ısticos en paralelo para resolver y aproximar la soluci´on a dicho problema. Se presenta el problema; se hace un an´alisis de la complejidad del mismo; se mencionan algunos de los modelos existentes para la programaci´on en paralelo as´ı como algunas bibliotecas que permiten el desarrollo de algoritmos con estos modelos; se introducen las m´etricas usuales que permiten medir el desempe˜ no de un algoritmo en paralelo; y se resumen los experimentos realizados. En los dise˜ nos de los algoritmos se utiliz´o el modelo exploratorio, y su implementaci´ on se realiz´o utilizando la biblioteca OpenMP en C. Los resultados obtenidos en instancias de prueba mostraron mejoras en el tiempo de ejecuci´on de hasta 10x con respecto a las implementaciones secuenciales de los algoritmos respectivos. Estos resultados permiten concluir que el dise˜ no propuesto y la implementaci´ on respectiva, resuelven de manera satisfactoria el problema planteado.

palabras clave: optimizaci´on combinatoria, optimizaci´on discreta, problema bin packing, heur´ısticas, algoritmos en paralelo.

Cap´ıtulo 1

Descripci´ on del problema 1.1.

Introducci´ on

La optimizaci´on combinatoria es una rama de la optimizaci´on en general. Se encarga b´asicamente de problemas de optimizaci´on donde la regi´on de soluciones factibles es discreta o puede ser reducida a una regi´on discreta, y tiene como objetivo encontrar la mejor soluci´on. Esta reducci´on, de manera sorprendente, convierte problemas que en el caso general pueden ser resueltos con relativa facilidad, en problemas sumamente complejos en su tiempo de soluci´on. Involucra las matem´aticas aplicadas y ciencias de la computaci´on, y est´a relacionada con investigaci´on de operaciones, teor´ıa de algoritmos y teor´ıa de la complejidad computacional, y abarca ´areas como la inteligencia artificial, las matem´aticas y la ingenier´ıa de software. Dentro de la optimizaci´on combinatoria, las l´ıneas de investigaci´ on han ido, tanto por definir t´ecnicas generales de soluci´on (branch and bound, optimizaci´on lineal entera, branch and price y generaci´on de columnas), como por resolver de manera ´optima, o encontrar heur´ısticas eficientes, para problemas espec´ıficos. Debido a la inconveniencia de encontrar soluciones ´optimas a problemas complejos, es que se suelen utilizar heur´ısticos que aseguren, al menos, una “buena”soluci´on. Es decir, una soluci´on que, aunque no es ´optima, es aceptable para el que presenta el problema. Dentro de dichos heur´ısticos, u ´ltimamente ha tomado gran fuerza la utilizaci´on de meta–algoritmos evolutivos, los cuales est´an inspirados en caracter´ısticas de la evoluci´ on biol´ogica: reproducci´on, mutaci´ on, recombinaci´ on y selecci´on, e incluyen t´ecnicas como algoritmos gen´eticos y simulated annealing entre otros. La computaci´on paralela es una t´ecnica de programaci´on que ha tenido un fuerte empuje en los u ´ltimos a˜ nos, debido a que el desarrollo de microprocesadores ha alcanzado un l´ımite en lo que se refiere al n´ umero m´aximo de operaciones que pueden ejecutarse por segundo. Esto ha motivado el desarrollo de las tecnolog´ıas de procesadores paralelos (multin´ ucleo) y procesos distribuidos. La programaci´on tradicional est´a orientada hacia la computaci´on secuencial; en ´esta, el flujo de instrucciones se ejecuta secuencialmente, una a una. En la computaci´on paralela se emplean elementos de procesamiento simult´aneo; esto se logra dividiendo el problema en subprocesos independientes de tal manera que cada elemento de procesamiento pueda ejecutarse a la vez. Estos elementos de procesamiento pueden ser diversos e incluir recursos tales como un u ´nico ordenador con muchos procesadores, varios ordenadores en red, hardware especializado o una combinaci´ on de los mismos. Esto hace que esta t´ecnica sea una herramienta u ´til para resolver problemas computacionalmente complejos; sin embargo, ello aumenta la dificultad del dise˜ no de un algoritmo en 1

paralelo, debido a que la comunicaci´on y sincronizaci´on entre los diferentes subprocesos debe realizarse adecuadamente para conseguir un buen rendimiento. En el contexto de los m´etodos heur´ısticos, el paralelismo no s´olo significa resolver los problemas de forma m´as r´apida, sino que adem´as se obtienen modelos de b´ usqueda m´as eficientes: un algoritmo heur´ıstico paralelo puede ser m´as efectivo que uno secuencial, aun ejecut´andose en un s´olo procesador [1]. El problema estudiado tiene un espacio factible muy grande [5]. Incluso para instancias peque˜ nas del problema la soluci´on ´optima no se puede hallar en un tiempo razonable, y para heur´ısticos, mientras mayor sea la cantidad de trabajo realizado, m´as cercana estar´a la aproximaci´ on de la soluci´on ´optima. Este proyecto tiene como objetivo dise˜ nar e implementar algoritmos en paralelo que permitan reducir el tiempo de ejecuci´on, en comparaci´on con los algoritmos actuales, tanto heur´ısticos como algoritmos que resuelven el problema de manera ´optima. Como resultado de la investigaci´on en el proyecto Optimizaci´ on de Lipschitz, optimizaci´ on combinatoria y algoritmos evolutivos [6] se han propuesto algoritmos secuenciales tanto para aproximar como para resolver de forma ´optima el problema. Por tratarse de un problema NP, el tiempo de c´omputo de la soluci´on, incluso para instancias peque˜ nas es excesivo, por esta raz´on el uso de algoritmos en paralelo es una alternativa natural de investigar, para encontrar buenas aproximaciones o soluciones ´optimas.

1.2.

Planteamiento del problema

En el trabajo de tesis de maestr´ıa del MSc. Luis Carrera [3], junto con su asesor el Dr. Feli´ u Sagols, se resolvi´o el siguiente problema de optimizaci´on combinatoria: Problema P: Dados d = [d1 , d2 , . . . , dn ], c y m, con di ∈ IN para i = 1, . . . , n, m ∈ IN , c ∈ IN , m · c ≥ n, determinar b = (b1 , . . . , bm ) y Sn×m = [si,j ], sujeto a: bj ∈ IN

j = 1, . . . , m

(1.1)

i = 1, . . . , n; j = 1, . . . , m

(1.2)

si,j = c

j = 1, . . . , m

(1.3)

bj si,j ≥ di

i = 1, . . . , n

(1.4)

si,j = 0, . . . , c n X i=1 m X j=1

tal que se minimice

m X

bj .

j=1

1.3.

Complejidad del problema

Con la idea de evidenciar la complejidad del problema considere la siguiente situaci´on: suponga que una tienda de abarrotes recibe mercader´ıa nueva, pero se percatan de que tienen almacenados 97 jugos de uva, 76 de manzana y 68 de naranja, y podr´ıan caducar si no se venden pronto. Se 2

!htb Cuadro 1.1: Matriz para representar una soluci´on al problema.   x y x+y  d1 a11 a12 r1     d2 a21 a22 r1  d3 a31 a32 r1

sugiere entonces ponerlos en oferta en 2 tipos de paquetes surtidos con 6 jugos, de manera que todos los paquetes de un mismo tipo sean iguales (es decir, que tengan los mismos sabores, y la misma cantidad de jugos de cada sabor). ¿C´omo se deben empacar los jugos, de manera que se pongan en oferta todos los jugos que estaban almacenados y se minimice el n´ umero de paquetes? Observe que se tienen tres tipos diferentes de jugos (objetos, n = 3) y dos tipos diferentes de paquetes (recipientes, m = 2). Para modelar el problema suponga que: x es el n´ umero de paquetes necesarios del primero tipo (repeticiones del recipiente 1). y es el n´ umero de paquetes necesarios del segundo tipo (repeticiones del recipiente 2). aij es el n´ umero de jugos de tipo i (uva, manzana o naranja) que se deben poner en el recipiente de tipo j (n´ umero de copias del objeto i-´esimo en el recipiente j-´esimo). d = (d1 , d2 , d3 ) = (97, 76, 68) los requerimientos de cada tipo de jugo. c = 6 la capacidad de cada paquete (capacidad del recipiente). Con esta notaci´on se puede representar una instancia del problema por medio de la matriz que se muestra en el Cuadro 1.1, donde se han incluido los t´erminos r1 , r2 y r3 los cuales representan el exceso o sobrante respecto a la cantidad deseada para cada uno de los objetos, y x + y representa el valor de la soluci´on al problema (total de paquetes necesarios). Por otro lado, como el n´ umero de jugos por paquete debe ser 6, deben satisfacerse la siguiente condici´on: 3 X aij = 6 j = 1, 2 (1.5) i=1

Adem´as, para agotar las existencias se debe cumplir que: a11 x + a12 y ≥ 97 a21 x + a22 y ≥ 76

(1.6)

a31 x + a32 y ≥ 68 Y se quiere minimizar f (x, y) = x + y (para utilizar la menor cantidad de jugos “extra”). Observe que el problema es complejo, pues no s´olo se debe minimizar el costo, sino que adem´as se debe buscar la forma de distribuir los jugos en los paquetes, esto hace que sea imposible aplicar directamente alguna t´ecnica de programaci´on lineal o entera, pues a priori no se conoce la distribuci´on que se debe asignar a cada tipo de paquete. Por ejemplo, una soluci´on se muestra en la 3

Cuadro 1.2: Una soluci´on factible al problema ejemplo.   20 24 44  97 4 1 7     76 1 3 16  68 1 2 0

Cuadro 1.2. afirma que si usamos 20 paquetes del tipo 1 y 24 paquetes del tipo 2 (ambos con capacidad para 6 jugos) el total de paquetes ser´ıa de 44. Adem´as, en cada paquete de tipo 1 se deben colocar cuatro jugos de uva, uno de manzana y uno de naranja; mientras que en cada paquete de tipo 2 se deben colocar uno de uva, tres de manzana y dos de naranja. Observe que esta soluci´on satisface las condiciones (1.5) y (1.7). Por otro lado, como deben ponerse en oferta todos los jugos existentes, pueden requerirse jugos extra, por ejemplo, en este caso se requieren 7 jugos de uva y 16 de manzana.

1.3.1.

Espacio factible

Para tener una idea de la complejidad del problema vamos a explorar el espacio factible. Para esto calculemos todas las posibles matrices de distribuci´on de jugos Ak que pueden presentarse:  k  a11 ak12 Ak =  ak21 ak22  ak31 ak32 Observe que como ak1j + ak2j + ak3j = 6, donde akij es un entero entre 0 y 6 para toda i = 1, 2, 3, y j = 1, 2, se tienen 28 posibles tripletas con suma 6, como se muestra en el Cuadro 1.3. Aqu´ı, se indican los valores de los akij presentes en la tripleta, mientras que los restantes son cero; por ejemplo, hay 6 tripletas que contienen los valores 1 y 5. akij

total

6 1,5 2,4 3,3 1,1,4 1,2,3 2,2,2

3 6 6 3 3 6 1

Cuadro 1.3: Tripletas con suma 6. As´ı, se tienen 282 = 784 posibles matrices de distribuci´on, alguna o algunas de las cuales producen una soluci´on ´optima, es decir, minimizan el n´ umero de paquetes. En la Figura 1.1 se muestran las soluciones ´optimas obtenidas al resolver la relajaci´on lineal del

4

problema: m´ın x + y A · (x, y)t ≥ dt aij ∈ 0, 1, · · · , c x, y ∈ N por medio de programaci´on lineal, para cada matriz de distribuci´on y para el vector de demandas d = (97, 76, 68). Observe que detr´as de cada uno de los puntos de la gr´afica de la Figura 1.1 est´a una o varias matrices de distribuci´on la cuales tienen a este punto como mejor soluci´on. La recta x + y = 41 que se muestra en la Figura 1.1 corresponde a la soluci´on ´optima del problema. Observe que existen varias distribuciones que alcanzan el ´optimo (puntos sobre la recta x + y = 21), por ejemplo las que se muestran en los Cuadros 1.4 y 1.5. 100

80

60 y

•

••• •• • • •

• •

•

• • •• • •••• •• • • •• • •• • • ••••• • • • ••• •• •• • • •

•

•

•

•

• •

•

•

• • • •••• • ••• •• •• • • • • • ••• • •• • • •• • 40 ••••• ••• •••• • • • • • • • •• • • •• ••• ••• •• ••• • • ••• • •• • •• ••• •• •• • • •••••• •• • • • • •• • • •• ••• •• • ••• •• • •• •• • • • •• • • •• •• •• ••• • •• •• • • • • • • • ••• •• • • • • 20 • • •• • ••• • •• • • •• •• • •• • • •• •• • •• • • • • • • •• •• •• • • • •• • • •• • •• • • •• • • • • •• • •• • • ••• • • • • • • • • • • 0 0 10 20 30 40 50 x

•

•

•

•

• • •

• •

• • • • • • • • • • • • • • •• • • • •• • • • 60 70

• •• •• • •• • • • • • • • • • 80

• • • • • • • • • •

90

• 100

Figura 1.1: Soluciones para todas las posibles matrices de distribuci´on.

Cuadro 1.4: Una distribuci´on  23  97 2   76 1 68 3

´optima al problema ejemplo.  18 41 3 3   3 1  0 1

En general, para determinar el n´ umero posibles de matrices de distribuci´on Ak , se determina el 5

Cuadro 1.5: Otra distribuci´on  34  97 3   76 1 68 2

´optima al problema ejemplo.  7 41 0 5   6 0  0 0

n´ umero de distribuciones para cada columna, tal que n X

aij = c

i=1

donde c es la capacidad de cualquiera de los recipientes. El n´ umero de distribuciones est´a dado por las combinaciones: µ ¶ (n + c − 1)! n+c−1 = n−1 (n − 1)! c! y en consecuencia el n´ umero total de matrices est´a dado por: µ ¶m n+c−1 c−1

(1.7)

Observe que la cantidad de posibles matrices Ak aumenta dr´asticamente con respecto al aumento de cualquiera de los par´ametros c, n ´o m. Por otro lado, note que no toda matriz Ak es una soluci´on factible, por ejemplo, aquellas matrices tales que ai1 = ai2 = · · · = ain = 0 para alg´ un i ∈ {1, 2, · · · , m}, es decir, las matrices donde no se asignaron copias de la demanda i-´esima en ninguno de los recipientes. Esto hace que la ecuaci´on (1.7) cuente algunas matrices de m´as.

1.4.

Objetivos del proyecto

Los objetivos propuestos inicialmente para la investigaci´ on, los cuales se cumplieron por completo, fueron los siguientes: 1. Objetivo general Dise˜ nar e implementar algoritmos en paralelo que aproximen y que resuelvan la variante propuesta al problema bin packing. 2. Objetivos espec´ıficos a) Investigar diferentes opciones disponibles para la programaci´on de algoritmos en paralelo. b) Estudio de la plataforma escogida para la programaci´on de algoritmos en paralelo.

6

c) Dise˜ nar una paralelizaci´on para el heur´ıstico que encuentra una soluci´on aproximada al problema. d ) Implementar el algoritmo en paralelo para el dise˜ no de paralelizaci´on del heur´ıstico. e) Dise˜ nar una paralelizaci´on para el m´etodo que encuentra la soluci´on ´optima al problema. f ) Implementar el algoritmo en paralelo para el dise˜ no de paralelizaci´on del ´optimo. g) Comparaci´on de los tiempos de ejecuci´on.

7

Cap´ıtulo 2

Programaci´ on paralela La computaci´on paralela es una t´ecnica de programaci´on que emplea elementos m´ ultiples de procesamiento simult´aneo para resolver un problema. Esto se logra dividiendo el problema en partes independientes de tal manera que cada elemento de procesamiento pueda ejecutar su parte de forma simult´anea. Los elementos de procesamiento son diversos, van desde un u ´nico computador con muchos procesadores, redes de computadoras o hasta hardware especializado. En los u ´ltimos a˜ nos el inter´es por la computaci´on paralela ha aumentado debido a la restricci´on f´ısica que impiden el escalado de frecuencia1 . Esto ha hecho que se aproveche la mejor y mayor integraci´on de los transistores para introducir otro tipo de mejoras, llegando as´ı hasta los cores de hoy en d´ıa. Es decir, para ganar en rendimiento se ha pasado de escalar en frecuencia a escalar en paralelismo o procesamiento multin´ ucleo.

2.1.

Dise˜ no de algoritmos en paralelo

El dise˜ no de algoritmos es fundamental al resolver problemas mediante el computador. Un algoritmo secuencial es esencialmente una receta o una sucesi´on de pasos usados para resolver un problema dado, usando un procesador. De forma similar un algoritmo en paralelo es una receta que dice como resolver un problema usando m´ ultiples procesadores. Sin embargo, especificar un algoritmo en paralelo es m´as que simplemente describir los pasos a seguir, se deben considerar aspectos como la concurrencia y el dise˜ nador debe indicar el conjunto de pasos que pueden ser ejecutados simult´aneamente. Esto es esencial para lograr obtener ventajas del uso de un computador paralelo. Al dise˜ nar un algortimo en paralelo se debe tomar en cuenta todos o algunos de los siguientes aspectos: Identificar porciones de trabajo que puedan ser ejecutadas simult´ aneamente. Asignar estas porciones de trabajo a m´ ultiples procesadores que se ejecutan en paralelo. Distribuir las entradas, salidas y c´alculo de datos intermedios asociados con el algoritmo. Administrar los accesos a datos compartidos por m´ ultiples procesadores. Sincronizar los procesos en algunas etapas de la ejecuci´on en paralelo. 1

Cada vez es m´ as dif´ıcil mejorar el rendimiento aumentando la frecuencia debido al aumento en el consumo de energ´ıa y consecuentemente de generaci´ on de calor.

8

2.1.1.

Descomposici´ on y dependencia de tareas

El proceso de dividir un problema en subproblemas m´as peque˜ nos (tareas) los cuales potencialmente pueden ser ejecutados en paralelo se conoce como descomposici´ on. El programador define en cu´ales y en cu´antas tareas se divide el problema principal; ´estas pueden tener diferente tama˜ no, pero una vez definidas, deben considerarse como una unidad indivisible. La ejecuci´on simult´ anea de m´ ultiples tareas es la clave para reducir el tiempo requerido para resolver un problema entero. En general hay tareas que pueden ser ejecutadas a la vez o en cualquier orden, son independientes, sin embrago, existen algunas que necesitan datos producidos por otras tareas por lo que puede ser necesario esperar a que estas finalizen, esto se conoce como sincronizaci´ on.

2.1.2.

Granularidad y concurrencia

El n´ umero y el tama˜ no de las tareas en las cuales un problema se descompone determina la granularidad de la descomposici´on. Si el problema se descompone en un gran n´ umero de tareas peque˜ nas se dice que la descomposici´on es fina y si se descompone en pocas tareas de gran tama˜ no se dice que la descomposici´on es gruesa. Un concepto importante y relacionado con la granularidad es el n´ umero m´aximo de tareas que pueden ser ejecutadas simult´aneamente por un programa en cualquier momento, esto se conoce como grado m´ aximo de concurrencia. En la mayor´ıa de los casos es menor que el n´ umero total de tareas debido a la dependencia entre tareas. Un indicador m´as u ´til para medir el desempe˜ no de un algoritmo en paralelo es el grado promedio de concurrencia, el cual es el n´ umero promedio de tareas que pueden ejecutarse simult´ aneamente durante la ejecuci´on del programa. Ambos, el grado m´aximo de concurrencia y el grado promedio de concurrencia usualmente aumentan a medida que la granularidad se hace m´as fina. Esto nos podr´ıa hacer pensar que el tiempo requerido para resolver un problema puede ser reducido simplemente incrementando la granularidad de la descomposici´on con el fin de realizar m´as y m´as tareas en paralelo, pero esto no es lo que sucede en la pr´actica, pues existe una cota inherente que establece que tan fina puede ser la descomposici´on de un problema. Otro factor que limita la granularidad y el grado de concurrencia es la interacci´ on entre las tareas que est´an en ejecuci´on. A menudo las tareas comparten entradas, salidas o datos intermedios. Esta dependencia es usualmente el resultado de que una salida de una tarea es la entrada de otra tarea.

2.2.

T´ ecnicas de descomposici´ on

Como ya mencionamos, uno de los pasos fundamentales para dise˜ nar un algoritmo en paralelo es dividir los c´alculos a realizar en un conjunto de tareas que se ejecutar´an simult´ aneamente. Existen muchas t´ecnicas de descomposici´on pero ninguna garantiza que el algoritmo resultante sea el mejor algoritmo paralelo para resolver un problema determinado. A pesar de esta deficiencia, utilizar una de las t´ecnicas de descomposici´on o una combinaci´ on de ellas a menudo proporciona una descomposici´on eficaz.

9

2.2.1.

Descomposici´ on recursiva

Es un m´etodo para inducir la concurrencia que puede ser aplicado a problemas que pueden resolverse mediante la estrategia de divide y vencer´ as. En esta t´ecnica, un problema se resuelve dividi´endolo en un conjunto de subproblemas independientes. Cada uno de estos subproblemas se resuelve de forma recursiva mediante la aplicaci´on de una divisi´on similar en peque˜ nos subproblemas, seguido de una combinaci´on de sus resultados.

2.2.2.

Descomposici´ on de datos

La descomposici´on de datos es un t´ecnica com´ unmente utilizada para inducir la concurrencia en algoritmos que trabajan sobre grandes estructuras de datos. En este m´etodo, la descomposici´on de los c´alculos se realiza en dos etapas. En la primera etapa, los datos sobre los que se realizar´an los c´alculos se particionan, y en la segunda etapa, estas particiones de datos se utilizan para inducir una divisi´on de los c´alculos en tareas. Las operaciones que realizan estas tareas en diferentes particiones de datos suelen ser similares La partici´on de datos se puede realizar de muchas formas; en general, hay que explorar y evaluar todas las formas posibles de dividir los datos y determinar cu´al de ellas produce una descomposici´on natural y eficiente.

2.2.3.

Descomposici´ on exploratoria

Se utiliza para descomponer problemas en los cuales los c´alculos subyacentes corresponden a una b´ usqueda sobre un espacio de soluciones. En la descomposici´on exploratoria se particiona el espacio de b´ usqueda en subespacios m´as peque˜ nos y se explora simult´ aneamente en cada uno de estos subespacios, hasta que las soluciones deseadas se encuentran.

2.2.4.

Descomposici´ on h´ıbrida

Las t´ecnicas de descomposici´on anteriores no son exclusivas y a menudo se pueden combinar entre s´ı. Con frecuencia un c´alculo se puede dividir en m´ utiples etapas a las cuales se les puede aplicar diferentes tipos de descomposici´on. Hoy en d´ıa es muy dif´ıcil desarrollar un programa paralelo de forma autom´atica. Por esto, se debe escoger el modelo apropiado, o una mezcla de ellos, para implementar un algoritmo dado.

2.3.

Modelos de programaci´ on paralela

Un modelo de programaci´on paralela es un conjunto de tecnolog´ıas hardware y software que permiten implementar algoritmos paralelos en la arquitectura adecuada. Desde el punto de vista del uso de la memoria existen tres modelos: los de memoria compartida (OpenMP), los de memoria distribuida (MPI, PVM) y los modelos h´ıbridos.

2.3.1.

MPI

MPI (Message Passing Interface) es un protocolo de comunicaci´ on entre computadoras. Es un est´andar que define la sintaxis y sem´antica de las funciones contenidas en una biblioteca usada

10

para la comunicaci´on entre los distintos nodos que ejecutan un programa en un sistema de memoria distribuida. El paso de mensajes es una t´ecnica empleada en programaci´on concurrente que permite sincronizar procesos. Su principal caracter´ıstica es que no requiere de memoria compartida, por lo que se usa en la programaci´on de sistemas distribuidos. El programador expl´ıcitamente divide el trabajo y los datos entre varios procesos y debe gestionar la comunicaci´ on entre ellos. Los elementos principales que intervienen en el paso de mensajes son el proceso que env´ıa, el que recibe y el mensaje. Dependiendo de si el proceso que env´ıa el mensaje espera a que el mensaje sea recibido, se puede hablar de paso de mensajes sincr´onico o asincr´onico. En el paso de mensajes asincr´onico, el proceso que env´ıa no espera a que el mensaje sea recibido, y contin´ ua su ejecuci´on, siendo posible que vuelva a generar un nuevo mensaje y a enviarlo antes de que se haya recibido el anterior. Por este motivo es necesario sincronizar procesos: el proceso que env´ıa mensajes s´olo se bloquea o se detiene cuando finaliza su ejecuci´on. En el paso de mensajes sincr´onico, el proceso que env´ıa el mensaje espera a que un proceso lo reciba para continuar su ejecuci´on [2]. Las implementaciones de MPI son un conjunto de bibliotecas de rutinas que pueden ser utilizadas en programas escritos en los lenguajes de programaci´on como: C, C++ y Fortran. La ventaja de MPI sobre otras bibliotecas de paso de mensajes, es que los programas que utilizan la biblioteca son r´apidos (pues la implementaci´on de la biblioteca ha sido optimizada para el hardware en la cual se ejecuta) y portables (pues MPI ha sido implementado para casi todas las arquitecturas de memoria distribuida).

2.3.2.

Posix Threads

POSIX Threads, o simplemente Pthreads es un est´andar para la programaci´on de aplicaciones multi-hilo. Existen implementaciones pr´acticamente para todos los sistemas operativos. En lenguajes de programaci´on como C/C++ y C# se implementa como una biblioteca que incluye tipos, funciones y constantes que permiten crear y manipular hilos, los cuales son usados para efectuar tareas simult´aneas dentro de un mismo proceso. El uso de hilos es m´as efectivo en sistemas con varios procesadores o multi-n´ ucleo, pues el flujo del proceso puede ser programado de forma tal que se beneficie del paralelismo o procesamiento distribuido.

2.3.3.

OpenMP

OpenMP es una interfaz de programaci´on de aplicaciones (API) usada para la programaci´on multiproceso de memoria compartida. Est´a disponible para muchas arquitecturas, incluidas las plataformas de UNIX, Microsoft Windows y Mac OS X. Se compone de un conjunto de directivas de compilaci´on, rutinas de biblioteca, y variables de entorno que afectan el comportamiento de un programa en tiempo de ejecuci´on. Esta aproximaci´on es completamente flexible, si bien requiere un mayor trabajo del programador. Puede ser empleada en arquitecturas de memoria distribuida e incluso en redes de computadores, y tambi´en en arquitecturas de memoria compartida, aunque en ese caso los diferentes procesos utilizan partes de memoria independientes y separadas. OpenMP es un modelo de programaci´on portable y escalable que proporciona a los programadores una interfaz simple y flexible para el desarrollo de aplicaciones paralelas, tanto para computadoras de escritorio como supercomputadoras. Se fundamente en el modelo fork-join en donde una tarea

11

muy pesada se divide en k subtareas (hilos) de menor peso (fork), para luego unir estos resultados parciales (join) en una respuesta final. Cuando se incluye una directiva de OpenMP el bloque de c´odigo se marca como paralelo y se lanzan hilos seg´ un la caracter´ıstica de la directiva y al final de ella se sincronizan los resultados para los diferentes hilos [11]. Se pueden construir aplicaciones con un modelo de programaci´on paralela h´ıbrida usando MPI y OpenMP, o a trav´es de las extensiones de OpenMP para los sistemas de memoria distribuida. Estas aplicaciones se ejecutan en un cluster de computadoras [9]. De estos modelos de programaci´on elegimos OpenMP por tratarse de un modelo de memoria compartida que mejor se adapta al problema de estudio y adem´as porque tenemos acceso directo a un computador en que podemos realizar la implementaci´ on bajo este esquema.

2.4.

M´ etricas para evaluar el desempe˜ no de un sistema paralelo

Usualmente un algoritmo secuencial es evaluado en t´erminos de su tiempo de ejecuci´on, el cual se expresa como una funci´on del tama˜ no de la entrada. Por otro lado, la estimaci´on del tiempo de ejecuci´on de un algoritmo paralelo es m´as complicado, pues no solo depende del tama˜ no de la entrada, sino que se deben considerar factores como el n´ umero de procesadores y par´ametros de comunicaci´ on, tales como la manera en que esta´ n interconectados los procesadores entre s´ı y con los m´odulos de memoria. Esto hace que se deba considerar como un sistema paralelo, compuesto por el algoritmo y la arquitectura en la cual se ejecutar´a [8]. Existen algunas m´etricas intuitivas para evaluar el desempe˜ no de un sistema paralelo. Tal vez, la m´as simple es el tiempo reloj que tom´o resolver una instancia de un problema dado en un sistema paralelo, pero esta medida tiene el inconveniente de que no puede ser extrapolada a otras instancias del problema o a otra configuraci´on de equipo m´as grande. Por esta raz´on, son necesarias m´etricas m´as complejas que permiten cuantificar y extrapolar el desempe˜ no de un sistema paralelo. Con este fin se han propuesto algunas m´etricas como las de speedup (aceleraci´on) y la eficiencia. Estas m´etricas intentan responder a preguntas como: 1. ¿Qu´e algoritmo es m´as r´apido entre varias alternativas? 2. ¿Qu´e tan beneficioso es resolver el problema en paralelo? 3. ¿C´omo se comporta el algoritmo al variar alguna de las caracter´ısticas del equipo o del problema?

2.4.1.

Speedup

Cuando evaluamos un sistema paralelo a menudo estamos interesados en conocer cu´anto desempe˜ no se logra al paralelizar una aplicaci´on respecto a una implementaci´ on secuencial. El speedup es una medida que refleja el beneficio de resolver un problema en paralelo. Se define como el cociente del tiempo que toma resolver una instancia de un problema con un s´olo procesador entre el tiempo que toma resolver la misma instancia del problema en paralelo con p procesadores id´enticos, es decir, T1 Sp = Tp

12

donde p es el n´ umero de procesadores, T1 es el tiempo de ejecuci´on del algoritmo secuencial y Tp es el tiempo de ejecuci´on del algoritmo paralelo usando p procesadores. El speedup responde a la pregunta ¿qu´e tan beneficioso es resolver el problema de forma paralela? y t´ıpicamente es un valor entre 0 y p. El speedup ideal o lineal se obtiene cuando Sp = p, esto quiere decir que al trabajar con p procesadores, el problema se resolver´ a p veces m´as r´apido comparado con el mejor algoritmo secuencial. Te´oricamente, el speedup nunca excede el n´ umero de procesadores pero algunas veces se presenta un aumento de velocidad mayor a p utilizando p procesadores, es decir, Sp > p, esto se conoce como superlinear speedup y se debe a ciertas caracter´ısticas del hardware presente en las computadoras modernas [8]. Dependiendo de como se calcule T1 se habla de: Speedup absoluto: si T1 se calcula con el mejor algoritmo secuencial conocido. Speedup relativo: si T1 se calcula ejecutando el algoritmo paralelo con un s´olo procesador.

2.4.2.

Eficiencia

S´olo en un sistema paralelo ideal con p procesadores se puede esperar un speedup igual a p. En la pr´actica, el comportamiento ideal no se alcanza porque durante la ejecuci´on del algoritmo paralelo, los procesadores no est´an dedicando el 100 % de su capacidad a los calculos que demanda el algoritmo. La eficiencia (E) es una medida de la fraccci´on de tiempo durante la cual los procesadores son usados con eficacia. Se define como la raz´on del speedup (Sp ) entre el n´ umero de procesadores p. En un sistema paralelo ideal se tiene que Sp = p con lo cual E = 1, pero como en la pr´actica Sp < p tenemos que 0 < E < 1, dependiendo de la eficacia con la cual son usados los procesadores. Matem´aticamente la eficiencia es E=

2.4.3.

Sp T1 = p p · Tp

Escalabilidad

Con frecuencia los algoritmos dise˜ nados se prueban en instancias relativamente peque˜ nas y usando pocos procesadores. Sin embargo, estos algoritmos intentan resolver problemas mucho m´as grandes y en equipos con un gran n´ umero de procesadores. Mientras que el desarrollo de c´odigo se ve simplificado al usar versiones reducidas del problema y de la m´aquina su desempe˜ no y exactitud son mucho m´as dif´ıciles de determinar. Se dice que un sistema paralelo es escalable si es capaz de usar de forma satisfactoria un n´ umero creciente de procesadores. Se utilizar´an las m´etricas de speedup y eficiencia para medir el desempe˜ no de los algortimos desarrollados.

13

Cap´ıtulo 3

An´ alisis de resultados 3.1.

Algoritmos

Los algoritmos en paralelo dise˜ nados e implementados para resolver o aproximar el problema propuesto son recursivos, tanto el determin´ıstico como el heur´ıstico. La base de la recursi´on es el caso m = 1, el cual consiste en resolver el siguiente problema: se minimize b

(3.1)

sujeto a s1 + · · · + sn = c si · b ≥ di

(3.2) i = 1, . . . , n,

(3.3)

b∈N

(3.4)

si ∈ {1, . . . , c}

(3.5)

El algoritmo UnRecipiente resuelve el problema de manera ´optima. Toma como entrada el n´ umero n de objetos distintos, la capacidad c del recipiente, y el vector de requerimientos para cada uno de los objetos d = [d1 , d2 , . . . , dn ], tal que c ≥ n. La salida del algoritmo es la tupla (b∗ , s = [s1 , s2 , . . . , sn ]), donde b∗ es la soluci´on ´optima para el problema y s determina el n´ umero de repeticiones de cada objeto en el recipiente. Algoritmo UnRecipiente (n, c, d) 1 2 3 4 5 6

si ← 1 para i ← 1, . . . , n para c0 ← n + 1 hasta c: encuentra j tal que ddj /sj e = m´ax{ddi /si e | i = 1, . . . , n} sj ← sj + 1 ∗ b ← m´ax{ddi /si e | i = 1, . . . , n} regresa (b∗ , s)

El an´alisis del tiempo de ejecuci´on del Algoritmo UnRecipiente consiste en el an´alisis del ciclo de la instrucci´on 2, el cual se ejecuta c − n veces; dentro de dicho ciclo, encontrar el ´ındice j requerido en la instrucci´on 3 toma tiempo n; lo dem´as toma tiempo constante. Por lo tanto, el tiempo de ejecuci´on del Algoritmo UnRecipiente es de Θ(n(c − n)). Dicho algoritmo es un algoritmo avaro (greedy), muy eficiente, por lo que no se consider´o necesario dise˜ nar e implementar una paralelizaci´on del mismo. 14

En ambos casos (tanto para el heur´ıstico como para el determin´ıstico), solamente la primera recursi´on se resuelve en paralelo mediante la t´ecnica de descomposici´on exploratoria; el resto de casos se resuelve de manera secuencial, pues el trabajo ya se est´a realizando en paralelo en cada uno de los procesadores. Por lo que se presenta primero la soluci´on secuencial para cada uno de los problemas. Para el heur´ıstico se tienen dos algoritmos secuenciales, ambos comparten la misma filosof´ıa, pero en uno de ellos (Heur-FullSolve) se analizan todos los casos posibles, mientras que en el otro (Heur-Solve) solo se exploran de forma adecuada algunos de ellos. Algoritmo Heur-Solve (n, m, c, d) 1 2 3 4 5 6 7 8 9 10 11 12 13 14

si m = 1: regresa UnRecipiente (n, c, d) determinar xm´ın y xm´ax (rango de la b´ usqueda) 0 0 0 0 sea q = [q1 , . . . , qn×c ] donde qi+(j−1)·n ← ddi /je; i = 1, . . . , n; j = 1, . . . , c sea q = [q1 , . . . , qk ] ⊂ q0 donde xm´ın ≤ qi ≤ xm´ax ; i = 1, . . . , k x∗ ← xm´ın · m para algunos qi ∈ q b1 ← qi para algunos s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c sea d0 = [d1 , . . . , dn0 ] donde (d0i0 ← di − si · b1 ) > 0 (b0 , S 0 ) ← Heur-Solve (n0 , m − 1, c, d0 ) si b1 + b01 + · · · + b0m−1 < x∗ : actualizar x∗ , b∗ , S ∗ regresa (b∗ , S ∗ )

Algoritmo Heur-FullSolve (n, m, c, d) 1 2 3 4 5 6 7 8 9 10 11 12 13

si m = 1: regresa UnRecipiente (n, c, d) determinar xm´ın y xm´ax x∗ ← xm´ın · m para cada s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c para i ← 1 hasta n: b1 ← ((t1 > 0) ? dd1 /t1 e : 0) si xm´ın ≤ b1 ≤ xm´ax : sea d0 = [d1 , . . . , dn0 ] donde (d0i0 ← di − si · b1 ) > 0 (b0 , S 0 ) ← Heur-FullSolve (n0 , m − 1, c, d0 ) si b1 + b01 + · · · + b0m−1 < x∗ : actualizar x∗ , b∗ , S ∗ ∗ ∗ regresa (b , S )

En el algoritmo determin´ıstico secuencial (Deterministico) se utiliza el heur´ıstico HeurSolve, que es m´as r´apido pero cuya soluci´on por lo general est´a m´as lejana de la ´optima. Para la paralelizaci´on del heur´ıstico se utiliz´o como base Heur-FullSolve, que se ejecuta de 15

Algoritmo Deterministico (n, m, c, d) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

si m = 1: regresa UnRecipiente (n, c, d) determinar xm´ın y xm´ax (b∗ , S ∗ ) ← Heur-Solve (n, m, c, d) x∗ = b∗1 + · · · + b∗n para cada s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c b1 ← xm´ax mientras b1 ≥ xm´ın sea d0 = [d1 , . . . , dn0 ] donde (d0i0 ← di − si · b1 ) > 0 (b0 , S 0 ) ← Deterministico (n0 , m − 1, c, d0 ) t ← b1 + b01 + · · · + b0m−1 si t < x∗ : actualizar x∗ , b∗ , S ∗ ∆ ← t − x∗ b1 ← b1 − ∆ − 1 regresa (b∗ , S ∗ )

manera recursiva. La directiva #pragma se utiliz´o en el pseudoc´odigo para mostrar construcciones especiales en paralelo. La directiva #pragma omp parallel indica el inicio de un bloque en paralelo, mientras que la directiva #pragma omp critical indica una secci´on de c´odigo que solamente puede ser ejecutada por uno de los procesadores a la vez. Lo fundamental en el dise˜ no de un algoritmo en paralelo es realizar una distribuci´on eficiente del trabajo. En este caso, lo que se busca es repartir de manera eficiente las distintas permutaciones que se deben analizar entre los diferentes procesadores; para ello, lo mejor es que la repartici´on de permutaciones se realice de manera global por medio de una funci´on. Cada vez que un procesador finaliza su tarea solicita a esta funci´on una nueva permutaci´ on para continuar trabajando, esto hace que este proceso deba sincronizarse lo cual puede generar un efecto de embudo en la llamada a la funci´on que asigna las permutaciones, sobre todo para instancias peque˜ nas del problema. En el caso de guardar la soluci´on ´optima, y para evitar el problema del cuello de botella mencionado, el algoritmo se implement´ o de manera que cada procesador guarda el ´optimo local de la soluci´on correspondiente a cada una de las permutaciones que explor´o. Luego, al final, se utiliza nuevamente la directiva #pragma omp critical, para escoger el ´optimo global de entre todos los ´optimos locales hallados por cada procesador. El algoritmo determin´ıstico en paralelo, igual que en el caso heur´ıstico, utiliza la directiva #pragma omp critical para obtener la permutaci´ on respectiva. Pero en este caso, como el trabajo que se realiza depende del ´optimo que se tenga (mientras mejor sea el ´optimo, menos trabajo se realiza), es mejor siempre tener un ´optimo de manera global. Por ello el ´optimo se define afuera de la directiva #pragma omp parallel, por lo que es un valor global. Pero entonces, para actualizarlo, se requiere de la directiva #pragma omp critical. Esto podr´ıa representar una desventaja por el efecto de embudo comentado anteriormente, pero esto es m´as probable que se presente para instancias peque˜ nas del problema, y/o con muchos procesadores.

16

Algoritmo Heur-Paralelo (n, m, c, d) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

determinar xm´ın y xm´ax #pragma omp parallel x∗ ← xm´ın · m #pragma omp critical obtener s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c hasta agotar las permutaciones haga: para i ← 1 hasta n: b1 ← ((t1 > 0) ? dd1 /t1 e : 0) si xm´ın ≤ b1 ≤ xm´ax : sea d0 = [d1 , . . . , dn0 ] donde (d0i0 ← di − si · b1 ) > 0 (b0 , S 0 ) ← Heur-FullSolve (n0 , m − 1, c, d0 ) si b1 + b01 + · · · + b0m−1 < x∗ : actualizar x∗ , b∗ , S ∗ #pragma omp critical obtener s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c #pragma omp critical escoger la mejor solucion (b∗ , S ∗ ) regresa (b∗ , S ∗ )

Algoritmo Deterministico-Paralelo (n, m, c, d) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

determinar xm´ın y xm´ax (b∗ , S ∗ ) ← Heur-Paralelo (n, m, c, d) x∗ ← b∗1 + · · · + b∗m #pragma omp parallel #pragma omp critical obtener s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c hasta agotar las permutaciones haga: b1 ← xm´ax mientras b1 ≥ xm´ın sea d0 = [d1 , . . . , dn0 ] donde (d0i0 ← di − si · b1 ) > 0 (b0 , S 0 ) ← Deterministico (n0 , m − 1, c, d0 ) t ← b1 + b01 + · · · + b0m−1 #pragma omp critical si t < x∗ : actualizar x∗ , b∗ , S ∗ ∆ ← t − x∗ b1 ← b1 − ∆ − 1 #pragma omp critical obtener s1 = [s1 , . . . , sn ]T ; si = 0, . . . , m´ın(c, ddi /xm´ın e); s1 + · · · + sn = c regresa (b∗ , S ∗ ) 17

3.2.

Experimentos

Se construy´o un conjunto de instancias de prueba, algunas de las cuales se muestran, junto con su respectiva soluci´on, en el ap´endice A. Cada instancia fue ejecutada con los algoritmos HeurParalelo y Deterministico-Paralelo en un computador con las siguientes caracter´ısticas: 24 GB de memoria RAM DDR3 1333MHz y 2 procesadores Intel 6-Core Xeon X5650 (2.66 GHz Nehalem) cada uno con 12 MB de memoria cach´e L3. Como se coment´o anteriormente en el an´alisis del problema, la complejidad del mismo depende de 3 par´ametros: el n´ umero n de demandas, el n´ umero m de tipos recipientes, y de c, que es la capacidad de cada recipiente. Para analizar el comportamiento de los algoritmos en paralelo es importante analizar instancias del problema de diversos tama˜ nos, por lo que se consider´o analizar cada algoritmo, variando solamente uno de los 3 par´ametros en cada caso. Para medir el desempe˜ no de los algoritmos se utilizaron las siguientes m´etricas: el speedup relativo y la eficiencia, con 1 hasta 12 procesadores. Se consider´o importante mostrar los tiempos de ejecuci´on para mostrar el comportamiento del problema con respecto a la variaci´on de los par´ametros (n, m y c), y para complementar el an´alisis de las m´etricas utilizadas (speedup relativo y eficiencia). Para los gr´aficos del speedup relativo, se ha incluido la recta y = x, que indica el comportamiento ideal de un algoritmo en paralelo. Lo usual es que los resultados est´en por debajo de la recta, pero en algunos casos, como ya se mencion´o, podr´ıa suceder que los resultados est´en por encima de la recta, lo cual se conoce como super speedup. De igual manera, para los gr´aficos de eficiencia, se ha incluido la recta y = 1, que representa el comportamiento ideal de un algoritmo en paralelo.

18

Figura 3.1: Resultados de tiempos en t procesadores al resolver un problema con par´ametros n = 8, m = 4, y c = 3, 4, 5, 7, con el Algoritmo Deterministico-Paralelo. 3

c=3

3

3

3

3 3

3 3

2.5 2

3

8 Tiempo (s)

Tiempo (s)

3.5

c=4

6 3

4

3 3

2

3

3 3 3 3

3

1.5

3 3

3 3

3

3 3 3

0 0

2

4

6

8

10

12

0

2

4

N´ umero de CPU’s 3

c=5

120

3

80 3 3

40

3

20

8

3

6

100

60

6

10

12

N´ umero de CPU’s

Tiempo (×103 s)

140

Tiempo (s)

3

3 3 3 3 3 3 3 3

c=7

5 4 3

3

3

2

3

1

0

3

3 3 3 3 3 3 3 3

0 0

2

4

6

8

10

12

0

N´ umero de CPU’s

2

4

6

8

N´ umero de CPU’s

19

10

12

Figura 3.2: Speedup en el uso de t procesadores al resolver un problema con par´ametros n = 8, m = 4, y c = 3, 4, 5, 7 con el Algoritmo Deterministico-Paralelo. c=3 c=4 c=5 c=7

12

Speedup

10

3 + 2 ×

8 6 × 2 +

4 + 2 × + 2 × 3

2 3 2 × +

2 × +

× 2

× 2 +

+ 3

3

3

×

×

2 +

2 +

3

×

2 +

+

3 3

× 2 +

× 2

3

3

3

3

0 0

2

4

6

8

10

12

N´ umero de CPU’s

Figura 3.3: Eficiencia en el uso de t procesadores al resolver un problema con par´ametros n = 8, m = 4, y c = 3, 4, 5, 7 con el Algoritmo Deterministico-Paralelo. 3 2 × +

1

+ 2 × 3

+ 2 ×

0.8

2 × +

× 2 +

× 2

× 2 +

Eficiencia

+

× 2 +

× 2

0.4

× ×

0.6 3

×

+

2 +

2 +

3 c=3 c=4 c=5 c=7

0.2

2 +

3 + 2 ×

3

3

3 3

3

3

3 3

0 0

2

4

6

8

N´ umero de CPU’s

20

10

12

Figura 3.4: Resultados de tiempos en t procesadores al resolver un problema con par´ametros n = 8, m = 5, y c = 4, 5, 6, 8 con el Algoritmo Heur-Paralelo. 0.4

3

3 8

3

0.3 0.25 3 0.2

3 3 3

0.15 2

4

6

3 3 3 3 3 8

10

6 3 3 3

0

2

4

Tiempo (×103 s)

Tiempo (s)

20

3

3

100 80

3

60

3 3 3 3

40 20

3

6

8

10

12

N´ umero de CPU’s

c=6

3

3 3 3 3 3 3 3

2

12

N´ umero de CPU’s 120

3

3

4 3

0

c=5

3

Tiempo (s)

Tiempo (s)

0.35

c=4

3 3 3 3

3

c=8

3

15 10

3 3

5

3

3 3 3 3 3 3 3 3

0 0

2

4

6

8

10

12

0

N´ umero de CPU’s

2

4

6

8

N´ umero de CPU’s

21

10

12

Figura 3.5: Speedup en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 8, m = 5, y c = 4, 5, 6, 8 con el Algoritmo Heur-Paralelo. c=4 c=5 c=6 c=8

12

Speedup

10

3 + 2 ×

×

×

×

8 ×

6 × 4 × 2 3 2 × +

× 3 + 2

2 + 3

× 2

× + 2 3

2 + 3

×

×

2 + 3

2 + 3

+ 3

2 + 3

2

2

+ 3

+ 3

2 + 3

0 0

2

4

6

8

10

12

N´ umero de CPU’s

Figura 3.6: Eficiencia en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 8, m = 5, y c = 4, 5, 6, 8 con el Algoritmo Heur-Paralelo. 3 2 × +

1

×

× ×

× ×

×

× ×

×

×

Eficiencia

0.8 0.6

+ 3 2

2 + 3

× + 2 3

0.4

2 + 3

2 + 3

c=4 c=5 c=6 c=8

0.2

3 + 2 ×

2 2 + 3

+ 3

2 + 3

2

2

+ 3

+ 3

2 + 3

0 0

2

4

6

8

N´ umero de CPU’s

22

10

12

Figura 3.7: Resultados de tiempos en t procesadores al resolver un problema con par´ametros n = 4, 8, 12, 16, m = 3, y c = 10 con el Algoritmo Deterministico-Paralelo. 3

n=4

3

n=8

3

3

15 Tiempo (s)

Tiempo (s)

2 1.5 1

3 3 3

0.5

3

3 3 3

3 3

10 3

5

3

3 3

3 3 3 3 3 3 3 3 3

0 0

2

4

6

8

10

12

0

2

4

N´ umero de CPU’s n = 12

3

8

3 Tiempo (×103 s)

Tiempo (s)

400 300 200

3 100

3

3

3

4

6

8

10

12

10

12

4 3 2

3

0

N´ umero de CPU’s

3

2

4

3 3 3 3 3 3 3 3 6

8

N´ umero de CPU’s

23

3

6

0 2

8

n = 16

3 3 3 3 3 3 3 3

0 0

6

N´ umero de CPU’s

10

12

Figura 3.8: Speedup en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 4, 8, 12, 16, m = 3, y c = 10 con el Algoritmo Deterministico-Paralelo. 16 n=4 n=8 n = 12 n = 16

14 12

3 + 2 ×

×

Speedup

10

2 ×

8 2 × +

6

2 × + 2 × + 3

4

3

× + 2

×

+

3

3

3

3

×

2

2

+

3 2 × +

2

2 ×

× 2

+ 3

+ 3

+ 3

2 + 3

3 2 × + 0 0

2

4

6

8

10

12

N´ umero de CPU’s

Figura 3.9: Eficiencia en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 4, 8, 12, 16, m = 3, y c = 10 con el Algoritmo Deterministico-Paralelo. 1.4 × + 3 2 1.2

2 × +

2 × +

3

× + 2

2 ×

2 ×

× 2

+

3

3 2 × +

1 Eficiencia

× 2 +

× 2

×

×

3 3

0.8

+

0.6

+

0.4

n=4 n=8 n = 12 n = 16

0.2

3

3 + 2 ×

3

3

+ 3

2

2

+ 3

+ 3

0 0

2

4

6

8

N´ umero de CPU’s

24

10

12

Figura 3.10: Resultados de tiempos en t procesadores al resolver un problema con par´ametros n = 4, 8, 12, 16, m = 3, y c = 10 con el Algoritmo Heur-Paralelo. 1.4 n=4

3

3 3

1

3

0.8

3 3

3 3

0.6

3

3

3

3

3

n=8

3

2 Tiempo (s)

Tiempo (ms)

1.2

3

2.5

1.5 1

3 3

0.5

3 3 3 3 3 3 3 3 3

0 0

2

4

6

8

10

12

0

2

N´ umero de CPU’s 3

250

n = 12

6

3

6

8

10

12

3

n = 16

3

Tiempo (×103 s)

5

200 Tiempo (s)

4

N´ umero de CPU’s

150 3

100

3

50

3

0 0

2

4

8

10

3 3

2

3

1

3 3 3 3 3 3 3 3 6

4

3

0

12

0

N´ umero de CPU’s

2

4

3 3 3 3 3 3 3 3 6

8

N´ umero de CPU’s

25

10

12

Figura 3.11: Speedup en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 4, 8, 12, 16, m = 3, y c = 10 con el Algoritmo Heur-Paralelo. n=4 n=8 n = 12 n = 16

14 12

3 + 2 ×

2 × 2 ×

Speedup

10

2 ×

8 2 × +

6

2 × +

+

× 2 +

4 2 3 2 × +

2 × + 3

3

3

3

3

×

2

×

+

2 + ×

3

3

×

2

2 +

+

+

+

3

3

3

3

0 0

2

4

6

8

10

12

N´ umero de CPU’s

Figura 3.12: Eficiencia en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 4, 8, 12, 16, m = 3, y c = 10 con el Algoritmo Heur-Paralelo. × 2 +

1.4 × + 2

2 + ×

1.2

+

2 × +

2 ×

2 ×

+

× 2

2 ×

×

3 2 × +

1 Eficiencia

2 ×

3

0.8

× 2

3

0.6

+

3 0.4

n=4 n=8 n = 12 n = 16

0.2

3 + 2 ×

3

3

3

3

2

+

3

+

+

3

3

+

3

0 0

2

4

6

8

N´ umero de CPU’s

26

10

12

Figura 3.13: Resultados de tiempos en t procesadores al resolver un problema con par´ametros n = 8, m = 2, 3, 4, y c = 8 con el Algoritmo Deterministico-Paralelo. m=2

3

2.5

3

3 3 3

2

3

3

1.5

Tiempo (s)

3

3 3

m=3

3

1.5

3

3

1.2 0.9 0.6

3 3

3 3

0.3

3 3 3 3

3

3 3 3 3

0 0

2

4

6

8

10

12

0

2

4

N´ umero de CPU’s m=4

3

40 30 20

3 3

10

3

0 0

6

8

N´ umero de CPU’s 3

50 Tiempo (×103 s)

Tiempo (ms)

3

2

4

3 3 3 3 3 3 3 3 6

8

N´ umero de CPU’s

27

10

12

10

12

Figura 3.14: Speedup en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 8, m = 2, 3, 4, y c = 8 con el Algoritmo Deterministico-Paralelo. 3 + 2

m=2 m=3 m=4

14 12

2 2 2 2

10 Speedup

2

2

8 6 2 3 +

4

2 +

2 + 3

2 + 3

3

3

3 2 +

2

+

+ 3

+ 3

+ 3

3 +

+ 3

3 2 + 0 0

2

4

6

8

10

12

N´ umero de CPU’s

Figura 3.15: Eficiencia en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 8, m = 2, 3, 4, y c = 8 con el Algoritmo Deterministico-Paralelo. 2

1.4 3 2 + 1.2

3 +

2 +

2 +

3

3 2 +

1 Eficiencia

2 +

2

2

2

2

2

2

+

3 3

0.8 0.6

3

0.4

+ 3

+ 3

3 + 2

m=2 m=3 m=4

0.2

+ 3

3 +

+ 3

0 0

2

4

6

8

N´ umero de CPU’s

28

10

12

Figura 3.16: Resultados de tiempos en t procesadores al resolver un problema con par´ametros n = 8, m = 2, 3, 4, 5, y c = 8 con el Algoritmo Heur-Paralelo. 1.2 m=2

3

m=3

0.3

3

3 3

3

1

3

3

Tiempo (s)

Tiempo (ms)

1.1

3

3

3

0.9

3

3 3 3 3

0.2 3 0.1

3

3 3 3 3

0.8

3 3 3 3 3

0 0

2

4

6

8

10

12

0

2

4

N´ umero de CPU’s m=4

3

100

8

10

12

3

12

m=5

3

3

Tiempo (×103 s)

10

80 Tiempo (s)

6

N´ umero de CPU’s

60 40

3 3 3

20

8

3

6 3

4

3

2

3 3 3 3 3 3 3 3

0

3 3 3 3 3 3 3 3

0 0

2

4

6

8

10

12

0

N´ umero de CPU’s

2

4

6

8

N´ umero de CPU’s

29

10

12

Figura 3.17: Speedup en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 8, m = 2, 3, 4, 5, y c = 8 con el Algoritmo Heur-Paralelo. 3 + 2 ×

m=2 m=3 m=4 m=5

14 12

Speedup

10 8 2 +

6 4 2 3 2 × +

2 + × 3

× 3

×

× +

× 3

2 ×

+ 2 2 +

2 +

3

3

3

2

2

2 ×

2 ×

× 2

+

+

+

+

× +

3

3

3

3

3

×

0 0

2

4

6

8

10

12

N´ umero de CPU’s

Figura 3.18: Eficiencia en el uso de t procesadores en la resoluci´on de un problema con par´ametros n = 8, m = 2, 3, 4, 5, y c = 8 con el Algoritmo Heur-Paralelo. 2

1.4

2 + +

1.2

2 +

2 + 2

3 2 × +

1 Eficiencia

+ 2

0.8

×

× 3

0.6

×

×

2 ×

+

3

0.4

3 + 2 ×

m=2 m=3 m=4 m=5

0.2

×

3

3

3

3

× +

3

2 × +

3

× 2

2 ×

+

3

2

+

× +

3

3

0 0

2

4

6

8

N´ umero de CPU’s

30

10

12

3.3.

Discusi´ on de resultados

Al momento de analizar los resultados utilizando los tiempos de ejecuci´on de un algoritmo en paralelo, se debe tomar en cuenta que requiere considerar no solamente el algoritmo, sino adem´as el sistema o el equipo en el que son ejecutados. Esto hace que pueden variar de un equipo a otro debido a la configuraci´on del equipo; pero incluso, se pueden obtener variaciones en las medidas de los tiempos en un mismo equipo, debido a la administraci´on de memoria y de procesos que realice el equipo en el momento dado. De los experimentos realizados (Figuras 3.1, 3.4, 3.7, 3.10, 3.13, 3.16), el tiempo de ejecuci´on de ambos algoritmos heur´ıstico y determin´ıstico, crecen de manera exponencial al variar cualquiera de los par´ametros n, m y c. Este resultado es de esperarse, pues la dimensi´on del espacio soluci´on crece al aumentar cualquiera de estos par´ametros (Ecuaci´on 1.7). La eficiencia mide el uso que se hace de los procesadores. Los gr´aficos de eficiencia muestran que los algoritmos son capaces de distribuir el trabajo en forma adecuada. De los experimentos realizados (Figuras 3.3, 3.6, 3.9, 3.12, 3.15) se observa que los algoritmos dise˜ nados son escalables, en el sentido de que, a mayor tama˜ no del problema, se hace un uso m´as eficiente de los procesadores. Se observa que para instancias peque˜ nas (Figuras 3.1, 3.10, 3.13, 3.16), el uso de un mayor n´ umero de procesadores afecta de manera negativa el desempe˜ no del algoritmo, lo cual es natural, porque el acceso cr´ıtico a variables compartidas obliga a los procesadores a estar mayor tiempo ociosos, debido a la sincronazaci´on de procesos que debe hacerse; no as´ı para instancias grandes del problema, donde el uso de los procesadores es eficiente.

3.4.

Conclusiones

Los resultados muestran que fue posible realizar un dise˜ no en paralelo para resolver el problema propuesto, tanto de manera determin´ıstica como heur´ıstica. El modelo exploratorio para programaci´on en paralelo fue utilizado en el proceso de dise˜ no de los algoritmos para la soluci´on del problema planteado, y la biblioteca OpenMP mostr´o ser adecuada para la implementaci´on de los algoritmos dise˜ nados. Los experimentos realizados evidenciaron que el dise˜ no e implementaci´ on de los algoritmos en paralelo son escalables y eficientes para resolver instancias del problema propuesto. Los resultados sugieren que el algoritmo heur´ıstico puede redise˜ narse para mejorar su eficiencia seg´ un los distintos valores de n, m ´o c. Es decir, dependiendo de las magnitudes de los distintos valores, el algoritmo puede reorientarse para realizar una b´ usqueda m´as efectiva sobre el espacio soluci´on. En general, como se puede ver en los experimentos, el algoritmo dise˜ nado permite la soluci´on de un problema al menos 8x m´as r´apido que el algoritmo secuencial asociado; y en varios casos, hasta 10x m´as r´apido.

31

Ap´ endice A

Instancias de prueba Se presentar´an las instancias (junto con su respectiva soluci´on) de algunos de los problemas utilizados. Para escribir la soluci´on encontrada, se utilizar´a la notaci´on introducida en el Cuadro 1.1. En algunos casos, el algoritmo heur´ıstico encontr´ o el ´optimo, por lo que se presentar´ au ´nicamente la soluci´on ´optima.

A.1.

Problema 1

Valores de los par´ametros: n = 8; m = 4; c = 7. Soluci´on del heur´ıstico y determin´ıstico: 77362 84383 61612 16193 89653 79044 57246 34722

28128 1 3 0 0 0 2 0 1

20538 0 0 3 0 2 0 2 0

32

16193 1 0 0 1 3 1 1 0

6609 5 0 0 0 0 1 0 1

71468 4 1 2 0 2 14 23 15

A.2.

Problema 2

Valores de los par´ametros : n = 8; m = 5; c = 8. Soluci´on del heur´ıstico y determin´ıstico: 77362 84383 61612 16193 89653 79044 57246 34722

A.3.

21096 0 4 0 0 3 1 0 0

16193 1 0 2 1 0 0 3 1

14613 3 0 2 0 1 1 0 1

8667 2 0 0 0 0 5 1 0

1959 0 0 0 0 6 0 0 2

Problema 3

Valores de los par´ametros : n = 8; m = 3; c = 10. Soluci´on del heur´ıstico: 77362 84383 61612 16193 89653 79044 57246 34722

26348 2 2 0 0 1 3 1 1

15449 0 1 4 0 3 0 2 0

8479 3 2 0 2 2 0 0 1

50276 771 720 184 765 0 0 0 105

28817 0 1 2 0 3 2 2 0

17361 4 3 0 0 0 1 0 2

4049 2 1 1 4 1 1 0 0

50227 180 566 71 3 847 0 388 0

Soluci´on del determin´ıstico: 77362 84383 61612 16193 89653 79044 57246 34722

33

62528 4 1 0 0 2 0 0 2

A.4.

Problema 4

Valores de los par´ametros : n = 8; m = 4; c = 8. Soluci´on del heur´ıstico: 77362 84383 61612 16193 89653 79044 57246 34722

22414 2 1 1 0 4 0 0 0

16193 0 1 0 1 0 3 3 0

15259 1 3 2 0 0 2 0 0

8681 2 0 1 0 0 0 1 4

62547 87 1 1 0 3 53 14 2

20538 0 1 3 0 2 0 2 0

18529 3 1 0 0 0 3 0 1

16193 0 1 0 1 3 1 1 1

7281 3 4 0 0 0 1 0 0

62541 68 1 2 0 2 17 23 0

Soluci´on del determin´ıstico: 77362 84383 61612 16193 89653 79044 57246 34722

34

Bibliograf´ıa [1] Alba Enrique. Parallel Metaheuristics: A New Class of Algorithms. John Wiley & Sons, New Jersey, 2005. [2] Pacheco, Peter. Parallel Programming with MPI. Morgan Kaufmann Publishers, San Francisco, 1997. [3] Carrera, Luis-Ernesto. Algoritmo para encontrar el ´ optimo a una simplificaci´ on de un problema combinatorio presente en la industria editorial. Tesis para optar por el grado de MSc. en Matem´atica Computacional, CINVESTAV, M´exico, D.F, 2006. [4] Carrera, L. y Figueroa, G. Un problema tipo bin-packing. Tecnolog´ıa en Marcha 24(2), 2011. [5] Carrera, L. y Figueroa, G. Estudio de una variante del problema bin-packing. XVII International Symposium on Mathematical Methods Applied to the Sciences. San Jos´e-Costa Rica. Febrero. 2010. [6] Carrera, L. y Figueroa, G. Optimizaci´ on combinatoria, optimizaci´ on de Lipschitz y algoritmos evolutivos. Informe final de proyecto. VIE. Cartago-Costa Rica. Enero. 2010. [7] Hromkovi˜c. Algoritmics for Hard Problems. 2nd edici´on, Springer Verlag, Berlin, 2004 [8] Grama, A. Gupta, A. Karypis, G. Kumar, V. Introduction to Parallel Computing. 2 edici´on, Addison Wesley, New York, 2003. [9] Quinn, Michael. Parallel Programming in C with MPI and OpenMP. McGraw-Hill, Singapore, 2004. [10] Gibbons, Alan y Rytter, Wojciech. Efficient Parallel Algorithms. Cambridge University Press, New York, 1990. [11] Chapman, B. Jost, G. Van Der Pas, Ruud. Using OpenMP. MIT Press. Massachusetts. 2007. [12] Talbi, El-Ghazali (editor). Parallel Combinatorial Optimization. John Wiley & Sons, New Jersey, 2006. [13] Gonzalez, T. (editor). Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall, New York, 2007.

35