Arpit Saxena

Stanford CS149 - Parallel Computing - Lecture 5

• 2 min read • Last modified

Fork-Join pattern

cilk Plus is C++ language extension, available as open standard in GCC and Intel ICC

cilk_spawn foo(args);

Semantics: invoke foo, but caller may continue executing asynchronously with execution of foo

cilk_sync;

Semantics: Returns when all calls spawned by current functions have completed. There is an implicit cilk_sync; at the end of every function that contains a cilk_spawn

This is very similar to async and await, except no value returns

This can be used to implement divide-and-conquer algorithms like quicksort.

Cilk Plus Impleemntation

There is a pool of worker threads

cilk_spawn foo(); // spawned child
bar();            // Continuation
cilk_sync;        //
  • In a serial implementation, what we do is that we first execute the spawned child and push the continuation into the stack (work queue)
  • In the parallel implementation, other threads can steal from the work queue

Two choices:

  • Run continuation first — child stealing
    • Like breadth first traversal, thread keeps adding work into queue
  • Run child first — continuation stealing
    • Thread works on child, pushes continuation onto the work queue which can be stolen by other worker threads

Consider the program:

for (int i = 0; i < n; i++)
	cilk_spawn foo(i);
cilk_sync;
  • If we run continuation first:
    • we will have pushed foo(0), foo(1), ..., foo(n-1) into the work queue. So the storage required will be O(n).
    • Then, considering that no other thread stole the work, the current thread will keep popping the stack and run foo(n-1), foo(n-2), ..., foo(0) which is different from the order in which the functions would’ve run serially
  • If we run child first:
    • It can shown that for T threads, we will use O(T) times the stack space a serial program uses.
    • The continuation can be stolen by another thread if they’re free

Cilk does continuation stealing (child-first) and implements a greedy join scheduling policy. Threads steal work as soon as they’re idle. If work isn’t being stolen, it means that all threads are busy.

Implementing sync

To implement sync, we need to keep track of the tasks for which a sync will wait. These can have a tag and that tag is known by sync:

  • For each tag, we have a descriptor block storing {spawn: n, done: m}. This means how many tasks were spawned for this tag and how many of those are done.
  • Somehow, this bookkeeping is only done when tasks are stolen. Otherwise, there’s no overhead
    • How?

Graph View