title: Code Gear、 Data Gear に基づく OS のプロトタイプ
author: 伊波 立樹
profile: 琉球大学理工学研究科
lang: Japanese
code-engine: coderay
## Gears OS
- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて
    - 並列性
    - 柔軟性
    - 信頼性

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

- 本研究では Gears OS のプロトタイプとして並列処理機構をCbC(Continuation based C) で実装を行う

## 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 は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う

<div style="text-align: center;">
    <img src="./images/meta_cg_dg.svg" alt="message" width="450">
</div>


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

## Continuation based C
- Code Segment の定義は ``__code CS名`` で行う
- 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) {
    ....
    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);
}
```

## Gears OS 構成
- Context
    - Thread 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される
- TaskQueue
    - 実行される Task のリストを扱う

<div style="text-align: center;">
    <img src="./images/gearsos.svg" alt="message" width="750">
</div>

## Gears OS の構成
- Persistent Data Tree
    - Code Gear によって参照される Data Gear の管理を行う
- TaskManager
    - Persistent Data Tree を監視し、 Task の依存関係を解決する

<div style="text-align: center;">
    <img src="./images/gearsos.svg" alt="message" width="750">
</div>

## Gears OS の構成
- Worker
    -  TaskQueue から Task を取得し、実行する

<div style="text-align: center;">
    <img src="./images/gearsos.svg" alt="message" width="750">
</div>

## TaskQueue
- Task Queue は Task の管理を行う
- すべての Worker の Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
- TaskQueue は 2つで Data Gear で表現される
    - 先頭と末尾の要素を持った Queue 表す Data Gear
    - Task と次の要素へのポインタを持った、List を表現する 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="700">
</div>

## Persistent Data Tree
- Persistent Data Tree は
    - Tree 自体を示す Data Gear
    - Node を示す Data Gear

を用いて木構造を表現する

``` c
union Data {
    struct Tree {
        struct Node* root;
    } tree;
    struct Node {
        // need to tree
        enum Code next;
        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>
        <ul>
            <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>
        </ul>
     </td>
    </tr>
  </tbody>
</table>

- Task が完了したら次の Task を取得する

## TaskManger
- TaskManager は Task の依存関係の解決を行う
- Thread の作成と停止も行う
- このコードは Thread の生成を行い、 Thread 毎の context を設定している **Meta Code Gear** である

``` c
// Meta Code Gear
__code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
    int i = loopCounter->i;

    if (i < worker->num) {
        struct Context* worker_context = &worker->contexts[i];
        worker_context->next = GetQueue;
        worker_context->data[Tree] = context->data[Tree];
        worker_context->data[ActiveQueue] = context->data[ActiveQueue];
        pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context);
        worker_context->thread_num = i;
        loopCounter->i++;

        goto meta(context, CreateWorker);
    }

    loopCounter->i = 0;
    goto meta(context, TaskManager);
}
```

## プロトタイプの実行
- 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
- これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった

## Gears で実行する 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 のプロトタイプの設計、実装を行った
- Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
- 依存関係のない Twice を実装し、並列処理が行えることを確認した

## 今後の課題
- 一般的に並列処理には依存関係が存在する
    - 複雑な並列処理を実行できるようにするために依存関係のある並列処理の例題を作成し、評価する
- GPUなどの他のプロセッサ演算に利用することが出来ない
    - Data Gear などのデータをGPUにマッピングするための機構が必要
- Gears OS でのデバック手法
    - 軽量継続はスタックを積まないため、スタックトレースが見えないためその対策
    - 並列処理でのデバック手法も考案する必要がある
- 型情報の検査
    - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する
- Contextの動的生成
    - 今は静的に自分で生成している
    - CbC 用の Runtime をつくり、 Context を動的に生成