Um sistema de detecção de conflitos com invalidação mista para a linguagem CMTJava

Abstract

The parallel computing has allowed a considerable performance gain in programs execution, dividing them into discrete parts solved concurrently using multiple computational resources. Despite its benefits, this paradigm increases the complexity in the development of algorithms, because it is necessary to take into account several aspects not present in sequential programming, such as the necessity to ensure mutual exclusion of tasks performed in parallel. Memory transactions are atomic execution units. Its use allows the programmer to focus on determining where atomicity is required, rather than the mechanisms needed to guarantee it. With this abstraction, the developer identifies the operations that form a critical section, while the transactional system determines how to execute that critical section isolatedly from other program threads. CMTJava (DU BOIS; ECHEVARRIA, 2009) is a Java extension for programming with transactional memory. This work describes the implementation of a new system to manage the concurrent execution of transactions. The system developed employs a hybrid conflict detection strategy, called mixed invalidation (SPEAR et al., 2006). Write/write conflits are detected eagerly and read/write conflicts are lazily detected. On the former implementation, both conflict types are detected by the end of the transaction execution. According to results obtained in a red-black tree microbenchmark, the mixed conflict detection strategy employed yields better performance than the previous work when the number of conflicts is high. In particular, the STM system developed is more efficient than the former implementation in most cases tested, being two times more efficient for executing search transactions in a red-black tree with 50000 elements.