Cilk-NOW 米澤研究室 金田憲二 “Adaptive and Reliable Parallel Computing on Networks of Workstations” Robert D. Blumofe (Univ. of Texas) Philip A. Lisiecki (MIT)

Presentation on theme: "Cilk-NOW 米澤研究室 金田憲二 “Adaptive and Reliable Parallel Computing on Networks of Workstations” Robert D. Blumofe (Univ. of Texas) Philip A. Lisiecki (MIT)"— Presentation transcript:

1 Cilk-NOW 米澤研究室 金田憲二 “Adaptive and Reliable Parallel Computing on Networks of Workstations” Robert D. Blumofe (Univ. of Texas) Philip A. Lisiecki (MIT) Proceedings of the USENIX Annual Technical Conference, 1997

2 Cilk言語 C言語に並列性を表現するためのプリミティブを加えたもの DAG型計算モデル

3 Cilk-NOW 遊休のPC上でCilkプログラムを実行するランタイムシステム 分散版Cilk PCの参加・脱退にあわせた並列度の調整
耐故障性

4 発表の概要 Cilk言語 並列度の調整 耐故障性 まとめ 動作例 work stealingスケジューラ PCの参加・脱退時の処理
再実行・チェックポイント まとめ

5 thread Fib (cont int k, int n) {
if (n <2) { send_argument (k,n); } else { cont int x, y; spawn_next Sum (k, ?x, ?y); spawn Fib (x, n-1); spawn Fib (y, n-2) }} thread Sum (cont int k, int x, int y) { send_argument (k, x+y); }

6 Cilkの文法 (1/3) spawn T (args …) spawn_next T (args …) 意味：スレッドTを並列に実行
実装：ランタイムがヒープ上にclosureを生成 Sum Fib Join counter k 空のArgument　slots 空のArgument　slots k Arguments Arguments n=9 ※Join counter:空のArgument　slots数(0で実行可能)

7 Cilkの文法 (3/3) cont continuation 空のempty argument slotへの参照
※closureへのポインタと 　　argument slotへのオフセットからなる Sum 2 k Fib x n=8 continuation Fib y n=7

8 Cilkの文法 (2/3) send_argument(k, value)
continuation kで指定されたargument slotにvalueを送る

9 動作例 Fib k n=9 Sum 2 k spawn_next Fib x n=8 spawn spawn Fib y n=7

10 動作例 Sum 2 k Fib x n=8 Fib y n=7

11 動作例 Sum 1 k 21 Fib y n=7

12 動作例 Sum k 21 13

13 work stealingスケジューラ (1/3)
各プロセスは ready dequeをもつ 実行可能なclosureが格納される join counterが0になったclosureは　　　　　　　 dequeの先頭におかれる dequeの先頭から実行されていく

14 work stealingスケジューラ (2/3)
ready dequeが空になるとwork stealingが起こる thiefはランダムにvictimを選択 steal requestをvictimに送信 victimは ready dequeが空でないなら，dequeの末尾のclosureをthiefに委譲 ready dequeが空なら，thiefに再トライを要求 ※盗む側：thief　　　盗まれる側:victim

15 work stealingスケジューラ (3/3)
なぜ末尾のclosureから盗むのか？ ヒューリスティック的な根拠 末尾のclosureほど多くspawnする場合が多い ⇒末尾のclosureほど大量のworkを含む ⇒なるべく小さい通信量で，大量のworkを盗める アルゴリズム的な根拠 次の3枚のスライドで説明する

16 work stealingの解析 (1/3) DAG型計算モデル sequential execution spawn spawn_next
continuation instruction thread procedure

17 work stealingの解析 (2/3) well structuredな計算とは 個々のprocedureは親にのみ値を送信
かつ，値の送信はprocedure中の最後のthreadの最後の操作

18 work stealingの解析 (3/3) well structuredな計算の実行時間は T1/P + T∞とモデル化できる
　　T1 : DAG中のinstruction数 　 　 (1プロセスにおける実行時間) T∞ : DAGの最長パス長 　　　　　　　 (critical path長) DAG上のcritical pathとなるclosureは， ready dequeの末尾に位置することより導きかれる

19 並列度の調整 遊休なPC上で（複数の）Cilkプログラムを走らせることを目指す PCの参加，脱退を効率よく扱うことを目指す プログラム A
B プログラム C

20 並列度の調整方法の概要 新たに参加するプロセスは， 他のプロセスからclosureを盗む 脱退するプロセスは，
必要に応じてcontinuationの参照先を更新 ※waiting closureの委譲を扱う必要がある

21 並列度の調整方法の詳細 work stealing方法の変更 脱退時の処理 subcomputation・result closureの導入

22 work stealing方法の変更 (1/5)
subcomputation ready, waiting, assigned poolから構成される globalにuniqueなnameを持つ PC名+localにuniqueな番号 work steal時に生成される closureの全てのcontinuationは同じsubcomputation中のclosureを参照する 異なるsubcomputation間の通信は，特殊なresult closureを中継させる

23 work stealing方法の変更 (2/5)
thiefは， subcomputationを生成 stealリクエストをvictimに送信 subcomputation r:j用ののclosureを盗みたい victim s thief r subcomputation s:i subcomputation r:j assigned waiting ready ready waiting assigned

24 work stealing方法の変更 (3/5)
victimは， ready poolの空でないsubcomputationをround-robinに選択 ready poolの末尾のclosureをassigned poolに移動 thiefの名前とthiefのsubcomputationの名前を保持 victim s thief r subcomputation s:i subcomputation r:j assigned waiting ready ready waiting assigned

25 work stealing方法の変更 (3/5)
victimは， ready poolの空でないsubcomputationをround-robinに選択 ready poolの末尾のclosureをassigned poolに移動 thiefの名前とthiefのsubcomputationの名前を保持 thief name victim s thief subcomp. thief r subcomputation s:i subcomputation r:j assigned waiting ready ready waiting assigned r　r:j

26 work stealing方法の変更 (4/5)
victimからthiefにclosureを送信 thiefはvictim workerの名前を記録 thiefはresult closureを生成 盗んできたclosure中のcontinuationを，　　　 　　result closureを参照するように変更する s victim name victim s thief r subcomputation s:i subcomputation r:j assigned waiting ready ready waiting assigned r　r:j result closure

27 work stealing方法の変更 (5/5)
3つのpoolがともに空になると終了 subcomputation r:jが終了 ack subcomp.の名前を含んだメッセージをvictimに 送信 victim workerのassigned poolから取り除かれる assigned pool中で同じsubcomp.のものを見つける ackをthiefに送信 thiefはackを受信するとsubcomp.を開放 victim s thief r s subcomputation s:i subcomputation r:j assigned waiting ready ready waiting assigned r　r:j

28 work stealing方法の変更 (5/5)
3つのpoolがともに空になると終了 subcomputation r:jが終了 ack subcomp.の名前を含んだメッセージをvictimに 送信 victim workerのassigned poolから取り除かれる assigned pool中で同じsubcomp.のものを見つける ackをthiefに送信 thiefはackを受信するとsubcomp.を開放 victim s thief r subcomputation s:i ready waiting assigned

29 脱退時の処理 subcomputationの委譲 subcomputationのserialize continuationの更新
委譲先のプロセスは， victim workerにメッセージを送信 victim closure中のthief subcomputationを変更 assigned pool中の全てのthief workerにメッセージを送信 victim worker nameを変更

30 脱退時の処理 worker t subcomputation t:k ready waiting assigned s s:i
worker s worker u t subcomputation s:i ready waiting assigned r　r:j worker r s subcomputation r:j assigned waiting ready

31 脱退時の処理 worker t subcomputation t:k ready waiting assigned s s:i
worker s worker u worker u t subcomputation s:i ready waiting assigned r　r:j worker r s subcomputation r:j assigned waiting ready

32 脱退時の処理 worker t u s:i 更新 subcomputation t:k ready waiting assigned
worker s worker u 更新 t subcomputation s:i ready waiting assigned 更新 r　r:j worker r s u 更新 subcomputation r:j assigned waiting ready

33 耐故障性 PCがクラッシュしてもプログラムが動作し続けることを保障する ⇒subcomputationの再実行 　+非同期チェックポイント

34 subcomputationの再実行 (1/2)
subcomputationは終了するまで他のsubcomputationに影響しないようにする subcomputationの終了時のみreturn valueを送信する ※well-structuredな計算なら通常 transaction処理を行う return valueを受け取ったときにcommit

35 subcomputationの再実行 (2/2)
故障が発見されると， 消失したsubcomputationを指すcontinuationをもつsubcomputationをabort abortしたsubcomputationを指すcontinuationをもつsubcomputationもabort 消失したsubcomputationから指されるcontinuationをもつsubcomputationは，消失したsubcomputationを再実行 ※ PCの故障は中央サーバが検出

36 worker t 再実行 subcomputation t:k ready waiting assigned s　s:i worker s t subcomputation s:i ready waiting assigned r　r:j worker r s subcomputation r:j assigned waiting ready abort

37 非同期チェックポイント 再実行のオーバヘッドを回避 subcomputationごとに定期的に状態を保存
c.f.)DAGのルートに近いsubcomputationの再実行 subcomputationごとに定期的に状態を保存

38 関連研究 ここ数年でCilk-NOWを参照している論文 SilkRoad[2000] Satin[2001] Concert[2002]
Cilk-NOW + SoftwareDSM Satin[2001] 広域環境上で効率の良いScheduling方式 Concert[2002] 安全な実行環境を提供することを目指す

39 まとめ 遊休のPC上でCilkプログラムを実行するランタイムシステム 分散版Cilk PCの参加・脱退にあわせた並列度の調整 耐故障性

40 疑問点など thief・victim間の参照は常に正しい？ 各プログラムへの公平な資源の割り当て 盗み・脱退・故障が同時に起こる場合などは？
現実的には十分？ 各プログラムへの公平な資源の割り当て 現在アルゴリズムを考案中とのこと