[computer-go] Pay-as-you-go cluster?

[Don Dailey]

On Mon, 2006-10-02 at 13:10 -0300, Eduardo Sabbatella wrote:
> 
> > If one finds a good way to paralellize a search
> > algorithm, it is probably
> > because it was inefficient from the very beginning.
> 
> That is not true.


Yes, it is.  

Magnus points out, in so many words, that if you do get 100% utilization
you must have started with something that was not serial in nature.
But the whole strength of this kind of search (as well as alpha/beta) is
that you can benefit enormously from previous work done.   So if you are
NOT, then as Magnus states, "it was inefficient from the very
beginning."

If you start with something that cannot benefit from work already done,
then you have an inefficient algorithm, although probably it is easy to
make parallel.  


If you have, say, a mini-max search that doesn't deal with alpha beta
cutoff's,  it's EASY to get close to 100% full processor utilization.
But you are getting 100% over a mini-max search, not 100% over the
serial alpha/beta algorithm. 

Another observation about parallel computing which is well known is that
you can almost always pick and choose your tradeoff's.   For instance
you can do things which minimize the amount of communication between
processors but this generally increases the amount of extra work that
you do.   If an algorithm is not perfectly serial in nature, there is no
free lunch, you must accept that you will not get 10X speedup with 10X
processors.   

This will be the case with UCT.   Since we are building a tree in
memory, and each simulation is refined by the previous simulation, this
is NOT an algorithm that we can expect to get 100% parallelism.   Don't
lose sleep over it, it is simply a fact of life.   


- Don