Zeta OpenCL Chess

AMD HD 7970 released

2011-12-22T16:53:00.006+01:00

AMD released the new top model HD 7970,
price will be about 500 Euros.

The new GCN architecture works now with 16 wide SIMD Units, with 4 SIMD Units on one Compute Unit.

Another point is the 384 bit Memory Interface with a bandwidth of 264GB/s!

Data
Cores: 2048
Compute Units: 32
SIMD Units: 32x4
GPU Clock: 925 MHz
GFLOP/s SP: 3790
GFLOP/s DP: 947
Memory Interface: 384 bit
Memory Clock: 1375MHz (GDDR5)
Memory Bandwidth: 264GB/s
private memory/SIMD Unit: 64 KB
local memory/Compute Unit Unit: 64 KB

Alternatives to pure AlphaBeta

2011-12-20T00:10:00.010+01:00

Monte Carlo Simulations with UCT
Monte Carlo Simulations with the UCT optimization work well for the Game of GO, but, as reported, not for Chess. Maybe with the computing power of an GPU there is a chance for it?
An MC-Approach runs thousands of random games and decides by the overall win/loss counters if a position is weak or strong.
UCT adds some heuristics to the randomness of game selection.

Nagging with SPAM
Naggers support the master process by searching, with a narrowed alpha-beta window, nodes from a tree to get updated AlphaBeta Values for the master process.

Pure Negamax or MiniMax
Has to search 100x more nodes than a serial performed AlphaBeta with good move ordering.

Zeta 094x - new stack design

2011-12-19T17:20:00.003+01:00

i am going to implement a spinlocked, two way linked list as a stack in the new version.

Hope this will boost things up, because changing some pointers should be faster than to copy hole boards.

###edit###

i will switch first with the 0933 design to a pointer based copy process and see how this will peform...

--
Srdja

Zeta 093x - lifo copy kills performance

2011-12-19T17:18:00.004+01:00

i 've tried to implement a shared lifo stack across simd units in 0933 and 0934, but the copy process kills the performance....

--
Srdja

New AMD GPUs in January?

2011-12-17T21:54:00.005+01:00

Regarding to some hardware-sites we will see new AMD GPUs in January, the HD 7000 series.
The top model, 7970, is suspected to hold 2048 stream processors on board, spread on 32 compute units. The HD 6970 has 1536 stream cores on 24 compute units.

According to AMD white papers each compute unit will be able to compute 10 Warps/Wavefronts with 64 threads and will have 64 KB Registers and 64 KB shared/local memory.

--
Srdja

Summary III: GPUs and Chess

2011-12-13T20:05:00.005+01:00

GPU as Coprocessor
Because of the communication latency between Host and GPU a no go,
maybe AMDs and Intels new APUs are more decent for this but afaik there are not many gpu cores on die.

Multi-Thread One Board Idea
I've tested different approaches for an architecture where multible threads work simultan on one chess position, but the peformance loss by workless threads was too high.

One Thread One Board Idea
Pro: Has the best occupancy of threads
Con: Limited Registers Memory per Thread causes a low Warp/Wavefront occupancy.

Board Presentation
My current solution is to use Quad-BitBoards, they use 32 Bytes for one Chess Position plus 8 Bytes additional Information like Castle Rights, so i can run 4*32 threads on one SIMD Unit of an NV GTS250.

Move Generation
QuadBitboards with an Magic BitBoard Move Generator are 64 bit based and perform better than an 32 bit 0x88 Move Generator with nested loops.

Parallel Search Algorithm
A Three-Tier Solution is needed,

1) for all Threads/work-items in one Warp/Wavefront on one SIMD Unit
2) for different Warps/Wavefront running on one SIMD Unit.
3) for distributing work across SIMD Units.

Outlook
- Board Presentation, solved
- Move Generation, solved
- Brute Force Negamax Algorithm for one SIMD Unit, solved

missing is a Parallel AlphaBeta Pruning Solution inside and across SIMD Units.

32 bit move generator again?

2011-12-05T15:37:00.005+01:00

I am not satisfied with the single thread performance, maybe i should switch back from BitBoards to an 0x88 move generator because GPUs are 32 bit optimized....not sure how the nested loops will perform on a simd unit...

### edit ###

ahh, i will keep the QuadBitBoards, they consume only 32 bytes of memory so i can run multible warps/wavefronts on one SIMD Unit.

### edit ###
I tested a 32 bit 0x88 move generator, but it does not perform as quick as the Magic Bitboard move generator....i guess the nested loops are not very SIMD friendly.

--
Srdja

Zeta 0934 - One Lifo Stack One Thread?

2011-12-05T15:33:00.003+01:00

A shared LIFO-Stack doesn't perform well with AlphaBeta Pruning, so maybe i can use one LIFO-Stack per thread and distribute somehow work accross threads.

Zeta 0934, search depth 4, good ab pruning with move ordering, one thread:

nodes: 1922 ,movecount: 11492, bestmove: 17900673 ,sec: 0.600000
nodes: 3055 ,movecount: 18177, bestmove: 17913158 ,sec: 0.750000
nodes: 11336 ,movecount: 60309, bestmove: 9008591 ,sec: 2.790000
nodes: 7692 ,movecount: 40912, bestmove: 17963090 ,sec: 2.780000
nodes: 5075 ,movecount: 29170, bestmove: 17892385 ,sec: 1.370000
nodes: 14323 ,movecount: 66261, bestmove: 17983893 ,sec: 3.190000
nodes: 4775 ,movecount: 37989, bestmove: 648577536 ,sec: 2.860000
nodes: 3471 ,movecount: 23288, bestmove: 219372902 ,sec: 1.120000
nodes: 9960 ,movecount: 37534, bestmove: 44564488 ,sec: 1.980000
nodes: 19522 ,movecount: 69898, bestmove: 17829968 ,sec: 4.000000

Zeta 0933 - Lifo Stack with bad AlphaBeta performance

2011-12-04T17:13:00.004+01:00

Negamax worked fine, but AlphaBeta Pruning performs bad.

Because i don't use a linked list as LIFO Stack i am not able to delete all Boards pruned by a Beta Cutoff, i have to visit every Board and then do the Cutoff again.

Zeta 0933, search depth 4, bad ab pruning, 128 threads on one simd unit:

