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

Presentation on theme: "共有メモリマシン上での 並列計算プログラミング"— Presentation transcript:

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

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

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

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

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

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

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

8 フィボナッチの並列化

9 フィボナッチ数を計算する 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; }

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

11 並列に計算できる箇所は？ この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つの関数の呼び出しは 並列に実行できる

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

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

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

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

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

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

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

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

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

21 言語の詳細

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

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

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

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

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

27 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

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

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

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

31 プログラム例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; }

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

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

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

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

36 プログラム例 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);

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

38 注意点 (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であることが保障されている

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

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

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

42 注意点 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

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

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

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

46 プログラム例：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;

47 プログラム例：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; }

48 プログラム例：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; }

49 プログラム例：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; }

50 プログラム例：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;

51 プログラム例：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;

52 実装の概要

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

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

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

56 参考文献 Cilk 5.3.2 Reference Manual
Supercomputing Technologies Group MIT Laboratory for Computer Science 2001

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