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


# 測定結果
* OS X(10.10.5)
* 2.3 GHz Intel Core i7
* length：1310720
* cpus/(length/task)/time
  * 1/10/0.164748s
  * 2/10/0.230114s
  * 4/10/0.479126s
  * 8/10/0.553448s
  * 1/81920/0.010666s
  * 2/81920/0.005303s
  * 4/81920/0.002657s
  * 8/81920/0.002521s