nodes: 76869 ,movecount: 76869, bestmove: 17900673 ,sec: 0.330000
nodes: 97599 ,movecount: 97599, bestmove: 17913158 ,sec: 0.280000
nodes: 209102 ,movecount: 209102, bestmove: 9008591 ,sec: 0.560000
nodes: 206391 ,movecount: 206391, bestmove: 17963090 ,sec: 0.560000
nodes: 187838 ,movecount: 187838, bestmove: 17892385 ,sec: 0.500000
nodes: 276374 ,movecount: 276374, bestmove: 17983893 ,sec: 0.760000
nodes: 142551 ,movecount: 142551, bestmove: 648577536 ,sec: 0.400000
nodes: 173269 ,movecount: 173269, bestmove: 219372902 ,sec: 0.460000
nodes: 229713 ,movecount: 229713, bestmove: 44564488 ,sec: 0.640000

--
Srdja

Zeta 0932 - Lifo Stack with negamax scores

2011-12-04T02:17:00.003+01:00

Got a LIFO Stack based processing within one SIMD Unit with negamax score running. Next topic is alpha beta pruning.

Zeta 0932, search depth 4, no ab pruning, 128 threads on one simd unit:

nodes: 206603 ,movecount: 206603, bestmove: 17900673 ,sec: 0.640000
nodes: 286578 ,movecount: 286578, bestmove: 17913158 ,sec: 0.710000
nodes: 554825 ,movecount: 554825, bestmove: 9008591 ,sec: 2.170000
nodes: 575267 ,movecount: 575267, bestmove: 17963090 ,sec: 3.380000
nodes: 632190 ,movecount: 632190, bestmove: 17892385 ,sec: 1.640000
nodes: 620515 ,movecount: 620515, bestmove: 17983893 ,sec: 1.630000
nodes: 636666 ,movecount: 636666, bestmove: 648577536 ,sec: 1.640000
nodes: 912485 ,movecount: 912485, bestmove: 219372902 ,sec: 2.420000
nodes: 673506 ,movecount: 673506, bestmove: 44564488 ,sec: 1.790000

--
Srdja

LIFO Stack and AlphaBeta Values

2011-12-03T18:47:00.002+01:00

i managed to distribute work within an SIMD Unit by use of an LIFO-Stack,
it looks faster than any previous solution,

but i don't have an idea how to handle the AlphaBeta Values,
a spinlocked, linked list is a nogo because of the SIMD nature of the architecture.

--
Srdja

LIFO Stack based Parallel Processing?

2011-11-30T12:01:00.003+01:00

i am expirementing with one LIFO-Stack per Thread,
so every thread works on his own Stack and workless Threads look in other Stacks for work to do.

--
Srdja

Zeta 0.920 - One Thread one Board

2011-09-24T13:15:00.003+02:00

Source:
Nvidia
https://github.com/smatovic/Zeta/tree/zeta_nvidia_0920
AMD
https://github.com/smatovic/Zeta/tree/zeta_amd_0920

Changes:
- one thread handles one board

Still Missing:
- castle moves
- en passant moves
- checkmate detection
- Quiscence Search

Zeta 0.920 uses one thread to compute the tree of one chess position.

Performance:
This design makes about 10 000 nps per Thread, with currently only one thread running.

Search depth 5 with AlphaBetaPruning and MoveOrdering:

nodes: 16875 ,movecount: 73700,sec: 1.820000
nodes: 54307 ,movecount: 260524,sec: 4.400000
nodes: 97125 ,movecount: 624798, sec: 8.410000
nodes: 113395 ,movecount: 1038605, sec: 10.530000

Outlook:
Next topic would be to build a load-balancing mechanism.

--
Srdja

Zeta 0.920 - One Thread one Board again

2011-09-23T14:29:00.003+02:00

The "One SIMD Unit One Board" Idea, is propably a dead end.

Too many idle threads, and a lausy Quiscence Search performance.

So i will try the "One Thread One Board" Idea again.

--
Srdja

Zeta 0.919 - Developer Release update

2011-09-22T11:57:00.004+02:00

Source:
https://github.com/smatovic/Zeta/tree/zeta_nvidia_0919

Changes:
- code cleanup
- root search move generation now on GPU.
- added buttom up heap sort for move ordering

Still Missing:
- castle moves
- en passant moves
- checkmate detection
- Quiscence Search

Zeta 0.919 uses one SIMD Unit with 128 Threads to compute one Chess Position in Parallel.
It assumes that there are not more than 128 possible moves from one position.
This parallel processing i call "SPPS - a Simple Parallel Processing Scheme".

Performance:
SPPS is quite slow....here some numbers with alphabeta pruning, move ordering and search depth 4 on a NV GTS 250:

nodes: 10209 ,movecount: 28354, sec: 0.290000
nodes: 16262 ,movecount: 70892, sec: 0.250000
nodes: 52921 ,movecount: 241981, sec: 0.670000
nodes: 35852 ,movecount: 379419, sec: 0.560000
nodes: 25582 ,movecount: 489738, sec: 0.450000
nodes: 57894 ,movecount: 721321, sec: 0.850000
nodes: 35494 ,movecount: 795703, sec: 0.350000
nodes: 20580 ,movecount: 874357, sec: 0.330000
nodes: 32805 ,movecount: 1033972,sec: 1.540000
nodes: 61802 ,movecount: 1404020,sec: 3.570000
nodes: 68647 ,movecount: 1800534,sec: 1.210000
nodes: 83326 ,movecount: 2325336,sec: 2.870000
nodes: 21810 ,movecount: 2559152,sec: 0.700000
nodes: 49937 ,movecount: 2730154,sec: 2.020000
nodes: 87208 ,movecount: 3233045,sec: 1.500000
nodes: 38732 ,movecount: 3577365,sec: 1.050000

Outlook:
Next topic would be to build a load-balancing mechanism across SIMD Units.

--
Srdja

Zeta 0.919 - heapsort

2011-09-21T15:51:00.002+02:00

heapsort is faster but not that much,
i think because of the simd structure it is more efficient to sort in parallel with 128 threads than every thread on its own...will try some parallel sorting mechanism.

##edit##
parallel sorting across global memory is a nogo because of unsynched reads/writes.

--
Srdja

Zeta 0.919 - bad bubblesort?

