ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

YBWC: Active Reparenting
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Vincent Diepeveen



Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands
PostPost subject: Re: YBWC: Active Reparenting    Posted: Wed Apr 11, 2012 1:54 pm Reply to topic Reply with quote
Daniel Shawul wrote:
Rein Halbersma wrote:
mcostalba wrote:
In Young Brothers Wait Concept (YBWC) available slaves are booked by the split point master, then start to search below the assigned split point and, once finished, return in idle state waiting to be booked by another master.

I have pushed a patch that introduces what I have called "Active Reparenting" so that when a slave finishes its job on the assigned split point, instead of passively waiting to be booked, searches a suitable active split point and reparents itself to that split point. Then immediately starts to search below the split point in exactly the same way of the others split point's slaves. This reduces to zero the time waiting in idle loop and _could_ increase scalability especially with many (8 or more) cores, at least this is the idea.

Perhaps Don Dailey can comment on this further, but it seems like you have rediscovered "randomized work stealing"! The MIT Cilk project used such a provably optimal scheduler to implement CilkChess. More speculatively: I wouldn't be surprised if even the convoluted DTS-type scheduling of the YBW algorithm would be another manifestation of work stealing.

What he did is not randomized work stealing, there is nothing random there. He just checked existing split points to reattach itself.
This will most probably not decreases idle time because working threads pick up threads quickly anyway if you let them, but the selection made by the former i.e higher up
in the tree may help. I actually mentioned about the randomized work stealing that I use on cluster search in my first post.
But this might not be the smartest thing to do since we could have differnt network interfaces with varying latency. MPI allows you to group processors for most efficient work sharing.

Cilk begins with an overhead of creating and destryoing threads,as Vincent explained. I don't know if it keeps a thread pool
for that but it is still expensive anyway. For simple applications like parallel fibonacci serial versions outperform parallel versions due
to this overhead. OpenMP has added task based parallelism now but its performance is poor compared to Cilk. http://myxman.org/dp/node/182

Also from what I read the performance of Socrates chess is affected by this overhead too. The authors have blamed the poor performance
on the algorithm used (Jamboree search) but that seems to me very similar to YBW algorithm. http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-548.pdf
A speedup of 48 out of 256 is what they get and I also read somewhere eles not many extensions/reductions were used.
So I have my doubts about cilk eventhough it makes life a lot easier.


Daniel - the real problem of Cilk is the same like that of all the parallel programs back then at massive supercomputers of some hundreds of cpu's.

They first slowdown their program factor 40 to 50 in order to claim a better scaling and speedup.

So that's exactly what Cilk was doing. When run at 1 processor cilkchess got 5000 nps a second. A simple bitboards program with near to zero evaluation, this at a 300Mhz Sun processor. Yes a 64 bits processor.

Without Cilk at his laptop it got 200k nps. That was a lot lower clocked laptop and a mobile chip.

For comparision at the same Sun processor Diep from back then got 10k nps and Diep had a huge evaluation also back then with all sorts of mobility scans and Crafty got around a 200k nps single core back then.

Now all the 'researches' and pdf's, the few that are there, are based upon comparing n processor search with 1 slowed down program that suffers the framework slowdown.

It's like saying your soldiers are moving fast at the battlefield.
And to prove they move fast you have them carry 50 kilo and also one of the spectators gets to carry 50 kilo.

It's a nonsense compare as you want to compare with a runner without that luggage of course as in computerchess you have to look strong against programs not using Cilk as well Smile

On top of that big major problem is the hopeless idea of doing things total centralized within Cilk which is already an exponential burden and threads that get idled and unidled, which is a big death penalty which you already hardly notice of course after being factor 40+ slowed down first.

Another bizarre claim is the speedup claim all these guys do - yet of course searches aren't comparable to todays searches. If you search fullwidth then of course it's much easier to split and get a good speedup.

The problem is, when i talked to them in the world champs 1999 and saw their output, none of them got more than 1 to 2 million nps or so at a 512 processor supercomputer. Cilkchess ran at a 512 processor origin3800. Some years later Diep would also run at it and reach 10.1 mln nps. Counted in same manner like Cilkchess that would be 20 mln nps, diep being a chessprogram with a huge evauluation function scanning all sorts of things in all sorts of loops as well.

My later requests to obtain logfiles from cilkchess were all ignored.
That already tells you the whole story.

Note that Deep Blue's logfiles also carry no searchcounter at all.

If you hide something that you HAVE to measure, then you have to hide something...

So it already was roughly a knockout at the same hardware of Diep versus Cilk. A program that's factor 10 to 20 times slower than a bitboard beancounter being effectively factors faster at the same supercomputer.

Their scaling and speedup numbers for *socrates and cilkchess basically are academic fraud in its purest form and everyone knows it. Chrilly Donninger later on joined them in doing that. He also compared a single hydra processor not using hashtables last 6 plies or so, with the full cluster not using hashtables last 6 plies, because the ONLY REASON to not use hashtables last 6 plies was because it didn't scale... ...meanwhile not doing it is deteriorating performance by factors. Around a factor 10 in my measurement.

In the first place it's pathetic to do that comparision in that manner.
Secondly it's pure fraud. Third it's the same fraud the guys before him did do.

