Implementing parallel search

[matthewlai]

Hello!

Question about parallel search - how are people implementing it?

I read up on YBW, and it makes sense conceptually, but I can't seem to come up with a way to implement it efficiently.

I understand that in search(), we first search the first node serially, before dividing up the remaining nodes.

The way I am thinking about doing it is, have the master thread look for an idle thread from a thread pool, and have them each take one of the remaining nodes.

The problem is, what should the master do, then? Should it also pick a node and start searching? If not, it looks like it would be difficult to manage number of actively-searching threads, and there will be many sleeping threads. If so, what if one of the children it spawned finishes early, and needs more work to do?

Thanks!

[ZirconiumX]

Hello!

Question about parallel search - how are people implementing it?

I read up on YBW, and it makes sense conceptually, but I can't seem to come up with a way to implement it efficiently.

I understand that in search(), we first search the first node serially, before dividing up the remaining nodes.

The way I am thinking about doing it is, have the master thread look for an idle thread from a thread pool, and have them each take one of the remaining nodes.

The problem is, what should the master do, then? Should it also pick a node and start searching? If not, it looks like it would be difficult to manage number of actively-searching threads, and there will be many sleeping threads. If so, what if one of the children it spawned finishes early, and needs more work to do?

Thanks!

From what I know, the master thread searching too is a standard implementation.

Matthew:out

[matthewlai]

Hello!

Question about parallel search - how are people implementing it?

I read up on YBW, and it makes sense conceptually, but I can't seem to come up with a way to implement it efficiently.

I understand that in search(), we first search the first node serially, before dividing up the remaining nodes.

The way I am thinking about doing it is, have the master thread look for an idle thread from a thread pool, and have them each take one of the remaining nodes.

The problem is, what should the master do, then? Should it also pick a node and start searching? If not, it looks like it would be difficult to manage number of actively-searching threads, and there will be many sleeping threads. If so, what if one of the children it spawned finishes early, and needs more work to do?

Thanks!

From what I know, the master thread searching too is a standard implementation.

Matthew:out

Ah I see. I guess in that case the threads must be self-organizing, through some kind of data structure without an active master.

[ymatioun]

I also found this confusing when i was implementing parallel search.
So the way i did it was several slave threads (4 for 4-core CPU), waiting on an event. When master thread reaches split point, it puts position data into global variable, triggers slave event and goes to sleep. Slaves pick-up the solve, and when they are done, wake up master and go to sleep themselves.

Youri.

[jdart]

Feel free to look at my implementation, which is doing what you describe:

https://github.com/jdart1/arasan-chess/tree/master/src

see Search::searchSMP and the ThreadPool class (threadp.h/.cpp).

Implementing the "helpful master" concept will increase performance but it is not a huge gain, so if you want you can defer implementing this.

--Jon

[syzygy]

If so, what if one of the children it spawned finishes early, and needs more work to do?

Usually slave threads pick a (next) move on their own. You obviously need to do some locking to make sure that two slaves do not pick the same move.

[syzygy]

Implementing the "helpful master" concept will increase performance but it is not a huge gain, so if you want you can defer implementing this.

I don't think the OP is there, yet.

The way I understand the question is: should the master be one of the search threads that search moves at the split node, or should it only somehow loop around waiting for available slaves in order to serve them with moves.

[matthewlai]

I also found this confusing when i was implementing parallel search.
So the way i did it was several slave threads (4 for 4-core CPU), waiting on an event. When master thread reaches split point, it puts position data into global variable, triggers slave event and goes to sleep. Slaves pick-up the solve, and when they are done, wake up master and go to sleep themselves.

Youri.

That sounds pretty simple, but if a slave splits again and becomes a master, aren't there only 3 threads searching now?

It's possible to spawn another thread in that case (6 threads total, 2 sleeping), but I am afraid it will end up with hundreds of sleeping threads which would kill scheduler performance.

[ymatioun]

I only allow splits by master thread. So when a slave thread has no more work, but some slaves are still working, CPU utilization drops, from 4 running threads down to 3, 2, then 1. This is certainly suboptimal, but very easy to implement.

Youri.

[matthewlai]

I only allow splits by master thread. So when a slave thread has no more work, but some slaves are still working, CPU utilization drops, from 4 running threads down to 3, 2, then 1. This is certainly suboptimal, but very easy to implement.

Youri.

Ah! I see.

It does sound very easy.

Do you know what average CPU utilization looks like over say a typical game?