Algoritmos Paralelos Usando Plantillas

Las plantillas de clases (class templates) son un mecanismo que permite describir tipos de datos genéricos para manejar otros tipos de datos. Por ejemplo, las “clases contenedoras” como listas, pilas y colas, permiten manejar sus contenidos de forma genérica sin importar el tipo específico de los objetos que contienen. Esta capacidad no se limita a ser utilizada en clases contenedoras, otra posibilidad es aplicarla para encapsular algoritmos de propósito general, como ciclos por ejemplo. El uso de plantillas de clases incluso se puede extender para habilitar nuestro código a ejecutarse de forma adecuada en computadoras con capacidad de procesamiento paralelo.
Threading Building Blocks es una librería de código abierto que provee plantillas para cómputo paralelo. Al usar TBB, el desarrollador representa el trabajo paralelo como un conjunto de tareas que son despachadas por la librería hacia un grupo administrado de threads (hilos de ejecución). Este artículo ilustra cómo aprovechar las plantillas de la librería TBB. Comenzamos con un simple ciclo “for” entre elementos que no tienen dependencias entre sí y luego mostramos un ejemplo más avanzado para el recorrido de un árbol binario.

Fundamentos
TBB trabaja por medio de la descomposición de los programas en tareas y el mapeo de dichas tareas a un grupo de threads. Una tarea representa un rango de datos a procesarse, junto con las operaciones que se realizarán en estos datos. El tamaño de las tareas depende tanto de la cantidad de procesamiento a realizarse en cada unidad, como del número de datos que pueden procesarse juntos.

El programador rara vez tiene forma de modificar la cantidad de procesamiento en cada unidad, pero sí puede variar el número de unidades de datos que se procesan juntos y de esta forma controlar que las tareas tengan el tamaño adecuado. Es importante que esto se logre, ya que si las tareas son demasiado grandes, algunos nodos de procesamiento paralelo se usarán mucho más que los demás, lo cual es ineficiente. Por otro lado, si las tareas son demasiado pequeñas, también hay ineficiencia porque se desperdicia demasiado procesamiento en coordinar la ejecución de tantas tareas tan pequeñas. Para ayudar en el manejo de estos casos, la librería TBB provee al desarrollador con un mecanismo para regular el tamaño de los datos.

Por ejemplo, en el caso de un ciclo “for”, la librería permite que el desarrollador especifique un parámetro denominado grain size (tamaño de grano) que es utilizado por la librería para definir cuantas iteraciones serán repartidas entre cada hilo de ejecución. El valor ideal del grain size depende de la naturaleza del algoritmo así como la configuración del hardware, así que puede ser un cálculo complicado. Por ello, TBB provee un mecanismo llamado “autoparticionador” que dinámicamente estima el grain size y que típicamente provee resultados suficientemente buenos.

Ejemplo: ciclo sin dependencias
Para los casos más sencillos de paralelismo de datos basado en ciclos, TBB provee plantillas de funciones para ayudar a convertir el código del ciclo serial a código paralelo equivalente. En este caso, la plantilla parallel_for simplemente reemplaza el ciclo serial tomando tres argumentos: el rango del índice del ciclo, una referencia a una clase definida por el usuario que contiene el cuerpo del ciclo, y un
tamaño de datos o particionador. Todos los elementos necesarios para el manejo de hilos, mapeo de tareas a hilos y coordinación para la ejecución de tareas son manejadas por la librería de forma transparente para el desarrollador. Es así que los desarrolladores pueden paralelizar sus códigos al utilizar prácticas estándar de orientación a objetos.


En esta situación podemos utilizar el template parallel_for. Este template recibe dos parámetros: el rango o espacio de iteración, y el objeto de la función. El manejo de espacios de iteración en TBB
requiere que la clase modelada implemente una interfaz con las siguientes operaciones:
• bool empty(): función que regresa “true” si el rango en cuestión está vacío.
• bool is_divisible(): función que regresa “true” si el rango se puede dividir en dos mitades.
• Un constructor que toma dos parámetros: el primero es la referencia al rango y el segundo es tbb::split, un objeto capaz de dividir el rango en varias partes.

La librería TBB también provee implementaciones de espacios de iteración de 1 y 2 dimensiones, blocked_range y blocked_range2d respectivamente. El espacio de iteración de una dimensión puede usarse en este ejemplo para representar un rango de valores de tipo T donde T tiene el tamaño size_t de nuestro ejemplo.

El operador de llamada a la clase Body depende del objeto de espacio de iteración, y en esencia contiene el cuerpo del ciclo “for” original, pero modificado para que pueda trabajar con sub-rangos.
El código de alto nivel se muestra en el listado 3.

El parallel_for divide recursivamente en mitades el espacio de iteración dado, que en este ejemplo es el intervalo medio abierto [0, item_ count). Esto crea tareas más pequeñas que dependen de sub-rangos
más pequeños. La función parallel_for divide un rango en sub-rangos hasta que sean menor o iguales a grain_size, que es el tamaño de rango de datos que el desarrollador considera óptimo. En caso que se desee usar el auto-particionador que dinámicamente estime el grain_size adecuado, nuestro código requeriría la modificación indicada en el listado 4.

Para ejecutar tbb::parallel_for, el programa debe inicializar la agenda de tareas de TBB creando un objeto de tipo task_scheduler_init. El constructor default de este objeto creará un grupo de threads e
inicializará las estructuras de datos internas de TBB. Es así que la función main para invocar nuestro código quedaría como en el listado 5.