2011-09-20T19:53:00.004+02:00

hmm,

Zeta with move ordering has less nodes but needs ins some cases more time than zeta with alphabeta pruning only,
propably bubblesort performs too many global memory reads and writes...will try quicksort.

--
Srdja

Zeta 0.918 - Developer Release

2011-09-18T22:18:00.003+02:00

Second Developer Release:

https://github.com/smatovic/Zeta/tree/zeta_nvidia_0918

Changes:
- code cleanup
- Added Alphabeta Pruning
- Added Move Ordering

Runs still on one SIMD Unit with 128 threads only.
It is time for an Load-Balancing mechanism across SIMD Units.

--
Srdja

"One SIMD Unit One Board" vs. "One Thread One Board"

2011-09-18T22:06:00.003+02:00

have to make a decision which design i want to use....

i think it is easier to handle tens of SIMD Units than thousands of threads.

--
Srdja

SPPS with AlphaBeta Pruning

2011-09-18T21:15:00.003+02:00

I ve implemented AlphaBeta Pruning in the SPPS Search which works like "One SIMD Unit One Board".

I thought i could give each SIMD Unit of the GPU one of the moves of the first search depth to compute. But i had to realize that this is a stupid idea.
AlphaBeta Pruning does not perform in this kind of way, parallization has to be done where good moves are suspected and not at the root.

--
Srdja

Zeta 0.917 - AlphaBeta Pruning with Move Ordering

2011-09-17T22:07:00.006+02:00

AlphaBeta with Move Ordering works fine on the GPU:

One Thread, search depth 4, without AlphaBeta Pruning:
nodes: 197281, sec: 9.720000

One Thread, search depth 4, with AlphaBeta Pruning:
nodes: 28464, sec: 3.340000

One Thread, search depth 4, with AlphaBeta Pruning and Move Ordering:
nodes: 9636 ,sec: 1.350000

--
Srdja

SPAM - Scalable Parallel Alpha-Beta Minimax

2011-09-17T20:24:00.004+02:00

an alternative parallel search algorithm based on "Nagging" by Alberto Maria Segre and others.

maybe this is what i was looking for...

--
Srdja

Zeta 0.917 - AlphaBeta Pruning is running

2011-09-16T17:41:00.004+02:00

:-)

x5-x10 Speedup, will take a look how MVV-LVA move ordering will perform.

--
Srdja

Zeta 0.916 - redesign looks good

2011-09-15T14:34:00.002+02:00

working on a redesign,
so every thread handles one board -> "one thread one board",
looks good.

Next Topics:
- AlphaBeta Pruning
- Special Moves
- Incremental Eval
- feed the threads more efficient with boards

--
Srdja

Zeta 0.916 - SPPS over multible SIMD Units

2011-09-13T18:45:00.003+02:00

Working on an extension of the SPPS Algorithm to work across multible SIMD Units.

Currently only one SIMD Unit of a GPU is used, a GPU has tens of those SIMD Units.

Have to consider Memory Usage, would be nice to get AlphaBeta-Pruning and Quiscence-Search directly implemented.

--
Srdja

Zeta 0.915 - First Developer Release

2011-07-13T21:33:00.006+02:00

Heyho,

today is the montenegrin Independence Day and i published the Source Code of Zeta under GPL:

for Nvidia Devices:
https://github.com/smatovic/Zeta/tree/zeta_nvidia_0915

and for AMD GPUs or Intel/AMD CPUs
https://github.com/smatovic/Zeta/tree/zeta_amd_0915

Zeta is more a prototype than a real chess engine. It uses only one SIMD Unit of a GPU with 128 Threads,
this is enough to achieve about 100 000 NPS, but still far away from that what a GPU is really able to compute, it is like using only 1 of 16 Cores.

Zeta is written in OpenCL, so it is able to run on GPUs, CPUs, APUs.

Zeta plays weak and buggy, a lot of well known chess techniques are not implemented.

So, whats inside?

- SPPS - a Simple Parallel Processing Scheme
- Quad-Bitboard Board Representation (Thanks to Gerd Isenberg, http://chessprogramming.wikispaces.com/Quad-Bitboards)
- Magic Bitboard Move Generator (Thanks to the Stockfish Team)
- Tablebased Evaluation (Thanks to Tomasz Michniewski, http://chessprogramming.wikispaces.com/Simplified+evaluation+function)

What's missing?

- Castle Moves
- En Passant Moves
- AlphaBeta Pruning
- Qsearch
- SMP over mutlible SIMD Untis
- All other well known techniques

Supported Platforms?
Until now only Linux with AMD OpenCL SDK or NVIDIA OpenCl SDK. No binaries.
CPUs (>=SSE3) will also work with AMD OpenCL SDK.

So feel free to contribute in GPU Chess :)

--
Srdja Matovic

Beaten by GPU in Chess

2011-07-09T07:42:00.005+02:00

Ok, i am a really bad player, but i got beaten by my GPU in chess.....

Zeta 0.912 - Fallback to SPPS

2011-07-07T23:29:00.002+02:00

DPPS is fast and has a good scalability, but i was not able to build a score-structure into it. It is just good for performance testing....so back to SPPS with its 128 threads per chess position.

--
Srdja

Zeta 0.910 - First Release Candidate

2011-07-06T14:53:00.003+02:00

I think i will finnish my work on DPPS, computing on one SIMD Unit only, and release the source.

Maybe 13th July would be a nice release date, it is the montenegrin independence day :)

Todo-List:

Castle Moves
En passant Moves
AlphaBeta Pruning
MVV-LVA Move ordering

After the release i can think about mutlible SIMD Unit with DPPS.

--
Srdja

Coprocessor idea is a no go

2011-07-05T21:37:00.004+02:00

made some tests,
100 GPU calls for move generation take about 1 second....

--
Srdja

Some numbers

2011-07-04T22:11:00.007+02:00

Here some numbers, the nps value is not compareable to that one from real chess engines...

SPPS, one SIMD Unit, 128 Threads:	500 Knps
DPPS, one CPU 2 Ghz Core:	5000 Knps
DPPS, one SIMD Unit 1 Thread	100 Knps
DPPS, one SIMD Unit 2 Threads	200 Knps
DPPS, one SIMD Unit 4 Threads	400 Knps
DPPS, one SIMD Unit 8 Threads	800 Knps
DPPS, one SIMD Unit 16 Threads	1000 Knps
DPPS, one SIMD Unit 32 Threads	1200 Knps
DPPS, one SIMD Unit 64 Threads	1200 Knps

