N-Queen Solver for OpenCL

Wow, that's great! I has been thinking about how to vectorize the code, although it's probably not easy but I think at least it's possible.

 

I found a bug which may prevent it to run with -local on G8X/G9X GPUs. A workaround is to specify thread numbers to multiple of 192 (such as 5376). I'll post updates later.

 

This works with the latest AMD Stream SDK 2.0.1 now. On my Radeon 4850 it takes 4.61 seconds to run 16 queen, and 3.79 seconds to run -local version. This is interesting because AFAIK Radeon 4850 does not support real local memory in OpenCL. However, it's possible that using local memory forces the compiler to use memory instead of registers so it reduces pressure on registers.

 

The new version uses a more complex algorithm to remove more symmetry. I'm not sure why using local is faster, though. I used the Stream KernelAnalyzer to compare the two kernels, but the local version seems to be using more registers than normal version, which is pretty odd.

I think the number of work items per work group is probably also an important factor. I plan to make a new option so it's possible to set the number of work items per work group (currently it's only possible to set the number of total work items).

If a vectorized kernel is faster (I'm still thinking about it), I think it's possible that Radeon 5870/5850 to be faster than GTX 285.

 

I have been experimenting with some optimization ideas. One is vectorization, another one is to reduce imbalance. That is, since each work item may take different time to run (some work items may end pretty soon while others may take a long time to finish), it creates an imbalance where some work items have to wait for other work items to finish, which is not very efficient. Furthermore, this problem is worse as the number of work items grows larger. However, the number of work items still has to be large enough to fully utilize the GPU, so it's a problem.

I made a simple modification to try reducing imbalance, by using a "global index" with an atomic add for each work item to get next work instead of just sit idle. Of course, this requires a GPU with support for atomic operations (i.e. cl_khr_global_int32_base_atomics).

Here are some prelimeary results (with GeForce 8800GT) :

New -local 17: 4.41s
Old -local 17: 5.06s

New -local 18: 32.8s
Old -local 18: 38.8s

New -local 19: 270s
Old -local 19: 330s

[EDIT] A test run with n = 20 takes around 2280 seconds.

 

I took a look at this program and it looks similar to my old algorithm, i.e. only the mirror symmetry is removed. I didn't recompile the program but it takes around 10 seconds to solve 16 queen on a Core 2 1.83GHz. The "rotation symmetry" removed program (the single threaded cpu path) takes 5.78 seconds to solve 16 queen.

 

Running on GTX 285:

New -local 17: 2.41s
Old -local 17: 2.44s

New -local 18: 15.1s
Old -local 18: 18.5s

New -local 19: 123s
Old -local 19: 155s

New -local 20: ~ 1060s

 

I got some weird problems now...
NVIDIA has released their new driver (196.75) which is supposed to support the latest ICD which is compatible with the latest ATI Stream SDK. However, after I installed the new driver, it can't find its own OpenCL device. After a few check I found out that nvcuda.dll lacks the necessary clIcdGetPlatformIDsKHR function (it has the other two functions).

So now it's a weird thing, which is, after installing ATI Stream SDK 2.0.1, NVIDIA's OpenCL.dll (which is actually Khronos' opencl.dll) can find only ATI's GPU on my computer. I delayed installing ATI Stream SDK 2.0.1 on my computer just because I was afraid that I might not be able to use my GTX 285 for OpenCL, but now NVIDIA's own driver just did that... Anyway, I hope they fixed that soon.

Then there is another problem. With previous SDK, the OpenCL compiler crashes with my n-queen kernel. 2.0.1 SDK fixed that. However, after I added the "imbalance reducing" logic (which is basically another loop around the original loop) it crashes again. Fortunately I coded a "force no atomics" option and I can verify that it runs without the new loop.

The new program is posted here instead of under the first post because it currently crashes with ATI Stream SDK 2.0.1 without the -noatomics option. It does not contain any of my vectorization experiments yet.

New options:

-noatomics: do not use atomics

Fixed:

-threads #: works with -local now


[EDIT] I reinstalled the driver and now OpenCL works again for NVIDIA's GPU. Now any OpenCL program can see both platforms working! That's great!

 

The OpenCL version runs faster when it uses the same technique as the older CUDA version.
However, with newer algorithms 16 queen takes longer to run (although 17 or larger queens take less time to run).