If you aren't good enough and/or if your framework isn't good enough to play exponential games with, don't say it is having a good scaling and good speedup as it hasn't.
Back to top
View user's profile Send private message Send e-mail Visit poster's website MSN Messenger
Display posts from previous:   
Subject Author Date/Time
YBWC: Active Reparenting Marco Costalba Tue Apr 10, 2012 5:38 pm
      Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 10, 2012 6:23 pm
            Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 10, 2012 7:11 pm
                  Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 10, 2012 7:54 pm
                        Re: YBWC: Active Reparenting Marco Costalba Tue Apr 10, 2012 8:48 pm
                              Re: YBWC: Active Reparenting Vincent Diepeveen Wed Apr 11, 2012 10:09 am
                                    Re: YBWC: Active Reparenting Robert Hyatt Mon Apr 16, 2012 6:53 pm
                        Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 10, 2012 11:11 pm
                              Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 10, 2012 11:33 pm
                              Re: YBWC: Active Reparenting Robert Hyatt Mon Apr 16, 2012 7:07 pm
                                    Re: YBWC: Active Reparenting Vincent Diepeveen Mon Apr 16, 2012 8:55 pm
                                          Re: YBWC: Active Reparenting Robert Hyatt Tue Apr 17, 2012 2:54 pm
                                                Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 17, 2012 5:42 pm
                                                      Re: YBWC: Active Reparenting Robert Hyatt Tue Apr 17, 2012 8:01 pm
                                                            Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 17, 2012 9:34 pm
                                                                  Re: YBWC: Active Reparenting Robert Hyatt Tue Apr 17, 2012 9:46 pm
                                                                        Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 17, 2012 10:30 pm
                                                                              Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 17, 2012 11:43 pm
                                                                                    Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 18, 2012 1:05 am
                                                                                          Re: YBWC: Active Reparenting Vincent Diepeveen Wed Apr 18, 2012 11:24 am
                                                                                          Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 18, 2012 1:01 pm
                                                                              Re: YBWC: Active Reparenting Robert Hyatt Wed Apr 18, 2012 7:34 pm
                                                                                    Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 18, 2012 11:18 pm
                                                                                          Re: YBWC: Active Reparenting Vincent Diepeveen Thu Apr 19, 2012 7:01 am
                                                                                          Re: YBWC: Active Reparenting Daniel Shawul Thu Apr 19, 2012 12:46 pm
                                                                                          Re: YBWC: Active Reparenting Vincent Diepeveen Thu Apr 19, 2012 2:40 pm
                                                                                          Re: YBWC: Active Reparenting Daniel Shawul Thu Apr 19, 2012 9:32 pm
                                                                                          Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 19, 2012 7:08 pm
                                                                                          Re: YBWC: Active Reparenting Daniel Shawul Thu Apr 19, 2012 9:37 pm
                                                                                          Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 19, 2012 9:48 pm
                                                                                          Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 19, 2012 6:59 pm
                                                                                          Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 19, 2012 5:30 pm
                                                                        Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 17, 2012 11:29 pm
                                                                              Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 18, 2012 12:58 am
                                                                  Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 17, 2012 11:18 pm
                                    Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 17, 2012 5:37 pm
      Re: YBWC: Active Reparenting Álvaro Begué Tue Apr 10, 2012 6:27 pm
            Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 10, 2012 6:44 pm
      Re: YBWC: Active Reparenting Robert Hyatt Tue Apr 10, 2012 9:39 pm
            Re: YBWC: Active Reparenting Marco Costalba Wed Apr 11, 2012 6:06 am
                  Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 12, 2012 1:20 am
                        Re: YBWC: Active Reparenting Vincent Diepeveen Sun Apr 15, 2012 10:04 am
                              Re: YBWC: Active Reparenting Marco Costalba Sun Apr 15, 2012 10:22 am
                                    Re: YBWC: Active Reparenting Vincent Diepeveen Sun Apr 15, 2012 2:39 pm
                                          Re: YBWC: Active Reparenting Marco Costalba Mon Apr 16, 2012 5:29 am
                                                Re: YBWC: Active Reparenting Vincent Diepeveen Mon Apr 16, 2012 5:54 pm
                                                      Re: YBWC: Active Reparenting Marco Costalba Tue Apr 17, 2012 11:30 am
                                                Re: YBWC: Active Reparenting Marco Costalba Wed Apr 18, 2012 6:31 am
      Re: YBWC: Active Reparenting Rein Halbersma Wed Apr 11, 2012 7:23 am
            Re: YBWC: Active Reparenting Vincent Diepeveen Wed Apr 11, 2012 9:07 am
            Re: YBWC: Active Reparenting Vincent Diepeveen Wed Apr 11, 2012 9:31 am
            Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 11, 2012 12:14 pm
                  Re: YBWC: Active Reparenting Vincent Diepeveen Wed Apr 11, 2012 1:54 pm
                  Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 12, 2012 1:28 am
                        Re: YBWC: Active Reparenting Daniel Shawul Tue Apr 17, 2012 5:49 pm
                              Re: YBWC: Active Reparenting Vincent Diepeveen Tue Apr 17, 2012 11:10 pm
                                    Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 18, 2012 12:50 am
                              Re: YBWC: Active Reparenting Robert Hyatt Wed Apr 18, 2012 7:38 pm
                                    Re: YBWC: Active Reparenting Daniel Shawul Wed Apr 18, 2012 11:30 pm
                                          Re: YBWC: Active Reparenting Vincent Diepeveen Thu Apr 19, 2012 7:08 am
                                                Re: YBWC: Active Reparenting Daniel Shawul Thu Apr 19, 2012 12:15 pm
                                                      Re: YBWC: Active Reparenting Vincent Diepeveen Thu Apr 19, 2012 1:53 pm
                                          Re: YBWC: Active Reparenting Robert Hyatt Thu Apr 19, 2012 7:11 pm
      Re: GPUs Srdja Matovic Mon Jun 04, 2012 5:08 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads