Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/24656
Título: | Estratégias de solução para o problema de alocação de registradores em compiladores |
Título(s) alternativo(s): | Solution strategies for the register allocation problem in compilers |
Autor(es): | Shimosaka, Gabriel Hitoshi |
Orientador(es): | Barbosa, Marco Antonio de Castro |
Palavras-chave: | Compiladores (Computadores) Programação heurística Grafos de ligação Compiling (Electronic computers) Heuristic programming Bond graphs |
Data do documento: | 12-Dez-2019 |
Editor: | Universidade Tecnológica Federal do Paraná |
Câmpus: | Pato Branco |
Citação: | SHIMOSAKA, Gabriel Hitoshi. Estratégias de solução para o problema de alocação de registradores em compiladores. 2019. Trabalho de Conclusão de Curso (Engenharia de Computação) - Universidade Tecnológica Federal do Paraná (UTFPR), Pato Branco, 2019. |
Resumo: | O principal objetivo de um compilador é transformar o código de uma linguagem fonte em uma linguagem objeto. Para isso, o código gerado pelo compilador deve fazer uso efetivo dos recursos limitados do processador. Entre os recursos mais restritos, está o conjunto de registradores. Portanto, a alocação de registradores é uma etapa de extrema importância para o processo de compilação. Compiladores modernos geralmente abstraem esse problema como um problema de Coloração de Grafo, pois este tipo de abordagem captura alguns dos aspectos críticos da alocação. Porém, realizar esta coloração de forma ótima, ou seja, da melhor maneira possível, caracteriza-se como um problema NP-Completo. Como os algoritmos conhecidos que resolvem estes problemas de maneira exata possuem um comportamento de pior caso exponencial, as heurísticas são adotas. Elas são capazes de dar uma boa solução em um tempo aceitável. Com o desenvolvimento deste trabalho foi possível realizar um comparativo entre diferentes estratégias e implementar uma solução alternativa com resultados iguais ou superiores. |
Abstract: | The main purpose of a compiler is to transform the code from a source language into a target language. To this end, the code generated by the compiler must make effective use of the limited processor resources. The set of registers is one of the most restricted resources in a processor. Therefore, the register allocation is an extremely important stage for the compilation process. Modern compilers generally abstract this problem as a Graph Coloring problem, because this type of approach captures some of the critical aspects of allocation. However, performing this coloration optimally, that is, in the best possible way, is characterized as an NP-Complete problem. Because known algorithms that solve these problems accurately have a worst-case exponential behavior, heuristics are adopted. They are able to give a good solution in an acceptable time. With the development of this paper, it was possible to compare different strategies and implement an alternative solution with equal or better results. |
URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/24656 |
Aparece nas coleções: | PB - Engenharia de Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
PB_COENC_2019_207.pdf | 796,81 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.