# HG changeset patch # User Tatsuki IHA # Date 1464541293 -32400 # Node ID 4c465c6fe2cc4daf56b69482931ce9a0d0efe7d8 # Parent f2f9c7110b4155231bc040d8e8f9a9b55f051845 Fix diff -r f2f9c7110b41 -r 4c465c6fe2cc paper/pic/codeGear_dataGear.graffle Binary file paper/pic/codeGear_dataGear.graffle has changed diff -r f2f9c7110b41 -r 4c465c6fe2cc paper/pic/codeGear_dataGear.pdf Binary file paper/pic/codeGear_dataGear.pdf has changed diff -r f2f9c7110b41 -r 4c465c6fe2cc paper/pic/codeGear_dataGear.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/pic/codeGear_dataGear.svg Mon May 30 02:01:33 2016 +0900 @@ -0,0 +1,201 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r f2f9c7110b41 -r 4c465c6fe2cc paper/pic/meta_cg_dg.graffle Binary file paper/pic/meta_cg_dg.graffle has changed diff -r f2f9c7110b41 -r 4c465c6fe2cc paper/pic/meta_cg_dg.pdf Binary file paper/pic/meta_cg_dg.pdf has changed diff -r f2f9c7110b41 -r 4c465c6fe2cc presen/images/codeGear_dataGear.svg --- a/presen/images/codeGear_dataGear.svg Sun May 29 19:28:03 2016 +0900 +++ b/presen/images/codeGear_dataGear.svg Mon May 30 02:01:33 2016 +0900 @@ -1,5 +1,5 @@ - + @@ -30,100 +30,172 @@ - + - - - - - - - - - - - + + + + + + + + + + + + + + + + + - - + + + + + + + + + + + + + + + + + + + + - - + + - - - - - - - - - + + + + + + + + + - + + + + + + + + + + + + + + + - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - + - + + + + + + + + + + + + + + + - + + + + + + + + + - - + + + + + + + + + + + + + + + + - - - + - - - - - - - - - - - - + + + + + + + + + - - - - - - - - - - - - - - - + + + + diff -r f2f9c7110b41 -r 4c465c6fe2cc presen/images/meta_cg_dg.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/images/meta_cg_dg.svg Mon May 30 02:01:33 2016 +0900 @@ -0,0 +1,275 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r f2f9c7110b41 -r 4c465c6fe2cc presen/sigos.html --- a/presen/sigos.html Sun May 29 19:28:03 2016 +0900 +++ b/presen/sigos.html Mon May 30 02:01:33 2016 +0900 @@ -75,7 +75,7 @@
伊波 立樹 - 琉球大学理工学研究科情報工学専攻 + 琉球大学理工学研究科
@@ -87,15 +87,26 @@

Gears OS

+ +

を指標とした Gears OS を設計してきた

+ + @@ -104,22 +115,40 @@

Gears OS の並列性

+
+ message +
+

Gears OS の柔軟性

+

等を柔軟に対応する

