Papers/2017/ikkun-sigos: presen/sigos.md~ comparison

comparison presen/sigos.md~ @ 30:3050872e76df

merge

author	ikkun
date	Tue, 16 May 2017 01:19:23 +0900
parents
children

comparison

equal deleted inserted replaced

-:ebf75ff50c46
+:3050872e76df
+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 を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能
+<div style="text-align: center;">
+<img src="./images/codeGear_dataGear.svg" alt="message" width="450">
+</div>
+## Gears OS の柔軟性
+- Gears OS は Meta Computation を使用することで
+- データ拡張や機能の追加
+- GPU 等のさまざまなアーキテクチャでも同じプログラムの動作
+- バージョンが異なる者同士がネットワーク接続しても通信
+等を柔軟に対応する
+- Meta Computation は 通常の Computaiton と階層を分けて処理を行う
+<div style="text-align: center;">
+<img src="./images/meta_gear.svg" alt="message" width="800">
+</div>
+## 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 の並列実行を行う
+<div style="text-align: center;">
+<img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600">
+</div>
+## 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 接続部分は見えないように実装を行う
+<div style="text-align: center;">
+<img src="./images/meta_cg_dg.svg" alt="message" width="850">
+</div>
+## 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 になる
+<div style="text-align: center;">
+<img src="./images/persistent_date_tree_2.svg" alt="message" width="800">
+</div>
+## 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 を取得して実行する
+<table align='center'>
+<tbody>
+<tr>
+<td>
+<div>
+<img src="./images/worker.svg" alt="message" width="600">
+</div>
+</td>
+<td>
+<ol>
+<li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
+<li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
+<li> Task に格納されている Code Gear を実行する </li>
+<li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
+</ol>
+</td>
+</tr>
+</tbody>
+</table>
+- Task が完了したら次の Task を取得する
+## TaskManger
+- TaskManager は Task の依存関係の解決を行う
+- Thread の作成と停止も行う
+<div style="text-align: center;">
+<img src="./images/taskManager.svg" alt="message" width="800">
+</div>
+## プロトタイプの実行
+- 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
+- これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
+## Gears OS で実行する Code Gear 例
+- プロトタイプのタスクの例題として Twice を実装した
+- Twice は与えられた整数配列を2倍にする例題である
+``` c
+// Twice Code Gear
+__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
+int i = loopCounter->i;
+if (i < alignment) {
+array[i+index*alignment] = array[i+index*alignment]*2;
+loopCounter->i++;
+goto twice(loopCounter, index, alignment, array);
+}
+loopCounter->i = 0;
+goto exit();
+}
+```
+## 並列処理の確認
+- Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
+- 環境
+- Memory : 16GB
+- CPU : 6-core Intel Xeon 2.66GHZ x 2
+- 要素数 : 2^17 * 1000
+- 分割数 : 640 タスク
+- 1 Task 当たりの処理量 : 2^11 * 100 elements
+<table  border="1" align='center' width='50%'>
+<tbody>
+<tr>
+<td style="text-align: center;">Number of Processors</td>
+<td style="text-align: center;">Time(ms)</td>
+</tr>
+<tr>
+<td style="text-align: center;">1 CPU</td>
+<td style="text-align: right;">1315</td>
+</tr>
+<tr>
+<td style="text-align: center;">2 CPUs</td>
+<td style="text-align: right;">689</td>
+</tr>
+<tr>
+<td style="text-align: center;">4 CPUs</td>
+<td style="text-align: right;">366</td>
+</tr>
+<tr>
+<td style="text-align: center;">8 CPUs</td>
+<td style="text-align: right;">189</td>
+</tr>
+<tr>
+<td style="text-align: center;">12 CPUs</td>
+<td style="text-align: right;">111</td>
+</tr>
+</tbody>
+</table>
+- 1cpu と 12cpu では 11.8 倍の向上が見られた
+## Cerium との比較
+- Cerium は本研究室で開発していた並列プログラミングフレームワーク
+- Cerium では Task を依存関係に沿って実行することで並列実行を可能にする
+- 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない
+- Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる
+- Task には汎用ポインタとしてデータの受け渡しを行う
+- 型情報がなく、型の検査を行うことが出来ない
+- Gears OS では 型情報をもつ Data Gear を定義
+## 既存の OS への対応
+- Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義
+- 通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う
+## まとめ
+- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
+- 依存関係のない Twice を実装し、並列処理が行えることを確認した
+## 今後の課題
+- 一般的に並列処理には依存関係が存在する
+- 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、  依存関係のある並列処理の例題を作成し、評価する
+- GPUなどの他のプロセッサ演算に利用することが出来ない
+- Data Gear などのデータをGPUにマッピングするための機構が必要
+- Gears OS でのデバック手法
+- 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案
+- 並列処理でのデバック手法も考案する必要がある
+- 型情報の検査
+- プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する
+- Contextの動的生成
+- 今は静的に自分で生成している
+- CbC 用の Runtime をつくり、 Context を動的に生成

Mercurial > hg > Papers > 2017 > ikkun-sigos

comparison presen/sigos.md~ @ 30:3050872e76df