O desempenho de um software depende das múltiplas otimizações no código realizadas por compiladores modernos para a remoção de computação redundante. A identificação de computação redundante é, em geral, indecidível em tempo de compilação, e impede a obtenção de um caso ideal de referência para a medição do potencial inexplorado de remoção de redundâncias remanescentes e para a avaliação da eficácia de otimização do código. Este trabalho apresenta um conjunto de métodos para a análise da efetividade de otimização de código através da observação do conjunto completo de instruções dinamicamente executadas e referências à memória na execução completa de um programa. Isso é feito por meio do desenvolvimento de um algoritmo de value numbering dinâmico e sua aplicação conforme as instruções vão sendo executadas. Este método reduz a análise interprocedural à análise de um grande bloco básico e detecta operações redundantes de memória e operações escalares que são visíveis apenas em tempo de execução. Desta forma, o trabalho estende a análise de reuso de instruções e oferece tanto uma aproximação mais exata do limite superior de otimização explorável dentro de um programa, quanto um ponto de referência para avaliar a eficácia de uma otimização. O método também provê uma visão clara de hotspots de redundância não explorados e uma medida de localidade de valor dentro da execução completa de um programa. Um modelo que implementa o método e integra-o a um simulador completo de sistema baseado em Power ISA 64-bits (versão 2.06) é desenvolvido. Um estudo de caso apresenta os resultados da aplicação deste método em relação a executáveis de um benchmark representativo (SPECInt2006) criados para cada nível de otimização do compilador GNU C/ C++. A análise proposta produz uma avaliação prática de eficácia da otimização de código que revela uma quantidade significativa de redundâncias remanescentes inexploradas, mesmo quando o maior nível de otimização disponível é usado. Fontes de ineficiência são identificadas através da avaliação de hotspots e de localidade de valor. Estas informações revelam-se úteis para o ajuste do compilador e da aplicação. O trabalho ainda apresenta um mecanismo eficiente para explorar o suporte de hardware na eliminação de redundâncias. / Software performance relies on multiple optimization techniques applied by modern compilers to remove redundant computation. The identification of redundant computation is in general undecidable at compile-time and prevents one from obtaining an ideal reference for the measurement of the remaining unexploited potential of redundancy removal and for the evaluation of code optimization effectiveness. This work presents a methodology for optimization effectiveness analysis by observing the complete dynamic stream of executed instructions and memory references in the whole program execution, and by developing and applying a dynamic value numbering algorithm as instructions are executed. This method reduces the interprocedural analysis to the analysis of a large basic block and detects redundant memory and scalar operations that are visible only at run-time. This way, the work extends the instruction-reuse analysis and provides both a more accurate approximation of the upper bound of exploitable optimization in the program and a reference point to evaluate optimization effectiveness. The method also generates a clear picture of unexploited redundancy hotspots and a measure of value locality in the whole application execution. A framework that implements the method and integrates it with a full-system simulator based on Power ISA 64-bit (version 2.06) is developed. A case study presents the results of applying this method to representative benchmark (SPECInt 2006) executables generated by various compiler optimization levels of GNU C/C++ Compiler. The proposed analysis yields a practical analysis that reveals a significant amount of remaining unexploited redundancies present even when using the highest optimization level available. Sources of inefficiency are identified with an evaluation of hotspot and value locality, an information that is useful for compilers and application-tuning softwares. The thesis also shows an efficient mechanism to explore hardware-support for redundancy elimination.

