Cerium と Alice

Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラムを記述する。 +

Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラミングを行う。 Code Segment が取り扱う Input/Output Data Segment を指定することで処理とデータの関係を決定する

Alice では Computaion を Data Segment を待ち合わせて Code Segment を実行することと定義している。 +これに対し、Meta Computation は Computation を実現する Computation と定義することができる。 +通信中の切断や再接続の処理などは Meta Computation に相当する

Data Segment にアクセスする API が設計上の問題で複雑化している。 -また、Java で実装されており、実行速度が遅いという問題がある

- - - -

- -

Gears OS

- - -

本研究では Cerium と Alice を開発して得られた知見から並列分散フレームワーク Gears OS の設計・開発を行う

- -

Gears OS では Alice の Code/Data Segment に相当する Code/Data Gear という単位を用いてプログラムを細かく分割する。 -Code Gear は Input Data Gear から Output Data Gear を生成する。 -Input/Output Data Gear の関係から Code Gear 間の依存関係を決定し、並列・分散処理を行う

+また、Meta Computation 自体が Alice で記述されていない

@@ -94,48 +102,7 @@

Gears OS

- - -

従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。 -関数型言語では Meta Computation に Monad を用いる手法があり、Gears OS では Code/Data Gear を Monad として定義して Meta Computation を実現する

- -

並列実行の信頼性を確保するため Gears OS では作成されたプログラムに対して Model Checking を行う。 -並列プログラムに Model Checking を行うことでそのプログラムが取り得る状態を列挙する。 -これにより、デッドロック等を検出することで信頼性を確保する

- - - -

- -

Features

- - -

Inherent Parallel

- -

Distributed Open Computation

- -

Reliablity

- -

　Separated Data Segment

- -

　Model Checking

- - - -

- -

Code/Data Gear

Code Gear と Data Gear

@@ -146,6 +113,52 @@ 接続された複数の Input Data Gear を参照し、単一または複数の Output Data Gear に書き込む。 Code Gear では接続された Data Gear のみに干渉することができる

Data Gear には、Primitive Data Type が格納される。 +直接ポインタを扱うことはなく、自分が知らない Code/Data Gear は名前で指し示す

+ +

Gear の特徴の一つとしてその処理が Code/Data Gear に閉じていることがある。 +これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする

+ + + +

+ +

Monad と Meta Computation

+ + +

関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるものがある。 +メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副作用、メモリ管理などがある。 +メタ計算の理論的な表現として Monad を用いることが Moggi らにより提案されている

+ +

Moand は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するのに必要な情報を格納している。 +失敗する計算の場合は、計算が失敗したかどうかのフラグが Monad に含まれる。 +通常の計算を Monad を返すように変更することでメタ関数が得られる。 +逆に Monad の中にある通常の値のみに着目すると通常の関数となる

+ + + +

+ +

Gears OS における Meta Computation

+ + +

Gears OS では Code/Data Gear に Meta Code/Data Gear を付属することで Monad を表現する。 +Meta Code/Data Gear は Code/Data Gear へのポインタを持っている。 +各 Gear の関連付けは Meta Gear を用いて行われる

+ +

オブジェクトレベルである Gear ではポインタを扱わず、メタレベルである Meta Gear でのみポインタを扱う。 +これにより、ポインタ関連のセキュリティフローを防止する。

@@ -154,14 +167,16 @@

Code Data Gear

実装言語

Code/Data Gear ではポインタを直接には扱わず、Code と Data の分離性を上げることで、ポインタ関連のセキュリティフローを防止する

Gears OS の実装には、本研究室で開発している Continuation based C(CbC) を用いる

Gear の特徴の一つとしてその処理が Code/Data Gear に閉じていることがある。 -これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。

CbC ではプログラムを Code Segment, Data Segment という単位で記述する。 +Code Segment 間の処理の移動には関数呼び出しではなく、goto を用いた軽量継続を用いている

+ +

CbC のコンパイルには LLVM をバックエンドとしたコンパイラを用いる

@@ -171,11 +186,16 @@

list

Gears OS の構成

List

arch

+ +

Gears OS では Context を生成し、Worker を起動する。 +Worker は Synchronized Queue から Code Gear を取得し、実行する。 +実行に必要な Data Gear は Context を通して、Persistent Data Gear から読み込みを行う。 +処理が終わると必要な Data Gear を Persistent Data Gear に書き込みを行う

