Gnuplot

Task を Input Data Gear として
Task内の idgCountをチェックする
揃っている場合、 Worker の Queue に
Task を Input Data Gear としてTaskManager の spawn を呼び出す
Task が待っている Data Gear のカウンタである idgCount をチェックする
idgCount が0の場合 Data Gear が揃っているので Worker の Queue に Task を送信する

@@ -284,18 +263,15 @@ - TaskManager から送信された Task を一つずつ取得して実行する

Worker は Queue から Task を取得する
Worker の Context から
Worker の Context からTask の Context へ入れ替える
Task に設定されている Code Gear を実行
Task の Output Data Gear の書き出し
Task Context から
Task Context から Worker の Context へ入れ替える
Worker は再び Queue から Task を取得する

@@ -341,8 +317,13 @@ - この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述では好ましくない - Task の設定は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である - そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した + +## par goto 構文 +- par goto 構文を記述すると新しく Context を生成し、TaskManager を通して Worker に送信される - par goto 構文には引数として Input/Output Data Gear等を渡す - スクリプトによって Code Gear の Input/Output の数を解析する +- Task は **__exit** に継続することで終了する + - Gears OS は Output Data Gear 生成した時点で終了するため**__exit** に直接継続せずに Data Gear を書き出す処理に継続する ``` c __code code1(Integer *integer1, Integer * integer2, Integer *output) { @@ -413,11 +394,11 @@ ## Twice - Twice は与えられた整数配列を2倍にする例題である - 並列実行の依存関係がなく、並列度が高い課題である - -## Twice の結果 - 要素数 2^27 - CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する - GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開 + +## Twice の結果 - 1 CPU と 32 CPU では約27.1倍の速度向上が見られた - GPU 実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上、通信時間を含めると 16 CPU より遅い - 通信時間がオーバーヘッドになっている @@ -466,11 +447,11 @@ ## BitonicSort - 並列処理向けのソートアルゴリズム - 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする - -## BitonicSort の結果 - 要素数 2^24 - CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する - GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開 + +## BitonicSort の結果 - 1 CPU と 32 CPU で約22.12倍の速度向上 - GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった - 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった @@ -552,6 +533,35 @@ } ``` +## まとめ +- Gears OS の並列処理機構の実装を行った +- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった +- par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった +- 2つの例題である程度の台数効果が出ることを確認した + +## 今後の課題 +- Gears OS の並列処理の信頼性の保証、チューニングを行う + +## 今後の課題 +- Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する + - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある + - モデル検査は CbC で記述されたモデル検査器である akasha を使用して行う。モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う + +## 今後の課題 +- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった + - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う + +## 今後の課題 +- OpenMP、 Go で Twice を実装し、 Gears OS の性能比較を行った +- その結果、 Gears OS が 1CPU での動作が遅いということがわかった。 + - par goto 文を使用する度に Context を生成するため、ある程度の時間がかかってしまう + - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成せずに関数呼出しを行う等の最適化が必要 + +

+ +

stub Code Gear

Interface の実装例

Interface を利用した Code Gear の呼び出し

par goto 構文

Twice の結果

BitonicSort の結果

OpenMP との比較

Go 言語との比較

まとめ

今後の課題

今後の課題

今後の課題

今後の課題