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 を動的に生成