共有メモリマシン上での 並列計算プログラミング 金田憲二

背景 速く計算ができると色々うれしいはず 一つ一つのプロセッサはまだまだ遅い 並列に計算することで高速化 1個のプロセッサで1000時間かかる計算を、1000個のプロセッサを使って1時間で!!!

どうやって並列計算をするのか 並列計算機を手に入れなければいけない プログラムを記述しなければいけない ※当然、実現したい計算の種類によって 最適な手段は異なる

並列計算機の種類 共有メモリマシン クラスタ 例）SunFire15K ネットワークでつながった数百～数千台の計算機 例）IBM BladeCenter 例）Sun V210 x 128

並列計算を記述する方法 普通の言語 自動並列化コンパイラ 並列プログラミング言語 例）C/Java + スレッド/通信ライブラリ とても大変 ユーザは並列計算を意識しないで済む 性能などの面で問題がある 並列プログラミング言語 例）Cilk、 Linda、KLIC、Stackthreads、… 簡便に高性能な並列計算を実現可能

今回取りあげるのは Cilk言語 90年代後半にMITで研究・開発 C言語にいくつかのキーワードを追加 共有メモリマシン上で動作 再帰関数などは結構簡単に並列化 例）チェスの次手の探索

発表の概要 ～Cilk言語のチュートリアル～ フィボナッチの並列化 言語の詳細 実装の概要

フィボナッチの並列化

フィボナッチ数を計算する Cプログラム #include <stdlib.h> #include <stdio.h> int fib (int n) { if (n<2) return (n) int x, y; x = fib (n-1); y = fib (n-2); return (x+y); } int main (int args, char *argv[]) { int n, result; n = atoi(argv[1]); result = fib (n); printf(“Result: %d\n”, result); return 0; }

並列に計算できる箇所は？ fib (3); fib (2); fib (4); fib (3); fib (5); fib (4); データ依存がない fib (1); fib (0);

並列に計算できる箇所は？ この2つの関数の呼び出しは 並列に実行できる #include <stdlib.h> #include <stdio.h> int fib (int n) { if (n<2) return (n) int x, y; x = fib (n-1); y = fib (n-2); return (x+y); } int main (int args, char *argv[]) { int n, result; n = atoi(argv[1]); result = fib (n); printf(“Result: %d\n”, result); return 0; } この2つの関数の呼び出しは 並列に実行できる

Cilkで記述された 並列フィボナッチ #include <stdlib.h> #include <stdio.h> #include <cilk.h> cilk int fib (int n) { if (n<2) return (n) else { int x, y; x = spawn fib (n-1); y = spawn fib (n-2); sync; return (x+y); } } cilk int main (int args, char *argv[]) { int n, result; n = atoi(argv[1]); result = spawn fib (n); sync; printf(“Result: %d\n”, result); return 0; }

プログラム中に現れる キーワード cilk spawn sync

cilk spawnやsyncを呼び出す関数の先頭につける識別子 cilk int f() { … } ※以降この識別子のついた関数をcilk procedureと呼ぶ

f (x)の終了を待たずにg ()も実行する spawn 並列関数呼び出し 関数の終了を待たずに呼び出し元が実行を続ける spawn f (x); g (); f (x)の終了を待たずにg ()も実行する

sync spawnした関数の終了を待つ y = spawn f (x); … sync; printf (“%d”, y);

コンパイル コマンド名：cilk gccと同じコンパイルオプションが使える $ cilk filename $ cilk -g -Wall -O2 fib.cilk -o cilk

実行 --nprocで計算機のプロセッサ数を指定 例）64プロセッサ上でのfib (32)の計算 $ filename --nproc n args $ ./fib --nproc 64 32 ※fib (32)の計算はSunFire 15K上で　　　約55倍のスピードアップ

プロファイリング (1/2) 以下のオプションをつけてコンパイル 以下のオプションをつけて実行 --cilk-profile --cilk-critical-path 以下のオプションをつけて実行 --stats level

プロファイリング (2/2) $ cilk -cilk-profile -cilk-critical-path -O2 fib.cilk -o fib $ ./fib --nproc 4 --stats 1 30 Result: 832040 RUNTIME SYSTEM STATISTICS Wall-clock running time on 4 processors: 2.593270 s Total work = 10.341069 s Total work (accumulated) = 7.746886 s Critical path = 779.588000 us Parallelism = 9937.154003

言語の詳細

言語の詳細 Storage allocation Locking Inlets Aborting Timer （プログラム例：n-queens）

Storage Allocation (1/2) Stack memoryへの割り当て Cilk procedure内では C関数内では ※関数がreturnする時に自動的に開放される ptr = Cilk_alloca(size)； ptr = alloca(size)；

Storage Allocation (2/2) Heap memoryへの割り当て 通常のCと同じ ptr = malloc(size)； free(ptr)；

Locking Cilkは相互排他ロックを提供する スレッド間で共有されるデータへのatomicなアクセスを可能にする

Data raceの例 (1/2) foo()が2を返す（ことを意図した）プログラム cilk int foo (void) { int x = 0; spawn bar(&x); x = x + 1; sync; return (x); } cilk void bar (int *px) { *px = *px + 1; return; }

Data raceの例 (2/2) 実行によっては、値が正しく更新されない cilk int foo (void) { int x = 0; spawn bar(&x); x = x + 1; sync; return (x); } cilk void bar (int *px) { *px = *px + 1; return; } (2) xをread (= 0) (1) xをread (= 0) (3) xへwrite (= 1) (4) xへwrite (= 1) (5) 1をreturn

API (1/2) 型 ロックを初期化する関数 ロックを取得する関数 ロックを開放する関数 Cilk_lockvar Cilk_lock_init(ｌ) Cilk_lock (ｌ) Cilk_unlock(ｌ)

