A transformação entre linguagens, ou entre diferentes formatos de uma mesma linguagem, é um assunto que desperta interesse há vários anos e desta forma alguns trabalhos tem surgido para tentar automatizar o processo de transformação entre notações diferentes. Este trabalho descreve as Gramáticas Transformacionais empregados para descrever as transformag6es necessárias para converter uma notação em uma linguagem fonte (LF) para uma notação equivalente em uma linguagem objeto (LO). Nesta Gramática é embutido o conceito de Gramáticas de Atributos, criando assim as Gramáticas Transformacionais com Atributos (GTAs). Para validação das GTAs é apresentado um protótipo de ferramenta transformacional, que gera um tradutor, de LF para LO, a partir da descrição da gramática da LF e das regras de transformações para a LO. Tanto a LF quanto a LO são gramáticas do tipo LALR(1). Como objetivo de construir a ferramenta mais genérica possível, foram realizados estudos sobre três ferramentas, com as quais as transformações são possíveis. São elas: YACC, SINLEX e GG. É feita uma breve descrição destas três ferramentas e uma comparação com o protótipo implementado. / Languages transformation or transformation among differents formats of the same language is a subject that , has had a lot of interest for t many years. Thus, research has been done aiming to automatize the proccess of transformation from one notation to another. This work describes the use of Transformation Grammars to describe the necessary transformations to convert from a Source Language (SL) notation to an equivalent Object Language (OL). The concept of Attribute Grammars is embbeded to these grammars, defining an Attributed Transformation Grammar (ATG). A transformation tool prototype to evaluate the ATGs is presented. This tool generates a translator from SL to OL using the SL grammar description and the corresponding transformation rules to the OL. Both the SL and OL are LALR(1) grammars. Studies on YACC, SINLEX and GG (tools wich allow transformations) were done trying to reach the most generic tool. A brief descriptions of these tools and a comparision with the prototype is presented.

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

La rapidité, la consommation énergétique et l'efficacité des systèmes logiciels et matériels sont devenues les préoccupations majeures de la communauté informatique de nos jours. Gérer de manière correcte et efficace les problématiques mémoire est essentiel pour le développement des programmes de grande tailles sur des architectures de plus en plus complexes. Dans ce contexte, cette thèse contribue aux domaines de l'analyse mémoire et de la compilation tant sur les aspects théoriques que sur les aspects pratiques et expérimentaux. Outre l'étude approfondie de l'état de l'art des analyses mémoire et des différentes limitations qu'elles montrent, notre contribution réside dans la conception et l'évaluation de nouvelles analyses qui remédient au manque de précision des techniques publiées et implémentées. Nous nous sommes principalement attachés à améliorer l'analyse de pointeurs appartenant à une même structure de données, afin de lever une des limitations majeures des compilateurs actuels. Nous développons nos analyses dans le cadre général de l'interprétation abstraite « non dense ». Ce choix est motivé par les aspects de correction et d'efficacité : deux critères requis pour une intégration facile dans un compilateur. La première analyse que nous concevons est basée sur l'analyse d'intervalles des variables entières ; elle utilise le fait que deux pointeurs définis à l'aide d'un même pointeur de base n'aliasent pas si les valeurs possibles des décalages sont disjointes. La seconde analyse que nous développons est inspirée du domaine abstrait des Pentagones ; elle génère des relations d'ordre strict entre des paires de pointeurs comparables. Enfin, nous combinons et enrichissons les deux analyses précédentes dans un cadre plus général. Ces analyses ont été implémentées dans le compilateur LLVM. Nous expérimentons et évaluons leurs performances, et les comparons aux implémentations disponibles selon deux métriques : le nombre de paires de pointeurs pour lesquelles nous inférons le non-aliasing et les optimisations rendues possibles par nos analyses / This thesis was motivated by the emergence of massively parallel processing and supercomputingthat tend to make computer programming extremely performing. Speedup, the power consump-tion, and the efficiency of both software and hardware are nowadays the main concerns of theinformation systems community. Handling memory in a correct and efficient way is a step towardless complex and more performing programs and architectures. This thesis falls into this contextand contributes to memory analysis and compilation fields in both theoretical and experimentalaspects.Besides the deep study of the current state-of-the-art of memory analyses and their limitations,our theoretical results stand in designing new algorithms to recover part of the imprecisionthat published techniques still show. Among the present limitations, we focus our research onthe pointer arithmetic to disambiguate pointers within the same data structure. We develop ouranalyses in the abstract interpretation framework. The key idea behind this choice is correctness,and scalability: two requisite criteria for analyses to be embedded to the compiler construction.The first alias analysis we design is based on the range lattice of integer variables. Given a pair ofpointers defined from a common base pointer, they are disjoint if their offsets cannot have valuesthat intersect at runtime. The second pointer analysis we develop is inspired from the Pentagonabstract domain. We conclude that two pointers do not alias whenever we are able to build astrict relation between them, valid at program points where the two variables are simultaneouslyalive. In a third algorithm we design, we combine both the first and second analysis, and enhancethem with a coarse grained but efficient analysis to deal with non related pointers.We implement these analyses on top of the LLVM compiler. We experiment and evaluate theirperformance based on two metrics: the number of disambiguated pairs of pointers compared tocommon analyses of the compiler, and the optimizations further enabled thanks to the extraprecision they introduce

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.

