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
|
|
24
|
24 # Cerium における GPGPU への対応
|
|
|
25 * OpenCL, CUDA を用いて GPGPU に対応している
|
|
|
26 * GPGPU ではメモリ空間が異なるためデータ転送が大きなオーバーヘッドになる
|
|
|
27 * 処理速度を上げるにはデータ転送をオーバーラップする必要がある
|
|
|
28
|
|
|
29 
|
|
|
30
|
|
|
31 # Cerium における GPGPU への対応
|
|
|
32 * Stream に命令を発行することで GPU を制御する
|
|
|
33 * Stream は命令が発行された順番通りに実行されることを保証する
|
|
|
34 * 複数の Stream を用意し、各 Stream に命令を発行することでデータ転送をオーバーラップすることができる
|
|
|
35
|
|
|
36 
|
|
|
37
|
|
|
38 # Bitonic Sort を用いた Cerium の評価
|
|
|
39 * Bitonic Sort は並列処理に向いたソートアルゴリズムである
|
|
|
40 * 最初から最後まで並列度が変わらず、台数による効果が出やすい
|
|
|
41
|
|
|
42 
|
|
|
43
|
|
|
44 # Bitonic Sort を用いた Cerium の評価
|
|
|
45 * 測定環境
|
|
|
46 * Model : MacPro Mid 2010
|
|
|
47 * OS : Mac OS X 10.10.5
|
|
|
48 * Memory : 16GB
|
|
|
49 * CPU : 2 x 6-Core Intel Xeon 2.66GHz
|
|
|
50 * GPU : NVIDIA Quadro K5000
|
|
|
51 * Cores : 1536
|
|
|
52 * Clock Speed : 706MHz
|
|
|
53 * Memory : 4GB GDDR5
|
|
|
54 * Memory Bandwidth : 173 GB/s
|
|
|
55 * 要素数：2<sup>20</sup>
|
|
|
56
|
|
|
57 <table border="1" align='center' width='50%'>
|
|
|
58 <tbody>
|
|
|
59 <tr>
|
|
|
60 <td style="text-align: center;">Processor</td>
|
|
|
61 <td style="text-align: center;">Time(ms)</td>
|
|
|
62 </tr>
|
|
|
63 <tr>
|
|
|
64 <td style="text-align: center;">1 CPU</td>
|
|
|
65 <td style="text-align: right;">6143</td>
|
|
|
66 </tr>
|
|
|
67 <tr>
|
|
|
68 <td style="text-align: center;">2 CPUs</td>
|
|
|
69 <td style="text-align: right;">4633</td>
|
|
|
70 </tr>
|
|
|
71 <tr>
|
|
|
72 <td style="text-align: center;">4 CPUs</td>
|
|
|
73 <td style="text-align: right;">2577</td>
|
|
|
74 </tr>
|
|
|
75 <tr>
|
|
|
76 <td style="text-align: center;">8 CPUs</td>
|
|
|
77 <td style="text-align: right;">1630</td>
|
|
|
78 </tr>
|
|
|
79 <tr>
|
|
|
80 <td style="text-align: center;">12 CPUs</td>
|
|
|
81 <td style="text-align: right;">1318</td>
|
|
|
82 </tr>
|
|
|
83 <tr>
|
|
|
84 <td style="text-align: center;">GPU</td>
|
|
|
85 <td style="text-align: right;">155</td>
|
|
|
86 </tr>
|
|
|
87 </tbody>
|
|
|
88 </table>
|
|
|
89
|
|
|
90 <table width="70%" align="center">
|
|
|
91 <tr>
|
|
|
92 <td><div align="center"><img src="pictures/bitonic_box.svg" width="1024"></div></td>
|
|
|
93 </tr>
|
|
|
94 </table>
|
|
|
95
|
|
|
96 # Bitonic Sort を用いた Cerium の評価
|
|
|
97 次に要素数を変更して測定を行った。
|
|
|
98
|
|
|
99 <table width="70%" align="center">
|
|
|
100 <tr>
|
|
|
101 <td><div align="center"><img src="pictures/bitonic_all.svg" width="1024"></div></td>
|
|
|
102 </tr>
|
|
|
103 <tr>
|
|
|
104 <td><div align="center"><img src="pictures/bitonic_part.svg" width="1024"></div></td>
|
|
|
105 </tr>
|
|
|
106 </table>
|
|
|
107
|
|
|
108 GPU による実行ではデータ転送の時間を考慮する必要がある。
|
|
|
109
|
|
|
110 GPGPU は大きなデータに対して有効であることがわかる。
|
|
|
111
|
|
19
|
112 # Cerium の問題点
|
|
|
113 * Task 間の依存関係
|
|
|
114
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 Cerium では Task 間の依存関係を設定することで並列処理を実現する。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 しかし、本来 Task は必要なデータが揃うことで実行可能になるものである。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 Task 同士の依存関係だけでは前の Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 データがどこでおかしくなったのか特定するのは難しく、デバックに時間が取られる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119
|
|
19
|
120 * データの型情報
|
|
|
121
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 Task は汎用ポインタでデータの受け渡しを行うのでそこで型情報が落ちる。
|
|
19
|
123 Task 側で正しく型変換を行うことで正しい処理を行うことができるが、誤った型変換を行うと未定義な動作となりデータ構造を破壊する可能性がある。
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 型システムによるプログラムの正しさを保証することもできず、型に基づく一連の不具合が起こる危険性がつきまとう。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125
|
|
19
|
126 # Cerium の問題点
|
|
|
127 * メモリ確保
|
|
|
128
|
|
|
129 Cerium の Allocator は Thread 間で共有されている。
|
|
|
130 ある Thread がメモリを確保しようとすると他の Thread はその間メモリを確保することができない。
|
|
|
131 これが並列度の低下に繋がり、処理速度が落ちる原因になる。
|
|
|
132
|
|
|
133 * オブジェクト指向と並列処理
|
|
|
134
|
|
|
135 同じ入力に対し、同じ入力を返すことが保証される参照透過な処理は並列化を行いやすい。
|
|
|
136 一方、オブジェクト指向は保守性と再利用性を高めるためにカプセル化やポリモフィズムを重視する。
|
|
|
137 オブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪い。
|
|
|
138
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 # Gears OS
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 本研究では Code Segment と Data Segment によって構成される Gears OS の設計・実装を行った。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
141
|
|
19
|
142 Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。
|
|
|
143
|
|
|
144 Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C) を用いた。
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146 # Code/Data Gear
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 Gears OS ではプログラムの単位として Gear を用いる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 Gear は並列実行の単位、データ分割、Gear 間の接続などになる。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 Code Gear は Code Segment と同等のものである。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。
|
|
20
|
152 接続された Data Gear 以外にアクセスすることはできない。
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 Data Gear はデータそのものを表す。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 int や文字列などの Primitive Data Type を複数持つ構造体として定義する。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156
|
|
19
|
157 Gear 特徴として処理やデータの構造が Code/Data Gear に閉じていることにある。
|
|
|
158 これにより実行時間、メモリ使用量などを予測可能なものにする。
|
|
|
159
|
|
|
160 # Gears OS の構成
|
|
|
161 * Context
|
|
|
162
|
|
|
163 接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、独立したメモリ空間を持っている。
|
|
|
164 複数の Context で TaskQueue と Persistent Data Tree は共有される。
|
|
|
165
|
|
|
166 * TaskQueue
|
|
|
167
|
|
|
168 ActiveTaskQueue と WaitTaskQueue の2種類の TaskQueue がある。
|
|
|
169 ActiveTaskQueue には実行可能な Task が挿入され、WaitTaskQueue には依存関係が解決されていない Task が挿入される。
|
|
|
170 先頭と末尾の Element へのポインタを持つ Data Gear と Task へのポインタと次の Element へのポインタを持つ Data Gear で構成される。
|
|
|
171 Compare and Swap(CAS) を利用することでスレッドセーフに Queue を操作することができる。
|
|
|
172
|
|
|
173 # Gears OS の構成
|
|
|
174 * Persistent Data Tree
|
|
|
175
|
|
|
176 Data Gear の管理を行う。
|
|
|
177 非破壊木構造で構成されるため読み書きを平行して行うことができる。
|
|
|
178 Red-Black Tree アルゴリズムを用いて平衡性を保ち、挿入・削除・検索における計算量を保証する。
|
|
|
179 Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。
|
|
|
180
|
|
|
181 * TaskManager
|
|
|
182
|
|
|
183 Gears OS における Task は実行する Code Gear と Input/Output Data Gear の組で表現される。
|
|
|
184 Input/Output Data Gear から依存関係を決定する。
|
|
|
185 TaskManager は Persistent Data Tree を監視し、Task の依存関係を解決する。
|
|
|
186
|
|
|
187 # Gears OS の構成
|
|
|
188 * Worker
|
|
|
189
|
|
|
190 Worker は ActiveTaskQueue から Task を取得する。
|
|
|
191 取得した Task の情報を元に必要な Data Gear を Persistent Data Tree から取得し、Code Gear を実行する。
|
|
|
192 実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。
|
|
|
193
|
|
|
194 
|
|
|
195
|
|
|
196 # Allocator
|
|
20
|
197 * Context の生成時にある程度の大きさのメモリ領域を確保
|
|
|
198 * Context には確保したメモリ領域を指す情報(heapStart, heap, heapLimit)を格納
|
|
19
|
199
|
|
20
|
200 ``` C
|
|
|
201 /* Context definition example */
|
|
|
202 #define ALLOCATE_SIZE 1000
|
|
|
203
|
|
|
204 // Code Gear Name
|
|
|
205 enum Code {
|
|
|
206 Code1,
|
|
|
207 Code2,
|
|
|
208 Allocator,
|
|
|
209 Exit,
|
|
|
210 };
|
|
|
211
|
|
|
212 // Unique Data Gear
|
|
|
213 enum UniqueData {
|
|
|
214 Allocate,
|
|
|
215 };
|
|
|
216
|
|
|
217 struct Context {
|
|
|
218 enum Code next;
|
|
|
219 int codeNum;
|
|
|
220 __code (**code) (struct Context*);
|
|
|
221 void* heapStart;
|
|
|
222 void* heap;
|
|
|
223 long heapLimit;
|
|
|
224 int dataNum;
|
|
|
225 union Data **data;
|
|
|
226 };
|
|
|
227
|
|
|
228 // Data Gear definition
|
|
|
229 union Data {
|
|
|
230 // size: 4 byte
|
|
|
231 struct Data1 {
|
|
|
232 int i;
|
|
|
233 } data1;
|
|
|
234 // size: 5 byte
|
|
|
235 struct Data2 {
|
|
|
236 int i;
|
|
|
237 char c;
|
|
|
238 } data2;
|
|
|
239 // size: 8 byte
|
|
|
240 struct Allocate {
|
|
|
241 long size;
|
|
|
242 } allocate;
|
|
|
243 };
|
|
|
244 ```
|
|
|
245
|
|
|
246 # Allocator
|
|
|
247 * Allocation を行うための情報を書き込む Data Gear が必要
|
|
|
248 * Context と同時に生成
|
|
|
249 ``` C
|
|
|
250 __code initContext(struct Context* context, int num) {
|
|
|
251 context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
|
|
|
252 context->heapStart = malloc(context->heapLimit);
|
|
|
253 context->heap = context->heapStart;
|
|
|
254 context->codeNum = Exit;
|
|
|
255
|
|
|
256 context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
|
|
|
257 context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
|
|
|
258
|
|
|
259 context->code[Code1] = code1_stub;
|
|
|
260 context->code[Code2] = code2_stub;
|
|
|
261 context->code[Allocator] = allocator_stub;
|
|
|
262 context->code[Exit] = exit_code;
|
|
|
263
|
|
|
264 context->data[Allocate] = context->heap;
|
|
|
265 context->heap += sizeof(struct Allocate);
|
|
|
266
|
|
|
267 context->dataNum = Allocate;
|
|
|
268 }
|
|
|
269 ```
|
|
|
270
|
|
|
271 # Allocator
|
|
|
272 * メモリ領域を指すポインタを動かすことで Data Gear のメモリを確保
|
|
|
273 * 確保した Data Gear は基本的に破棄可能なものである
|
|
|
274 * リニアにメモリを確保し、サイズを超えたら先頭に戻って再利用
|
|
|
275
|
|
|
276 
|
|
|
277
|
|
|
278 # Allocator
|
|
|
279 * Allocation に必要な情報を Data Gear に書き込み、Allocator に接続する
|
|
|
280 * 生成した Data Gear には Context を介してアクセスすることができるが、Context を直接扱うのは好ましくない
|
|
|
281 * Context から値を取り出すだけのメタレベルの Code Gear を用意
|
|
|
282
|
|
|
283 ``` C
|
|
|
284 // Meta Code Gear
|
|
|
285 __code meta(struct Context* context, enum Code next) {
|
|
|
286 // meta computation
|
|
|
287 goto (context->code[next])(context);
|
|
|
288 }
|
|
|
289
|
|
|
290 // Code Gear
|
|
|
291 __code code1(struct Context* context, struct Allocate* allocate) {
|
|
|
292 allocate->size = sizeof(struct Data1);
|
|
|
293 context->next = Code2;
|
|
|
294
|
|
|
295 goto meta(context, Allocator);
|
|
|
296 }
|
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
297
|
|
20
|
298 // Meta Code Gear(stub)
|
|
|
299 __code code1_stub(struct Context* context) {
|
|
|
300 goto code1(context, &context->data[Allocate]->allocate);
|
|
|
301 }
|
|
|
302
|
|
|
303 // Meta Code Gear
|
|
|
304 __code allocator(struct Context* context, struct Allocate* allocate) {
|
|
|
305 context->data[++context->dataNum] = context->heap;
|
|
|
306 context->heap += allocate->size;
|
|
|
307
|
|
|
308 goto meta(context, context->next);
|
|
|
309 }
|
|
|
310
|
|
|
311 // Meta Code Gear(stub)
|
|
|
312 __code allocator_stub(struct Context* context) {
|
|
|
313 goto allocator(context, &context->data[Allocate]->allcate);
|
|
|
314 }
|
|
|
315
|
|
|
316 // Code Gear
|
|
|
317 __code code2(struct Context* context, struct Data1* data1) {
|
|
|
318 // processing
|
|
|
319 }
|
|
|
320
|
|
|
321 // Meta Code Gear(stub)
|
|
|
322 __code code2_stub(struct Context* context) {
|
|
|
323 goto code2(context, &context->data[context->dataNum]->data1);
|
|
|
324 }
|
|
|
325 ```
|
|
|
326
|
|
|
327 # TaskQueue
|
|
|
328 TaskQueue は Task を管理する。
|
|
24
|
329
|
|
|
330 すべての Context で共有され、CAS 命令を利用して変更することで平行にアクセスされてもデータの一貫性を保証する。
|
|
20
|
331
|
|
|
332 * 先頭と末尾の要素へのポインタを持った Queue を表す Data Gear
|
|
|
333 * Task と次の要素へのポインタを持った Element を表す Data Gear
|
|
|
334 ``` C
|
|
|
335 // Code Gear Name
|
|
|
336 enum Code {
|
|
|
337 PutQueue,
|
|
|
338 GetQueue,
|
|
|
339 };
|
|
|
340
|
|
|
341 // Unique Data Gear
|
|
|
342 enum UniqueData {
|
|
|
343 Queue,
|
|
|
344 Element,
|
|
|
345 };
|
|
|
346
|
|
|
347 // Queue definication
|
|
|
348 union Data {
|
|
|
349 // size: 20 byte
|
|
|
350 struct Queue {
|
|
|
351 struct Element* first;
|
|
|
352 struct Element* last;
|
|
|
353 int count;
|
|
|
354 } queue;
|
|
|
355 // size: 16 byte
|
|
|
356 struct Element {
|
|
|
357 struct Task* task;
|
|
|
358 struct Element* next;
|
|
|
359 } element;
|
|
|
360 }
|
|
|
361 ```
|
|
|
362
|
|
|
363 # TaskQueue の操作(Enqueue)
|
|
|
364 * Enqueue は Queue の最後の要素を取り出し、次の要素に追加する要素を設定
|
|
|
365 * Queue を表す Data Gear が指す末尾を追加する要素に設定
|
|
|
366 * 正しく最後の要素が取り出せたことを保証して末尾の変更を行う必要がある
|
|
|
367
|
|
|
368 ``` C
|
|
|
369 // Enqueue
|
|
|
370 __code putQueue(struct Context* context, struct Queue* queue, struct Element* new_element) {
|
|
|
371 struct Element* last = queue->last;
|
|
|
372
|
|
|
373 if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
|
|
|
374 last->next = new_element;
|
|
|
375 queue->count++;
|
|
|
376
|
|
|
377 goto meta(context, context->next);
|
|
|
378 } else {
|
|
|
379 goto meta(context, PutQueue);
|
|
|
380 }
|
|
|
381 }
|
|
|
382 ```
|
|
|
383
|
|
|
384 # Persistent Data Tree
|
|
|
385 * Data Gear の管理を行う
|
|
|
386 * 複数の Context で共有
|
|
|
387 * 一度構築した木構造を破壊することなく新しい木構造を構築するので平行して読み書き可能
|
|
|
388 * 非破壊木構造の基本的な戦略はルートから変更したいノードへのパスをすべてコピーし、パス上に存在しないノードはコピー元の木構造と共有する
|
|
|
389
|
|
|
390 
|
|
|
391
|
|
|
392 # Persistent Data Tree
|
|
|
393 * 木構造を構築するとき最悪なケースでは事実上の線形リストになり、計算量が O(n) となる
|
|
|
394 * 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
|
|
|
395 * Red-Black Tree では変更したノードからルートに上りながら条件を満たすように色の変更や木の回転を行う
|
|
|
396 * Code Gear の継続では呼び出し元に戻ることが出来ないので Context に辿ったパスを記憶するためのスタックを準備する。
|
|
|
397
|
|
|
398 ```C
|
|
23
|
399 // Unique Data Gear
|
|
|
400 enum UniqueData {
|
|
|
401 Tree,
|
|
|
402 Traverse,
|
|
|
403 Node,
|
|
|
404 };
|
|
|
405
|
|
|
406 // Context definication
|
|
|
407 struct Context {
|
|
|
408 stack_ptr node_stack;
|
|
|
409 };
|
|
|
410
|
|
|
411 // Red-Black Tree definication
|
|
|
412 union Data {
|
|
|
413 // size: 8 byte
|
|
|
414 struct Tree {
|
|
|
415 struct Node* root;
|
|
|
416 } tree;
|
|
|
417 // size: 12 byte
|
|
|
418 struct Traverse {
|
|
|
419 struct Node* current;
|
|
|
420 int result;
|
|
|
421 } traverse;
|
|
|
422 // size: 32 byte
|
|
|
423 struct Node {
|
|
|
424 int key;
|
|
|
425 union Data* value;
|
|
|
426 struct Node* left;
|
|
|
427 struct Node* right;
|
|
|
428 enum Color {
|
|
|
429 Red,
|
|
|
430 Black,
|
|
|
431 } color;
|
|
|
432 } node;
|
|
|
433 };
|
|
|
434 ```
|
|
|
435
|
|
|
436 # Persistent Data Tree
|
|
24
|
437 * 親を取得し、親からの参照を変更して親をスタックに積み直す
|
|
|
438 * 自分と左右の3点のノードで回転を行うことで平衡にする
|
|
|
439 * 回転後も条件を満たしているか確認する必要がある
|
|
|
440
|
|
|
441 ```C
|
|
|
442 // Code Gear
|
|
|
443 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
|
|
|
444 struct Node* tmp = node->right;
|
|
|
445 struct Node* parent = 0;
|
|
|
446
|
|
|
447 stack_pop(context->node_stack, &parent);
|
|
|
448
|
|
|
449 if (parent) {
|
|
|
450 if (node == parent->left)
|
|
|
451 parent->left = tmp;
|
|
|
452 else
|
|
|
453 parent->right = tmp;
|
|
|
454 } else {
|
|
|
455 tree->root = tmp;
|
|
|
456 }
|
|
|
457
|
|
|
458 stack_push(context->node_stack, &parent);
|
|
|
459
|
|
|
460 node->right = tmp->left;
|
|
|
461 tmp->left = node;
|
|
|
462 traverse->current = tmp;
|
|
|
463
|
|
|
464 stack_pop(context->code_stack, &context->next);
|
|
|
465 goto meta(context, context->next);
|
|
|
466 }
|
|
|
467
|
|
|
468 // Meta Code Gear(stub)
|
|
|
469 __code rotateLeft_stub(struct Context* context) {
|
|
|
470 goto rotateLeft(context,
|
|
|
471 context->data[Traverse]->traverse.current,
|
|
|
472 &context->data[Tree]->tree,
|
|
|
473 &context->data[Traverse]->traverse);
|
|
|
474 }
|
|
|
475 ```
|
|
|
476
|
|
|
477 # Worker
|
|
|
478 * TaskQueue から Task を取得して実行
|
|
|
479 * TaskQueue へのアクセスには CAS 命令を用いる
|
|
|
480 * Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている
|
|
|
481 * Task が完了したら次の Task を取得するために GetQueue に戻ってくる必要がある
|
|
|
482 * CAS に失敗したら CAS をやり直すために自分自身に継続する
|
|
|
483
|
|
|
484 ```C
|
|
|
485 // Task definication
|
|
|
486 union Data {
|
|
|
487 // size: 8 byte
|
|
|
488 struct Task {
|
|
|
489 enum Code code;
|
|
|
490 int key;
|
|
|
491 } task;
|
|
|
492 }
|
|
|
493 ```
|
|
|
494
|
|
|
495 ```C
|
|
|
496 // Dequeue
|
|
|
497 __code getQueue(struct Context* context, struct Queue* queue, struct Node* node) {
|
|
|
498 if (queue->first == 0)
|
|
|
499 return;
|
|
|
500
|
|
|
501 struct Element* first = queue->first;
|
|
|
502 if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) {
|
|
|
503 queue->count--;
|
|
|
504
|
|
|
505 context->next = GetQueue;
|
|
|
506 stack_push(context->code_stack, &context->next);
|
|
|
507
|
|
|
508 context->next = first->task->code;
|
|
|
509 node->key = first->task->key;
|
|
|
510
|
|
|
511 goto meta(context, GetTree);
|
|
|
512 } else {
|
|
|
513 goto meta(context, GetQueue);
|
|
|
514 }
|
|
|
515 }
|
|
|
516 ```
|
|
|
517
|
|
|
518 # Worker
|
|
|
519 * Worker で実行される Code Gear は特別なものではなく、他の Code Gear と同じ記述である
|
|
|
520 * 依存関係のない Code Gear はすべて並列に動作させることができることを意味する
|
|
|
521 * Gears OS 自体が Code Gear によって構成され、Gears OS の実装自体が Gears Programming の指針となる
|
|
|
522
|
|
|
523 ```C
|
|
|
524 // Code Gear
|
|
|
525 __code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int alignment, int* array) {
|
|
|
526 int i = loopCounter->i;
|
|
|
527
|
|
|
528 if (i < alignment) {
|
|
|
529 array[i+index*alignment] = array[i+index*alignment]*2;
|
|
|
530 loopCounter->i++;
|
|
|
531
|
|
|
532 goto meta(context, Twice);
|
|
|
533 }
|
|
|
534
|
|
|
535 loopCounter->i = 0;
|
|
|
536
|
|
|
537 stack_pop(context->code_stack, &context->next);
|
|
|
538 goto meta(context, context->next);
|
|
|
539 }
|
|
|
540
|
|
|
541 // Meta Code Gear(stub)
|
|
|
542 __code twice_stub(struct Context* context) {
|
|
|
543 goto twice(context,
|
|
|
544 &context->data[LoopCounter]->loopCounter,
|
|
|
545 context->data[Node]->node.value->array.index,
|
|
|
546 context->data[Node]->node.value->array.alignment,
|
|
|
547 context->data[Node]->node.value->array.array);
|
|
|
548 }
|
|
|
549 ```
|
|
|
550
|
|
|
551 # TaskManager
|
|
|
552 * TaskManager は Task の依存関係の解決を行う
|
|
|
553 * Worker の起動・停止も行う
|
|
|
554
|
|
|
555 ```C
|
|
|
556 // Code Gear
|
|
|
557 __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
|
|
|
558 int i = loopCounter->i;
|
|
|
559
|
|
|
560 if (i < worker->num) {
|
|
|
561 struct Context* worker_context = &worker->contexts[i];
|
|
|
562 worker_context->next = GetQueue;
|
|
|
563 worker_context->data[Tree] = context->data[Tree];
|
|
|
564 worker_context->data[ActiveQueue] = context->data[ActiveQueue];
|
|
|
565 pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context);
|
|
|
566 worker_context->thread_num = i;
|
|
|
567 loopCounter->i++;
|
|
|
568
|
|
|
569 goto meta(context, CreateWorker);
|
|
|
570 }
|
|
|
571
|
|
|
572 loopCounter->i = 0;
|
|
|
573 goto meta(context, TaskManager);
|
|
|
574 }
|
|
|
575
|
|
|
576 // Meta Code Gear
|
|
|
577 __code createWorker_stub(struct Context* context) {
|
|
|
578 goto createWorker(context,
|
|
|
579 &context->data[LoopCounter]->loopCounter,
|
|
|
580 &context->data[Worker]->worker);
|
|
|
581 }
|
|
|
582 ```
|
|
|
583
|
|
|
584 # Gears OS の評価
|
|
|
585 * Red-Black Tree アルゴリズムに基づいて非破壊木構造で構築される Persistent Data Tree
|
|
|
586 * CAS 命令を用いてアクセスすることで並列に動作させてもデータの一貫性を保証する TaskQueue
|
|
|
587 * TaskQueue から Task を取得し実行する Worker
|
|
|
588
|
|
|
589 Gears OS を用いて依存関係のない並列処理を実行可能な状態となった
|
|
|
590
|
|
|
591 簡単な並列処理の例題を実装し、評価を行う
|
|
|
592
|
|
|
593 # Twice
|
|
|
594 依存関係のない簡単な例題として Twice を実装した
|
|
|
595
|
|
|
596 Twice は与えられた整数配列を2倍にする例題である
|
|
|
597
|
|
|
598 * 配列のサイズを元に処理範囲と処理量を決める index, alignment, 配列へのポインタを持つ Data Gear に分割
|
|
|
599 * Data Gear を Persistent Data Tree に挿入
|
|
|
600 * 実行する Code Gear(Twice) と実行に必要な Data Gear の key を持つ Task を生成
|
|
|
601 * 生成した Task を TaskQueue に挿入
|
|
|
602 * Worker の起動
|
|
|
603 * Worker が TaskQueue から Task を取得
|
|
|
604 * 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得
|
|
|
605 * Code Gear(Twice) を実行
|
|
|
606
|
|
|
607 # Result
|
|
|
608 * 要素数：2<sup>17</sup> * 1000 elements
|
|
|
609 * 分割数：640 tasks
|
|
|
610 * 1 Task 当たりの処理量：2<sup>11</sup> * 100 elements
|
|
|
611
|
|
|
612 <table border="1" align='center' width='50%'>
|
|
|
613 <tbody>
|
|
|
614 <tr>
|
|
|
615 <td style="text-align: center;">Number of Processors</td>
|
|
|
616 <td style="text-align: center;">Time(ms)</td>
|
|
|
617 </tr>
|
|
|
618 <tr>
|
|
|
619 <td style="text-align: center;">1 CPU</td>
|
|
|
620 <td style="text-align: right;">1315</td>
|
|
|
621 </tr>
|
|
|
622 <tr>
|
|
|
623 <td style="text-align: center;">2 CPUs</td>
|
|
|
624 <td style="text-align: right;">689</td>
|
|
|
625 </tr>
|
|
|
626 <tr>
|
|
|
627 <td style="text-align: center;">4 CPUs</td>
|
|
|
628 <td style="text-align: right;">366</td>
|
|
|
629 </tr>
|
|
|
630 <tr>
|
|
|
631 <td style="text-align: center;">8 CPUs</td>
|
|
|
632 <td style="text-align: right;">189</td>
|
|
|
633 </tr>
|
|
|
634 <tr>
|
|
|
635 <td style="text-align: center;">12 CPUs</td>
|
|
|
636 <td style="text-align: right;">111</td>
|
|
|
637 </tr>
|
|
|
638 </tbody>
|
|
|
639 </table>
|
|
|
640
|
|
|
641 <table width="70%" align="center">
|
|
|
642 <tr>
|
|
|
643 <td><div align="center"><img src="pictures/twice.svg" width="1024"></div></td>
|
|
|
644 </tr>
|
|
|
645 </table>
|
|
|
646
|
|
|
647 1 CPU と 12 CPU で約11.8倍の速度向上を確認した
|
|
|
648
|
|
|
649 十分な台数効果が出ていることがわかる
|
|
|
650
|
|
|
651 # まとめ
|
|
|
652 * Cerium を開発して得られた知見から Code/Data Segment を持つ Gears OS を設計した
|
|
|
653 * 基本的な機能として Allocator, TaskQueue, Persistent Data Tree, Worker を実装した
|
|
|
654 * 実装した基本的な機能を組み合わせ Gears OS のプロトタイプを作成し、依存関係のない簡単な並列処理の例題を実装した
|
|
|
655 * Gears OS がオーバーヘッドにならず、十分な台数効果が出ることを確認した
|
|
|
656 * Gears OS の実装自体が Gears OS を用いて並列処理を記述する際の指針となるように実装した
|
|
|
657
|
|
|
658 # 今後の課題
|
|
|
659 * 一般的に並列処理には依存関係が存在する。
|
|
|
660 複雑な並列処理を実行できるようにするために依存関係を解決する TaskManager を実装する必要がある
|
|
|
661 * GPU など他のプロセッサを演算に利用することができない。
|
|
|
662 Code/Data Segment を用いて各プロセッサにのアーキテクチャにマッピングした実行機構を実装する必要がある
|
|
|
663 * Data Segment 専用の構文を用意するべきである。
|
|
|
664 いまの実装では必要ない Data Segment を持つ場合がある。
|
|
|
665 実行可能な Code Segment のリストから推論し必要な Data Segment のみを持つようにする必要がある
|
|
|
666 * Data Segment の型情報を検査する機能がない。
|
|
|
667 型シグネチャを導入し、プログラムの正しさを保証する型システムを Gears OS 上に実装する必要がある |
