Made available in DSpace on 2016-06-02T19:06:23Z (GMT). No. of bitstreams: 1 6777.pdf: 1533148 bytes, checksum: 25830198cf2d72379370c2466a0688cc (MD5) Previous issue date: 2015-02-04 / The physical limitations of silicon forced the industry to develop solutions that exploit the processing power of combining several general purpose processors. Even complex supercomputers that have multiple processors, they are still considered to inefficient processes that require large amounts of arithmetic operations using floating point data. Reconfigurable computing is gaining more space to have a performance close to a specific purpose devices (ASIC), and yet keep the flexibility provided by the architecture of general purpose processors. However, the complexity of hardware description languages often becomes a problem to the development of new projects. Tools for high-level synthesis have become more popular, they allow the transformation code in high-level hardware simply and quickly. However, solutions found in current tools generate simple hardware that does not exploit the techniques to improve the pipeline in hardware. This paper presents the development of techniques to exploit processing parallelism of the reconfigurable devices through programs described in language C. These techniques identify loops and improve the performance in hardware. As a result, we have improved in the high-level synthesis process generating optimized hardware. / A limitação física do silício forçou a indústria a desenvolver soluções que explorassem o poder de processamento de combinação de vários processadores de propósito geral. Mesmo os supercomputadores complexos que dispõem de vários processadores, eles ainda são considerados ineficientes para processamentos que exigem grandes quantidades de operações aritméticas utilizando dados em ponto flutuante. A computação reconfigurável vem ganhando cada vez mais espaço por ter um desempenho próximo aos dispositivos de propósito específico (ASIC), e ainda assim, manter a flexibilidade proporcionada pela arquitetura dos processadores de propósito geral. Entretanto, a complexidade das linguagens de descrição de hardware se torna muitas vezes uma barreira para o desenvolvimento de novos projetos. Ferramentas de síntese de alto nível vem se popularizando, elas permitem a transformação de códigos em alto nível em hardware de maneira simples e rápida. Entretanto, soluções encontradas nas ferramentas atuais, geram hardware simples que não exploram as técnicas que permitam melhorar o pipeline em hardware. Este trabalho apresenta o desenvolvimento de técnicas que permitem explorar o poder do paralelismo nos dispositivos reconfiguráveis por meio de programas descritos em uma linguagem C. Essas técnicas identificam laços de repetição e melhoram o desempenho em hardware. Como resultado, temos a melhora no processo de síntese de alto nível gerando hardware otimizado.

Este trabalho descreve técnicas de análise estática de compilação baseadas na álgebra e programação linear que buscam otimizar a distribuição de loops forall e array em programas escritos na linguagem S/SAL visando à execução em máquinas paralelas de memória distribuídas. Na fase de alinhamento, nós trabalhamos com o alinhamento de hiperplanos onde objetivo é tentar encontrar as porções dos diferentes arrays que necessitam ser distribuídas juntas. Na fase de divisão, que tenta quebrar em partes independente dados e computações, nós usamos duas funções afins, a função de decomposição de dados e a função de decomposição de computação. A última fase, o mapeamento, distribui os elementos de computação nos elementos de processamento usando um conjunto de inequações. As técnicas foram implementadas num compilador SISAL, mas pode ser usada sem mudanças em outras linguagens de associação simples e com a adição de análise de dependências pode ser usada em linguagens imperativas. / This work describes static compiler analysis techniques based on linear algebra and linear programming for optimizing the distribution of forall loops and of array elements in programs written in the SISAL programming language for distributed memory parallel machines. In the alignment phase, attempt is made in the identification of portions of different arrays that need to be distributed jointly by means of alignment of hyperplanes. In the partitioning phase, effort is made in breaking as even possible the computation and pertinent data in independent parts, by means of using related functions: the data decomposition function and the computation decomposition function. The last phase is dedicated to the mapping, which comprises the distribution of the elements of computation into the existing processing elements by means of a set of inequations. These techniques are being implemented in a SISAL compiler, but can be also used without changes by means of other single assignment languages or, with the addition of dependency analysis when using other set of languages, as well.

