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

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

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

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

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

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で実行可能)

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

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

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

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

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

動作例 Sum k 21 13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

脱退時の処理 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

脱退時の処理 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

脱退時の処理 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

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

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

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

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

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

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

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

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