Re: [computer-go] Hardware-Instruction.

[Don Dailey <drd@xxxxxxx>]

A little more about Cilk, since Vincent grossly mispresented it.

Cilk  is really C  with a  few simple  constructs added;  spawn, sync,
inlet and abort.   An inlet can catch the result  of a computation and
can abort work  inside it.  This mechanism makes  it perfect for alpha
beta searching.

Any function  that begins  with the keyword  "cilk" can be  spawned in
parallel.  The scheduler is based on work stealing.  In cilk you don't
think about  the number of  processors, this is abstracted  away.  Any
time  a "sync"  keyword is  invoked,  the processor  doesn't idle,  it
randomly grabs work from somewhere else.

The  beauty of  cilk  is that  it  rarely invokes  overhead for  these
parallel constructs.  The cilk  pre-processor constructs 2 versions of
each  "cilk" function,  one that  is purely  serial and  knows nothing
about the cilk keywords and  associated overheads and the other "slow"
version has all  the good stuff for managing  the scheduler.  The vast
majority of the time your program  is invoking pure C code without any
cilk overhead.

Here is an  example of the fibonacci function taken  from the cilk web
page:


cilk int fib (int n)
{
    if (n < 2) return n;
    else
    {
        int x, y;

        x = spawn fib (n-1);
        y = spawn fib (n-2);

        sync;

        return (x+y);
    }
}




For alpha/beta applications like chess, there is an abort keyword that
can be  invoked to stop  work that is  happening, such as is  the case
when you get a beta cutoff.   An "inlet" can catch this case and abort
all work spawned  inside the parent stack frame.   Basically, you call
the inlet (which is a function  inside a cilk function GCC style) with
a spawn  statement as an argument  to the inlet  function.  Inside the
inlet, you can abort work.

This sounds a  lot more complicated than it actually  is.  It is quite
trivial to write  an alpha/beta search routine using  cilk without the
normal pain  and agony and  debugging using a threading  library (like
pthreads) for instance.

The scheduler is  efficient and your code is  effecient, you are still
programming in  C.  You tell cilk  how many processes you  want to use
and cilk will use than many (even  if you are on a serial machine, you
can write, debug  and test parallel programs specifying  any number of
proceses.)    

If you write  a cilk program and  run it as a 1  processor program, it
will  run nearly as  fast as  the same  program written  without cilk,
usually within 1 or 2 percent slowdown.

It's really cool for many parallel programming tasks.

Check it out at  http://supertech.lcs.mit.edu/cilk/home/intro.html

- Don

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