Paralelización Automática Basada en Memoria Transaccional

Abstract

Con la aparición de los chips multiprocesador, la industria del hardware ha pasado la responsabilidad sobre la eficiencia de las aplicaciones a la comunidad de desarrolladores de software. La gran mayoría de programadores aún continua desarrollando programas secuenciales, mientras que la mayor parte del desarrollo paralelo aun se realiza por grupos fuertemente especializados en programación paralela de alto rendimiento, debido a su complejidad y a la necesidad de disponer de una profunda comprensión de conceptos hardware, algoritmos y herramientas de programación paralelas.

La Memoria Transaccional (TM) emerge como una alternativa a la programación paralela convencional, facilitando el desarrollo de programas concurrentes. Estos sistemas proporcionan al programador las construcciones necesarias para definir bloques de instrucciones que ejecutan como unidades atómicas y aisladas (transacciones), siguiendo un modelo de concurrencia optimista. Estas transacciones se ejecutan en paralelo, a menos que se detecte un conflicto entre ellas en el acceso a un objeto común. La detección de conflictos se realiza de manera transparente por parte del sistema transaccional y supone un aspecto crítico para el rendimiento del sistema. Sin embargo, la memoria transaccional, como paradigma de programación, aun presenta algunas limitaciones a la hora de paralelizar determinados tipos de códigos, especialmente aquellos que presentan restricciones de precedencia, puesto que tienden a serializar en exceso su ejecución, desperdiciando así gran parte de la ganancia de rendimiento obtenida por el proceso de paralelización.

En esta tesis, proponemos un modelo de ejecución transaccional pensado para explotar la máxima concurrencia de programas secuenciales y paralelos que presenten restricciones de precedencia. Una sección de código del programa se divide en chunks, los cuales se asignan a diferentes hilos para ejecutar como transacciones. Estas transacciones ejecutan concurrentemente y de manera desordenada, intentando aprovechar el máximo paralelismo al tiempo que se gestiona su finalización (commit) asegurando que las dependencias de datos mantengan una semántica secuencial basada en su orden de precedencia.

Este orden de precedencia parcial, derivado de la sección de código del programa, es extraído por el compilador y/o definido por el programador para garantizar la corrección de la ejecución paralela. Cuando se detecte un conflicto, el sistema transaccional utilizará el orden de precedencia definido para aplicar la mejor política para resolverlo, preservando el orden y maximizando la explotación de la concurrencia. En este modelo se define un nuevo estado en el ciclo de vida de una transacción, denominado executed-but-not-committed, en el que esta ha finalizado su ejecución pero sus cambios aun no han sido confirmados en memoria. Este nuevo estado permite explotar la concurrencia en dos niveles: intra-thread and inter-thread. El primero es mejorado al permitir a los hilos lanzar nuevas transacciones manteniendo las anteriores activas, a la espera de poder realizar su commit cumpliendo con la semántica secuencial del programa original, evitando así que el hilo se bloquee. La explotación del segundo nivel se debe al desacoplo de las fases de ejecución y commit, que permiten relajar la condición de commit de las transacciones (condición necesaria para poder hacer visibles sus cambios en memoria), permitiendo desordenar los commits sin afectar a la semántica secuencial del programa original.

Además, debido a que las operaciones de reducción aglutinan una importante parte del tiempo de ejecución en muchas aplicaciones del mundo real, y a que su uso está fuertemente ligado a construcciones iterativas, hemos considerado los bucles de reducción como un escenario de especial interés en nuestro modelo de ejecución. En concreto, hemos analizado cómo el manejo de las direcciones de memoria pertenecientes a variables de reducción en entornos transaccionales, ayuda a facilitar y mejorar la explotación de concurrencia. Tras este análisis hemos propuesto un soporte como extensión a nuestro modelo de ejecución, con el fin de gestionar las operaciones de reducción como un caso especial de accesos conflictivos a memoria.

Todas nuestras aportaciones se han implemento sobre un conocido STM (TinySTM) y evaluadas utilizando un conjunto de benchmarks representativo, tanto para el ámbito transaccional como para la computación paralela de alto rendimiento.