Com o crescente número de usuários de computadores, novas ferramentas têm sido apresentadas com a finalidade de aumentar a eficiência dos computadores, meio para que seus usuários disponham de recursos automatizados. Mais recentemente, máquinas ligadas em rede de computadores e o fenômeno Internet tornaram necessárias ferramentas específicas para este tipo particular de uso. Entre as principais respostas a essas necessidades surgiu a linguagem Java, que tem ganhado adeptos tanto na comunidade científica como no mercado. Surge daí a necessidade de buscar formas alternativas para o uso de computadores em rede. Entre as soluções propostas encontra-se a de arquiteturas e linguagens paralelas. Estas ferramentas, ainda em fase experimental, apresentam soluções que podem a médio e longo prazo serem viáveis, desde que estudos e pesquisas mostrem sua viabilidade. Neste trabalho investiga-se a aplicação do conceito de paralelismo em linguagens para rede, mais especificamente a linguagem Java. A proposta é estudar as possíveis formas para se explorar o paradigma de linguagens paralelas em ambientes Java. Para isto, apresenta-se uma pesquisa relativa as principais linguagens paralelas disponíveis na literatura, de forma a conhecer as melhores soluções apresentadas por essas linguagens. O trabalho apresenta também um estudo realizado em um conjunto de ferramentas Java disponíveis no mercado. Finalmente, propõe-se um novo ambiente que possa disponibilizar ao usuário os melhores recursos da linguagem Java, explorando as melhores soluções encontradas na literatura. / With the increasing number of computer users, new tools have been presented to improve the computers efficiency and to make automated resources available for those users. Nowadays, the use of computers in a network and the Internet phenomenon requires specific tools. Among them, the Java language appears as an important tool, which has been attracting users in both the scientific and commercial communities. At the same time the computer networks are becoming more popular and some problems have emergent concerned to the networks assessment and connections. It is necessary to look for alternative ways of handling the network computer systems. The parallel architectures and languages appear among the proposed solutions. These tools are still in an experimental phase, studies and researches being necessary additional to confirm their feasibility. In this work we investigate the application of parallelism concepts in languages for networks, and particular we deal with the Java language. The aim is to study the possible approaches for exploring the parallel languages paradigm in Java environments. Research about the main parallel languages available in the literature is presented, in order to check the best solutions proposed by those languages. The work also presents an investigation about the Java tools available in the commercial market. Finally a new environment is proposed that makes some of the best resources of language Java available to the users by exploring the best solutions found in the literature.

