Orientador: Alexandro José Baldassin / Banca: Orlando de Andrade Figueiredo / Banca: Rodolfo Jardim de Azevedo / Resumo: 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... / Abstract: 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 ... / Mestre

Submitted by ADEMIR MARQUES JUNIOR null (adejunior_marques@hotmail.com) on 2016-06-01T16:14:13Z No. of bitstreams: 1 dissertacao.pdf: 1570162 bytes, checksum: 62279b5b860975f65c7da1a5dbddaa90 (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-06-02T14:41:35Z (GMT) No. of bitstreams: 1 marquesjunior_a_me_sjrp.pdf: 1570162 bytes, checksum: 62279b5b860975f65c7da1a5dbddaa90 (MD5) / Made available in DSpace on 2016-06-02T14:41:35Z (GMT). No. of bitstreams: 1 marquesjunior_a_me_sjrp.pdf: 1570162 bytes, checksum: 62279b5b860975f65c7da1a5dbddaa90 (MD5) Previous issue date: 2016-04-28 / O conceito de Memória Transacional foi criado para simplificar a sincronização de dados em memória, necessária para evitar a computação de dados inconsistentes por processadores multinúcleos, que se tornaram padrão devido às limitações encontradas em processadores de um núcleo. Em evolução constante pela busca de desempenho, os escalonadores de transação foram criados como alternativa aos gerenciadores de contenção presentes nos Sistemas de Memória Transacional. O consumo de energia é preocupação crescente, desde os grandes data centers até os disposítivos móveis que dependem de tempo de bateria, sendo também explorado no contexto de sistemas com Memória Transacional. Trabalhos anteriores consideraram, em sua maioria, somente o uso de gerenciadores de contenção, sendo o objetivo deste trabalho uma análise sobre o uso de escalonadores de transação. Desta forma, são exploradas nesta dissertação as técnicas de escalonamento dinâmico de tensão e frequência (DVFS) para a criação de uma heurística para a redução do consumo de energia utilizando o escalonador LUTS como base. Com o uso de aplicações do benchmark STAMP e biblioteca de memória transacional TinySTM, este trabalho faz uma análise sobre a eficiência energética dos escalonadores de referência ATS e LUTS, enquanto propõe uma nova heurística com o objetivo de reduzir o consumo de energia, denominada LUTSDynamic-Serializer, que alterna entre o uso de spinlock e de trava mutex de forma dinâmica. O uso desta heurística reduziu o EDP em até 17% e 61% em valores de EDP (Eenergy-Delay Product), e 4,95% e 15,8% na média geométrica das aplicações estudadas, em comparação aos escalonadores LUTS e ATS respectivamente, quando se utilizou a configuração de 8 threads, que é a limitação física de threads do processador utilizado no ambiente de experimento. / The Transactional Memory concept was created to simplify the synchronization of data in memory, needed to avoid computation of inconsistent data in multicore processors, which became standard due to limitations in single core processors. In constant search for performance, transactional schedulers were created as a alternative to contention managers present in transactional memory systems. The energy consumption is a crescent worry, ranging from big data centers to mobile devices which are dependent on battery life, and also being studied in Transactional Memory systems. Past works only considered the use of contention managers, and therefore this work seeks to analyse the impact of transactional schedulers. The techniques involving Dynamic Frequency-Voltage Scaling (DVFS) were explored with the motivation to create a heuristic to reduce energy consumption using the LUTS scheduler as a start. Utilizing the STAMP benchmark and the TinySTM transactional memory library, this work does an analysis about the energy efficiency of the reference scheduler ATS and LUTS, while proposing a new heuristic, named LUTSDynamic-Serializer, with the aim to reduce energy consumption by making a choice between spin-lock and mutex lock in a dynamic manner. We achieve with our heuristic up to 17% and 61% in EDP (Energy-Delay Product), and 4,95% and 15,8% considering the geometric mean among the applications studied, compared against the schedulers LUTS and ATS respectively, when we used the configuration with 8 threads, which is the physical limit of threads in the processor used in the experiments.

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

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.

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

Orientador: Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T23:05:30Z (GMT). No. of bitstreams: 1 Garcia_LeonardoAugustoGuimaraes_M.pdf: 3415043 bytes, checksum: 9df4293802303aa68e123c48882f387f (MD5) Previous issue date: 2013 / Resumo: A evolução das arquiteturas de computadores nos últimos anos, com a considerável introdução de processadores com vários núcleos e computadores com vários processadores, inclusive em máquinas consideradas de baixo poder de processamento, faz com que seja primordial o desenvolvimento de novos paradigmas e modelos de programação paralela que sejam fáceis de usar e depurar pela grande maioria dos programadores de sistemas. Os modelos de programação paralela, atualmente disponíveis, são baseados em primitivas de implementação cujo uso é complexo, tedioso e altamente sujeito a erros como, por exemplo, locks, semáforos, sinais, mutexes, monitores e threads. Neste cenário, as Memórias Transacionais (TM) aparecem como uma alternativa promissora que promete ser eficiente e, ao mesmo tempo, fácil de programar. Muita pesquisa foi feita nos últimos anos em relação às Memórias Transacionais em Software (STM), a maior parte delas relacionada a seu desempenho, com pouca atenção dada a outras métricas importantes, como, por exemplo, o consumo energético e como este se relaciona com o tempo de execução - energy-delay product (EDP). Esta dissertação de mestrado faz uma avaliação destas métricas em uma STM configurada com diversas políticas de gerenciamento da TM e de utilização energética, sendo algumas destas combinações inéditas. É mostrado que os resultados para desempenho e EDP nem sempre seguem a mesma tendência e, portanto, pode ser apropriado escolher diferentes políticas de gerenciamento dependendo de qual é o foco da otimização que se deseja fazer, sendo que algumas vezes a execução sequencial pode ser melhor que qualquer execução paralela. De uma forma geral, a execução com o uso de TM foi mais rápida quando comparada com a execução sequencial em dois terços dos casos analisados e teve melhor EDP em um terço das execuções. Através desta análise foi possível derivar um conjunto mínimo de políticas de gerenciamento da TM que foram capazes de entregar melhor resultado para o conjunto de benchmarks estudados, além de identificar tendências sobre o comportamento dos sistemas de TM para grupos de benchmarks quando se varia o número de núcleos executando em paralelo e o tamanho da carga de trabalho / Abstract: The recent unveilings on the computer architecture area, with the massive introduction of multi-core processors and computers with many processors in the last years, even in embedded systems, has brought to light the necessity to develop new paradigms and models for parallel programming that could be leveraged and are easy to debug by the majority of the developers. The current parallel programming models are based on primitives whose use is complex, tedious and highly error prone, such as locks, semaphores, signals, mutexes, monitors and threads. In this scenario, the Transactional Memories (TM) appear as a promising alternative which aims to be efficient and, at the same time, easy to program. Lots of research have been made on the past years on Software Transactional Memories (STM), the majority of them interested on the performance of such systems, with little attention given to other metrics such as energy and the relationship between energy and performance, known as the energy-delay product (EDP). This work evaluates these metrics in an STM configured with a number of TM and energy management policies, some of them new. It is shown that performance and EDP do not always follow the same trend, and, because of that, it might be appropriate to choose different management policies depending on the optimization target. It is also important to never forget about the sequential execution, as it can be more advantageous than any parallel execution in some scenarios. Overall, the execution with TM has a better performance when compared to the sequential execution in two thirds of the analysed situations, and a better EDP in one third of the scenarios. Through the analysis made in this work, it was possible to derive a minimal set of TM management policies that were able to deliver the best results with the benchmarks analysed. It was also possible to identify behavioural trends on the TM systems in certain sets of benchmarks when changing the number of cores in the execution and the workload size / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-09T13:43:25Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Francisco Miranda Soares da Silva Neto.pdf: 1968720 bytes, checksum: 60383d7751d95b545cae9a16a83f611c (MD5) / Made available in DSpace on 2015-03-09T13:43:26Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Francisco Miranda Soares da Silva Neto.pdf: 1968720 bytes, checksum: 60383d7751d95b545cae9a16a83f611c (MD5) Previous issue date: 2014-02-27 / In recent years, the diminishing rate with which we can increase the amount of transistors in a processor core has slowed down the increase of computers’ power. Moore’s Law appears to be drawing to an end. With it, the assumption that software written today will be more efficiently executed in the future simply due to processors’ evolution is being challenged. On the other hand, parallel applications can still be made more efficient by distributing work among different processors to be executed at the same time, thus reducing overall execution time. To enable parallelization, we must have multiple processor cores. This has led to the popularization of multicore architectures. However, writing parallel applications is not trivial. A program must be either written from the start to be executed in parallel, or later adapted for parallel execution. The programmer has the error-prone task of parallelizing the application through use of concurrency and parallelism constructs. Locking, the most common concurrency option, presents risks for inexperienced programmers, such as the famous Deadlock and Livelock problems. As we move from single core architectures to multicore, our programming languages need to make it easier for the programmers to use concurrency. Many researchers have pointed at Software Transactional Memory (STM) as an answer to that issue, as it is a lock-free, abstract way to guarantee isolated access to shared resources. But adapting for STM a program that uses lock is not simple. Besides being an error-prone task, technical details of the language might require special attention to preserve the program’s behavior. In this dissertation, we propose a set of program transformations for concurrency constructs in Haskell, a purely functional programming language. They may be used to refactor a program’s existing locks into transactional constructs from Haskell’s STM implementation. This allows a programmer to gain the benefits of working on STM even for programs which were already developed using locks. Each transformation is accompanied by execution examples and a discussion on its ability to preserve program behavior. We also present a supporting study, in which a controlled experiment was used to evaluate the benefits of locks or STM for the development of Haskell programs. Although subjects’ opinions tended to favor lock-based concurrency, those which used STM overall committed significantly fewer mistakes and required on average 12% less time to finish their assignments. / Recentemente, a queda na taxa de crescimento da quantidade de transístores integráveis em processadores tem desacelerado o crescimento de poder computacional. A lei de Moore parece aproximar-se de seu fim. Com isso, é desafiada a premissa de que software escrito hoje terá melhor desempenho no futuro simplesmente devido à evolução dos processadores. Ainda assim, aplicações paralelas ainda podem se tornar mais eficientes ao se distribuir trabalho entre diferentes processadores para execução simultânea. Para permitir a paralelização, são necessários múltiplos núcleos de processamento, o que tem levado à popularização de arquiteturas multinúcleo. Entretanto, a escrita de aplicações paralelas não é trivial. Deve-se escrever um programa para execução paralela desde sua concepção, ou adaptá-lo posteriormente para execução paralela. O programador tem a difícil tarefa de paralelização da aplicação através do uso de construções de concorrência e paralelismo. Travas, a mais comum opção para concorrência, apresentam riscos para programadores inexperientes, tais quais os famosos problemas de Deadlock e Livelock. Ao adaptarem-se de arquiteturas de um único núcleo para as de multinúcleo, as linguagens de programação precisam facilitar o uso de concorrência para os programadores. Muitos pesquisadores têm indicado Memória Transacional em Software (STM, do inglês Software Transactional Memory) como a resposta para esse problema, por ser uma forma abstrata e não bloqueante para garantia de acesso isolado a recursos compartilhados. Mas adaptar para STM programas que usam travas não é simples. Além de ser uma atividade propensa a erros, detalhes técnicos da linguagem podem requerer cuidados para se preservar o comportamento do programa. Nesta dissertação, é proposto um conjunto de transformações de programas para construções de concorrência em Haskell, uma linguagem de programação puramente funcional. Elas podem ser usadas para refatorar travas de um programa para uso de construções transacionais da implementação de STM em Haskell. Isso permite ao programador aproveitar os benefícios do trabalho com STM mesmo para programas já desenvolvidos com uso de travas. Cada transformação é acompanhada de exemplos de execução e uma discussão sobre sua capacidade de preservar o comportamento do programa. Também é apresentado um estudo de apoio, no qual um experimento controlado foi usado para avaliar os benefícios do uso de travas ou STM no desenvolvimento de programas em Haskell. Apesar das opiniões dos participantes terem favorecido o uso de travas, aqueles que usaram STM cometeram em geral menos erros e em média precisaram de 12% a menos de tempo para terminar suas tarefas.

Orientador: Sandro Rigo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-13T10:38:16Z (GMT). No. of bitstreams: 1 Kronbauer_FernandoAndre_M.pdf: 3637569 bytes, checksum: 4c5752e2ae7f853d3b5f4971d6d7cbab (MD5) Previous issue date: 2009 / Resumo: Enquanto que arquiteturas paralelas vão se tornando cada vez mais comuns na indústria de computação mais e mais programadores precisam escrever programas paralelos e desta forma são expostos aos problemas relacionados ao uso dos mecanismos tradicionais de controle de concorrência. Memórias transacionais têm sido propostas como um meio de aliviar as dificuldades encontradas ao escreverem-se programas paralelos: o desenvolvedor precisa apenas marcar as seções de código que devem ser executadas de forma atômica e isolada - na forma de transações, e o sistema cuida dos detalhes de sincronização. Neste traba­lho exploramos propostas de memórias transacionais com suporte específico em hardware (HTM), desenvolvendo uma plataforma flexível para a prototipagem, simulação e carac­terização destes sistemas. Também exploramos um sistema de memória transacional com suporte apenas em software (STM), apresentando uma abordagem nova para gerenciar a contenção entre transações. Esta abordagem leva em consideração os padrões de acesso aos diferentes dados de um programa ao escolher o gerenciador de contenção a ser usado para o acesso a estes dados. Elaboramos uma modificação da plataforma de STM que nos permite realizar esta associação entre dados e gerenciamento de contenção, e a partir desta implementação realizamos uma caracterização baseada nos padrões de acesso aos dados de um programa executando em diferentes sistemas de computação. Os resultados de nosso trabalho mostram a viabilidade do uso de memórias transacionais em um ambi­ente de pesquisa acadêmica, e apontam caminhos para a realização de trabalhos futuros que aumentem a viabilidade do seu uso também pela indústria. / Abstract: As parallel architectures become prevalent in the computer industry, more and more programmers are required to write parallel programs and are thus being exposed to the problems related to the use of traditional mechanisms for concurrency control. Transactional memory has been devised as a means for easing the burden of writing parallel Programs: the programmer has only to mark the sections of code that are to be executed in an atomic and isolated way - in the form of transactions, and the system takes care of the synchronization details. In this work we explore different proposals of transactional memories based on specific hardware support (HTM), developing a flexible platform for the prototyping, simulation and characterization of these systems. We also explore a transactional memory system based solely on software support (STM), devising a novel approach for managing the contention among transactions. This new approach takes into account access patterns to different data in an application when choosing the contention management strategy to be used for the access to these data. We made modifications to the STM system in order to enable the association of the data with the contention manager algorithm, and using the new implementation we characterized the STM system based on the access patterns to the data of a program, running it on different hardware. Our results show the viability of the use of transactional memories in an academic environment, and serve as a basis for the proposal of different directions to be followed in future research work, aimed at leveraging the use of transactional memories by the industry. / Mestrado / Mestre em Ciência da Computação

Orientador: Paulo Cesar Centoducatte / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T20:59:38Z (GMT). No. of bitstreams: 1 Baldassin_AlexandroJose_D.pdf: 1596141 bytes, checksum: 265aa763c420b69f70d59ff687bd8ad9 (MD5) Previous issue date: 2009 / Resumo: A adoção dos microprocessadores com múltiplos núcleos de execução pela indústria semicondutora tem criado uma crescente necessidade por novas linguagens, metodologias e ferramentas que tornem o desenvolvimento de sistemas concorrentes mais rápido, eficiente e acessível aos programadores de todos os níveis. Uma das principais dificuldades em programação concorrente com memória compartilhada é garantir a correta sincronização do código, evitando assim condições de corrida que podem levar o sistema a um estado inconsistente. A sincronização tem sido tradicionalmente realizada através de métodos baseados em travas, reconhecidos amplamente por serem de difícil uso e pelas anomalias causadas. Um novo mecanismo, conhecido como memória transacional (TM), tem sido alvo de muita pesquisa recentemente e promete simplificar o processo de sincronização, além de possibilitar maior oportunidade para extração de paralelismo e consequente desempenho. O cerne desta tese é formado por três trabalhos desenvolvidos no contexto dos sistemas de memória transacional em software (STM). Primeiramente, apresentamos uma implementação de STM para processadores assimétricos, usando a arquitetura Cell/B.E. como foco. Como principal resultado, constatamos que o uso de sistemas transacionais em arquiteturas assimétricas também é promissor, principalmente pelo fator escalabilidade. No segundo trabalho, adotamos uma abordagem diferente e sugerimos um sistema de STM especialmente voltado para o domínio de jogos computacionais. O principal motivo que nos levou nesta direção é o baixo desempenho das implementações atuais de STM. Um estudo de caso conduzido a partir de um jogo complexo mostra a eficácia do sistema proposto. Finalmente, apresentamos pela primeira vez uma caracterização do consumo de energia de um sistema de STM considerado estado da arte. Além da caracterização, também propomos uma técnica para redução do consumo em casos de alta contenção. Resultados obtidos a partir dessa técnica revelam ganhos de até 87% no consumo de energia / Abstract: The shift towards multicore processors taken by the semiconductor industry has initiated an era in which new languages, methodologies and tools are of paramount importance to the development of efficient concurrent systems that can be built in a timely way by all kinds of programmers. One of the main obstacles faced by programmers when dealing with shared memory programming concerns the use of synchronization mechanisms so as to avoid race conditions that could possibly lead the system to an inconsistent state. Synchronization has been traditionally achieved by means of locks (or variations thereof), widely known by their anomalies and hard-to-get-it-right facets. A new mechanism, known as transactional memory (TM), has recently been the focus of a lot of research and shows potential to simplify code synchronization as well as delivering more parallelism and, therefore, better performance. This thesis presents three works focused on different aspects of software transactional memory (STM) systems. Firstly, we show an STM implementation for asymmetric processors, focusing on the architecture of Cell/B.E. As an important result, we find out that memory transactions are indeed promising for asymmetric architectures, specially due to their scalability. Secondly, we take a different approach to STM implementation by devising a system specially targeted at computer games. The decision was guided by poor performance figures usually seen on current STM implementations. We also conduct a case study using a complex game that effectively shows the system's efficiency. Finally, we present the energy consumption characterization of a state-of-the-art STM for the first time. Based on the observed characterization, we also propose a technique aimed at reducing energy consumption in highly contended scenarios. Our results show that the technique is indeed effective in such cases, improving the energy consumption by up to 87% / Doutorado / Sistemas de Computação / Doutor em Ciência da Computação

Orientador: Guido Costa Souza de Araújo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T08:27:32Z (GMT). No. of bitstreams: 1 Nicacio_DanielHenricusdeKnegtDutra_D.pdf: 2579331 bytes, checksum: b8e15a6f91203b98455f39d63d63a634 (MD5) Previous issue date: 2012 / Resumo: Sistemas de Memória Transacional em Software (MTS) têm sido usados como uma abordagem para melhorar o desempenho ao permitir a execução concorrente de blocos atômicos. Porém, em cenários com alta contenção, sistemas baseados em MTS podem diminuir o desempenho consideravelmente, já que a taxa de conflitos aumenta. Políticas de gerenciamento de contenção têm sido usadas como uma forma de selecionar qual transação abortar quando um conflito ocorre. No geral, gerenciadores de contenção não são capazes de evitar conflitos, tendo em vista que eles apenas selecionam qual transação abortar e o momento em que ela deve reiniciar. Como gerenciadores de contenção agem somente após a detecção de um conflito, é difícil aumentar a taxa de transações finalizadas com sucesso. Abordagens mais pró-ativas foram propostas, focando na previsão de quando uma transação deve abortar e atrasando o início de sua execução. Contudo, as técnicas pró-ativas continuam sendo limitadas, já que elas não substituem a transação fadada a abortar por outra transação com melhores probabilidades de sucesso, ou quando o fazem, dependem do sistema operacional para essa tarefa, tendo pouco ou nenhum controle de qual transação será a substituta. Esta tese apresenta o LUTS, Lightweight User-Level Transaction Scheduler, um escalonador de transação de baixo custo em nível de usuário. Diferente de outras técnicas, LUTS provê maneiras de selecionar outra transação a ser executada em paralelo, melhorando o desempenho do sistema. Nós discutimos o projeto do LUTS e propomos uma heurística dinâmica, com o objetivo de evitar conflitos, que foi construída utilizando os métodos disponibilizados pelo LUTS. Resultados experimentais, conduzidos com os conjuntos de aplicações STAMP e STMBench7, e executando nas bibliotecas TinySTM e SwissTM, mostram como nossa heurística para evitar conflitos pode melhorar efetivamente o desempenho de sistema de MTS em aplicações com alta contenção / Abstract: Software Transaction Memory (STM) systems have been used as an approach to improve performance, by allowing the concurrent execution of atomic blocks. However, under high-contention workloads, STM-based systems can considerably degrade performance, as transaction conflict rate increases. Contention management policies have been used as a way to select which transaction to abort when a conflict occurs. In general, contention managers are not capable of avoiding conflicts, as they can only select which transaction to abort and the moment it should restart. Since contention manager's act only after a conflict is detected, it becomes harder to effectively increase transaction throughput. More proactive approaches have emerged, aiming at predicting when a transaction is likely to abort, postponing its execution. Nevertheless, most of the proposed proactive techniques are limited, as they do not replace the doomed transaction by another or, when they do, they rely on the operating system for that, having little or no control on which transaction to run. This article proposes LUTS, a Lightweight User-Level Transaction Scheduler. Unlike other techniques, LUTS provides the means for selecting another transaction to run in parallel, thus improving system throughput. We discuss LUTS design and propose a dynamic conflict-avoidance heuristic built around its scheduling capabilities. Experimental results, conducted with the STAMP and STMBench7 benchmark suites, running on TinySTM and SwissTM, show how our conflict-avoidance heuristic can effectively improve STM performance on high contention applications / Doutorado / Ciência da Computação / Doutor em Ciência da Computação