Dissertação (mestrado) - Universidade Federal do Rio de Janeiro. Coordenação dos Programas de Pos-Graduação em Engenharia / Made available in DSpace on 2012-10-15T22:14:42Z (GMT). No. of bitstreams: 0

Orientador : Guido Costa Souza de Araujo, Paulo Cesar Centoducatte / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-31T15:05:26Z (GMT). No. of bitstreams: 1 Buss_MarciodeOliveira_M.pdf: 6143829 bytes, checksum: 232f545e77eff7126860d60f0be8372a (MD5) Previous issue date: 2001 / Resumo: A incansável busca por máquinas mais velozes, aliada aos enormes avanços tecnológicos na concepção de circuitos integrados, retiraram as arquiteturas Very Long Instruction W ord (VLIW) de um estado amórfico para a realidade. Embora tenham surgido como CIs recentemente [1], as máquinas VLIW foram idealizadas há algumas décadas atrás [13, 16, 22, 23]. Os processadores que definem este modelo de processamento não mais obedecem regras clássicas de execução: instruções de um dos possíveis fluxos de controle de um comando de desvio condicional são executadas mesmo antes do término da avaliação da condição, a qual determinará se a transferência de controle deverá ocorrer ou não; executam simultaneamente inúmeras instruções, de diferentes tipos, oriundas do mesmo programa; computam programas que foram compilados de uma forma revolucionária: todo o programa é analisado em busca de operações paralelizáveis, como se fosse um único (macro) bloco. Numa tentativa de contribuição a esta linha de pesquisa, este trabalho visa a detecção e exploração do paralelismo 'escondido' em programas originalmente sequenciais. Esta busca gera resultados que são analisados e quantificados com o intuito de se encontrar uma arquitetura-alvo adequada para uma aplicação específica. Esta metodologia encontra-se inserida no contexto de uma área denominada Embedded Systems, a qual se preocupa em otimizar ao máximo a execução de uma classe restrita de aplicações ou até mesmo uma única aplicação-chave de um sistema dedicado. O modelo de arquitetura considerado neste trabalho é denominado VLIW particionado (do inglês partitioned VLIW). Este modelo difere da máquina VLIW ideal pelo fato de não possuir um único banco de registradores centralizado, mas sim vários bancos de registradores que se comunicam através de barramentos especiais. Com este modelo de arquitetura em mãos, o trabalho desenvolvido nesta dissertação trata da investigação de problemas relacionados com o mapeamento de uma aplicação específica a uma máquina VLIW dedicada. Em um macro-cenário, este trabalho tenta responder a seguinte questão: "Qual é a máquina VLIW adequada para uma dada aplicação ?,'. Ou ainda, "Quantos bancos de registradores e quantas unidades funcionais o processador para esta aplicação deveria ter?" / Abstract: The untiring search for faster machines, alIied to the great technological advances in the field of integrated circuits conception, brought out the Very Long Instruction Word architectures from an amorphous status to reality. Although they have appeared recently as real chips [1], the VLIW machines were idealized some decades ago [13, 16, 22, 23]. The microprocessors that define this processing model no longer obey classical rules of execution: instructions coming from one of the possible control flows resulted of a branch instruction are executed even before the finish of the evaluation condition. This evaluation condition will determine if the control transfer should occur or noto Also, these architectures execute simultaneously many instructions, of different kinds, issued from the same programo Moreover, these processors compute programs that were compiled through a revolutionary way: alI the program is analized to search for paralelizable operations. As an attempt to contribute to this research field, this work aim the development of a methodology to detect and exploit the paralelism "hided" in sequential-written programs. The results generated by this search are analized and quantified in order to find a targetarchitecture for a specific application. This work is inserted in the context of an area calIed Embedded Systems. This research field worry about the maximum optimization of an application class or even only one key-application of a embedded system. The architecture model considered in this work is denoted as "Partitioned VLIW Architecture". This model is slightly different of the ideal VLIW architecture model. In the ideal model, there must be only one centralized register file, in order to guarantee the maximum Instruction Levei ParalIelism (ILP). AlI the functional units share the same register file. On the other hand, the architecture model being considered here presents many distributed register files, which have an special bus to communicate data among them. With this architecture model in mind, the work developed in this thesis investigates some of the problems related to mapping one specific application to an embedded VLIW architecture. Roughly speaking, this work tries to answer the following question: "What is the ideal VLIW architecture for a given application'1" or "How many register files and how many functional units the processor for that application should have '1" / Mestrado / Mestre em Ciência da Computação

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-24T04:28:13Z (GMT). No. of bitstreams: 1 263131.pdf: 756956 bytes, checksum: 840e0f33f9d99e70d7bddaadf6eaffa6 (MD5)

