PDF de programación - Simulación de Programas Paralelos en Haskell

Simulación de Programas Paralelos en Haskell

Martín A. Ceresa

CIFASIS, Rosario, Argentina

Resumen El estudio de formas de incorporar de manera simple y efi-
ciente la programación paralela al desarrollo de software sigue siendo
objeto de investigación. En particular, en el lenguaje de programación
Haskell (Marlow 2010) se ha desarrollado una variedad de extensiones del
lenguaje, bibliotecas, y abstracciones, que permiten encarar el problema
de la programación paralela desde diversos ángulos.
Para dar soporte a la experimentación con formas nuevas de incorporar
paralelismo al desarrollo de software es necesario el desarrollo de herra-
mientas adecuadas que permitan el análisis de las ejecuciones obtenidas.
En este trabajo se propone una herramienta para el estudio de programas
paralelos dentro del lenguaje de programación Haskell. Esta herramienta
permite al programador observar directamente qué computaciones se van
a paralelizar, dándole un mayor entendimiento sobre la ejecución de su
programa.

Keywords: parallel functional programming, Haskell, Klytius

1.

Introducción

La presencia de procesadores multinúcleo en la mayoría de los dispositivos
condiciona al desarrollador a escalar sus programas mediante la ejecución para-
lela. Debido a la necesidad de incorporar paralelismo en los programas se han
extendido los lenguajes de programación, o bien se ha desarrollado bibliotecas,
con diversos grados de éxito. El estudio de las formas de incorporar de mane-
ra simple y eficiente la programación paralela al desarrollo de software sigue
siendo objeto de investigación. En particular, en el lenguaje de programación
Haskell (Marlow 2010) se ha desarrollado una variedad de extensiones, biblio-
tecas, y abstracciones, que permiten encarar el problema de la programación
paralela desde diversos ángulos.

El desarrollo de herramientas adecuadas que permitan el análisis de las ejecu-
ciones obtenidas es necesario tanto al momento de dar soporte a la experimenta-
ción con nuevas formas de incorporar paralelismo, introducir nuevos estudiantes
a la programación paralela, o para comprender el comportamiento de los pro-
gramas.

En este trabajo se le otorga al programador la posibilidad de observar direc-
tamente qué computaciones se van a paralelizar, permitiéndole tener un mayor
entendimiento sobre la ejecución de su programa. Se presenta el desarrollo de

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-76139 la herramienta Klytius, donde se implementa un lenguaje de dominio específi-
co destinado a representar programas paralelos, y se definen representaciones
gráficas para la estructura de programas paralelos.

El artículo se encuentra estructurado de la siguiente forma: sección 1, intro-
ducción al paralelismo y sus problemáticas; sección 2, introducción al paralelismo
básico en Haskell y a Klytius; sección 3, implementación de Klytius; sección 4,
trabajo relacionado; sección 5, conclusiones y trabajo futuro.

1.1. Problemáticas del Paralelismo

Para explotar todo el hardware subyacente el programador debe pensar de
manera paralela, obteniendo beneficios en velocidad, con la desventaja que el
diseño del software se torna más complicado. Se debe tener en cuenta dos aspec-
tos: 1. intrínseco al diseño del algoritmo, identificar qué tareas se pueden realizar
en paralelo, analizar la dependencia de datos, etc; 2. configuración del hardware
disponible, cantidad de núcleos disponibles, cómo distribuir las diferentes tareas
y establecer canales de comunicación entre ellos.

Debido a limitaciones físicas no es posible continuar aumentando la velocidad
de procesamiento de los microprocesadores. Esto produce que el programador
deba incorporar el paralelismo dentro del diseño de sus programas, o modificar
sus algoritmos.

El programador debe dedicar tiempo y esfuerzo en pensar cómo paraleli-
zar sus programas, y en el caso de que sean modificados, garantizar que no se
introducen nuevos errores.

Al aumentar las unidades de procesamiento se da lugar a la posibilidad de
ejecutar varias instrucciones de manera simultánea, es decir, permite paralelizar
la ejecución de los programas. Esto, en teoría, permite multiplicar el poder de
cómputo, aunque, en la práctica no es tan fácil obtener un mayor rendimiento.
Esto sucede principalmente por dos razones:

No todo es paralelizable. Hay tareas que son inherentemente secuenciales, es
decir, que no se van a poder paralelizar completamente sino que tienen al
menos un proceso el cual se tiene que realizar de manera secuencial.
Paralelizar no es gratis. Aún dados algoritmos que son totalmente parale-
lizables, deberemos saber cómo dividiremos los datos, cuantos núcleos hay
disponibles, cómo distribuiremos las distintas tareas en los diferentes núcleos
y cómo se comunican entre ellos en el caso que sea necesario.

