Orientadores: Guido Costa Souza de Araújo, José Nelson Amaral / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T10:12:59Z (GMT). No. of bitstreams: 1 Pereira_MarcioMachado_D.pdf: 2922376 bytes, checksum: 9775914667eadf354d7e256fb2835859 (MD5) Previous issue date: 2015 / Resumo: Nos últimos anos, Memórias Transacionais (Transactional Memories ¿ TMs) têm-se mostrado um modelo de programação paralela que combina, de forma eficaz, a melhoria de desempenho com a facilidade de programação. Além disso, a recente introdução de extensões para suporte a TM por grandes fabricantes de microprocessadores, também parece endossá-la como um modelo de programação para aplicações paralelas. Uma das questões centrais na concepção de sistemas de TM em Software (STM) é identificar mecanismos ou heurísticas que possam minimizar a contenção decorrente dos conflitos entre transações. Apesar de já terem sido propostos vários mecanismos para reduzir a contenção, essas técnicas têm um alcance limitado, uma vez que o conflito é evitado por interrupção ou serialização da execução da transação, impactando consideravelmente o desempenho do programa. Este trabalho explora uma abordagem complementar para melhorar o desempenho de STM através da utilização de escalonadores. Um escalonador de TM é um componente de software que decide quando uma determinada transação deve ser executada ou não. Sua eficácia é muito sensível às métricas usadas para prever o comportamento das transações, especialmente em cenários de alta contenção. Este trabalho propõe um novo escalonador, Dynamic Transaction Scheduler ¿ DTS, para selecionar a próxima transação a ser executada. DTS é baseada em uma política de "recompensa pelo sucesso" e utiliza uma métrica que mede com melhor precisão o trabalho realizado por uma transação. Memórias Transacionais em Hardware (HTMs) são mecanismos interessante para implementar TM porque integram o suporte a transações no nível da arquitetura. Por outro lado, aplicações que usam HTM podem ter o seu desempenho dificultado pela falta de escalabilidade e transbordamento da cache de dados. Este trabalho apresenta um extenso estudo de desempenho de aplicações que usam HTM na arquitetura Haswell da Intel. Ele avalia os pontos fortes e fracos desta nova arquitetura, realizando uma exploração das várias características das aplicações de TM. Este estudo detalhado revela as restrições impostas pela nova arquitetura e introduz uma política de serialização simples, porém eficaz, para garantir o progresso das transações, além de proporcionar melhor desempenho / Abstract: In the last few years, Transactional Memories (TMs) have been shown to be a parallel programming model that can effectively combine performance improvement with ease of programming. Moreover, the recent introduction of (H)TM-based ISA extensions, by major microprocessor manufacturers, also seems to endorse TM as a programming model for today¿s parallel applications. One of the central issues in designing Software TM (STM) systems is to identify mechanisms or heuristics that can minimize contention arising from conflicting transactions. Although a number of mechanisms have been proposed to tackle contention, such techniques have a limited scope, because conflict is avoided by either interrupting or serializing transaction execution, thus considerably impacting performance. This work explores a complementary approach to boost the performance of STM through the use of schedulers. A TM scheduler is a software component that decides when a particular transaction should be executed. Their effectiveness is very sensitive to the accuracy of the metrics used to predict transaction behaviour, particularly in high-contention scenarios. This work proposes a new Dynamic Transaction Scheduler ¿ DTS to select a transaction to execute next, based on a new policy that rewards success and an improved metric that measures the amount of effective work performed by a transaction. Hardware TMs (HTM) are an interesting mechanism to implement TM as they integrate the support for transactions at the lowest, most efficient, architectural level. On the other hand, for some applications, HTMs can have their performance hindered by the lack of scalability and by limitations in cache store capacity. This work presents an extensive performance study of the implementation of HTM in the Haswell generation of Intel x86 core processors. It evaluates the strengths and weaknesses of this new architecture by exploring several dimensions in the space of TM application characteristics. This detailed performance study provides insights on the constraints imposed by the Intel¿s Transaction Synchronization Extension (Intel¿s TSX) and introduces a simple, but efficient, serialization policy for guaranteeing forward progress on top of the best-effort Intel¿s HTM which was critical to achieving performance / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

