What is the meaning of "minimum split depth"

[benstoker]

What exactly does it effect and how does it relate to the # of cores? Reference: stockfish

[bob]

What exactly does it effect and how does it relate to the # of cores? Reference: stockfish

Probably the idea came from Crafty. The basic idea is that you don't want to split too near the q-search, because the resulting sub-trees are very small, and the effort to do a split can exceed the effort required to do the entire search.

This paramater has two effects that are diametrically opposed.

(1) as it is made larger, you do fewer splits, and incur less split overhead. And by pushing the splits back closer to the root, you also have a pretty good chance of choosing a good split point since move ordering is more accurate nearer to the root. But you also increase the amount of time when threads have no work to do, waiting for some search to back up enough so that it can split after it satisfies this condition. NPS will drop. But time to depth will drop too. For a while. As you make this larger and larger, NPS will continue to drop, and time to depth will start to rise. Obvious boundary condition is to set this to infinity and you never do a split at all.

(2) as this value is reduced, you split near to the frontier where you cross over into the q-search. You end up with less processor idle time, since you don't have to wait as long to split, but overhead goes up along with the increase in NPS and the time-to-depth number can start to rise.

This is something that needs tuning for each SMP machine you run on, in the case of crafty. In my code, there are other parameters (such as minimum thread group which limits how many processors can work together at one split point) and such.

[michiguel]

What exactly does it effect and how does it relate to the # of cores? Reference: stockfish

Probably the idea came from Crafty.

I think it is more likely it came from Glaurung.

Miguel

The basic idea is that you don't want to split too near the q-search, because the resulting sub-trees are very small, and the effort to do a split can exceed the effort required to do the entire search.

This paramater has two effects that are diametrically opposed.

(1) as it is made larger, you do fewer splits, and incur less split overhead. And by pushing the splits back closer to the root, you also have a pretty good chance of choosing a good split point since move ordering is more accurate nearer to the root. But you also increase the amount of time when threads have no work to do, waiting for some search to back up enough so that it can split after it satisfies this condition. NPS will drop. But time to depth will drop too. For a while. As you make this larger and larger, NPS will continue to drop, and time to depth will start to rise. Obvious boundary condition is to set this to infinity and you never do a split at all.

(2) as this value is reduced, you split near to the frontier where you cross over into the q-search. You end up with less processor idle time, since you don't have to wait as long to split, but overhead goes up along with the increase in NPS and the time-to-depth number can start to rise.

This is something that needs tuning for each SMP machine you run on, in the case of crafty. In my code, there are other parameters (such as minimum thread group which limits how many processors can work together at one split point) and such.

[Milos]

I think it is more likely it came from Glaurung.

It came from Bob or even Marsland in time when Tord was not even a teenager...

[Gian-Carlo Pascutto]

I think it is more likely it came from Glaurung.

It came from Bob or even Marsland in time when Tord was not even a teenager...

For once Bob will claim "we did this in the 70's" and I'll actually agree.

[michiguel]

I think it is more likely it came from Glaurung.

It came from Bob or even Marsland in time when Tord was not even a teenager...

For once Bob will claim "we did this in the 70's" and I'll actually agree.

Yes, It must have come from Bob, I know. Not from Crafty

Miguel
PS: Anyway, isn't this an obvious concept? not doing something expensive at the tips?

[bob]

What exactly does it effect and how does it relate to the # of cores? Reference: stockfish

Probably the idea came from Crafty.

I think it is more likely it came from Glaurung.

And likely _that_ came from Crafty. This "idea" has been used since 1996-1997 when Crafty first started to use parallel search. Nothing new as it was also used in Cray Blitz in 1984.

Miguel

The basic idea is that you don't want to split too near the q-search, because the resulting sub-trees are very small, and the effort to do a split can exceed the effort required to do the entire search.

This paramater has two effects that are diametrically opposed.

(1) as it is made larger, you do fewer splits, and incur less split overhead. And by pushing the splits back closer to the root, you also have a pretty good chance of choosing a good split point since move ordering is more accurate nearer to the root. But you also increase the amount of time when threads have no work to do, waiting for some search to back up enough so that it can split after it satisfies this condition. NPS will drop. But time to depth will drop too. For a while. As you make this larger and larger, NPS will continue to drop, and time to depth will start to rise. Obvious boundary condition is to set this to infinity and you never do a split at all.

(2) as this value is reduced, you split near to the frontier where you cross over into the q-search. You end up with less processor idle time, since you don't have to wait as long to split, but overhead goes up along with the increase in NPS and the time-to-depth number can start to rise.

This is something that needs tuning for each SMP machine you run on, in the case of crafty. In my code, there are other parameters (such as minimum thread group which limits how many processors can work together at one split point) and such.

[bob]

I think it is more likely it came from Glaurung.

It came from Bob or even Marsland in time when Tord was not even a teenager...

For once Bob will claim "we did this in the 70's" and I'll actually agree.

Not quite. But we did do it in 1984 when we did the first "real" parallel search in Cray Blitz. 1983 was a hack where we only split at the root, having only 2 weeks from the time Cray said "we have a 2 cpu machine you can use in New York" until the tournament started.

[bob]

I think it is more likely it came from Glaurung.

It came from Bob or even Marsland in time when Tord was not even a teenager...

For once Bob will claim "we did this in the 70's" and I'll actually agree.

Yes, It must have come from Bob, I know. Not from Crafty

Miguel
PS: Anyway, isn't this an obvious concept? not doing something expensive at the tips?

Depends on the architecture. In Cray Blitz, until we hit the C90/T90 boxes, we used a value of "0" for this as we could split at the tips (or even beyond) quite efficiently thanks to the memory bandwidth of that box. It began to be an issue when we hit 16 cpus, and then 32 on the T90. On the PC, I have used values from 2 to 6 so far. And I think that when we ran on an older 64-node Itanium box we used 8 to 10 (Eugene would have to answer that, it was his box, I just suggested playing with the value). Splitting was pretty expensive on that machine as it was a "poor NUMA" box.

[benstoker]

What exactly does it effect and how does it relate to the # of cores? Reference: stockfish

Probably the idea came from Crafty. The basic idea is that you don't want to split too near the q-search, because the resulting sub-trees are very small, and the effort to do a split can exceed the effort required to do the entire search.

This paramater has two effects that are diametrically opposed.

(1) as it is made larger, you do fewer splits, and incur less split overhead. And by pushing the splits back closer to the root, you also have a pretty good chance of choosing a good split point since move ordering is more accurate nearer to the root. But you also increase the amount of time when threads have no work to do, waiting for some search to back up enough so that it can split after it satisfies this condition. NPS will drop. But time to depth will drop too. For a while. As you make this larger and larger, NPS will continue to drop, and time to depth will start to rise. Obvious boundary condition is to set this to infinity and you never do a split at all.

(2) as this value is reduced, you split near to the frontier where you cross over into the q-search. You end up with less processor idle time, since you don't have to wait as long to split, but overhead goes up along with the increase in NPS and the time-to-depth number can start to rise.

This is something that needs tuning for each SMP machine you run on, in the case of crafty. In my code, there are other parameters (such as minimum thread group which limits how many processors can work together at one split point) and such.

Can the split point be automatically determined as a function of NPS? Rather than hard coding it in?