1.2. Paralelismo en Lenguajes Funcionales Puros

Los lenguajes funcionales puros nos permiten representar las computaciones
en términos de funciones puras, es decir, nos permiten presentar a un programa
como una función que obtiene toda la información necesaria a través de sus
argumentos y devuelve algún valor como resultado de su computación, sin utilizar
información externa a ella que no este explícitamente dentro de sus argumentos,
ni modificar nada fuera del resultado que otorga al finalizar. Por lo tanto todo

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-76140 comportamiento se vuelve explícito. Esto permite que sea más fácil razonar sobre
los programas y estudiar su comportamiento.

Particularmente al utilizar lenguajes funcionales puros obtenemos las siguien-

tes ventajas (Roe 1991):

Nos permite razonar sobre los programas paralelos de la misma manera que
los secuenciales.
Nos permite delegar todos los aspectos de coordinación de computaciones al
runtime.
No existe la posibilidad de que haya deadlock, excepto en condiciones donde
su versión secuencial no termine debido a dependencias cíclicas.

1.3. Contribuciones

Hemos desarrollado un lenguaje de dominio específico embebido en Haskell
para la simulación simbólica de programas paralelos. A su vez, hemos asignado
una representación gráfica a las diferentes construcciones del lenguaje de dominio
específico, que en conjunto permite al programador observar directamente qué
computaciones se van a paralelizar, dándole un mayor entendimiento sobre la
ejecución de su programa.

Actualmente la herramienta se encuentra alojada en un repositorio Git públi-
co, https://bitbucket.org/martinceresa/klytius/. Se presenta como un
paquete a instalar por la herramienta Cabal de la plataforma de Haskell.

El presente artículo es una versión reducida del trabajo de finalización de la
carrera de grado de Licenciatura en Ciencias de la Computación. El trabajo fue
realizado bajo la supervisión de Mauro Jakelioff y Ezequiel Rivas, a los cuales
estoy muy agradecido por su dedicación.

2. Paralelismo Puro en Haskell

2.1. Particionamiento Semi-Explícito.

Dentro de los lenguajes funcionales se encuentran dos enfoques para para-
lelismo: a) particionamiento implícito, donde el compilador es el encargado de
paralelizar los programas; b) particionamiento explícito, donde el programador es
el encargado no solo de detectar computaciones a paralelizar, sino que además
debe proveer mecanismos de organización de computaciones, como ser, cómo
distribuir las tareas en los procesadores (Hammond 1994).

El lenguaje de programación Haskell presenta un enfoque intermedio, don-
de el programador es quien indica cuáles son las computaciones que se pueden
paralelizar, mientras que el runtime es el encargado de la coordinación de las
computaciones (Loidl y col. 2008). Este enfoque se denomina particionamiento
semi-explícito de programas. Esta división no es arbitraria, sino que se repre-
sentan dos niveles de abstracción diferentes: a) un nivel bajo que depende del
hardware de la computadora, como ser, cantidad de procesadores, tecnología
disponible para la comunicación entre los procesadores, donde el compilador y

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-76141 el entorno de ejecución son los encargados de utilizar dichos recursos; b) un ni-
vel alto el cual es especificado por el programador, y es inherente al programa,
independiente del hardware en el cual se vaya a ejecutar o del estado del sistema
en el momento de la ejecución.

2.2. Primitivas Básicas de Paralelismo.

El lenguaje de programación Haskell, cuenta con dos combinadores básicos

de coordinación de computaciones.
: : a → b → b

par , pseq

Ambos combinadores son los únicos con acceso al control del paralelismo puro
del programa1.

Denotacionalmente ambas primitivas son proyecciones en su segundo argu-

mento.

par
a b = b
pseq a b = b

Operacionalmente pseq establece que el primer argumento debe ser evaluado
antes que el segundo, mientras que par indica que el primer argumento puede
llegar a ser evaluado en paralelo con la evaluación del segundo. Utilizando los
combinadores básicos par y pseq el programador establece el qué y cómo para-
lelizar sus programas, dejando la coordinación de computaciones al compilador
en conjunto con el runtime.

Definiremos como comportamiento dinámico a los efectos generados por el uso
de los combinadores básicos de paralelismo, los cuales son reflejados en tiempo
de ejecución.

Toda computación a marcada por par a b, será vista por el entorno de ejecu-
ción como una oportunidad de trabajo a realizar en paralelo, la cual se denomina
spark. La acción de sparking no fuerza inmediatamente la creación de un hilo,
sino que es el runtime el encargado de determinar cuáles sparks van a ejecu-
tarse, tomando esta decisión en base al estado general del sistema, como ser, si
encuentra disponible a algún núcleo en el cual ejecutar la evaluación del spark.