17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 title: Code Segment と Data Segment を持つ Gears OS の設計
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 author: Shohei KOKUBO
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 profile: 琉球大学大学院修士2年
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 # 並列環境下におけるプログラミング
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 これはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 つまり、プログラムを並列処理に適した形で記述するためのフレームワークが必要になる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 マルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 並列処理をする上でこれらのリソースを無視することはできない。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 しかし、これらのプロセッサで性能を引き出すためにはそれぞれのアーキテクチャに合わせた並列プログラミングが必要になる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 # Cerium
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 Cerium は本研究室で開発している並列プログラミングフレームワークである。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 Cerium では関数またはサブルーチンを Task として定義する。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 Task 間で依存関係を設定することができ、TaskManager が依存関係を解決することで実行可能な状態となる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 実行可能な状態となると Task に設定された実行デバイスの Scheduler に転送され実行される。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23
|
|
19
|
24 # Cerium の問題点
|
|
|
25 * Task 間の依存関係
|
|
|
26
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 Cerium では Task 間の依存関係を設定することで並列処理を実現する。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 しかし、本来 Task は必要なデータが揃うことで実行可能になるものである。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 Task 同士の依存関係だけでは前の Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 データがどこでおかしくなったのか特定するのは難しく、デバックに時間が取られる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31
|
|
19
|
32 * データの型情報
|
|
|
33
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 Task は汎用ポインタでデータの受け渡しを行うのでそこで型情報が落ちる。
|
|
19
|
35 Task 側で正しく型変換を行うことで正しい処理を行うことができるが、誤った型変換を行うと未定義な動作となりデータ構造を破壊する可能性がある。
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 型システムによるプログラムの正しさを保証することもできず、型に基づく一連の不具合が起こる危険性がつきまとう。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37
|
|
19
|
38 # Cerium の問題点
|
|
|
39 * メモリ確保
|
|
|
40
|
|
|
41 Cerium の Allocator は Thread 間で共有されている。
|
|
|
42 ある Thread がメモリを確保しようとすると他の Thread はその間メモリを確保することができない。
|
|
|
43 これが並列度の低下に繋がり、処理速度が落ちる原因になる。
|
|
|
44
|
|
|
45 * オブジェクト指向と並列処理
|
|
|
46
|
|
|
47 同じ入力に対し、同じ入力を返すことが保証される参照透過な処理は並列化を行いやすい。
|
|
|
48 一方、オブジェクト指向は保守性と再利用性を高めるためにカプセル化やポリモフィズムを重視する。
|
|
|
49 オブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪い。
|
|
|
50
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 # Gears OS
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 本研究では Code Segment と Data Segment によって構成される Gears OS の設計・実装を行った。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53
|
|
19
|
54 Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。
|
|
|
55
|
|
|
56 Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C) を用いた。
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 # Code/Data Gear
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 Gears OS ではプログラムの単位として Gear を用いる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 Gear は並列実行の単位、データ分割、Gear 間の接続などになる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 Code Gear は Code Segment と同等のものである。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 接続された Data Gear 以外にアクセスすることは
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 Data Gear はデータそのものを表す。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 int や文字列などの Primitive Data Type を複数持つ構造体として定義する。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68
|
|
19
|
69 Gear 特徴として処理やデータの構造が Code/Data Gear に閉じていることにある。
|
|
|
70 これにより実行時間、メモリ使用量などを予測可能なものにする。
|
|
|
71
|
|
|
72 # Gears OS の構成
|
|
|
73 * Context
|
|
|
74
|
|
|
75 接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、独立したメモリ空間を持っている。
|
|
|
76 複数の Context で TaskQueue と Persistent Data Tree は共有される。
|
|
|
77
|
|
|
78 * TaskQueue
|
|
|
79
|
|
|
80 ActiveTaskQueue と WaitTaskQueue の2種類の TaskQueue がある。
|
|
|
81 ActiveTaskQueue には実行可能な Task が挿入され、WaitTaskQueue には依存関係が解決されていない Task が挿入される。
|
|
|
82 先頭と末尾の Element へのポインタを持つ Data Gear と Task へのポインタと次の Element へのポインタを持つ Data Gear で構成される。
|
|
|
83 Compare and Swap(CAS) を利用することでスレッドセーフに Queue を操作することができる。
|
|
|
84
|
|
|
85 # Gears OS の構成
|
|
|
86 * Persistent Data Tree
|
|
|
87
|
|
|
88 Data Gear の管理を行う。
|
|
|
89 非破壊木構造で構成されるため読み書きを平行して行うことができる。
|
|
|
90 Red-Black Tree アルゴリズムを用いて平衡性を保ち、挿入・削除・検索における計算量を保証する。
|
|
|
91 Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。
|
|
|
92
|
|
|
93 * TaskManager
|
|
|
94
|
|
|
95 Gears OS における Task は実行する Code Gear と Input/Output Data Gear の組で表現される。
|
|
|
96 Input/Output Data Gear から依存関係を決定する。
|
|
|
97 TaskManager は Persistent Data Tree を監視し、Task の依存関係を解決する。
|
|
|
98
|
|
|
99 # Gears OS の構成
|
|
|
100 * Worker
|
|
|
101
|
|
|
102 Worker は ActiveTaskQueue から Task を取得する。
|
|
|
103 取得した Task の情報を元に必要な Data Gear を Persistent Data Tree から取得し、Code Gear を実行する。
|
|
|
104 実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。
|
|
|
105
|
|
|
106 
|
|
|
107
|
|
|
108 # Allocator
|
|
|
109
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 # 測定結果
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 * OS X(10.10.5)
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 * 2.3 GHz Intel Core i7
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 * length：1310720
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 * cpus/(length/task)/time
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 * 1/10/0.164748s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 * 2/10/0.230114s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 * 4/10/0.479126s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 * 8/10/0.553448s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 * 1/81920/0.010666s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 * 2/81920/0.005303s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 * 4/81920/0.002657s
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 * 8/81920/0.002521s |
