Mercurial > hg > Papers > 2018 > parusu-master

comparison slide/slide.md @ 89:bc7d11285a4a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix slide
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Mon, 12 Feb 2018 14:48:30 +0900
parents 3c127f675c45
children a9885c038bb6
comparison
equal deleted inserted replaced
88:3c127f675c45 89:bc7d11285a4a
2 author: 伊波 立樹 2 author: 伊波 立樹
3 profile: 琉球大学理工学研究科 河野研 3 profile: 琉球大学理工学研究科 河野研
4 lang: Japanese 4 lang: Japanese
5 code-engine: coderay 5 code-engine: coderay
6 6
7 ## メタ計算を用いた並列処理 7 ## 並列処理の重要性
8 - 並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている 8 - 並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている
9 - しかし、並列処理のチューニングや信頼性を保証するのは難しい 9 - しかし、並列処理のチューニングや信頼性を保証するのは難しい
10 - スレッド間の共通資源の競合などの非決定的な実行 10 - 共通資源の競合などの非決定的な実行が発生するため、従来のテストやデバッグではテストしきれない部分が残ってしまう
11 - 従来のテストやデバッグではテストしきれない部分が残ってしまう
12 - GPU などのアーキテクチャに合わせた並列プログラミングの記述 11 - GPU などのアーキテクチャに合わせた並列プログラミングの記述
13 12
14 ## Gears OS 13 ## Gears OS
15 - 本研究室では処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している 14 - 本研究室では処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
16 - 並列処理の Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される 15 - 並列処理の Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される
17 - 計算をノーマルレベルとメタレベルに階層化、 信頼性と拡張性をメタレベルで保証する 16 - 計算をノーマルレベルとメタレベルに階層化、 信頼性と拡張性をメタレベルで保証する
18 - 並列処理の信頼性を通常の計算(ノーマルレベル) に保証 17 - 並列処理の信頼性を通常の計算(ノーマルレベル) に保証
19 - CPU、GPU などの実行環境の切り替え、データ拡張等のを提供 18 - CPU、GPU などの実行環境の切り替え、データ拡張等を提供
20 19
21 ## Gears OS 20 ## Gears OS
22 - 本研究ではGears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う 21 - 本研究ではGears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う
23 - また、並列処理を行う例題を用いて評価、 OpenMP、 Go 言語との比較を行う 22 - また、並列処理を行う例題を用いて評価、 OpenMP、 Go 言語との比較を行う
24 23
25 ## Code Gear、 Data Gear 24 ## Code Gear/Data Gear
26 - Gears OS は Code Gear、 Data Gear という単位で構成される 25 - Gears OS は Code Gear、 Data Gear という単位で構成される
27 - Code Gear はプログラムの処理そのものを表す 26 - Code Gear はプログラムの処理そのものを表す
28 - Data Gear はデータそのものを表す 27 - Data Gear はデータそのものを表す
29 - Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する 28 - Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する
30 - Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う 29 - Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う
63 - 下記のコードでは Code Gear を2つ定義し、 cg0 から cg1 への継続を示している 62 - 下記のコードでは Code Gear を2つ定義し、 cg0 から cg1 への継続を示している
64 63
65 ``` c 64 ``` c
66 __code cg0(int a, int b) { 65 __code cg0(int a, int b) {
67 goto cg1(a+b); 66 goto cg1(a+b);
68
69 } 67 }
70 68
71 __code cg1(int c) { 69 __code cg1(int c) {
72 goto cg2(c); 70 goto cg2(c);
73 } 71 }
75 73
76 ## Context 74 ## Context
77 - Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear 75 - Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear
78 - 従来のOS のスレッドやプロセスに対応し、以下の要素を定義している 76 - 従来のOS のスレッドやプロセスに対応し、以下の要素を定義している
79 - 独立したメモリ空間 77 - 独立したメモリ空間
80 - Code Gear、 Data Gear へのポインタ 78 - Code/Data Gear へのポインタ
81 - 並列実行用の Task 情報 79 - 並列実行用の Task 情報
82 - Data Gear の型情報 80 - Data Gear の型情報
83 - Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする 81 - Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする
84 82
85 ## Data Gear の表現 83 ## Data Gear の表現
104 ``` 102 ```
105 103
106 ## stub Code Gear 104 ## stub Code Gear
107 - Data Gear にアクセスするにはContext を経由する 105 - Data Gear にアクセスするにはContext を経由する
108 - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある 106 - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
109 - Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub Code Gear を用意する 107 - Gears OS ではメタレベルで通常の Code Gear で必要な Data Gear を Context から取り出す処理を行う stub Code Gear を用意している
110 108
111 ``` c 109 ``` c
112 // normal level Code Gear 110 // normal level Code Gear
113 __code cg0(struct Context* context, struct Integer integer, struct Queue queue) { 111 __code cg0(struct Context* context, struct Integer integer, struct Queue queue) {
114 ... 112 ...
127 125
128 ## Context での stub Code Gear の記述の問題点 126 ## Context での stub Code Gear の記述の問題点
129 - stub Code Gear は Context から Code Gear と Data Gear の全ての組合せを展開して記述する必要がある 127 - stub Code Gear は Context から Code Gear と Data Gear の全ての組合せを展開して記述する必要がある
130 - しかし、 Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた 128 - しかし、 Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた
131 - Data Gear は番号で指定するため、 Code Gear が どの Data Gear の番号に対応しているかを記述する必要がある 129 - Data Gear は番号で指定するため、 Code Gear が どの Data Gear の番号に対応しているかを記述する必要がある
132 - 自動化するために、同じ番号の Data Gear を使いまわす問題 130 - stub Code Gear を自動生成するために、同じ番号の Data Gear を使いまわす問題
133 - そのため Gears OS のモジュール化する仕組みとして **Interface** を導入した 131 - そのため Gears OS のモジュール化する仕組みとして **Interface** を導入した
134 132
135 ## Interface 133 ## Interface
136 - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear 134 - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear
137 - stub Code Gear はInteface を実装した Code Gear で決まった形になるため、自動生成が可能である 135 - stub Code Gear はInteface を実装した Code Gear で決まった形になるため、自動生成が可能である
199 } 197 }
200 ``` 198 ```
201 199
202 ## Interface を利用した Code Gear の呼び出し 200 ## Interface を利用した Code Gear の呼び出し
203 - Interface を利用した Code Gear への継続は `goto interface->method` で行われる 201 - Interface を利用した Code Gear への継続は `goto interface->method` で行われる
204 - ここでの **interface** は Interfaceの型で包んだポインタ、 **method** は実装した Code Gear に対応する 202 - ここでの **interface** は Interfaceの型で包んだData Gear、 **method** は実装した Code Gear に対応する
205 203
206 ``` 204 ```
207 __code code1() { 205 __code code1() {
208 Queue* queue = createSingleLinkedQueue(context); 206 Queue* queue = createSingleLinkedQueue(context);
209 Node* node = new Node(); 207 Node* node = new Node();
353 351
354 - カウンタの値が0になった実行可能な Task は TaskManager を通して Worker に送信される 352 - カウンタの値が0になった実行可能な Task は TaskManager を通して Worker に送信される
355 353
356 ## 並列構文 354 ## 並列構文
357 - 並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する 355 - 並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する
358 - この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述は好ましくない 356 - この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述では好ましくない
359 - Task の設定の記述は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である 357 - Task の設定は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である
360 - そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した 358 - そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した
361 - par goto 構文には引数として Input/Output Data Gear等を渡す 359 - par goto 構文には引数として Input/Output Data Gear等を渡す
362 - スクリプトによって Code Gear の Input/Output の数を解析する 360 - スクリプトによって Code Gear の Input/Output の数を解析する
363 361
364 ``` c 362 ``` c
370 368
371 ## CUDA への対応 369 ## CUDA への対応
372 - Gears OS は GPU での実行もサポートする 370 - Gears OS は GPU での実行もサポートする
373 - GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる 371 - GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる
374 - 今回は CUDA への実行のサポートをおこなった 372 - 今回は CUDA への実行のサポートをおこなった
375 - CUDA へ GPU を Device、 CPU を Host として定義する 373 - CUDA は GPU を Device、 CPU を Host として定義する
376 - CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する 374 - CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する
377 - 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた Code Gear を提供する 375 - 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた並列処理機構を提供する
378 376
379 ## CUDAWorker 377 ## CUDAWorker
380 - CUDA で実行する Task を受け取る Worker 378 - CUDA で実行する Task を受け取る Worker
381 - 初期化の際に CUDA ライブラリの初期化等を行う 379 - 初期化の際に CUDA ライブラリの初期化等を行う
382 380
400 398
401 ## CUDABuffer 399 ## CUDABuffer
402 - Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある 400 - Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある
403 - Device にデータ領域を確保するにはサイズの指定が必要 401 - Device にデータ領域を確保するにはサイズの指定が必要
404 - Data Gear には Meta Data Gear でデータのサイズを持っている 402 - Data Gear には Meta Data Gear でデータのサイズを持っている
405 - だが、Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう 403 - しかし、 Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう
406 - CUDA Buffer ではそのマッピングを行う 404 - CUDA Buffer ではそのマッピングを行う
407 - このマッピングは Task の stub Code Gear で行われる 405 - このマッピングは Task の stub Code Gear で行われる
408 406
409 <div style="text-align: center;"> 407 <div style="text-align: center;">
410 <img src="./images/cudaDataArchitecture.svg" alt="message" width="500"> 408 <img src="./images/cudaDataArchitecture.svg" alt="message" width="500">
411 </div> 409 </div>
412 410
413 ## CUDA での呼び出し 411 ## CUDA での呼び出し
414 - Gears OS では stub Code Gear で CUDA による実行を切り替える 412 - Gears OS では Task で実行される Code Gear の stub Code Gear で CUDA による実行を切り替える
415 - stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う 413 - stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う
416 - stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する 414 - stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する
417 415
418 ## Gears OS の評価 416 ## Gears OS の評価
419 - 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った 417 - 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った
604 - Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する 602 - Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する
605 - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある 603 - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある
606 - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う 604 - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う
607 - OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。 605 - OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。
608 - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう 606 - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう
609 - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成セずに関数呼出しを行う等の最適化が必要 607 - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成せずに関数呼出しを行う等の最適化が必要
610 - 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった 608 - 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった
611 - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持サれているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデーの通信を行う 609 - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う