Made available in DSpace on 2014-06-12T15:58:08Z (GMT). No. of bitstreams: 2 arquivo3259_1.pdf: 5762420 bytes, checksum: 0af73887e3af768529c1569155447ba5 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / FUNDAÇÃO DE APOIO AO DESENVOLVIMENTO DA UFPE / Linhas de Produtos de Software (LPS) são definidas como conjuntos de sistemas de software que atendem a um mercado especifico, que compartilham caracteristicas em comum, porem sendo suficientemente distintos entre si, e que são desenvolvidos a partir de um conjunto de artefatos reusaveis. Entre os beneficios possiveis com a implantação de LPS podemos citar o reuso em larga escala e o aumento de produtividade. Um fator-chave no desenvolvimento de uma LPS e o mecanismo utilizado para a estruturação fonte. Uma das tecnicas mais comumente utilizadas para a estruturação de variações de código e a compilação condicional, tambem chamada de pre-processamento. Apesar de ser amplamente utilizada, o uso de compilação condicional incorre em problemas de legibilidade, modularidade, manutenibilidade e qualidade. Programação Orientada a Aspectos (POA) e uma alternativa a compilação condicional para a estruturação de variações de codigo em LPS, podendo apresentar melhor legibilidade, modularidade, manutenibilidade, qualidade, entre outros fatores, do que a compilação condicional. Entretanto, o uso de AspectJ, implementação mais popular de POA sobre a linguagem Java, como mecanismo de estruturação de variações gera um overhead (aumento) sobre o tamanho final do codigo compilado. No contexto de LPS de sistemas para plataformas em dispositivos moveis, em plataformas como Java ME, que possuem restrições de memoria, esse overhead pode tornar inviavel o uso do produto final. Neste trabalho, analisamos o impacto do uso de AspectJ como mecanismo de estruturação de variações sobre o tamanho do codigo compilado e investigamos os motivos por tras deste aumento. Para tal, utilizamos o BestLap e o Juggling, duas LPS de jogos para dispositivos Java ME que possuem uma versão puramente pre-processada e uma versão hibrida, que utiliza pre-processamento e AspectJ. Utilizamos o BestLap na analise de tamanho para quanticar o overhead com dois compiladores AspectJ, o ajc e o abc. Em seguida, analisamos o codigo compilado de um subconjunto das construções As pectJ, a fim de identificar quais construções geram overhead no tamanho do codigo compilado e os motivos por tras deste overhead. Esse subconjunto consistiu de todas as construções AspectJ utilizadas na versão híbrida do BestLap e do Juggling, o ultimo utilizado apenas para a elicitação das construções analisadas. Com base nessa investigação, desenvolvemos quatro otimizações para o compilador abc que modificam o codigo compilado de certas construções visando a eliminar o overhead. Apresentamos detalhes da implementação e discutimos as pre-condições e a corretude das otimizações desenvolvidas. Em seguida, apresentamos o resultado da aplicação destas otimizações em duas LPS e discutimos como implementações diferentes, porem equivalentes, da mesma variação em AspectJ podem inviabilizar a aplicação das otimizações Por fim, para garantir que as modificações realizadas pelas otimizações não prejudiquem o desempenho, apresentamos o resultado de testes de desempenho realizados em programas AspectJ usados em benchmarks apos a aplicação das nossas otimizações

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: Marco Aurelio Amaral Henriques / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T23:04:47Z (GMT). No. of bitstreams: 1 Herai_RobertoHirochi_M.pdf: 4053882 bytes, checksum: c48bdb80fdf9c0bbdb2249a62b3a2345 (MD5) Previous issue date: 2005 / Resumo: A predição de desempenho é um importante mecanismo para avaliar a utilização de recursos e estimar o tempo de execução de aplicações em sistemas paralelos. Este trabalho apresenta uma ferramenta que permite criar modelos que representam características da aplicação e dos computadores utilizados para processá-la. Tais modelos são combinados para gerar um modelo de desempenho mais abrangente, cuja análise permite obter estimativas de tempo de execução que contemplem fatores de atraso tais como operações aritméticas sobre diferentes tipos de dados e efeitos de contenção, causados por concorrência. As estimativas podem ser geradas em poucos segundos e permitem analisar o impacto causado na aplicação pela utilização de diferentes configurações do sistema de processamento paralelo. A ferramenta foi implementada para um sistema de processamento paralelo baseado em Java, chamado JoiN, e ela mostrou ser possível obter estimativas satisfatórias de tempos de execução para diversos tipos de aplicações paralelas / Abstract: Performance prediction is an important mechanism to evaluate the use of resources and predict the execution time of applications in parallel systems. This work presents a tool for the creation of models that represent applications and computers characteristics. Such models are combined to generate a performance model, whose analysis derives execution time estimates that include delay factors, such as arithmetic operations on different data types and contention effects caused by process concurrence. The estimates can be generated in a few seconds and allow the analysis of the impact caused in the application by changes in the parallel system configuration. The tool was implemented for a Java based parallel processing system called JoiN and it showed that satisfactory execution time estimates can be obtained for several types of parallel applications / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

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