Considerando a crescente demanda por desempenho em sistemas computacionais, a implementação de algoritmos diretamente em hardware com o uso de FPGAs (Field-programmable Gate Arrays) é uma alternativa que tem apresentado bons resultados. Porém, os desafios de programação envolvidos no uso de FPGAs, de tal forma a explorar eficientemente seus recursos, limita o número de desenvolvedores em função da predominância do paradigma de programação tradicionalmente sequencial, imposto pelas linguagens imperativas. Assim, este trabalho busca desenvolver mecanismos que facilitem o desenvolvimento com FPGAs, otimizando o uso de memória e explorando o paralelismo das operações. Este documento apresenta a tese de doutorado de título LALP+ : um framework para o desenvolvimento de aceleradores de hardware em FPGAs. Dado que a latência para leitura e escrita de dados têm sido um gargalo para algumas aplicações de alto desempenho, este trabalho trata do desenvolvimento de técnicas para geração de arquiteturas de hardware, considerando aspectos relativos ao mapeamento, gerenciamento e acesso à memória em arquiteturas reconfiguráveis. Para isto, o projeto desenvolvido utiliza como base a linguagem LALP, cujo foco é o tratamento de loops com a técnica de loop pipelining. As técnicas descritas nesta tese são empregadas no desenvolvimento do framework LALP+, o qual estende LALP com a implementação de novas características e funcionalidades, de forma a contribuir para o aumento do seu nível de abstração. As arquiteturas criadas utilizando LALP+ foram comparadas às geradas por ferramentas comerciais e acadêmicas, tendo apresentado, em média, um melhor desempenho, com redução do tempo de execução de 10;01, no melhor caso. Espera-se, por meio das contribuições aqui apresentadas, facilitar a implementação de produtos e projetos relacionados a aplicações de computação de alto desempenho que envolvam o uso de arquiteturas reconfiguráveis, promovendo uma maior absorção desta tecnologia. / Considering the demand for high-performance in computer systems, the implementation of algorithms directly in hardware by using FPGAs (Field-programmable Gate Arrays) is an alternative that has shown good results. However, the number of developers is limited due to the challenges faced for efficiently programming FPGAs. In addition to that, developers are more used to the traditional sequential programming paradigm imposed by the imperative languages. This work seeks to develop mechanisms to facilitate the development with FPGAs, by optimizing memory usage and exploiting the parallelism of operations inside a loop. This document presents the doctoral thesis entitled LALP+ : a framework for developing FPGA-based hardware accelerators. Since the latency for reading and writing data have been a bottleneck for high performance applications, this work deals with the development of techniques for generation of hardware architectures, considering aspects related to mapping, management and memory access in reconfigurable architectures, using as basis the LALP language, which focuses on the treatment of loops with the technique of loop pipelining. The techniques described in this thesis are employed in the development of the LALP+ framework, which extends LALP by implementing new features and functionalities, in order to contribute to increase its abstraction level. LALP+ architectures were compared to ones generated by using academical and commercial tools, having presented, on average, better performance, with a execution time speedup of 10;01 for the best case. Thus, it is expected that the hereby presented contributions facilitate the implementation of products and projects related to high-performance computing applications with reconfigurable architectures, contributing for the use of such technology.

Orientador: Guido Costa Souza de Araújo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T08:05:03Z (GMT). No. of bitstreams: 1 Porto_JoaoPaulo_D.pdf: 1983380 bytes, checksum: edef40fbafe26ce2d849308b08daf786 (MD5) Previous issue date: 2011 / Resumo: É sabido que o modelo de desenvolvimento de micro-processadores baseado na extração de Instruction-Level Parallelism (ILP) de código sequencial atingiu seu limite. Encontrar soluções escaláveis e eficientes que permitam a manutenção de inúmeras instruções em execução simultaneamente tem se mostrado um desafio maior que o imaginado. Neste sentido, arquitetos e micro-arquitetos de computadores vêm buscando soluções alternativas para o desenvolvimento de novas arquiteturas. Dentre as soluções existentes, vêm ganhando força as baseadas na extração de Thread-Level Parallelism (TLP). Resumidamente, TLP é um tipo de paralelismo que tenta quebrar um programa sequencial em tarefas relativamente independentes entre si para executá-las em paralelo. TLP pode ser extraído por hardware ou software. Idealmente, uma solução híbrida deve ser utilizada, com o software realizando a identificação das oportunidades de extração de TLP, e com o hardware provendo suporte para execução do código gerado. Com tal solução de compromisso, o hardware fica livre da necessidade de especular, e o software pode trabalhar com maiores garantias. Nesta Tese, estudaram-se formas automáticas de paralelização e extração de TLP. Inicialmente, focou-se em traces dinâmicos de execução de programas sequenciais. Técnicas existentes (tais como MRET e Trace Trees) mostraram-se inapropriadas, de modo que desenvolveu-se uma nova técnica chamada Compact Trace Tree (CTT), que mostrou-se mais rápida que Trace Trees. Trace Tree (TT) também apresentam grande nível de especialização de código (tail duplication), característica ausente em MRET. Além de CTT, esta Tese apresenta Trace Execution Automata (TEA), um autômato que representa traces de execução. Esta representação revelou, em nossos experimentos, quase 80% de economia de espaço quando comparada com a representação usual. A seguir, o foco da Tese foi voltado para laços de execução e para paralelização estática de código sequencial através de Decoupled Software Pipeline (DSWP). Nosso primeiro resultado nesta direção, usando Java, mostrou claramente que sem nenhum suporte em hardware, a paralelização estática de programas poderia atingir um ganho de desempenho médio de 48% nas aplicações paralelizadas. Finalmente, a Tese propõe um modelo de execução paralelo baseado em DSWP que permite a consistência de dados entre as diversas threads de programas paralelizados. Apesar de não avaliar esta arquitetura completamente, os resultados iniciais são promissores. Além disso, o suporte necessário em hardware é simples e acomoda-se sobre o protocolo de coerência de cache existente, sem alterações sensíveis no processador / Abstract: The usual, Insturction-Level Parallelism (ILP)-oriented, microprocessor development model is known to have reached a hard-to-break limit. Finding scalable and efficient solutions that keep several instructions on-the-fly simultaneously has proven to be moredifficult than imagined. In this sense, computer architects and micro-architects have been seeking alternatives to develop new architectures. Among all, the TLP-based solutions are gaining strength. In short, TLP strives to break a sequential program into quasi-independent tasks in order to execute them in parallel. TLP can be extracted either by hardware or software. Ideally, a hybrid solution would be employed, with the software being responsible to identifying TLP opportunities, and the hardware offering support for the parallel code execution. With such solution, the hardware is free from the heavy speculation burden, whilst the software can be parallelized with more warranties. In this Thesis, automatic parallelization and TLP strategies were studied. The research first focused on dynamic execution traces. Existing techniques, such as MRET and Trace Trees proved unsuitable for our goals, which led us to develop a new trace identification technique called Compact Trace Trees, which showed to be faster than Trace Trees. Compact Trace Trees also present trace specialization, which MRET lacks. Besides Compact Trace Trees, this Thesis presents a new trace representation called Trace Execution Automata, an automaton representing the execution traces. This technique revealed nearly 80% memory size savings when compared to the usual, code duplication representation. Next, the Thesis' focus shifted to parallelizing loops statically. Our initial result in this direction, using Java and without any hardware support, clearly revealed that static parallelization of sequential programs could reach a 48% average speedup when compared to their sequential execution. Finally, a new, Decoupled Software Pipelining-based execution model with automatic data coherence amongst parallelized programs'threads is proposed by the Thesis. Despite the lack of a full model evaluation, the initial results are promising. Differently from other proposals, the hardware support necessary for this architecture is simple and builds upon the existing cache coherence protocol, without any modifications to this sensitive system component / Doutorado / Doutor em Ciência da Computação

