Utilize este link para identificar ou citar este item: https://bdm.unb.br/handle/10483/34524
Arquivos neste item:
Arquivo Descrição TamanhoFormato 
2022_LuisHenriquePereiraTaira_tcc.pdfTrabalho de conclusão de curso1,32 MBAdobe PDFver/abrir
Registro completo
Campo Dublin CoreValorLíngua
dc.contributor.advisorRibas, Bruno César-
dc.contributor.authorTaira, Luís Henrique Pereira-
dc.identifier.citationTAIRA, Luís Henrique Pereira. Uma implementação paralela em GPU do algoritmo Walksat. 2022. 39 f., il. Trabalho de conclusão de curso (Bacharelado em Engenharia de Software) — Universidade de Brasília, Brasília, 2022.pt_BR
dc.descriptionTrabalho de conclusão de curso (graduação) — Universidade de Brasília, Faculdade UnB Gama, 2022.pt_BR
dc.description.abstractResolverodores SAT são os programas de computador que resolvem o problema da Satisfatibilidade, que, por ser um dos problemas NP-Completos e por suas aplicações, é um importante problema para a Ciência da Computação. Por isso, várias áreas do conhecimento são impactadas quando melhor desempenho é alcanlçado por Resolvedores SAT. O uso de processamento paralelo é uma forma comum de se realizar grandes quantidades de computação no menor tempo possível. Portanto é interessante utilizar paralelização em Resolvedores SAT para obter o melhor desempenho possível. Este trabalho teve como objetivo investigar o potencial de melhora do desempenho de um Resolvedor SAT, baseado no algoritmo Walksat, mediante a aplicação de processamento paralelo. Para isso foram desenvolvidos dois Resolvedores SAT baseados no Walksat, um serial e um paralelo que usa aceleração de GPU (Graphical Processing Unit) para que pudesse ser feita uma análise comparativa de seus desempenhos. Os resultados obtidos por meio de testes demostraram que a implementação paralela teve desempenho significativamente pior do que as implementações seriais. Os resultados dos testes mostraram também que a implementação paralela obtida não utiliza todo o potencial de processamento paralelo de uma GPU. Portanto teoriza-se que uma implementação melhor otimizada do Walksat para GPU possa alcançar desempenho melhor.pt_BR
dc.rightsAcesso Abertopt_BR
dc.subject.keywordLinguagem de programação (Computadores)pt_BR
dc.subject.keywordProgramação paralela (Computação)pt_BR
dc.subject.keywordAlgoritmos de computadorpt_BR
dc.titleUma implementação paralela em GPU do algoritmo Walksatpt_BR
dc.typeTrabalho de Conclusão de Curso - Graduação - Bachareladopt_BR
dc.date.accessioned2023-04-11T13:26:35Z-
dc.date.available2023-04-11T13:26:35Z-
dc.date.submitted2022-
dc.identifier.urihttps://bdm.unb.br/handle/10483/34524-
dc.language.isoPortuguêspt_BR
dc.rights.licenseA concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor que autoriza a Biblioteca Digital da Produção Intelectual Discente da Universidade de Brasília (BDM) a disponibilizar o trabalho de conclusão de curso por meio do sítio bdm.unb.br, com as seguintes condições: disponível sob Licença Creative Commons 4.0 International, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação desta.pt_BR
dc.description.abstract1The objective of this research was to investigate the performance gains of a SAT Solver based on the Walksat algorithm when parallel processing is used. For this purpose, two Walksat based SAT Solvers were developed, one based on serial processing and the other on parallel processing using GPU (Graphical Processing Unit) acceleration, so that a comparative analysis of their performance could be made. SAT Solvers are computer programs that solve the Satisfiability problem, which is an important topic for Computer Science because of its applications and for being an NP Complete problem; therefore, many areas of knowledge are impacted when SAT Solvers achieve better performance. A common way to execute large amounts of computation in the shortest amount of time possible is to use parallel processing. Hence, it is of interest, to use parallelization to achieve the best possible performance in SAT Solvers. The results, that were obtained via tests, demonstrated that the parallel implementation had significantly worse performance than the serial implementations. The results also showed that the parallel solution does not utilize all of the parallel processing potential of a GPU and thus it is theorized that a better optimized implementation for GPU of the Walksat algorithm could accomplish better performance.pt_BR
Aparece na Coleção:Engenharia de Software



Todos os itens na BDM estão protegidos por copyright. Todos os direitos reservados.