+ + + +
+ message +
+
@@ -129,13 +158,13 @@
  • 検証
    • モデル検査を行う
      • -
    • できるだけ有限状態
      • -
    • スタックや環境など不必要に状態を入れない
      • +
    • モデル検査は状態の数が膨大になると検査するのが難しい
      • +
    • そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う
  • 証明
      -
    • Code Gear と Data Gear を理論に定義
      • +
    • Code Gear と Data Gear を理論的に定義
    • @@ -144,11 +173,15 @@
    -

    Gears OS での Gear

    +

    この発表は

    @@ -160,23 +193,11 @@
  • Code Gear はプログラムの処理そのものを表す
  • Data Gear は int や 文字列などの Data そのものを表す
  • Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
    • +
  • Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う
    • - message -
    - - -
    -
    - -

    Code Gear、 Data Gear での並列実行

    - - -
    - message + message
    @@ -185,9 +206,8 @@

    Meta Computation

    @@ -197,14 +217,19 @@

    Meta Gear

    - message + message
    @@ -224,15 +249,21 @@

    Continuation based C

    + +
    +
    + +

    Continuation based C

    + + 
    /* code1 define */
 __code code1(List list) {
     ....
@@ -249,11 +280,76 @@
    +

    CbC を用いた Gears OS の記述

    +
      +
    • Gears OS での Code Gear も Code Segment の定義のように記述する
      • +
    • 各 Code Gear の引数は 必要な Data Gear を示す
      • +
    • このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている
      • +
    + +
    __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 を使用する
      • +
    + +
    __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 code2_stub(struct Context* context) {
+    goto code1(context, &context->data[Node]->node.value->array);
+}
+
    + + +
    +
    +

    Context

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

    Context

      -
    • 実行可能な Code Gear の名前は enum で定義する
      • -
    • Context の初期化時に名前と関数ポインタを対応付ける
      • -
    - -
    enum Code {
-    Code1,
-    Code2,
-    Code3,
-    Exit,
-};
-
    - - -
    -
    - -

    Context

    -
      -
    • Context は C の構造体で表現される
      • +
    • Context は +
        +
      • 実行可能な Code Gear の数を示す CodeNum
        • +
      • 実行可能な Code Gear のリストを示す Code
        • +
      • Data Gear の Allocate 用の heapStart, heap, heapLimit
        • +
      • Data Gear の数を示す dataNum
        • +
      • Data Gear のリストを示す data +で構成される
        • +
      + 
    /* context define */
@@ -295,14 +382,25 @@
 };
    + +
    +
    + +

    Context

      -
    • 実行可能な Code Gear の数を示す CodeNum
      • -
    • 実行可能な Code Gear へのポインタ Code
      • -
    • Data Gear の Allocate 用の heapStart, heap, heapLimit
      • -
    • Data Gear の数を示す dataNum
      • -
    • Data Gear へのポインタ data
      • +
    • 実行可能な Code Gear の名前は enum code で定義する
      • +
    • Context の初期化時に名前と関数ポインタを対応付ける
      • +
    • 現在の Gears ではこの enum code 使って接続先の Code Gear を指定する
    +
    enum Code {
+    Code1,
+    Code2,
+    Code3,
+    Exit,
+};
+
    +
    @@ -332,10 +430,11 @@

    Code Gear の stub

      -
    • 通常 Data Gear にアクセスするにはContext を経由しなければならない
      • -
    • しかし、通常の Code Gear ではMeta Data Gear である Context をあまり参照したくない
      • -
    • そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
      • -
    • stub は一種の Meta Code Gear である
      • +
    • 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 を示している
    __code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
@@ -352,73 +451,16 @@
    -

    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 code2_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
        -
      • Worker 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される
        • +
      • Thread 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される
    • TaskQueue
        -
      • CAS を利用したスレッドセーフなQueue
        • -
      • ActiveTaskQueue と WaitTaskQueue の 2種類
        • +
      • 実行される Task のリストを扱う
    @@ -457,9 +499,7 @@
    • Worker
        -
      • Worker は ActiveTaskQueue から Task を取得する
        • -
      • 取得した Task から必要な Data Gear を Tree から取得し、 Code Gear を実行
        • -
      • 実行後必要なデータを Persistent Data Tree 書き出す
        • +
      • TaskQueue から Task を取得し、実行する
    @@ -475,7 +515,7 @@

    TaskQueue

    • Task Queue は Task の管理を行う
      • -
    • すべての Worker の Context で共有される
      • +
    • すべての Worker の Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
    • TaskQueue は 2つで Data Gear で表現される
      • 先頭と末尾の要素を持った Queue 表す Data Gear
        • @@ -505,18 +545,18 @@

        TaskQueueの操作(Enqueue)

        • Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
          • -
        • 正しく最後の要素が変更できたことをCAS で 保証し、末尾の変更を行う必要がある
          • +
        • 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある
        -
        __code putQueue3(struct Context* context, struct Queue* queue, struct Element* new_element) {
+
        __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 meta(context, context->next);
+        goto exit();
     } else {
-        goto meta(context, PutQueue3);
+        goto putQueue3(queue, new_element);
     }
 }
 