The project, Spider III, presents architecture and protocol of a multi-agent-based internet distributed computing system, which provides a convenient development and execution environment for transparent task distribution, load balancing, and fault tolerance. Spider is an on going distribution computing project in the Department of Computer Science, California State University San Bernardino. It was first proposed as an object-oriented distributed system by Han-Sheng Yuh in his master's thesis in 1997. It has been further developed by Koping Wang in his master's project, of where he made large contribution and implemented the Spider II System.

This thesis presents the developed taxonomy of the agent-based distributed computing systems. Based on this taxonomy, a design, implementation, analysis and distribution protocol of a multi-agent architecture for internet-based distributed computing system was developed. A prototype of the designed architecture was implemented on Spider III using the IBM Aglets software development kit (ASDK 2.0) and the language Java.

Exploiting better performance from computer programs translates to finding more instructions to execute in parallel. Since most general purpose programs are written in an imperatively sequential manner, closely lying instructions are always data dependent, making the designer look far ahead into the program for parallelism. This necessitates wider superscalar processors with larger instruction windows. But superscalars suffer from three key limitations, their inability to scale, sequential fetch bottleneck and high branch misprediction penalty. Recent studies indicate that current superscalars have reached the end of the road and designers will have to look for newer ideas to build computer processors. Speculative Multithreading (SpMT) is one of the most recent techniques to exploit parallelism from applications. Most SpMT architectures partition a sequential program into multiple threads (or tasks) that can be concurrently executed on multiple processing units. It is desirable that these tasks are sufficiently distant from each other so as to facilitate parallelism. It is also desirable that these tasks are control independent of each other so that execution of a future task is guaranteed in case of local control flow misspeculations. Some task prediction mechanisms rely on the compiler requiring recompilation of programs. Current dynamic mechanisms either rely on program constructs like loop iterations and function and loop boundaries, resulting in unbalanced loads, or predict tasks which are too short to be of use in an SpMT architecture. This thesis is the first proposal of a predictor that dynamically predicts control independent tasks that are consistently wide apart, and executes them on a novel SpMT architecture.

<p dir="ltr">Heterogeneous clusters with nodes containing one or more accelerators, such as GPUs, have become common. While MPI provides inter-address space communication, and OpenCL provides a process with access to heterogeneous computational resources, programmers are forced to write hybrid programs that manage the interaction of both of these systems. This paper describes an array programming interface that provides users with automatic and manual distributions of data and work. Using work distribution and kernel def and use information, communication among processes and devices in a process is performed automatically. By providing a unified programming model to the user, program development is simplified.</p>

