|
0
|
1 title: Gears OS のモジュール化と並列 API
|
|
|
2 author: Mitsuki Miyagi, Yu Tobaru, Shinji Kono
|
|
|
3 profile: 琉球大学
|
|
|
4 lang: Japanese
|
|
|
5 code-engine: coderay
|
|
|
6
|
|
7
|
7 % ## OS の信頼性
|
|
3
|
8 % - コンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。
|
|
|
9 % - OS は非決定的な実行を持つため、OS の信頼性を保証するには、証明を用いる方法とプログラムの可能な実行を全て数え上げるモデル検査を用いる必要がある。
|
|
|
10 % - 従来のテストとデバッグではテスト仕切れない部分が残ってしまい、不十分。
|
|
|
11 % - モデル検査は無限の状態でなくても巨大な状態を調べる事になり、状態を有限に制限したり、状態を抽象化したりする方法が用いられる。
|
|
|
12 %
|
|
7
|
13 % ## OS の拡張性
|
|
3
|
14 % - 時代とともに進歩するハードウェア、サービスに対応するために OS 自体が拡張される必要がある。
|
|
|
15 % - OS を検証する際にも、1度ではなくアプリケーションやサービス、デバイスが新しくなる毎に検証をやり直す必要がある。
|
|
|
16 %
|
|
7
|
17 % ## OS の拡張性と信頼性の両立
|
|
3
|
18 % - OSの拡張性と信頼性の観点から、OS は信頼性と拡張性を両立させることが重要であるといえる。
|
|
|
19 % - 本研究室では、OS の信頼性の保証と拡張性を実現することを目標に Gears OS を設計中である。
|
|
|
20
|
|
7
|
21 ## Gears OS
|
|
3
|
22 - 現代のOS では拡張性と信頼性を両立させることが要求されている。
|
|
|
23 - 時代と共にハードウェア、サービスが進歩していき、その度に OS を検証できる必要があるため、拡張性が必要。
|
|
9
|
24 - OS は非決定的な実行を持ち、従来の OS ではテストしきれない部分が残ってしまうため、信頼性が欠けてしまうので信頼性のある OS が必要。
|
|
|
25 - 本研究室では、拡張性と信頼性を実現することを目標に Gears OS の開発を行なっている。
|
|
0
|
26
|
|
5
|
27 % 欠けてしまうで終わってるので "それら"は 分かりづらい
|
|
|
28 % 並列API 研究目的とAPIとの繋がりがない
|
|
|
29 % モジュールとAPIの説明分ける
|
|
|
30 % 拡張性と信頼性を実現する時に Interfaceと par goto 構文がなぜ必要なのかに繋げる話が必要
|
|
3
|
31 % APIと実装の分離が望ましい理由は？
|
|
5
|
32
|
|
7
|
33 ## API と実装の分離
|
|
3
|
34 - Gears OS は Continuation based C(以下、CbC)によって記述されている。
|
|
|
35 - CbC は Code Gear と Data Gear の単位でプログラムを記述していて、システムやアプリケーションを作る際に、この2つは柔軟に再利用する必要がある。
|
|
|
36 - この時に、機能を接続する API と実装の分離が可能であることが望ましい。
|
|
|
37
|
|
|
38 % 上と繋がってない
|
|
|
39 % なんでモジュールシステムが必要？
|
|
5
|
40 % 形式化と言わない
|
|
|
41 % 形式化 formalization
|
|
|
42 % ここでいう形式化はInterfaceとは関係ない
|
|
|
43 % interface は仕様とAPIの分離
|
|
|
44 % 実装の分割 がInterface
|
|
|
45 % まず、形式化が重要(仕様、実装、実行をlogicで記述)
|
|
|
46 % その記述にAgdaを使う
|
|
|
47
|
|
|
48 % Interfaceはほとんどかかない
|
|
6
|
49 % TaskScheduler の図も入れる Gears の構成のやつ
|
|
5
|
50
|
|
7
|
51 ## Gears OS での形式化とInterfaceの導入
|
|
5
|
52 - 形式化とは仕様、実装、実行を Logic で記述する事である。
|
|
|
53 - Gears OS では、継続を使った関数型プログラムとして実装を記述する
|
|
9
|
54 - Logic としては、依存型関数言語である Agda を使う(外間の発表)
|
|
5
|
55 - 証明とモデル検査を使って、信頼性を確保する
|
|
|
56
|
|
7
|
57 ## Gears OS の Interface
|
|
9
|
58 - Code Gear と Deta Gear は Interface と呼ばれるまとまり(モジュール)で記述される。
|
|
5
|
59 - Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。
|
|
|
60 - Interface は Data Gear で記述されて、Meta Deta Gear と呼ばれる。
|
|
|
61 - Java などの Class に相当する。
|
|
9
|
62 % - Interface を外から呼び出すための Code Gear 群の型
|
|
5
|
63 - Interface を呼び出す時に必要となる引数を全て格納する Data Gear
|
|
9
|
64 % - 実装に使う Code Gear の番号が含まれている。
|
|
|
65 % - Code Gear の番号を変更することによって異なる実装を実現できる
|
|
5
|
66
|
|
|
67 % Interface は実行時に実装を入れ替える事ができる
|
|
|
68 % 呼び出すものはStack 上に積めない
|
|
|
69 % Contextも集合
|
|
|
70
|
|
7
|
71 ## 並列API
|
|
9
|
72 - Geas OS 信頼性を保証するために、モジュールシステムが必要である。
|
|
3
|
73 - 本研究では、モジュールシステムとその応用である並列APIについて考察する。
|
|
|
74 - 並列APIは継続を基本とした関数型プログラミングと両立する必要があり、ここでは CbC の goto 文を拡張した par goto を導入する。
|
|
0
|
75
|
|
7
|
76 ## スライドの流れ
|
|
5
|
77 - Interface
|
|
3
|
78 - <font color="red">CbC</font>
|
|
|
79 - Gears OS における並列実行
|
|
|
80 - 比較
|
|
|
81 - 今後の課題
|
|
0
|
82
|
|
3
|
83
|
|
|
84
|
|
|
85
|
|
|
86
|
|
7
|
87 ## CbC
|
|
5
|
88 - ノーマルレベルとメタレベルの計算を1つの言語で表現できる言語として、本研究室で設計した CbC を用いる。
|
|
2
|
89 - ノーマルレベルの計算
|
|
5
|
90 - コンピュータの計算はプログラミング言語で行われる。
|
|
2
|
91 - その部分をノーマルレベルの計算と呼ぶ。
|
|
|
92 - メタレベルの計算
|
|
|
93 - コードが実行される際の以下の部分が、メタレベルの計算という。
|
|
|
94 - 処理系の詳細や使用する資源
|
|
5
|
95 - コードの仕様や型などの部分
|
|
|
96
|
|
|
97 % ノーマルレベルとメタレベルの違い
|
|
|
98 % 以外 = メモリ
|
|
|
99 % 定義されたものに従って形式的にプログラムが記述されるが、その実行の資源や環境がメタレベル
|
|
|
100 % 実行するのはOSや資源
|
|
|
101 % 実際にはプログラムで記述されていない部分(CPU,メモリの資源、並列処理、外界の影響) この４つ書く
|
|
|
102 % CbC の特徴はメタもかける
|
|
|
103 % OS での資源はCbCでかける
|
|
|
104 % シミュレーションされた外界
|
|
|
105 % シミュレーションされてない外界はOSとは違うのでCbCで書けない
|
|
|
106 % ぱるすさんの図入れるMeta data Gear
|
|
|
107
|
|
7
|
108 ## CbC
|
|
2
|
109 - CbC を用いることで、ノーマルレベルの計算の信頼性をメタレベルから保証できるようになる。
|
|
5
|
110 - CbC を用いてCode Gear と Data Gear を導入する。
|
|
|
111
|
|
2
|
112
|
|
3
|
113 % - 検証には 定理証明支援系である Agda を用いる。
|
|
|
114 % - Gears の記述をモジュール化するために Interface を導入した。
|
|
|
115 % - さらに並列処理の記述用に par goto 構文を導入する。
|
|
|
116
|
|
7
|
117 % ## par goto の実行
|
|
3
|
118 % - 本論文では Interface と par goto の実装を記述し、評価を行なった。
|
|
|
119 % - また、マルチ CPU と GPU 上での par goto 文の実行を確認した。
|
|
2
|
120
|
|
5
|
121 % par goto には構文と実行の話がある
|
|
|
122 % ストーリー的に早いのでここでは入れない
|
|
|
123
|
|
7
|
124 ## CbC の構文
|
|
3
|
125 - CbC の Code Gear は __code という型を持つ関数として記述する。
|
|
|
126 - 継続で次の Code Gear に遷移するので、戻り値は持たない。
|
|
|
127 - 遷移は goto 文による継続で処理を行い、引数として入出力を行う。
|
|
|
128 ```c
|
|
|
129 __code cg0(int a, int b) {
|
|
|
130 goto cg1(a+b);
|
|
|
131 }
|
|
|
132 __code cg1(int c) {
|
|
|
133 goto cg2(c);
|
|
|
134 }
|
|
|
135 ```
|
|
5
|
136 - CbC の記述だけでは並列実行にならない
|
|
|
137
|
|
|
138 % 関数呼び出しで実装したい なのでpar つける
|
|
|
139 % 意味: 戻り値がなく exitで呼び出す
|
|
|
140 % par goto (並列実行を実装したい、形式化したい=Agdaの記述をしたい) 並列実行を形式化する
|
|
|
141 % 本文のpar goto を削って載せる
|
|
|
142 % なぜ par goto が必要か
|
|
|
143 % context がこれの先に出てないとだめ
|
|
|
144 % 形式化はどうするの？-> par goto を使う。
|
|
|
145 % par goto を使えば並列実行されたGears の形式化ができる
|
|
|
146
|
|
|
147
|
|
|
148
|
|
7
|
149 ## スライドの流れ
|
|
3
|
150 - CbC
|
|
|
151 - <font color="red">Gears OS における並列実行</font>
|
|
0
|
152 - 比較
|
|
|
153 - 今後の課題
|
|
|
154
|
|
3
|
155
|
|
7
|
156 ## Gears における並列実行
|
|
3
|
157 - Gears OS ではメタ計算を柔軟に記述するためのプログラミングの単位として Code Gear と Data Gear を用いる。
|
|
|
158 - それぞれにメタレベルの単位が存在し、Meta Data Gear と Meta Code Gear と呼ぶ。
|
|
|
159 - メタレベルの計算は Perl スクリプトによって生成され、Code Gear で記述される。
|
|
7
|
160 <div style="text-align: center;">
|
|
8
|
161 <img src="./image/meta_cg_dg.svg" alt="Meta Data Gear と Meta Code Gear" width="600">
|
|
7
|
162 </div>
|
|
3
|
163
|
|
7
|
164
|
|
|
165
|
|
|
166 % ## Interface
|
|
5
|
167 % - この時、Code Gear と Deta Gear は Interface と呼ばれるまとまり(モジュール)で記述される。
|
|
|
168 % - Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。
|
|
3
|
169
|
|
7
|
170 ## Gears OS の構造
|
|
9
|
171 - Gears OS は以下の要素で構成されている
|
|
|
172 - Context
|
|
|
173 - TaskQueue
|
|
|
174 - TaskManager
|
|
|
175 - Worker
|
|
|
176
|
|
7
|
177 <div style="text-align: center;">
|
|
9
|
178 <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
|
|
7
|
179 </div>
|
|
|
180
|
|
|
181
|
|
|
182 ## Context
|
|
3
|
183 - 1つのスレッド内で使われる Interface の Code Gear と Data Gear は Meta Data Gear に格納される。
|
|
|
184 - この Meta Data Gear を Context と呼ぶ。
|
|
|
185 - Context を複製して複数の CPU に割り当てることにより並列実行が可能になる。
|
|
5
|
186 - Context は Task でもある。
|
|
|
187 - Task は実行する Code Gear と Data Gear を全て持っている。
|
|
3
|
188
|
|
7
|
189 ## par goto
|
|
3
|
190 - Context の複製には par goto を用いる。
|
|
|
191 - 他に、入力の同期、タスクスケジューラへの Context の登録が行われる。
|
|
|
192
|
|
5
|
193 % exit が説明不足
|
|
|
194 % code gear の実行は他のシープに邪魔されない。
|
|
|
195 % 並列実行時の書き換えは許してない
|
|
|
196
|
|
7
|
197 ## 1つの Code Gear の実行は他の Code Gear に割り込まれない
|
|
5
|
198 - 共有された Data Gear があった時に、それに対する変更はただ1つの Code Gear だけが許される
|
|
|
199 - 読み込みは複数であってもいい
|
|
|
200 - Agda 側で、並列実行を Code Gear の順次実行としてシミュレーションするため
|
|
|
201 - このような実行になるように Gears OS の実装を行う
|
|
3
|
202
|
|
5
|
203 % 複数走ったなかの成功したものをコミットするのがexit
|
|
|
204
|
|
9
|
205 <div style="text-align: center;">
|
|
|
206 <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
|
|
|
207 </div>
|
|
|
208
|
|
5
|
209
|
|
|
210
|
|
|
211
|
|
7
|
212 ## __exit
|
|
5
|
213 - 複数実行した時に、共有 Data Gear に書き込みを成功したかを確認する(commit)
|
|
|
214 - par goto で生成された Task は __exit に継続することで終了する
|
|
|
215 - GearsOS の Task は Output Data Gear を生成した時点で終了する
|
|
3
|
216 - そのため、par goto では直接 __exit に継続せず、Output Data Gear への書き出し処理に継続される。
|
|
|
217 - Code Gear と Data Gear の依存関係をノーマルレベルで記述できるようになる。
|
|
|
218 ```c
|
|
|
219 __code code1(Integer *integer1, Integer * integer2, Integer *output) {
|
|
|
220 par goto add(integer1, integer2, output, __exit);
|
|
|
221 goto code2();
|
|
|
222 }
|
|
|
223 ```
|
|
0
|
224
|
|
9
|
225 ## Perl スクリプトによる Meta Data Gear の生成
|
|
|
226
|
|
|
227
|
|
|
228 % Task Manager
|
|
|
229 %
|
|
|
230
|
|
|
231 ```c
|
|
|
232 __code code1(struct Context *context, Integer *integer1, Integer *integer2, Integer *output) {
|
|
|
233 // create context
|
|
|
234 context->task = NEW(struct Context);
|
|
|
235 initContext(context->task);
|
|
|
236
|
|
|
237 // set task parameter
|
|
|
238 context->task->next = C_add;
|
|
|
239 context->task->idgCount = 2;
|
|
|
240 context->task->idg = context->task->dataNum;
|
|
|
241 context->task->maxIdg = context->task->idg + 2;
|
|
|
242 context->task->odg = context->task->maxIdg;
|
|
|
243 context->task->maxOdg = context->task->odg + 1;
|
|
|
244
|
|
|
245 // create Data Gear Queue
|
|
|
246 GET_META(integer1)->wait = createSynchronizedQueue(context);
|
|
|
247 GET_META(integer2)->wait = createSynchronizedQueue(context);
|
|
|
248 GET_META(integer3)->wait = createSynchronizedQueue(context);
|
|
|
249
|
|
|
250 // set Input Data Gear
|
|
|
251 context->task->data[context->task->idg+0] = (union Data*)integer1;
|
|
|
252 context->task->data[context->task->idg+1] = (union Data*)integer2;
|
|
|
253
|
|
|
254 // set Output Data Gear
|
|
|
255 context->task->data[context->task->odg+0] = (union Data*)integer3;
|
|
|
256
|
|
|
257
|
|
|
258 // set TaskManager->spawns parameter
|
|
|
259 Gearef(context, TaskManager)->taskList = context->taskList;
|
|
|
260 Gearef(context, TaskManager)->next1 = C_code2;
|
|
|
261 goto parGotoMeta(context, C_code2);
|
|
|
262 }
|
|
|
263 ```
|
|
|
264 % // add taskList Element
|
|
|
265 % struct Element* element;
|
|
|
266 % element = &ALLOCATE(context, Element)->Element;
|
|
|
267 % element->data = (union Data*)context->task;
|
|
|
268 % element->next = context->taskList;
|
|
|
269 % context->taskList = element;
|
|
|
270
|
|
5
|
271 % 失敗した時はmeta compitation で処理する
|
|
|
272
|
|
2
|
273
|
|
0
|
274
|
|
7
|
275 % ## Interface
|
|
0
|
276
|
|
|
277
|
|
7
|
278 % ## Context
|
|
3
|
279
|
|
7
|
280 % ## 並列構文
|
|
0
|
281
|
|
7
|
282 ## スライドの流れ
|
|
3
|
283 - CbC
|
|
|
284 - Gears OS における並列実行
|
|
|
285 - <font color="red">比較</font>
|
|
|
286 - 今後の課題
|
|
|
287
|
|
7
|
288 ## Gears OS の評価(目的)
|
|
5
|
289 - 並列構文とそれを実現する Meta Compitation が十分に揃っているかを確認したい
|
|
|
290 - 並列処理の台数効果を確認する
|
|
|
291 - 既存の並列言語と比較して不要なオーバーヘッドがあるか調べたい
|
|
3
|
292
|
|
7
|
293 ## Gears OS の評価(環境)
|
|
3
|
294 - CPU、GPU環境で Gears OS の測定を行う。
|
|
|
295 - 使用した環境は次のようになる。
|
|
4
|
296 - CPU 環境
|
|
|
297 - Model : Dell PowerEdgeR630
|
|
|
298 - Memory : 768GB
|
|
|
299 - CPU : 2 × 18-Core Intel Xeon 2.30GHz
|
|
|
300 - CPU 環境
|
|
|
301 - GPU : GeForce GTX 1070
|
|
|
302 - Cores : 1920
|
|
|
303 - ClockSpeed : 1683MHZ
|
|
|
304 - Memory Size : 8GB GDDR5
|
|
0
|
305
|
|
7
|
306 ## Twice
|
|
3
|
307 - 評価には与えられた整数配列の全ての要素を2倍にする例題である Twice を使う。
|
|
|
308 - Twice では 通信時間を考慮しなければ、CPU より コア数の多い GPU が有利となる。
|
|
|
309 - 要素数2^27のデータに対する Twice の実行結果を示す。
|
|
|
310 - CPU では2^27のデータを64個のデータに分割した。
|
|
|
311 - kernel only は 通信速度を除いた速度である。
|
|
4
|
312
|
|
|
313 <table border="1" align='center' width='50%'>
|
|
|
314 <tbody>
|
|
|
315 <tr>
|
|
|
316 <td style="text-align: center;">Processor</td>
|
|
|
317 <td style="text-align: center;">Time(ms)</td>
|
|
|
318 </tr>
|
|
|
319 <tr>
|
|
|
320 <td style="text-align: center;">1 CPU</td>
|
|
|
321 <td style="text-align: right;">1181.215</td>
|
|
|
322 </tr>
|
|
|
323 <tr>
|
|
|
324 <td style="text-align: center;">2 CPUs</td>
|
|
|
325 <td style="text-align: right;">627.914</td>
|
|
|
326 </tr>
|
|
|
327 <tr>
|
|
|
328 <td style="text-align: center;">4 CPUs</td>
|
|
|
329 <td style="text-align: right;">324.059</td>
|
|
|
330 </tr>
|
|
|
331 <tr>
|
|
|
332 <td style="text-align: center;">8 CPUs</td>
|
|
|
333 <td style="text-align: right;">159.932</td>
|
|
|
334 </tr>
|
|
|
335 <tr>
|
|
|
336 <td style="text-align: center;">16 CPUs</td>
|
|
|
337 <td style="text-align: right;">85.518</td>
|
|
|
338 </tr>
|
|
|
339 <tr>
|
|
|
340 <td style="text-align: center;">32 CPUs</td>
|
|
|
341 <td style="text-align: right;">43.496</td>
|
|
|
342 </tr>
|
|
|
343 <tr>
|
|
|
344 <td style="text-align: center;">GPU</td>
|
|
|
345 <td style="text-align: right;">127.018</td>
|
|
|
346 </tr>
|
|
|
347 <tr>
|
|
|
348 <td style="text-align: center;">GPU(kernel only)</td>
|
|
|
349 <td style="text-align: right;">6.018</td>
|
|
|
350 </tr>
|
|
|
351 </tbody>
|
|
|
352 </table>
|
|
3
|
353
|
|
7
|
354 ## 評価の考察
|
|
3
|
355 - コア数が上がるごとに、処理速度が上がっている。
|
|
|
356 - GPUでの実行は 32CPU に比べて約7.2倍の速度向上が見られた。
|
|
|
357 - 通信速度を含めると 16CPU より遅い。
|
|
0
|
358
|
|
3
|
359 % なんでGo言語？
|
|
7
|
360 ## Go 言語との比較
|
|
3
|
361 - Go 言語でも Twice を用いた検証を行い、Gears OS との速度比較を行なった。
|
|
|
362 - 1CPU と 32CPU では約4.33倍の速度向上が見られた。
|
|
|
363 - CPU数による速度向上は、Gears OS の方が上だが、処理速度では Go言語の方が速い結果となった。
|
|
4
|
364 <div style="text-align: center;">
|
|
7
|
365 <img src="./image/vsgo.svg" alt="Goとの比較" width="500">
|
|
4
|
366 </div>
|
|
|
367
|
|
3
|
368
|
|
7
|
369 ## スライドの流れ
|
|
3
|
370 - CbC
|
|
|
371 - Gears OS における並列実行
|
|
|
372 - 比較
|
|
|
373 - <font color="red">今後の課題</font>
|
|
0
|
374
|
|
7
|
375 ## 今後の課題
|
|
3
|
376 - Go 言語との比較から 1CPU での動作が遅いことがわかった。
|
|
|
377 - par goto 文を使用することで、Contextを生成し、並列処理を行う。
|
|
|
378 - しかし、Context はメモリ空間の確保や使用する全ての Code Gear Data Gear の設定をする必要があり、生成に時間がかかってしまう事が原因。
|
|
|
379 - 処理が軽い場合は Context を生成しないようなチューニングが必要である。
|
