--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/gearsos.tex	Wed Feb 17 16:59:46 2016 +0900
@@ -0,0 +1,239 @@
+\chapter{Gears OS}
+Cerium と Alice の開発を通して得られた知見から並列分散処理には Code の分割だけではなく Data の分割も必要であることがわかった。
+当研究室で開発している Code Segment を基本的な処理単位とするプログラミング言語 Continuation based C(CbC) を用いて Data Segment を定義し、Gears OS の設計と基本的な機能の実装を行なった。
+
+本章では Gears OS の設計と実装した基本的な機能について説明する。
+\section{Code Gear と Data Gear}
+Gears OS ではプログラムの単位として Gear を用いる。
+Gear は並列実行の単位、データの分割、Gear 間の接続等になる。
+
+Code Gear はプログラムの処理そのものになる。
+これは OpenCL/CUDA の kernel, Cerium の Task に相当する。
+Code Gear は任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込む。
+Code Gear は接続された Data Gear 以外にアクセスできない。
+Code Gear から次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定することで実現できる。
+Code Gear は Code Segment そのものである。
+
+Data Gear はデータそのものを表す。
+int や文字列などの Primitive Data Type を持っている。
+
+Gear の特徴として処理やデータの構造が Code Gear, Data Gear に閉じていることにある。
+これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
+
+\newpage
+
+\section{Gears OS の構成}
+Gears OS は以下の要素で構成される。
+\begin{itemize}
+\item Context \\
+  接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Data Gear のためのメモリ空間等を持っており、Context を通してアクセスすることができる。
+  メインとなる Context と Worker 用の Context があり、TaskQueue と Persistent Data Tree は共有される。
+  Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
+  Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。
+\item TaskQueue \\
+  ActiveTaskQueue と WaitTaskQueue の2つの TaskQueue を持つ。
+  先頭と末尾の Element へのポインタを持つ Queue を表す Data Gear である。
+  Element は Task を表す Data Gear へのポインタと次の Element へのポインタを持っている。
+  Compare and Swap(CAS) を使ってアクセスすることでスレッドセーフな Queue として利用することが可能になる。
+\item TaskManager \\
+  Task には Input Data Gear, Output Data Gear が存在する。
+  Input/Output Data Gear から依存関係を決定し、TaskManager が解決する。
+  依存関係が解決された Task は WaitTaskQueue から ActiveTaskQueue に移される。
+  TaskManager はメインとなる Context を参照する。
+\item Persistent Data Tree \\
+  非破壊木構造で構成された Lock-free なデータストアである。
+  Red-Black Tree として構成することで最悪な場合の挿入・削除・検索の計算量を保証する。
+\item Worker \\
+  TaskQueue から Task の取得・実行を行う。
+  Task の処理に必要なデータは Persistent Data Tree から取得する。
+  処理後、必要なデータを Persistent Data Tree に書き出して再び Task の取得・実行を行う。
+\end{itemize}
+
+図:\ref{fig:gearsos} は Gears OS の構成図である。
+
+\newpage
+
+\begin{figure}[!ht]
+  \begin{center}
+    \includegraphics[scale=0.35]{./images/gearsos.pdf}
+  \end{center}
+  \caption{Gears OS}
+  \label{fig:gearsos}
+\end{figure}
+
+\section{Allocator}
+Gears OS では Context の生成時にある程度の大きさのメモリ領域を確保する。
+Context には確保したメモリ領域を指す情報が格納される。
+このメモリ領域を利用して Task の実行に必要な Data Gear を生成する。
+
+Context の定義と生成はソースコード:\ref{context},ソースコード:\ref{initcontext} の通りである。
+
+\lstinputlisting[label=context, caption=Context]{src/context.h}
+\lstinputlisting[label=initcontext, caption=initContext]{src/initContext.c}
+
+\newpage
+
+Context はヒープサイズを示す heapLimit, ヒープの初期位置を示す heapStart, ヒープの現在位置を示す heap を持っている。
+必要な Data Gear のサイズに応じて heap の位置を動かすことで Allocation を実現する。
+
+allocate を行うには allocate に必要な Data Gear に情報を書き込む必要がある。
+この Data Gear は Context 生成時に生成する必要があり、ソースコード:\ref{context} 14行目の Allocate がそれに当たる。
+UniqueData で定義した Data Gear は Context と同時に生成される。
+
+Temporal Data Gear にある Data Gear は基本的には破棄可能なものなので heapLimit を超えたら heap を heapStart の位置に戻し、ヒープ領域を再利用する(図:\ref{fig:allocation})。
+必要な Data Gear は Persistent Data Tree に書き出すことで他の Worker からアクセスすることが可能になる。
+
+\begin{figure}[!ht]
+  \begin{center}
+    \includegraphics[scale=0.4]{./images/allocation.pdf}
+  \end{center}
+  \caption{Allocation}
+  \label{fig:allocation}
+\end{figure}
+
+実際に allocate を行う Code Gear はソースコード:\ref{allocate} の通りである。
+
+Context 生成時に実行可能な Code Gear と名前が対応付けられる。
+その対応付けられた Code Gear が Context の code に格納される。
+この code を介して遷移先の Code Gear を決定する。
+
+Code Gear には Context が接続されるが Context を介して Data Gear にアクセスすることはない。
+stub を介して間接的に必要な Data Gear にアクセスする。
+
+\lstinputlisting[label=allocate, caption=allocate]{src/allocate.c}
+
+\section{Synchronized Queue}
+Gears OS における Synchronized Queue は TaskQueue として利用される。
+メインとなる Context と Worker 用の Context で共有され、Woker が TaskQueue から Task を取得し実行することで並列処理を実現する。
+
+Gears OS での Queue を Queue を表す Data Gear と Queue の構成要素である Element によって表現する。
+Queue を表す Data Gear には先頭の Element を指す first, 末尾の Element を指す last, Element の個数を示す count が格納される。
+Element を表す Data Gear には Task を示す task, 次の Element を示す next が格納される。
+
+ソースコード:\ref{queue} は Context の定義(ソースコード:\ref{context})に追加する Queue と Element の定義である。
+
+\lstinputlisting[label=queue, caption=Context: queue]{src/queue.h}
+
+新たに Queue に対する操作を行う Code Gear の名前を追加し、UniqueData には Queue の情報が入る Queue(ソースコード:\ref{queue} 9行目) と Enqueue に必要な情報を書き込む Element(ソースコード:\ref{queue} 10行目) を定義している。
+
+通常の Enqueue, Dequeue を行う Code Gear はソースコード:\ref{enqueue} と ソースコード:\ref{dequeue} の通りである。
+
+\lstinputlisting[label=enqueue, caption=Enqueue]{src/enqueue.c}
+\lstinputlisting[label=dequeue, caption=Dequeue]{src/dequeue.c}
+
+ソースコード:\ref{enqueue} とソースコード:\ref{dequeue} はシングルスレッドでは正常に動作するが、マルチスレッドでは期待した動作を達成できない可能性がある。
+並列実行すると同じメモリ位置にアクセスされる可能性があり、データの一貫性が保証できないからである。
+データの一貫性を並列実行時でも保証するために Compare and Swap(CAS) を利用して Queue の操作を行うように変更する必要がある。
+CAS はデータの比較・置換をアトミックに行う命令である。
+メモリからのデータの読み出し、変更、メモリへのデータの書き出しという一連の処理を、CAS を利用することで処理の間に他のスレッドがメモリに変更を加えていないということを保証することができる。
+CAS に失敗した場合は置換は行わず、再びデータの読み出しから始める。
+
+ソースコード:\ref{enqueue} 44行目の putQueue3, 51行目の putQueue4, ソースコード:\ref{dequeue} 2行目の getQueue が実際に Queue を操作している Code Gear である。
+これらの Code Gear から CAS を利用したソースコード:\ref{sync_enqueue}, ソースコード:\ref{sync_dequeue} の Code Gear に接続を変更することでスレッドセーフな Queue として扱うことが可能になる。
+Code Gear は Gears OS における最小の処理単位となっており、接続を変更することでプログラムの振る舞いを柔軟に変更することができる。
+
+\lstinputlisting[label=sync_enqueue, caption=Enqueue using CAS]{src/sync_enqueue.c}
+\lstinputlisting[label=sync_dequeue, caption=Dequeue using CAS]{src/sync_dequeue.c}
+
+\section{Persistent Data Tree}
+Gears OS では Persistent Data Gear の管理に木構造を用いる。
+この木構造は非破壊で構成される。
+非破壊木構造とは一度構築した木構造を破壊することなく新しい木構造を構築することで、木構造を編集する方法である。
+非破壊木構造は木構造を書き換えることなく編集を行う(図:\ref{fig:non-destructive_tree})ため、読み書きを平行して行うことが可能である。
+赤色で示したノードが新しく追加されたノードである。非破壊木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。
+そして、パス上に存在しないノードはコピー元の木構造と共有することである。
+
+\newpage
+
+\begin{figure}[!h]
+  \centering
+  \includegraphics[scale=0.7]{images/nondestructive_tree_modification.pdf}
+  \caption{木構造の非破壊的編集}
+  \label{fig:non-destructive_tree}
+\end{figure}
+
+木構造はディレクトリツリー、構文木など階層構造を持つデータを表現する。
+またはデータベースのインデックスなど情報を探索しやすくするための探索木としても用いられる。
+Gears OS では Data Tree として木構造を利用する。
+その場合、普通に木構造を構築するだけでは偏った木構造が構築される可能性がある。
+最悪なケースでは事実上の線形リストになり、計算量が O(n) となる。
+挿入・削除・検索における処理時間を保証するため Red-Black Tree を用いて木構造の平衡性を保証する。
+
+Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。
+
+\begin{itemize}
+\item 各ノードは赤または黒の色を持つ。
+\item ルートの色は黒である。
+\item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。
+\item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。
+\end{itemize}
+
+これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。
+
+Red-Black Tree は挿入・削除を行ったあとに変更したノードからルートへのパスを辿りながら Red-Black Tree の条件を満たすように色の変更や木の回転を行う。
+関数呼び出しが可能なプログラミング言語では戻り値でパスを辿ることができるが、CbC は末尾呼び出し最適化が行われるように記述する必要があるのでパスを辿るにはノードに親への参照を持たせるか挿入・削除時に辿ったパスを記憶するしかない。
+ノードが親への参照を持つと非破壊木構造を構築することが出来ないので、辿ったパスを記憶する方法を用いる。
+辿ったパスを記憶するため Context にスタックを持たせる。
+
+ソースコード:\ref{tree}は Context に追加する Tree, Node および Tree の操作を行う Code Gear 名の定義である。
+
+\lstinputlisting[label=tree, caption=Context: Red-Black Tree]{src/tree.h}
+
+Tree は参照する木を格納する Code Gear である。
+この Code Gear は Context の生成時に生成される。
+Traverse は木の探索に用いられる Code Gear である。
+Code Gear は末尾最適化されるので呼び出し元の情報が残らない。
+参照しているノードの情報を Code Gear 間で持ち歩くためには Traverse のような Data Gear が必要になる。
+
+赤ノードが続かないという Red-Black Tree の条件を満たすか判定する Code Gear はソースコード:\ref{insert}の通りである。
+まず、親の情報が必要なのでパスを記憶しているスタックから親ノードを取得する。
+親ノードが黒である場合、木を回転する必要はなく木は平衡を保っているので木に対する操作を終了する。
+
+\lstinputlisting[label=insert, caption=Insert Case]{src/insert.c}
+
+木の左回転を行う Code Gear はソースコード:\ref{rotateLeft}の通りである。
+自分、親、兄弟の3点のノードの回転である。
+回転を行ったあとにも Red-Black Tree の条件を満たしているか確認する必要があるので回転後に変更された親ノードを再びスタックに記憶する。
+また、回転の際に現在見ているノードが変更する必要がある。
+
+\newpage
+
+\lstinputlisting[label=rotateLeft, caption=Rotate Left]{src/rotate.c}
+
+\section{Worker}
+Worker は TaskQueue から Task を取得し、実行する。
+Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。
+実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。
+
+各 Worker は個別の Context を参照している。
+メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。
+ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。
+
+Worker が Task の取得を行う Code Gear はソースコード:\ref{sync_dequeue}の通りである。
+TaskQueue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。
+Task の実行後に再び Task の取得を行う Code Gear に戻る必要がある。
+Context は実行する Code Gear のスタックを持っているのでそのスタックに積む(ソースコード:\ref{sync_dequeue} 11行目)ことで戻ることができる。
+
+Task に格納され Worker で実行される Code Gear はソースコード:\ref{task}の通りである。
+ソースコード:\ref{task}は指定された要素の値を2倍する Twice という例題である。
+Twice は並列実行される。
+
+\lstinputlisting[label=task, caption=Task Sample]{src/twice.c}
+
+並列処理される Code Gear と言っても他の Code Gear と完全に同じである。
+これは Gears OS 自体が Code Gear によって構成されていることに起因する。
+つまり、Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないときすべて並列に動作させることができるということを意味する。
+
+\section{TaskManager}
+Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。
+Task には Input/Output Data Gear の情報が格納されている。
+Input Data Gear は Task に必要な Data Gear で揃ったら Task は実行可能な状態になる。
+Output Data Gear は Task が Persistent Data Tree に書き出す Data Gear である。
+この Input と Output の関係が依存関係となる。
+TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。
+
+TaskManager は Worker の管理も行う。
+メインとなる Context には Worker の情報が格納されており、TaskManager はこの Context を参照して Worker の起動・停止を行う。
+ソースコード\ref{init_worker}は Worker を起動する Code Gear である。
+
+\lstinputlisting[label=init_worker, caption=InitWorker]{src/initWorker.c}