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 

Parallelization questions, ABDADA or DTS?
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: Parallelization questions, ABDADA or DTS?    Posted: Sat Mar 24, 2012 9:52 pm Reply to topic Reply with quote
BeRo wrote:
diep wrote:

If you do that then it's more of a lossy YBW already basically Smile


Yes, there you're right.

diep wrote:

It's questionable whether you can abort children by hashtable in a lossless manner. We can prove of course that you might always overwrite that specific hashtable entry.

So only a lossy concept would make sense then.

The question i'd have then is that if you already do the administering work of YBW, then why would you need the overhead of additional stores to hashtable, which only makes things lossy and slower?



I'm implementing the plain classical YWBC stuff (together with the helpful master concept) as the first step in this moment, and then I'll see, what optimizations I can do as the next step, so the chances, as you already said, that it remains plain YWBC with some small optimizations, are very high. The original origin hybrid idea was just a chain of first-brainstorm-thoughts.

diep wrote:

By the way are you capable of reading the original abdada paper?
It's encrypted into Anglish by the original French author! Bon.


No, I'm a german, not a french, so don't confuse through my french-sounding surname. Smile


Yes i realize that, because the Gruendlich and systematic working Rudolf Huber was the first guy who could decipher the Anglish as written by the original abdada author. I'm convinced it would've been more popular quite a tad sooner otherwise.

The big difference between abdada and all others is that abdada basically is giving an implementation, not so much algorithm.

YBW is just a simple to understand algorithm, which leaves the question open on how to efficiently implement it; implementing it efficiently for dozens of cores is *really hard*.

Abdada on the other hand with its implementation limitation can be combined of course with YBW, because abdada in itself isn't an algorithm at all Smile

It's just an implementation idea. "oh let's solve it using lossy storage in hashtable".

In theory you could get away setting just 1 bit there; you probably won't split near the leaves anyway so odds you overwrite it using multiprobe system is already real small, and odds for a write error which is really a huge factor smaller than the overwrite, that's even more neglectible.

theoretic odds of overwrite are also real small, just the chaining lemma, which really is the case, it's not some sort of 'theoretic effect'; chaining REALLY happens.

The chaining effect causes a small chance of overwrite - you can easily risk that.

So for abdada you need real real little - yet it's just an implementation idea and a cheap one, it's not an algorithm from my point of view.

Starting with a master -slave concept is maybe a good idea to start implementing parallel search - yet in the long run take into account you want to get rid of it. A central master always is an obstacle you don't want to have; it creates a huge worst case.

Vincent
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
Parallelization questions, ABDADA or DTS? Benjamin Rosseaux Fri Mar 23, 2012 3:45 pm
      Re: Parallelization questions, ABDADA or DTS? Matthew R. Brades Fri Mar 23, 2012 3:54 pm
            Re: Parallelization questions, ABDADA or DTS? Robert Hyatt Sat Mar 24, 2012 2:57 am
                  Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sat Mar 24, 2012 8:19 am
                        Re: Parallelization questions, ABDADA or DTS? Benjamin Rosseaux Sat Mar 24, 2012 10:52 am
                              Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sat Mar 24, 2012 12:44 pm
                                    Re: Parallelization questions, ABDADA or DTS? Benjamin Rosseaux Sat Mar 24, 2012 1:57 pm
                                          Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sat Mar 24, 2012 9:52 pm
                                                Re: Parallelization questions, ABDADA or DTS? Benjamin Rosseaux Sun Mar 25, 2012 6:29 pm
                                                      Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sun Mar 25, 2012 7:27 pm
                  Re: Parallelization questions, ABDADA or DTS? Jon Dart Sat Mar 24, 2012 6:06 pm
            Re: Parallelization questions, ABDADA or DTS? Daniel Shawul Sat Mar 24, 2012 6:06 pm
                  Re: Parallelization questions, ABDADA or DTS? Seb Dragulic Sat Mar 24, 2012 9:26 pm
                        Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sat Mar 24, 2012 10:16 pm
                        Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sat Mar 24, 2012 10:38 pm
                              Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sat Mar 24, 2012 10:52 pm
                              Re: Parallelization questions, ABDADA or DTS? Seb Dragulic Sun Mar 25, 2012 12:21 am
                                    Re: Parallelization questions, ABDADA or DTS? Vincent Diepeveen Sun Mar 25, 2012 12:43 am
                                          Re: Parallelization questions, ABDADA or DTS? Seb Dragulic Sun Mar 25, 2012 12:59 am
                        Re: Parallelization questions, ABDADA or DTS? Daniel Shawul Sat Mar 24, 2012 11:25 pm
                  Re: Parallelization questions, ABDADA or DTS? Daniel Shawul Sat Mar 24, 2012 11:31 pm
      Re: Parallelization questions, ABDADA or DTS? Robert Hyatt Sat Mar 24, 2012 2:56 am
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