title: Code Segment と Data Segment を持つ Gears OS の設計
author: Shohei KOKUBO
profile: 琉球大学大学院修士2年

# 並列環境下におけるプログラミング
マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。
これはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。
つまり、プログラムを並列処理に適した形で記述するためのフレームワークが必要になる。

マルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。
並列処理をする上でこれらのリソースを無視することはできない。
しかし、これらのプロセッサで性能を引き出すためにはそれぞれのアーキテクチャに合わせた並列プログラミングが必要になる。
並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。

# Cerium
Cerium は本研究室で開発している並列プログラミングフレームワークである。

Cerium では関数またはサブルーチンを Task として定義する。
Task 間で依存関係を設定することができ、TaskManager が依存関係を解決することで実行可能な状態となる。
実行可能な状態となると Task に設定された実行デバイスの Scheduler に転送され実行される。

![Cerium の構成](./pictures/createTask.svg)

# Cerium における GPGPU への対応
* OpenCL, CUDA を用いて GPGPU に対応している
* GPGPU ではメモリ空間が異なるためデータ転送が大きなオーバーヘッドになる
* 処理速度を上げるにはデータ転送をオーバーラップする必要がある

![GPU](./pictures/gpu.svg)

# Cerium における GPGPU への対応
* Stream に命令を発行することで GPU を制御する
* Stream は命令が発行された順番通りに実行されることを保証する
* 複数の Stream を用意し、各 Stream に命令を発行することでデータ転送をオーバーラップすることができる

![stream](./pictures/stream.svg)

# Bitonic Sort を用いた Cerium の評価
* Bitonic Sort は並列処理に向いたソートアルゴリズムである
* 最初から最後まで並列度が変わらず、台数による効果が出やすい

![bitonic](./pictures/bitonic.svg)

# Bitonic Sort を用いた Cerium の評価
* 測定環境
  * Model : MacPro Mid 2010
  * OS : Mac OS X 10.10.5
  * Memory : 16GB
  * CPU : 2 x 6-Core Intel Xeon 2.66GHz
  * GPU : NVIDIA Quadro K5000
    * Cores : 1536
    * Clock Speed : 706MHz
    * Memory : 4GB GDDR5
    * Memory Bandwidth : 173 GB/s
* 要素数：2<sup>20</sup>

<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;">6143</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">4633</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">2577</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">1630</td>
    </tr>
    <tr>
      <td style="text-align: center;">12 CPUs</td>
      <td style="text-align: right;">1318</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU</td>
      <td style="text-align: right;">155</td>
    </tr>
  </tbody>
</table>

<table width="70%" align="center">
  <tr>
    <td><div align="center"><img src="pictures/bitonic_box.svg" width="1024"></div></td>
  </tr>
</table>

# Bitonic Sort を用いた Cerium の評価
次に要素数を変更して測定を行った。

<table width="70%" align="center">
  <tr>
    <td><div align="center"><img src="pictures/bitonic_all.svg" width="1024"></div></td>
  </tr>
  <tr>
    <td><div align="center"><img src="pictures/bitonic_part.svg" width="1024"></div></td>
  </tr>
</table>

GPU による実行ではデータ転送の時間を考慮する必要がある。

GPGPU は大きなデータに対して有効であることがわかる。

# Cerium の問題点
* Task 間の依存関係

Cerium では Task 間の依存関係を設定することで並列処理を実現する。
しかし、本来 Task は必要なデータが揃うことで実行可能になるものである。
Task 同士の依存関係だけでは前の Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。
データがどこでおかしくなったのか特定するのは難しく、デバックに時間が取られる。

* データの型情報

Task は汎用ポインタでデータの受け渡しを行うのでそこで型情報が落ちる。
Task 側で正しく型変換を行うことで正しい処理を行うことができるが、誤った型変換を行うと未定義な動作となりデータ構造を破壊する可能性がある。
型システムによるプログラムの正しさを保証することもできず、型に基づく一連の不具合が起こる危険性がつきまとう。

# Cerium の問題点
* メモリ確保

Cerium の Allocator は Thread 間で共有されている。
ある Thread がメモリを確保しようとすると他の Thread はその間メモリを確保することができない。
これが並列度の低下に繋がり、処理速度が落ちる原因になる。

* オブジェクト指向と並列処理

同じ入力に対し、同じ入力を返すことが保証される参照透過な処理は並列化を行いやすい。
一方、オブジェクト指向は保守性と再利用性を高めるためにカプセル化やポリモフィズムを重視する。
オブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪い。

# Gears OS
本研究では Code Segment と Data Segment によって構成される Gears OS の設計・実装を行った。

Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。

Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C) を用いた。

# Code/Data Gear
Gears OS ではプログラムの単位として Gear を用いる。
Gear は並列実行の単位、データ分割、Gear 間の接続などになる。

Code Gear は Code Segment と同等のものである。
Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。
接続された Data Gear 以外にアクセスすることはできない。

Data Gear はデータそのものを表す。
int や文字列などの Primitive Data Type を複数持つ構造体として定義する。

Gear 特徴として処理やデータの構造が Code/Data Gear に閉じていることにある。
これにより実行時間、メモリ使用量などを予測可能なものにする。

# Gears OS の構成
* Context

接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、独立したメモリ空間を持っている。
複数の Context で TaskQueue と Persistent Data Tree は共有される。

* TaskQueue

ActiveTaskQueue と WaitTaskQueue の2種類の TaskQueue がある。
ActiveTaskQueue には実行可能な Task が挿入され、WaitTaskQueue には依存関係が解決されていない Task が挿入される。
先頭と末尾の Element へのポインタを持つ Data Gear と Task へのポインタと次の Element へのポインタを持つ Data Gear で構成される。
Compare and Swap(CAS) を利用することでスレッドセーフに Queue を操作することができる。

# Gears OS の構成
* Persistent Data Tree

Data Gear の管理を行う。
非破壊木構造で構成されるため読み書きを平行して行うことができる。
Red-Black Tree アルゴリズムを用いて平衡性を保ち、挿入・削除・検索における計算量を保証する。
Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。

* TaskManager

Gears OS における Task は実行する Code Gear と Input/Output Data Gear の組で表現される。
Input/Output Data Gear から依存関係を決定する。
TaskManager は Persistent Data Tree を監視し、Task の依存関係を解決する。

# Gears OS の構成
* Worker

Worker は ActiveTaskQueue から Task を取得する。
取得した Task の情報を元に必要な Data Gear を Persistent Data Tree から取得し、Code Gear を実行する。
実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。

![Gears OS の構成](./pictures/gearsos.svg)

# Allocator
* Context の生成時にある程度の大きさのメモリ領域を確保
* Context には確保したメモリ領域を指す情報(heapStart, heap, heapLimit)を格納

``` C
/* Context definition example */
#define ALLOCATE_SIZE 1000

// Code Gear Name
enum Code {
    Code1,
    Code2,
    Allocator,
    Exit,
};

// Unique Data Gear
enum UniqueData {
    Allocate,
};

struct Context {
    enum Code next;
    int codeNum;
    __code (**code) (struct Context*);
    void* heapStart;
    void* heap;
    long heapLimit;
    int dataNum;
    union Data **data;
};

// Data Gear definition
union Data {
    // size: 4 byte
    struct Data1 {
        int i;
    } data1;
    // size: 5 byte
    struct Data2 {
        int i;
        char c;
    } data2;
    // size: 8 byte
    struct Allocate {
        long size;
    } allocate;
};
```

# Allocator
* Allocation を行うための情報を書き込む Data Gear が必要
  * Context と同時に生成
``` C
__code initContext(struct Context* context, int num) {
    context->heapLimit        = sizeof(union Data)*ALLOCATE_SIZE;
    context->heapStart        = malloc(context->heapLimit);
    context->heap             = context->heapStart;
    context->codeNum          = Exit;
    
    context->code             = malloc(sizeof(__code*)*ALLOCATE_SIZE);
    context->data             = malloc(sizeof(union Data*)*ALLOCATE_SIZE);

    context->code[Code1]      = code1_stub;
    context->code[Code2]      = code2_stub;
    context->code[Allocator]  = allocator_stub;
    context->code[Exit]       = exit_code;
    
    context->data[Allocate]   = context->heap;
    context->heap            += sizeof(struct Allocate);
    
    context->dataNum          = Allocate;
}
```

# Allocator
* メモリ領域を指すポインタを動かすことで Data Gear のメモリを確保
* 確保した Data Gear は基本的に破棄可能なものである
* リニアにメモリを確保し、サイズを超えたら先頭に戻って再利用

![Allocator](./pictures/allocation.svg)

# Allocator
* Allocation に必要な情報を Data Gear に書き込み、Allocator に接続する
* 生成した Data Gear には Context を介してアクセスすることができるが、Context を直接扱うのは好ましくない
* Context から値を取り出すだけのメタレベルの Code Gear を用意

``` C
// Meta Code Gear
__code meta(struct Context* context, enum Code next) {
    // meta computation
    goto (context->code[next])(context);
}

// Code Gear
__code code1(struct Context* context, struct Allocate* allocate) {
    allocate->size = sizeof(struct Data1);
    context->next  = Code2;
    
    goto meta(context, Allocator);
}

// Meta Code Gear(stub)
__code code1_stub(struct Context* context) {
    goto code1(context, &context->data[Allocate]->allocate);
}

// Meta Code Gear
__code allocator(struct Context* context, struct Allocate* allocate) {
    context->data[++context->dataNum] = context->heap;
    context->heap                    += allocate->size;

    goto meta(context, context->next);
}

// Meta Code Gear(stub)
__code allocator_stub(struct Context* context) {
    goto allocator(context, &context->data[Allocate]->allcate);
}

// Code Gear
__code code2(struct Context* context, struct Data1* data1) {
    // processing
}

// Meta Code Gear(stub)
__code code2_stub(struct Context* context) {
    goto code2(context, &context->data[context->dataNum]->data1);
}
```

# TaskQueue
TaskQueue は Task を管理する。

すべての Context で共有され、CAS 命令を利用して変更することで平行にアクセスされてもデータの一貫性を保証する。

* 先頭と末尾の要素へのポインタを持った Queue を表す Data Gear
* Task と次の要素へのポインタを持った Element を表す Data Gear
``` C
// Code Gear Name
enum Code {
    PutQueue,
    GetQueue,
};

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

// Queue definication
union Data {
    // size: 20 byte
    struct Queue {
        struct Element* first;
        struct Element* last;
        int count;
    } queue;
    // size: 16 byte
    struct Element {
        struct Task* task;
        struct Element* next;
    } element;
}
```

# TaskQueue の操作(Enqueue)
* Enqueue は Queue の最後の要素を取り出し、次の要素に追加する要素を設定
* Queue を表す Data Gear が指す末尾を追加する要素に設定
* 正しく最後の要素が取り出せたことを保証して末尾の変更を行う必要がある

``` C
// Enqueue
__code putQueue(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;
        queue->count++;
        
        goto meta(context, context->next);
    } else {
        goto meta(context, PutQueue);
    }
}
```

# Persistent Data Tree
* Data Gear の管理を行う
* 複数の Context で共有
* 一度構築した木構造を破壊することなく新しい木構造を構築するので平行して読み書き可能
* 非破壊木構造の基本的な戦略はルートから変更したいノードへのパスをすべてコピーし、パス上に存在しないノードはコピー元の木構造と共有する

![非破壊木構造](./pictures/tree.svg)

# Persistent Data Tree
* 木構造を構築するとき最悪なケースでは事実上の線形リストになり、計算量が O(n) となる
* 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
* Red-Black Tree では変更したノードからルートに上りながら条件を満たすように色の変更や木の回転を行う
* Code Gear の継続では呼び出し元に戻ることが出来ないので Context に辿ったパスを記憶するためのスタックを準備する。

```C
// Unique Data Gear
enum UniqueData {
    Tree,
    Traverse,
    Node,
};

// Context definication
struct Context {
    stack_ptr node_stack;
};

// Red-Black Tree definication
union Data {
    // size: 8 byte
    struct Tree {
        struct Node* root;
    } tree;
    // size: 12 byte
    struct Traverse {
        struct Node* current;
        int result;
    } traverse;
    // size: 32 byte
    struct Node {
        int key;
        union Data* value;
        struct Node* left;
        struct Node* right;
        enum Color {
            Red,
            Black,
        } color;
    } node;
};
```

# Persistent Data Tree
* 親を取得し、親からの参照を変更して親をスタックに積み直す
* 自分と左右の3点のノードで回転を行うことで平衡にする
* 回転後も条件を満たしているか確認する必要がある

```C
// Code Gear
__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
    struct Node* tmp = node->right;
    struct Node* parent = 0;
    
    stack_pop(context->node_stack, &parent);

    if (parent) {
        if (node == parent->left)
            parent->left = tmp;
        else
            parent->right = tmp;
    } else {
        tree->root = tmp;
    }

    stack_push(context->node_stack, &parent);
    
    node->right = tmp->left;
    tmp->left = node;
    traverse->current = tmp;
    
    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}
    
// Meta Code Gear(stub)
__code rotateLeft_stub(struct Context* context) {
    goto rotateLeft(context,
                    context->data[Traverse]->traverse.current,
                    &context->data[Tree]->tree,
                    &context->data[Traverse]->traverse);
}
```

# Worker
* TaskQueue から Task を取得して実行
* TaskQueue へのアクセスには CAS 命令を用いる
* Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている
* Task が完了したら次の Task を取得するために GetQueue に戻ってくる必要がある
* CAS に失敗したら CAS をやり直すために自分自身に継続する

```C
// Task definication
union Data {
    // size: 8 byte
    struct Task {
        enum Code code;
        int key;
    } task;
}
```

```C
// Dequeue
__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;

        goto meta(context, GetTree);
    } else {
        goto meta(context, GetQueue);
    }
}
```

# Worker
* Worker で実行される Code Gear は特別なものではなく、他の Code Gear と同じ記述である
  * 依存関係のない Code Gear はすべて並列に動作させることができることを意味する
  * Gears OS 自体が Code Gear によって構成され、Gears OS の実装自体が Gears Programming の指針となる

```C
// 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);
}

// Meta Code Gear(stub)
__code twice_stub(struct Context* context) {
    goto twice(context,
               &context->data[LoopCounter]->loopCounter,
               context->data[Node]->node.value->array.index,
               context->data[Node]->node.value->array.alignment,
               context->data[Node]->node.value->array.array);
}
```

# TaskManager
* 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);
}
    
// Meta Code Gear
__code createWorker_stub(struct Context* context) {
    goto createWorker(context,
                      &context->data[LoopCounter]->loopCounter,
                      &context->data[Worker]->worker);
}
```

# Gears OS の評価
* Red-Black Tree アルゴリズムに基づいて非破壊木構造で構築される Persistent Data Tree
* CAS 命令を用いてアクセスすることで並列に動作させてもデータの一貫性を保証する TaskQueue
* TaskQueue から Task を取得し実行する Worker

Gears OS を用いて依存関係のない並列処理を実行可能な状態となった

簡単な並列処理の例題を実装し、評価を行う

# Twice
依存関係のない簡単な例題として Twice を実装した

Twice は与えられた整数配列を2倍にする例題である

* 配列のサイズを元に処理範囲と処理量を決める index, alignment, 配列へのポインタを持つ Data Gear に分割
* Data Gear を Persistent Data Tree に挿入
* 実行する Code Gear(Twice) と実行に必要な Data Gear の key を持つ Task を生成
* 生成した Task を TaskQueue に挿入
* Worker の起動
* Worker が TaskQueue から Task を取得
* 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得
* Code Gear(Twice) を実行

# Result
* 要素数：2<sup>17</sup> * 1000 elements
* 分割数：640 tasks
* 1 Task 当たりの処理量：2<sup>11</sup> * 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>

<table width="70%" align="center">
  <tr>
    <td><div align="center"><img src="pictures/twice.svg" width="1024"></div></td>
  </tr>
</table>

1 CPU と 12 CPU で約11.8倍の速度向上を確認した

十分な台数効果が出ていることがわかる

# まとめ
* Cerium を開発して得られた知見から Code/Data Segment を持つ Gears OS を設計した
* 基本的な機能として Allocator, TaskQueue, Persistent Data Tree, Worker を実装した
* 実装した基本的な機能を組み合わせ Gears OS のプロトタイプを作成し、依存関係のない簡単な並列処理の例題を実装した
* Gears OS がオーバーヘッドにならず、十分な台数効果が出ることを確認した
* Gears OS の実装自体が Gears OS を用いて並列処理を記述する際の指針となるように実装した

# 今後の課題
* 一般的に並列処理には依存関係が存在する。
複雑な並列処理を実行できるようにするために依存関係を解決する TaskManager を実装する必要がある
* GPU など他のプロセッサを演算に利用することができない。
Code/Data Segment を用いて各プロセッサにのアーキテクチャにマッピングした実行機構を実装する必要がある
* Data Segment 専用の構文を用意するべきである。
いまの実装では必要ない Data Segment を持つ場合がある。
実行可能な Code Segment のリストから推論し必要な Data Segment のみを持つようにする必要がある
* Data Segment の型情報を検査する機能がない。
型シグネチャを導入し、プログラムの正しさを保証する型システムを Gears OS 上に実装する必要がある