title: Gears OSにおける並列処理
author: 東恩納 琢偉
profile: 琉球大学理工学研究科
lang: Japanese
code-engine: coderay
## Gears OS
- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて分けることによって
- 並列性
- 柔軟性
- 信頼性
を指標とした Gears OS を設計してきた
- 本研究では Gears OS のプロトタイプとして並列処理機構を Continuation based C(CbC) で実装を行う
## Gears OS の並列性
- Gears OS はプログラムの単位として Gear を用いる
- Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある
- Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能
## Gears OS の柔軟性
- Gears OS は Meta Computation を使用することで
- データ拡張や機能の追加
- GPU 等のさまざまなアーキテクチャでも同じプログラムの動作
- バージョンが異なる者同士がネットワーク接続しても通信
等を柔軟に対応する
- Meta Computation は 通常の Computaiton と階層を分けて処理を行う
## Gears OS の信頼性
- 検証
- モデル検査を行う
- モデル検査は状態の数が膨大になると検査するのが難しい
- そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う
- 証明
- Code Gear と Data Gear を理論的に定義
## この発表は
- Gears OS でのGear
- Meta Computation
- Continuation based C(CbC)
- CbC を用いた Gears OS の記述
- Gears OS の並列処理のプロトタイプ
- まとめ
- 課題
## Code Gear、 Data Gear
- Gears OS は Code Gear、 Data Gear という Gear で構成される
- Code Gear はプログラムの処理そのものを表す
- Data Gear は int や 文字列などの Data そのものを表す
- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う
## Meta Computation
- Meta Computation は通常の Computation のための Computation
- 並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理などを行う
- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現
## Meta Gear
- Meta Computation は Code/Data Gearの接続の間に行われる
- Meta Computation の処理も Code/Data Gear で実現する
- この Gear を Meta Code/Data Gearと呼ぶ
- Meta Code Gear は Meta Computation のプログラム部分
- Meta Data Gear は Meta Code Gear で管理されるデータ部分
- Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う
## Continuation based C
- Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる
- CbC は処理を Code Segment を用いて記述する事を基本とする
- Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している
## Continuation based C
- Code Segment の定義は ``__code CS名`` で行う
- Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
- Code Segment の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
- このような環境を持たない継続を軽量継続と呼ぶ
## Continuation based C
- このコードは code1、code2 の2つの Code Segment を定義している
- code1 内の ``goto code2`` でcode2 への継続を行っている
``` c
/* code1 define */
__code code1(List list) {
....
goto code2(list)
}
/* code2 define */
__code code2(List list) {
...
}
```
## CbC を用いた Gears OS の記述
- Gears OS での Code Gear も Code Segment の定義のように記述する
- 各 Code Gear の引数は 必要な Data Gear を示す
- このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている
``` c
__code code1(struct Array* array, struct LoopCounter* loopCounter) {
...
goto code2(array);
}
__code meta_code1(struct Context* context, enum Code next) {
goto (context->code[next])(context);
}
__code code2(struct Array* array) {
...
}
```
## CbC の Gears OS サポート
- 実際は code1 から code2 への継続の間には Meta Code Gear である meta_code1 が実行される
- 通常は Meta Level の継続をプログラマーは意識する必要はない
- そこで、CbC は Code Gear 間の接続に自動的に Meta Code Gear を挟むというサポートを行う
- CbC のサポートを行うとこのコードのように展開される
- メタレベルのサポートの際は **context** という Meta Data Gear を使用する
``` c
__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
...
goto meta_code1(context, Code2);
}
__code code1_stub(struct Context* context) {
goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
}
__code meta_code1(struct Context* context, enum Code next) {
goto (context->code[next])(context);
}
__code code2(struct Context* context, struct Array* array) {
...
}
```
## Context
- Context は
- 接続可能な Code/Data Gear のリスト
- 独立したメモリ空間
をもっている
- 各 Code/Data Gear にアクセスする際は Context を経由する
## Context
- Context は
- 実行可能な Code Gear の数を示す **codeNum**
- 実行可能な Code Gear のリストを示す **code**
- Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit**
- Data Gear の数を示す **dataNum**
- Data Gear のリストを示す **data**
で構成される
``` c
/* context define */
struct Context {
int codeNum;
__code (**code) (struct Context*);
void* heapStart;
void* heap;
long heapLimit;
int dataNum;
union Data **data;
};
```
## Context
- 実行可能な Code Gear の名前は **enum code** で定義する
- Context の初期化時に名前と関数ポインタを対応付ける
- 現在の Gears ではこの enum code 使って接続先の Code Gear を指定する
``` c
enum Code {
Code1,
Code2,
Code3,
Exit,
};
```
## Data Gear の表現
- 使用する Data Gear は C の共用体と構造体を用いた表現をする
- これを元に Gears OS は 必要な Data Gear を allocate する
``` c
/* data Gear define */
union Data {
struct Time {
enum Code next;
double time;
} time;
struct LoopCounter {
int i;
} loopCounter;
....
};
```
## Code Gear の stub
- Data Gear にアクセスするにはContext を経由する
- だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
- stub は一種の Meta Code Gear であるため、 CbC で自動生成される
- このコードでは Array と LoopCounter が必要な code1 の stub を示している
``` c
__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
...
}
/* stub define */
__code code1_stub(struct Context* context) {
goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
}
```
## プロトタイプ の構成
- 今回は並列処理を行う機構の実装を行う
- 必要な要素は大きく5つ
- Context
- TaskQueue
- 実行される Task のリストを扱う
- Persistent Data Tree
- Code Gear によって参照される Data Gear の管理を行う
- Worker
- TaskQueue から Task を取得し、実行する
- TaskManager
- Persistent Data Tree を監視し、 Task の依存関係を解決する
※ TaskManager は今回未実装
## TaskQueue
- Task Queue は Task のリストを扱う
- すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
- TaskQueue は 2つで Data Gear で表現される
- 先頭と末尾の要素を持った Queue 表す Data Gear
- Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear
``` c
// Data Gear define
union Data {
struct Queue {
struct Element* first;
struct Element* last;
} queue;
struct Element {
struct Task* task;
struct Elemen* next;
} element
};
```
## TaskQueueの操作(Enqueue)
- Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
- 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある
``` c
__code putQueue3(struct Queue* queue, struct Element* new_element) {
struct Element* last = queue->last;
if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
last->next = new_element;
goto exit();
} else {
goto putQueue3(queue, new_element);
}
}
```
## Persistent Data Tree
- Persistent Data Tree は Data Gear の管理を行う
- TaskQueue と同じですべての Thread で共有される
- Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
- 木構造から読み出される Data Gear は Code Gear の Input Data Gear, 書き出すData Gear は Output Data Gear になる
## Persistent Data Tree
- Persistent Data Tree は
- Tree 自体を示す Data Gear
- Node を示す Data Gear
を用いて木構造を表現する
``` c
union Data {
struct Tree {
struct Node* root;
} tree;
struct Node {
int key; // comparable data segment
union Data* value;
struct Node* left;
struct Node* right;
// need to balancing
enum Color {
Red,
Black,
} color;
} node;
};
```
## Worker
- Worker は TaskQueue から Task を取得して実行する
