Software Transactional Memory (STM) helps programmers write correct concurrent code by allowing them to identify atomic sections rather than focusing on the mechanics of concurrency control. Given code with atomic sections, the compiler and STM runtime can work together to ensure proper controlled access to shared memory. STM runtimes use either lazy or eager version management. Lazy versioning buffers transaction updates, whereas eager versioning applies updates in-place. The current set of primitives suit lazy versioning since memory needs to be accessed through the runtime. We present a new set of runtime primitives that better suit eager versioned STM. We propose a novel extension to the compiler/runtime interface, consisting of memory reservations and memory releases. These extensions enable optimizations specific to eager versioned runtimes. A memory reservation allows a transaction to perform instrumentation-free access on a memory address. A release allows a read-only address to be modified by another transaction. Together, these reduce the instrumentation overhead required to support STM and improve concurrency between readers and writers. We have implemented these primitives and evaluated its performance on the STAMP benchmarks. Our results show strong performance and scalability improvements to eager versioned algorithms.

Existing atomic section interface proposals, thus far, have tended to only isolate transactions from each other. Less considered is the coordination of threads performing transactions with respect to one another. Synchronization of nested sections is typically relegated to outside of and among the top-level flattened sections. However existing models do not permit the composition of even simple synchronization constructs such as barriers. The proposed model integrates synchronization as a first-class construct in a truly nested atomic block implementation. The implementation is evaluated on quantitative benchmarks, with qualitative examples of the atomic section interface???s expressive power compared with conventional transactional memory implementations.

A Memória Transacional (TM) surgiu nos últimos anos como uma nova solução para sincronização em sistemas multiprocessados de memória compartilhada, permitindo explorar melhor o paralelismo das aplicações ao evitar limitações inerentes ao mecanismo de locks. Neste modelo, o programador define regiões de código que devem executar de forma atômica. O sistema tenta executá-las de forma concorrente, e, em caso de conflito nos acessos à memória, toma as medidas necessárias para preservar a atomicidade e isolamento das transações, na maioria das vezes abortando e reexecutando uma das transações. Um dos modelos mais aceitos de memória transacional em hardware é o LogTM, implementado neste trabalho em um MPSoC embarcado que utiliza uma NoC para interconexão. Os experimentos fazem uma comparação desta implementação com locks, levando-se em consideração performance e energia do sistema. Além disso, este trabalho mostra que o tempo que uma transação espera para reiniciar sua execução após ter abortado (chamado de backoff delay on abort) tem impactos significativos na performance e energia. Uma análise deste impacto é feita utilizando-se de três políticas de backoff. Um mecanismo baseado em um handshake entre transações, chamado Abort handshake, é proposto como solução para o problema. Os resultados dos experimentos são dependentes da aplicação e configuração do sistema e indicam ganhos da TM na maioria dos casos em relação ao mecanismo de locks. Houve redução de até 30% no tempo de execução e de até 32% na energia de aplicações de baixa demanda de sincronização. Em um segundo momento, é feita uma análise do backoff delay on abort na performance e energia de aplicações utilizando três políticas de backoff em comparação com o mecanismo Abort handshake. Os resultados mostram que o mecanismo proposto apresenta redução de até 20% no tempo de execução e de até 53% na energia comparado à melhor política de backoff dentre as analisadas. Para aplicações com alta demanda de sincronização, a TM mostra redução no tempo de execução de até 63% e redução de energia de até 71% em comparação com o mecanismo de locks. / Transactional Memory (TM) has emerged in the last years as a new solution for synchronization on shared memory multiprocessor systems, allowing a better exploration of the parallelism of the applications by avoiding inherent limitations of the lock mechanism. In this model, the programmer defines regions of code, called transactions, to execute atomically. The system tries to execute transactions concurrently, but in case of conflict on memory accesses, it takes the appropriate measures to preserve the atomicity and isolation, usually aborting and re-executing one of the transactions. One of the most accepted hardware transactional memory model is LogTM, implemented in this work in an embedded MPSoC that uses an NoC as interconnection mechanism. The experiments compare this implementation with locks, considering performance and energy. Furthermore, this work shows that the time a transaction waits to restart after abort (called backoff delay on abort) has significant impact on performance and energy. An analysis of this impact is done using three backoff policies. A novel mechanism based on handshake of transactions, called Abort handshake, is proposed as a solution to this issue. The results of the experiments depends on application and system configuration and show TM benefits in most cases in comparison to the locks mechanism, reaching reduction on the execution time up to 30% and reduction on the energy consumption up to 32% on low contention workloads. After that, an analysis of the backoff delay on abort on the performance and energy is presented, comparing to the Abort handshake mechanism. The proposed mechanism shows reduction of up to 20% on the execution time and up to 53% on the energy, when compared to the best backoff policy. For applications with a high degree of synchronization, TM shows reduction on the execution time up to 63% and energy savings up to 71% compared to locks.