Orientador: Rodolfo Jardim de Azevedo / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-05T13:01:34Z (GMT). No. of bitstreams: 1 BlasiJunior_Francisco_M.pdf: 934725 bytes, checksum: 6a13eaaaee52e0aabb1a74f3c2c4669f (MD5) Previous issue date: 2005 / Resumo: As otimizações implementadas em compiladores proporcionam uma melhora significativa de desempenho dos programas. Em muitos casos, proporcionam também a redução do tamanho do programa. Quase todos os programas em produção são compilados com diretivas de otimização, para obter máximo desempenho.Para o estudo de novas técnicas de otimização, faz-se necessário um ambiente de testes no qual essas técnicas possam ser incorporadas facilmente. O projeto Xingó foi desenvolvido com esse intuito. Gerando código C compilável, o Xingó proporciona facilmente a verificação do resultado das otimizações implementadas.Este trabalho mostra a implementa¸c¿ao de algumas otimizações em loops no projeto Xingó, demonstrando a viabilidade de novas otimizações serem incorporadas. Além disso, este trabalho analisa o resultado da utiliza¸c¿ao de ferramentas disponíveis no mercado que verificam a corretude de cada uma das otimizações e que avaliam o desempenho do sistema com as otimizações implementadas / Abstract: Software performance is signifcantly improved by the optimizations implemented on the compilers. In some cases, the compiler optimizations also reduces the size of the software.It is necessary to have a test environment in order to study the result of optimization technics. The Xingó project was developed with such a concept in mind. By generating C compilable code, Xingó allows easy visualization of the results of new optimization technics.This work shows the implementation of some loop optimizations on the Xingó project, demonstrating that it can incorporate new optimizations. Besides that, this work shows the results from the usage of available tools that checks each optimization correctness and also tools that analyses the performance of the system with the optimizations incorporated. / Mestrado / Engenharia de Computação / Mestre em Computação

