title: Gears OS における並列処理
author: 東恩納 琢偉
profile:琉球大学工学部
lang: Japanese
code-engine: coderay

# 研究目的
- 当研究室では  処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
- Gears OS では Task を Code Gear が実行するときに必要な Input Data Gear と出力の Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う.
- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は、通常の計算とは別の階層のメタ計算として記述する。
- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。
- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の実行の検証をメタ計算として記述することで、 並列処理の精度を保証する。

# メタ計算を使った並列処理

- 並列処理のプログラミングはチューニングや信頼性の確保が困難である。
- これらのチューニングや信頼性の確保を、アルゴリズムから分離しメタ計算で行う
- 当研究室ではメタ計算をサポートする言語として Continuation based C (CbC) を開発している
- CbC は Code Gear と Data Gear という処理とデータの単位を持っており、メタ計算を行うための Meta Code Gear、Meta Data Gear がある。
- Gears OS は CbC を用いて記述されている。

# Code Gear と Data Gear

- Code Gear、Data Gear とはプログラムを分解し、処理の部分を Code Gear、int や文字列などの部分を Data Gear という単位で分割したものである。
- Code Gear の処理はその処理に必要な Data Gear が揃ってから行われる。
- Code Gear の処理の移行は goto を使って行い、この移行の仕方を継続という。
- goto による移行は戻り値を持たないためスタックを積む必要がない、スタックに積まない継続を軽量継続と呼ぶ。

# Code Gear と Data Gear を用いた計算

- Code Gear の処理の実行は、接続された Data Gear が揃ってから実行される。
- Data Gear には Output Data Gear と Input Data Gear があり、Code Gear は接続された Data Gear 以外を変更することはない。
- そのため通常の計算ではポインタを気にすることはなく、ポインタ演算はメタ計算部分で行われる。
- Code Gear の処理は tail call のみで遷移を行う関数型プログラミングである。
- agda に変換することができ、プログラムの正しさを証明できる。

# Code Gear の例
- 下記のコードは Code Gear で記述された stack のコードの一部である
- Code Gear は \_\_code Code Gear で始まり、次の Code Gear へ goto で遷移する。

```c
_code clearSingleLinkedStack(struct SingleLinkedStack* stack,__code next(...)) {
    stack->top = NULL;
    goto next(...);
}

__code pushSingleLinkedStack(struct SingleLinkedStack* stack,union Data* data, __code next(...)) {
    Element* element = new Element();
    element->next = stack->top;
    element->data = data;
    stack->top = element;
    goto next(...);
}
```

# メタ計算

- メタ計算は通常の計算のための計算である
- 並列処理の依存関係の解決、GPUなどのアーキテクチャ実行のための処理を行う。
- Gears OSではメタ計算は Meta Code Gear、Meta Data Gear で表現される。

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

# Gears OS

- Gears OS は Code Gear、Data Gearの単位を用いて開発されており、CbCで記述される。
- Meta Code Gear は 通常の Code Gear の直後に遷移され、メタ計算を実行する。
- Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。
- stub によってMeta Code Gear から

# Gears OS の並列性

- Code Gear が処理するのに必要な Input Data Gear と処理実行後に出力される Output Data Gear の組を Task と呼ぶ。
- Code Gear は Task 以外とは依存関係がない
- 依存関係が明確化されている Code Gear Data Gear で記述することで、並列化し易い。

<div style="text-align: center;">
    <img src="./fig/codeGear_dataGear.svg" alt="message" width="550">
</div>


# Gears OS の構成

- Gears OS は以下の要素で構成される。
    - Context
    - TaskQueue
    - TaskManager
    - Worker

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

# Context

- Context は接続可能な Code Gear、Data Gear のリスト等を持っている Meta Data Gear である
- Gears OS は必要な Code Gear、Data Gear に参照したい場合、この Context を通す必要がある
- Context は 接続に必要な Code/Data Gear のリスト、 Data Gear を確保するためのメモリ空間、実行する Code Gear、実行に必要な Input Data Gear のカウンタ等をもっている
<!-- context のこーど？  -->

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

# TaskManager
- TaskManager は Task、Worker の生成
- Worker に生成した Task の送信
- 生成した Worker の終了処理等を行う

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

# Worker
- Worker は thread と実行する Task が入っている Queue を持っている
- TaskManager から送信された Task を Queue から取り出し、Code Gear を実行する
- Task は Context なので、Code Gear の実行に必要な Input Data Gear はその Context から参照される
- Code Gear を実行した後は出力される Output Data Gear から依存関係を解決する
<div style="text-align: center;">
    <img src="./fig/gears_structure.svg" alt="message" width="600">
</div>

# CUDA
- CUDA とは NVIDIA 社が提供している並列コンピューティング用の統合開発環境である。
- コンパイラ、ライブラリなどの並列コンピューティングを行うのに必要なサポートを提供している。
- CUDAを利用することで、もともとは画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用することができる
- GPUにはCPUに比べ多数のコアがあり、並列に処理することによってCPUよりも高速に処理を行うことができる
- CPUに比べ複雑な計算ができない、GPU単体に直接命令を書き込むこともできないなど、問題点も存在する。

# CUDAWoker
- Worker thread で動くTaskスケジューラーである。
- CUDAのライブラリの初期化を行う。
- GPU へのデータ転送及びGPU側でのTaskの実行はTaskのMeta Code Gear で行われる。
- Data Gear の待ち合わせ管理を行う。
- receive Task というAPI を持ち、Taskがなくなるまで繰り返す。

<!--
# CbC による Gears OS 記述の問題

- Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
- これらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
-->

<!-- 順番まだ考えてない

# interface の記述

- interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
- 呼び出される Code Gear の引数となる Data Gear はここで全て定義される。
- Code Gear、Data Gear に参照するために Context を通す必要があるが、interface を記述することでデータ構造の API と Data Gear を結びつけることが出来、 呼び出しが容易になった。

```c
typedef struct Stack<Impl>{
    union Data* stack;
    union Data* data;
    union Data* data1;
    __code whenEmpty(...);
    __code clear(Impl* stack,__code next(...));
    __code push(Impl* stack,union Data* data, __code next(...));
    __code pop(Impl* stack, __code next(union Data*, ...));
    __code pop2(Impl* stack, union Data** data, union Data** data1, __code next(union Data**, union Data**, ...));
    __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
    __code get(Impl* stack, union Data** data, __code next(...));
    __code get2(Impl* stack,..., __code next(...));
    __code next(...);
} Stack;
```

# stub Code Gear

- Code Gear が必要とする Data Gear を取り出す際に Context を通す必要があるが、Context を直接扱うのはセキュリティ上好ましくない。
- そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
- stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する間に挟まれる。

# stub Code Gear の生成

- stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
- stub Code Gear を 自動生成する generate stub を Perl スクリプトで作成することによって Code Gear の記述量を約半分にすることができる。
- stub を生成するために generate_stub は指定された cbc ファイルの __code型である Code Gear を取得し、引数から必要な Data Gear を選択する。
- generate_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
- また、この時既に stub Code Gear が記述されている Code Gear は無視される。
- cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。

# Context の生成

- generate_context は Context.h、Interface.cbc、generate_stub で生成されたImpl.cbc を見て Context を生成する Perl スクリプトである。

-->

# 依存関係の解決
- Gears での依存関係の解決は Data Gear にQueueをもたせることで行う
- Queue には その Data Gear を待っている Task が入っている
- Task は実行に必要な Input Data Gear のカウンタを持っており, Data Gear は書き出されると、依存関係にある Taskのカウンタをデクリメントする
- 全ての Input Data Gear が揃ったら, Taskを Worker に送信する

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

# Gears OSにおけるTask生成構文
- この記述方法では Meta Data Gearである Task を直接参照しているためノーマルレベルでの記述は好ましくなく、メタレベルでの記述を行いたい。
- そこで以下のような記述を新たに考案した。
- par goto は先に上げたCode1 に変換される記述であり、これによりノーマルレベルでは直接 Taskを参照せずに par goto の引数で Task の設定を行うことができる。
- この記述を拡張することでCPU GPUでの切り替えを行うことも可能であると考える。

```c
    par goto add(integer1, integer2, output, __exit);
```

# Task生成のメタレベルでの実装
- Task生成では新しくContextを生成し引数となるData　Segmentの設定を行う
- Context をactive Task Queue に挿入する

```c
__code createTask(TaskManager* taskManager, Context* task, Integer *integer1, Integer *integer2, Integer *output) {
    task->next = C_add; // set Code Gear
    task->idgCount = 2; // set Input Data Gear Counter
    task->data[task->idg] = (union Data*)integer1; // set Input Data Gear reference                                                                                   task->data[task->idg+1] = (union Data*)integer2;
    task->maxIdg = task->idg + 2;
    task->odg = task->maxIdg; // Output Data Gear index
    task->data[task->odg] = (union Data*)output; // set Output Data Gear reference
    task->maxOdg = task->odg + 1;
    taskManager->next = C_createTask1;
    goto meta(context, taskManager->taskManager->TaskManager.spawn); // spawn task
}

// code gear
__code add(Integer *integer1, Integer *integer2, Integer *output) {
    ....
}


```

# 従来のシステムとの比較
- 以下のシステムと比較していきます
- Microware OS/9 モジュール単位で実装されたりreal-time OS
- compiler directve を使用する HPC
- CUDA
- golang
- Aspect J

# Microware OS/9
-  モジュール単位で記述された real-time OS
- モジュール内部では普通のシステムコールを行う
- ユーザーレベルとシステムレベルの区別がある
- Gears OS はメタ計算のサポートがある
- データモジュールの待ち合わせなどの機能はOS/9にはない

# compiler directve
- C や Fortran のコードに並列用の指示を埋め込む手法
- 専用のコンパイラが用意される
- チューニングはコンパイラが用意された機能の範囲内で行う
- Gears OS ではメタ計算を使った個別のチューニングが可能

# CUDA
- NVIDIA GPGPU 用の並列計算ライブラリ
- 並列計算を行うカーネルとデータ転送を記述する部分からなる
- 細かい最適化を行う場合はDriver APIを用いる
- Gears OS ではCUDAのカーネルをそのまま Code Gear として使うことができる
- データ転送部分はメタレベルで記述する

# golang
- シンプルな構文を持つ並列言語
- go routine 単位で並列処理を行う
- データの単位としてunion が入っている
- go routine 間の通信はchannel を用いて行う
- Gears OSでは並列処理の実装はmeta Code Gear で行う
- 通信は Data Gear の待ち合わせで行う

# Aspect J
- Java用のメタ計算記述
- ポイントカットと呼ばれる方法でメタ計算を挟む位置を指定する
- 計算のログを取るのに使われている
- Code Gear ではCode segment　間の任意の位置にメタ計算を挿入することができる
- Aspect J よりも下位のメタ計算を記述することが可能

# まとめ
- Gears OS のメタ計算を用いた並列処理の実装について考察した
- CPUWoker とGPUWoker が稼働している
- ノーマルレベルでの記述からstub とContext そしてメタ計算部分を生成するスクリプトを作成した
- 他のシステムとの比較を行った
- 今後は実装の詳細化、raspberry pi への実装
- メタ計算を用いたプログラム検証などを行っていく