Os sistemas fotovoltaicos tem se difundido mundialmente como uma tecnologia de energia limpa que pode ser utilizada na maior parte do planeta Terra. Isto o torna um sistema muito interessante para geração distribuída. A peça fundamental para o aproveitamento da energia fotovoltaica na geração distribuída é o inversor conectado a rede elétrica. Assim o rendimento deste equipamento influencia diretamente no aproveitamento da energia gerada pelos painéis fotovoltaicos e consequentemente no tempo em que o sistema se paga. O comportamento sazonal da geração de energia, onde o inversor trabalha na maior parte do tempo entre 10% e 90% da capacidade, principalmente em sistemas sem rastreamento, não permite que o inversor seja avaliado somente pelo seu rendimento em plena carga, mas pela curva de rendimento completa em toda faixa de operação. O método proposto para a melhora do rendimento do sistema em baixas potências é a utilização de inversores de baixa potência conectados a rede elétrica em paralelo trabalhando de maneira escalonada. Assim, em baixas potências o rendimento é mais elevado que se fosse utilizado um único inversor. Neste trabalho são avaliados também as consequências do paralelismo na taxa de distorção harmônica da corrente e as vantagens de ampliação na vida útil dos equipamentos e o recurso de redundância. Foram implementados 4 inversores de 300W de saída, na topologia ponte completa com frequência de comutação e amostragem de 21,6kHz, controlados cada um por um DSC 56F8014 da Freescale, e um dispositivo para monitoração dos inversores utilizando um microcontrolador PIC18F4520. Todos os dispositivos possuem interface de comunicação UART isolada com protocolo LIN. Os inversores foram testados em operação com modo de compartilhamento de potência contínuo, onde todos os inversores operam com parcelas identicas de potência, e no modo escalonado, onde os inversores entram em operação sob a demanda da potência a ser processada. Os resultados apresentam uma melhora de 3,7% no rendimento entre o sistema de compartilhamento de potência contínuo e escalonado, avaliados pelo rendimento ponderado do sistema (IEC-61836). / Photovoltaic systems have been spreading globally as a clean energy technology that can be used in most of the planet Earth. This makes it a very interesting system for distributed generation. The key to the use of photovoltaics in distributed generation inverter is connected to the power grid. Thus the performance of this equipment directly influences the use of energy generated by the photovoltaic panels and consequently the time that the system pays for itself. The seasonal behavior of power generation, where the drive works most of the time between 10% and 90% of capacity, especially in systems without tracking, does not allow the drive to be evaluated not only by their performance at full load, but the full yield curve throughout the operating range. The proposed method improves the system performance at low power is the use of low power inverters connected in parallel to mains electricity working in installments. Thus, in the low power output is higher than if a single drive were used. This work also evaluated the consequences of parallelism in the rate of harmonic current distortion and benefits of expanding the life of the equipment and the use of redundancy . We implemented four inverters 300W output full bridge topology with switching frequency of 21.6 kHz and sampling, each controlled by a Freescale 56F8014 DSC, and a device for monitoring the inverters using a PIC18F4520 microcontroler. All devices have isolated communication interface UART with LIN protocol. The inverters were tested in operation mode continuous power sharing , where all the inverters operate with identical plots power, and staggered where the inverters come into operation upon the demand of power being processed. The results show an improvement of 3,7% in revenue sharing system between the power and continued staggered valued at weighted yield of the system (IEC-61836). / 5000

Este trabalho apresenta o projeto e a implementação prática de um método completo para ser utilizado na conexão de UPSs monofásicos em paralelo. Existe um algoritmo que executa o droop de fase/frequência, e um novo método que trabalha com e sem comunicação de dados entre os inversores. Quando a comunicação está ativa, um novo algoritmo é utilizado, inserindo um resistência virtual variável, junto com o compartilhamento de potência ativa, obtendo um baixo valor de THD (Total Harmonic Distortion) na tensão de saída e bom compartilhamento de potência. Quando a comunicação de dados não funciona, uma resistência virtual constante é inserida, aumentando a THD de saída com carga não-linear, mas ainda proporcionando um bom compartilhamento de potência ativa. A vantagem é poder obter um bom desempenho quando a comunicação de dados está operando, mas, no caso de sua falha, o sistema ainda funciona, proporcionando maior confiabilidade. A implementação possui um algoritmo de emulação de carga eletrônica, com o propósito de executar testes de produção, baseado no mesmo algoritmo de paralelismo, apenas mudando algumas variáveis. / This work presents the design and experimental implementation of a complete paralleling method to be used for parallel single-phase UPSs connection. There is a algorithm that performs a phase/frequency droop, and a new method to work with or without data communication among the inverters. When communication is working, a new algorithm is used, inserting a variable virtual resistance in the output, along with active power sharing, obtaining a low output voltage THD (Total Harmonic Distortion) value and good power sharing. Without communication a constant virtual resistance is inserted, increasing the output THD with non-linear load, but still allowing a good active power sharing. The advantage is to obtain a good performance operation with communication, but, in case of communication failure, the system still works providing more reliability. The implementation have a electronic load emulation algorithm, with purpose to execute factory tests, based in the same parallelism algorithm, just changing some variables.

