Hardware expert thoughts re EGTB generation

[vb4]

Since I have a very general understanding about hardware design I was hoping one of the experts could answer this. When generating EGTB's to date everyone uses software and I have never seen any thoughts about why not use hardware such as FPGA's or VLSI's technology. Intuitively it seems that to be a better fit and offers much more spped then software. Curious to read some of you hardware experts thoughts.

Thanks,

Les

[hgm]

This is because EGTB generation is a storage problem, and the technologies you mention do not offer storage. If you generate EGTBs on hard disk, you are waiting for disk I/O all the time. When you have enough RAM to generate them without using the disk, your CPU is idle 99% of the time, waiting for cache misses to be satisfied.

So if you want to use special hardware, you should use systems with a large memory bandwidth (many parallel banks).

[Edmund]

Probably the main difficulties still remain, like memory management. Furthermore I think that current algorithms are far from perfect and should be optimized first.

[hgm]

Well, I have a quite efficient algorithm now for in-memory generation, which should be able to generate at only one DRAM access per cache line per cycle. So for a 6-men Pawnless end-game requiring 8GB of memory, on my 2.4GHz Core 2 Duo, which takes 137 clocks for a sequential dirty (64-byte) cache-line fill, that would be about 0.9 ns/byte * 8GB = 7.2 sec per generation cycle. So if the end-game would have max DTC = 50, it would be generated in ~360 sec by such an algorithm.

[vb4]

Thanks for your thoughts. Your generator that you talked about sounds pretty impressive. Has that been used in generating any of the 6 piece EGTB's? or is this something you finished pretty recently? WHat are your plans for your generator going forward?

Thanks,

Les

[hgm]

Has that been used in generating any of the 6 piece EGTB's?

No it hasn't, and I am still working on implementing it. So the number I gave is just an estimate based on the memory bandwidth of my computer, which I did measure.

I have only 2GB of memory in my PC, though, so I couldn't generate any 6-men EGTBs in RAM anyway. If they are Pawnles, that is. As soon as they have Pawns, it becomes much easier, as the tablebase factorises into P-slices that would only require 8 times fewer memory for the first Pawn, and 64 times less for any subsequent Pawn.

My final aim is to generate EGTBs with 4 or 5 Pieces and 3-5 Pawns 'on the fly' by my engine when it becomes clear that they are needed, in ponder time. I expect this to be very helpful in endgames like KRPPKRP.

[Edmund]

Well, I have a quite efficient algorithm now for in-memory generation, which should be able to generate at only one DRAM access per cache line per cycle. So for a 6-men Pawnless end-game requiring 8GB of memory, on my 2.4GHz Core 2 Duo, which takes 137 clocks for a sequential dirty (64-byte) cache-line fill, that would be about 0.9 ns/byte * 8GB = 7.2 sec per generation cycle. So if the end-game would have max DTC = 50, it would be generated in ~360 sec by such an algorithm.

Fair enough that sounds quite promising, hope to see a prototype in the near future.