Uma implementação paralela em GPU do algoritmo Walksat

Abstract

Resolverodores 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.