Zeta 0.911 - GPU as a Coprocessor again?

2011-07-04T20:34:00.003+02:00

I was able to implement a non-recursive, negamax-like search algorithm on one SIMD Unit of the GPU.

But SIMD Units run autonomous, so i reconsider the idea to let the GPU act as a Move-Generator and Evaluation-Processor only, the search itself would be done on the CPU.

--
Srdja

Zeta 0.910 - DPPS in sync but slow

2011-07-04T16:53:00.003+02:00

DPPS on one SIMD Unit is fast, because it has an internal sync function. Across more SIMD Units therre is no built-in sync function, so i have to let the others SIMD Units wait for the workers and this method slows the hole procedure down.

Have to redesign the use of multible SIMD Units.

--
Srdja

Nvidia 28 nm GPU Keppler in Q4 2011?

2011-07-02T13:31:00.004+02:00

According to some news sites Nvidia has just taped out their Keppler series....this seems a bit late for a production date in Q4 2011, maybe Q2 2012 is more approriate.

--
Srdja

Zeta 0.905 - DPPS out of sync

2011-07-01T19:04:00.004+02:00

with the current design i am running out of sync between different warps/wavefronts/ and different SIMD Units.

SPPS works only inside of one work-group (SIMD Unit) and DPPS works only inside of one Warp/Wavefront of a SIMD Unit.

Need somekind of "wait_until_others_finishes();"

--
Srdja

Zeta 0.905 - DPPS with 1 to 32 threads running

2011-06-28T00:37:00.002+02:00

got DPPS with max 32 threads running, nice speedup, but it is difficult to handle global vars within different warps/wavefronts and different SIMD Units.

The GTS250 handles 32 Threads in one Warp, so i have to take care about counters for the next Warp...

--
Srdja

Zeta 0.905 - DPPS

2011-06-26T17:38:00.003+02:00

working on a Dynamic Parallel Processing Scheme. The current SPPS-Search needs 128 threads for each board position, the coming DPPS will use only as much threads as moves are present...will take some time.

--
Srdja

Zeta 0.903 - Quiscence Search

2011-06-24T01:40:00.003+02:00

As i thought the SPPS-Search with 128 parallel Threads has problems when the engine enters the Q-Search. In Q-Search are only Capture-Moves considered and as fewer the moves size is the more power i am loosing with spps :(

--
Srdja

Zeta 0.903 - Negamax Scores working

2011-06-23T11:40:00.004+02:00

Got an parallel mechanism running which behaves like a non-recursive Negamax with 128 parallel threads, i call it "SPPS" - a Simple Parallel Processing Scheme.

..in other words, Zeta plays its first games of chess :)

--
Srdja

Zeta 0.9 - Profiler data

2011-06-21T13:19:00.000+02:00

Occupancy Analysis for kernel spps_gpu on device GeForce GTS 250

Kernel details: Grid size: [16 1 1], Block size: [1 128 1]

Register Ratio: 0.9375 ( 7680 / 8192 ) [59 registers per thread]
Shared Memory Ratio: 0.28125 ( 4608 / 16384 ) [4208 bytes per Block]

Active Blocks per SM: 1 (Maximum Active Blocks per SM: 8)
Active threads per SM: 128 (Maximum Active threads per SM: 768)

Potential Occupancy: 0.166667 ( 4 / 24 )
Achieved occupancy: 0.166667 (on 16 SMs)

Occupancy limiting factor: Registers

--
Srdja

Zeta 0.9 - and correct Perft results :)

2011-06-21T01:43:00.001+02:00

it took some while, but now are the nodecounters correct.....move gen works still without castling and en passant.

--
Srdja

Zeta 0.9 - Good Perft Performance

2011-06-20T17:48:00.003+02:00

first performance tests for move generation with parallel mechanism look good.

the holy question is if the alpha-beta pruning with move ordering performs as good as on a CPU....

--
Srdja

Debugging the move generator

2011-06-19T11:40:00.002+02:00

for debugging the move generator perft is verrry usefull:

http://chessprogramming.wikispaces.com/Perft+Results

--
Srdja

AMDs Graphics Core Next - GCN

2011-06-18T16:45:00.004+02:00

Infos about AMDs next GPU architecture:

http://www.anandtech.com/show/4455/amds-graphics-core-next-preview-amd-architects-for-compute

Changes:

non-VLIW Design
16 wide SIMD Units
4 SIMD Units / Compute Unit
10 Wavefronts / SIMD Unit
64 KB registers / SIMD Unit
64 KB LDS / CU

According to a german news site it is unlikely that GCN will be launched in 2011.

--
Srdja

New 28 nm GPUs from AMD this year

2011-06-17T13:32:00.000+02:00

according to some news sites AMD is going to launch new 28 nm GPUs this year.

It is not clear if only the performance will increase or a new GPU architecture will be introduced....

--
Srdja

Zeta 0.9 - Pieces are moving again

2011-06-16T16:48:00.005+02:00

Yeeha, Pieces are moving again on the GPU :)

Zeta 0.9 approach

Quad Bitboard Board Presentation
Magic Bitboard Move Generation for sliders
Attack Tables for non-sliders

Thought a while on a 32 bit Move Generator but 1) the board presentation uses too much memory and 2) the nested while loops are not very SIMD friendly.
Quad Bitboards use only 32 Bytes for one Board and can be combined with a fast Magic-Bitboard Move Generator.

I also tried a Kogge-Stone Move Generator with 8 threads for 8 directions in parallel, but the Magic Bitboards performed better.

On the Nvidia GTS250 i am currently able to run 16*128 threads. With these 2048 parallel threads i got an occupancy of the GPU of 1/6 only, the GPU is able to run max 12880 threads.

With some work on the registers use i could double the running threads, i guess more is not possible.

Other GPUs have a better registers/thread ratio. The AMD 69xx series for example offers 256 KB private memory and 32 KB local memory.

--
Srdja

PS: did i mention that i am looking for sponsors? :-)

GTS450 with 2 GB available

2011-06-15T22:20:00.004+02:00

Just saw that there are entry level GPUs with 2 GB RAM available, GTS450 for < 100 Euro.

