Smp concepts
Posted: Sun Jun 01, 2014 9:54 am
Hi everybody,
a long time has passed and now, and i want to spend some time on chess programming again.
Not sure yet, where to take the time from, but i guess with less sleep there will be a way .
It is high time to solve my SMP puzzle, so i do have some questions about SMP program flow concerning
different approaches i got to work. In this thread i don't want to ask to many questions about implementation
details, but about basics concepts i figured out by myself. So, i am not sure which way to go because
of less experience in this area. Here i go, maybe you like to comment on the ideas or even add some others.
Some parameters i like to know more about in context of the following approaches:
* SPLIT_DEPTH
* MAX_THREADS_PER_SPLITPOINT
* MAX_SPLITPOINTS
* FORWARD_SPLITTING
* SHARED_DATA ( TRANS_TABLE )
* SPLITPOINT CHAINS
* SPLITPOINT PRIORITIZATION
* SYNCHRON vs. ASYNCHRON MULTITHREADING
Approach 1: Polling Threads ( Ants )
=========================================
This was the most intuitive approach to me. Alls helpers loop, while the engine
is in search mode ( burning cycles ), and are checking some kind of shared split point stack.
If the conditions to join a split point are fulfilled, a thread works as long as there is work
to do on this split point. The eye catchers have been.
- a thread can join anytime anywhere, as long there are open split points ( no idle time until it is signaled )
- Even a helping master can join not only a slave but elsewhere. Joining a slave of the splitpoint is optional.
Well, here the question is, if to use the option as requirement, so to finish the current split point as soon as possible.
- MAX_THREADS_PER_SPLITPOINT is harder to control, because if a splitpoint is finished already by less than MAX_THREADS_PER_SPLITPOINT,
it has to be avoided that another thread joins although the synchronisation condition has been occured.
( eg: 2 threads solved the splitpoint. The master waits for its slave. Now, the split point is left while another would like to join.
This is not a big problem but different to other approches where master books its slaves )
- the controls are done over the split point objects. Threads don't care about the states of other threads.
Now, if someone has experience with this approach, negative or positive, i like to hear about it, especially regarding
the points listed ahead.
Approach 2: Staking Master Concept (SMC)
=========================================
I guess this is the most common used approach. When doing a split, the master checks which thread is available,
then it is staked by the master to the splitpoint. The eye catchers have been.
- the helpers have to be setup and signaled / state-changed by the master.
- Splits have to be avoided when no thread is available. Here the idea of late joins may improve the situation.
Meaning that after a thread returns from a sub task, there will be another check for free threads that can join.
- Threads can stay in idle state,
Approach 3: Asynchron Anytime Anywhere (AAA)
==============================================
This approach has not been tested by me until now. It is a modification of Ants, where the idea is
that anytime anywhere means, that a master can exit immediately the splitpoint. The only thing which
must be changed would be, that the path to a splitpoint must be outplayed by a slave ( at least ), so
the recursion stack is rebuilt. In that case any thread can exit anytime and join anytime anywhere or do whatever it likes.
It is like assigning the current tree state where the thread dependencies are dissolved.
- copy the complete tree state for any splitpoint.
Stressing SMP controls
========================
Doesn't matter where the bottle necks in any approach are, but i guess that with more spanning the tree, the more unimportant
the stress factors are, simply because with limited split points the time a thread is really working gets a higher ratio.
So communication and organization becomes less.
Finally the ahead mentioned catchwords are not explained in detail because i guess within this thread each of it will be
discussed anyway, if not, there is no need to explain it either .
Happy to be back again and curious for replies
Michael
a long time has passed and now, and i want to spend some time on chess programming again.
Not sure yet, where to take the time from, but i guess with less sleep there will be a way .
It is high time to solve my SMP puzzle, so i do have some questions about SMP program flow concerning
different approaches i got to work. In this thread i don't want to ask to many questions about implementation
details, but about basics concepts i figured out by myself. So, i am not sure which way to go because
of less experience in this area. Here i go, maybe you like to comment on the ideas or even add some others.
Some parameters i like to know more about in context of the following approaches:
* SPLIT_DEPTH
* MAX_THREADS_PER_SPLITPOINT
* MAX_SPLITPOINTS
* FORWARD_SPLITTING
* SHARED_DATA ( TRANS_TABLE )
* SPLITPOINT CHAINS
* SPLITPOINT PRIORITIZATION
* SYNCHRON vs. ASYNCHRON MULTITHREADING
Approach 1: Polling Threads ( Ants )
=========================================
This was the most intuitive approach to me. Alls helpers loop, while the engine
is in search mode ( burning cycles ), and are checking some kind of shared split point stack.
If the conditions to join a split point are fulfilled, a thread works as long as there is work
to do on this split point. The eye catchers have been.
- a thread can join anytime anywhere, as long there are open split points ( no idle time until it is signaled )
- Even a helping master can join not only a slave but elsewhere. Joining a slave of the splitpoint is optional.
Well, here the question is, if to use the option as requirement, so to finish the current split point as soon as possible.
- MAX_THREADS_PER_SPLITPOINT is harder to control, because if a splitpoint is finished already by less than MAX_THREADS_PER_SPLITPOINT,
it has to be avoided that another thread joins although the synchronisation condition has been occured.
( eg: 2 threads solved the splitpoint. The master waits for its slave. Now, the split point is left while another would like to join.
This is not a big problem but different to other approches where master books its slaves )
- the controls are done over the split point objects. Threads don't care about the states of other threads.
Now, if someone has experience with this approach, negative or positive, i like to hear about it, especially regarding
the points listed ahead.
Approach 2: Staking Master Concept (SMC)
=========================================
I guess this is the most common used approach. When doing a split, the master checks which thread is available,
then it is staked by the master to the splitpoint. The eye catchers have been.
- the helpers have to be setup and signaled / state-changed by the master.
- Splits have to be avoided when no thread is available. Here the idea of late joins may improve the situation.
Meaning that after a thread returns from a sub task, there will be another check for free threads that can join.
- Threads can stay in idle state,
Approach 3: Asynchron Anytime Anywhere (AAA)
==============================================
This approach has not been tested by me until now. It is a modification of Ants, where the idea is
that anytime anywhere means, that a master can exit immediately the splitpoint. The only thing which
must be changed would be, that the path to a splitpoint must be outplayed by a slave ( at least ), so
the recursion stack is rebuilt. In that case any thread can exit anytime and join anytime anywhere or do whatever it likes.
It is like assigning the current tree state where the thread dependencies are dissolved.
- copy the complete tree state for any splitpoint.
Stressing SMP controls
========================
Doesn't matter where the bottle necks in any approach are, but i guess that with more spanning the tree, the more unimportant
the stress factors are, simply because with limited split points the time a thread is really working gets a higher ratio.
So communication and organization becomes less.
Finally the ahead mentioned catchwords are not explained in detail because i guess within this thread each of it will be
discussed anyway, if not, there is no need to explain it either .
Happy to be back again and curious for replies
Michael