Parallel search, Where to start?

[Chang]

Hi,

I've been trying to implement parallel search(multithread), unfortunately, I cannot imagine how to do it together with handling hashtable and PV lines. Are there any simple source codes or recommended reading papers on this?

Any help is appreciated.

Teerapong

[sje]

For the main transposition table, I add a vector of 256 spinlocks each of which guard a piece of the main table. This allows safe and efficient multithreaded sharing in a portable fashion and independently of the structure of a transposition table element.

[sje]

A PV is grown from the bottom up and is set whenever a ply zero (root) move is established as the best root move so far. If more than one thread is operating at ply zero, then the new-best-root-move routine needs a mutex to guard the compare and replace operation which assigns a new PV.

[bob]

Hi,

I've been trying to implement parallel search(multithread), unfortunately, I cannot imagine how to do it together with handling hashtable and PV lines. Are there any simple source codes or recommended reading papers on this?

Any help is appreciated.

Teerapong

There's a paper on the Cray Blitz DTS algorithm on the cis.uab.edu web page under faculty/ my home page link... It might be a bit more complex than what you want to read to get started, however...

[Steve Maughan]

Take a look at Viper Chess by Tord:

http://www.glaurungchess.com/viper/

It's less than 5k lines and includes parallel code.

Hope this helps,

Steve

[uaf]

Parallel Alpha-Beta Search on Shared Memory Multiprocessors by Valavan Manohararajah

For the hash table, you could take a look at Dr. Hyatt's xoring method for lockless hashing: http://www.cis.uab.edu/hyatt/hashing.html

[bhlangonijr]

Hi,

I've been trying to implement parallel search(multithread), unfortunately, I cannot imagine how to do it together with handling hashtable and PV lines. Are there any simple source codes or recommended reading papers on this?

Any help is appreciated.

Teerapong

Hi,

This is a very helpful thread covering the topic:
http://www.talkchess.com/forum/viewtopi ... ce911e37dc

The basics on chessprogramming wiki:
http://chessprogramming.wikispaces.com/Parallel+Search

I have implemented a sort of Younger Brothers Wait approach in my open source engine. It took only a few lines of code to get it done. Although it was VERY time-consuming rewriting and testing the code to do it right.
http://sourceforge.net/projects/redqueenchess/

PS: I would suggest you not going for SMP if you still haven't a stable and working chess engine.