PDA

View Full Version : Backtracking algorithm and OpenCL?



matt542
12-19-2009, 05:49 PM
Hi guys!

I'm just starting out with OpenCL and want to know if I'll get any performance improvement by porting over a backtracking algorithm (such as the one in a sudoku solver) to OpenCL?

Matt

dbs2
01-04-2010, 07:58 AM
OpenCL on GPU hardware is really optimized for data-parallel operation. Backtracking typically takes many many different code paths, which will perform very poorly on a GPU. Of course you still have more threads in parallel so you might win, but you won't see anything like the gains you'd get from a data-parallel algorithm. If you can figure out how to make your backtracking algorithm data-parallel then you could get a big win.

jeff474
01-09-2010, 01:08 AM
I was thinking of starting out with OpenCL as well but how complex is it it to get that big win :) thanks from me too for the reply its very helpful,