Orientador: Guido Costa Souza Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T14:27:52Z (GMT). No. of bitstreams: 1 Oliveira_MarcioRodrigode_M.pdf: 1563381 bytes, checksum: 52e2e029998b3539a26f5c2b76284d88 (MD5) Previous issue date: 2005 / Resumo: Atualmente existe um grande mercado para o desenvolvimento de aplicações para sistemas embutidos, pois estes estão fazendo parte crescente do cotidiano das pessoas em produtos de eletrônica de consumo como telefones celulares, palmtop's, agendas eletrônicas, etc. Os produtos de eletrônica de consumo possuem grandes restrições de projeto, tais como custo reduzido, baixo consumo de potência e muitas vezes alto desempenho. Deste modo, o código produzido pelos compiladores para os programas executados nestes produtos, devem executar rapidamente, economizando energia de suas baterias. Estes melhoramentos são alcançados através de transformações no programa fonte chamadas de otimizações de código. A otimização preload de dados consiste em mover dados de um alto nível da hierarquia de memória para um baixo nível dessa hierarquia antes deste dado ser usado. Este é um método que pode reduzir a penalidade da latência de memória. Este trabalho mostra o desenvolvimento da otimização de preload de dados no compilador Xingo para a plataforma Pocket PC, cuja arquitetura possui um processador XScale. A arquitetura XScale possui a instrução preload, cujo objetivo é fazer uma pré-busca de dados para a cache. Esta otimização insere (através de previsões) a instrução preload no código intermediário do programa fonte, tentando prever quais dados serão usados e que darão miss na cache (trazendo-os para esta cache antes de seu uso). Com essa estratégia, tenta-se minimizar a porcentagem de misses na cache de dados, reduzindo o tempo gasto em acessos à memória. Foram usados neste trabalho vários programas de benchmarks conhecidos para a avaliação dos resultados, dentre eles destacam-se DSPstone e o MiBench. Os resultados mostram que esta otimização de preload de dados para o Pocket PC produz um aumento considerável de desempenho para a maioria dos programa testados, sendo que em vários programas observou-se uma melhora de desempenho maior que 30%! / Abstract: Nowadays, there is a big market for applications for embedded systems, in products as celIular phones, palmtops, electronic schedulers, etc. Consumer electronics are designed under stringent design constraints, like reduced cost, low power consumption and high performance. This way, the code produced by compiling programs to execute on these products, must execute quickly, and also should save power consumption. In order to achieve that, code optimizations must be performed at compile time. Data preload consists of moving data from a higher leveI of the memory hierarchy to a lower leveI before data is actualIy needed, thus reducing memory latency penalty. This dissertation shows how data preload optimization was implemented into the Xingo compiler for the Pocket PC platform, a XScale based processor. The XScale architecture has a preload instruction, whose main objective is to prefetch program data into cache. This optimization inserts (through heuristics) preload instructions into the program source code, in order to anticipate which data will be used. This strategy minimizes cache misses, allowing to reduce the cache miss latency while running the program code. Some benchmark programs have been used for evaluation, like DSPstone and MiBench. The results show a considerable performance improvement for almost alI tested programs, subject to the preload optimization. Many of the tested programs achieved performance improvements larger than 30% / Mestrado / Otimização de Codigo / Mestre em Ciência da Computação