Os sistemas fotovoltaicos tem se difundido mundialmente como uma tecnologia de energia limpa que pode ser utilizada na maior parte do planeta Terra. Isto o torna um sistema muito interessante para geração distribuída. A peça fundamental para o aproveitamento da energia fotovoltaica na geração distribuída é o inversor conectado a rede elétrica. Assim o rendimento deste equipamento influencia diretamente no aproveitamento da energia gerada pelos painéis fotovoltaicos e consequentemente no tempo em que o sistema se paga. O comportamento sazonal da geração de energia, onde o inversor trabalha na maior parte do tempo entre 10% e 90% da capacidade, principalmente em sistemas sem rastreamento, não permite que o inversor seja avaliado somente pelo seu rendimento em plena carga, mas pela curva de rendimento completa em toda faixa de operação. O método proposto para a melhora do rendimento do sistema em baixas potências é a utilização de inversores de baixa potência conectados a rede elétrica em paralelo trabalhando de maneira escalonada. Assim, em baixas potências o rendimento é mais elevado que se fosse utilizado um único inversor. Neste trabalho são avaliados também as consequências do paralelismo na taxa de distorção harmônica da corrente e as vantagens de ampliação na vida útil dos equipamentos e o recurso de redundância. Foram implementados 4 inversores de 300W de saída, na topologia ponte completa com frequência de comutação e amostragem de 21,6kHz, controlados cada um por um DSC 56F8014 da Freescale, e um dispositivo para monitoração dos inversores utilizando um microcontrolador PIC18F4520. Todos os dispositivos possuem interface de comunicação UART isolada com protocolo LIN. Os inversores foram testados em operação com modo de compartilhamento de potência contínuo, onde todos os inversores operam com parcelas identicas de potência, e no modo escalonado, onde os inversores entram em operação sob a demanda da potência a ser processada. Os resultados apresentam uma melhora de 3,7% no rendimento entre o sistema de compartilhamento de potência contínuo e escalonado, avaliados pelo rendimento ponderado do sistema (IEC-61836). / Photovoltaic systems have been spreading globally as a clean energy technology that can be used in most of the planet Earth. This makes it a very interesting system for distributed generation. The key to the use of photovoltaics in distributed generation inverter is connected to the power grid. Thus the performance of this equipment directly influences the use of energy generated by the photovoltaic panels and consequently the time that the system pays for itself. The seasonal behavior of power generation, where the drive works most of the time between 10% and 90% of capacity, especially in systems without tracking, does not allow the drive to be evaluated not only by their performance at full load, but the full yield curve throughout the operating range. The proposed method improves the system performance at low power is the use of low power inverters connected in parallel to mains electricity working in installments. Thus, in the low power output is higher than if a single drive were used. This work also evaluated the consequences of parallelism in the rate of harmonic current distortion and benefits of expanding the life of the equipment and the use of redundancy . We implemented four inverters 300W output full bridge topology with switching frequency of 21.6 kHz and sampling, each controlled by a Freescale 56F8014 DSC, and a device for monitoring the inverters using a PIC18F4520 microcontroler. All devices have isolated communication interface UART with LIN protocol. The inverters were tested in operation mode continuous power sharing , where all the inverters operate with identical plots power, and staggered where the inverters come into operation upon the demand of power being processed. The results show an improvement of 3,7% in revenue sharing system between the power and continued staggered valued at weighted yield of the system (IEC-61836). / 5000

