77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 title: Gears OS の並列処理
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 author: 伊波 立樹
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 profile: 琉球大学理工学研究科 河野研
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 lang: Japanese
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 code-engine: coderay
|
|
82
|
6
|
|
83
|
7 ## メタ計算を用いた並列処理
|
|
|
8 - 並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている
|
|
|
9 - しかし、並列処理のチューニングや信頼性を保証するのは難しい
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 - スレッド間の共通資源の競合などの非決定的な実行
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 - 従来のテストやデバッグではテストしきれない部分が残ってしまう
|
|
83
|
12 - GPU などのアーキテクチャに合わせた並列プログラミングの記述
|
|
|
13
|
|
|
14 ## Gears OS
|
|
87
|
15 - 本研究室では処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
|
|
|
16 - 並列処理の Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される
|
|
|
17 - 計算をノーマルレベルとメタレベルに階層化、 信頼性と拡張性をメタレベルで保証する
|
|
83
|
18 - 並列処理の信頼性を通常の計算(ノーマルレベル) に保証
|
|
|
19 - CPU、GPU などの実行環境の切り替え、データ拡張等のを提供
|
|
|
20
|
|
|
21 ## Gears OS
|
|
84
|
22 - 本研究ではGears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う
|
|
87
|
23 - また、並列処理を行う例題を用いて評価、 OpenMP、 Go 言語との比較を行う
|
|
84
|
24
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 ## Code Gear、 Data Gear
|
|
87
|
26 - Gears OS は Code Gear、 Data Gear という単位で構成される
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 - Code Gear はプログラムの処理そのものを表す
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 - Data Gear はデータそのものを表す
|
|
82
|
29 - Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する
|
|
|
30 - Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 <div style="text-align: center;">
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600">
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 </div>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35
|
|
87
|
36 ## メタ計算
|
|
|
37 - メタ計算 は通常の計算を実行するための計算
|
|
|
38 - 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等
|
|
|
39 - Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる
|
|
|
40 - メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる
|
|
|
41
|
|
|
42 ## Meta Gear
|
|
|
43 - メタ計算 は Code Gear の接続間に行われる
|
|
|
44 - メタ計算 の処理も Code/Data Gear で実現する
|
|
|
45 - この Gear を Meta Code/Data Gearと呼ぶ
|
|
|
46 - Meta Code Gear は メタ計算 のプログラム部分
|
|
|
47 - Meta Data Gear は Meta Code Gear で管理されるデータ部分
|
|
|
48 - Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う
|
|
|
49
|
|
|
50 <div style="text-align: center;">
|
|
|
51 <img src="./images/meta_cg_dg.svg" alt="message" width="850">
|
|
|
52 </div>
|
|
|
53
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 ## Continuation based C
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 - Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる
|
|
87
|
56 - CbC は Code Gear を用いて記述する事を基本とする
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 ## Continuation based C
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 - Code Gear の定義は ``__code CS名`` で行う
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 - Code Gear 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 - Code Gear の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 - このような環境を持たない継続を軽量継続と呼ぶ
|
|
87
|
63 - 下のコード例では Code Gear を2つ定義し、 cg0 から cg1 への継続を示している
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 ``` c
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 __code cg0(int a, int b) {
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 goto cg1(a+b);
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 }
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 __code cg1(int c) {
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 goto cg2(c);
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 }
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 ```
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 ## Context
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 - Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear
|
|
87
|
78 - 従来のOS のスレッドやプロセスに対応し、以下の要素を定義している
|
|
|
79 - 独立したメモリ空間
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 - Code Gear、 Data Gear へのポインタ
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 - 並列実行用の Task 情報
|
|
87
|
82 - Data Gear の型情報
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 - Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 ## Data Gear の表現
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 - Data Gear は構造体を用いて定義する
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 - メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 - Data Gear のメモリに確保する際のサイズ情報はこの型から決定する
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 ``` c
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 /* data Gear define */
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 union Data {
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 struct Timer {
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 union Data* timer;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 enum Code start;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 enum Code end;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 enum Code next;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 } Timer;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 struct TimerImpl {
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 double time;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 } TimerImpl;
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 ....
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103 };
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 ```
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105
|
|
82
|
106 ## Code Gear の stub Code Gear
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 - Data Gear にアクセスするにはContext を経由する
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
|
|
82
|
109 - Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub Code Gear を用意する
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 ``` c
|
|
87
|
112 // normal level Code Gear
|
|
|
113 __code cg0(struct Context* context, struct Integer integer, struct Queue queue) {
|
|
|
114 ...
|
|
|
115 }
|
|
|
116
|
|
|
117 // meta level stub Code Gear
|
|
|
118 __code cg0_stub(struct Context* context) {
|
|
|
119 // get data index number
|
|
|
120 Integer integer = &context->data[context->dataNum]->Integer
|
|
|
121 // get enum data
|
|
|
122 Queue* queue = &context->data[Queue]->Queue;
|
|
|
123 // continuation Code Gear
|
|
|
124 goto cg0(context, integer, queue);
|
|
|
125 }
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 ```
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128 ## Context での stub Code Gear の記述の問題点
|
|
87
|
129 - stub Code Gear は Context から Code Gear と Data Gear の組合せを展開して記述する必要がある
|
|
|
130 - しかし、 Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた
|
|
|
131 - Context は全ての Code と Data の集合を表現しているため、全て組合せを展開する必要がある
|
|
|
132 -
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 - そのため Gears OS のモジュール化する仕組みとして **Interface** を導入した
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 ## Interface
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136 - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear
|
|
82
|
137 - stub Code Gear は実装した Code Gear で決まった形になるため、自動生成が可能である
|
|
87
|
138 - Interface を導入することで、 Stack や Queue などのデータ構造を仕様と実装に分けて記述することが出来る
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 - Interface は Java のインターフェース、 Haskell の型クラスに対応する
|
|
82
|
140
|
|
|
141 ## Interface の定義
|
|
85
|
142 - Interface の定義には以下の内容を定義する
|
|
|
143 - 引数のData Gear 群
|
|
|
144 - 操作(API) 実行後に継続される Code Gear
|
|
86
|
145 - 操作(API) である Code Gear と Code Gear に渡す引数情報
|
|
85
|
146
|
|
|
147 ``` c
|
|
|
148 typedef struct Queue<Impl>{
|
|
|
149 // Data Gear parameter
|
|
|
150 union Data* queue;
|
|
|
151 union Data* data;
|
|
|
152 __code next(...);
|
|
|
153 __code whenEmpty(...);
|
|
|
154
|
|
|
155 // Code Gear
|
|
|
156 __code clear(Impl* queue, __code next(...));
|
|
|
157 __code put(Impl* queue, union Data* data, __code next(...));
|
|
|
158 __code take(Impl* queue, __code next(union Data*, ...));
|
|
|
159 __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...));
|
|
|
160 } Queue;
|
|
|
161 ```
|
|
82
|
162
|
|
|
163 ## Interface の実装
|
|
85
|
164 - Interface には複数の実装を行うことが出来る
|
|
|
165 - 実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う
|
|
|
166 - 代入する Code Gear を入れ替えることで別の実装を表現する
|
|
86
|
167 - 実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる
|
|
85
|
168
|
|
|
169 ```
|
|
|
170 Queue* createSingleLinkedQueue(struct Context* context) {
|
|
|
171 struct Queue* queue = new Queue(); // Allocate Queue interface
|
|
|
172 struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement
|
|
|
173 queue->queue = (union Data*)singleLinkedQueue;
|
|
|
174 singleLinkedQueue->top = new Element();
|
|
|
175 singleLinkedQueue->last = singleLinkedQueue->top;
|
|
|
176 queue->clear = C_clearSingleLinkedQueue;
|
|
|
177 queue->put = C_putSingleLinkedQueue;
|
|
|
178 queue->take = C_takeSingleLinkedQueue;
|
|
|
179 queue->isEmpty = C_isEmptySingleLinkedQueue;
|
|
|
180 return queue;
|
|
|
181 }
|
|
|
182 ```
|
|
|
183
|
|
|
184 ## Interface の実装例
|
|
|
185 - SingleLinkedQueue の put 実装
|
|
|
186 - 引数は Queue Interface の定義にあわせる
|
|
86
|
187 - 第1引数は 実装対象の Data Gear の型になる
|
|
|
188 - 第3引数の(...) は Output Data Gear を記述する
|
|
|
189 - ... は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある
|
|
85
|
190
|
|
|
191 ``` c
|
|
|
192 __code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) {
|
|
|
193 Element* element = new Element();
|
|
|
194 element->data = data;
|
|
|
195 element->next = NULL;
|
|
|
196 queue->last->next = element;
|
|
|
197 queue->last = element;
|
|
|
198 goto next(...);
|
|
|
199 }
|
|
|
200 ```
|
|
82
|
201
|
|
|
202 ## Interface を利用した Code Gear の呼び出し
|
|
86
|
203 - Interface を利用した Code Gear への継続は `goto interface->method` で行われる
|
|
|
204 - ここでの **interface** は Interfaceの型で包んだポインタ、 **method** は実装した Code Gear に対応
|
|
|
205 - この構文は実際にはスクリプトで変換される
|
|
|
206 - 変換後はメタレベルのコードになる
|
|
|
207
|
|
|
208 ```
|
|
|
209 __code code1() {
|
|
|
210 Queue* queue = createSingleLinkedQueue(context);
|
|
|
211 Node* node = new Node();
|
|
|
212 node->color = Red;
|
|
|
213 goto queue->put(node, queueTest2);
|
|
|
214 }
|
|
|
215 ```
|
|
|
216
|
|
|
217 ## Interface を利用した Code Gear の呼び出し(スクリプト変換後)
|
|
|
218 - Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す
|
|
|
219 - この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる
|
|
|
220 - 呼び出すCode Gear の引数情報に合わせて引数に格納
|
|
|
221
|
|
|
222 ```
|
|
|
223 __code code1(struct Context *context) {
|
|
|
224 Queue* queue = createSingleLinkedQueue(context);
|
|
|
225 Node* node = &ALLOCATE(context, Node)->Node;
|
|
|
226 node->color = Red;
|
|
|
227 Gearef(context, Queue)->queue = (union Data*) queue;
|
|
|
228 Gearef(context, Queue)->data = (union Data*) node;
|
|
|
229 Gearef(context, Queue)->next = C_queueTest2;
|
|
|
230 goto meta(context, queue->put);
|
|
|
231 }
|
|
|
232 ```
|
|
|
233
|
|
|
234 ## Interface での stub Code Gear
|
|
|
235 - メタ計算で格納された引数は、 stub Code Gear で Code Gear に渡される
|
|
|
236 - Interface を実装した Code Gear は stub Code Gear の自動生成が可能である
|
|
|
237
|
|
|
238 ``` c
|
|
|
239 __code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) {
|
|
|
240 Element* element = &ALLOCATE(context, Element)->Element;
|
|
|
241 element->data = data;
|
|
|
242 element->next = NULL;
|
|
|
243 queue->last->next = element;
|
|
|
244 queue->last = element;
|
|
|
245 goto meta(context, next);
|
|
|
246 }
|
|
|
247
|
|
|
248 // generated by script
|
|
|
249 __code putSingleLinkedQueue_stub(struct Context* context) {
|
|
|
250 SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue);
|
|
|
251 Data* data = Gearef(context, Queue)->data;
|
|
|
252 enum Code next = Gearef(context, Queue)->next;
|
|
|
253 goto putSingleLinkedQueue(context, queue, data, next);
|
|
|
254 }
|
|
|
255 ```
|
|
|
256
|
|
82
|
257 ## 並列処理の構成
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
258 - 今回は並列処理を行う機構の実装を行う
|
|
82
|
259 - 構成要素
|
|
|
260 - Task(Context)
|
|
86
|
261 - TaskManager
|
|
|
262 - Worker の生成、依存関係を解決したTask を Worker に送信する
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
263 - Worker
|
|
86
|
264 - SynchronizedQueue から Task を取得し、実行する
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
265
|
|
82
|
266 ## Task(Context)
|
|
86
|
267 - Gears OS では並列実行する Task を Context で表現する
|
|
|
268 - Context Task用の情報として以下の情報をもっている
|
|
|
269 - 実行する Code Gear
|
|
|
270 - Input/Output Data Gear の格納場所
|
|
|
271 - 待っている Input Data Gear の数
|
|
|
272 - 実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる
|
|
|
273 - stub Code Gear は自動生成される
|
|
|
274
|
|
|
275 ``` c
|
|
|
276 __code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) {
|
|
|
277 output->value = input1->value + input2->value;
|
|
|
278 goto next(output, ...);
|
|
|
279 }
|
|
|
280 ```
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
281
|
|
82
|
282 ## TaskManger
|
|
|
283 - 初期化時に決まった数の Worker を作成
|
|
|
284 - 依存関係を解決した Task を各 Worker の Queue に送信する
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
285
|
|
82
|
286 <div style="text-align: center;">
|
|
86
|
287 <img src="./images/sendTask.svg" alt="message" width="800">
|
|
82
|
288 </div>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
289
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
290 ## Worker
|
|
86
|
291 - 初期化の際にスレッドと Worker 用の Context を生成する
|
|
|
292 - TaskManager から送信された Task を取得して実行する
|
|
|
293
|
|
|
294 <div>
|
|
|
295 <div style="float: left;">
|
|
|
296 <img src="./images/workerRun.svg" alt="message" width="600">
|
|
|
297 </div>
|
|
|
298 <div style="float: left; font-size=100%;">
|
|
|
299 <ol>
|
|
|
300 <li>Worker は Queue から Task を取得する</li>
|
|
|
301 <li>Worker Context から Task へ入れ替える</li>
|
|
|
302 <li>Task の Code Gear を実行</li>
|
|
|
303 <li>Task の Output Data Gear の書き出し</li>
|
|
|
304 <li>Task から WorkerContext へ入れ替える</li>
|
|
|
305 <li>Worker は再び Queue から Task を取得する</li>
|
|
|
306 </ol>
|
|
|
307 </div>
|
|
|
308 </div>
|
|
|
309
|
|
|
310 ## Synchronized Queue
|
|
|
311 - Worker で使用される Queue
|
|
|
312 - TaskManager を経由して Task を送信するスレッドと Task を取得するスレッドで操作される
|
|
|
313 - そのためマルチスレッドでのデータの一貫性を保証する必要がある
|
|
|
314 - Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する
|
|
|
315 - この Queue は Queue Interface を実装し、 List を利用した実装を行った
|
|
|
316
|
|
|
317 ```
|
|
|
318 struct SynchronizedQueue {
|
|
|
319 struct Element* top;
|
|
|
320 struct Element* last;
|
|
|
321 struct Atomic* atomic;
|
|
|
322 };
|
|
|
323 // Singly Linked List element
|
|
|
324 struct Element {
|
|
|
325 union Data* top;
|
|
|
326 struct Element* next;
|
|
|
327 };
|
|
|
328 ```
|
|
|
329
|
|
|
330 ## 依存関係の解決
|
|
|
331 - 依存関係の解決は Data Gear にメタレベルで依存関係解決用の Queueをもたせることで行う
|
|
|
332 - Code Gear を実行した後、 Output Data Gear を書き出す処理を行う
|
|
|
333 - 書き出し処理は Data Gear の Queue から依存関係にある Task を参照する
|
|
|
334 - Task には実行に必要な Input Data Gear のカウンタを持っているため、そのカウンタをデクリメントする
|
|
|
335 - カウンタが0になったら Input Data Gear が揃ったことになるため、TaskManager を経由して Worker に送信する
|
|
|
336
|
|
|
337 <div style="text-align: center;">
|
|
|
338 <img src="./images/dependency.svg" alt="message" width="600">
|
|
|
339 </div>
|
|
|
340
|
|
|
341 ## 並列構文
|
|
|
342 - 並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する
|
|
|
343 - この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述は好ましくない
|
|
87
|
344 - Task の設定の記述は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である
|
|
86
|
345 - そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した
|
|
|
346 - par goto 構文には引数として Input/Output Data Gear等を渡す
|
|
|
347 - スクリプトによって Code Gear の Input/Output の数を解析する
|
|
|
348
|
|
|
349 ``` c
|
|
|
350 __code code1(Integer *integer1, Integer * integer2, Integer *output) {
|
|
|
351 par goto add(integer1, integer2, output, __exit);
|
|
|
352 goto code2();
|
|
|
353 }
|
|
|
354 ```
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
355
|
|
86
|
356 ## CUDA への対応
|
|
|
357 - Gears OS は GPU での実行もサポートする
|
|
|
358 - GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる
|
|
|
359 - 今回は CUDA への実行のサポートをおこなった
|
|
|
360 - CUDA へ GPU を Device、 CPU を Host として定義する
|
|
|
361 - CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する
|
|
|
362 - 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた Code Gear を提供する
|
|
|
363
|
|
|
364 <div style="text-align: center;">
|
|
|
365 <img src="./images/cudaArchitecture.svg" alt="message" width="500">
|
|
|
366 </div>
|
|
|
367
|
|
|
368 ## CUDAExecutor
|
|
|
369 - CUDA Executor は Executor Interface を実装した以下の Code Gear を持つ
|
|
|
370 - HostからDevice へのデータの送信(read)
|
|
|
371 - kernel の実行(exec)
|
|
|
372 - Device から Host へのデータの書き出し(write)
|
|
|
373
|
|
|
374 ``` c
|
|
|
375 typedef struct Executor<Impl>{
|
|
|
376 union Data* Executor;
|
|
|
377 struct Context* task;
|
|
|
378 __code next(...);
|
|
|
379 // method
|
|
|
380 __code read(Impl* executor, struct Context* task, __code next(...));
|
|
|
381 __code exec(Impl* executor, struct Context* task, __code next(...));
|
|
|
382 __code write(Impl* executor, struct Context* task, __code next(...));
|
|
|
383 }
|
|
|
384 ```
|
|
|
385
|
|
|
386 ## CUDABuffer
|
|
|
387 - Host、 Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある
|
|
|
388 - Device にデータ領域を確保するにはサイズの指定が必要
|
|
|
389 - Data Gear には Meta Data Gear でデータのサイズを持っている
|
|
|
390 - だが、Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう
|
|
|
391 - CUDA Buffer ではそのマッピングを行う
|
|
|
392 - このマッピングは Task の stub Code Gear で行われる
|
|
|
393
|
|
|
394 <div style="text-align: center;">
|
|
|
395 <img src="./images/cudaDataArchitecture.svg" alt="message" width="500">
|
|
|
396 </div>
|
|
|
397
|
|
|
398 ## CUDA での呼び出し
|
|
|
399 - Gears OS では stub Code Gear で CUDA による実行を切り替える
|
|
|
400 - stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う
|
|
|
401 - stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する
|
|
|
402
|
|
|
403 ## Gears OS の評価
|
|
|
404 - 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った
|
|
|
405 - CPU 環境
|
|
|
406 - Model : Dell PowerEdgeR630
|
|
|
407 - Memory : 768GB
|
|
|
408 - CPU : 2 x 18-Core Intel Xeon 2.30GHz
|
|
|
409 - GPU 環境
|
|
|
410 - GPU : GeForce GTX 1070
|
|
|
411 - Cores : 1920
|
|
|
412 - ClockSpeed : 1683MHz
|
|
|
413 - Memory Size : 8GB GDDR5
|
|
|
414 - Memory Bandwidth : 256GB/s
|
|
|
415
|
|
|
416 ## Twice
|
|
|
417 - Twice は与えられた整数配列を2倍にする例題である
|
|
|
418 - 並列実行の依存関係がなく、並列度が高い課題である
|
|
|
419 - 要素数 2^27
|
|
|
420 - CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する
|
|
|
421 - GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開
|
|
|
422
|
|
|
423 ## Twice の結果
|
|
|
424 <table border="1" align='center' width='50%'>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
425 <tbody>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
426 <tr>
|
|
86
|
427 <td style="text-align: center;">Processor</td>
|
|
|
428 <td style="text-align: center;">Time(ms)</td>
|
|
|
429 </tr>
|
|
|
430 <tr>
|
|
|
431 <td style="text-align: center;">1 CPU</td>
|
|
|
432 <td style="text-align: right;">1181.215</td>
|
|
|
433 </tr>
|
|
|
434 <tr>
|
|
|
435 <td style="text-align: center;">2 CPUs</td>
|
|
|
436 <td style="text-align: right;">627.914</td>
|
|
|
437 </tr>
|
|
|
438 <tr>
|
|
|
439 <td style="text-align: center;">4 CPUs</td>
|
|
|
440 <td style="text-align: right;">324.059</td>
|
|
|
441 </tr>
|
|
|
442 <tr>
|
|
|
443 <td style="text-align: center;">8 CPUs</td>
|
|
|
444 <td style="text-align: right;">159.932</td>
|
|
|
445 </tr>
|
|
|
446 <tr>
|
|
|
447 <td style="text-align: center;">16 CPUs</td>
|
|
|
448 <td style="text-align: right;">85.518</td>
|
|
|
449 </tr>
|
|
|
450 <tr>
|
|
|
451 <td style="text-align: center;">32 CPUs</td>
|
|
|
452 <td style="text-align: right;">43.496</td>
|
|
|
453 </tr>
|
|
|
454 <tr>
|
|
|
455 <td style="text-align: center;">GPU</td>
|
|
87
|
456 <td style="text-align: right;">127.018</td>
|
|
86
|
457 </tr>
|
|
|
458 <tr>
|
|
|
459 <td style="text-align: center;">GPU(kernel only)</td>
|
|
|
460 <td style="text-align: right;">6.018</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
461 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
462 </tbody>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
463 </table>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
464
|
|
86
|
465 - 1 CPU と 32 CPU では 約27.1倍の速度向上が見られた
|
|
87
|
466 - GPU 実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上、通信時間を含めると 16 CPU より遅い
|
|
|
467 - 通信時間がオーバーヘッドになっている
|
|
82
|
468
|
|
|
469 ## BitonicSort
|
|
86
|
470 - 並列処理向けのソートアルゴリズム
|
|
|
471 - 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする
|
|
|
472 - 要素数 2^24
|
|
|
473 - CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する
|
|
|
474 - GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開
|
|
|
475
|
|
|
476 <div style="text-align: center;">
|
|
|
477 <img src="./images/bitonicNetwork.svg" alt="message" width="500">
|
|
|
478 </div>
|
|
82
|
479
|
|
|
480 ## BitonicSort の結果
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
481
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
482 <table border="1" align='center' width='50%'>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
483 <tbody>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
484 <tr>
|
|
86
|
485 <td style="text-align: center;">Processor</td>
|
|
|
486 <td style="text-align: center;">Time(s)</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
487 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
488 <tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
489 <td style="text-align: center;">1 CPU</td>
|
|
86
|
490 <td style="text-align: right;">41.416</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
491 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
492 <tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
493 <td style="text-align: center;">2 CPUs</td>
|
|
86
|
494 <td style="text-align: right;">23.340</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
495 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
496 <tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
497 <td style="text-align: center;">4 CPUs</td>
|
|
86
|
498 <td style="text-align: right;">11.952</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
499 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
500 <tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
501 <td style="text-align: center;">8 CPUs</td>
|
|
86
|
502 <td style="text-align: right;">6.320</td>
|
|
|
503 </tr>
|
|
|
504 <tr>
|
|
|
505 <td style="text-align: center;">16 CPUs</td>
|
|
|
506 <td style="text-align: right;">3.336</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
507 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 <tr>
|
|
86
|
509 <td style="text-align: center;">32 CPUs</td>
|
|
|
510 <td style="text-align: right;">1.872</td>
|
|
|
511 </tr>
|
|
|
512 <tr>
|
|
|
513 <td style="text-align: center;">GPU</td>
|
|
|
514 <td style="text-align: right;">5.420</td>
|
|
|
515 </tr>
|
|
|
516 <tr>
|
|
|
517 <td style="text-align: center;">GPU(kernel only)</td>
|
|
|
518 <td style="text-align: right;">0.163</td>
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
519 </tr>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
520 </tbody>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
521 </table>
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
522
|
|
86
|
523 - 1 CPU と 32 CPU で約22.12倍の速度向上
|
|
87
|
524 - GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった
|
|
86
|
525 - 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526
|
|
82
|
527 ## OpenMP との比較
|
|
|
528 ## Go との比較
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
529
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
530 ## まとめ
|
|
86
|
531 - Gears OS の並列処理機構の実装を行った
|
|
|
532 - Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった
|
|
|
533 - par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった
|
|
|
534 - 2つの例題である程度の台数効果が出ることを確認した
|
77
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
535
|
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
536 ## 今後の課題
|
|
86
|
537 - Gears OS の並列処理の信頼性の保証、チューニングを行う
|
|
|
538 - Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する
|
|
|
539 - 証明はCbC のプログラムヲ証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある
|
|
|
540 - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う
|
|
|
541 - OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。
|
|
|
542 - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう
|
|
|
543 - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成セずに関数呼出しを行う等の最適化が必要
|
|
|
544 - 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった
|
|
|
545 - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持サれているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデーの通信を行う
|