Orientador: Tomasz Kowaltowski / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T03:22:30Z (GMT). No. of bitstreams: 1 Costa_ClevanRicardoda_M.pdf: 1291094 bytes, checksum: 09ecb271fba38a234b38746d0b88988d (MD5) Previous issue date: 1995 / Resumo: Este trabalho consiste na introdução de uma fase de otimização no compilador para a linguagem LL. O eu principal objetivo é a inferência de tipos, realizada através de uma análise de fluxo de dados. São apresentados diversos métodos para inferência de tipos em linguagens orientadas a objetos, bem como uma revisão sobre análise de fluxo de dados. O método de Kaplan e Ullman éapresentado com mais detalhes, juntamente com sua adaptação para LL , sua implementação e junção ao compilador desenvolvido para a linguagem. Finalmente são apresentadas as conclusões, os resultados obtidos e as propostas de extensões futuras para o trabalho. / Abstract: We describe in this thesis an optirnization phase for a compiler for the language LL. Its main goal is type inference achieved through data fiow analysis. Several methods for type inference in object-oriented languages are described, including a description of data fiow analysis. The Kaplan and Ullman method is described in more detail. Its adaptation to . LL and the implementation within an existing compiler are also described. We present also some final conclusions, including examples and possible extensions. / Mestrado / Mestre em Ciência da Computação

