Document details

Description

Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2020-06-03T17:15:06Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rafael_de_Leao_Bandeira.pdf: 757665 bytes, checksum: 0e83a077af5a8e9a3e1b51da218862af (MD5)

Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2020-06-04T01:48:44Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rafael_de_Leao_Bandeira.pdf: 757665 bytes, checksum: 0e83a077af5a8e9a3e1b51da218862af (MD5)

Made available in DSpace on 2020-06-04T01:49:04Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rafael_de_Leao_Bandeira.pdf: 757665 bytes, checksum: 0e83a077af5a8e9a3e1b51da218862af (MD5) Previous issue date: 2013-12-11

Sem bolsa

A computação paralela permitiu um considerável ganho de desempenho na execução dos programas, dividindo-os em partes discretas resolvidas concorrentemente usando múltiplos recursos computacionais. Apesar dos seus benefícios, esse paradigma aumenta a complexidade no desenvolvimento dos algoritmos, pois é necessário levar em conta vários aspectos inexistentes na codificação de programas sequenciais, como por exemplo, garantir a exclusão mútua das tarefas executadas paralelamente. Transações de memória são unidades de execução atômica. Sua utilização permite ao programador focar em determinar onde a atomicidade é necessária, ao invés dos mecanismos necessários para garanti-la. Com essa abstração, o desenvolvedor identifica as operações que formam uma seção crítica, enquanto que o sistema transacional determina como executar aquela seção crítica isoladamente em relação aos outros fluxos de execução do programa. CMTJava (DU BOIS; ECHEVARRIA, 2009) é uma extensão de Java para programação com memórias transacionais. Neste trabalho descreve-se a implementação de um novo sistema para gerenciamento da execução concorrente das transações na CMTJava. O sistema transacional desenvolvido utiliza uma estratégia híbrida para detecção de conflitos, conhecida como invalidação mista (SPEAR et al., 2006). Conflitos entre transações de escrita são detectados de forma adiantada e conflitos entre uma transação de leitura e outra de escrita são detectados tardiamente. Na implementação antecedente, ambos tipos de conflitos são detectados ao final da execução da transação. De acordo com resultados obtidos através de experimentos com árvores rubro-negras, o sistema de detecção de conflitos com invalidação mista proposto obtém melhor desempenho que o trabalho anterior em cenários onde o número de conflitos é grande. Em particular, o sistema transacional desenvolvido mostrou-se mais eficiente que a implementação anterior na maioria dos cenários testados, sendo até duas vezes mais eficiente para execução de transações de busca em uma árvore rubro-negra com 50000 elementos.

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.