4342

A Highly Scalable Solution of an NP-Complete Problem Using CUDA

Saiyedul Islam, Raghav Tandon, Shashank Singh, Alok Misra
6th International Symposium on Parallel Computing in Electrical Engineering (PARELEC), 2011

@inproceedings{islam2011highly,

   title={A Highly Scalable Solution of an NP-Complete Problem Using CUDA},

   author={Islam, S. and Tandon, R. and Singh, S. and Misra, A.},

   booktitle={Parallel Computing in Electrical Engineering (PARELEC), 2011 6th International Symposium on},

   pages={93–98},

   organization={IEEE},

   year={2011}

}

Source Source   

697

views

NP Complete problems are one of the most complex problems in computer science but their vast applications in real world always pushes the scientists to explore new ways to solve them. We extended the original problem definition of Boolean Satisfiability Problem to finding all satisfiable solutions of a given problem instance and used massively parallel architecture of CUDA (Compute Unified Device Architecture) for reducing its run time. Certainly, exponential time complexity of this NP Complete problem can’t be so easily reduced to polynomial time but through our implementation it can be well challenged for sufficiently large number of inputs. Our fully optimized implementation attained speedup ranging from 19x to 188x on Nvidia Ge Force GTX 260 for different type of SAT problems.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: