Binary file paper/sigos.pdf has changed

--- a/paper/sigos.tex	Sun May 08 16:06:04 2016 +0900
+++ b/paper/sigos.tex	Sun May 08 19:27:32 2016 +0900
@@ -281,7 +281,7 @@
 この Input と Output の関係が依存関係となる。
 TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。
 
-\section{評価}
+\section{プロトタイプの動作}
 Gears OS の評価として依存関係のない例題の並列実行を行った。
 
 今回使用した例題は Twice という整数配列を2倍にする例題である。
@@ -340,6 +340,82 @@
 しかし、 タスクの粒度が小さすぎると CAS の失敗が多くなり、性能がでないことがある。
 Code Gear には実行時間を予想可能なものにするという特徴があるため、タスクが最適な粒度なのかを検査する機能が必要になると考えられる。
 
+\section{比較}
+本章では今回設計・実装した Gears OS と既存の並列フレームワークとの比較を行う。
+また、Gears OS は以下のような性質を有している。
+
+\begin{itemize}
+\item リソース管理 \\
+  Context 毎に異なるメモリ空間を持ち、それを管理する。
+  Meta Code Gear, Meta Data Gear を用いてネットワーク管理、並行制御等を行う。
+\item 処理の効率化 \\
+  依存関係のない Code Gear は並列実行することが可能である。
+  また、Code Gear 自体が処理の最小単位となっており Code Gear を利用してプログラムを記述するとプログラム全体の並列度を高めることに繋がる。
+\item プロセッサ利用の抽象化 \\
+  Multi Core CPU, GPU を同等の実行機構で実行可能である。
+\end{itemize}
+
+これらの性質を有する Gears OS はオペレーティングシステムであると言えるので既存の OS との比較も行う。
+
+\paragraph*{Cerium}
+\begin{itemize}
+\item 依存関係 \\
+  Cerium では Task 間で依存関係を設定する。
+  Task の途中でデータが破損しても完了を TaskManager に通知し、依存関係を解決して次の Task が実行される。
+  これではデータの正しさを保証することができない。
+
+  Gears OS では Task に Input/Output Data Gear を設定することで Input と Output の関係から依存関係を決定する。
+  TaskManager は Persistent Data Tree を監視し、必要な Data Gear が揃っていることを確認すると依存関係を解決する。
+\item データの型情報 \\
+  Cerium では Task にデータを引き渡すとき汎用ポインタを用いる。
+  このときデータの型情報が落ちるので Task の組み合わせが型的に安全なのか保証することができない。
+
+  Gears OS では型情報を持つ分割されたデータとして Data Gear を定義し、Data Gear 単位でデータを Task に引き渡す。
+  Data Gear を型シグネチャとして Task の組み合わせが正しいことを保証する。
+\item Allocator \\
+  Cerium では Thread 間で Allocator を共有している。
+  ある Thread がメモリ確保を行うとその間、他の Thread はメモリを確保することができず並列度が低下する。
+
+  Gears OS では Thraed ごとに Context を割り当てる。
+  Context は独立したメモリ空間を持つので他の Thread と干渉することないメモリの確保を行うことができる。
+\item 並列処理との相性 \\
+  Cerium はオブジェクト指向言語である C++ で実装されている。
+  オブジェクト指向は保守性と再利用性を高めるためにカプセル化とポリモフィズムを重視する。
+  オブジェクトの状態によって振る舞いが変わるため参照透過な処理でなくなり並列処理との相性が悪い。
+
+  Gears OS は本研究で開発している CbC を用いて実装する。
+  CbC は Code Segment という単位でプログラムを記述する。
+  Code Segment はスタックに値を積まない軽量継続を用いて他の Code Segment に遷移する。
+  この軽量継続により並列化、ループ制御などを意識した最適化がソースコードレベルで行うことができる。
+\end{itemize}
+
+\paragraph*{OpenCL/CUDA}
+OpenCL\cite{opencl}/CUDA\cite{cuda} では並列処理に用いる関数を kernel として定義する。
+OpenCL では CommandQueue, CUDA では Stream という命令キューに命令を発行することで GPU を利用することができる。
+命令キューは発行された順番通りに命令が実行されることが保証されている。
+複数の命令キューを準備して、各命令キューに命令を発行することで命令を並列に実行することができる。
+命令キュー単位で依存関係を設定することができる。
+つまり、命令キューに入っている最後の命令次第でデータを待っているのか kernel の実行を待っているのか変わるので依存関係の記述が複雑になる。
+データは kernel の引数の定義に型変換され渡される。
+データ転送の際には型情報が落として渡す必要があり、型を意識したプログラミングが必要になる。
+
+一方、Gears OS ではデータによって依存関係が決定する。
+また、データを Data Segment という単位で分割して管理しており型情報を保ったままデータの受け渡しを行うことができる。
+
+\paragraph*{OpenMP}
+OpenMP ではループ制御構文の前にアノテーションを付ける(Code \ref{openmp})ことでコンパイラが解釈し、スレッド処理を行うように変換して並列処理を行う。
+
+\lstinputlisting[label=openmp, caption=OpenMP]{src/openmp.c}
+
+他の並列化手法に比べて既存のコードに対する変更が少なくて済む。
+しかし、この方法ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになる。
+
+一方、Gears OS では初めから Code Gear, Data Gear という単位でプログラムを分割して記述するのでプログラム全体の並列度を高めることができる。
+
+\paragraph*{従来の OS}
+従来の OS が行ってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code/Data Gear として定義する。
+通常の Code Gear から必要な制御を推論し、Meta Code Gear を接続することで従来の OS が行ってきた制御を提供する。
+このメタ計算は関数型言語で用いられる Monad に基づいて実現する。
 \section{まとめ}
 本論文では Code Gear、 Data Gear  によって構成される Gears OS のプロトタイプの設計、実装を行った。
 
@@ -366,6 +442,8 @@
 
 また、型情報を残すために Data Gear を定義しているが、 Data Gear 野方情報を検査していない。
 プログラムの正しさを保証するために Data Gear の型情報を検査するシステムを 実装する必要がある。
+% GPU の方も書く
+% debug 手法
 
 \nocite{*}
 \bibliographystyle{ipsjunsrt}