A Memória Transacional (TM) surgiu nos últimos anos como uma nova solução para sincronização em sistemas multiprocessados de memória compartilhada, permitindo explorar melhor o paralelismo das aplicações ao evitar limitações inerentes ao mecanismo de locks. Neste modelo, o programador define regiões de código que devem executar de forma atômica. O sistema tenta executá-las de forma concorrente, e, em caso de conflito nos acessos à memória, toma as medidas necessárias para preservar a atomicidade e isolamento das transações, na maioria das vezes abortando e reexecutando uma das transações. Um dos modelos mais aceitos de memória transacional em hardware é o LogTM, implementado neste trabalho em um MPSoC embarcado que utiliza uma NoC para interconexão. Os experimentos fazem uma comparação desta implementação com locks, levando-se em consideração performance e energia do sistema. Além disso, este trabalho mostra que o tempo que uma transação espera para reiniciar sua execução após ter abortado (chamado de backoff delay on abort) tem impactos significativos na performance e energia. Uma análise deste impacto é feita utilizando-se de três políticas de backoff. Um mecanismo baseado em um handshake entre transações, chamado Abort handshake, é proposto como solução para o problema. Os resultados dos experimentos são dependentes da aplicação e configuração do sistema e indicam ganhos da TM na maioria dos casos em relação ao mecanismo de locks. Houve redução de até 30% no tempo de execução e de até 32% na energia de aplicações de baixa demanda de sincronização. Em um segundo momento, é feita uma análise do backoff delay on abort na performance e energia de aplicações utilizando três políticas de backoff em comparação com o mecanismo Abort handshake. Os resultados mostram que o mecanismo proposto apresenta redução de até 20% no tempo de execução e de até 53% na energia comparado à melhor política de backoff dentre as analisadas. Para aplicações com alta demanda de sincronização, a TM mostra redução no tempo de execução de até 63% e redução de energia de até 71% em comparação com o mecanismo de locks. / Transactional Memory (TM) has emerged in the last years as a new solution for synchronization on shared memory multiprocessor systems, allowing a better exploration of the parallelism of the applications by avoiding inherent limitations of the lock mechanism. In this model, the programmer defines regions of code, called transactions, to execute atomically. The system tries to execute transactions concurrently, but in case of conflict on memory accesses, it takes the appropriate measures to preserve the atomicity and isolation, usually aborting and re-executing one of the transactions. One of the most accepted hardware transactional memory model is LogTM, implemented in this work in an embedded MPSoC that uses an NoC as interconnection mechanism. The experiments compare this implementation with locks, considering performance and energy. Furthermore, this work shows that the time a transaction waits to restart after abort (called backoff delay on abort) has significant impact on performance and energy. An analysis of this impact is done using three backoff policies. A novel mechanism based on handshake of transactions, called Abort handshake, is proposed as a solution to this issue. The results of the experiments depends on application and system configuration and show TM benefits in most cases in comparison to the locks mechanism, reaching reduction on the execution time up to 30% and reduction on the energy consumption up to 32% on low contention workloads. After that, an analysis of the backoff delay on abort on the performance and energy is presented, comparing to the Abort handshake mechanism. The proposed mechanism shows reduction of up to 20% on the execution time and up to 53% on the energy, when compared to the best backoff policy. For applications with a high degree of synchronization, TM shows reduction on the execution time up to 63% and energy savings up to 71% compared to locks.