With 2 GB RAM the limiting factor would only be the register sizes of private and local memory, which are a bit more relaxed on the Fermi architecture,

GTS450:
Shaders: 196
SIMD Units: 4
GPU Clock: 783 MHz
Shader Clock: 1566 MHz
GFLOP/s SP: 601.34 (max. single point precision)
GFLOP/s DP: 75 (max. double point precision)
Memory Interface: 128 bit
Memory Clock: 3608 MHz (GDDR3)
Memory Bandwidth: 57.73 GB/s
private memory/SIMD Unit: 128 KB
local memory/SIMD Unit: 48 KB
Threads/SIMD Unit: 1536

Memory limits max amount of threads

2011-06-15T18:19:00.004+02:00

1) private and shared memory limits the max amount of threads by register size for kernel computation,

2) but global memory limits too :(

In OpenCL currently only 1/4 of physical GPU RAM is allocateable in one block, means 128 MB from 512...that is bad....with my actual design i am only able to use 2048 instead of 12288 possible threads.

CL_DEVICE_MAX_MEM_ALLOC_SIZE: 128 MByte
CL_DEVICE_GLOBAL_MEM_SIZE: 511 MByte

--
Srdja

Registers on GTS250

2011-06-14T16:14:00.004+02:00

Running actual into problems with the size of private memory on a Nvidia GTS250.

GTS250 has 16 SIMD Units each got 8K Registers, means 32 KB of private memory and is capable of running 24 Warps a 32 Threads. Means i have to run at least 768 threads per SIMD Unit to get a occupancy of 100%, means i got only 42 Bytes for kernel computation :(

Same with shared memory, which is 16 KB per SIMD Unit, 16384 Bytes / 768 Threads = 21,333333333 Bytes/Thread.

--
Srdja

New and maybe last approach

2011-06-13T15:59:00.002+02:00

To finish this project in a clean way i will code all my ideas straight down in OpenCL,
even if the performance tests show up that it will end in a desaster ;)

Always when...

2011-06-13T04:47:00.002+02:00

i give up i get the best ideas....will be back soon.

--
Srdja

Some reasons against chess on GPUs

2011-06-08T23:34:00.003+02:00

GPUs are "SIMT" devices, Single Instruction Mutlible Thread
A GPU consists of tens of SIMD Units, inside of these SIMD Units every process executes the same code, so branches and while loops are not welcome. Therefore a Movegenerator has to be designed SIMD friendly, because every process has to wait for the others to finish.

Memory
Too little, fast private and local memory. Global Memory (RAM) is slow. A GPU-chess program has to be designed that every process which works on an board can hold the board presentation in private or local memory.

Not that fast
GPUs have more "raw" computation power than CPUs but also a lot of restrictions.
Todays High-End GPUs have about 600 GFLOP in DP, a 4 Core CPU maybe 50 GFLOP.
The standard MinMax algorithm is boosted on CPUs with alpha-beta pruning by a magnitude. And alpha-beta-pruning can be boosted again by a magnitude with good move ordering.
So without ab-pruning even the fastet GPU will loose the game against a CPU.

No Recursion, no communication, no sync
How to build an Master-Slave relationship between Threads in an parallel alpha-beta algorithm for distributing work with these limitations?

--
Srdja

Summary II: GPUs and Chess

2011-02-03T20:39:00.004+01:00

After almost one year GPU-Chess it is time for a second summary:

GPU as Coprocessor
Because of the communication latency between Host and GPU a no go,
maybe AMDs and Intels new APUs are more decent for this but afaik there are not many stream cores on die.

One Thread one Board Idea
Is a stopper, over last generations of GPUs the local/private memory by thread was almost constant. Where "memory by thread" means a constellation of threads which is able to use the computation power of an GPU. In Numbers: 32 to 512 Bytes by thread.

Multi-Thread one Board
Because of local memory limits it is neccassary to couple threads together and use the coupled memory for computation.

Board Presentation
Because of the GPU-architecure a 16*4*32 Bit optimized Board Presentation ("Quarter BitBoards") would perform best.

Move Generation
It is questionable if the hole chess move generation including checks for legality perform well on such a SIMD device.
My tests with dummy data showed that a clear BitBoard Design with precalculated Hashtables ("Magic BitBoards") performs better then nested loops. The point is if the Hashtables fit in fast local/private memory or has to be fetched from slow global memory....

Parallel Search Algorithm
For the most efficient parallel game tree search algoroithms is communication between threads/tasks needed. But OpenCL doesnt offer such built in communication, it has to be solved manually with slow global memory.

Outlook
I will give the "Quarter BitBoard" idea a try and will see....

Nvidia GTS250 / G92b

2011-01-29T22:30:00.008+01:00

Comparison of entry level Nvidia GPUs, nice cards for starting GPU programming.

GTS250:
Shaders: 128
SIMD Units: 16
GPU Clock: 738 MHz
Shader Clock: 1836 MHz
GFLOP/s SP: 705 (max. single point precision)
GFLOP/s DP: 88 (max. double point precision)
Memory Interface: 256 bit
Memory Clock: 2200 MHz (GDDR3)
Memory Bandwidth: 70.4 GB/s
constant memory size: 64 KB
private memory/SIMD Unit: 32 KB
local memory/SIMD Unit: 16 KB

8800 GT:
Shaders: 112
SIMD Units: 14
GPU Clock: 600 MHz
Shader Clock: 1500 MHz
GFLOP/s SP: 504 (max. single point precision)
GFLOP/s DP: 63 (max. double point precision)
Memory Interface: 256 bit
Memory Clock: 1800 MHz (GDDR3)
Memory Bandwidth: 57.6 GB/s
constant memory size: 64 KB
private memory/SIMD Unit: 32 KB
local memory/SIMD Unit: 16 KB

One thread one board

2011-01-29T11:01:00.002+01:00

The "one thread one board" idea proparly will never fit on GPUs. Because of the amount of threads needed to use the full computation power of the device the memory by thread is very limited.
Therefore it may be neccessary to couple some thread to work on one board....

Design thoughts for AMDs Cayman

2011-01-19T08:10:00.014+01:00

The 64 bit performance on Cayman is 1/4 of 32 bit performance. And memory reads/writes are organised in 128 bit a 4 * 32 bit. So a 32 bit board presentation should perform better.

Usefull OpenCL Setup could be:
8 simultan workgroups * 16 wide SIMD * 4 Wavefronts * 24 SIMD Units => 12288 total work-items

Possible Board Presentations

Quad-BitBoards, 256 bit
Quadbitbards with 4*64 bit Board presentation and 64 work-items, one work group, working simultan on one board. Shared memory could hold precalculated attack and Kindegarten-Bitboard tables for move generation.
Pro; 64 work-items working on one board -> more registers for use.
Con: 64 work-items, each for one square, a lot of unused computing power.

Classic BitBoards. 2*6*64 bit
Classis BitBoards with 2*6*64 bit with 6 work-items working on the same board.
Con: 6 work-items coupled don't have enough private memory for deep calculations.

32 bit
Don't have a clue how to organize the board effective in 32 bit parts and to use less than 3/4 more arithmetic operations compared to bitboards for move generation.
Maybe a 0x88 design with some modifications in move generation?

Memory Latency in AMDs Cayman series

2011-01-19T07:24:00.005+01:00

private memory
The ALU needs 4 cycles to fetch two 32 bit operands from register file (256KB per SIMD).

shared memory
The LDS - Local Data Share (shared memory) has 32 KB per SIMD Unit. This LDS can be shared by an entire work-group and needs one ALU operation (4 cycles) for read access of two 32 bit values and one ALU operation and one memory operation for writes.

Compared to the non OpenCL specific GDS - Global Data Share with 24 cycles latency and a total of 64KB it is fast.

Another programmer giving GPU Chess a try?

2011-01-13T15:41:00.007+01:00

Hey Vincent, welcome to the party? :)

