|
13
|
1 title: Gears OS における並列処理
|
|
|
2 author: Takui Higashionna
|
|
|
3 profile:
|
|
|
4 lang: Japanese
|
|
|
5 code-engine: coderay
|
|
|
6
|
|
16
|
7 # メタ計算を使った並列処理
|
|
|
8
|
|
|
9 - 並列処理のプログラミングはチューニングや信頼性の確保が困難である。
|
|
|
10 - これらのチューニングや信頼性の確保を、アルゴリズムから分離しメタ計算で行う
|
|
|
11 - 並列処理のプラグラミングは、処理のパイプライン
|
|
|
12 - 当研究室ではメタ計算をサポートする言語として Continuation based C (CbC) を開発している
|
|
|
13 - CbC は Code Gear と Data Gear という処理とデータの単位を持っており、メタ計算を行うための Meta Code Gear、Meta Data Gear がある。
|
|
|
14 - Gears OS は CbC を用いて記述されている。
|
|
|
15
|
|
14
|
16 # Code Gear Data Gear
|
|
|
17
|
|
16
|
18 - Code Gear、Data Gear とはプラグラムを分解し、処理の部分を Code Gear、int や文字列などの部分を Data Gear という単位で分割したものである。
|
|
14
|
19 - Code Gear の処理の移行は goto を使って行い、この移行の仕方を継続という。
|
|
|
20 - goto による移行は戻り値を持たないため、スタックを積む必要のない、スタックに積まない継続を軽量継続と呼ぶ。
|
|
|
21
|
|
16
|
22 # Code Gear Data Gear を用いた計算
|
|
14
|
23
|
|
|
24 - Code Gear の処理の実行は、接続された Data Gear が揃ってから実行される。
|
|
|
25 - Data Gear には Output Data Gear と Input Data Gear があり、Code Gear は接続された Data Gear 以外を変更することはない。
|
|
16
|
26 - そのため通常の計算ではポインタを気にすることはなく、ポインタ演算はメタ計算部分で行われる。
|
|
|
27 - Code Gear の処理は tail call のみで遷移を行う関数型プログラミングである。
|
|
|
28 - agda に変換することができ、プログラムの正しさを証明できる。
|
|
14
|
29
|
|
|
30 # メタ計算
|
|
|
31
|
|
|
32 - メタ計算は通常の計算のための計算である
|
|
|
33 - 並列処理の依存関係の解決、GPUなどのアーキテクチャ実行のための処理を行う。
|
|
|
34 - Gears OSではメタ計算は Meta Code Gear、Meta Data Gear で表現される。
|
|
|
35
|
|
|
36 # Gears OS
|
|
|
37
|
|
16
|
38 - Gears OS は Code Gear、Data Gearの単位を用いて開発されており、CbCで記述される。
|
|
|
39 - Meta Code Gear は 通常の Code Gear の直後に遷移され、メタ計算を実行する。
|
|
|
40 - Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。
|
|
14
|
41
|
|
16
|
42 # Gears OS の並列性
|
|
14
|
43
|
|
|
44 - Code Gear が処理するのに必要なinput Data Gear と処理実行後に出力される Input Data Gear の組を Task と呼ぶ。
|
|
|
45 - Code Gear は Task 以外とは依存関係がない
|
|
|
46 - 依存関係が明確化されている Code Gear Data Gear で記述することで、並列化し易い。
|
|
|
47
|
|
|
48 <div style="text-align: center;">
|
|
|
49 <img src="./images/codeGear_dataGear.svg" alt="message" width="800">
|
|
|
50 </div>
|
|
|
51
|
|
15
|
52 # Gears OS の柔軟性
|
|
|
53
|
|
|
54 - Gears OS はメタ計算を使用することで
|
|
|
55 -- データ拡張や機能の追加
|
|
|
56 -- GPU 等の様々なアーキテクチャでも同じプログラムの動作
|
|
|
57 - メタ計算は通常の処理と階層を分けて処理を行う。
|
|
|
58
|
|
|
59 <div style="text-align: center;">
|
|
|
60 <img src="./images/meta_gear.svg" alt="message" width="800">
|
|
|
61 </div>
|
|
|
62
|
|
16
|
63 # Gears OS の構成
|
|
15
|
64
|
|
16
|
65 - Gears OS は以下の要素で構成される。
|
|
|
66
|
|
|
67 # Context
|
|
|
68
|
|
|
69 - Gears OS は Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear を持つ。
|
|
|
70 - Gears OS は必要な Code Gear、Data Gear に参照したい場合、この Context を通す必要がある。
|
|
|
71 - Context は 接続に必要な Code/Data Gear のリスト、 Data Gear を確保するためのメモリ空間、実行する Code Gear、Code Gear の実行に必要な Input Data Gear のカウンタ等をもっている。
|
|
|
72
|
|
|
73 # TaskManager
|
|
|
74
|
|
|
75 - TaskManager は Task、Worker の生成、Worker に生成した Task の送信、生成した Worker の終了処理等を行う。
|
|
|
76
|
|
|
77 # Worker
|
|
|
78
|
|
|
79 - Worker は thread と実行する Task が入っている Queue を持っている。
|
|
|
80 - Worker は TaskManager から送信された Task を Queue から取り出し、Code Gear を実行する。
|
|
|
81 - Task は Context なので、Code Gear の実行に必要な Input Data Gear はその Context から参照される。
|
|
|
82 - Code Gear を実行した後は出力される Output Data Gear から依存関係を解決する。
|
|
|
83
|
|
|
84 # 依存関係の解決
|
|
|
85
|
|
|
86
|
|
|
87
|
|
|
88
|
|
|
89
|
|
|
90
|
|
|
91
|
|
|
92
|
|
|
93
|