Orientador: Guido Costa Souza de Araujo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T07:49:18Z (GMT). No. of bitstreams: 1 Attrot_Wesley_D.pdf: 1097052 bytes, checksum: 298445ea7d116f82e1c318d1a5dab324 (MD5) Previous issue date: 2008 / Resumo: Tradutores binários dinâmicos ou DBTs2, são programas projetados para executar, em uma arquitetura-alvo, programas binários de arquiteturas diferentes, realizando assim a tradução do programa binário em tempo de execução. Eles também podem ser utilizados para se melhorar o desempenho de programas nativos de uma dada arquitetura. DBTs podem coletar informação de profile da aplicação em tempo de execução, habilidade essa impossível para um compilador estático. Este tipo de informação pode ser usada pelos DBTs para realizar novos tipos de otimizações, não possíveis em um compilador estático, seja por falta de informação do comportamento do programa, ou por não conhecer que regiões do código são mais importantes para otimizar, em detrimento de outras. Como os DBTs gastam tempo para traduzir o código binário, é muito importante que os processos de tradução e otimização sejam extremamente rápidos, para que o impacto final no tempo total de execução seja o mínimo possível. Desta forma, para um tradutor binário dinâmico é essencial saber onde aplicar as otimizações, isto é, descobrir quais regiões do código traduzido são realmente importantes e que podem resultar em ganhos de desempenho. Uma vez que tais regiões tenham sido identificadas, os DBTs irão aplicar às mesmas, otimizações de código de forma a tentar compensar o tempo gasto na tradução do programa binário e mesmo melhorar o desempenho da aplicação traduzida. Como o acesso à memória é algo custoso para um programa, evitá-lo em um ambiente dinâmico pode fazer com que o programa traduzido obtenha ganhos de desempenho, compensando assim parte do tempo gasto no processo de tradução Com isso, neste trabalho investigou-se o ganho de desempenho que pode ser obtido em um ambiente de tradução dinâmica ao se tentar otimizar os acessos à memória que o programa traduzido realiza dentro das regiões de código selecionadas para otimização. O processo de otimiza¸c¿ao tenta, tanto quanto possível, evitar acessos à memória principal do computador, transformando-os em acessos à registradores da arquitetura alvo. Como grande parte das otimizações de código necessita de informações de fluxo de dados para poder realizar transformações de código, este trabalho também investigou uma nova forma de se melhorar as análises de fluxo de dados que s¿ao executadas em trechos limitados de código pelo tradutor binário dinâmico. Os resultados mostram que otimizar os acessos à memória produz ganhos pequenos, da ordem de 2%. No tocando a melhora da informa¸c¿ao de fluxo de dados, descobriu-se que quando se busca por registradores disponíveis, pode-se descobrir que quase 25% do total dos registradores investigados estão de fato vazios e podem ser utilizados em otimizações. / Abstract: Dynamic binary translators or DBTs, are programs designed to execute, in a target architecture, binary programs from different architectures, performing the translation of the binary program during the execution time. They can also be used to improve the performance of native programs for a specific architecture. DBTs can collect profile information from the application during runtime, this skill is impossible for a static compiler. This kind of information can be used by the DBTs to perform new kinds of optimizations, not possible in the static compiler, due to few information about the program's behavior, or does not know the regions of the code that are more important to optimize, in detriment of others. DBTs spend time translating the binary code, so is very important that the translation and the optimization process, both be as fast as possible, to the impact in the overall execution time, be the minimum possible. In this way, for a dynamic binary translator, is essential to know where to apply the optimizations, that is, find out what regions of the translated code are really important and that can generate performance improvements. When these regions are identified, the DBTs apply code optimizations in these regions to compensate the time spend to translate the binary program and even improve the performance of the translated aplication. Memory access is a expensive operation for programs, to avoid it in a dynamic environment may result in performance improvement in the translated program, compensating the time spend to translate the binary. In this work, we investigate the performance improvement that can be achieved in a dynamic translation environment when we optimize the memory access that the translated program performs inside the regions selected for optimization. The optimization process tries, when possible, to avoid access to the main computer memory, transforming them into registers access of the target architecture. Many code optimizations need data flow information to perform code transformations, in this work we also investigate a new way to improve the data flow analysis that are performed in constraint regions of code by the dynamic binary translator. The results show that optimize the memory access produce small gains, about 2%. When we try to improve the data flow information, we have discovered that when we are looking for available registers, we can find that almost 25% of the investigated registers are empty and can be used for optimizations. / Doutorado / Sistemas de Computação / Doutor em Ciência da Computação