forums.amd.com

AMD HD 69xx

2011-01-12T19:54:00.014+01:00

New Cayman cards from AMD:

AMD 6970
Shaders: 1536
SIMD Units: 24
GPU Clock: 880 MHz
Shader Clock: 880 MHz
GFLOP/s SP: 2700 (max. single point precision)
GFLOP/s DP: 675 (max. double point precision)
Memory Interface: 256 bit
Memory Clock: 1375 MHz (GDDR5)
Memory Bandwidth: 176 GB/s
Registers/SIMD: 256KB (private memory)
GDS: 64KB (global data share)
LDS: 32KB (shared memory)
VLIW: 4 (previos cypress-model has 5)

As far as i can see there is no increasement of register size compared to Cypress-Architecture (58xx).

Zeta Dva

2011-01-11T18:13:00.003+01:00

i lost my CPU zeta code, hence i will start to code another version:

http://zeta-dva.blogspot.com/

Project canceled

2010-08-04T15:40:00.000+02:00

choose life and not computer chess ;)

Memory Latency

2010-07-05T20:29:00.002+02:00

Not only global memory has latency that has to be considered, but also L1 (private) and L2 (local/shared) and constant memory has latency.

NV papers say 24 clocks for registers (should be L1 memory) and ATI papers say 24 clocks for Global Data Share (should be constant memory).

So i have to reconsider the decision to use Hash-Tables and Attack-Tables which resist in constant memory. It could be faster just to compute the moves...

The future is fusion?

2010-07-01T12:50:00.003+02:00

According to some news-sites AMD is going to launch its first APU, Application Processing Unit, in 2010/2011 called Fusion. There will be a quad-core version but how many stream cores will fit on the die?

With the GPU-Cores on die there is not much latency between GPU and CPU so a Chess Engine could use the CPU in a classic way and the GPU-Cores as a Coprocessor for special tasks like move generation or evaluation in parallel.

We will see if AMDs APU, Fusion, prevails against the common CPU-GPU concept...

Zeta 0.8.3.x Quad BitBoard design

2010-06-30T17:39:00.010+02:00

The new design of the move generator will use Quad-BitBoards, 4*64 Bit = 32 Bytes. I am going to mix precalculated Attack Tables for Pawns, Knights and King, and a Kindergarten BitBoard approach for Rooks, Bishops and Queens. Magic BitBoards are a no go because their tables (40KB+800KB) don't fit in constant memory (64KB). Kindergarten BitBoards use 2*4KB Tables afaik. It is still a "one thread one board" architecture.

I will assume a min. of 256 Bytes local memory per thread so i can reach a fix search depth of max. 28 per thread without using slow global memory.

1* 32 Bytes Quad-BitBoard
28 * 4 Bytes move

Because the move generator is interleaved with the upcoming search algorithm i also need some data for the scores:

28 * 2 Bytes alpha score
28 * 2 Bytes beta score

The state of the move generator is stored for each depth in a move with 4 Bytes. So the move generator iterates through all from pieces and throuh all to squares.

If the fix search depth of 28 is reached i plan a fallback to global memory, packing the previous move and score data in global memory and restoring it when the thread is moving back in search tree.

With 256 Bytes of local memory as requirement i could use following OpenCL setup:

NV 8800 GT:
total work size: 896
local work size: 64

ATI 5770:
total work size: 1280
local work size: 64

...this will take some time...

Threads again

2010-06-29T22:14:00.006+02:00

With thanks to Philippe from Cuda Chess i got now a clue how GPU threading works.

The numbers mentioned in an earlier post are the max the device can handle. But every application is different, in memory use or cycles of calculation, so other thread configurations perform better.

Redesign of the move generator

2010-06-27T22:00:00.004+02:00

I thought of using one thread for one board, but with the new numbers in mind i got only about 20 Bytes of memory for each thread...an alternative would be to couple threads working on the same board...

Concurrent threads on GPUs

2010-06-27T21:40:00.005+02:00

Many sources, many different numbers, here some new:

ATI 5870: 31744
5870

8800 GT: 10752
8800 GT

Close to the metal

2010-06-22T16:18:00.017+02:00

A comparison of the Nvidia 8800GT and ATI 5770 computing capabilities:

8800 GT:
Shaders: 112
SIMD Units: 14
GPU Clock: 600 MHz
Shader Clock: 1500 MHz
GFLOP/s SP: 504 (max. single point precision)
GFLOP/s DP: 63 (max. double point precision)
Memory Interface: 256 bit
Memory Clock: 1800 MHz (GDDR3)
Memory Bandwidth: 57.6 GB/s
L1 Memory: ??? 8 KB per SIMD Unit
L2 Memory: ??? 16KB per SIMD Unit

