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
Daniel Shawul



Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia
PostPost subject: Re: YBWC: Active Reparenting    Posted: Thu Apr 19, 2012 12:46 pm Reply to topic Reply with quote
Quote:

As i woke up sooner than Bob: 64 KB is what Cray Blitz copied.
But is it relevant? Sure maybe for the speedup of Cray Blitz.
This is not so interesting 35 years later.

Enough has been said about how Bob writes his articles around 2002.

DTS is a real invention, don't ever forget that.

Not sure when Bob invented it, yet we're in 2012 now and it still works great for up to a core or 32 at todays hardware giving a magnificent speedup, whereas it's not so complicated to build in a centralized manner.

I'll have to see anyone of us inventing something that still works 35 years later.

Cilkchess and Zugzwang and Hydra and Deep Blue are far more recent creations and these entities lose factor 40-50 handsdown and Deep Blue loses effectively a lot more than that.

Vincent I do not doubt it is a great invention. The online article about DTS is a bit confusing what is going on with the HELP command. I made another post about when and how much is being copyied when a HELP is issued. But later I deleted it because I found something else which implied very little (not some 64kb) is being copied in IEEE journal. So I just decided to give Bob a chance to explain. My deleted post is quoted below.

Daniel wrote:

First this:
online_article wrote:

The HELP command is the primary signaling mechanism within DTS. Whenever a processor is "out of work" it sends the HELP command to what is effectively the entire group of active processors. The HELP command simply requests that any processors that are actively searching subtrees temporarily stop, copy the "tree state" to shared memory, and then continue searching.

As these "tree states" become available, the idle processor that initiated the HELP command analyzes each state to determine if it can find a satisfactory split point. If not, it simply re-broadcasts the HELP command.


But later you say.
online_article wrote:

An interesting feature here, is that once a processor finds a viable split-point, and the Split() operation is performed, whenever any other processor becomes idle, they check for active split-points before broadcasting a HELP command. If a processor locates any valid split points, and there is work remaining at any of them, it simply attaches to the split point with the most work remaining, and does not broadcast a help command.

So clearly there is no copying if there are active split points. So the "HELP" command and hence the copying of tree state to shared memory is _rarely_ done, which is the key here. Also even after the HELP command is issued (i.e once we determine the active split points are no good), why do we ask the busy processors copy the tree state to shared memory ? Can't it look for a good split point like we did the test for reattaching to active split points? Copying should be done only when we actually split IMO, doing that while looking for a good split point is sure to consume bandwidth. The whole reason why we don't split at shallow depths is to reduce the cost of splitting (i.e copying tree state). I can understand that finding good split points is top priority at that time because YBW was not invented. So the copying while looking for split points could be justified because of that.


The IEEE journal says
Quote:

Whenever a processor exhausts the work
(sub-tree) that it is working on, it broadcasts a help
request to all busy processors. These processors
make a quick copy of the type of each node they
are searching in the current sub-tree and the
number of unsearched branches at each node,
and give this information to the idle processor. The
busy processors then resume searching where
they were interrupted. The idle processor (or
processors if more than one is idle) examines the
data and picks the most likely split point based on
immediately stop and try to find more useful work
to proceed with, by broadcasting a help request.
As a processor finds a new best score for a split
point, it shares the value with other parallel
searchers at that split point to improve their AB
cutoff performance. These issues are dealt with
more deeply in Hyatt’s thesis [7].

So this clearly says very little is copyied. This makes much more sense. Does some one have the phd thesis btw ?

Quote:

I don't know what's wrong with you there. Wake up - we live in 2012.

Technology from half a century ago you're comparing with the superior GPU technology we have right now made by Nvidia, with another monster soon to show up from them that you measure in TERAFLOPS a gpu. Nothing can rival THAT on this planet.

Go have a look at Zugzwang 1988 ok. It's 10 years after Cray Blitz. They run at a 512 processor box with each 'processor' being 1Mhz.

Sure, not processors that can get the same IPC like todays ones and the box is not symmetric multiprocessing either, yet...

How much nodes a second does the box reach in total for Zugzwang?

200.
So not 200k. Not 20k. Two-hundred.

Checkout the specs of the box. The network of it was magnificent as compared to the CPU's.

Over 2.5 million cycles per node.

Their paper claims a 50% speedup kind of.

After some longer study of the weird technical terminology used in that article i concluded they divided the number of nodes from 1 processor by the number of nodes searched by n processors and claimed that as their speedup.

Now as they invented (?) YBW that's going to be pretty good of course, especially if you forget to mention that...

Factor time they forgot... ...so the simple algorithm of having 511 cpu's idle and just 1 search would get the magnificent speedup of 100% in this manner...

I hope you're not projecting these standards onto todays standards...

Maybe I got carried away a bit but it sure seemed to be exciting for the participants at that time. Also I want to get to the bottom of what the old Crays are about. Those supercomputers have very few cores that got performance in 1-2 gflops. Like any other supercomputer the performance is measured with LINPACK and kind of weird to have a chess application on it. Harry said less than 5% of chess is vectorizable but he still managed to vectorize some on movegen and attacks. The large number of registers also helped to do a number of hash probes at one time (upto 7), and also to store bitboards and other things that can't be easily done on non-vector processors. If you can access the IEE journal you may find it interesting too Smile
_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul
Back to top
View user's profile Send private message Visit poster's website Yahoo 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