Refining the plan

During the last two weeks, I have been thinking about ways to utilize better the GPU in the move generator. There are two problems: divergence and insufficient processor utilization. These problems are opposite in a way. A large number of threads handling different positions produce divergent execution paths, but on the other hand it is difficult to get good processor utilization with a small number of threads. In addition, one has to take into account that more threads use more shared memory, at least in my current plan.

There are basically four kinds of more generators: sliding pieces, pawns, kings, and knights. It seems to me that trying to write a generic move generator for all pieces, in an attempt to avoid divergence, is wasting processor time. For example, knight move generator requires only a simple table look-up. Sliding pieces generator is a little more complicated, requiring masking blocked paths and outputting potentially several destination squares per direction. Pawn moves have different capture and moving directions, and one has to take into account double pawn moves, en passant and promotions. King move generator requires complicated handling of castling (e.g. the king cannot move over a square where it were in check). I have decided to split the move generator in four parts, so I can optimize each part separately. The problem then is that I need lots of positions, so that each move generator has something to do.

I will make an attempt to use 256 positions per thread group (256 threads also). Then there is a chance that there are enough threads for the full utilization of the processors. Each of the four move generators can use 64 threads to handle a different group of positions. Divergence is not a problem when the threads in the same move generator belong to the same wave (or warp in CUDA terminology). If one move generator runs out of work, the threads in the wave can help with another move generator. The worst case scenario is that there are 253 positions for one move generator and only one position for each of the other three generators. Then the three generators with only one position waste 63 threads each, while the one with the most threads must run four times, if the others finish too late to help it. I think this is quite rare, but I still have to think about something clever to avoid idle threads.

Shared memory usage will obviously be one on the major limiting factors. With 256 positions to store, we cannot afford 8 bitboards, because that would take 16 kB, which is all of our budget for the shared memory. I think the best solution would be using 4 bitboards only (in total 8 kB). As I explained in an earlier post, it is possible to pack the flag bits in the 4 bitboards. However, because the packing and unpacking is computationally expensive, I came up with a plan, where the flags bits are not stored in the positions. They have to be stored in the move data structures anyway, because one has to be able to undo a move and restore the flag bits. So why waste extra space elsewhere. The means that there always has to be a move associated with a position, but that is the case anyway, because we are generating one move at a time, and the move generator takes the previous move as an input parameter.

The rest of the shared memory can be used for storing move stacks and split points. There is no room for full move stacks, because one move takes 8 bytes and 256 moves take 2 kB. I plan to store only three last moves per position (in total 6 kB), and store the rest in the global memory. The three moves are stored in a ring buffer that act as a cache. I hope that latency of the the memory accesses can be hidden by the work that is done in the last 2 ply. I will try to implement this in the next few weeks.