Submitted by Bruno Chinelato Honorio (brunochonorio@gmail.com) on 2018-09-16T23:56:19Z No. of bitstreams: 1 DissertacaoMestrado.pdf: 942500 bytes, checksum: 267b4e03ea0654a9a66bd58f2490310b (MD5) / Rejected by Elza Mitiko Sato null (elzasato@ibilce.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo: Problema 01) Está faltando o LOGO (Símbolo)da Universidade/Câmpus na capa do seu trabalho.(este item é obrigatório) Problema 02) Solicito que corrija a descrição na natureza da pesquisa na folha de rosto e insira na folha de aprovação): Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação, junto ao Programa de Pós-Graduação em Ciência da Computação, do Instituto de Geociências e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de Rio Claro Problema 03) A paginação deve ser sequencial, iniciando a contagem na folha de rosto e mostrando o número a partir da introdução, a ficha catalográfica ficará após a folha de rosto e não deverá ser contada; a contagem no seu arquivo começou na introdução. Problema 04) Quando a financiadora é FAPESP, deve constar o nome dela e o número do processo também na folha de aprovação e nos agradecimentos, é norma do convênio. Lembramos que o arquivo depositado no repositório deve ser igual ao impresso, o rigor com o padrão da Universidade se deve ao fato de que o seu trabalho passará a ser visível mundialmente. Agradecemos a compreensão on 2018-09-17T14:32:13Z (GMT) / Submitted by Bruno Chinelato Honorio (brunochonorio@gmail.com) on 2018-09-19T22:38:43Z No. of bitstreams: 1 dissertacaoMestrado.pdf: 1125894 bytes, checksum: f24c8da48aae1c09a95bd67d010c2e68 (MD5) / Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2018-09-20T14:44:36Z (GMT) No. of bitstreams: 1 honorio_bc_me_sjrp.pdf: 1093610 bytes, checksum: 238491c1445e63f7afbd08da117f2a87 (MD5) / Made available in DSpace on 2018-09-20T14:44:36Z (GMT). No. of bitstreams: 1 honorio_bc_me_sjrp.pdf: 1093610 bytes, checksum: 238491c1445e63f7afbd08da117f2a87 (MD5) Previous issue date: 2018-08-09 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Memória Transacional (Transactional Memory – TM) possibilita que programadores utilizem-se do conceito de transação na escrita de código concorrente. Nesse contexto, uma transação pode ser entendida como um bloco de instruções que é executado atomicamente e de forma isolada, ou seja, os estados intermediários no processamento de uma transação não são vistos pelas demais. Embora inicialmente confinada ao ambiente acadêmico, TM está se tornando cada vez mais popular. Prova disto é a adição de hardware transacional aos novos processadores da Intel e IBM, além de suporte para codificação de transações provido por compiladores como o GCC. A grande vantagem do modelo transacional é o maior nível de abstração fornecido ao programador, facilitando a escrita de programas concorrentes e evitando erros de sincronização famosos causados pelas travas (locks), como o deadlock. Infelizmente, o suporte em software para execução de transações ainda não provê desempenho muito bom. Em particular, o código transacional, produzido por compiladores e o sistema de tempo de execução associado, ainda pode ser considerado ineficiente. Nesta dissertação é realizado um estudo atualizado sobre a geração de código transacional do compilador GCC com o objetivo de encontrar a razão da deficiência de desempenho do compilador. O trabalho feito indica que uma das principais fontes de ineficiência são as barreiras de leitura e escrita inseridas pelo compilador. O problema dessa instrumentação acontece quando o compilador não consegue determinar, em tempo de compilação, se uma região de memória será acessada concorrentemente ou não, forçando o compilador a tomar uma decisão pessimista e instrumentar essa região de memória. Esse fenômeno é chamado de instrumentação excessiva. Para superar essas limitações, esta dissertação propõe uma nova construção de linguagem através de uma nova cláusula pragma que permite que programadores especifiquem quais regiões de memória não precisam ser instrumentadas. Para validar a nova cláusula pragma, esta dissertação conduziu experimentos usando o pacote STAMP, composto por aplicações transacionais. Os resultados obtidos mostram um grande ganho de desempenho para as aplicações que usaram o pragma proposto, com essas aplicações sendo até 7.2x mais rápidas que o código original gerado pelo GCC. / Transactional Memory (TM) allows programmers to utilize the concept of transaction for writing concurrent code. In this context, a transactioncan be extended as a block of instructions that is executed atomically and isolated, that is, the intermediate states of the processing of a transaction can not be seen by the other transactions. Although initially confined to the academic field, TM is becoming more popular. An evidence of this is the addition of transactional hardware to the new processors from Intel and IBM, as well as the support for transactional code provided by compilers such as GCC. The biggest advantage to the transactional model is the bigger level of abstraction provided to the programmer, making the process of writing parallel code easier, as well as avoiding famous synchronization errors caused by traditional locks, such as the deadlock problem. Unfortunately, the software support for execution of transaction still does not provide a good performance. In particular, transactional code, produced by compilers and the associated runtime system, can still be considered inefficient. This thesis performs an up-to-date study of the GCC transactional code generation and with the objective to find where the main performance losses are coming from. The study done indicates that one of the main sources of inefficiency is the read and write barriers inserted by the compiler. The problem of this instrumentation is that the compiler cannot determine, at compile time, if a memory region will be accessed concurrently or not, forcing the compiler to take a pessimist approach and instrument this memory region. This phenomenom is called Over-instrumentation. To overcome these limitations, this thesis proposes a new language construct through a new pragma clause that allows programmers to specify which memory regions do not need to be instrumented. To validade the new pragma clause, this thesis conducted experiments using the STAMP benchmark suite, composed of transactional applications. The obtained results show a great performance gain for applications that used the proposed pragma, with them being up to 7.2x faster than the original code generated by GCC. / 2016/12103-7

