ペディグリー (系図)

インテル® Cilk™ Plus プログラムの実行では、ペディグリー (64 ビット整数の可変長シーケンス) により個々の最大ストランドが識別されます。 インテル® Cilk™ Plus は、現在実行中のストランドのペディグリーを問い合わせることができる API を提供しています。

概念的には、プログラムの実行において、現在実行中のストランドのペディグリーは最大ストランド境界で変わります。最大ストランド境界は、cilk_spawn、cilk_sync、および cilk_for の各チャンクで発生します。

ペディグリーには、3 つの主な特性があります。

• 一意: 実行 DAG 中の各最大ストランドのペディグリーは異なります。

• 辞書順序: インテル® Cilk™ Plus プログラムのシリアル実行で、ストランドのペディグリーは「辞書」順序で増加します。

• 決定論性: ストランド不変プログラムにより生成される実行 DAG において、DAG 中の各ストランドのペディグリーは、プログラムを実行するたびに常に同じになります。

例えば、次のインテル® Cilk™ Plus プログラムについて考えてみます。

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;
}

このプログラムは、ラベル A ～ M までの 13 のストランドを含む、実行 DAG を生成します。次に、ストランドにペディグリーを割り当てる 1 つの有効な方法を示します。ストランド H のペディグリーは [0, 0, 2] です。最初の 0 は最上位、最後の 2 は最下位を示します。各ストランドのペディグリーは一意なので特性 1 を満たします。そして、プログラムのシリアル実行は、ストランドをアルファベット順 (A から M の順) に実行し、各ストランドのペディグリーは辞書順序で増加するため、特性 2 も満たします。最後に、このプログラムはストランド不変なので、特性 3 により、プログラムを実行するたび、各ストランドに常に同じペディグリーが割り当てられることが保証されます。