@@ -185,27 +205,15 @@

singly linked list の実装

Code Gear の継続

Context -
- list の先頭を示す head
-
DataSegment -
- 任意
-
MetaDataSegment -
- 次の mds を示す next
-

Code Gear では、次に実行する Code Gear を名前で指定する。 +Meta Code Gear が名前を解釈して、対応する Code Gear に引き渡す。 +Gear OS では、この Meta Code Gear を Context と定義する

+ +

Context には Code Gear の名前とポインタの対応表、Data Gear の Allocation 用の情報、Code Gear が参照する Data Gear へのポインタ、Data Gear に格納される Data Type の情報が格納されている

@@ -215,27 +223,227 @@

操作

Persistent Data Gear

+ + +

Data Gear の管理には木構造を用いる。 +この木構造は非破壊で構成される。 +非破壊的木構造では、ロックなしに平行して読み書き・参照を行うことが可能である

+ +

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

+ + + +

+ +

List

+ + +

通常 List は要素と次へのポインタを持つ構造体で表現される

+ +

Gears OS の場合、オブジェクトレベルではポインタを扱わないので、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される

+ +

List

+ + + +

+ +

Synchronized Queue

+ + +

Gears OS では 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

+ + + +

+ +

Context

+ + +

/* Context definition */
+enum Code {
+    Code1,
+    Code2,
+    Allocator,
+};
+
+enum UniqueData {
+    Allocate,
+    Tree,
+};
+
+struct Context {
+    int codeNum;
+    __code (**code) (struct Context *);
+    void* heap_start;
+    void* heap;
+    long dataSize;
+    int dataNum;
+    union Data **data;
+};
+

+ + + +

+ +

Code Gear

append -
- head から探索して末尾に新たな DS を追加
-
delete -
- head を next に変更
-
traverse -
- list を先頭から表示
-

// Code Gear
+__code code1(Allocate allocate) {
+    allocate.size = sizeof(long);
+    allocate.next = Code2;
+    goto Allocate(allocate); // goes through meta
+}
+
+// Meta Code Gear
+__code meta(struct Context* context, enum Code next) {
+    // meta computation
+    goto (context->code[next])(context);
+}
+
+// Meta Code Gear
+__code allocate(struct Context* context) {
+    context->data[++context->dataNum] = context->heap;
+    context->heap += context->data[Allocate]->allocate.size;
+    goto (context->code[context->data[Allocate]->allocate.next])(context);
+}
+
+// Code Gear
+__code code2(Allocate allocate, Count count) {
+    // processing
+}
+

+ +

// 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);
+}
+
+// Meta Code Gear
+__code meta(struct Context* context, enum Code next) {
+    // meta computation
+    goto (context->code[next])(context);
+}
+
+// Meta Code Gear
+__code allocate(struct Context* context) {
+    context->data[++context->dataNum] = context->heap;
+    context->heap += context->data[Allocate]->allocate.size;
+    goto (context->code[context->data[Allocate]->allocate.next])(context);
+}
+
+// Code Gear
+__code code2(struct Context* context) {
+    // processing content
+}
+

+ + + +

+ +

Data Gear

+ + +

union Data {
+    struct Tree {
+        union Data* root;
+        union Data* current;
+        union Data* prev;
+        int result;
+    } tree;
+    struct Node {
+        int key;
+        int value;
+        enum Color {
+            Red,
+            Black,
+        } color;
+        union Data* left;
+        union Data* right;
+    } node;
+    struct Allocate {
+        long size;
+        enum Code next;
+    } allocate;
+};
+

+ + + +

+ +

比較

+ + +

Code Gear は Cerium の Task、Alice の Code Segment, OpenCL/CUDA の kernel に相当する

+ +

Data Gear は Alice の Data Segment に相当する。 +Ceirum, OpenCL/CUDA には Data Gear に相当する物は存在しない

+ +

Cerium, OpenCL/CUDA では処理同士の依存関係を記述する必要があるが、Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する

+ + + +

+ +

まとめ

+ + +

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

+ +

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

+ +

Meta Computation を Moand に基づいて実現する。 +Gears OS では Meta Code/Data Gear を用いて Monad を表現する

+ +

機能として Model Checking を提供し、プログラムの信頼性を確保する