Nice announcement from Adobe, Photoshop CS5 will continue to use OpenGL for classical 2D and3D rendering, and will use nVidia CUDA Technology for Mercury Engine…
Mercury Engine is a rendering video renderer with real-time effects, using CUDA-technology (on Vidia 8xxx, 9xxx and GTx graphic cards), to accelerate effect and video rendering.
Thanks Adobe to use CUDA, and offer us to unleash the power of our computer 
The communication bottleneck is the worst thing in a multi-threaded chess program on CUDA (or OpenCL), as there’s few paper on that, especially considering the number of thread involved, compared to multi-CPU multi-core computers.
While Robert Hyatt and others try to have the best efficiency with up to 16 or 32 threads, maybe 64, the number of threads you may deal with on CUDA is one or two order of magnitude larger. And nodes/cpu are decreasing fast on more than 4 threads (using DTS high-performance parallel search), or 2 threads (with PVS algorithm).
A simple integrated graphic chip, like the GeFroce 9400M on laptops, is designed to run 144 threads at-once and might run thousands of threads, to hide memory latency. My desktop development system with GeForce GTX 260 needs at least 5 000 threads to be used at 100%.
The problem is that CUDA GPU needs a maximum number of threads to hide some instruction latencies (such as MULtiplications) or memory access latency (or worse ATOMIC m,emory access latency); and on the other side, actual parallel algorithm are designed for a few number of threads and unable to handle more than few dozen threads where we need to be able to handle thousands!
The problems:
Robert Hyatt DTS algorithm is an interesting point to start from, because it’s well documented, running on the best chess programs, with evident benefits over previous PVS algorithm.
My key idea wasn’t to make DTS works for 5 000 threads, but instead, to reduce the number of tasks that DTS should balance to the number of SM (each SM as 8 SP and handle from 32 to 768 threads basically), so there will be 2 tasks on an IGP GeForce 9400M and 27 tasks on GeForce GTX 260. Back on track with Robert Hyatt results
On each SM, I used only 32 threads in parallel, from the 192 threads expected to hide MUL latencies, because I don’t care about 1 MULtiplication, but care about register usage and Shared Memory limitations, respectively 8192 registers and 16KB.
Then I applied another reduction, grouping 8-threads into a group (micro-threading), having just 4 group by SM, each one processing one position, to -again- reduce communication needs between threads, using CUDA natural communication and synchronization technology: they share the same Instruction Pointer
So each SM, and it’s threads will be working on a subtree, doing a depth-first search, and splitting internally the work between the different macro-threads, with only 4 related position to examine in parallel. Reducing divergence between threads on the same warp because they work on positions isssued from the same split point, so they usually share a large amount of common representation and thus non-divergent processing.
And how to communicate between these 4 groups into the SM? Naturally using the DTS algorithm, with a simple implementation, as these threads are naturally synchronized by their Instruction Pointer, they will simply store results after each move or leaf and first one will handle split point to allocate work for the 4 into a group buffer in Shared memory.
At the SM level, there’s the advantages:
At the GPU-level:
On conclusion…
Using DTS algorithm on a high-level with low-level thread reduction and grouping (macro-threading and micro-threading), you could use a GPU with 64 threads at 74% and a GPU with 864 threads (GTX 260 216-core) with 47% efficiency, that is far more than expected using the best algorithms alone, with nVidia recommended number of threads.
PS: notice that the 47% efficiency correspond to only 10 threads using basic PVS algorithm, while we are actually using 864 threads on the GTX260 GPU!
This morning I was reading the Robert Hyatt’s article about Rotated bitmaps on Crafty Chess Engine, and it’s pretty interesting and real good, simple explanation, with deep understanding of the uathor and moreover he gives tracks to improvements that are awesome. Robert Hyatt, as many other gaves me real insight into modern chess programming and I love it!
How to implement it efficiently into a CUDA Chess Engine, that is 32bits by nature, albeit the algorithm itself is designed for 64bits? There’s also some great implementation, for example in Crafty (Robert Hyatt’s team engine) itself
A lesson that I learned, reading Robert Hyatt’s paper on implementation of programming techniques, is that you have to implement the inner loop first, efficient pre-ordering move generator, hash-table lookup and evaluator: their logical structure will probably impact the whole data structures of your code!
I used stupid simple structures, with functions to convert board to bitmaps, board to pieces->position, and back. That’s bad in CUDA, because you loose time (CPU cycles), you waste data storage (Registers and Shared Memory), and your code is more complicated with more divergence.
Programming Chess for CUDA consist of developping the basic inner loop first, move generator, hash-table lookup and evaluator, then construct your code around it, and it’s logical structure mapped to what will be needed at the inner loop level.
The new iPhone oS 4.0 brings 2 new features that are really hot, on the edge of technology for desktop, and 2 to 3 years ahead of other mobile platforms: OpenCL and Grand Central.
Grand Central is an Apple technology to parallelize and dispatch sub-tasks between multiple-thread, with few modification on the source-code level, without the need to explicitly launch threads or manage thread communication or synchronization, and object locking: it enable to easily add multi-threading to any part of a mono-threaded application, on a per-loop basis. It’s a breakthrough in computer technology to enable developper to use whatever number of core or executing threads are available.
OpenCL is the use of CPU or GPU to do some computations, if you read this blog, you probably know the technology and it’s potential.
What is surprising is to find these 2 technologies on a mobile platform, especially Grand Central, since all iPhone and iPod Touch sold are mono-core. But since iPad is dual-core, and some expect the future iPhone HD to be dual-core too, Grand Central take sense! And any iPad, iPod Touch and iPhone sport a GPU that is OpenCL compatible, so OpenCL Mathematical acceleration libraries that use the GPU to accelerate processing on iPad/iPhone/iPod Touch is a great move forward.
OpenCL, Grand Central, on desktop, laptop and now mobile platforms, this is totally awesome! Thanks Apple!