@@ -529,9 +569,9 @@
 
        Persistent Data Tree
        
 
          
   
        • Persistent Data Tree は Data Gear の管理を行う
          • 
-  
        • TaskQueue と同じですべての Context で共有される
          • 
-  
        • 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
          • 
-  
        • Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う
          • 
+  
        • TaskQueue と同じですべての Thread で共有される
          • 
+  
        • Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
          • 
+  
        • unix のファイルシステムに相当する的な
          • 
 
        
 
 
@@ -542,52 +582,10 @@
 
          
   
        • Worker は TaskQueue から Task を取得して実行する
          • 
   
        • TaskQueue へのアクセスは Enqueue 操作と同じで CAS を用いる
          • 
-  
        • Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている
          • 
+  
        • Task には実行する Code Gear と実行に必要な Data Gear の ree の key が格納されている
          • 
   
        • Task が完了したら次の Task を取得する
          • 
-
        
-
-
        // Task define
-union Data {
-    // size: 8 byte
-    struct Task {
-        enum Code code;
-        int key;
-    } task;
-}
-
        
-
-
        __code getQueue(struct Context* context, struct Queue* queue, struct Node* node) {
-    if (queue->first == 0)
-        return;
-
-    struct Element* first = queue->first;
-    if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) {
-        queue->count--;
-
-        context->next = GetQueue;
-
-        context->next = first->task->code;
-        node->key = first->task->key;
-
-        struct Traverse *t = &context->data[Traverse]->traverse;
-        t->next = GetQueue;
-        goto meta(context, Get);
-    } else {
-        goto meta(context, GetQueue);
-    }
-}
-
-
        
-
-
-
    -
    - -

    Worker

    -
    • Worker で実行される Code Gear は他の Code Gear と同様の記述である
    • つまり依存関係のない Code Gear は並列で動作させることができる
      • -
    • Gears OS 自体が Code Gear によって構成されるため、 Gears OS の実装自体が Gears でプログラミングを行う際の指針になる
    @@ -597,10 +595,11 @@

    TaskManger

    • TaskManager は Task の依存関係の解決を行う
      • -
    • Worker の作成と停止も行う
      • +
    • Thread の作成と停止も行う
      • +
    • このコードは Thread の生成を行い、 Thread 毎の context を設定している Meta Code Gear
    -
    // Code Gear
+
    // Meta Code Gear
 __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
     int i = loopCounter->i;
 
@@ -625,37 +624,36 @@
    -

    プロトタイプの評価

    +

    プロトタイプの実行

    • 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
    • これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
      • -
    • Gears OS の評価として依存関係のない例題を実装して評価を行う
    -

    Twice

    +

    Gears で実行する Code Gear 例

      -
    • 依存関係のない例題として Twice を実装した
      • +
    • プロトタイプのタスクの例題として Twice を実装した
    • Twice は与えられた整数配列を2倍にする例題である
    // Twice Code Gear
-__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int alignment, int* array) {
+__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 meta(context, Twice);
+        goto twice(loopCounter, index, alignment, array);
     }
 
     loopCounter->i = 0;
 
