Pedigrees

In an execution of an Intel® Cilk™ Plus program, each maximal strand is identified by its pedigree, a variable-length sequence of 64-bit integers. Intel® Cilk™ Plus provides an API that enables you to query the pedigree of a currently executing strand.

Conceptually, as a program executes, the pedigree for the currently executing strand changes at the boundaries of maximal strands. Recall that maximal strand boundaries occur at each cilk_spawn, cilk_sync, and at each grain of a cilk_for.

Pedigrees satisfy three key properties:

• Uniqueness: Every maximal strand in an execution DAG has a distinct pedigree.

• Lexicographic ordering: In any serial execution of an Intel® Cilk™ Plus program, the pedigrees of strands increase in a "dictionary" ordering.

• Determinism: For any execution DAG generated by a strand-invariant program, the pedigree for each strand in the DAG is always the same across multiple runs of the program.

For example, consider following Intel® Cilk™ Plus program.

int fib(int n) {
   if (n < 2) {
      return n;
   }
   else {
      int x, y;
      x = cilk_spawn fib(n-1);
      y = fib(n-2);
      cilk_sync;
      return x+y;
  }
}

int main(void) {
   int ans = fib(4);
   printf(“fib(4) = %d\n”, ans);
   return 0;
}

This program generates the following execution DAG, which has 13 strands, labeled A through M. One valid way of assigning pedigrees to strands is shown below. Strand H has a pedigree of [0, 0, 2]. The first term of 0 is the most-significant term, and the last term of 2 is the least-significant term. Property 1 is satisfied because each strand has a unique pedigree. Property 2 is satisfied because a serial execution of the program executes strands in alphabetical order (from A to M), and the pedigrees for each strand are increasing lexicographically. Finally, since this program is strand-invariant, Property 3 guarantees that every execution of the program assigns the same pedigree to each strand each the program runs.