Muhammad Osama: SAT Solving using Ant Colony Optimization on GPUs


Event Details


In this talk, I will discuss how the Boolean Satisfiability (SAT) problem can be solved using a parallel implementation of the Ant Colony Optimization (ACO) algorithm for execution on the Graphics Processing Unit (GPU). We propose a new efficient parallel strategy for the ACO algorithm executed entirely on the CUDA architecture, and perform experiments to compare it with the best sequential version exists implemented on CPU with incomplete approaches. We show how SAT problem can benefit from the GPU solutions, leading to significant improvements in speed-up even though keeping the quality of the solution. Our results shows that the new parallel implementation executes up to 21x faster compared to its sequential counterpart.