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 の問題点
* 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