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

[Eduardo Sabbatella]

Hello,

I agree 100% with you, except on algorithm
optimization :-)

You have to get some tradeoffs, as you pointed.

Distributed hashes, or whatever structure is
impossible to maintain at "inner loop" level. Even, on
SMP machines.

Thats the whole point on this. Try to batch a couple
of updates and do that lazily. Don't worry about doing
10k*proc not _SO_ efficient MC simulations. That
simulations are not useless, they are using perhaps a
transposition table 100ms "old". (and all they will be
new simulations because the posibility of repeating a
random game simulation is almost impossible).

At some point, it will be a tradeoff between the
"response speed" of the algorithm (in the sense of
speed chossing wise paths),  agains more wise
selections. (because more games tried, more confident
selecctions).


Eduardo


 --- Don Dailey <drd at mit.edu> escribió:

> 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
> 
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
>
http://www.computer-go.org/mailman/listinfo/computer-go/
> 



	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas