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

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

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

## Code Gear、 Data Gear
- Gears OS は Code Gear、 Data 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>

## メタ計算
- メタ計算 は通常の計算を実行するための計算
- 信頼性の確保やメモリ管理、スレッド管理、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>

## 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 の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
    - このような環境を持たない継続を軽量継続と呼ぶ
- 下のコード例では Code Gear を2つ定義し、 cg0 から cg1 への継続を示している

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

}

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

## Context
- Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear
- 従来のOS のスレッドやプロセスに対応し、以下の要素を定義している
    - 独立したメモリ空間
    - Code Gear、 Data Gear へのポインタ
    - 並列実行用の Task 情報
    - Data Gear の型情報
- 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
// normal level Code Gear
__code cg0(struct Context* context, struct Integer integer, struct Queue queue) {
    ...
}

// meta level stub Code Gear
__code cg0_stub(struct Context* context) {
    // get data index number
    Integer integer = &context->data[context->dataNum]->Integer
    // get enum data
    Queue* queue = &context->data[Queue]->Queue;
    // continuation Code Gear
    goto cg0(context, integer, queue);
}
```

## Context での stub Code Gear の記述の問題点
- stub Code Gear は Context から Code Gear と Data Gear の組合せを展開して記述する必要がある
- しかし、 Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた
    - Context は全ての Code と Data の集合を表現しているため、全て組合せを展開する必要がある
    - 
- そのため 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 の定義には以下の内容を定義する
    - 引数のData Gear 群
    - 操作(API) 実行後に継続される Code Gear
    - 操作(API) である Code Gear と 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 の定義にあわせる
- 第1引数は 実装対象の Data Gear の型になる
- 第3引数の(...) は Output Data Gear を記述する
    -  ... は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput 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` で行われる
- ここでの **interface**  は Interfaceの型で包んだポインタ、 **method** は実装した Code Gear に対応
- この構文は実際にはスクリプトで変換される
    - 変換後はメタレベルのコードになる

```
__code code1() {
    Queue* queue = createSingleLinkedQueue(context);
    Node* node = new Node();
    node->color = Red;
    goto queue->put(node, queueTest2);
}
```

## Interface を利用した Code Gear の呼び出し(スクリプト変換後)
- Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す
- この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる
- 呼び出すCode Gear の引数情報に合わせて引数に格納

```
__code code1(struct Context *context) {
    Queue* queue = createSingleLinkedQueue(context);
    Node* node = &ALLOCATE(context, Node)->Node;
    node->color = Red;
    Gearef(context, Queue)->queue = (union Data*) queue;
    Gearef(context, Queue)->data = (union Data*) node;
    Gearef(context, Queue)->next = C_queueTest2;
    goto meta(context, queue->put);
}
```

## Interface での stub Code Gear
- メタ計算で格納された引数は、 stub Code Gear で Code Gear に渡される
- Interface を実装した Code Gear は stub Code Gear の自動生成が可能である

``` c
__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) {
    Element* element = &ALLOCATE(context, Element)->Element;
    element->data = data;
    element->next = NULL;
    queue->last->next  = element;
    queue->last = element;
    goto meta(context, next);
}

// generated by script
__code putSingleLinkedQueue_stub(struct Context* context) {
	SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue);
	Data* data = Gearef(context, Queue)->data;
	enum Code next = Gearef(context, Queue)->next;
	goto putSingleLinkedQueue(context, queue, data, next);
} 
```

## 並列処理の構成
- 今回は並列処理を行う機構の実装を行う
- 構成要素
    - Task(Context)
    - TaskManager
        - Worker の生成、依存関係を解決したTask を Worker に送信する
    - Worker
        - SynchronizedQueue から Task を取得し、実行する

## Task(Context)
- Gears OS では並列実行する Task を Context で表現する 
- Context Task用の情報として以下の情報をもっている
    - 実行する Code Gear
    - Input/Output Data Gear の格納場所
    - 待っている Input Data Gear の数
- 実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる
    - stub Code Gear は自動生成される

``` c
__code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) {
    output->value = input1->value + input2->value;
    goto next(output, ...);
}
```

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

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

## Worker
- 初期化の際にスレッドと Worker 用の Context を生成する 
- TaskManager から送信された Task を取得して実行する

<div>
    <div style="float: left;">
        <img src="./images/workerRun.svg" alt="message" width="600">
    </div>
    <div style="float: left; font-size=100%;">
        <ol>
            <li>Worker は Queue から Task を取得する</li>
            <li>Worker Context から Task へ入れ替える</li>
            <li>Task の Code Gear を実行</li>
            <li>Task の Output Data Gear の書き出し</li>
            <li>Task から WorkerContext へ入れ替える</li>
            <li>Worker は再び Queue から Task を取得する</li>
        </ol>
    </div>
</div>

## Synchronized Queue
- Worker で使用される Queue
- TaskManager を経由して Task を送信するスレッドと Task を取得するスレッドで操作される
- そのためマルチスレッドでのデータの一貫性を保証する必要がある
- Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する
- この Queue は Queue Interface を実装し、 List を利用した実装を行った

```
struct SynchronizedQueue {
    struct Element* top;
    struct Element* last;
    struct Atomic* atomic;
};
// Singly Linked List element
struct Element {
    union Data* top;
    struct Element* next;
};
```