Este trabalho apresenta o projeto e a implementação prática de um método completo para ser utilizado na conexão de UPSs monofásicos em paralelo. Existe um algoritmo que executa o droop de fase/frequência, e um novo método que trabalha com e sem comunicação de dados entre os inversores. Quando a comunicação está ativa, um novo algoritmo é utilizado, inserindo um resistência virtual variável, junto com o compartilhamento de potência ativa, obtendo um baixo valor de THD (Total Harmonic Distortion) na tensão de saída e bom compartilhamento de potência. Quando a comunicação de dados não funciona, uma resistência virtual constante é inserida, aumentando a THD de saída com carga não-linear, mas ainda proporcionando um bom compartilhamento de potência ativa. A vantagem é poder obter um bom desempenho quando a comunicação de dados está operando, mas, no caso de sua falha, o sistema ainda funciona, proporcionando maior confiabilidade. A implementação possui um algoritmo de emulação de carga eletrônica, com o propósito de executar testes de produção, baseado no mesmo algoritmo de paralelismo, apenas mudando algumas variáveis. / This work presents the design and experimental implementation of a complete paralleling method to be used for parallel single-phase UPSs connection. There is a algorithm that performs a phase/frequency droop, and a new method to work with or without data communication among the inverters. When communication is working, a new algorithm is used, inserting a variable virtual resistance in the output, along with active power sharing, obtaining a low output voltage THD (Total Harmonic Distortion) value and good power sharing. Without communication a constant virtual resistance is inserted, increasing the output THD with non-linear load, but still allowing a good active power sharing. The advantage is to obtain a good performance operation with communication, but, in case of communication failure, the system still works providing more reliability. The implementation have a electronic load emulation algorithm, with purpose to execute factory tests, based in the same parallelism algorithm, just changing some variables.

The effective use of GPUs for accelerating applications depends on a number of factors including effective asynchronous use of heterogeneous resources, reducing data transfer between CPU and GPU, increasing occupancy of GPU kernels, overlapping data transfers with computations, reducing GPU idling and kernel optimizations. Overcoming these challenges require considerable effort on the part of the application developers. Most optimization strategies are often proposed and tuned specifically for individual applications. Message-driven executions with over-decomposition of tasks constitute an important model for parallel programming and provide multiple benefits including communication-computation overlap and reduced idling on resources. Charm++ is one such message-driven language which employs over decomposition of tasks, computation-communication overlap and a measurement-based load balancer to achieve high CPU utilization. This research has developed an adaptive runtime framework for efficient executions of Charm++ message-driven parallel applications on GPU systems. In the first part of our research, we have developed a runtime framework, G-Charm with the focus primarily on optimizing regular applications. At runtime, G-Charm automatically combines multiple small GPU tasks into a single larger kernel which reduces the number of kernel invocations while improving CUDA occupancy. G-Charm also enables reuse of existing data in GPU global memory, performs GPU memory management and dynamic scheduling of tasks across CPU and GPU in order to reduce idle time. In order to combine the partial results obtained from the computations performed on CPU and GPU, G-Charm allows the user to specify an operator using which the partial results are combined at runtime. We also perform compile time code generation to reduce programming overhead. For Cholesky factorization, a regular parallel application, G-Charm provides 14% improvement over a highly tuned implementation. In the second part of our research, we extended our runtime to overcome the challenges presented by irregular applications such as a periodic generation of tasks, irregular memory access patterns and varying workloads during application execution. We developed models for deciding the number of tasks that can be combined into a kernel based on the rate of task generation, and the GPU occupancy of the tasks. For irregular applications, data reuse results in uncoalesced GPU memory access. We evaluated the effect of altering the global memory access pattern in improving coalesced access. We’ve also developed adaptive methods for hybrid execution on CPU and GPU wherein we consider the varying workloads while scheduling tasks across the CPU and GPU. We demonstrate that our dynamic strategies result in 8-38% reduction in execution times for an N-body simulation application and a molecular dynamics application over the corresponding static strategies that are amenable for regular applications.