API (2/2) ロックを取得できるのは同時に一つの　　スレッド ロックを取得できなかったスレッドは　　　　　　　　　　　そのロックが開放されるまで待機

プログラム例1 #include <cilk-lib.h> Cilk_lockvar mylock; { Cilk_lock_init(mylock); Cilk_lock(mylock); /* critical section (atomicに実行したいコード) */ Cilk_unlock(mylock); }

プログラム例2 #include <cilk-lib.h> Cilk_lockvar mylock; cilk int foo (void) { int x = 0; Cilk_lock_init(mylock); spawn bar(&x); Cilk_lock(mylock); x = x + 1; Cilk_unlock(mylock); sync; return (x); } cilk void bar (int *px) { Cilk_lock (mylock); *px = *px + 1; Cilk_unlock(mylock); return; }

Inlets spawnの返り値に使える操作というものが制限されている そのためにspawnの返り値を操作するための特殊な機構

spawnに対する制限 (1/2) spawnの返り値に対して許されている操作は = *= /= %= += -= = 　　 *= 　 /= %= += -= &= ^= |= <<= >>= 　のみ y += spawn f (x); 旨い

spawnに対する制限 (2/2) 以下のような操作は許されていない z = spawn f (x) + spawn g (y) h (spawn f (x)); ただしhはCの関数

Inlet spawnの返り値を処理する特殊な関数 Cilk procedure内で定義される spawnの返り値を渡すことができる cilk int f (int x) { inlet int g (int y) { … } z = g (spawn h())

プログラム例 cilk int fib (int n) { int x = 0; inlet void summer (int result) { x += result; } if (n < 2) return n; summer (spawn fib (n-1)); summer (spawn fib (n-2)); sync; return (x);

注意点 (1/2) inlet中でspawnやsyncを呼び出すことはできない cilk int f (int x) { inlet int g (int y) { z = spawn h(); } z = g (spawn h())

注意点 (2/2) Implicit atomicity spawnの呼び出したスレッドと同じスレッドがinlet内を処理する cilk int fib (int n) { inlet void summer (int result) { x += result; } summer (spawn fib (n-1)); summer (spawn fib (n-2)); xへのアクセスはatomicであることが保障されている

Aborting spawnしたCilk procedureを中断させる機構 探索の枝狩りなどの目的に使用する

Abort inlet内にabortプリミティンブをいれる cilk int f (int n) { inlet void g (int x) { ... abort; } …

プログラム例 cilk void search(int n) { inlet void catch() { if (解が発見された) { abort; } … } for (x in 探索空間) { catch (spawn search (x));

注意点 abortが呼ばれた時点でまだspawnされていないタスクは中断されない (3) abortを呼び出す cilk void foo(int n) { inlet void bar() { abort; } bar (spawn baz(17)); spawn baz(28); (3) abortを呼び出す (1) baz(17)をspawn (2) baz(17)が終了 (4) baz(28)をspawn

Timer 型 wall-clock timeを返す関数 Cilk_timeを秒に変換する関数 Cilk_time t = Cilk_get_wall_time() sec = Cilk_time_sec(t)

プログラム例：n-queens (1/8) N×Nのチェスボード上で以下の条件を満たすN個のQueenの配置を求める

プログラム例：n-queens (2/8) #include <stdlib.h> #include <stdio.h> #include <string.h> #include <cilk.h> #include <cilk-lib.h> …

プログラム例：n-queens (3/8) … int safe(char *config, int i, int j) { int r, s; for (r = 0; r < i; r++) { s = config[r]; if (j==s || i-r==j-s || i-r==s-j) { return 0; } return 1;

プログラム例：n-queens (4/8) … cilk char *nqueens(char *config, int n, int i) { char *new_config; char *done = NULL; int j; inlet void catch(char *res) { if (res != NULL) { if (done == NULL) { done = res; } abort; }

プログラム例：n-queens (5/8) … if (i==n) { char *result; /* put this good solution in heap, and return a pointer to it */ result = malloc(n*sizeof(char)); memcpy(result, config, n*sizeof(char)); return result; }

プログラム例：n-queens (6/8) … /* try each possible position for queen <i> */ for (j=0; j<n; j++) { new_config = Cilk_alloca((i + 1) * sizeof(char)); memcpy(new_config, config, i*sizeof(char)); if (safe(new_config, i, j)) { new_config[i] = j; catch(spawn nqueens(new_config, n, i+1)); } if (done != NULL) { break; } sync; return done; }

プログラム例：n-queens (7/8) … cilk int main(int argc, char *argv[]) { int n; char *config; char *result; n = atoi(argv[1]); config = Cilk_alloca(n*sizeof(char)); result = spawn nqueens(config, n, 0); sync;

プログラム例：n-queens (8/8) … if (result != NULL) { int i; printf("Solution: "); for (i=0; i<n; i++) { printf(“%2d\n”, result[i]); } } else { printf(“No solutions!\n”); } return 0;

実装の概要

実装の概要 work-stealingによる負荷分散 idleなプロセッサはランダムに選んだプロセッサからタスクを盗む

実装の概要 work-stealingによる負荷分散 idleなプロセッサはランダムに選んだプロセッサからタスクを盗む

実装の概要 work-stealingによる負荷分散 idleなプロセッサはランダムに選んだプロセッサからタスクを盗む

参考文献 Cilk 5.3.2 Reference Manual Supercomputing Technologies Group MIT Laboratory for Computer Science http://supertech.lcs.mit.edu/cilk 2001

コンパイル方法 foo.cilk foo.c foo.o foo cilk2c gcc ld Cilk runtime system