RE: FW: [PATCH] Cilk Keywords (_Cilk_spawn and _Cilk_sync) for C

["Tannenbaum, Barry M" <barry dot m dot tannenbaum at intel dot com>]

That's exactly correct.

There are two ways to implement a work-stealing scheduler. We refer to them as:

   - Child Stealing - This is what TBB implements. The spawned call is bundled up with all the parameters and pushed onto a queue. The worker will continue executing the code after the spawned function until a sync, at which point it will go back and execute any spawned functions that haven't already been stolen.

   - Parent Stealing - When a _Cilk_spawn is executed, an annotation is made on the worker's deque indicating that the continuation (the code following the _Cilk_spawn call) is available for stealing, and the worker starts executing the spawned function. When the spawned function returns, a check is made to determine whether the parent has been stolen. If it hasn't, then the spawned function returns normally. If it has, then execution jumps to the sync.

Cilk implements Parent Stealing. Since you're running with 1 worker, there's no other worker to steal the continuation. So steal_flag will never be set to 1 and you'll never break out of the loop.

One of the advantages of Child Stealing is that it's very light weight. It requires a jmpbuf (in the __cilkrts_stack_frame allocated in the spawning function) and a char * in the worker's deque.

   - Barry (Intel Cilk Plus Development)


-----Original Message-----
From: Thomas Schwinge [mailto:thomas@codesourcery.com] 
Sent: Monday, September 22, 2014 9:56 AM
To: Iyer, Balaji V
Cc: gcc-patches@gcc.gnu.org
Subject: Re: FW: [PATCH] Cilk Keywords (_Cilk_spawn and _Cilk_sync) for C

Hi!

On Tue, 27 Aug 2013 21:30:49 +0000, "Iyer, Balaji V" <balaji.v.iyer@intel.com> wrote:
> --- /dev/null
> +++ gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c
> @@ -0,0 +1,37 @@
> +/* { dg-do run  { target { i?86-*-* x86_64-*-* arm*-*-* } } } */
> +/* { dg-options "-fcilkplus" } */
> +/* { dg-options "-lcilkrts" { target { i?86-*-* x86_64-*-* arm*-*-* } 
> +} } */
> +
> +void f0(volatile int *steal_flag)
> +{
> +  int i = 0;
> +  /* Wait for steal_flag to be set */
> +  while (!*steal_flag) 
> +    ;
> +}
> +
> +int f1()
> +{
> +
> +  volatile int steal_flag = 0;
> +  _Cilk_spawn f0(&steal_flag);
> +  steal_flag = 1;  // Indicate stolen
> +  _Cilk_sync;
> +  return 0;
> +}
> +
> +void f2(int q)
> +{
> +  q = 5;
> +}
> +
> +void f3()
> +{
> +   _Cilk_spawn f2(f1());
> +}
> +
> +int main()
> +{
> +  f3();
> +  return 0;
> +}

Is this really well-formed Cilk Plus code?  Running with CILK_NWORKERS=1, or -- the equivalent -- in a system with just one CPU (as per libcilkrts/runtime/os-unix.c:__cilkrts_hardware_cpu_count returning 1), I see this test busy-loop as follows:

    Breakpoint 1, __cilkrts_hardware_cpu_count () at ../../../source/libcilkrts/runtime/os-unix.c:358
    358     {
    (gdb) return 1
    Make __cilkrts_hardware_cpu_count return now? (y or n) y
    #0  cilkg_get_user_settable_values () at ../../../source/libcilkrts/runtime/global_state.cpp:385
    385             CILK_ASSERT(hardware_cpu_count > 0);
    (gdb) c
    Continuing.
    ^C
    Program received signal SIGINT, Interrupt.
    f0 (steal_flag=steal_flag@entry=0x7fffffffd03c) at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:9
    9         while (!*steal_flag) 
    (gdb) info threads
      Id   Target Id         Frame 
    * 1    Thread 0x7ffff7fcd780 (LWP 30816) "spawning_arg.ex" f0 (steal_flag=steal_flag@entry=0x7fffffffd03c) at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:9
    (gdb) list
    4
    5       void f0(volatile int *steal_flag)
    6       { 
    7         int i = 0;
    8         /* Wait for steal_flag to be set */
    9         while (!*steal_flag) 
    10          ;
    11      }
    12
    13      int f1()
    (gdb) bt
    #0  f0 (steal_flag=steal_flag@entry=0x7fffffffd03c) at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:9
    #1  0x00000000004009c8 in _cilk_spn_0 () at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:17
    #2  0x0000000000400a4b in f1 () at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:17
    #3  0x0000000000400d0e in _cilk_spn_1 () at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:30
    #4  0x0000000000400d7a in f3 () at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:30
    #5  0x0000000000400e33 in main () at [...]/source/gcc/testsuite/c-c++-common/cilk-plus/CK/spawning_arg.c:35

No additional thread has been spawned by libcilkrts, and the one initial thread is stuck in f0, without being able to make progress.  Should in f0's while loop, some function be called to "yield to libcilkrts scheduler", or should libcilkrts have spawned an additional thread, or is the test case just not valid Cilk Plus code?


GrÃÃe,
 Thomas