-    goto meta(context, context->next);
+    goto exit();
 }
    @@ -663,9 +661,10 @@
    -

    実験環境

    +

    並列処理の確認

      -
    • 測定環境 +
    • Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
      • +
    • 環境
      • Model : MacPro Mid 2010
      • OS : Mac OS X 10.10.5
        • @@ -678,11 +677,6 @@
      • 1 Task 当たりの処理量 : 2^11 * 100 elements
      - -
    -
    - -

    結果

    @@ -712,13 +706,8 @@
    -
    - message -
    -
      -
    • 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた
      • -
    • 十分な台数効果が出てる事がわかる
      • +
    • 1cpu と 12cpu では 11.8 倍の向上が見られた
    @@ -730,12 +719,13 @@
  • Cerium は本研究室で開発していた並列プログラミングフレームワーク
  • Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする
      -
    • 本来 Task はデータに依存するもので Task 感の依存関係ではデータの依存関係を保証することが出来ない
      • +
    • 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない
    • Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる
    • -
  • また Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、型の検査を行うことが出来ない +
  • Task には汎用ポインタとしてデータの受け渡しを行う
      +
    • 型情報がなく、型の検査を行うことが出来ない
    • Gears OS では 型情報をもつ Data Gear を定義
    • @@ -749,6 +739,7 @@
    • Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義
    • 通常の Code Gear から必要な制御を推論し、 Meta Code Gear を接続することで従来のOSが行ってきた制御の提供を行う
      • +
    • 対応表書く
    @@ -759,7 +750,7 @@
    • Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った
    • Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
      • -
    • 依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した
      • +
    • 依存関係のない Twice を実装し、並列処理が行えることを確認した
    @@ -780,16 +771,19 @@
  • Gears OS でのデバック手法
      -
    • 軽量継続はスタックを積まないため、スタックトレースが見えない
      • -
    • Context から Data Gear を取得できるため、そこから現在の状況を把握することができる
      • -
    • Context を見ることができる コードを Meta Computation として入れることで Code Gear を止めて、 Data Gear の状態を見ることができる
      • -
    • しかし、 Gears OS は並列実行を基本とするため、 並列で動いているCode Gear に対しては綺麗にデバック出来ない
      • +
    • 軽量継続はスタックを積まないため、スタックトレースが見えないためその対策
    • 並列処理でのデバック手法も考案する必要がある
  • 型情報の検査
      -
    • プログラムの正しさを保証するために Data Gear 野方情報を検査するシステムを Meta Computation として実装する
      • +
    • プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する
      • +
    +
    • +
  • Contextの動的生成 +
      +
    • 今は静的に自分で生成している
      • +
    • CbC 用の Runtime をつくり、 Context を動的に生成
    • diff -r f2f9c7110b41 -r 4c465c6fe2cc presen/sigos.md --- a/presen/sigos.md Sun May 29 19:28:03 2016 +0900 +++ b/presen/sigos.md Mon May 30 02:01:33 2016 +0900 @@ -1,65 +1,84 @@ title: Code Gear、 Data Gear に基づく OS のプロトタイプ author: 伊波 立樹 -profile: 琉球大学理工学研究科情報工学専攻 +profile: 琉球大学理工学研究科 lang: Japanese code-engine: coderay ## Gears OS -- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて、並列性、柔軟性、信頼性を指標とした Gears OS を設計してきた -- 本研究では Gears OS のプロトタイプとして並列処理機構をCbC(Continuation based C) で実装し、並列処理を行う簡単な例題を用いて評価を行う +- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて + - 並列性 + - 柔軟性 + - 信頼性 + +を指標とした Gears OS を設計してきた + +- 本研究では Gears OS のプロトタイプとして並列処理機構をCbC(Continuation based C) で実装を行う ## Gears OS の並列性 -- Code Gear と Data Gear という Code と Data の単位を使って構成される +- Gears OS はプログラムの単位として Gear を用いる +- Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある - Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能 +
    + message +
    + ## Gears OS の柔軟性 -- Gear を追加することでデータ拡張や機能の追加が可能 -- GPU 等のさまざまなアーキテクチャでも同じプログラムが動く -- バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う -- 実行時の処理の変更を可能とする +- Gears OS は Meta Computation を使用することで + - データ拡張や機能の追加 + - GPU 等のさまざまなアーキテクチャでも同じプログラムの動作 + - バージョンが異なる者同士がネットワーク接続しても通信 + +等を柔軟に対応する + +- Meta Computation は 通常の Computaiton と階層を分けて処理を行う + +
    + message +
    ## Gears OS の信頼性 - 検証 - モデル検査を行う - - できるだけ有限状態 - - スタックや環境など不必要に状態を入れない + - モデル検査は状態の数が膨大になると検査するのが難しい + - そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う - 証明 - - Code Gear と Data Gear を理論に定義 + - Code Gear と Data Gear を理論的に定義 -## Gears OS での Gear -- Gears OS はプログラムの単位として Gear を用いる -- Gear は並列実行の単位、データの分割、 Gear 間の接続等になる -- Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある +## この発表は +- Gears OS でのGear +- Meta Computation +- Continuation based C(CbC) +- CbC を用いた Gears OS の記述 +- Gears OS のプロトタイプの構成 +- まとめ +- 課題 ## Code Gear、 Data Gear - Code Gear はプログラムの処理そのものを表す - Data Gear は int や 文字列などの Data そのものを表す - Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する +- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う
    - message + message
    -## Code Gear、 Data Gear での並列実行 -- Gears OS では Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う - -
    - message -
    ## Meta Computation -- Gears OS の柔軟性は Meta Computation で実現 - Meta Computation は通常の Computation のための Computation -- 並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理など +- 並列処理の依存関係の解決、 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 Data Gear はMeta Computation を行うために使用する Data Gear -- Meta 部分は Normal Level からなるべく見えない +- 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 は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う
    - message + message
    @@ -70,10 +89,13 @@ ## Continuation based C - Code Segment の定義は ``__code CS名`` で行う - - Code Gear も同等に定義する - Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ - C の関数呼び出しとは異なり、Code Segment では戻り値を持たない。このような環境を持たない継続を計量継続と呼ぶ +## Continuation based C +- このコードは code1、code2 の2つの Code Segment を定義している +- code1 内の ``goto code2`` でcode2 への継続を行っている + ``` c /* code1 define */ __code code1(List list) { @@ -87,85 +109,32 @@ } ``` -## Context -- Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている Meta Data Gear -- 各 Gear にアクセスする際は Context を経由する -- Worker 毎にContext を持っている - -## Context -- 実行可能な Code Gear の名前は **enum** で定義する -- Context の初期化時に名前と関数ポインタを対応付ける - -``` c -enum Code { - Code1, - Code2, - Code3, - Exit, -}; -``` - -## Context -- Context は C の構造体で表現される +## CbC を用いた Gears OS の記述 +- Gears OS での Code Gear も Code Segment の定義のように記述する +- 各 Code Gear の引数は 必要な Data Gear を示す +- このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている ``` 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 Data Gear である Context をあまり参照したくない -- そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する -- stub は一種の Meta Code Gear である - -``` c -__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { +__code code1(struct Array* array, struct LoopCounter* loopCounter) { ... + goto code2(array); } -/* stub define */ -__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 Array* array) { + ... } ``` - ## CbC の Gears OS サポート -- 通常の goto の継続では Meta Code Gear への継続が見えてしまう -- Code Gear の指定も 一度 Meta を挟む必要があるので enum を指定することで行っている +- 実際は 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) { @@ -190,31 +159,91 @@ } ``` -## CbC の Gears OS サポート -- Meta Code Gear への接続を自動的に行う構文サポートを行う -- stub の自動生成も行う +## 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) { ... - 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) { - ... +/* stub define */ +__code code1_stub(struct Context* context) { + goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter); } ``` ## Gears OS の構成 - Context - - Worker 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される + - Thread 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される - TaskQueue - - CAS を利用したスレッドセーフなQueue - - ActiveTaskQueue と WaitTaskQueue の 2種類 + - 実行される Task のリストを扱う
    message @@ -232,9 +261,7 @@ ## Gears OS の構成 - Worker - - Worker は ActiveTaskQueue から Task を取得する - - 取得した Task から必要な Data Gear を Tree から取得し、 Code Gear を実行 - - 実行後必要なデータを Persistent Data Tree 書き出す + - TaskQueue から Task を取得し、実行する
    message @@ -242,7 +269,7 @@ ## TaskQueue - Task Queue は Task の管理を行う -- すべての Worker の Context で共有される +- すべての Worker の Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する - TaskQueue は 2つで Data Gear で表現される - 先頭と末尾の要素を持った Queue 表す Data Gear - Task と次の要素へのポインタを持った、List を表現する Element という Data Gear @@ -264,18 +291,18 @@ ## TaskQueueの操作(Enqueue) - Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定 -- 正しく最後の要素が変更できたことをCAS で 保証し、末尾の変更を行う必要がある +- 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある ``` c -__code putQueue3(struct Context* context, struct Queue* queue, struct Element* new_element) { +__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 meta(context, context->next); + goto exit(); } else { - goto meta(context, PutQueue3); + goto putQueue3(queue, new_element); } } @@ -283,62 +310,24 @@ ## Persistent Data Tree - Persistent Data Tree は Data Gear の管理を行う -- TaskQueue と同じですべての Context で共有される -- 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ -- Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う +- TaskQueue と同じですべての Thread で共有される +- Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ +- unix のファイルシステムに相当する的な ## Worker - Worker は TaskQueue から Task を取得して実行する - TaskQueue へのアクセスは Enqueue 操作と同じで CAS を用いる -- Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている +- Task には実行する Code Gear と実行に必要な Data Gear の ree の key が格納されている - Task が完了したら次の Task を取得する -``` c -// Task define -union Data { - // size: 8 byte - struct Task { - enum Code code; - int key; - } task; -} -``` - -``` c -__code getQueue(struct Context* context, struct Queue* queue, struct Node* node) { - if (queue->first == 0) - return; - - struct Element* first = queue->first; - if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) { - queue->count--; - - context->next = GetQueue; - - context->next = first->task->code; - node->key = first->task->key; - - struct Traverse *t = &context->data[Traverse]->traverse; - t->next = GetQueue; - goto meta(context, Get); - } else { - goto meta(context, GetQueue); - } -} - -``` - -## Worker -- Worker で実行される Code Gear は他の Code Gear と同様の記述である -- つまり依存関係のない Code Gear は並列で動作させることができる -- Gears OS 自体が Code Gear によって構成されるため、 Gears OS の実装自体が Gears でプログラミングを行う際の指針になる ## TaskManger - TaskManager は Task の依存関係の解決を行う -- Worker の作成と停止も行う +- Thread の作成と停止も行う +- このコードは Thread の生成を行い、 Thread 毎の context を設定している **Meta Code Gear** ``` c -// Code Gear +// Meta Code Gear __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) { int i = loopCounter->i; @@ -359,35 +348,35 @@ } ``` -## プロトタイプの評価 +## プロトタイプの実行 - 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った - これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった -- Gears OS の評価として依存関係のない例題を実装して評価を行う -## Twice -- 依存関係のない例題として Twice を実装した +## Gears で実行する Code Gear 例 +- プロトタイプのタスクの例題として Twice を実装した - Twice は与えられた整数配列を2倍にする例題である ``` c // Twice Code Gear -__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int alignment, int* array) { +__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 meta(context, Twice); + goto twice(loopCounter, index, alignment, array); } loopCounter->i = 0; - goto meta(context, context->next); + goto exit(); } ``` -## 実験環境 -- 測定環境 +## 並列処理の確認 +- Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った +- 環境 - Model : MacPro Mid 2010 - OS : Mac OS X 10.10.5 - Memory : 16GB @@ -396,7 +385,6 @@ - 分割数 : 640 タスク - 1 Task 当たりの処理量 : 2^11 * 100 elements -## 結果 @@ -426,29 +414,27 @@
    -
    - message -
    +- 1cpu と 12cpu では 11.8 倍の向上が見られた -- 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた -- 十分な台数効果が出てる事がわかる ## Cerium との比較 - Cerium は本研究室で開発していた並列プログラミングフレームワーク - Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする - - 本来 Task はデータに依存するもので Task 感の依存関係ではデータの依存関係を保証することが出来ない + - 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない - Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる -- また Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、型の検査を行うことが出来ない +- 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 のプロトタイプの設計、実装を行った - Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った -- 依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した +- 依存関係のない Twice を実装し、並列処理が行えることを確認した ## 今後の課題 - 一般的に並列処理には依存関係が存在する @@ -459,7 +445,7 @@ - 軽量継続はスタックを積まないため、スタックトレースが見えないためその対策 - 並列処理でのデバック手法も考案する必要がある - 型情報の検査 - - プログラムの正しさを保証するために Data Gear 野方情報を検査するシステムを Meta Computation として実装する + - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する - Contextの動的生成 - 今は静的に自分で生成している - CbC 用の Runtime をつくり、 Context を動的に生成