O desempenho de um software depende das múltiplas otimizações no código realizadas por compiladores modernos para a remoção de computação redundante. A identificação de computação redundante é, em geral, indecidível em tempo de compilação, e impede a obtenção de um caso ideal de referência para a medição do potencial inexplorado de remoção de redundâncias remanescentes e para a avaliação da eficácia de otimização do código. Este trabalho apresenta um conjunto de métodos para a análise da efetividade de otimização de código através da observação do conjunto completo de instruções dinamicamente executadas e referências à memória na execução completa de um programa. Isso é feito por meio do desenvolvimento de um algoritmo de value numbering dinâmico e sua aplicação conforme as instruções vão sendo executadas. Este método reduz a análise interprocedural à análise de um grande bloco básico e detecta operações redundantes de memória e operações escalares que são visíveis apenas em tempo de execução. Desta forma, o trabalho estende a análise de reuso de instruções e oferece tanto uma aproximação mais exata do limite superior de otimização explorável dentro de um programa, quanto um ponto de referência para avaliar a eficácia de uma otimização. O método também provê uma visão clara de hotspots de redundância não explorados e uma medida de localidade de valor dentro da execução completa de um programa. Um modelo que implementa o método e integra-o a um simulador completo de sistema baseado em Power ISA 64-bits (versão 2.06) é desenvolvido. Um estudo de caso apresenta os resultados da aplicação deste método em relação a executáveis de um benchmark representativo (SPECInt2006) criados para cada nível de otimização do compilador GNU C/ C++. A análise proposta produz uma avaliação prática de eficácia da otimização de código que revela uma quantidade significativa de redundâncias remanescentes inexploradas, mesmo quando o maior nível de otimização disponível é usado. Fontes de ineficiência são identificadas através da avaliação de hotspots e de localidade de valor. Estas informações revelam-se úteis para o ajuste do compilador e da aplicação. O trabalho ainda apresenta um mecanismo eficiente para explorar o suporte de hardware na eliminação de redundâncias. / Software performance relies on multiple optimization techniques applied by modern compilers to remove redundant computation. The identification of redundant computation is in general undecidable at compile-time and prevents one from obtaining an ideal reference for the measurement of the remaining unexploited potential of redundancy removal and for the evaluation of code optimization effectiveness. This work presents a methodology for optimization effectiveness analysis by observing the complete dynamic stream of executed instructions and memory references in the whole program execution, and by developing and applying a dynamic value numbering algorithm as instructions are executed. This method reduces the interprocedural analysis to the analysis of a large basic block and detects redundant memory and scalar operations that are visible only at run-time. This way, the work extends the instruction-reuse analysis and provides both a more accurate approximation of the upper bound of exploitable optimization in the program and a reference point to evaluate optimization effectiveness. The method also generates a clear picture of unexploited redundancy hotspots and a measure of value locality in the whole application execution. A framework that implements the method and integrates it with a full-system simulator based on Power ISA 64-bit (version 2.06) is developed. A case study presents the results of applying this method to representative benchmark (SPECInt 2006) executables generated by various compiler optimization levels of GNU C/C++ Compiler. The proposed analysis yields a practical analysis that reveals a significant amount of remaining unexploited redundancies present even when using the highest optimization level available. Sources of inefficiency are identified with an evaluation of hotspot and value locality, an information that is useful for compilers and application-tuning softwares. The thesis also shows an efficient mechanism to explore hardware-support for redundancy elimination.

Orientador: Alexandro José Baldassin / Resumo: Com o crescimento contínuo do consumo de energia em microprocessadores,cientistas e engenheiros da computação redirecionaram atenção a arquiteturas heterogêneas, onde dispositivos de classes diferentes são usados para acelerar a computação. Dentre eles, existem as FPGAs (Field-Programmable Gate Arrays) cujo hardware pode ser reconfigurado após sua fabricação. Esta classe de dispositivos demonstra desempenho comparável aos processadores convencionais enquanto consomem apenas uma fração de energia. O uso de FPGAs vem se proliferando nos últimos anos e a perspectiva é que o nível de adoção continue a crescer. No entanto, programar FPGAs e aprimorar os programas para obter maior desempenho continua uma tarefa não trivial. Este trabalho apresenta uma compilação das principais transformações de código para otimização de programas direcionados à FPGAs. Neste trabalho também é avaliado o desempenho de programas executando em FPGAs. Mais especificamente, um subconjunto das transformações de código são aplicadas em um kernel OpenCL e os tempos de execução são medidos em um dispositivo da Intel®. Os resultados mostram que, sem a aplicação das transformações, o desempenho dos dispositivos é abaixo do que é observado quando as transformações são de fato aplicadas. / Abstract: With the ever increasing power wall in microprocessor design, scientists and engineers shifted their attention to heterogeneous architectures, where in several classes of devices are used for different kinds of computation. Among them are FPGAs whose hardware can be reconfigured after manufacturing. These devices offer comparable performance to CPUs while consuming only a fraction of energy. Infact, the use of FPGAs have been proliferating in recent years and should continue to do so considering the amount of attention these devices are receiving. Still, programmability and performance engineering in FPGAs remain hard. This work presents acompilation of the most prominent code transformations for optimizing code aimed at FPGAs. In this work we also evaluate the performance of programs running on FPGAs. More specifically, we apply a subset of the code transformations to an OpenCL kernel and measure the execution time on a Intel® FPGA. We show that, without applying these transformations before execution, poor performance is observed and the devices are underutilized. / Mestre