Orientadores: Guido Costa Souza de Araújo, Edson Borin / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T12:28:12Z (GMT). No. of bitstreams: 1 Lucas_DivinoCesarSoares_M.pdf: 1053361 bytes, checksum: e29ab79838532619ba298ddde8ba0f39 (MD5) Previous issue date: 2013 / Resumo: Máquinas virtuais (MVs) são sistemas que se propõem a eliminar a incompatibilidade entre duas, em geral diferentes, interfaces e dessa forma habilitar a comunicação entre diferentes sistemas. Nesse sentido, atuando como mediadores, uma MV está em um ponto que a permite fomentar o desenvolvimento de soluções inovadoras para vários problemas. Tais sistemas geralmente utilizam técnicas de emulação, por exemplo, interpretação ou tradução dinâmica de binários, para executar o código da aplicação cliente. Para determinar qual técnica de emulação é a ideal para um trecho de código geralmente é necessário que a MV empregue algum tipo de predição para determinar se o benefício de compilar o código supera os custos. Este problema, na maioria dos casos, resume-se a predizer se o dado trecho de código será frequentemente executado ou não, problema conhecido pelo nome de Predição de Código Quente. Em geral, se o preditor sinalizar um trecho de código como quente, a MV imediatamente toma a decisão de compilá-lo. Contudo, um problema surge nesta estratégia, à resposta do preditor é apenas a decisão de uma heurística e é, portanto, suscetível a erros. Quando o preditor sinaliza como quente um trecho de código que não será frequentemente executado, ou seja, um código que de fato é "frio", ele está fazendo uma predição errônea de código quente. Quando uma predição incorreta é feita, ocorre que a técnica de emulação que a MV utilizará para emular o trecho de código não compensará o seu custo e, portanto a MV gastará mais tempo executando o seu próprio código do que o código da aplicação cliente. Neste trabalho, foi avaliado o impacto de predições incorretas de código quente no desempenho de MVs emulando vários tipos de aplicações. Na análise realizada foi avaliado o preditor de código quente baseado em limiar, uma técnica frequentemente utilizada para identificar regiões de código que serão frequentemente executadas. Para fazer esta análise foi criado um modelo matemático para simular o comportamento de tal preditor e a partir deste modelo uma série de resultados puderam ser explorados. Inicialmente é mostrado que este preditor frequentemente erra a predição e, como conseqüência, o tempo gasto fazendo compilações torna-se o maior componente do tempo de execução da MV. Também é mostrado como diferentes limiares de predição afetam o número de predições incorretas e qual o impacto disto no desempenho da MV. Também são apresentados resultados indicando qual o impacto do custo de compilação, tradução e velocidade do código traduzido no desempenho da MV. Por fim é mostrado que utilizando apenas o conjunto de aplicações do SPEC CPU 2006 para avaliar o desempenho de MVs que utilizam o preditor de código quente baseado em limiar pode levar a resultados imprecisos / Abstract: Virtual machines are systems that aim to eliminate the compatibility gap between two, possible distinct, interfaces, thus enabling them to communicate. This way, acting like a mediator, the VM lies at an important position that enables it to foster innovative solutions for many problems. Such systems usually rely on emulation techniques, such as interpretation and dynamic binary translation, to execute guest application code. In order to select the best emulation technique for each code segment, the VM typically needs to predict whether the cost of compiling the code overcome its future execution time. This problem, in the common case, reduce to predicting if the given code region will be frequently executed or not, a problem called Hot Code Prediction. Generally, if the predictor flags a given code region as hot the VM instantly takes the decision to compile it. However, a problem came out from this strategy, the predictor response is only a decision made by means of a heuristic and thus it can be incorrect. Whenever the predictor flags a code region that will be infrequently executed (cold code) as hot code, we say that it is doing a hotness misprediction. Whenever a misprediction happens it means that the technique the VM will use to emulate the code will not have its cost amortized by executing the optimized code and thus the VM will, in fact, spend more time executing its own code rather than the guest application code. In this work we measure the impact of hotness mispredictions in a VM emulating several kinds of applications. In our analysis we evaluate the threshold-based hot code predictor, a technique commonly used to predict hot code fragments. To do so we developed a mathematical model to simulate the behavior of such predictor and we use it to estimate the impact of mispredictions in several benchmarks. We show that this predictor frequently mispredicts the code hotness and as a result the VM emulation performance becomes dominated by miscompilations. Moreover, we show how the threshold choice can affect the number of mispredictions and how this impacts the VM performance. We also show how the compilation, interpretation and steady state execution cost of translated instructions affect the VM performance. At the end we show that using SPEC CPU 2006 benchmarks to measure the performance of a VM using the threshold-based predictor can lead to misleading results / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Paulo Cesar Centoducatte, Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T08:52:36Z (GMT). No. of bitstreams: 1 Felicio_CristianoLino_M.pdf: 971885 bytes, checksum: 8ba5bf45f0d0284fcc7671ce0be406f7 (MD5) Previous issue date: 2005 / Resumo: Devido ao aumento da complexidade dos novos processadores, especialmente processadores DSPs, a capacidade dos compiladores de gerar um código altamente otimizado para as novas arquiteturas de computadores é cada vez mais desafiador. O compilador Xingó tem como objetivos possibilitar pesquisas em otimização e geração de código para novas arquiteturas. Para permitir tais pesquisas, é necessário que o compilador possua uma infra-estrutura capaz de representar, de uma maneira simples e correta, o código nas diversas fases de compilação. Este trabalho apresenta as principais representações de programa do compilador Xingó, bem como os módulos que fazem a tradução de um programa, em uma representação origem, para um programa em uma representação destino (intermediária ou final). Estes móulos compõem o front-end do compilador, que leva à Representação Intermediária Xingó, e parte do back-end, com destaque para a Infra-Estrutura de Geração de Código do Xingó. A Representação Intermediária do Xingó é de fácil manipulação, independente de máquina e apresenta uma sintaxe muito próxima à da linguagem C, por isso tem permitido otimizações independente de máaquina e pode ser traduzida em código C compilável. Já a Infra-Estrutura de Geração de Código apresenta facilidades no desenvolvimento de novos geradores de código, principalmente porque os detalhes da máquina alvo são externos ao compilador, sendo incluídos através de parâmetros configuráeis e módulos bem definidos. Os testes realizados até o presente momento validam parte da Infra-Estrutura de Geração de Código e têm demonstrado uma boa qualidade do Código Intermediário Xingó. Os testes mostram que o Código Intermediário estão sendo corretamente representado para todos os programas do benchmark NullStone (6611 programas) e para uma quantidade razoável de programas dos benchmarks MediaBench e SPEC. Os resultados alcançados até o momento trazem novas oportunidades em pesquisas na área de compiladores, especialmente otimização e geração de código / Abstract: Due to the increasing complexity of the new processors, mainly DSPs processors, the capacity of generating highly optimized code for the new computer architectures by the compilers is increasingly motivating. The Xingó compiler has as goal allow research in code optimization and code generation for new architectures. In order to enable such researches, is necessary to the compiler to provide an infrastructure capable of representing, in an easy and correct form, the code in the several compiling phases. This work presents the main program representations of the Xingó compiler, and the modules that perform the conversion of a program, in a base representation, to a program in a destination representation (intermediate or ultimate). These modules constitute the front-end of the compiler, that generates the Xingó Intermediate Representation, and share of the back-end, with highlight to the Xingó Code Generation Infrastructure. The Xingó Intermediate Representation is easy to use, it is machine independent and has a very approximate syntax of the C language, thereby it has enabled to perform machine independent optimizations and is able to be converted to C Code. Upon the Code Generation Infrastructure, it provides facilities to development of new code generators, mainly because the details of the target machine are outside to the compiler, been included across configurable parameters and well-defined modules.The tests completed up to now validate piece of the Code Generation Infrastructure and reveal good quality of the Xingó Intermediate Code. The testes show that the Intermediate Code is been correctly generated to any programs of the NullStone benchmark (6611 programs) and also to a reasonable quantity of programs of the MediaBench and SPEC benchmarks. The test results acquired up to now conduce to new opportunities for researches on areas such as optimization and code generation / Mestrado / Ciência da Computação / Mestre em Ciência da Computação