Soporte de Orden y Reducciones en Sistemas de Memoria Transaccional

Abstract

En esta tesis se proponen soluciones basadas en memoria transaccional (TM) para optimizar la detección y resolución de conflictos en códigos que presentan operaciones de reducción. Las reducciones aparecen frecuentemente en aplicaciones científicas en combinación con patrones de acceso irregulares que dificultan su paralelización de forma eficiente. Nuestra propuesta contempla las reducciones como una operación transaccional adicional en el modelo TM. El tratamiento explícito de las reducciones permite filtrar los conflictos originados por dichas operaciones manteniendo la consistencia del sistema sin necesidad de abortar transacciones.

Este trabajo introduce además un orden total de precedencia entre transacciones que implica que éstas confirmen sus cambios a memoria en un orden específico, facilitando así la paralelización de aplicaciones secuenciales. El uso de este orden permite además detectar reducciones parciales; accesos a memoria que violan las condiciones de reducción.

Dado que un orden de precedencia estricto penaliza el rendimiento y puede ser demasiado restrictivo, esta tesis aborda también el diseño de un orden de precedencia parcial, donde las restricciones a la hora de confirmar los cambios a memoria no se aplican entre transacciones individuales sino entre grupos de ellas, permitiendo aumentar el grado de paralelismo de la aplicación. Introducimos el concepto de barrera transaccional, una primitiva cuya semántica es similar a una barrera de sincronización tradicional, pero que aprovecha TM para permitir a los hilos seguir ejecutando código de forma especulativa. Nuestra propuesta utiliza estas barreras para establecer un orden parcial de precedencia, lanzando transacciones con restricciones de precedencia dinámicas que permiten evitar bloqueos debidos a la sincronización manteniendo la corrección del programa.