ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS PERFORMANCE ANALYSIS OF HASKELL IN THE EXECUTION OF ALGORITHMS PARALLELIZED WITH PRIMITIVE Alex Puertas González 1, Jorge Gabriel Hoyos Pineda 2 1 Universidad Santo Tomás Seccional Tunja, Colombia, [email protected], Calle 19 No 11-64 Tunja 2 Universidad Santo Tomás Seccional Tunja, Colombia, [email protected]

RESUMEN: Este documento presenta el análisis de los resultados de las pruebas de desempeño realizadas con Haskell en la ejecución de algoritmos en paralelo, utilizando las primitivas proporcionadas por este lenguaje de programación funcional. Este análisis se constituye en un resultado parcial de un proyecto de investigación que tiene como objetivo evaluar el desempeño de aplicaciones desarrolladas mediante programación funcional sobre hardware multicore. Para la prueba de desempeño se utilizó el algoritmo de generación de la serie Fibonacci paralelizado mediante primitivas, y se hicieron pruebas con diferente número de núcleos en una misma máquina. El análisis de los resultados obtenidos permitió comprobar la optimización del tiempo de procesamiento, hasta los límites permitidos por el programa y la máquina de pruebas. También se logró observar las implicaciones que esta clase de procesamiento tiene en el uso de las memorias primaria y secundaria en un computador. Palabras Clave: Programación funcional, Procesamiento paralelo, Haskell.

ABSTRACT: This paper presents the analysis of the results of performance tests conducted with Haskell in executing parallel algorithms, using the primitives provided by this functional programming language. This analysis constitutes a partial result of a research project that aims to evaluate the performance of applications developed using functional programming on multicore hardware. The performance tests were made with the algorithm for generating the Fibonacci series, which was parallelized using primitives, and their execution with different number of cores in a single machine. The analysis of the result allowed to verify the optimization of processing time, to the extent permitted by the program and the test machine. It was also possible to observe the implications in primary and secondary memory use, that this kind of processing have in the computer. KeyWords: Functional programming, Parallel processing, Haskell.

1. INTRODUCCIÓN El grupo de investigación GIDINT de la Universidad Santo Tomás seccional Tunja, viene desarrollando el proyecto denominado “Evaluación del desempeño de la programación funcional en hardware multicore”. El objetivo del proyecto es evaluar el desempeño de aplicaciones desarrolladas mediante programación funcional sobre hardware multicore, para el

