接続可能な 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 の依存関係を解決する。
+
+
+
+
+
+
Cerium の構成
+
+
Worker
+
+
+
Worker は ActiveTaskQueue から Task を取得する。
+取得した Task の情報を元に必要な Data Gear を Persistent Data Tree から取得し、Code Gear を実行する。
+実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。
+
+
+
diff -r 0188222d2886 -r 4dcfec1bf1e7 slide/index.md
--- a/slide/index.md Wed Feb 17 20:29:45 2016 +0900
+++ b/slide/index.md Thu Feb 18 07:20:46 2016 +0900
@@ -21,22 +21,39 @@
![Cerium の構成](./pictures/createTask.svg)
-# Cerium の問題点(1/2)
+# Cerium の問題点
+* Task 間の依存関係
+
Cerium では Task 間の依存関係を設定することで並列処理を実現する。
しかし、本来 Task は必要なデータが揃うことで実行可能になるものである。
Task 同士の依存関係だけでは前の Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。
データがどこでおかしくなったのか特定するのは難しく、デバックに時間が取られる。
-# Cerium の問題点(2/2)
+* データの型情報
+
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 Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。
+
+Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C) を用いた。
# Code/Data Gear
Gears OS ではプログラムの単位として Gear を用いる。
@@ -49,7 +66,47 @@
Data Gear はデータそのものを表す。
int や文字列などの Primitive Data Type を複数持つ構造体として定義する。
-Gear 特徴として
+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
+
# 測定結果
* OS X(10.10.5)
diff -r 0188222d2886 -r 4dcfec1bf1e7 slide/pictures/gearsos.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/pictures/gearsos.svg Thu Feb 18 07:20:46 2016 +0900
@@ -0,0 +1,430 @@
+
+