I've been using this "abort early to save time" idea almost since the beginning. It works fine with root parallelization.
David > -----Original Message----- > From: [email protected] [mailto:computer-go- > [email protected]] On Behalf Of Mark Boon > Sent: Sunday, August 12, 2012 9:07 PM > To: [email protected] > Subject: Re: [Computer-go] Kas Cup - results and prizes > > Interesting, I'd have thought it would matter quite bit, especially with > higher numbers of threads. > > One thing I found (quite a few years back now already) is that you can > optimize a lot by doing the following: when one node has so many more > wins than the second best that it can't be overtaken even if the second > best wins all of the remaining playouts, abort thinking. With a couple > of extensions to this general idea (aborting not just when it's > impossible, just very unlikely to be overtaken) I found that a player > that does 64K lightweight simulations using this method spends the same > time and plays the same level as one that does a fixed 32K simulations. > Roughly. The higher the number of simulations, the bigger the savings. > > This type of optimization must be much harder with root-level > parallelization, so you'd have to factor that in when comparing methods. > > Mark > > On Aug 10, 2012, at 9:55 PM, "David Fotland" <[email protected]> > wrote: > > > Not much memory overhead. If you look at your tree you will find that > > most nodes are only visited one or two times. There is a lot of noise > > in the fringes of the tree, so there are few duplicates. This also > > means that not sharing most of the tree has no impact on strength. > > > > David > > > >> -----Original Message----- > >> From: [email protected] [mailto:computer-go- > >> [email protected]] On Behalf Of Michael Williams > >> Sent: Friday, August 10, 2012 9:42 AM > >> To: [email protected] > >> Subject: Re: [Computer-go] Kas Cup - results and prizes > >> > >> I imagine you can get around the lack of implicit information sharing > >> that you get with a shared tree by explicitly sharing information > >> near the root. > >> > >> But doesn't having separate trees mean a large memory overhead due to > >> duplicate nodes? > >> > >> > >> On Fri, Aug 10, 2012 at 9:26 AM, David Fotland > >> <[email protected]> > >> wrote: > >>> Because my current approach seems to work just as well (or maybe > >>> better), and I haven't had time to code up a shared try and tune it > >>> up to validate that assumption. Chaslot's paper indicates perhaps > >>> that not having a shared tree is stronger. My guess is that they > >>> are about the same, so it's not worth the effort to change. > >>> > >>> david > >>> > >>>> -----Original Message----- > >>>> From: [email protected] [mailto:computer-go- > >>>> [email protected]] On Behalf Of Michael Williams > >>>> Sent: Friday, August 10, 2012 12:06 AM > >>>> To: [email protected] > >>>> Subject: Re: [Computer-go] Kas Cup - results and prizes > >>>> > >>>> Why don't you use a shared tree? > >>>> > >>>> > >>>> On Thu, Aug 9, 2012 at 11:49 PM, David Fotland > >>>> <[email protected]> > >>>> wrote: > >>>>> On an i7-2600 Many Faces does 11.4K pps with 4 threads, and 18.7k > >>>>> with > >>>>> 8 threads, a 64% increase, so the 2600 scales a little better than > >>>>> the 3770, but the 3770 is still a litte bit faster. > >>>>> > >>>>> > >>>>> > >>>>> david > >>>>> > >>>>> > >>>>> > >>>>> From: [email protected] > >>>>> [mailto:[email protected]] On Behalf Of Erik van der > >>>>> Werf > >>>>> Sent: Thursday, August 09, 2012 4:41 AM > >>>>> > >>>>> > >>>>> To: [email protected] > >>>>> Subject: Re: [Computer-go] Kas Cup - results and prizes > >>>>> > >>>>> > >>>>> > >>>>> I don't have an i7-2600, but I could run oakfoam on the 3930. I > >>>>> just downloaded it and it does compile. If you give me a list of > >>>>> gtp commands to run the benchmark, then I will send you the output > >> back. > >>>>> > >>>>> > >>>>> > >>>>> Erik > >>>>> > >>>>> > >>>>> > >>>>> On Thu, Aug 9, 2012 at 12:38 PM, ds <[email protected]> wrote: > >>>>> > >>>>> This is very interesting, > >>>>> > >>>>> I have not more than 10% with oakfoam on i7-2600K. Would be > >>>>> interesting if it is the processor or if you e.g. access more > >>>>> often memory instead of cache due to your code... > >>>>> > >>>>> Do you have the chance to run your program on a i7-2600? or do you > >>>>> have to much time and try > >>>>> https://bitbucket.org/francoisvn/oakfoam/wiki/Home > >>>>> on your i7-3930. If so, I would be very much interested in the > >>>>> number you get in the beginning of a 19x19 game without book:) > >>>>> > >>>>> > >>>>> Detlef > >>>>> > >>>>> Am Donnerstag, den 09.08.2012, 12:16 +0200 schrieb Erik van der > >> Werf: > >>>>> > >>>>>> On Thu, Aug 9, 2012 at 11:14 AM, Petr Baudis <[email protected]> > wrote: > >>>>>> On Wed, Aug 08, 2012 at 09:08:47PM +0200, ds wrote: > >>>>>>> Hyperthreading does the trick, I have the experience it > >>>>>> increases the > >>>>>>> performance by about 10%. I think this is due to waiting > >>>> for > >>>>>> RAM I/O or > >>>>>>> things like that.... > >>>>>> > >>>>>> > >>>>>> Yes. With hyperthreading, performance per thread goes down > >>>>>> significantly, but total performance goes up by about 15%. > >> In > >>>>>> the > >>>>>> Pentium 4 era, hyperthreading did not usually pay off, but > >>>>>> with i7, > >>>>>> its performance is much better. The basic idea is that > >> there > >>>>>> are two > >>>>>> instruction pipelines that share the same ALU and other > >>>>>> processor units; > >>>>>> if one of the pipelines stalls (usually due to memory > >> fetch), > >>>>>> the other > >>>>>> can use the ALU in the meantime, or the two threads may > >> use > >>>>>> different > >>>>>> parts of the CPU altogether based on what the instructions > >>>> do. > >>>>>> > >>>>>> > >>>>>> > >>>>>> 10-15%, really, that low? For my program (on an i7-3930K, going > >>>>>> from > >>>>>> 6 to 12 threads) it is more in the order of 40% extra simulations > >>>>>> per second. > >>>>>> > >>>>>> > >>>>>> Erik > >>>>>> > >>>>>> > >>>>> > >>>>>> _______________________________________________ > >>>>>> Computer-go mailing list > >>>>>> [email protected] > >>>>>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >>>>> > >>>>> > >>>>> _______________________________________________ > >>>>> Computer-go mailing list > >>>>> [email protected] > >>>>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >>>>> > >>>>> > >>>>> > >>>>> > >>>>> _______________________________________________ > >>>>> Computer-go mailing list > >>>>> [email protected] > >>>>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >>>> _______________________________________________ > >>>> Computer-go mailing list > >>>> [email protected] > >>>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >>> > >>> _______________________________________________ > >>> Computer-go mailing list > >>> [email protected] > >>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >> _______________________________________________ > >> Computer-go mailing list > >> [email protected] > >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > > > _______________________________________________ > > Computer-go mailing list > > [email protected] > > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