logro del cual se propone desarrollar una investigación de tipo exploratoria cuasi experimental, compuesta por cuatro fases. La segunda fase contempla la realización de un estudio comparativo de los lenguajes de programación funcional. En el desarrollo de esta fase se seleccionaron cinco lenguajes de programación funcional para realizar el estudio comparativo, dos considerados puros (Haskell y Erlang) y tres considerados hibridos (Scala, Lisp y F#). Una vez realizada la comparación en términos

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”

Puertas, A.; Hoyos, J. | “ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS”

de sintaxis, codificación, compilación y ejecución, se procedió a examinar los mecanismos existentes en cada uno de los lenguajes, que hacen posible la paralelización de algoritmos. En el caso de Haskell, se evidencio la existencia de extensiones orientadas al procesamiento paralelo, que han surgido en respuestas a diferentes aspectos que afectan el desempeño de algoritmos que corren en paralelo. Sin embargo el equipo de investigación, considero importante utilizar las primitivas proporcionadas por el lenguaje, en las pruebas de desempeño iniciales. En la primera parte, se hace una breve introducción a la programación funcional y su relación con la programación paralela. En una segunda parte se habla del lenguaje funcional Haskell y se presentan los resultados parciales de las pruebas de desempeño en la ejecución de algoritmos en paralelo, que se han realizado hasta el momento con dicho lenguaje.

2. LA PROGRAMACIÓN FUNCIONAL La programación funcional es un paradigma de programación cuya esencia es la construcción de funciones como método de abstracción. El concepto de función aquí utilizado se acerca más a la noción matemática de función, que al concepto utilizado comúnmente en los lenguajes de programación [1]. En este paradigma las funciones son ciudadanas de primera clase, ya que en este paradigma un programa es una función en sí mismo, que puede estar compuesto de otras funciones que pueden utilizar a su vez otras funciones como parámetros o como resultado de la evaluación de las mismas [2]. Son muchas las bondades que se le atribuyen a la programación funcional y a los lenguajes de programación funcionales, entre ellas que son de más alto nivel que los lenguajes tradicionales, son más cercanos a la especificación, ausencia de efectos laterales, de rápida escritura, más concisos, facilitan la modularidad y el reuso, y además pueden ser ejecutados más fácilmente en arquitecturas paralelas [1],[3],[4]. Estas ventajas y las características propias de la programación funcional, se constituyen en herramientas que hacen posible que los programadores enfrenten de mejor forma la complejidad creciente del desarrollo de software [2].

2.1 La programación funcional paralela Una de las aplicaciones dónde se ha advertido una gran potencialidad para la implementación de la programación funcional, es la programación paralela a través de varios núcleos, en función de mejorar el rendimiento en el hardware moderno [5], lo que constituye un gran reto para los desarrolladores, quienes ahora tienen que pensar con la complejidad

adicional de este enfoque de programación. La gran mayoría de los lenguajes funcionales incluyen primitivas que facilitan la labor de paralelización. Se pueden utilizar dos tipos de paralelización, implícita y explicita. Adiconalmente, la paralelización puede generar efectos no deseados en cuanto al desempeño de los programas, por lo que han surgido para los diferentes lenguajes, librerías o complementos especializados en las tareas propias de paralelización.

3. HASKELL COMO LENGUAJE FUNCIONAL Haskell es un lenguaje de programación funcional de propósito general, que incorpora muchas de las innovaciones recientes en el diseño de lenguajes de programación [6]. Incorpora las características propias de los lenguajes funcionales como son las funciones de alto orden, los tipos de datos algebraicos, el emparejamiento de patrones, la evaluación perezosa, entre otras. Haskell surgió a partir del consenso de la comunidad de la programación funcional, sobre la necesidad de crear un lenguaje común, que recogiera el poder expresivo y los fundamento semánticos existentes en más de una docena de lenguajes funcionales puros existentes en el momento (1987), que posibilitara un uso más generalizado de los lenguajes funcionales en el desarrollo de todo tipo de aplicaciones [6]. La relevancia de Haskell radica en que se ha constituido en un estándar de facto, respaldado por la comunidad de programación funcional, ha sido uno de los lenguajes sobre los que más se ha investigado en la última década, y ha dado origen a muchas variantes, o nuevos lenguajes construidos sobre sus bases.

3.1 Haskell y paralelismo En [7] se mencionan dos elementos fundamentales para la implementación de la programación paralela en Haskell. En primer lugar, la granuralidad que busca dar un tamaño lógico a las subdivisiones de código, para así aprovechar las capacidades de los procesadores, y en segundo lugar, las dependencias de datos en la secuencialización de los programas en tiempo de ejecución, bien sea de forma explícita o implícita. Para el caso de [8] se enuncia el aprovechamiento de las ventajas de Haskell como lenguaje aplicable a soluciones multicore, en este caso teniendo en cuenta la vectorización de datos, en donde se transforma un programa que use datos en paralelismo anidado a otro que implemente datos paralelizados de tipo plano. Se conocen por lo menos dos extensiones para

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”

Puertas, A.; Hoyos, J. | “ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS”

Haskell orientadas al procesamiento paralelo, las cuales utilizan diferentes enfoques para aprovechar una arquitectura multicore. En [7] se presenta una comparación de dos implementaciones diferentes. La primera de ellas conocida como GpH, usa un mecanismo de memoria heap compartida físicamente. La segunda conocida como Eden, está diseñada para el uso en máquinas paralelas de memoria distribuida, donde existe una memoria heap independiente por cada núcleo y la comunicación entre núcleos se realiza mediante el intercambio de mensajes. Adicionalmente, en [9] se proponen cuatro constructos orientados a la arquitectura como una extensión orientada al procesamiento paralelo creada para el lenguaje Haskell, que aprovecha la información acerca del tamaño de las tareas, para controlar los datos de forma local y distribuir el trabajo.

4. PRUEBAS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS EN PARALELO Con el fin de realizar la prueba de implementación de la programación funcional paralela, como se ha mencionado anteriormente, se ha seleccionado el lenguaje de programación Haskell, teniendo en cuenta el algoritmo del par Fibonacci usando primitivas básicas de paralelismo, como puede apreciarse a continuación:

4.1 Algoritmo de prueba

donde se introduce al programa, el número para la ejecución del cálculo, en este caso como parámetro del mismo. En (3) se pueden observar las asignaciones para medir el tiempo inicial y final del proceso, y finalmente (4) muestra las dos líneas de impresión por pantalla del programa: la primera, en donde se ve el resultado de la operación Fibonacci y la segunda para el tiempo de procesamiento del mismo. Teniendo en cuenta lo anterior es posible observar el siguiente comportamiento en la consola de ejecución:

Figura. 2: Muestra de la ejecución del programa usando un núcleo

Para este particular, en (5) puede apreciarse la entrada del programa, compuesta por el nombre del mismo y dos parámetros de uso, el primero demarcado con +RTS, que especifica una variable para el compilador de Haskell, en este caso N1, en donde el número representa la cantidad de núcleos usados para el procesamiento del programa. El segundo, especificado con –RTS que define un parámetro de usuario para su utilización dentro del algoritmo codificado. Para este particular se usó el número 50 como base para el cálculo del par Fibonacci (GHC, 2014). Ahora bien, en (6) pueden observarse las dos líneas de impresión del programa, por un lado está el resultado de la operación para el número 50 y por el otro, el tiempo en segundos, de duración del procesamiento.

4.2 Condiciones iniciales

Figura. 1: Detalle del programa Fibonacci Paralelo Funcional

Para explicar el código de implementación del par Fibonacci desarrollado, en este caso denominado pfib.hs, se han numerado las secciones importantes de la siguiente forma: en (1) se encuentra la función principal para el cálculo del número, se ha implementado el algoritmo recursivo, dada la naturaleza de Haskell y la estandarización del código, en relación a las pruebas futuras en otros lenguajes de este tipo. En (2) se desarrolla una secuencia en

Por otro lado, para el desarrollo de la prueba se han seleccionado las siguientes condiciones iniciales, tanto de Hardware, como de software en función del procesamiento del algoritmo: Para el procesador se usó un AMD FX(tm)-8150 con cuatro procesadores físicos y un Reloj de CPU de 3600 MHz a 64 bits. Para la memoria principal se contó con una DDR3 de 8192 MB de capacidad en un solo canal a 1600 MHz. En cuanto al sistema operativo base, se usó un Microsoft Windows 7 Ultimate 6.1.7601 Service Pack 1 Compilación 7601 y finalmente la versión de Haskell implementada fue la GHC 7.10.2 del 29 de Julio de 2015.

4.3 Resultados de la prueba En función de desarrollar la prueba del algoritmo en paralelo usando Haskell, se procedieron a ejecutar 10 pruebas para cada uno de los procesadores,

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”

Puertas, A.; Hoyos, J. | “ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS”

teniendo en cuenta, tanto la paralelización mediante primitivas del lenguaje de programación, como las condiciones de máquina y software anteriormente citadas, teniendo en cuenta el cálculo estadístico correspondiente y la medida del tiempo de procesamiento en segundos:

condiciones iniciales de la prueba, se pudo observar el siguiente comportamiento respecto de estas variables:

Tabla I: Tiempos generales de ejecución por núcleo

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 Promedio

N1 2334,63 2280,13 1783,87 2119,51 2048,41 1978,12 1814,41 1854,45 2303,04 2283,89 2080,05 204,51 41824,87

N2 1193,82 1192,05 1192,49 1176,00 1180,60 1157,49 1167,53 1166,60 1177,57 1163,42 1176,76 12,35 152,59

N3 990,76 952,76 925,37 915,33 913,75 908,61 938,47 959,21 946,96 963,14 941,44 24,84 617,11

N4 762,88 823,78 810,44 771,71 770,31 761,90 764,44 820,76 760,86 865,46 791,25 34,54 1193,33

Es importante observar el ahorro en tiempo de procesamiento usando paralelización del proceso de acuerdo a los núcleos utilizados. También se puede notar la homogeneidad de las muestras tomadas para N2, de acuerdo a sus medidas de varianza y desviación estándar, las cuales, durante el desarrollo de la prueba, fueron las más bajas de todas las calculadas. Por otra parte es relevante decir que se evidencia la estabilización del proceso y aleja la noción de que un proceso, al ser procesado por N procesadores, será N veces más rápido en cuanto a su ejecución. Por otra parte, por cada una de las muestras tomadas, se tomaron medidas de la cantidad de procesadores usados por el proceso, el porcentaje de uso general de CPU, los subprocesos creados para el procesamiento, las memorias virtual, principal, compartida y privada para cada una de las iteraciones, como puede apreciarse a continuación: Tabla III: Datos de procesador y memoria por muestra

Con base en lo anterior y teniendo en cuenta las

Figura. 3: Uso de CPU y asignación de núcleos y subprocesos

En lo respectivo al procesamiento, el comportamiento es proporcional a la cantidad de núcleos utilizados por Haskell, ya que oscila entre el 13% lo cual representa un core de la máquina, hasta un 50% que evidencia el uso de todos los núcleos físicos de procesamiento. Es de notar también, la cantidad de subprocesos creados por el lenguaje de programación, dado su mecanismo de paralelización, de hecho se crea uno por cada N especificado. Lo anterior teniendo en cuenta la exclusión de los subprocesos propios de Haskell (5 en total). Con relación a los datos respectivos a la memoria usada por el algoritmo, se obtuvieron los comportamientos referenciados en la figura 4. Es de notar el comportamiento lineal de la memoria virtual asignada, la cual crece proporcionalmente a la creación de subprocesos para la ejecución del algoritmo. También puede notarse la asignación constante de memoria compartida para el proceso, debido a que su diferencia entre ejecuciones es relativamente pequeña, independientemente de los núcleos involucrados. Finalmente puede observarse un aumento en la cantidad de memoria privada asignada para el

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”

Puertas, A.; Hoyos, J. | “ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS”

proceso en función de los cores involucrados en este, lo cual corrobora el hecho de trabajar de forma paralela, de hecho, es posible realizar la suma entre la memoria compartida y la privada y se obtendría un dato relativo a la memoria principal asignada para cada caso.

Ahora bien, en función de observar el comportamiento del procesamiento paralelo, se ha generado el siguiente gráfico en donde se observa el promedio del tiempo de ejecución, contra la cantidad de núcleos de la máquina de prueba:

Figura. 5: Tiempo promedio de procesamiento por núcleo

Como puede apreciarse en la gráfica, existe un ahorro de tiempo sustancial entre las medidas tomadas para N1 y N2, en este caso de 1120,47 segundos, lo cual representa la mitad del tiempo de ejecución en estos dos casos, de hecho, es de notar que la suma de las diferencias de tiempo, entre núcleos a partir de N2 hasta N4 no es superior a la presentada entre los dos primeros, lo cual elimina la idea de un comportamiento directamente proporcional entre el tiempo de ejecución del proceso y los núcleos utilizados para la operación. Para observar la aceleración del proceso, se tendrá en cuenta el cociente entre la menor de las aplicaciones para un procesador (N1P4 =1783,87) y el resto de muestras. Para después realizar un promedio con los diez resultados por cada uno de los núcleos, derivando en la siguiente tabla: Tabla IIIII: Aceleraciones para el algoritmo recursivo de Fibonacci Paralelo N1 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 Promedio

Figura. 4: Uso de Memoria principal y secundaria

N2 0,76 0,78 1,00 0,84 0,87 0,90 0,98 0,96 0,77 0,78 0,87 0,09 0,01

N3 1,49 1,50 1,50 1,52 1,51 1,54 1,53 1,53 1,51 1,53 1,52 0,02 0,00

N4 1,80 1,87 1,93 1,95 1,95 1,96 1,90 1,86 1,88 1,85 1,90 0,05 0,00

2,34 2,17 2,20 2,31 2,32 2,34 2,33 2,17 2,34 2,06 2,26 0,10 0,01

Como puede verse, la aceleración promedio en el

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”

Puertas, A.; Hoyos, J. | “ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS”

procesamiento del algoritmo, es creciente hasta el estado N4 en donde se puede notar la máxima de la prueba, sin embargo no es directamente proporcional al número de núcleos de la máquina de cómputo, como puede apreciarse a continuación:

Figura. 6: Aceleración promedio de procesamiento por núcleo

Es así que se puede comprobar la optimización en el procesamiento del algoritmo Fibonacci usando programación paralela funcional a través de las herramientas de Haskell, sin tener en cuenta otras técnicas de desarrollo adicionales. Puede apreciarse que el crecimiento no es necesariamente lineal y que al final de la implementación tiende a estabilizarse, sin tener en cuenta la cantidad de núcleos involucrados en la operación.

5. CONCLUSIONES En este trabajo se ha podido desarrollar un algoritmo recursivo de forma funcional utilizando Haskell. Realizando esta prueba se ha podido comprobar la optimización del tiempo de procesamiento, hasta los límites permitidos por el programa y la máquina de pruebas. También se han observado las implicaciones que esta clase de procedimientos tienen en las memorias primarias y secundarias en un computador. Se ha podido comprobar la aceleración en el proceso y su comportamiento matemático. Por último se ha determinado el uso de procesador, la cantidad de subprocesos asociados al paralelismo mediante primitivas de Haskell en función del tiempo de procesamiento. También se puede anotar que se ha desarrollado un marco de trabajo para las futuras fases del proyecto de investigación, dados otros lenguajes funcionales puros e híbridos y las comparaciones respectivas entre ellos.

6. REFERENCIAS BIBLIOGRÁFICAS 1. Henderson P:"Software Engineer’s Reference Book", Elsevier;, 1991. 2. Gónzalez Osorio FA:"Programacion funcional: conceptos", Ing e Investig., pp. 65–71, . 3. Hudak P:"Conception, evolution, and application of functional programming languages", ACM Comput Surv [Internet]., Vol. 21, No. 3, pp. 359– 411, 1989 Sep 1;Available from: http://portal.acm.org/citation.cfm?doid=72551.72554 4. Hughes J:"Why Functional Programming Matters", Addison-Wesley;, 1990. 5. Pankratius V, Schmidt F, Garret G:"Combining Functional and Imperative Programming for Multicore Software : An Empirical Study Evaluating Scala and Java", pp. 123–33, 2012; 6. Marlow S:"Haskell 2010 Language Report", p. 1–3292010. 7. Berthold J, Marlow S, Hammond K, Zain A Al:"Comparing and Optimising Parallel Haskell Implementations for Multicore Machines", 2009 Int Conf Parallel Process Work [Internet]., Ieee;, pp. 386–93, 2009 Sep [cited 2015 Sep 25];Available from: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm ?arnumber=5364479 8. Jones SP, Leshchinskiy R, Keller G, Chakravarty MMT:"Harnessing the Multicores : Nested Data Parallelism in Haskell", In: Hariharan, R.; Mukud M ;Vina. V., editor. FSTTCS., Bangalore;, p. 1–322008. 9. Aswad MK, Trinder PW, Loidl HW:"Architecture aware parallel programming in Glasgow Parallel Haskell (GPH)", Procedia Comput Sci [Internet]., Elsevier Masson SAS;, Vol. 9, No. 1, pp. 1807–16, 2012;Available from: http://dx.doi.org/10.1016/j.procs.2012.04.199

7. SÍNTESIS CURRICULARES DE LOS AUTORES Alex Puertas González. Nacido en Tunja/Colombia el 2 de septiembre de 1978 Ingeniero de Sistemas de la Universidad Católica de Colombia (Bogotá/Colombia) en 2007 Especialista en Seguridad de la Información de la Universidad de los Andes (Bogotá/Colombia) en 2009 Ha trabajado como docente universitario desde el año 2002 en programas de Ingeniería de sistemas, en modalidad presencial, semipresencial y en línea, orientando asignaturas, tanto de ciencias básicas, en la línea de formación en matemáticas: Cálculos, álgebras y métodos numéricos, como en el campo aplicado,

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”

Puertas, A.; Hoyos, J. | “ANÁLISIS DE DESEMPEÑO DE HASKELL EN LA EJECUCIÓN DE ALGORITMOS PARALELIZADOS CON PRIMITIVAS” haciendo especial énfasis en asignaturas del área de las redes y comunicaciones y administración de recursos. En el ámbito laboral, ha trabajado en la implementación de soluciones de internetworking en calidad de diseñador y personal de soporte. Actualmente labora en la Universidad Santo Tomás, como docente de tiempo completo, con participación en proyectos de investigación y la dirección del semillero de seguridad informática de la facultad. Se le puede contactar al correo electrónico [email protected] y a la dirección postal Calle 19 No. 11-64 Tunja - Boyacá (Colombia)

Ciencias de la Información y las Comunicaciones en la Universidad Distrital “Francisco José de Caldas”. Desde hace siete años es profesor de tiempo completo e investigador en la Facultad de Ingeniería de Sistemas de la Universidad Santo Tomás Seccional Tunja. Como producto de su participación en diferentes proyectos de investigación ha sido autor y coautor de varios artículos publicados en revistas científicas y trabajos presentados a eventos nacionales e internacionales. Ha participado también como miembro del comité editorial, científico y de árbitros en diferentes publicaciones y eventos científicos y académicos. Se le puede contactar al correo electrónico [email protected], y a la dirección postal Calle 19 No. 11-64 Tunja - Boyacá (Colombia)

Jorge Gabriel Hoyos Pineda. Ingeniero de Sistemas de la Universidad Antonio Nariño, en el 2009 se graduó como Magister en

“III Conferencia Internacional en Ciencias Computacionales e Informáticas”