Orientador: Rogerio Drummond / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-14T12:25:20Z (GMT). No. of bitstreams: 1 Carneiro_LuizCarlosDurso_M.pdf: 1312947 bytes, checksum: acb50ddd9e5a376a4ae9e62164ad20dd (MD5) Previous issue date: 1989 / Resumo: É objetivo deste trabalho a apresentação do estudo da viabilidade de implementação de compiladores para linguagens de comando de alto nível. As linguagens de comando têm se mostrado poderosas ferramentas de desenvolvimento nos ambientes de programação modernos, deixando para trás o conceito antigo de que serviam apenas para alocação de periféricos e execução de programas. Este estudo foi iniciado com o intuito de aumentar o potencial destas linguagens, tornando-as mais rápidas. Este trabalho está orga.nizado em 4 capítulos, onde são expostos vários aspectos do estudo das linguagens de comando e da implementação de um compilador protótipo. No capítulo 1 é feita uma introdução às linguagens de comando, abordando tópicos que vão desde a sua origem até as modernas linguagens de comando de alto nível. o capítulo 2 se constitui da apresentação da linguagem de comando escolhida como protótipo para implementação: a C-SHELL do sistema UNIX. Já o capítulo 3 contém informações mais específicas sobre a implementação. Serão mostradas de modo distinto as partes da C-SHELL que foram implementadas utilizando recursos presentes no sistema UNIX e as partes independentes de sistema operacional. Estas discussões serão apresentadas a nível de algoritmos utilizados e quando for necessário, por questões de clareza, serão apresentados detalhes do código gerado. Finalizando, o capítulo 4 é formado pela conclusão deste trabalho. Neste capítulo são discutidas as vantagens da compilação das linguagens de comando de alto nível. Serão apresentados algumas comparações com as linguagens de comando disponíveis no nosso ambiente de programação UNIX e os novos passos a serem tomados nesta linha de estudo. Nos apêndices poderão ser encontradas demonstrações de uso da linguagem, detalhes da composição dos diversos módulos do sistema e orientações para a instalação do compilador em outros sistemas UNIX e UNIX-LIKE. / Abstract: Not informed. / Mestrado / Mestre em Ciência da Computação

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-10-24T12:49:20Z (GMT). No. of bitstreams: 1 Ottoni_GuilhermedeLima_M.pdf: 2467303 bytes, checksum: 3894457788c8896fac76459cfbda00e4 (MD5) Previous issue date: 2002 / Resumo: O avanço tecnológico dos sistemas computacionais tem proporcionado o crescimento do mercado de sistemas dedicados, cada vez mais comuns no dia-a-dia das pessoas, como por exemplo em telefones celulares, palmtops e sistemas de controle automotivo. Devido às suas características, estas novas aplicações requerem sistemas que aliem baixo custo, alto desempenho e baixo consumo de potência. Uma das maneiras de atender a estes requisitos é utilizando processadores especializados. Contudo, a especialização na arquitetura dos processadores impõe novos desafios para o desenvolvimento de software para estes sistemas. Em especial, os compiladores - geralmente responsáveis pela otimização de código - precisam ser adaptados para produzir código eficiente para estes novos processadores. Na área de processamento de sinais digitais, como em telefonia celular, processadores especializados, denominados DSPs2, são amplamente utilizados. Estes processadores tipicamente possuem poucos registradores de propósito geral e modos de endereçamento bastante limitados. Além disso, muitas das suas aplicações envolvem o processamento de grandes seqüências de dados, as quais são geralmente armazenadas em vetores. Como resultado, o estudo de técnicas de otimização de referências a vetores tornou-se um problema central em compilação para DSPs. Este problema, denominado Global Array Reference Allocation (GARA), é o objeto central desta dissertação. O sub-problema central de GARA consiste em se determinar, para um dado conjunto de referências a vetores que serão alocadas a um mesmo registrador de endereçamento, o menor custo das instruções que são necessárias para manter este registrador com o endereço adequado em cada ponto do programa. Nesta dissertação, este sub-problema é modelado como um problema em grafos, e provado ser NP-difícil. Além disso, é proposto um algoritmo eficiente, baseado em programação dinâmica, para resolver este sub-problema de forma exata sob certas restrições. Com base neste algoritmo, duas técnicas são propostas para resolver o problema de GARA. Resultados experimentais, obtidos pela implementação destas técnicas no compilador GCC, comparam-nas com outros resultados da literatura. Os resultados demonstram a eficácia das técnicas propostas nesta dissertação / Abstract: The technological advances in computing systems have stimulated the growth of the embedded systems market, which is continuously becoming more ordinary in people's lives, for example in mobile phones, palmtops and automotive control systems. Because of their characteristics, these new applications demand the combination of low cost, high performance and low power consumption. One way to meet these constraints is through the design of specialized processors. However, processor specialization imposes new challenges to the development of software for these systems. In particular, compilers - generally responsible for code optimization - need to be adapted in order to produce efficient code for these new processors. In the digital signal processing arena, such as in cellular telephones, specialized processors, known as DSPs (Digital Signal Processors), are largely used. DSPs typically have few general purpose registers and very restricted addressing modes. In addition, many DSP applications include large data streams processing, which are usually stored in arrays. As a result, studing array reference optimization techniques became an important task in compiling for DSPs. This work studies this problem, known as Global Array Reference Allocation (GARA). The central GARA subproblem consists of determining, for a given set of array references to be allocated to the same address register, the minimum cost of the instructions required to keep this register with the correct address at alI program points. In this work, this subproblem is modeled as a graph theoretical problem and proved to be NP-hard. In addition, an efficient algorithm, based on dynamic programming, is proposed to optimally solve this subproblem under some restrictions. Based on this algorithm, two techniques to solve GARA are proposed. Experimental results, from the implementation of these techniques in the GCC compiler, compare them with previous work in the literature. The results show the effectiveness of the techniques proposed in this work / Mestrado / Mestre em Ciência da Computação

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-10-24T12:45:09Z (GMT). No. of bitstreams: 1 Ottoni_DesireeLeopoldodaSilva_M.pdf: 1826554 bytes, checksum: 11256685b6244447ac6c729e9b8394ba (MD5) Previous issue date: 2004 / Resumo: Nos últimos anos, uma classe importante de aplicações em telecomunicações e multimídia tem despertado um grande interesse no projeto e pesquisa de processadores dedicados, em particular de DSPs2. Além de desempenho, estas aplicações demandam baixo consumo de potência e custo reduzido. Com o propósito de atender a esta demanda, projetistas de DSPs precisam especializar suas arquiteturas com unidades funcionais dedicadas. Devido a rigorosas restrições de projeto, é comum encontrar DSPs com poucos registradores de propósito geral e modos de endereçamento restritos, baseados em unidades especializadas no cálculo de endereços de memória. Por serem arquiteturas irregulares, as otimizações de código existentes nos compiladores para processadores de propósito geral não são eficientes para DSPs. Isto resultou em um aumento no interesse por pesquisa de técnicas de otimizações para estes processadores. Esta dissertação propõe duas novas técnicas de otimização de código para o problema de Offset Assignment(OA). Uma solução para OA visa encontrar uma disposição das variáveis automáticas de um programa na memória, de forma a minimizar o uso de instruções explícitas de endereçamento, obtendo assim um código de melhor desempenho. Este tipo de otimização é um dos problemas centrais de compilação para DSPs, dado que grande parte das instruções geradas para estes processadores é de endereçamento. Uma extensa revisão bibliográfica sobre Offset Assignment é apresentada nesta dissertação. Além disso, são propostos dois novos algoritmos que resolvem variações deste problema: a heurística CSOA, que resolve o problema de Simple Offset Assignment, e a heurística CGOA, que resolve o problema de General Offset Assignment. As duas heurísticas utilizam informações de longevidade das variáveis de modo a realizar união seletiva de variáveis na memória, resultando em uma melhor utilização de modos de endereçamento de auto-incrementojdecremento. Além das duas técnicas propostas, foram implementadas outras quatro técnicas existentes na literatura. Uma análise comparativa, baseada num conjunto de experimentos usando o benchmark Mediabench, revelou a superioridade de CSOA e CGOA sobre os outros métodos / Abstract: In recent years, an important class of applications in telecommunication and multimedia has created a large interest in the design and research of dedicated processors, specially Digital Signal Processors (DSPs). In addition to performance, these applications demand low power consumption and reduced cost. In order to achieve these goals, DSP designers need to specialize the architecture with dedicated functional units. Due to their stringent design constraints, it is common to find DSPs containing very few general-purpose registers, and restricted addressing modes, typically based on specialized address generation units. Given their irregular architectures, compiler code optimization techniques for general-purpose processors are not efficient for DSPs. This has resulted in an increasing interest in the research of optimization techniques target to such processors. This dissertation proposes two novel code optimization techniques for the Offset Assignment (OA) problem. A solution to OA aims at finding a memory layout for automatic variables in a program, such that the use of explicit memory addressing instructions is minimized, thus increasing the performance of the resulting code. This type of optimization is one of the central problems in compilation for DSPs, as address computation accounts for a large share of the instructions generated for these processors. A long survey on OA is presented in this dissertation. Moreover, two new algorithms to solve variations of OA are proposed: the CSOA heuristic, to solve the Simple Offset Assignment problem; and the CGOA heuristic, which solves the General Offset Assignment. Both techniques use liveness information to perform selective coalescing of variables in memory, resulting in an improved use of auto-increment/decrement addressing modes. In addition to the two proposed algorithms, four other techniques from the literature have been implemented. A comparative analysis, based on a set of experiments using the Media Bench benchmark, has revealed the superiority of CSOA and CGOA with respect to the other methods / Mestrado / Mestre em Ciência da Computação

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-20T02:29:47Z (GMT). No. of bitstreams: 1 187559.pdf: 1326329 bytes, checksum: ce19b086716ef0ed401625c845169a37 (MD5) / Na busca por informações que auxiliem os processos de gerência da rede, do serviço e, inclusive, do relacionamento com o cliente, o registro da chamada telefônica, também conhecido como CDR (call detail recording), tem ganhado espaço. Mas, em virtude da imensa quantidade de CDRs gerados, bem como da diversidade de formatos existentes, a extração de informações do CDR não é uma tarefa muito fácil, principalmente por quem não possui conhecimentos aprofundados em linguagens de programação. Este trabalho propõe uma linguagem simples para a edição das regras de extração de informações do CDR e um ambiente computacional com interface web que permite a inserção de novos formatos e o cruzamento destas informações com outras (como lista telefônica, cadastros etc.). Visando facilitar a extração destas informações por profissionais de diversas áreas e sua utilização por várias aplicações, o ambiente e a linguagem propostos baseiam-se na teoria de compiladores. Através do uso de um editor dirigido pela sintaxe, que guia o usuário na edição da regra, garante-se sua corretude. Este editor é acompanhado de um tradutor desta regra, para linguagem C++, que é então executada gerando uma saída em arquivo texto ou XML (eXtensible Markup Language). Um caso de aplicação em CRM (Customer Relationship Management) é utilizado para validar a linguagem e o ambiente.

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T23:43:23Z (GMT). No. of bitstreams: 1 Cintra_MarceloSilva_M.pdf: 4931297 bytes, checksum: 7c0c9ec0d753cee26428360bb75ed2bd (MD5) Previous issue date: 2000 / Resumo: O modo de endereçamento indireto é o modo mais utilizado para acessos a arrays em programas que executam em arquiteturas CISC dedicadas. A razão para isto é que o endereçamento indireto permite o cálculo rápido de endereços usando instruções curtas. Este trabalho propõe uma solução para o problema de alocação de registradores de endereçamento para referências a elementos de arrays em laços, utilizando modo de endereçamento indireto combinado com auto-incremento. O resultado é um algoritmo que minimiza o número de registradores de endereçamento e instruções de redirecionamento requeridas por um programa. Este trabalho propõe uma extensão, para o caso multi-dimensional. de trabalhos anteriores baseados na cobertura do Grafo de Indexação(IG). Este trabalho propõe ainda um algoritmo de alocação global baseado em uma variação de Static Single Assignment Forra e uma heurística para a redução do número de registradores requeridos pela cobertura do IG. Um compilador otimizante pertencente à Conexant Systems Inc. é utilizado para testar estas idéias. Resultados experimentais, usando programas reais, mostraram uma melhoria de desempenho de 11.3% no tempo de execução quando comparado com uma técnica de coloração baseada em prioridade. Devido ao impacto da alocação de registradores na geração de código, esta técnica pode melhorar substancialmente o tamanho do código gerado, reduzindo a dissipação de energia e aumentando o desempenho do sistema. Estas características são extremamente desejáveis para o projeto de computadores portáteis modernos. / Abstract: Indirect addressing is by far the most used addressing mode in programs running in embedded CISC architectures. The reason is that it enables fast address computation combined with short instructions. This work proposes a solution to the problem of allocating address registers to array references within loops, when using indirect addressing combined with auto-increment. The result is an algorithm that minimizes the number of address registers and redirect instructions required by a program. It extends previous work using Indexing Graph(lG) covering to the multidimensional case, and proposes a global allocation algorithm based on a variation of Static Single Assignment Form. This work also presents a heuristic that aims at reducing the number of address registers required by the covering of the IG. An optimizing production compiler from Conexant Systems Inc. is used to test the approach. Experimental results, using real world-programs, showed an 11% performance improvement when compared to a priority-based register coloring technique. Because of the impact of register alocation in code generation, this technique can substantially improve code size, power dissipation and performance, without increasing cost. These are very desirable features for the design of modern portable computers. / Mestrado / Mestre em Ciência da Computação

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T21:43:33Z (GMT). No. of bitstreams: 1 Attrot_Wesley_M.pdf: 721177 bytes, checksum: 1c97565911cb6bc949136fe53ed46d5d (MD5) Previous issue date: 2004 / Resumo: O aumento da complexidade dos novos projetos de microprocessadores aumentou consideravelmente a necessidade de compiladores que sejam capazes de gerar codigo altamente otimizado. Isto resultou em uma grande demanda por novas otimizações de codigo que possam fazer uso dos novos recursos da arquitetura do processador. Projetar tais otimizações e um trabalho muito complexo que requer uma plataforma de compilação flexivel e simples de usar. O compilador Xingo foi desenvolvido como uma ferramenta para auxiliar o trabalho de pesquisa em areas como otimização de codigo e arquitetura de computadores. Xingo e um compilador otimizante capaz de gerar codigo C a partir de sua representação intermediaria. Tal caracteristica auxilia o desenvolvedor a avaliar a corretude e o desempenho de novas otimizações de codigo. Xingo tambem e um compilador redirecionavel, isto e, pode ser facilmente portado para varias arquiteturas. O compilador Xingo possui oito otimizações independentes de maquina (meados de mar¸co de 2004) e que foram avaliadas com a ajuda do benchmark NullStone, o qual e um benchmark para compiladores de produção de alta qualidade, amplamente utilizado por companias da industria da computação. Do total de 6611 testes realizados pelo NullStone, o Xingo produziu codigo correto para 6581 (99,54%) sem a aplicaçao de nenhuma otimização. Depois da aplicação de todas as otimizações disponiveis, o Xingo produziu codigo correto para 6497 testes (98,27%). Estes numeros refletem a qualidade da plataforma de compilação Xingo, abrindo uma nova gama de oportunidades de pesquisa nas 'areas de tecnologias de compila¸c¿ao e projeto de arquiteturas no Laboratorio de Sistemas de Computação (IC-UNICAMP). Pretende-se tornar o Xingo de dominio publico em meados de 2005 / Abstract: The increasing complexity of the new microprocessor designs has considerably increased the pressure for compilers that are capable of generating highly optimized code. This has resulted in a great demand for new code optimizations which can make an effective usage of the processor architectural resources. Designing such optimnizations is usually a very complex task that requires a flexible and easy to use compiler platform. The Xing'o compiler was designed as a tool to help researchers working in areas like compiling optimization and computer architecture. Xing'o is an optimizing compiler capable of generating compilable C code from its intermediate representation. Such feature considerably helps the designer in evaluating the correcteness and performance of new code optimization techniques. Xingo is also a retargetable compiler, that is, it can be easily ported for several architectures. The Xingo compiler has eight machine independent code optimizations (circa March 2004) and was evaluated with the help of the NullStone benchmark, a roduction-quality compiler benchmark, largely used by companies in the computer industry. Out of the 6611 programs available at Nullstone, Xing'o produced correct code for 6581 (99,54%) without the application of any optimization. After applying all the available optimizations, Xingo produced correct code for 6497 programs (98,27%). These numbers reflect the quality of the Xing'o compiling platform, opening up a new set of research opportunities in areas like compiling technology and architecture design at the Computer Systems Laboratory, (IC-UNICAMP). Xingo is planned to go on public domain by early 2005 / Mestrado / Ciência da Computação / Mestre em Ciência da Computação