title: Code Gear、 Data Gear に基づく OS のプロトタイプ
author: 伊波 立樹
profile: 琉球大学理工学研究科情報工学専攻
lang: Japanese
code-engine: coderay

## Gears OS
- CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている
- そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある
- マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない
- また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している
- 並列処理をする上でこれらのリソースを無視することができない
- しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる
- 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる
- 本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS のプロトタイプ設計・実装を行い、簡単な例題を用いて評価を行う

## Cerium
- Cerium は本研究室で開発していた並列プログラミングフレームワークである
- Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする
- 依存関係を Task 間で設定する
- しかし、本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない
- また、Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、 汎用ポインタをキャストして利用している

## 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 での Gear
- Gears OS はプログラムの単位として Gear を用いる
- Gear は並列実行の単位、データの分割、 Gear 間の接続等になる
- Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある

## Code Gear
- Code Gear はプログラムの処理そのものを表す
- 任意の数の Input Data Gear を参照し、 Code Gear の処理が完了すると任意の数の Output Data Gear を生成する
- Code Gear は接続された Input Data Gear 以外の Data にはアクセスしない

## Data Gear
- Data Gear は Data そのものを表す
- int や 文字列などの Primitive Data Type が入っている
- Code Gear から参照される Data Gear を Input Data Gear、 Code Gear の処理で生成される結果を Output Data Gear を呼ぶ

## Code Gear、 Data Gear での並列実行
- Gears OS では Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う

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

## Meta Computation
- Gears OS では通常の Computation のために実行する Computation を Meta Computation として扱う
- Meta Computation の例として並列処理の依存関係の解決、 OSが行うネットワーク管理、メモリ管理等がある
- 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 へ接続する

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

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

## Gears OS の構成
- Context
    - 接続可能な Code/Data Gear のリスト、 TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、独立したメモリ空間を持っている
    - Worker 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される
- TaskQueue
    - CAS を利用したスレッドセーフなQueue
    - ActiveTaskQueue と WaitTaskQueue の 2種類
    - ActiveTaskQueue は実行可能なTaskが挿入され, WaitTaskQueue には依存関係が解決されていないTaskが挿入される

## Gears OS の構成
- Persistent Data Tree
    - Code Gear によって参照される Data Gear の管理を行う
    - Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う
- TaskManager
    - Task の依存関係の解決を行う
    - Persistent Data Tree を監視し、 Task の依存関係を解決する

## Gears OS の構成
- Worker
    - Worker は ActiveTaskQueue から Task を取得する
    - 取得した Task から必要な Data Gear を Tree から取得し、 Code Gear を実行
    - 実行後必要なデータを Persistent Data Tree 書き出す

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

## Context

## Allocator

## TaskQueue
- Task Queue は Task の管理を行う
- すべての Worker の Context で共有される
- TaskQueue は 2つで Data Gear で表現される
    - 先頭と末尾の要素を持った Queue 表す Data Gear
    - Task と次の要素へのポインタを持った、List を表現する Element という Data Gear

``` c
// Code Gear Name
enum Code {
    PutQueue,
    GetQueue
};

// Unique Data Gear
enum UniqueData {
    Queue,
    Element
};

// Data Gear definication
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 から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
- Queue の last を追加する要素に設定
- 正しく最後の要素が変更できたことをCAS で 保証し、末尾の変更を行う必要がある

``` c
__code putQueue3(struct Context* context, 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);
    } else {
        goto meta(context, PutQueue3);
    }
}

```

## Persistent Data Tree
- Persistent Data Tree は Data Gear の管理を行う
- TaskQueue と同じですべての Context で共有される
- 一度破壊した木構造を破壊すること無く新しい木構造を構築するため、変更して読み書き可能
- 非破壊木構造はルートから変更したいノードへのパスすべてをコピーし、パズ上に存在しないノードはコピー元の木構造と共有する

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

## Persistent Data Tree
- 木構造を構築するとき最悪なケースでは事実上の線形リストになる
- そのため、挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ

## Worker
- Worker は TaskQueue から Task を取得して実行する
- TaskQueue へのアクセスは Enqueue 操作と同じで CAS を用いる
- Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている
- Task が完了したら次の Task を取得する

``` c
// Task definication
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;
        stack_push(context->code_stack, &context->next);

        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 の作成と停止も行う

``` c
// 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 OS の評価として依存関係のない例題を実装して評価を行う

## Twice
- 依存関係のない例題として Twice を実装した
- Twice は与えられた整数配列を2倍にする例題である

``` c
// Twice Code Gear
__code twice(struct Context* context, 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);
    }

    loopCounter->i = 0;

    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}
```

## 実験環境
- 測定環境
    - Model : MacPro Mid 2010
    - OS : Mac OS X 10.10.5
    - Memory : 16GB
    - CPU : 6-core Intel Xeon 2.66GHZ x 2
- 要素数 : 2^17
- 分割数 : 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>

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

- 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた

## 比較

## まとめ