Name
Title | ||
|---|---|---|
An Efficient Implementation of Ant Colony Optimization on GPU for the Satisfiability Problem |
Abstract | ||
|---|---|---|
This paper focuses on solving the Boolean Satisfiability (SAT) problem using a parallel implementation of the Ant Colony Optimization (ACO) algorithm for execution on the Graphics Processing Unit (GPU) using NVIDIA CUDA (Compute Unified Device Architecture). 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/PDP.2015.59 | PDP |
Keywords | Field | DocType |
parallel processing,ant colony optimization,boolean satisfiability problem | Ant colony optimization algorithms,Architecture,Computer science,CUDA,Parallel computing,Parallel processing,Boolean satisfiability problem,Sat problem,General-purpose computing on graphics processing units,Graphics processing unit | Conference |
ISSN | Citations | PageRank |
1066-6192 | 2 | 0.38 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hassan A. Youness | 1 | 5 | 1.88 |
| Aziza Ibraheim | 2 | 2 | 0.38 |
| Mohammed Moness | 3 | 13 | 2.86 |
| Muhammad Osama | 4 | 12 | 3.37 |