Le concept de processeur multicœurs constitue le facteur dominant pour offrir des hautes performances aux applications parallèles. Afin de développer des applications parallèles capable de tirer profit de ces plate-formes, les développeurs doivent prendre en compte plusieurs aspects, allant de l'architecture aux caractéristiques propres à l'application. Dans ce contexte, la Mémoire Transactionnelle (Transactional Memory – TM) apparaît comme une alternative intéressante à la synchronisation basée sur les verrous pour ces plates-formes. Elle permet aux programmeurs d'écrire du code parallèle encapsulé dans des transactions, offrant des garanties comme l'atomicité et l'isolement. Lors de l'exécution, les opérations sont exécutées spéculativement et les conflits sont résolus par ré-exécution des transactions en conflit. Bien que le modèle de TM ait pour but de simplifier la programmation concurrente, les meilleures performances ne pourront être obtenues que si l'exécutif est capable de s'adapter aux caractéristiques des applications et de la plate-forme. Les contributions de cette thèse concernent l'analyse et l'amélioration des performances des applications basées sur la Mémoire Transactionnelle Logicielle (Software Transactional Memory – STM) pour des plates-formes multicœurs. Dans un premier temps, nous montrons que le modèle de TM et ses performances sont difficiles à analyser. Pour s'attaquer à ce problème, nous proposons un mécanisme de traçage générique et portable qui permet de récupérer des événements spécifiques à la TM afin de mieux analyser les performances des applications. Par exemple, les données tracées peuvent être utilisées pour détecter si l'application présente des points de contention ou si cette contention est répartie sur toute l'exécution. Notre approche peut être utilisée sur différentes applications et systèmes STM sans modifier leurs codes sources. Ensuite, nous abordons l'amélioration des performances des applications sur des plate-formes multicœurs. Nous soulignons que le placement des threads (thread mapping) est très important et peut améliorer considérablement les performances globales obtenues. Pour faire face à la grande diversité des applications, des systèmes STM et des plates-formes, nous proposons une approche basée sur l'Apprentissage Automatique (Machine Learning) pour prédire automatiquement les stratégies de placement de threads appropriées pour les applications de TM. Au cours d'une phase d'apprentissage préliminaire, nous construisons les profiles des applications s'exécutant sur différents systèmes STM pour obtenir un prédicteur. Nous utilisons ensuite ce prédicteur pour placer les threads de façon statique ou dynamique dans un système STM récent. Finalement, nous effectuons une évaluation expérimentale et nous montrons que l'approche statique est suffisamment précise et améliore les performances d'un ensemble d'applications d'un maximum de 18%. En ce qui concerne l'approche dynamique, nous montrons que l'on peut détecter des changements de phase d'exécution des applications composées des diverses charges de travail, en prévoyant une stratégie de placement appropriée pour chaque phase. Sur ces applications, nous avons obtenu des améliorations de performances d'un maximum de 31% par rapport à la meilleure stratégie statique. / Multicore processors are now a mainstream approach to deliver higher performance to parallel applications. In order to develop efficient parallel applications for those platforms, developers must take care of several aspects, ranging from the architectural to the application level. In this context, Transactional Memory (TM) appears as a programmer friendly alternative to traditional lock-based concurrency for those platforms. It allows programmers to write parallel code as transactions, which are guaranteed to execute atomically and in isolation regardless of eventual data races. At runtime, transactions are executed speculatively and conflicts are solved by re-executing conflicting transactions. Although TM intends to simplify concurrent programming, the best performance can only be obtained if the underlying runtime system matches the application and platform characteristics. The contributions of this thesis concern the analysis and improvement of the performance of TM applications based on Software Transactional Memory (STM) on multicore platforms. Firstly, we show that the TM model makes the performance analysis of TM applications a daunting task. To tackle this problem, we propose a generic and portable tracing mechanism that gathers specific TM events, allowing us to better understand the performances obtained. The traced data can be used, for instance, to discover if the TM application presents points of contention or if the contention is spread out over the whole execution. Our tracing mechanism can be used with different TM applications and STM systems without any changes in their original source codes. Secondly, we address the performance improvement of TM applications on multicores. We point out that thread mapping is very important for TM applications and it can considerably improve the global performances achieved. To deal with the large diversity of TM applications, STM systems and multicore platforms, we propose an approach based on Machine Learning to automatically predict suitable thread mapping strategies for TM applications. During a prior learning phase, we profile several TM applications running on different STM systems to construct a predictor. We then use the predictor to perform static or dynamic thread mapping in a state-of-the-art STM system, making it transparent to the users. Finally, we perform an experimental evaluation and we show that the static approach is fairly accurate and can improve the performance of a set of TM applications by up to 18%. Concerning the dynamic approach, we show that it can detect different phase changes during the execution of TM applications composed of diverse workloads, predicting thread mappings adapted for each phase. On those applications, we achieve performance improvements of up to 31% in comparison to the best static strategy.

