Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/38953
Tipo: | Dissertação |
Título: | A machine learning approach for data structure selection |
Título(s) alternativo(s): | Uma abordagem baseada em aprendizado de máquina para seleção de estrutura de dados |
Autor(es): | Tarsila Bessa Nogueira Assunção |
Primeiro Orientador: | Gisele Lobo Pappa |
Primeiro Coorientador: | Fernando Magno Quintão Pereira |
Primeiro membro da banca : | Diego Elias Damasceno Costa |
Segundo membro da banca: | Adriano César Machado Pereira |
Resumo: | Accurate data structure selection can vastly improve a program's performance and memory usage. However, it is hard to understand the behavior of a data structure in an application before running it, making choosing the best data structure to use in a computer program a complex task. This dissertation presents a framework capable of automatically selecting data structures for a given program and input. The framework consists of four components: a program data extractor, which collects information on the behavior of the data structures used in the input program; a feature constructor that transforms the extracted data into machine learning features; two different offline machine learning models which automatically select data structures to be used with the given application/input combination; and a program reconstructor that creates a new version of the input program using the data structures selected by the models. The framework is evaluated with synthetic and real world applications and is capable of reaching the same level of accuracy as the original developers when selecting the data structures for the applications. |
Abstract: | Uma seleção de estrutura de dados adequada pode melhorar bastante o desempenho e uso de memória de um programa. Porém, é difícil entender o comportamento de uma estrutura de dados em uma aplicação antes de executá-la, o que torna complexa a tarefa de escolher a melhor estrutura de dados para o uso em um programa de computador. Esta dissertação apresenta um framework capaz de selecionar, de maneira automática, estruturas de dados para um programa e sua entrada. O framework é formado por quatro componentes: um componente para extração de dados, que coleta informação sobre o comportamento das estruturas de dados usadas no programa dado como entrada; um construtor de features, que transforma as informações extraídas em features para modelos de aprendizado de máquina; dois modelos de aprendizado de máquina que selecionam automaticamente estruturas de dados para serem usadas com o conjunto de programa e entrada; e um reconstrutor de programas que cria uma nova versão da aplicação dada como entrada usando as estruturas de dados selecionadas pelos modelos. O framework é avaliado em aplicações sintéticas e reais e é capaz de atingir a mesma acurácia que os desenvolvedores originais ao escolher estruturas de dados para as aplicações. |
Assunto: | Computação – Teses Aprendizado de máquina – Teses Estrutura de dados – Seleção – Teses Redes neurais (Computação) – Teses |
Idioma: | eng |
País: | Brasil |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
Curso: | Programa de Pós-Graduação em Ciência da Computação |
Tipo de Acesso: | Acesso Aberto |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-nc-nd/3.0/pt/ |
URI: | http://hdl.handle.net/1843/38953 |
Data do documento: | 14-Dez-2020 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
a_machine_learning_approach_for_data_structure_selection.pdf | 3.49 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons