- -

Gears OS

Gears OS は Code Gear と Data Gear によって構成される
Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする
Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する
Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される
Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する
依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる
Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される
検証 +
- モデル検査を行う
- できるだけ有限状態
- スタックや環境など不必要に状態を入れない
+
証明 +
- Code Gear と Data Gear を理論に定義
+

@@ -158,12 +148,10 @@

Code Gear、 Data Gear

Code Gear はプログラムの処理そのものを表す
任意の数の Input Data Gear を参照し、 Code Gear の処理が完了すると任意の数の Output Data Gear を生成する
Code Gear は接続された Input Data Gear 以外の Data にはアクセスしない
Data Gear は Data そのものを表す
int や文字列などの Primitive Data Type が入っている
Code Gear から参照される Data Gear を Input Data Gear、 Code Gear の処理で生成される結果を Output Data Gear を呼ぶ
Data Gear は int や文字列などの Data そのものを表す
Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する

@@ -187,9 +175,10 @@

Meta Computation

Gears OS では通常の Computation のために実行する Computation を Meta Computation として扱う
Meta Computation の例として並列処理の依存関係の解決、 OSが行うネットワーク管理、メモリ管理等がある
Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現する
Gears OS の柔軟性は Meta Computation で実現
Meta Computation は通常の Computation のための Computation
並列処理の依存関係の解決、 GPUなどの別アーキテクチャでの実行のための処理など
Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現

@@ -198,8 +187,10 @@

Meta Gear

Meta Code Gear は通常の Code Gear の直後に接続され、 Meta Computation を実行する
Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続する
Meta Code Gear は通常の Code Gear の直後に接続され、 Meta Computation を実行
Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続
Meta Data Gear はMeta Computation を行うために使用する Data Gear
Meta 部分は Normal Level からなるべく見えない

@@ -214,7 +205,7 @@

Gears OS の実装は本研究室で開発しているCbC(Continuation based C)を用いる
CbC は処理を Code Segment を用いて記述する事を基本とする
そのため Gears OS の Code Gear を記述する事に適している
Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している

@@ -223,21 +214,192 @@

Continuation based C

Code Segment の定義は __code CS名 で行う
Code Segment の定義は __code CS名 で行う +
- Code Gear も同等に定義する
+
Code Segment 間は goto CS名 で移動する。この移動を継続と呼ぶ
C の関数呼び出しとは違い、 Code Segment では戻り値を持たないため、スタックに値を積まない
このような元の環境を持たない継続を計量継続と呼ぶ

/* code1 define */
+__code code1(List list) {
+    ....
+    goto code2(list)
+}
+
+/* code2 define */
+__code code2(List list) {
+    ...
+}
+

+ + +

+ +

Context

Context は接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている
Gear にアクセスする際は Context を経由する
Gears OS では Worker 毎にContext を持っている

+ +

Context

実行可能な Code Gear の名前は enum で定義する
Context の初期化時に名前と関数ポインタを対応付ける

+ +

enum Code {
+    Code1,
+    Code2,
+    Code3,
+    Exit,
+};
+

+ + +

+ +

Context

Context は C の構造体で表現される

+ +

/* context define */
+struct Context {
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    union Data **data;
+};
+

+ +

実行可能な Code Gear の数を示す CodeNum
実行可能な Code Gear へのポイント Code
Data Gear の Allocate 用の heapStart, heap, heapLimit
Data Gear の数を示す dataNum
Data Gear へのポインタ data

Gears OS の構成

Data Gear の表現

使用する Data Gear は C の共用体と構造体を用いた表現をする
これを元に Gears OS は必要な Data Gear を allocate する

+ +

/* 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 Code Gear である Context をあまり参照したくない
そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
stub は一種の Meta Code Gear である

+ +

__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);
+}
+

+ + +

+ +

CbC の Gears OS サポート

通常の goto の継続では Meta Code Gear への継続が見えてしまう
Code Gear の指定も一度 Meta を挟む必要があるので enum を指定することで行っている

+ +

__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) {
+    ...
+}
+
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Node]->node.value->array);
+}
+

+ + +

+ +

CbC の Gears OS サポート

Meta Code Gear への接続を自動的に行う構文サポートを行う
stub の自動生成も行う

+ +

__code code1(struct Context* context, 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 Context* context, struct Array* array) {
+    ...
+}
+

+ + +

+ +

Gears OS の構成

Context

Gears OS の構成

Persistent Data Tree

Gears OS の構成

Worker

Context

Context は接続可能な Code/Data Gearへの参照をもっている
Gears OS では必要な Code/Data Gear を参照したい場合、 Context を通す必要がある

メインとなる Context と Worker 用 Context がある

TaskQueue と Persistent Data Tree はすべての Context で共有する
Task が完了したら次の Task を取得する

// Task definication
+// Task define
 union Data {
     // size: 8 byte
     struct Task {
@@ -441,7 +602,6 @@
         queue->count--;
 
         context->next = GetQueue;
-        stack_push(context->code_stack, &context->next);
 
         context->next = first->task->code;
         node->key = first->task->key;
@@ -532,7 +692,6 @@
 
     loopCounter->i = 0;
 
-    stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
@@ -596,6 +755,7 @@
 
 
   1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた
+  十分な台数効果が出てる事がわかる
 
 
 
@@ -610,21 +770,41 @@
 
 まとめ
 
-  Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った
+  Cerium を開発して得られた知見か らCode Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った
   Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
-  依存関係のない Twice を用いて並列処理を行い性能を示した
+  依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した


 
 
-課題
+今後の課題
 
-  依存関係のある並列処理の例題を作成し、評価する
-  GPU への対応
-  Gears OS でのデバック手法
-  型情報の検査を Meta Computation で行う
+  一般的に並列処理には依存関係が存在する
+    
+      複雑な並列処理を実行できるようにするために依存関係のある並列処理の例題を作成し、評価する
+    
+  
+  GPUなどの他のプロセッサ演算に利用することが出来ない
+    
+      Data Gear などのデータをGPUにマッピングするための機構が必要
+    
+  
+  Gears OS でのデバック手法
+    
+      軽量継続はスタックを積まないため、スタックトレースが見えない
+      Context から Data Gear を取得できるため、そこから現在の状況を把握することができる
+      Context を見ることができる コードを Meta Computation として入れることで Code Gear を止めて、 Data Gear の状態を見ることができる
+      しかし、 Gears OS は並列実行を基本とするため、 並列で動いているCode Gear に対しては綺麗にデバック出来ない
+      並列処理でのデバック手法も考案する必要がある
+    
+  
+  型情報の検査
+    
+      プログラムの正しさを保証するために Data Gear 野方情報を検査するシステムを Meta Computation として実装する
+    
+  
 
 
 
diff -r f3161681d273 -r f88786cba8b5 presen/sigos.md
--- a/presen/sigos.md	Sat May 28 18:57:36 2016 +0900
+++ b/presen/sigos.md	Sun May 29 16:34:28 2016 +0900
@@ -4,33 +4,23 @@
 lang: Japanese
 code-engine: coderay
 
-## Gears OS
-- CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている
-- そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある
-- マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない
-- また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している
-- 並列処理をする上でこれらのリソースを無視することができない
-- しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる
-- 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる
-- 本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS のプロトタイプ設計・実装を行い、簡単な例題を用いて評価を行う
+## Gears OS の並列性
+- Code Gear と Data Gear という Code と Data の単位を使って構成される
+- Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能
 
-## Cerium
-- Cerium は本研究室で開発していた並列プログラミングフレームワーク
-- Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする
-- 依存関係を Task 間で設定する
-
-## Cerium の問題点
-- 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない
-- Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、 汎用ポインタをキャストして利用している
+## Gears OS の柔軟性
+- Gear を追加することでデータ拡張や機能の追加が可能
+- GPU などの CPU とは異なるアーキテクチャでも同じプログラムが動く
+- バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う
+- 実行時の処理の変更を可能とする
 
-## Gears OS 
-- Gears OS は Code Gear と Data Gear によって構成される
-- Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする
-- Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する
-- Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される
-- Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する
-- 依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる 
-- Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される
+## Gears OS の信頼性
+- 検証
+    - モデル検査を行う
+    - できるだけ有限状態
+    - スタックや環境など不必要に状態を入れない
+- 証明
+    - Code Gear と Data Gear を理論に定義
 
 ## Gears OS での Gear
 - Gears OS はプログラムの単位として Gear を用いる
@@ -39,11 +29,9 @@
 
 ## Code Gear、 Data Gear
 - Code Gear はプログラムの処理そのものを表す
-- 任意の数の Input Data Gear を参照し、 Code Gear の処理が完了すると任意の数の Output Data Gear を生成する
-- Code Gear は接続された Input Data Gear 以外の Data にはアクセスしない
-- Data Gear は Data そのものを表す
-- int や 文字列などの Primitive Data Type が入っている
-- Code Gear から参照される Data Gear を Input Data Gear、 Code Gear の処理で生成される結果を Output Data Gear を呼ぶ
+- Data Gear は int や 文字列などの Data そのものを表す
+- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
+
 
     
 
@@ -56,33 +44,168 @@


 
 ## Meta Computation
-- Gears OS では通常の Computation のために実行する Computation を Meta Computation として扱う
-- Meta Computation の例として並列処理の依存関係の解決、 OSが行うネットワーク管理、メモリ管理等がある
-- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現する
+- Gears OS の柔軟性は Meta Computation で実現
+- Meta Computation は通常の Computation のための Computation
+- 並列処理の依存関係の解決、 GPUなどの別アーキテクチャでの実行のための処理など
+- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現
 
 ## Meta Gear
-- Meta Code Gear は 通常の Code Gear の直後に接続され、 Meta Computation を実行する
-- Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続する
+- Meta Code Gear は 通常の Code Gear の直後に接続され、 Meta Computation を実行
+- Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続
+- Meta Data Gear はMeta Computation を行うために使用する Data Gear
+- Meta 部分は Normal Level からなるべく見えない
 
 
     
 
 
+
 ## Continuation based C
 - Gears OS の実装は本研究室で開発しているCbC(Continuation based C)を用いる
 - CbC は処理を Code Segment を用いて記述する事を基本とする
-- そのため Gears OS の Code Gear を記述する事に適している
+- Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している
 
 ## Continuation based C
 - Code Segment の定義は ``__code CS名`` で行う
+    - Code Gear も同等に定義する
 - Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
 - C の関数呼び出しとは違い、 Code Segment では戻り値を持たないため、スタックに値を積まない
 - このような元の環境を持たない継続を計量継続と呼ぶ
 
-
-    
-
+``` c
+/* code1 define */
+__code code1(List list) {
+    ....
+    goto code2(list)
+}
+
+/* code2 define */
+__code code2(List list) {
+    ...
+}
+```
+
+## Context
+- Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている
+- Gear にアクセスする際は Context を経由する
+- Gears OS では Worker 毎にContext を持っている
+
+## Context
+- 実行可能な Code Gear の名前は **enum** で定義する
+- Context の初期化時に名前と関数ポインタを対応付ける
+
+``` c
+enum Code {
+    Code1,
+    Code2,
+    Code3,
+    Exit,
+};
+```
+
+## Context
+- Context は C の構造体で表現される
+
+``` c
+/* context define */
+struct Context {
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    union Data **data;
+};
+```
+
+- 実行可能な Code Gear の数を示す **CodeNum**
+- 実行可能な Code Gear へのポイント **Code**
+- Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit**
+- Data Gear の数を示す **dataNum**
+- Data Gear へのポインタ **data**
+
+## 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 Code Gear である Context をあまり参照したくない
+- そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
+- stub は一種の Meta Code Gear である
+
+``` 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);
+}
+```
+
+
+## CbC の Gears OS サポート
+- 通常の goto の継続では Meta Code Gear への継続が見えてしまう
+- Code Gear の指定も 一度 Meta を挟む必要があるので enum を指定することで行っている
+
+``` 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) {
+    ...
+}
+
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Node]->node.value->array);
+}
+```
+
+## CbC の Gears OS サポート
+- Meta Code Gear への接続を自動的に行う構文サポートを行う
+- stub の自動生成も行う
+
+``` c
+__code code1(struct Context* context, 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 Context* context, struct Array* array) {
+    ...
+}
+```
 
 ## Gears OS の構成
 - Context
@@ -121,7 +244,6 @@
 
 ## Context
 - Context は接続可能な Code/Data Gearへの参照をもっている
-- Gears OS では必要な  Code/Data Gear を参照したい場合、 Context を通す必要がある
 - メインとなる Context と Worker 用 Context がある
     - TaskQueue と Persistent Data Tree はすべての Context で共有する
     - Worker 毎に作られる Temporal Data Gear のメモリ空間は Context 毎に異なる
@@ -146,7 +268,7 @@
     Element
 };
 
-// Data Gear definication
+// Data Gear define
 union Data {
     struct Queue {
         struct Element* first;
@@ -183,16 +305,7 @@
 ## Persistent Data Tree
 - Persistent Data Tree は Data Gear の管理を行う
 - TaskQueue と同じですべての Context で共有される
-- 一度破壊した木構造を破壊すること無く新しい木構造を構築するため、変更して読み書き可能
-- 非破壊木構造はルートから変更したいノードへのパスすべてをコピーし、パズ上に存在しないノードはコピー元の木構造と共有する
-
-
-    
-
-
-## Persistent Data Tree
-- 木構造を構築するとき最悪なケースでは事実上の線形リストになる
-- そのため、挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
+- 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
 
 ## Worker
 - Worker は TaskQueue から Task を取得して実行する
@@ -201,7 +314,7 @@
 - Task が完了したら次の Task を取得する
 
 ``` c
-// Task definication
+// Task define
 union Data {
     // size: 8 byte
     struct Task {
@@ -221,7 +334,6 @@
         queue->count--;
 
         context->next = GetQueue;
-        stack_push(context->code_stack, &context->next);
 
         context->next = first->task->code;
         node->key = first->task->key;
@@ -290,7 +402,6 @@
 
     loopCounter->i = 0;
 
-    stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 ```
@@ -340,16 +451,29 @@