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 

MP Implementation: One Method or Varied?
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: MP Implementation: One Method or Varied?    Posted: Mon May 28, 2012 3:09 pm Reply to topic Reply with quote
Howard E wrote:
When designing multi-processor chess programs is there typically one way to do this? Or do we see different approaches in how to utilize the processors?


there are many ways to do it. However nowadays chessprograms search very deep and get a lot of positions per second and the number of cores keeps growing.

So the first requirement is to implement a SMP search that doesn't deteriorate the branching factor too much. Many 'old school' SMP solutions really have a bad effect on the branching factor. Branching factor is the time to get to the next ply here to use not an accurate definition of it. In 80s and 90s this was far over factor 10 for most supercomputers or some other big factor. Nowadays we're at 2.0 or better.

If you manage to parallellize your program getting that branching factor up from 2.0 to 3.0, to give an example, then even a 1000 processor supercomputer will be outsearched by a simple laptop.

So februari 1998 when talking to Rainer Feldmann about how to parallellize Diep, he did do the historic prediction that initially if you parallellize your program, you're actually SLOWER, not faster! He had a talent there to predict the future. Februari 1999 first run on Bob's quad Xeon, diep was 6x slower than Diep single cpu. Not faster at all!

Then there is a number of SMP approaches that definitely will not scale well or simply have a very bad speedup when the number of cores used grows.

As it appears more complex ways to parallellize simply perform better then, yet there is very few who managed and/or did do the effort to implement more complex forms of YBW.

So what you see typically is that several 'cheapskate' solutions have been developed to get *some* speedup meanwhile still following YBW.

As usual such algorithms don't dictate the datastructure how to efficiently implement YBW.

Then there can also be distinguished between the types of implementation.

One can implement YBW with central locking, such as crafty for example is doing and get a decent speedup, or you can try to look for a way to do it without central locking such as Diep. In that case you scale easier to more cores meanwhile having a magnificent speedup.

Now YBW is a rather simple idea. Search the first move sequential and after that parallellize the rest of the moves. This means obviously that the real difficult to accomplish goal is cheap splitting and cheap abortion.

So some enthusiasts saw therefore another cheapskate implementation that avoids the complex way to abort cpu's, such as i do in Diep, and simply not abort at all. The question is whether one would be able to call what some do there a full YBW implementation, if you don't abort.

In short all sorts of hybrid forms of SMP search are there.

In general the surviving mechanism everywhere is YBW.

What YBW doesn't dictate of course is what to do when in this given position P that has been split all moves are 'under search' and 1 of the cores is ready with its job there, yet doesn't win a queen or something, so no fail high occurs - the other cpu's do not need to get aborted.

So there is a wildgrow of mechanisms there that get used what to do if something like that happens.

Some engines, the ones that are recursive in general, are stuck there in the mudd as they might own the recursions previous to this position. Others not using recursion such as Diep can frankly do whatever they want.

Yet realize YBW is not easy to implement if you try to fully implement it. It does preserve however your branching factor very well and we cannot say that from most other forms of SMP such as Aphid, to give an example.
So in general spoken a good performing SMP search is a very mathematical type of accomplishment where the programmer needs a big skillset to prove correctness of search. Only a few on this planet have that.

Picking up just another software architect from the street and have him implement a good performing SMP search that's asking for trouble.

A quote that definitely describes this for SMP:

"Computerchess is very boring, you always see the same persons!" Jonathan Schaeffer.
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
MP Implementation: One Method or Varied? Howard Exner Sat May 26, 2012 6:32 pm
      Re: MP Implementation: One Method or Varied? Matthew R. Brades Sat May 26, 2012 7:21 pm
            Re: MP Implementation: One Method or Varied? Jon Dart Sat May 26, 2012 11:22 pm
            Re: MP Implementation: One Method or Varied? Howard Exner Tue May 29, 2012 5:53 pm
                  Re: MP Implementation: One Method or Varied? Vincent Diepeveen Tue May 29, 2012 6:51 pm
                  Re: MP Implementation: One Method or Varied? Ronald de Man Tue May 29, 2012 7:18 pm
      Re: MP Implementation: One Method or Varied? Vincent Diepeveen Mon May 28, 2012 3:09 pm
      Re: MP Implementation: One Method or Varied? Jouni Uski Mon May 28, 2012 5:33 pm
            Re: MP Implementation: One Method or Varied? Uri Blass Tue May 29, 2012 8:39 am
                  Re: MP Implementation: One Method or Varied? Alexander Zacharias Thu Jun 07, 2012 1:05 pm
            Re: MP Implementation: One Method or Varied? Ricardo Barreira Tue May 29, 2012 9:19 am
            Re: MP Implementation: One Method or Varied? Joona Kiiski Tue May 29, 2012 12:03 pm
                  Re: MP Implementation: One Method or Varied? Ricardo Barreira Tue May 29, 2012 1:27 pm
            Re: MP Implementation: One Method or Varied? Daniel Shawul Tue May 29, 2012 1:03 pm
            Re: MP Implementation: One Method or Varied? Robert Hyatt Tue May 29, 2012 3:18 pm
                  Re: MP Implementation: One Method or Varied? Vincent Diepeveen Tue May 29, 2012 4:03 pm
                        Re: MP Implementation: One Method or Varied? Daniel Shawul Tue May 29, 2012 4:31 pm
                              Re: MP Implementation: One Method or Varied? Vincent Diepeveen Tue May 29, 2012 6:33 pm
                        Re: MP Implementation: One Method or Varied? Robert Hyatt Wed May 30, 2012 6:25 pm
                              Re: MP Implementation: One Method or Varied? Vincent Diepeveen Sat Jun 02, 2012 4:07 pm
            Re: MP Implementation: One Method or Varied? Jan Brouwer Wed May 30, 2012 9:13 pm
                  Re: MP Implementation: One Method or Varied? Daniel Shawul Wed May 30, 2012 9:36 pm
                        Re: MP Implementation: One Method or Varied? Vincent Diepeveen Sat Jun 02, 2012 3:58 pm
                  Re: MP Implementation: One Method or Varied? Ricardo Barreira Thu May 31, 2012 8:26 am
                        Re: MP Implementation: One Method or Varied? Robert Hyatt Thu May 31, 2012 3:30 pm
                  Re: MP Implementation: One Method or Varied? Vincent Diepeveen Sat Jun 02, 2012 3:57 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