A rápida evolução do hardware demanda uma evolução contínua dos compiladores. Um processo de ajuste deve ser realizado pelos projetistas de compiladores para garantir que o código gerado pelo compilador mantenha uma determinada qualidade, seja em termos de tempo de processamento ou outra característica pré-definida. Este trabalho visou automatizar o processo de ajuste de compiladores por meio de técnicas de aprendizado de máquina. Como resultado os planos de compilação obtidos usando aprendizado de máquina com as características propostas produziram código para programas cujos valores para os tempos de execução se aproximaram daqueles seguindo o plano padrão utilizado pela LLVM. / The fast evolution of hardware demands a continue evolution of the compilers. Compiler designers must perform a tuning process to ensure that the code generated by the compiler maintain a certain quality, both in terms of processing time or another preset feature. This work aims to automate compiler adjustment process through machine learning techniques. As a result the compiler plans obtained using machine learning with the proposed features had produced code for programs whose values for the execution times approached those following the standard plan used by LLVM.

A rápida evolução do hardware demanda uma evolução contínua dos compiladores. Um processo de ajuste deve ser realizado pelos projetistas de compiladores para garantir que o código gerado pelo compilador mantenha uma determinada qualidade, seja em termos de tempo de processamento ou outra característica pré-definida. Este trabalho visou automatizar o processo de ajuste de compiladores por meio de técnicas de aprendizado de máquina. Como resultado os planos de compilação obtidos usando aprendizado de máquina com as características propostas produziram código para programas cujos valores para os tempos de execução se aproximaram daqueles seguindo o plano padrão utilizado pela LLVM. / The fast evolution of hardware demands a continue evolution of the compilers. Compiler designers must perform a tuning process to ensure that the code generated by the compiler maintain a certain quality, both in terms of processing time or another preset feature. This work aims to automate compiler adjustment process through machine learning techniques. As a result the compiler plans obtained using machine learning with the proposed features had produced code for programs whose values for the execution times approached those following the standard plan used by LLVM.

This work presents a strategy for the coupled poro-elasto-plastic formulation. The Finite Element Method (FEM) is used to solve the differential equations, interpolating displacement and pore pressure fields. This problem is solved fully coupled, based on an only one system of equations. The nonlinear problem is globally solved by the Newton-Raphson procedure, and the Closest Point algorithm is implemented for the returning map in the elasto-plastic models. Based on a computational module that has already been developed (PORO), which is written using C++ language and Object-Oriented Programming (OOP), this work expands this program creating new classes for different elasto-plastic constitutive models. The program is verified by classical examples in the literature such as the poro-elastic column and the problem of Schiffman. Some strategies for optimization the computational cost are presented, which use specialized math libraries (MKL) and code parallelization (OpenMP). / Este trabalho apresenta, discute e implementa a formulação poro-elastoplástica fortemente acoplada. A discretização espacial das equações diferenciais governantes é realizada através do Método dos Elementos Finitos (MEF), com interpolação do campo de deslocamento e da poropressão. O problema poro-mecânico é resolvido de forma totalmente acoplada, com base em um único sistema de equações. O método iterativo de Newton-Rhapson é empregado para a solução global do problema não linear, tendo ainda o algoritmo implícito iterativo Closest Point para a integração local das equações da plasticidade. Baseando-se em um programa computacional pré-existente denominado PORO, escrito na linguagem C++ e que utiliza o paradigma de Programação Orientada a Objetos (POO), faz-se a adaptação desse código através da criação de novas classes para permitir o uso de modelos constitutivos elastoplásticos e lei de fluxo associada no acoplamento poro-mecânico. Para verificação do programa são analisados problemas clássicos da literatura, a exemplo da coluna poro-elástica e o caso de Schiffman. Descrevem-se ainda algumas estratégias de otimização do custo computacional, implementando-se o uso de bibliotecas matemáticas (MKL) e paralelização do código (OpenMP).