title: Gears OS の並列処理
author: 伊波 立樹
profile: 琉球大学理工学研究科 河野研
lang: Japanese
code-engine: coderay

## メタ計算を用いた並列処理
- 並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている
- しかし、並列処理のチューニングや信頼性を保証するのは難しい
    - スレッド間の共通資源の競合などの非決定的な実行
    - 従来のテストやデバッグではテストしきれない部分が残ってしまう
    - GPU などのアーキテクチャに合わせた並列プログラミングの記述

## Gears OS
- 本研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される
    - Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う
- Gears OS では計算をノーマルレベルとメタレベルに階層化
- 信頼性と拡張性をメタレベルで保証する
    - 並列処理の信頼性を通常の計算(ノーマルレベル) に保証
    - CPU、GPU などの実行環境の切り替え、データ拡張等のを提供
    
## Gears OS
- 本研究ではGears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う
- また、並列処理を行う例題を用いて評価、 Open MP、 Go 言語との比較を行う

## Code Gear、 Data Gear
- Gears OS は Code Gear、 Data Gear という Gear で構成される
- Code Gear はプログラムの処理そのものを表す
- Data Gear はデータそのものを表す
- Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する
- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う

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

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

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

## Continuation based C
- このコードは cg0、cg1 の2つの Code Gear を定義している
- cg0 内の ``goto cg1`` でgj1 への継続を行っている
    - ここで(a+b) が cg1 への入力になる

``` c
__code cg0(int a, int b) {
    goto cg1(a+b);

}

__code cg1(int c) {
    goto cg2(c);
}
```

## メタ計算
- メタ計算 は通常の計算を実行するための計算
- 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等
- Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる
- メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる

## Meta Gear
- メタ計算 は Code Gearの接続の間に行われる
- メタ計算 の処理も Code/Data Gear で実現する
- この Gear を Meta Code/Data Gearと呼ぶ
    - Meta Code Gear は メタ計算 のプログラム部分
    - 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>

## Context
- Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear
- 従来のOS のスレッドやプロセスに対応
    - 独立したメモリ空間を持つ
    - Code Gear、 Data Gear へのポインタ
    - 並列実行用の Task 情報
- を持つ
- Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする

## Data Gear の表現
- Data Gear は構造体を用いて定義する
- メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される
- Data Gear のメモリに確保する際のサイズ情報はこの型から決定する

``` c
/* data Gear define */
union Data {
    struct Timer {
        union Data* timer;
        enum Code start;
        enum Code end;
        enum Code next;
    } Timer;
    struct TimerImpl {
        double time;
    } TimerImpl;
    ....
};
```

## Code Gear の stub Code Gear
- Data Gear にアクセスするにはContext を経由する
- だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub Code Gear を用意する

``` c
```

## Context での stub Code Gear の記述の問題点
- Context プログラム全体で使用する Code Gear と Data Gear の集合
- 全ての Code と Data の組合せをContext から 全て展開し、その組合せを stub Code Gear に書く必要がある
- Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた
- そのため Gears OS のモジュール化する仕組みとして **Interface** を導入した

## Interface
- Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear
- stub Code Gear は実装した Code Gear で決まった形になるため、自動生成が可能である
- Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る
- Interface は Java のインターフェース、 Haskell の型クラスに対応する

## Interface の定義
- Interface の定義には以下の内容を定義する
    - 操作(API) である Code Gear と Code Gear に渡す引数情報
    - 引数のData Gear 群
    - 操作(API) 実行後に継続される Code Gear

``` c
typedef struct Queue<Impl>{
        // Data Gear parameter
        union Data* queue;
        union Data* data;
        __code next(...);
        __code whenEmpty(...);

        // Code Gear
        __code clear(Impl* queue, __code next(...));
        __code put(Impl* queue, union Data* data, __code next(...));
        __code take(Impl* queue, __code next(union Data*, ...));
        __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...));
} Queue;
```

## Interface の実装
- Interface には複数の実装を行うことが出来る
- 実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う
- 代入する Code Gear を入れ替えることで別の実装を表現する
- 実装した Data Gear の生成は関数呼び出しで行われ、 外から見るとInterface の型で扱われる

```
Queue* createSingleLinkedQueue(struct Context* context) {
    struct Queue* queue = new Queue(); // Allocate Queue interface
    struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement
    queue->queue = (union Data*)singleLinkedQueue;
    singleLinkedQueue->top  = new Element();
    singleLinkedQueue->last = singleLinkedQueue->top;
    queue->clear = C_clearSingleLinkedQueue;
    queue->put  = C_putSingleLinkedQueue;
    queue->take  = C_takeSingleLinkedQueue;
    queue->isEmpty = C_isEmptySingleLinkedQueue;
    return queue;
}
```

## Interface の実装例
- SingleLinkedQueue の put 実装
- 引数は Queue Interface の定義にあわせる
- 第一引数は 実装対象の Data Gear の型になる

``` c
__code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) {
    Element* element = new Element();
    element->data = data;
    element->next = NULL;
    queue->last->next  = element;
    queue->last = element;
    goto next(...);
}
```

## Interface を利用した Code Gear の呼び出し
- Interface を利用した Code Gear への継続として `goto interface->method` を提供している
## 並列処理の構成
- 今回は並列処理を行う機構の実装を行う
- 構成要素
    - Task(Context)
    - Worker
        -  Queue から Task を取得し、実行する
    - TaskManager
        - Persistent Data Tree を監視し、 Task の依存関係を解決する

※ TaskManager は今回未実装

## Task(Context)

## TaskManger
- 初期化時に決まった数の Worker を作成
- 依存関係を解決した Task を各 Worker の Queue に送信する

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

## 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 を取得する

## Synchronized Queue
- Task Queue は Task のリストを扱う
- Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
- TaskQueue は 2つで Data Gear で表現される
    - 先頭と末尾の要素を持った Queue 表す Data Gear
    - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear

## 依存関係の解決

## データ並列

## CUDA への対応
## CUDA Worker
## CUDA Executor

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

## 実験環境
- CPU 環境
    - Memory : 16GB
    - CPU : 6-core Intel Xeon 2.66GHZ x 2
- GPU 環境

## Twice
- タスクの例題として Twice と BitonicSort を実装した
- 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 の結果

## BitonicSort

## BitonicSort の結果

<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 倍の向上が見られた

## OpenMP との比較

## Go との比較

## まとめ
- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
- 依存関係のない Twice を実装し、並列処理が行えることを確認した

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