Submitted by Gustavo José de Sousa null (gustavo.jo.sousa@gmail.com) on 2017-11-07T18:17:35Z No. of bitstreams: 1 dissertacao.pdf: 1114730 bytes, checksum: 360fec3dffa930a34e0cdc2bb0ff960d (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-11-21T13:38:05Z (GMT) No. of bitstreams: 1 sousa_gj_me_sjrp.pdf: 1114730 bytes, checksum: 360fec3dffa930a34e0cdc2bb0ff960d (MD5) / Made available in DSpace on 2017-11-21T13:38:05Z (GMT). No. of bitstreams: 1 sousa_gj_me_sjrp.pdf: 1114730 bytes, checksum: 360fec3dffa930a34e0cdc2bb0ff960d (MD5) Previous issue date: 2017-08-30 / Omissão de lock é uma técnica onde operações de aquisição e liberação de lock são omitidas (especulação) de forma a permitir que regiões críticas compartilhando um mesmo lock possam executar concorrentemente, permitindo assim se explorar um nível maior de concorrência em programas que utilizam esse método popular de sincronização. Para se manter o princípio de atomicidade, as modificações no estado do programa realizadas pela região crítica são mantidas em um buffer interno e são efetivadas apenas ao fim da mesma. Em caso de inconsistências, diferentes políticas em como proceder são possíveis, o que diferencia as diversas abordagens de omissão de lock encontradas na literatura. Por exemplo, a abordagem original, Speculative Lock Elision (SLE), que é implementada no nível microarquitetural, recorre a adquirir o lock de forma tradicional quando uma especulação falha. Em algumas situações, esta política conservadora acaba por restringir o ganho em desempenho originalmente pretendido por impor um volume de sincronização desnecessário (lemming effect). Uma forma de superar tal limitação é o emprego de omissão de lock transacional (Transactional Lock Elision, em inglês), onde a especulação de regiões críticas se dá por meio de transações e o controle de execução é devolvido ao software em eventos de transações abortadas, o que permite que diferentes estratégias sejam empregadas com o objetivo de permitir execução concorrente mesmo em presença de falha de especulação. Neste contexto, uma das abordagens possíveis é o esquema chamado Software-assisted Conflict Management (SCM), onde um lock auxiliar é utilizado para sincronizar transações abortadas e, assim, manter o lock original livre, permitindo que outras transações prossigam sua execução. No presente trabalho, uma extensão ao SCM é proposta, o esquema Fine-grained Software-assisted Conflict Management (FGSCM), onde múltiplos locks são utilizados para permitir que transações abortadas por conflitos em diferentes regiões de memória possam ser executadas de forma concorrente. O algoritmo proposto foi implementado utilizando a interface RTM da extensão Intel® TSX e experimentos foram realizados em um máquina quadcore, para os quais, em casos com predominância de operações de leitura em memória, observou-se um ganho em desempenho médio de 11% e 36% com relação à abordagem SCM original e ao uso de um spin lock comum, respectivamente. / Lock elision is a technique that omits acquire/release lock operations (speculation) so as to allow critical regions sharing the same lock to run concurrently, which yields a higher level of concurrency explored by programs that use such popular synchronization mechanism. In order to honor atomicity, modifications on the program's state made by the critical regions are kept in an internal buffer and only applied at the end of the speculation. If inconsistency is found, different policies on how to proceed are possible, which make up the several existing approaches found in the literature. As an example, the original one, namely Speculative Lock Elision (SLE), which is implemented at the level of microarchitecture, falls back to acquire the lock in a standard manner when there is speculation error. In some situations, such conservative policy ends up restricting the intended performance gains due to the unnecessary synchronization imposed (lemming effect). A way to address this issue is through Transactional Lock Elision (TLE) techniques, in which speculation of critical regions is done by means of transactions and execution control is passed back to software on abort events, which makes possible the use of different strategies to allow concurrent execution even in presence of speculation error. In this context, one possible approach is called Software-assisted Conflict Management (SCM), where an auxiliary lock is used to serialize aborted transactions and, as such, keep the original one free, so that others may proceed on their execution. The work presented in this document proposes an extension of SCM, called Fine-grained Software-assisted Conflict Management (FGSCM), where multiple auxiliary locks are applied in order to allow transactions aborted due to conflict on different regions of memory to be executed concurrently. The proposed algorithm was implemented by using the RTM interface from Intel®'s TSX extension and experiments were performed on a quadcore machine. On read-dominated workloads, an average performance gain of 11% and 36% was observed against the original SCM and a typical spin lock, respectively.

Memória Transacional tem se demonstrado um paradigma promissor na implementação de aplicações concorrentes sob memória compartilhada que busquem evitar um modelo de sincronização baseado em locks. Em vez de sujeitar a execução a um acesso exclusivo com base no valor de um lock que é compartilhado por threads concorrentes, uma aplicação sob Memória Transacional tenta executar seções críticas de modo otimista, desfazendo as modificações no caso de um conflito de acesso à memória. Entretanto, apesar de a abordagem baseada em locks ter adquirido um número significativo de ferramentas automatizadas para a depuração, profiling e otimização automatizados (por ser uma das técnicas de sincronização mais antigas e mais bem pesquisadas), o campo da Memória Transacional ainda é comparativamente recente, e programadores frequentemente precisam adaptar manualmente suas aplicações transacionais ao encontrar problemas de eficiência. Este trabalho propõe um sistema no qual o profiling de código em uma implementação de Memória Transacional simulada é utilizado para caracterizar uma aplicação transacional, formando a base para uma parametrização automatizada do respectivo sistema especulativo para uma execução eficiente do código em questão. Também é proposta uma abordagem de escalonamento de threads guiado por profiling em uma implementação de Memória Transacional baseada em software, usando dados coletados pelo profiler para prever a probabilidade de conflitos e determinar que thread escalonar com base nesta previsão. São apresentados os resultados de experimentos sob ambas as abordagens. / Transactional Memory has shown itself to be a promising paradigm for the implementation of shared-memory concurrent applications that eschew a lock-based model of data synchronization. Rather than conditioning exclusive access on the value of a lock that is shared across concurrent threads, Transactional Memory attempts to execute critical sections optimistically, rolling back the modifications in the event of a data access conflict. However, while the lock-based approach has acquired a significant body of debugging, profiling and automated optimization tools (as one of the oldest and most researched synchronization techniques), the field of Transactional Memory is still comparably recent, and programmers are usually tasked with an unguided manual tuning of their transactional applications when facing efficiency problems. We propose a system in which code profiling in a simulated hardware implementation of Transactional Memory is used to characterize a transactional application, which forms the basis for the automated tuning of the underlying speculative system for the efficient execution of that particular application. We also propose a profile-guided approach to the scheduling of threads in a software-based implementation of Transactional Memory, using collected data to predict the likelihood of conflicts and determine what thread to schedule based on this prediction. We present the results achieved under both designs.

A Memória Transacional (TM) surgiu nos últimos anos como uma nova solução para sincronização em sistemas multiprocessados de memória compartilhada, permitindo explorar melhor o paralelismo das aplicações ao evitar limitações inerentes ao mecanismo de locks. Neste modelo, o programador define regiões de código que devem executar de forma atômica. O sistema tenta executá-las de forma concorrente, e, em caso de conflito nos acessos à memória, toma as medidas necessárias para preservar a atomicidade e isolamento das transações, na maioria das vezes abortando e reexecutando uma das transações. Um dos modelos mais aceitos de memória transacional em hardware é o LogTM, implementado neste trabalho em um MPSoC embarcado que utiliza uma NoC para interconexão. Os experimentos fazem uma comparação desta implementação com locks, levando-se em consideração performance e energia do sistema. Além disso, este trabalho mostra que o tempo que uma transação espera para reiniciar sua execução após ter abortado (chamado de backoff delay on abort) tem impactos significativos na performance e energia. Uma análise deste impacto é feita utilizando-se de três políticas de backoff. Um mecanismo baseado em um handshake entre transações, chamado Abort handshake, é proposto como solução para o problema. Os resultados dos experimentos são dependentes da aplicação e configuração do sistema e indicam ganhos da TM na maioria dos casos em relação ao mecanismo de locks. Houve redução de até 30% no tempo de execução e de até 32% na energia de aplicações de baixa demanda de sincronização. Em um segundo momento, é feita uma análise do backoff delay on abort na performance e energia de aplicações utilizando três políticas de backoff em comparação com o mecanismo Abort handshake. Os resultados mostram que o mecanismo proposto apresenta redução de até 20% no tempo de execução e de até 53% na energia comparado à melhor política de backoff dentre as analisadas. Para aplicações com alta demanda de sincronização, a TM mostra redução no tempo de execução de até 63% e redução de energia de até 71% em comparação com o mecanismo de locks. / Transactional Memory (TM) has emerged in the last years as a new solution for synchronization on shared memory multiprocessor systems, allowing a better exploration of the parallelism of the applications by avoiding inherent limitations of the lock mechanism. In this model, the programmer defines regions of code, called transactions, to execute atomically. The system tries to execute transactions concurrently, but in case of conflict on memory accesses, it takes the appropriate measures to preserve the atomicity and isolation, usually aborting and re-executing one of the transactions. One of the most accepted hardware transactional memory model is LogTM, implemented in this work in an embedded MPSoC that uses an NoC as interconnection mechanism. The experiments compare this implementation with locks, considering performance and energy. Furthermore, this work shows that the time a transaction waits to restart after abort (called backoff delay on abort) has significant impact on performance and energy. An analysis of this impact is done using three backoff policies. A novel mechanism based on handshake of transactions, called Abort handshake, is proposed as a solution to this issue. The results of the experiments depends on application and system configuration and show TM benefits in most cases in comparison to the locks mechanism, reaching reduction on the execution time up to 30% and reduction on the energy consumption up to 32% on low contention workloads. After that, an analysis of the backoff delay on abort on the performance and energy is presented, comparing to the Abort handshake mechanism. The proposed mechanism shows reduction of up to 20% on the execution time and up to 53% on the energy, when compared to the best backoff policy. For applications with a high degree of synchronization, TM shows reduction on the execution time up to 63% and energy savings up to 71% compared to locks.

Orientador: Sandro Rigo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T08:11:55Z (GMT). No. of bitstreams: 1 Moreira_JoaoBatistaCorreaGomes_M.pdf: 4664392 bytes, checksum: 9057389ff1b0a5e68e89f32ea1310090 (MD5) Previous issue date: 2010 / Resumo: O surgimento das novas arquiteturas multiprocessadas introduziu novos desafios ao desenvolvimento de software. Dentre estes desafios está a dificuldade de realizar a sincronização adequada entre os fluxos de execução. Para solucionar este problema, novos mecanismos de sincronização com abstrações mais simplificadas tem sido propostos. Seguindo esta corrente, as Memórias Transacionais surgem como uma promissora alternativa aos mecanismos de sincronização tradicionais. Por se tratar de uma alternativa recentemente proposta, pouco se conhece a respeito dos efeitos no consumo de energia devido ao uso de Memórias Transacionais. Este trabalho apresenta um estudo comparativo entre os consumos de energia observados na execução do benchmark STAMP com usos de um sistema STM (Memória Transacional em Software) e de sincronização baseada em locks. Os resultados obtidos demonstram que a STM apresentou um desempenho inferior aos locks no que diz respeito ao consumo de energia, apresentando um consumo médio três vezes maior. Também foi avaliada a influência das penalidades decorrentes do uso de locks no consumo de energia, mostrando que, em sistemas cujo custo de falha na aquisição de um lock supera dez mil ciclos, a aplicação de STMs passa a ser uma abordagem competitiva. Durante os testes com Memórias Transacionais tornou-se clara a necessidade de ferramentas de simulação que possibilitam projetos de hardware e testes de software de forma mais ágil. Este trabalho descreve a implementação de uma plataforma de simulação para estimar o consumo de energia com abstração híbrida obtida a partir da integração de processadores funcionais que são gerados através da linguagem ArchC com a plataforma MPARM (que possui precisão de ciclos). Esta implementação atingiu ganhos de desempenho médios de até 2.1 vezes, com um máximo de 2.9 vezes. Imprecisões obtidas nas estimativas de consumo de energia puderam ser estatisticamente corrigidas através da aplicação de métodos de regressão linear, apresentando erros médios de 5,85%, sendo o erro mínimo e máximo de 0,87% e 19,6%, respectivamente / Abstract: The advent of the contemporary multiprocessor architectures has challenged software development. In order to overcome the hurdle of properly ordering the execution and data flows, new synchronization methods with simplified abstraction have been proposed. In this context, Transactional Memories have emerged as an alternative to traditional synchronization methods. Little is known about the effects on power consumption due to the use of ransactional memories since it is a recently proposed alternative. This work compares the Power consumption of the STAMP benchmark execution when using a STM system and a lockbased implementation. The results show that the STM implementation presented a worse performance, consuming three times more energy in avarage. In addition, the penalties deriving from the employment of locks in power consumption were assessed, indicating that, in systems where a failure in lock acquisition costs more than ten thousand cycles, the use of STMs becomes a competitive approach. The experiments with Transactional Memories executed during the first stage of this research indicated that faster simulation tools for hardware design and software testing are needed. Hence, this work describes an implementation of a simulation platform, built using hybrid abstraction level, that is able to estimate power consumption. The platform is the result of integrating functional processors described in the ArchC language with the MPARM platform, which is cycle-based. The implementation displays an average performance speedup of 2.1 and a maximum of 2.9. Inaccuracies due to power consumption estimation could be statistically adjusted by applying corrections based on linear regression. The model carries an average error of 5.85% with a maximum of 19.6% and minimum of 0.86% / Mestrado / Arquitetura de Computadores / Mestre em Ciência da Computação