5770:
Shaders: 800
SIMD Units: 10
GPU Clock: 850 MHz
Shader Clock: 850 MHz
GFLOP/s SP: 1360 (max. single point precision)
GFLOP/s DP: -/- (max. double point precision)
Memory Interface: 128 bit
Memory Clock: 1200 MHz (GDDR5)
Memory Bandwidth: 76.8 GB/s
L1 Memory: 8KB per SIMD Unit
L2 Memory: 32KB per SIMD Unit

The 8800 GT is a little bit outdated (not sure if they are still available) but still a good shot for GPU-Computing and the ATI 5770 is more a midrange card. So this is not a comparison of equivalent GPUs or of NV and ATI. But it will show some differences in GPU Computing which have to be considered.

ATI 5770
The 5770 needs 2 cycles to compute a Warp/Wavefront with 16 threads. This means we could run our OpenCL application effectively with 2560 total work-items and a work group size of 256 so we get 128 Bytes of local memory per work-item.

Nvidia 8800 GT
The 88000 GT needs 4 cycles to compute a Warp/Wavefront with 32 threads. This means we could run our OpenCL application effectively with 448 total work-items and a work group size of 32 so we get 512 Bytes of local memory per work-item.

*** Edit 20100625 ***
ATI: 10240 total, 256 local with 32 Bytes
NV: 3584 total, 256 local with 64 Bytes
should be a theoreticaly possible configuration

If someone wishes to design a Chess Engine that is able to run on different GPU architectures effectively then he has to consider that:

1) global work item size can differ
2) local work item size can differ
3) size of memory per work-item can differ
4) Memory Bandwidth/work-item can differ

Zeta 0.8.2.2, 0x88 -> fast move generator

2010-06-22T15:25:00.007+02:00

With the new knowlegde from canada i was able to get closer to the max possible amount of moves generated on my GPU. The generator is now fast enough to feed a search algorithm with moves, "just" have to care about memory limits...

Merci beaucoup Monsieur Cuda Chess

2010-06-22T13:32:00.006+02:00

I am in contact with my french Cuda-Colleague from canada and learned a lot about GPU specs.

From OpenCL view there are just kernels, work-items and work-groups. But the GPU architecture is more sophisticated. Warps/Wavefronts, different cycles for muls and mads, and memory bandwidth/latency limitations.

Thanks!

Visit his blog: Cuda Chess

Global Memory usage

2010-06-17T15:28:00.005+02:00

Wondered why my move generation is slow....here is the anwser:

memory-limits-and-new-developer-generation

My CUDA-colleague has an better eye for hardware limitations.

My hole computations ran with "slow" global Memory because the data just didnt fit in private/local memory!

Summary I: GPUs and Chess

2010-06-15T16:04:00.000+02:00

At first i thought of using the GPU as a Coprocessor to generate moves in parallel or do fast evaluation. But the Host-GPU latency is too high for this approach.

So the next idea was to pack the hole search algorithm on the GPU. This is a huge step and consist in main of these parts

1) Move generation on GPU
Has to be slim and fast to fit for the "little" Processing Elements of the GPU.

2) Evaluation on GPU
s.a.

3) Non-recursive search algorithm
Something like a stack and a while loop is needed to resolve recursion.

But to use the hole power of the GPU there is also a need of parallizing the search algorithm.
This will cause some problems because in OpenCL work-items of a work-group can be synced but not work-items accross other work-groups. So a effective Load-Balancing mechanism is needed to give work to idle Proccesors. Again we need some stack mechanism and loops.

Outlook:
Zetas move generation is still slow compared to CPU-engines but fast enough to do the next step and work on a parallized search algorithm like PVS.

SIMD, SPMD, GPUs and OpenCL

2010-06-15T15:37:00.005+02:00

Here some technical notes:

1) GPU architecture
GPUs consist of a lot of simple Processing Elements. These little processors are coupled to Stream Cores and Stream Cores are coupled to SIMD Units on the GPU.
The ATI 5870 for example has 1600 Processing Elements. One Stream Core has 5 Processing Elements (4 for normal computation) and 16 Stream Cores build one SIMD Unit with a total of 20 of these SIMD Units.

2) SIMD and SPMD on GPUs
Within the Processing Elements of a Stream Core the GPU is working as a SIMD device but every SIMD Unit works autonomous so these SIMD Units work like SPMD.

3) OpenCL
OpenCL language has the terms work-item and work-group. Work-item are threads within a SIMD-Unit, and work-groups are these SIMD-Units. In OpenCL SIMD-Unit means Computing-Unit. And the hole GPU is an Computing-Device.

Zeta 0.8.2.1.3, 0x88 movegen speedup

2010-06-13T18:46:00.000+02:00

10000 moves need now about 1 second to be calculated on one SIMD processor. The GPU i use has ten of those SIMD processors. This is still very slow...

Cant get BitBoards working on GPU

2010-06-13T18:37:00.001+02:00

the magic-hashtables i copied from Stockfish dont work on the GPU...

0x88 meets BitBoards

2010-06-09T13:04:00.000+02:00

Tested the GPU movegeneration with some dummy data to emulate the behavour of an 0x88-BitBoard approach....looks good.

Zeta 0.8.2.1, 0x88, movegen still slow

2010-06-07T16:08:00.000+02:00

One Processor of the GPU needs ~ 100 milliseconds to calculate 20 moves. The same code on the CPU needs less than 5 milliseconds. So my code of move generation is not optimized to fit on SIMD architecture.

...maybe i should mix the 0x88 board presentation with bitboard-precalculated attack tables...

Zeta 0.8.2.1, 0x88 with new design

2010-06-04T22:01:00.001+02:00

Redesigned the 0x88 move generation to fit on SIMD architecture...this is the first time i really believe that the project will hit its goals :)

Next step is to implement an load balancing mechanism like PVS.

SPMD/SIMD on GPUs

2010-06-03T00:50:00.000+02:00

Had to realize that every if-else condition doubled the runtime on the GPU.

I know that this is true for SIMD architecture, but GPU shall be able to act although as SPMD devices where every Proccessing Element has its own instruction counter.

So i hope it is only my "old" hardware which doesnt support SPMD....

##edit 20100603###

