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:tho...@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.i...@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

Reply via email to