Re: [computer-go] Hardware-Instruction.

[Don Dailey <drd@xxxxxxx>]

 > MPI is probably faster and more flexible.

I might  also add that Cilk is  not slow, there is  almost no overhead
associated with  the Cilk runtime.  MIT  spent a great  deal of effort
making it very efficient.  You  still have to write parallel code, and
have implementation choices that might effect your program.

Cilkchess  use  the "younger  brothers  wait"  algorithm,  which is  a
programming choice,  you might do  it differently.  Basically,  at any
node you search  the leftmost branch SERIALLY, (no  spawn and no wait)
and if that doesn't give you a beta cutoff, you search all the sibling
nodes using  spawn calls  inside an "inlet."   If ANY of  the children
return with a beta cutoff, it  is caught by the inlet which aborts the
work being done in the  parent stack frame (all those parallel spawned
siblings  at the  current node.)   It is  very simple,  recursive, and
efficient.

I would like to  mention that all the work done on  Cilk was driven by
the computer chess  application.  In some sense Cilk  was created just
for  computer  chess  and  some  of it's  features  were  designed  to
accomodate the needs of alpha/beta searchers.

I have always been a bit  surprised how much trouble people have taken
to write and  debug parallel code the hard way.   With Cilk you hardly
even think about your program as a parallel monstrosity and you simple
focus on the chess part.

At the last world championship we played in, David Levy predicted that
we  would not  win even  though  we were  one of  the favorites.   His
prediction and reasoning was based  on the fact that parallel programs
are  typically full of  bugs and  problems.  I  really laughed  when I
heard his reasons,  because it was literally the  last thing likely to
be a  problem or  go wrong for  us, but  the most likely  for everyone
else.   This  part  was trivial.   As  it  turned  out, we  didn't  do
particular  well that  year, but  it had  nothing to  do  with David's
reasons.  I realized then that we were way ahead of everyone else with
regard  to parallelism.  There  were other  parallel programs  at that
tournament  that  were hanging  up  and  crashing  and even  requiring
reboots.

- Don



   Date: Sat, 6 Nov 2004 12:49:53 -0500
   From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
   Cc: computer-go@xxxxxxxxxxxxxxxxx
   Reply-To: drd@xxxxxxxxxxxxxxxxx, computer-go <computer-go@xxxxxxxxxxxxxxxxx>
   Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
   X-Scanned-By: MIMEDefang 2.42


   > According my feeling is Cilk more high level than e.g. MPI. It is easier
   > converting an existing programm to a parallel version with Cilk than with
   > MPI. I assume (but have never done any concrete tests or studies) that this
   > high-level comes with a price. MPI is probably faster and more flexible.

   Cilk is really C, so it's not a high level language.  Probably you are
   right about  the flexibility issue,  Cilk does the  scheduling itself.
   But MIT  did a lot  of studies and  for computer Chess and  many other
   kinds of tasks, they showed that the random work stealing algorithm is
   "provably  efficient", whatever  that means.   It would  very  hard to
   demonstrate an  improved scheduling algorithm and  before Cilk Bradley
   Kuszmaul did a  parallel chess program at MIT that  use the same exact
   algorithm but doing it the hard way, without Cilk.

   - Don
   _______________________________________________
   computer-go mailing list
   computer-go@xxxxxxxxxxxxxxxxx
   http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/