its not my hardware...GPUs are more like "SIMD within SPMD"....

Zeta 0.8.2.0, 0x88 -> simple moves on GPU

2010-06-02T18:23:00.000+02:00

I ported the 0x88 move generation (without castling moves) from MicroMax by H.G. Mueller to the GPU.

The MicroMax Code is compact and fast, but i still dont have a clue how to port the castling moves in an efficient matter...

Zeta 0.8.2.0, working on 0x88 on GPU

2010-05-30T14:03:00.000+02:00

After bitboards and 12x10 board presentation i will give the 0x88 array structure a try on the GPU.

... i redesigned the 12x10 array move generation but its still too slow on the GPU.

Zeta 0.8.1.0, 12x10 on GPU

2010-05-27T00:55:00.001+02:00

i implemented an 12x10 array move generation on the gpu, as i thought this approach is much faster than bitboards becouse 1) less memory operations are used and 2) GPUs have more power on single precision operations.

Zeta, 0.8.0.6, poor bitboard performance

2010-05-26T20:37:00.000+02:00

i implemented the hole bitboard-move-generation on the GPU. one process needs about 2 seconds to calculate the first 20 moves only. must be some global memory issuses.

Zeta 0.8.0.6, Pawns are movin :)

2010-05-25T22:28:00.000+02:00

yeha,

pawn moves are now generated in OpenCL on the GPU.

Communication latency between Host and GPU is high (~ 50 ms), but i hope the calculation speedup by the GPU will balance this out.

Implementing PV-Split

2010-05-24T16:26:00.000+02:00

Currently i am working on an implementaion of the Principal Variation Splitting algorithm in OpenCL.

PVS:
The root process goes the left tree down to the max search depth. Then backs one ply up and gives the remaining boards to other processing elements for calculation. When all processors finished their calculation the root process backs again one ply up and gives work to processors. This procedure is repeated until depth 0, the root, is reached.

Pro:
Easy to implement.

Contra:
1) We got on an average of 40 Boards by depth. This means if there are more than 40 processing elements not all will get busy.

2) When one proccesing element finishes its calculation it goes idle, waitung for the others to finish.

Maybe the contras can be reduced with some extensions to the original PVS...

No multi-GPU support

2010-05-20T14:12:00.000+02:00

To keep things simple i decided to perform the chess calculations at the beginning only on one GPU/OpenCL Device.

PVS and DTS

2010-05-20T13:58:00.001+02:00

Had some time to read about PVS and DTS parallel search algorithms.

DTS (Dynamic Tree Splitting) has better scalability but is difficult to implement.
PVS (Principal Variation Splitting) scalability depends on the amount of moves, i read about a max speedup of 5x in Chess.

Nvidia Fermi, GTX480 specs out

2010-03-27T11:45:00.001+01:00

Specifications of the new Fermi cards by Nvidia are out.

*** Edit 20100521 ***
just read that the nvidia GeForce GTX Cards have only 1/8 DP of SP and Nvidia Tesla series has 1/2.

GTX480:
Shader Units: 480 Shader
Shader Clock: 1401 MHz
GFlops SP: 1.344,96
GFlops DP: 168,12
Max Power: >250 W

Tesla M2050/M2070:
Shader Units: 448 Shader
Shader Clock: 1.150 MHz
GFlops SP: 1.030 Gflops
GFlops DP: 515 Gflops
Max Power: 247W TDP

For comparison:
ATI 5870:
Shader Units: 1600 Shader
Shader Clock: 850 MHz
GFlops SP: 2.720
GFlops DP: 544
Max Power: 188 W

Summer pause

2010-03-23T20:27:00.000+01:00

project pauses until middle of july.

Non-Recursive AlphaBeta

2010-03-23T19:25:00.001+01:00

Figured it out how to put Alpha Beta in a while-loop. Next step will be to code all the C-functions like Move-Generation and Evaluation in OpenCL and to implement an effective Load-Balancing mechanism...

NegaMax on SIMD

2010-03-18T20:02:00.000+01:00

Found a paper from Holger Hopp and Peter Sanders describing an YBWC-AlphaBeta implementation on SIMD devices. They built a stack mechanism for non-recursive alphabeta, but they although use communication between threads for their master/slave concept.

OpenCL Negamax search

2010-03-13T22:37:00.000+01:00

Is hard to implement.
In OpenCL work-groups can not be synced with other work-groups during the calculation, only work-items as a member of a work-group can be synced. So if one work-group computes the moves of one board, there is no way to tell unused work-groups on the fly to take these generated moves and compute further.

Zeta, GPU version 0.8.0.2

2010-03-12T17:48:00.001+01:00

thinking about parallizing the threads...
maybe one board by compting unit of the OpenCL device and 6x64 threads for move generation?

Move Generation on GPU

2010-03-09T16:14:00.000+01:00

I managed to generate some moves on the GPU, but the communication delay between HOST and GPU makes this aproach too slow for an Chess Engine. The point is to package the hole Search Algorithm on the GPU, not only some parts like move generation.

Zeta, GPU version 0.8.0.1

2010-03-07T21:26:00.001+01:00

CPU Version is running, so i start coding in OpenCl a GPU-Version...

Zeta, CPU version 0.7.0.4

2010-03-06T16:27:00.000+01:00

Move generation is complete. Looks a lot of faster than version 0.6.0.6. But move ordering is still buggy.

Zeta, CPU version 0.7.0.3

2010-03-01T16:58:00.000+01:00

General Movegeneration and checkmate funtions are ready.
castling, en passant and pawn promotion are missing...

Zeta, CPU version 0.7.0.2

2010-02-27T21:10:00.000+01:00

Sliders are on their ways (thanx to Stockfish for the hashtables!), thinking know about an effective method for checking check and checkmate...ahhh 12x10 array was kindergarten...

Zeta, CPU version 0.7.0.1

2010-02-27T09:32:00.001+01:00

The CPU BitBoard Edition of Zeta is now able to genereate Pawn, Knight and King moves, the more advanced Magic BitBoard technic for sliding pieces will follow....

Zeta CPU version 0.7.0.1

2010-02-25T18:06:00.000+01:00

Becouse of speed issueses i am going to change the board presentation from 12x10 array to Magic BitBoards.

I hope i will finish the CPU Version soon, so i can focus on developing a search algorithm for GPUs.