Cellular Genetic Algorithms and Local Search for 3-SAT problem on Graphic Hardware
China University of Geoscience, Wuhan
IEEE Congress on Evolutionary Computation, 2006. CEC 2006
@conference{luo2006cellular,
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},
pages={2988–2992},
isbn={0780394879},
year={2006},
organization={IEEE}
}
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.
January 23, 2011 by hgpu