Recorrido de un árbol por recursividad
Los algoritmos de alto nivel que la librería TBB provee son convenientes para el desarrollador porque esconden la complejidad del manejo de tareas y threads.

El programador de tareas (task scheduler) de TBB provee una interfaz de C++ simple que puede ser utilizada para asignar, generar y combinar tareas. Con la interfaz del programador de tareas también
es posible expresar un amplio rango de algoritmos.
Por ejemplo, con él podemos expresar fácilmente paralelismo recursivo y anidado de forma escalable.

Para ilustrar esto, veamos el listado 6, que contiene la implementación serial para el recorrido de un árbol binario.

El listado 7 tiene el código que podemos utilizar para hacer el recorrido del árbol binario de forma paralela.

No temos primero que este algoritmo recursivo puede ser visto como un árbol de tareas. Es así que creamos una nueva clase MyRecursiveTask usando tbb::task como clase base. La clase tbb::task contiene el método virtual execute que debe ser implementado por quienes hereden esta clase base. El método execute será invocado cuando alguno de los threads ejecute la tarea que estamos manejando como objeto.

También es importante darnos cuenta que el método MyRecursiveTask conceptualmente es muy similar a la función SerialTreeTraversal que ya habíamos definido (en las ramas que no están vacías aplica la función foo a los datos almacenados en el nodo raíz de la rama y crea dos nuevas tareas MyRecursiveTask para las ramas no vacías a la izquierda y derecha). Los nuevos objetos de tarea hijos deben ser asignados por el método especial task::allocate_child. Cuando un nuevo objeto tarea es asignado, la nueva tarea se puede agendar para ejecución al invocar el método task::spawn.

Para nuestro ejemplo, una tarea crea dos tareas adicionales que agregamos a la lista tbb::task_list y luego generamos la lista de tareas invocando spawn_and_wait_for_all(list). Generar una lista de tareas típicamente brinda mejor desempeño que generar las tareas de forma individual.

Todas las tareas de TBB son agendadas de acuerdo a su relación padre-hijo. Una tarea padre espera a sus hijos y para ello necesita saber a cuantos hijos debe esperar. Esto se logra con una llamada al método set_ref_count(count) donde “count” es el número de hijos + 1.

El código de alto nivel que invoca a MyRecursiveTask se muestra en el listado 8. La función ParallelTreeTraversal primero invoca la versión sobrecargada (overloaded) del operador new y el método estático tbb::task::allocate_root para crear una tarea raíz. La tarea raíz es una tarea especial que no tiene padre.

Para este ejemplo, la tarea raíz es un objeto root_task del tipo MyRecursiveTask. Entonces, tbb::task::spawn_root_and_wait será llamado para iniciar la creación de nuevas tareas del mismo tipo que las ramas; esto se hace recursivamente. Antes de llamar a la función ParallelTreeTraversal, el programa debe inicializar un programador de tareas.


Uso de un espacio de iteración personalizado
Por default el espacio de iteración de TBB es genérico. Para el ejemplo del ciclo utilizamos el espacio de iteración tbb:blocked_range pero incluso podemos ir más allá e implementar un espacio específico a un problema. Por ejemplo, el algoritmo de recorrido de árbol también se puede implementar utilizando tbb:parallel_for, sin usar recursividad explícita. El listado 9 muestra cómo se puede implementar el espacio de iteración para los nodos del árbol.

El código MyRange::MyRange (MyRange& r, tbb::split) indica un constructor divisor. Toma un rango (en este caso, una rama del árbol) y aplica la función foo a los datos almacenados en la raíz de dicha rama y la divide en dos sub-ramas. La rama derecha se asigna a el rango en cuestión, mientras que la rama izquierda se convierte en un sub-rango nuevo. La división de rangos continúa mientras que la raíz de la rama en cuestión no esté vacía y el sub-rango izquierdo o derecho no sea nulo. El listado 10 muestra el contenido de la clase Body.

Cuando el rango ya no se puede dividir más, MyRange::is_divisible regresafalso. El operador de la clase Body es invocado y si la hoja no es NULL entonces la función “foo” es aplicada a los datos almacenados en el nodo hoja. El listado 11 muestra el código que lo invoca.

Esta implementación se basa en el hecho de que la función parallel_for divide el trabajo de forma recursiva, de tal forma que la implementación no requiere utilizar recursividad de forma explícita. Utilizando espacios de iteración personalizados le permite al desarrollador controlar por completo la forma en que el trabajo se distribuye entre tareas. Esto puede ser muy útil cuando un dato acarrea información acerca de la complejidad del trabajo de sus elementos.

Conclusión
Hemos ilustrado la estrategia de paralelismo basado en la descomposición de tareas para implementar un árbol binario por medio de recursión explícita y por medio de la definición de un espacio de iteración personalizado. Hemos podido hacer todo esto sin necesidad de hacer grandes cambios al
código serial, gracias a los elementos provistos por la librería Threading Building Blocks.
Conoce más sobre TBB en www. threadingbuildingblocks.org

Acerca del Autor
Michael D’Mello es Ingeniero Senior de Consultoría Técnica en la división de productos para desarrolladores en Intel. Cuenta con más de 18 años de experiencia profesional, especializándose en cómputo paralelo. Es Doctor en Química por la Universidad de Texas en Austin.