Cellular Genetic Algorithms and Local Search for 3-SAT problem on Graphic Hardware

Zhongwen Luo, Hongzhi Liu
China University of Geoscience, Wuhan
IEEE Congress on Evolutionary Computation, 2006. CEC 2006


   title={Cellular genetic algorithms and local search for 3-sat problem on graphic hardware},

   author={Luo, Z. and Liu, H.},

   booktitle={Evolutionary Computation, 2006. CEC 2006. IEEE Congress on},






Source Source   



As a well known NP-hard problem, SAT problem is widely discussed by computer science society. In this paper, two common algorithms for SAT problems are implemented based on graphic hardware. They are greedy local search and genetic algorithm. After a brief description of the basic algorithm, we give our modification of the algorithm for fitting with graphic hardware’s SIMD model. Then some implementation details and tricks for graphic hardware are given. At last testing result are given. We compared the performance of graphic hardware based computation with CPU based computation. The result shows a performance improvement on graphic hardware over ordinary CPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: