title: Monad に基づくメタ計算を基本とする Gears OS の設計
author: 小久保翔平
profile: 琉球大学大学院修士2年

# Gears OS の並列性
処理とデータの単位として Code Gear, Data Gear を用いる

　並列実行の単位となる

　処理とデータの関係から依存関係を決定

Many Core CPU, GPU, Xeon Phi などを有効に利用するためにはそれぞれのアーキテクチャに合わせた記述が必要

Gears OS では Gear を用いて並列実行環境に合わせた設計・実装を行う

# Gears OS の柔軟性      
Gear を追加することでデータ拡張や機能の追加が可能

バージョンが異なる Gears OS でもの Gear 共通部分を用いて通信を行う

# Gears OS の信頼性
Code/Data Gear にはメタ計算に必要な情報として Meta Code/Data Gear が付属されている

　関数型言語における Monad に相当

プログラムに対してメタレベルで Model Checking する

　元のプログラムに影響を与えない

　並列実行時のデッドロック検出

　Code Gear 間での型検査

# Cerium
Cerium では Task という分割された処理を依存関係に沿って並列実行する

Task 同士の依存関係はプログラマ自身が記述する

　Task の種類が増えるほど記述が複雑になる

Task 間の依存関係にのみ着目

　データの依存関係を正しく保証しない

Task が取り扱うデータに型情報がない

　汎用ポインタを型変換して利用

　型検査できない

# Alice
Alice では処理とデータの単位として Code Segment, Data Segment を用いる

処理とデータの関係から Code Segment 間の依存関係が決定

Data Segment を待ち合わせて Code Segment を実行することを Computaion と定義

Computaion を実現する Computaion を Meta Computaion と定義

　切断や再接続時の処理、データの圧縮の機能などが相当

　通常の Computaion に影響しない

　Meta Computaion 自体は Alice で記述されていない

Data Segment にアクセスする API が設計上の問題で複雑化している

# Code/Data Gear
通常レベルとして Code/Data Gear を用いる

　ポインタを扱わない

Code Gear は処理そのもの

　OpenCL/CUDA の kernel に相当

　接続された複数の Input Data Gear を参照

　単一または複数の Output Data Gear に書き出す

　自分が知らない Code/Data Gear は名前で指し示す

Data Gear はデータそのもの

　C の構造体で表現

　Primitive Data Type を格納

# Meta Code/Data Gear
メタレベルとして Meta Code/Data Gear を用いる

　ポインタを扱う

各 Gear の関連付け

Model Checking

平行制御

# Gear を用いた List の表現
通常 List は要素と次へのポインタを持つ構造体で表現する

Gears OS では任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List を表現する

![List](pictures/List.svg){: style="width: 70%"}

# Code/Data Gear の性質
ポインタの使用を通常レベルとメタレベルで分離

　ポインタ関連のセキュリティフローを防止

処理が Code/Data Gear に閉じている

　接続された Gear のみに干渉できる

　処理の実行時間、メモリ使用量が予測可能

# Gears OS における Meta Computation
関数型言語における Monad に基づいて Meta Computation を行う

　Monad を用いる手法は Moggi らが提案

Gears OS の Meta Computation は Meta Code/Data Gear を用いる

# 実装言語
本研究室で開発している Continuation based C(CbC) で実装

　LLVM をバックエンドした CbC コンパイラを用いる

CbC ではプログラムを Code Segment, Data Segment という単位で記述


Code Segment 間の処理の移動は goto を用いた軽量継続

　末尾最適化を強制

# Context
実行に必要な情報をまとめた Context を生成

　OS の Process, Thread に相当

　メタレベル

Code Gear の名前とポインタの対応

Data Gear を Allocate するための情報

Code Gear が参照する Data Gear へのポインタ

Data Gear に格納される Data Type の情報

![arch](pictures/GearsOS_arch.svg){: style="width: 50%"}

# Context
```
/* Context definition */
enum Code {
    Code1,
    Code2,
    Allocator,
};
```

実行可能な Code Gear の名前を enum Code で宣言

初期化時に名前と関数ポインタを対応付ける

# Context
```
enum UniqueData {
    Allocate,
    Tree,
};
```

初期化時に確保する Data Gear を enum UniqueData で宣言

# Context
```
struct Context {
    int codeNum;
    __code (**code) (struct Context *);
    void* heap_start;
    void* heap;
    long dataSize;
    int dataNum;
    union Data **data;
};
```

実行可能な Code Gear の数を示す codeNum

実行可能な Code Gear へのポインタ code

Data Gear の Allocate 用のポインタ heap_start, heap, dataSize

Data Gear の数を示す dataNum

Data Gear へのポインタ data

# Data Gear
```
union Data {
    struct Tree {
        // Tree member definition
    } tree;
    struct Node {
        // Node member definition
    } node;
    struct Allocate {
        long size;
        enum Code next;
    } allocate;
};
```

Data Gear は C の共用体と構造体を用いた表現する

# Persistent Data Gear
Data Gear の管理には木構造を用いる

非破壊で構成する

　平行して読み書き・参照を行うことが可能

　変更前の木構造をすべて保持しているので過去のデータにアクセス可能

![arch](pictures/GearsOS_arch.svg){: style="width: 50%"}

# Worker
Worker は Synchronized Queue から実行する Code Gear を取得

実行に必要な Data Gear は Persistent Data Gear から読み込む

処理が完了したら Persistent Data Gear に書き込む

![arch](pictures/GearsOS_arch.svg){: style="width: 50%"}

# Synchronized Queue
List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する

Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する

M:receiver/sender が CAS を行う Meta Code Gear となる

![sync](pictures/synchronizedQueue.svg){: style="width: 80%"}

# Code Gear の例
```
// Code Gear
__code code1(struct Context* context) {
    context->data[Allocate]->allocate.size = sizeof(struct Node);
    context->data[Allocate]->allocate.next = Code2;
    goto meta(context, Allocate);
}
```

必要な情報を Data Gear に書き込み Allocate を行う Code Gear に接続する Code Gear

ポインタを扱っており設計思想と異なる

# Code Gear の例
```
// Code Gear
__code code1(Allocate allocate) {
    allocate.size = sizeof(long);
    allocate.next = Code2;
    goto Allocate(allocate); // goes through meta
}
```

前の Code Gear として解釈するように CbC コンパイラを改良する

# 比較
Code Gear

　Cerium の Task

　Alice の Code Segment

　OpenCL/CUDA の kernel

Data Gear

　Alice の Data Segment

　Ceirum, OpenCL/CUDA には同等のものはない

Gears OS は Alice と同様に処理とデータの関係から依存関係を決定

Cerium, OpenCL/CUDA では処理同士の依存関係を記述する

　データの依存関係を保証できない

# 今後の課題
Cerium と同様の例題を動かし比較・評価

　Sort

　Word Count

　FFT

GPGPU のサポート

# まとめ
処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった

Gear という単位を用いて記述することでプログラムを柔軟に変更することを可能とした

Meta Code/Data Gear を用いて Meta Computation を実現する

Meta Computation の一つとして Model Checking を行う