[computer-go] Lockless hash table and other parallel search ideas

[Rémi Coulom]

Olivier Teytaud wrote:
>> Hi,
>>
>> I have got a lockless hash table to work, and I thought I'd share the 
>> results.
>> [...]
>
> Great! For networks of 4-cores, it is not very useful,
> but for highly smp machines it could be great - with your
> grid5000 account, you might run crazystone on a
> 16-core machine and have a very impressive crazyStone.
> Olivier
Thanks for the tip. Here are the results on 9x9:

cores playouts/s
    1    18,025
    2    33,749
    3    48,165
    4    62,268
    5    75,539
    6    87,136
    7   100,840
    8   115,862
   10   134,185
   12   158,491
   14   174,274
   16   205,379 (speedup = 11.4)

and on 19x19:
    1    3,780
    2    7,427
    3   11,009
    4   13,905
    5   17,684
    6   21,265
    7   24,418
    8   27,907
   10   34,710
   12   40,975
   14   48,000
   16   54,193 (speedup = 14.3)

Hardware is 8x Dual Core AMD Opteron 875, 2.2 GHz

I'll run tests to try to figure out how much strength is lost by 
parallelization (ie, what is the winning rate of 10,000 sequential 
playouts vs 1,000 playouts over 10 processors). Hideki ran similar tests 
against GNU Go, and found 25 Elo loss with 4 CPUs. So 54,193 playouts 
per second over 16 CPUs will certainly not perform as well as 54,193 
sequential playouts.

Rémi