Extending the applicability of deterministic multithreading

Abstract

With the increased number of cores on a single processor chip, an application can achieve good performance if it splits the execution into multiple threads that run on multiple cores at the same time. To synchronize threads, Transactional Memory (TM) allows them to concurrently execute sections of code (transactions) with accesses to shared memory, and requires reexecution of one of the transactions in case of a conflicting access. Even though parallel programming with TM is simpler and less error-prone than with the traditional locking mechanism, concurrent programming errors are hard to avoid in general. The reason is that threads run in parallel and might interleave in a nondeterministic order. As a consequence, an error can occur in one execution but be hidden in another (which makes debugging hard), and the application output might vary (which makes testing and replica-based fault tolerance hard). To help programmers in testing, debugging and providing fault tolerance, researchers have proposed deterministic multithreading, which guarantees that application threads access shared memory in the same order and the application gives the same output whenever it runs with the same input parameters. In this thesis we present DeTrans, a system for deterministic multithreading in transactional applications. DeTrans ensures determinism even in the presence of data races, by executing non-transactional code serially and transactions in parallel. We compare DeTrans with Dthreads, a widely-used deterministic system for lock-based applications, and analyse sources of the overhead caused by deterministic execution. Instead of using memory protection hardware and operating system facilities, DeTrans exploits properties of TM implemented in software and outperforms Dthreads. To allow transactions to invoke standard library functions while running deterministically and to increase parallelism, this thesis proposes TM-dietlibc, a TM-aware standard library. Our experience in modifying a lock-based standard library in order to integrate it in a TM system is applicable for any TM-aware software. TM-dietlibc provides concurrent execution of standard library functions and only in a few cases the execution switches to serial. In comparison to completely serialized execution, TM-dietlibc shows high scalability and performance improvement for benchmarks with short transactions and low contention. Serialization of transactions - which is still required for transactions in TM-dietlibc with non-reversible side effects - might enforce an order of threads execution different from the one enforced by a deterministic system, causing a deadlock. By porting deterministic system DeTrans in TM-dietlibc, we ensure deterministic multithreading at application and standardlibrary level, and avoid deadlocks by serializing transactions in deterministic order. In this thesis we also discuss a common limitation of deterministic systems - ad hoc synchronization. Ad hoc synchronization is in general widely used, but similarly to transaction serialization, it might be prone to deadlocks during deterministic execution. We use hardware performance counters to identify synchronization loops at runtime and to avoid deadlocks by dynamically (but deterministically) changing the order of threads execution.

Con el aumento del número de núcleos en un solo procesador, una aplicación puede lograr un buen rendimiento si se divide la ejecución en múltiples hilos que se ejecutan en múltiples núcleos al mismo tiempo. Para sincronizar estos hilos, memoria transaccional (TM) permite ejecutar simultáneamente secciones de código (transacciones) con accesos a memoria compartida, y requiere re-ejecución de una de las transacciones en caso de un acceso a memoria que causa un conflicto. A pesar de que la programación paralela con TM es más simple y menos propensa a errores que con mecanismos de cerrojos tradicionales, los errores de programación concurrentes son difíciles de evitar en general. La razón es que los hilos se ejecutan en paralelo y pueden intercalar en ordenes no deterministas. Como consecuencia, un error puede ocurrir en una ejecución, pero se oculta en otro (lo que hace que la depuración difícil), y el resultado de la aplicación puede variar (lo que hace el testeo y la tolerancia a fallos basada en réplica difícil). Para ayudar a los programadores en el testeo, depuración y proporcionar tolerancia a fallos, los investigadores han propuesto sistemas multihilos deterministas, que garantizan que los diferentes hilos de las aplicaciones accedan a la memoria compartida en el mismo orden y la aplicación da el mismo resultado cada vez que se ejecuta con los mismos parámetros de entrada. En esta tesis presentamos DeTrans, un sistema determinista para las aplicaciones transaccionales. DeTrans asegura el determinismo incluso en presencia de condiciones de carrera de datos, mediante la ejecución de código no transaccional en serie y las transacciones en paralelo. Comparamos DeTrans con Dthreads, un sistema determinista ampliamente utilizado para aplicaciones basadas en cerrojos, y analizamos las fuentes de coste adicional causadas por la ejecución determinista. En lugar de utilizar hardware de protección de memoria y las funcionalidades del sistema operativo, DeTrans explota las propiedades de TM implementadas en software y rinde mejor que Dthreads. Para permitir que las transacciones puedan invocar funciones de la librería estándar durante la ejecución determinista y aumentar el paralelismo, esta tesis propone TM-dietlibc, una librería estándar consciente de TM. Nuestra experiencia en la modificación de una librería estándar basada en locks con el fin de integrarlo en un sistema de TM es aplicable a cualquier software consciente de TM. TM-dietlibc proporciona ejecución simultánea de funciones de la librería estándar y sólo en unos pocos casos la ejecución pasa a ser en serie. En comparación con la ejecución totalmente serial, TM-dietlibc muestra una alta escalabilidad y una mejora del rendimiento para aplicaciones con transacciones cortas y contención baja. Serialización de transacciones - que todavía se requieren para las transacciones en TM-dietlibc con efectos secundarios no reversibles - podría forzar un orden de ejecución de los hilos distinta de la aplicada por un sistema determinista, causando un deadlock. Portando el sistema determinista DeTrans a TM-dietlibc, aseguramos ejecuciones multihilo deterministas tanto a nivel de la aplicación como de la librería estándar, y evitamos deadlocks serializando transacciones en orden determinista. En esta tesis también discutimos una limitación común de los sistemas deterministas - la sincronización ad-hoc. La sincronización ad-hoc es en general ampliamente utilizada, pero de manera similar a la serialización transacción, puede ser propensa a deadlocks durante la ejecución determinista. Utilizamos contadores de rendimiento hardware para identificar bucles de sincronización durante la ejecución y así evitar deadlocks de forma dinámica (pero determinista) cambiando el orden de ejecución de los hilos.