Parallel search: is deterministic or not?

[Uri Blass]

Logically the search can be deterministic if we decide that the at stage i of the search all threads gets independent tasks to search N(i) nodes and if part of the threads finished searching N(i) nodes they do nothing until the rest of the threads search N nodes

The threads can use their local hash and local killers and local history
or some global unchanged information that they have from previous search.

After all threads searched N(i) nodes they can share information like hash information to be available to all and the computer can decide about some value N(i+1) when all threads get indepenent tasks to search N(i+1) nodes

The tree is always the same after every stage and if the number of threads is K then the size of the tree is

1)K*N(1) after stage 1
2)K*N(1)+K*N(2) after stage 2 when N(2) can be function of the tree
3)KxN(1)+K*N(2)+K*N(3) after stage 3

The tree may not be the same in the middle of a stage but it is going to be always the same at the end of the stage.

[bob]

Logically the search can be deterministic if we decide that the at stage i of the search all threads gets independent tasks to search N(i) nodes and if part of the threads finished searching N(i) nodes they do nothing until the rest of the threads search N nodes

The threads can use their local hash and local killers and local history
or some global unchanged information that they have from previous search.

After all threads searched N(i) nodes they can share information like hash information to be available to all and the computer can decide about some value N(i+1) when all threads get indepenent tasks to search N(i+1) nodes

The tree is always the same after every stage and if the number of threads is K then the size of the tree is

1)K*N(1) after stage 1
2)K*N(1)+K*N(2) after stage 2 when N(2) can be function of the tree
3)KxN(1)+K*N(2)+K*N(3) after stage 3

The tree may not be the same in the middle of a stage but it is going to be always the same at the end of the stage.

Let me reference my original premise, which was based on a "reasonable parallel implementation." What you are proposing will certainly work. And it will work _very_ badly. When you use 8, 16, 24 or 32 cores (or way beyond if you get to GCP's distributed search), all of that overhead means that Amdahl's law falls right on your head with a mass of several tons. Who wants a parallel speedup of 4 with 32 cores? If you are lucky. Who wants a parallel speedup of 8 with 400 cores on a cluster? Reference "Amdahl's law with respect to parallel search" with Google for some spot-on analysis.

So my original discussion was based on a reasonable algorithm. Not one where everybody searches the same number of nodes and then synchronizes before going on. That will provide nothing short of horrible performance. While we want nothing short of optimal performance.