## 依存関係の解決
- 依存関係の解決は Data Gear にメタレベルで依存関係解決用の Queueをもたせることで行う
- Code Gear を実行した後、 Output Data Gear を書き出す処理を行う
- 書き出し処理は Data Gear の Queue から依存関係にある Task を参照する
- Task には実行に必要な Input Data Gear のカウンタを持っているため、そのカウンタをデクリメントする
- カウンタが0になったら Input Data Gear が揃ったことになるため、TaskManager を経由して Worker に送信する

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

## 並列構文
- 並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する
- この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述は好ましくない
- Task の設定の記述は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である
- そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した
- par goto 構文には引数として Input/Output Data Gear等を渡す
    - スクリプトによって Code Gear の Input/Output の数を解析する

``` c
__code code1(Integer *integer1, Integer * integer2, Integer *output) {
    par goto add(integer1, integer2, output, __exit);
    goto code2();
}
```

## CUDA への対応
- Gears OS は GPU での実行もサポートする
- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる
- 今回は CUDA への実行のサポートをおこなった
- CUDA へ GPU を Device、 CPU を Host として定義する
- CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する
- 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた Code Gear を提供する

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

## CUDAExecutor
- CUDA Executor は Executor Interface を実装した以下の Code Gear を持つ
    - HostからDevice へのデータの送信(read)
    - kernel の実行(exec)
    - Device から Host へのデータの書き出し(write)

``` c
typedef struct Executor<Impl>{
    union Data* Executor;
    struct Context* task;
    __code next(...);
    // method
    __code read(Impl* executor, struct Context* task, __code next(...));
    __code exec(Impl* executor, struct Context* task, __code next(...));
    __code write(Impl* executor, struct Context* task, __code next(...));
}
```

## CUDABuffer
- Host、 Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある
    - Device にデータ領域を確保するにはサイズの指定が必要
    - Data Gear には Meta Data Gear でデータのサイズを持っている
    - だが、Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう
- CUDA Buffer ではそのマッピングを行う
    - このマッピングは Task の stub Code Gear で行われる

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

## CUDA での呼び出し
- Gears OS では stub Code Gear で CUDA による実行を切り替える
- stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う
- stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する

## Gears OS の評価
- 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った
- CPU 環境
    - Model : Dell PowerEdgeR630
    - Memory : 768GB
    - CPU : 2 x 18-Core Intel Xeon 2.30GHz
- GPU 環境
    - GPU : GeForce GTX 1070
    - Cores : 1920
    - ClockSpeed : 1683MHz
    - Memory Size : 8GB GDDR5
    - Memory Bandwidth :  256GB/s

## Twice
- Twice は与えられた整数配列を2倍にする例題である
- 並列実行の依存関係がなく、並列度が高い課題である
- 要素数 2^27
- CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する
- GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開

## Twice の結果
<table  border="1" align='center' width='50%'>
  <tbody>
    <tr>
      <td style="text-align: center;">Processor</td>
      <td style="text-align: center;">Time(ms)</td>
    </tr>
    <tr>
      <td style="text-align: center;">1 CPU</td>
      <td style="text-align: right;">1181.215</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">627.914</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">324.059</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">159.932</td>
    </tr>
    <tr>
      <td style="text-align: center;">16 CPUs</td>
      <td style="text-align: right;">85.518</td>
    </tr>
    <tr>
      <td style="text-align: center;">32 CPUs</td>
      <td style="text-align: right;">43.496</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU</td>
      <td style="text-align: right;">127.018</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU(kernel only)</td>
      <td style="text-align: right;">6.018</td>
    </tr>
  </tbody>
</table>

- 1 CPU と 32 CPU では 約27.1倍の速度向上が見られた
- GPU 実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上、通信時間を含めると 16 CPU より遅い
- 通信時間がオーバーヘッドになっている

## BitonicSort
- 並列処理向けのソートアルゴリズム
- 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする
- 要素数 2^24
- CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する
- GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開

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

## BitonicSort の結果

<table  border="1" align='center' width='50%'>
  <tbody>
    <tr>
      <td style="text-align: center;">Processor</td>
      <td style="text-align: center;">Time(s)</td>
    </tr>
    <tr>
      <td style="text-align: center;">1 CPU</td>
      <td style="text-align: right;">41.416</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">23.340</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">11.952</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">6.320</td>
    </tr>
    <tr>
      <td style="text-align: center;">16 CPUs</td>
      <td style="text-align: right;">3.336</td>
    </tr>
    <tr>
      <td style="text-align: center;">32 CPUs</td>
      <td style="text-align: right;">1.872</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU</td>
      <td style="text-align: right;">5.420</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU(kernel only)</td>
      <td style="text-align: right;">0.163</td>
    </tr>
  </tbody>
</table>

- 1 CPU と 32 CPU で約22.12倍の速度向上
- GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった
- 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった

## OpenMP との比較
## Go との比較

## まとめ
- Gears OS の並列処理機構の実装を行った
- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった
- par goto  構文を導入することで、ノーマルレベルで並列処理の記述が可能になった
- 2つの例題である程度の台数効果が出ることを確認した

## 今後の課題
- Gears OS の並列処理の信頼性の保証、チューニングを行う
- Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する
    - 証明はCbC のプログラムヲ証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある
    - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う
- OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。 
    - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう
    - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成セずに関数呼出しを行う等の最適化が必要
- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった
    - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持サれているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデーの通信を行う