DeTrans: Deterministic and Parallel execution of Transactions

• Vesna Smiljkovic Centro Nacional de Supercomputacion
• Srdan Stipic Universitat Politecnica de Catalunya / Barcelona Supercomputing Center
• Christof Fetzer Technische Universitat Dresden
• Osman Ünsal Barcelona Supercomputing Center
• Adrián Cristal Artificial Intelligence Research Institute / Spanish National Research Council / Barcelona Supercomputing Center
• Mateo Valero Universitat Politecnica de Catalunya / Barcelona Supercomputing Center

Resumo

Deterministic execution of a multithreaded application guarantees the same output as long as the application runs with the same input parameters. Determinism helps a programmer to test and debug an application and to provide fault-tolerance in the systems based on replicas. Additionally, Transactional Memory (TM) greatly simplifies development of multithreaded applications where applications use transactions (instead of locks) as a concurrency control mechanism to synchronize accesses to shared memory. However, deterministic systems proposed so far are not TM-aware. They violate the main properties of TM (atomicity, consistency and isolation of transactions), and execute TM applications incorrectly. In this paper, we present DeTrans, a runtime system for deterministic execution of multithreaded TM applications. DeTrans executes TM applications deterministically, it executes nontransactional code serially in round-robin order, and transactional code in parallel. Also, we show how DeTrans works with both eager and lazy software TM. We compare DeTrans with Dthreads, a state-of-the-art deterministic execution system. Unlike Dthreads, DeTrans does not use memory protection hardware nor facilities of the underlying operating system (OS) to execute multithreaded applications deterministically. DeTrans uses properties of software TM to ensure deterministic execution. We evaluate DeTrans using the STAMP benchmark suite and we compare DeTrans and Dthreads performance costs. DeTrans incurs less overhead because threads execute in the same address space without any OS system calls overhead. According to our results, DeTrans is 3.99x, 3.39x, 2.44x faster on average than Dthreads for 2, 4 and 8 threads, respectively.

Palavras-chave: Instruction sets, Libraries, Benchmark testing, Synchronization, Computer bugs, Arrays, transactional memory, determinism, multithreading